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 U1+U2+...+Un, which induces (as we have seen before) finite sum decompositions of X and Y as (say) X1+..+Xm and Y1+...+Yk, and a decomposition of the vertices of G into spans Gi,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 ZxU1+ZxU2+...+ZxUn, with left interface ZxX1+ZxX2+...+ZxXm, right interface ZxY1+ZxY2+...+ZxYk, with spans being l(Z)xGi,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.
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 ZxU1+ZxU2+...+ZxUn, with left interface ZxX1+ZxX2+...+ZxXm, right interface ZxY1+ZxY2+...+ZxYk, with spans being l(Z)xGi,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
posted by Unknown at 11:42 PM
0 Comments:
Post a Comment
<< Home