Tag Archives: zipper macro

Zipper logic

As seen in GLC or chemlambda, combinatory logic is a matter of zipping, unzipping or self-multiplication of (half) zippers.

So, why not taking this seriously, by asking if there is a way to express combinatory logic as a logic of zippers.

Besides the fun, there are advantages of using this for computing with space, just let me first  explain the logic of zippers in all detail.

The starting point is the fact that the S, K, I combinators and the reductions they are involved into can be expressed by the intermediary of zippers.

I am going back to the post Combinators and zippers.

A  n-zipper in GLC (in fact I am going to use chemlambda in order to eliminate the GLOBAL FAN-OUT move)  is a graph which has 2n nodes, looking like this:

zipper_n_1

Zippers are interesting because they behave like actual zippers. Indeed, we can unzip  a zipper by a graphic beta move:

zipper_n_2

Therefore, we can define a k-ZIP move, as a concatenation of k beta moves, which can be applied to a n-zipper, provided that k \leq n.

As a real zipper, we see that the n-zipper can be split into 2 half zippers, which are denoted as “-n Z” and “+n Z”.

zipper_n_3

Prepared like this, let’s think about combinators. In the SKI system a general combinator is expressed as a tree made by application nodes, which has as leaves the combinators S, K, and I.

Now, we can see a tree made by application nodes  as a combination  of + half zippers.

Also, the leaves, i.e. the S,K, I combinators are themselves made of half zippers and termination nodes or fanout nodes.

This is easy to see for the I and K combinator (images taken from the post  Combinators and zippers ):

zipper_3

_________________

zipper_4  The combinator S is made of:

  • one -3Z  half-zipper
  • one -2Z half-zipper
  • one -1Z half zipper
  • one fanout node

linked in a particular way:

zipper_5Conclusion: any combinator expressed through S,K,I is made of:

  • a tree of + half zippers
  • with leaves made by -1Z, -2Z, -3Z half zippers,
  • connected perhaps to fanout nodes and termination nodes.

The reduction of a combinator is then expressed by:

  •  application of k-ZIP moves
  • LOC PRUNING moves (in relation to termination nodes and also in relation to CO-ASSOC moves, see further)
  • and DIST moves.

Let me explain. The application of k-ZIP moves is clear. The k-ZIP moves shorten the + half zippers which form the application tree.

We sit now in chemlambda, in order to avoid the GLOBAL FAN-OUT. Then, what about the moves related to a half zipper which is connected to the in arrow of a fanout node?

These are DIST moves. Indeed, remark that  all half zippers are DISTRIBUTORS.  Because they are made by concatenations of lambda or application nodes.

Moreover, the fanout node is a distributor itself! Indeed, we may see the CO-ASSOC move as a DIST move, via the application of some FAN-IN and LOC PRUNING moves:

zipper_n_4

All in all this defines the Zipper Logic, which is then Turing universal.  In the next post I shall give all details, but it’s straightforward.

_______________________________________

Teaser: B-type neural networks in graphic lambda calculus (II)

The connections in a B-type neural network can be trained.  The following  quote and figure are taken from the article  Turing’s Neural Networks of 1948, by Jack Copeland and Diane Proudfoot:

Turing introduced a type of neural network that he called a ‘B-type unorganised machine’, consisting of artificial neurons, depicted below as circles, and connection-modifiers, depicted as boxes. A B-type machine may contain any number of neurons connected together in any pattern, but subject always to the restriction that each neuron-to-neuron connection passes through a connection-modifier.

connecmod

A connection-modifier has two training fibres (coloured green and red in the diagram). Applying a pulse to the green training fibre sets the box to pass its input–either 0 or 1–straight out again. This is pass mode. In pass mode, the box’s output is identical to its input. The effect of a pulse on the red fibre is to place the modifier in interrupt mode. In this mode, the output of the box is always 1, no matter what its input. While it is in interrupt mode, the modifier destroys all information attempting to pass along the connection to which it is attached. Once set, a connection-modifier will maintain its function unless it receives a pulse on the other training fibre. The presence of these modifiers enables a B-type unorganised machine to be trained, by means of what Turing called ‘appropriate interference, mimicking education’.

Let’s try to construct such a connection in graphic lambda calculus.  I shall use the notations from the previous post  Teaser: B-type neural networks in graphic lambda calculus (I).

3. Connections.   In lambda calculus, Church booleans are the following terms: TRUE = \lambda x . \lambda y .x and FALSE = \lambda x. \lambda y. y (remark that TRUE is the combinator K).  By using the algorithm for transforming lambda calculus terms into graphs in GRAPH, we obtain the following graphs:

switch_5

They act on other graphs (A, B) like this:

switch_6

The graphs are almost identical: they are both made by a 2-zipper with an additional termination gate and a wire. See the  post   Combinators and zippers  for more explanations about TRUE, or K.

I am going to exploit this structure in the construction of a connection. We are going to need the following ingredients: a 2-zipper, an INPUT BOX (otherwise called “switch”, see further) and an OUTPUT BOX,

