### The algebra of processes V

SEQUENTIAL PROGRAMMING in Cospan(Graph) continued:

We are now not interested in the alphabet A, but just in writing sequential programs whose input/output behaviour yield partial functions, so we take A to be a one letter alphabet and ignore it.

There is an operation I have not introduced which strictly speaking is not in Cospan because it is a little bit of parallelism, which however does not involve any parallel communication. We will see later that it is an operation which involves Span and Cospan.

Consider a cospan of graphs X ← G → Y where the states of G have a given finite sum decomposition as U

Now given a set Z let l(Z) be the graph with vertex set Z and one loop at each vertex.

Then we can form a new span with set of states ZxU

If you write out this span explicitly you will see that you need the distributive law isomorphism of products over sums to define the new cospan.

We will call this new cospan ZxG.

What is the meaning of ZxG? Why is it needed in sequential programming? It is just the fact that you need to keep variables, Z in this case, in memory while you perform a behaviour of G.

I will show you how this comes up in describing the constructions "if then else" and "while".

(Before I forget there are two more constants you need for sequential programming (i) the diagonal function (copy) Z →ZxZ considered as a cospan and the function (forget) Z →I as a cospan.)

I will describe "if then else", "while" and "addition" just as pictures and let you think about why they are expressions in Cospan(Graph) and why they do what is implied by the names. Of course you will have realized by now that these pictures are formalization of flow charts in Cospan(Graph).

Note: In the pictures the lines indicate identification of state.

(The pictures area little crude and perhaps I should improve them.)

IF P THEN DO F ELSE G where P is a cospan from X to 1+1 and F and G are cospans from Y to Z.

WHILE P DO F where P is a cospan from Y to 1+1 and F is a cospan from Y to Y.

ADDITION: a program for computing addition from the cospans predecessor and successor described in an earlier post.

_{1}+U_{2}+...+U_{n}, which induces (as we have seen before) finite sum decompositions of X and Y as (say) X_{1}+..+X_{m}and Y_{1}+...+Y_{k}, and a decomposition of the vertices of G into spans G_{i,j}.Now given a set Z let l(Z) be the graph with vertex set Z and one loop at each vertex.

Then we can form a new span with set of states ZxU

_{1}+ZxU_{2}+...+ZxU_{n}, with left interface ZxX_{1}+ZxX_{2}+...+ZxX_{m}, right interface ZxY_{1}+ZxY_{2}+...+ZxY_{k}, with spans being l(Z)xG_{i,j}.If you write out this span explicitly you will see that you need the distributive law isomorphism of products over sums to define the new cospan.

We will call this new cospan ZxG.

What is the meaning of ZxG? Why is it needed in sequential programming? It is just the fact that you need to keep variables, Z in this case, in memory while you perform a behaviour of G.

I will show you how this comes up in describing the constructions "if then else" and "while".

(Before I forget there are two more constants you need for sequential programming (i) the diagonal function (copy) Z →ZxZ considered as a cospan and the function (forget) Z →I as a cospan.)

I will describe "if then else", "while" and "addition" just as pictures and let you think about why they are expressions in Cospan(Graph) and why they do what is implied by the names. Of course you will have realized by now that these pictures are formalization of flow charts in Cospan(Graph).

Note: In the pictures the lines indicate identification of state.

(The pictures area little crude and perhaps I should improve them.)

IF P THEN DO F ELSE G where P is a cospan from X to 1+1 and F and G are cospans from Y to Z.

WHILE P DO F where P is a cospan from Y to 1+1 and F is a cospan from Y to Y.

ADDITION: a program for computing addition from the cospans predecessor and successor described in an earlier post.

Labels: category theory, computing

## 0 Comments:

## Post a Comment

<< Home