Monday, January 15, 2007

Geometry, computation and reflection

Last night i discovered a geometric interpretation of the reflective versions of the λ- and π-calculi. It's 'simplicial' in nature. (For an implementation see: http://svn.biosimilarity.com/src/open/mirrororrim/rho/trunk/ocaml/ .)

For example, take the reflective version of the asynchronous π-calculus.














































P,Q::=0// stop, or nil process




x[|P|]// lift




x(y).P// blocking input




P|Q// parallel composition




*x// drop








x,y::=^P^// quote


Assign a dimension to each term constructor. Thus, we have




















0-dim
lift-dim
input-dim
par-dim
drop-dim
quote-dim


or 6 dimensions.

We define a recursive function, G[ - ]: L(P)xR2x5 → R6, assigning to each term a shape in 6 dimensions. The additional arguments are scale-factors and offsets for each term-constructor/dimension. For readability we will elide the additional argument, but for access, they are structured as a vector of pairs, ((ls,lo),(is,io),(ps,po),(ds,do),(qs,qo)), scale factor and offset for each dimension but the 0-dim.



























































G[0](…)=(0,0,0,0,0,0)






G[x[|P|]](…)={ (r0,...,r5) |
let cx = barycenter(G[x](…)) in
let cp = barycenter(G[P](…)) in
let ct = vertex equidistant to cx, cp and perpendicular to [cx,cp] in lift-direction in
(r0,...,r5) in ls[cx,cp,ct] + lo }






G[x(y).P](…)={ (r0,...,r5) |
let cx = barycenter(G[x](…)) in
let cy = barycenter(G[y](…)) in
let cp = barycenter(G[P](…)) in
let ct = vertex equidistant to cx, cy, cp and perpendicular to [cx,cy,cp] in input-direction in
(r0,...,r5) in is[cx,cy,cp,ct] + io}






G[P|Q](…)={ (r0,...,r5) |
let cp = barycenter(G[P](…)) in
let cq = barycenter(G[Q](…)) in
let ct = vertex equidistant to cp, cq and perpendicular to [cp,cq] in the par-direction in
(r0,...,r5) in ps[cp,cq,ct] + po }






G[*x](…)={ (r0,...,r5) |
let cx = barycenter(G[x](…)) in
let ct = vertex unit length from cx in drop-direction in
(r0,...,r5) in ds[cx,ct] + do }






G[^P^](…)={ (r0,...,r5) |
let cp = barycenter(G[P](…)) in
let ct = vertex unit length from cp in quote-direction in
(r0,...,r5) in qs[cp,ct] + qo }


i believe that this will yield interesting visualizations of the terms of this calculus if we assign 3 dims to x,y,z and 3 dims to pitch, roll and yaw. The dynamics of execution will yield animations.

1 comment:

Unknown said...

Should each 6-tuple be though of as a point or a vector (if using the (x, y, z, yaw, pitch, roll) coordinates)?

I'm somewhat curious as to what a simple data structure such as a linked-list or tree would look like over time in this kind of geometry.