which is almost identical with a switch (it is identical as a graph, but we are going to connect it with other graphs at each labelled edge):

switch_2

I start with the following description of objects and moves from the freedom sector of graphic lambda calculus (the magenta triangles were used also in the previous post).  I call the object from the middle of the picture a switch.

switch_1

As you can see, a switch can be transformed into one of the two graphs (up and down parts of the figure).  We can exploit the switch in relation with the TRUE and FALSE graphs. Indeed, look at the next figure, which describes graphs almost identical with the TRUE and FALSE graph (as represented by using zippers), with an added switch:

switch_4

Now we are ready for describing a connection like the one from the B-type neural networks (only that better, because it’s done in graphic lambda calculus, thus much more expressive than boolean expressions). Instead of training the connection by a boolean TRUE of FALSE input (coming by one of the green or red wires in the first figure of the post), we replace the connection by an OUTPUT BOX (should I call it “synapse”? I don’t know yet) which is controlled by a switch. The graph of a connection is the following:

switch_3

The connection between an axon and a dendrite is realized by having the axon at “1” and the dendrite at “3”. We may add a termination gate at “2”, but this is irrelevant somehow. At the top of the figure we have a switch, which can take any of the two positions corresponding, literary, to TRUE or FALSE. This will transform the OUTPUT BOX into one of the two possible graphs which can be obtained from a switch.

You may ask why did I not put directly a switch instead of an OUTPUT BOX. Because, in this way, the switch itself may be replaced by the OUTPUT BOX of another connection. The second reason is that by separating the graph of the connection into a switch, a 2-zipper and an OUTPUT BOX, I proved that what is making the switch to function is the TRUE-FALSE like input, in a rigorous way. Finally, I recall that in graphic lambda calculus the green dashed ovals are only visual aids, without intrinsic significance. By separating the OUTPUT BOX from the INPUT BOX (i.e. the switch) with a zipper, the graph has now an unambiguous structure.

Currying by using zippers and an allusion to the Cartesian Theater

Here is a recipe for understanding currying with the help of zippers.  (Done in graphic lambda calculus.)

We have a graph A \in GRAPH which has one output and several inputs. We want to curry it. For this we have to artificially give names to the inputs, i.e. to number them (notice that such a thing is not needed in graphic lambda).

curry_1

The next step is to use a n-zipper in order to clip the inputs, by using n graphic beta moves, until we get this:

curry_2

This graph is, in fact, the following one (we replace the n-zipper, which is just a notation, or a macro, with its expression).

curry_3

The graph inside the green dotted rectangle is the currying of A, let’s call him Curry(A).  This graph has only one output and no inputs.  (The procedure of currying can be made itself into a graph which is applied to  the output of A, but we stop at this level for this post.) The graph inside the red dotted rectangle is almost a list. We shall transform it into a list by using again a zipper and one graphic beta move.

curry_4

Now we’re done!

As you see, the currying creates the list, or the list creates the currying, or both form a pair, like the homunculus Curry(A) and the scenic space List(1,2, ... , n), an allusion to my post on the Cartesian Theater.

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.

Combinators and zippers

The goal of this post is to show how to use graphic lambda calculus for understanding the SKI combinators. For the graphs associated to the SKI combinators see this post.

__________

UPDATE: See also the post “Combinators and stickers“.

__________

Zippers have been introduced here.  In particular, the first three zippers are depicted in the following figure.

zipper_2

The combinator I has the expression I = \lambda x . x and it satisfies the relation I A \rightarrow A, where \rightarrow means any combination of beta reduction and alpha renaming (in this case is just one beta reduction: I A = \left( \lambda x . x \right) A \rightarrow A).

In the next figure it is shown that the combinator I  (figured in green) is just a half of the zipper_1, with an arrow added (figured in blue).

zipper_3

When you open the zipper you get A, as it should.

The combinator K = \lambda xy.x satisfies K A B = (KA)B \rightarrow A. In the next figure the combinator K (in green) appears as half of the zipper_2, with one arrow and one termination gate added (in blue).

zipper_4

When you open the zipper you obtain a pair made by A   and B which gets the termination gate on top of it. GLOBAL PRUNING sends B to the trash bin.

Finally, the combinator S = \lambda xyz. ((xz)(yz)) satisfies SABC = ((SA)B)C \rightarrow (AC)(BC). The combinator S (in green) appears to be made by half of the zipper_3, with some arrows added and also with a “diamond” added (all in blue). Look well at the “diamond”, it is very much alike the emergent sum gate from this post.

zipper_5

Let’s use the zipper

I shall use the zipper macro for improving  upon the computation done in “Emergent sums and differences in graphic lambda calculus”  as an example of computation in graphic lambda calculus.

We have to glue the following graphs, by respecting the red labels

emer_zipper_2

in order to obtain the graph which is the subject of manipulation in  the mentioned post:

emer_zipper_3

Zippers are for this. We shall use a 4-zipper.

emer_zipper_4

I shall let you glue all graphs in the right places indicated by the red labels. It is funny to see here a mixture of lambdas, applications and emergent algebras dilation gates.