From combinators and zippers to interaction graphs (part I)

In the post Combinators and zippers I gave a description of the SKI combinators and their fundamental relations in terms of zippers.  See the tutorial page on graphic lambda calculus for background.

As a conclusion of the post  on combinators and zippers, let me mention that the I and K combinators appear as “half” of the 1-zipper and 2-zipper respectively, with some wires and termination gates added. The combinator S appears as a half of the 3-zipper with a “diamond” added, which in fact serves to generate more zippers when composed with other combinators.

Looks like gibberish? Here is for example the relation SKK \rightarrow I, as deduced in graphic lambda calculus, by using zippers:

zipper_6

Looks like I did it without using GLOBAL FAN-OUT! The point is that we may transform combinatory logic into a calculus with zippers, half-zippers (see how the left half zipper from the expression of K, made by two \lambda gates, couples to form a 2-zipper with the right-half zipper made by two \curlywedge gates from the “diamond”) and some wires and termination gates.

Here comes the more interesting part: could we do it with zippers written in terms of emergent algebras and by using the dual of the graphic beta move instead?

I shall first explain what a zipper in emergent algebra is. Look at the next figure to see one:

zipper_7

This is 3-zipper written with the help of the emergent algebra crossing macro. It unzips by using three \beta^{*}(\varepsilon) moves.

The problem with this zipper is that it is not at all clear what a half of it might be. Related to this is the fact that we can “unzip” independently each of the parts of the zipper, there is no order of zipping-unzipping, because we already have all the patterns needed to apply the dual of the graphic beta move. This is a different situation, compared to the one of the usual zipper. In the usual zipper case, that zipper is in fact made by two halves, one containing the \lambda gates, the other half containing the \curlywedge  gates; there is only one place where we can apply the graphic beta move and after the application of this move appears a new pattern proper for the application of the next graphic beta move and so on, until the zipper becomes unzipped.

In the extreme case of the 1-zipper, which is nothing but the pattern for the application of the graphic beta move, we can identify the \lambda  gate with the left half of the zipper and the \curlywedge gate with the right half of the zipper. On the contrary, we can’t do anything comparable to this for the 1-zipper from emergent algebras.

A solution which could get us out of this problem (and therefore one which would allow to do combinatory logic in the realm of emergent algebra) is to introduce “interaction graphs”, which form a new sector of the graphic lambda calculus.  These interaction graphs look (superficially) a bit alike Feynman trivalent diagrams, with “interaction  nodes” decorated either with \lambda or with \curlywedge, and wires corresponding to “particles” \Upsilon or \varepsilon. This is for the next time, I have to play a bit more with those before showing them.

Advertisements

One thought on “From combinators and zippers to interaction graphs (part I)”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s