# Graphic lambda calculus and chemlambda(III)

This post introduces chemlambda v2. I continue from the last post, which describes the fact that chemlambda v1, even if it has only local rewrites, it is not working well when used with the dumbest possible reduction algorithms.

Nature has to work with the dumbest algorithms, or else we live in a fairy tale.

Chemlambda v2 is an artificial chemistry, in the following sense:

• it is a graph rewrite system over oriented fatgraphs made of a finite number of nodes, from the list: 5 types of 3-valent nodes, A (application), L (lambda abstraction), FO (fanout), FI (fanin), FOE (external fanout), 1 type of 2-valent node Arrow, 3 types of 1-valent nodes, FRIN (free in), FROUT (free out), T (termination). Compared to chemlambda v1, there is a new node, the FOE. The nodes, not the rewrites, are described in this early explanation called Welcome to the soup. (Mind that the gallery of example which is available at the end of these explanation mixes chemlambda v1 and chemlambda v2 examples. I updated the links so that is no longer pointing to this very early gallery of examples. However if you like it here is it.)
• the rewrites CO-COMM and CO-ASSOC of chemlambda v1 are not available, instead there are several new DIST rewrites: FO-FOE, L-FOE, A-FOE, FI-FO, and a new beta like rewrite FI-FOE. As in chemlambda v1, the patterns of the rewrites fit with the interaction combinator rewrites if we forget the orientation of the edges, but the 3-valent nodes don’t have a principal port, so they don’t form interaction nets. Moreover, the are conflicts among the rewrites, i.e. there are configurations of 3 nodes such that we have a node which belongs to two pairs of nodes which may admit rewrites. The order of application of rewrites may matter for such conflicts.
• there is an algorithm of application of rewrites, which is either the deterministic greedy algorithm with a list of priority of rewrites (for example beta rewrites have priority over DIST rewrites, whenever there is a conflict), or the random application algorithm.

Sources for chemlambda v2:

The goal of chemlambda v2: to explore the possibility of molecular computers in this artificial chemistry.

This needs explanations. Indeed,  does the system work with the simplest random algorithm? We are not interested into semantics, because it is, or it relies on global notions, We are not (very) interested into reduction strategies for lambda terms, because they are not as simple as the dumbest algorithms we use here. Likewise for readback, etc.

So, does chemlambda v2 work enough for making molecular computers?  Pure untyped lambda calculus reduction problems are an inspiration. If the system works for the particular case of graphs related to lambda terms then this is a bonus for this project.

As you see, instead of searching for an algorithm which could implement, decentralized say, a lambda calculus reduction strategy, we ask if a particular system reduces (graphs related to) terms with one algorithm from the fixed class of dumbest ones.

That is why the universality in the sense of Lafont is fascinating. In this post I argued that Lafont universality property of interaction combinators means, in this pseudo-chemical sense, that the equivalent molecular computer based on interaction combinators reactions (though not the translations) works for implementing a big enough class of reactions which are Turing universal in particular (Lafont  shows concretely that he can implement Turing machines).

(continues with the part IV)

# Graphic lambda calculus and chemlambda (II)

Chemlambda v2 is an entirely different project than GLC and chemlambda v1. This post continues from the first part. It explains the passage towards chemlambda v2.

A problem of GLC and chemlambda v1 is that research articles are opinion pieces, not validated by programs and experiments. The attempt to use GLC with the Actor Model in order to build a decentralized computing proposal, aka distributed GLC, failed because of this. Does all of this work?

The CO-COMM and CO-ASSOC rewrites lead to the situation that,  in order to be useful, either:

• they have to be applied by a human or by a(n unknown) very clever algorithm
• or they are applied in both directions randomly, which implies that no GLC or chemlambda v1 reduction ever terminates.

Here is an early visual tutorial  which introduces the nodes of chemlambda v2.  At the end of it you are pointed to See also a gallery of examples which mixes chemlambda v1 with chemlambda v2, like these:

Or, another example, the Y combinator. In chemlambda v1, without using CO-COMM and CO-ASSOC, the Y combinator applied to an unspecified term behaves like this.  In chemlambda v2, where there is a supplimentary node and other rewrites, the Y combinator behaves almost identically, but some nodes (the yellow FOE here instead of the green FO before) are different:

# Graphic lambda calculus and chemlambda (I)

Looks like there is a need to make a series of posts dedicated to the people who try to use this blog as a source in order to understand graphic lambda calculus (aka GLC) and chemlambda. This is the first one.

Sources for GLC:

• the best source is the article M. Buliga, Graphic lambda calculus. Complex Systems 22, 4 (2013), 311-360   (link to article in journal) (link to article in arXiv)
• you can see the GLC page (link) here, which has been updated many times after chemlambda appeared, but it is unmodified starting from the section “What is graphic lambda calculus?” and there are links to many others posts here which explain GLC as it is, that is before chemlambda.

GLC is a graph rewriting system for fatgraphs made of trivalent or 1-valent nodes. The trivalent nodes used are A (application), L (lambda), FO (fanout), epsilon (for dilations). There is one 1-valent node, T (termination). Loops with no nodes and arrows, i.e. oriented edges with no nodes are accepted as well. There is no algorithm proposed for the reduction of these graphs.

The graph rewrites are:

– local ones (i.e. involving only a finite number, a priori given, of nodes and edges)

•   graphic beta move, which is like Lamping graph rewrite, only purely local, i.e. there is no limitation on the global shape of the graph, thus it is  somehow more general than the beta rewrite from untyped lambda beta calculus; a possible interpretation is C= let x=B in A rewrites to x=B and C=A

• CO-COMM and CO-ASSOC rewrites for the FO (fanout) which are, due to the orientation of the edges, really like graphical, AST forms of co-commutativity and co-associativity
• local pruning group of rewrites, which describe the interaction of the trivalent nodes with the T node; incidentally T and FO interact like if T is a co-unit for FO
• a group of rewrites for the dilation nodes, which are those of emergent algebras, which involve the fanout FO and the dilation nodes

– global rewrites:

• global fan-out
• global pruning

In section 3 of the article on GLC is given an algorithm of conversion of untyped lambda terms into graphs which is a little more than a modification of the AST of the lambda term, in such a way that the orientation of the edges is respected. That is because the lambda node L has one incoming edge and two outgoing edges!

I prove then that GLC can be used for untyped lambda beta calculus, but also for emergent algebras and also for a variant of knot theoretic graphs where there is no need for them to be planar. Finally, I show that there might be other “sectors” of graphs which may be interesting, regardless of their meaning (or lack of it) with respect to lambda calculus.

The problem of GLC is that it has these global rewrites. Can these be replaced by local rewrites?

That’s how chemlambda appeared.

I was aware that some applications of global fanout can be done with local rewrites, but not all. Also, the interest in GLC was not extended to the interest into emergent algebras, to my dismay.

On the other side I became obsessed with the idea that if the global fanout can be replaced by local rewrites entirely then it should be possible in principle to see the rewrites as chemical reactions between individual molecules. A bigger problem would be then: would these reactions reduce the graph-molecules under the dumbest algorithm among all, the random one? Nature functions like this, so any algorithm which would be global in some sense is completely excluded.

This led me to write the article: M. Buliga, Chemical concrete machine (link to DOI) (link to arXiv version).  This is chemlambda v1, which is actually a transition from GLC to something else, or better said to another research subject in the making.

Other sources for this mix glc-chemlambda v1:

Chemlambda v1, or the “chemical concrete machine”, is a graph rewriting algorithm which uses the trivalent nodes A, L, FI (fan-in), FO, and the 1-valent node T and only local rewrites:

• the graphic beta rewrite (between the nodes L and A) and the fan-in rewrite (between the nodes FI and FO)

• the CO-COMM and CO-ASSOC rewrites

• two DIST (from distributivity) rewrites, for the pairs A-FO and L-FO

• local pruning rewrites (involving the 1-valent node T)

•  and elimination of loops

As you see, all rewrites except CO-COMM and CO-ASSOC are alike the ones from Lafont article Interaction combinators, except that the graphs are directed and the nodes don’t have a principal port for interaction. Here are the interaction combinators rewrites

In the chemical concrete machine article are mentioned Berry and Boudol chemical abstract machine and Fontana and Buss alchemy, but not Lafont.  My fault. From what I knew then the beta rewrite came from Lamping or better Wadsworth, the fan-in came from Turaev (knotted trivalent graphs), and the DIST rewrites came from the graphical version of linear emergent algebras, or even better from the Reidemeister 3 rewrite in knot theory.

In this article there is no algorithm for application of the rewrites. (You shall see that in chemlambda v2, which is an artificial chemistry,  there are actually several, among them the deterministic greedy one, with a list of priority of the rewrites, because there are collisions otherwise, and the random one, which interested me the most.)

However I suggest that the rewrites can be seen as done in a truly chemical sense, mediated by (invisible) enzymes, each rewrite type with it’s enzyme.

I proved that we can translate from GLC to chemlambda v1 and that global fan-out and global pruning can be replaced by sequences of rewrites from chemlambda v1. There was no proof that this replacement of the global rewrites with cascades of local rewrites can be done by the algorithms considered. I proved the Turing universality by using the BCKW system of combinators.

The chemical concrete machine article ends however with:

“With a little bit of imagination, if we look closer to what TRUE, FALSE and IFTHENELSE are doing, we see that it is possible to adapt the IFTHENELSE to a molecule which releases, under the detection of one molecule (like TRUE), the ”medicine” A, and under the detection of another molecule (like FALSE) the ”medicine” B.”

The chemlambda page (link) here is reliable for chemlambda v1, but it also contain links to newer versions.

[UPDATE: I retrieved this view from 2014  of the story.]

# How space is born (0)

This opens a new series of posts, which will turn us back to the “computing with space” theme, the main interest here at chorasimilarity.

Look again at the move R2 of graphic lambda calculus.

The epsilon and mu are, originally, elements of a commutative group. Suggestions have been made repeatedly that the commutative group can be anything.

The epsilon and mu are port names, just like the red 1, 2, 3 from the figure.

In the more recent drawing conventions (not that that matters for the formalism) the port names are in blue.

Here is again the same move, but without the epsilon and mu.

Of course, the green node is the fanout, in the chemlambda version.

Yes, eventually, everything is related to everything in this open notebook.

In the next posts I shall take it step by step.

________________________________________________________________

# Lambda calculus and the fixed point combinator in chemlambda (VIII)

This is the 8th  (continuing from part I  and part II  and part III and part IV and part V and part VI  and part VII) in a series of expository posts where we put together in one place the pieces from various places about:

• how is treated lambda calculus in chemlambda
• how it works, with special emphasis on the fixed point combinator.

I hope to make this presentation  self-contained. (However, look up this page, there are links to online tutorials, as well as already many posts on the general subjects, which you may discover either by clicking on the tag cloud at left, or by searching by keywords in this open notebook.)

_________________________________________________________

This series of posts may be used as a longer, more detailed version of sections

• The chemlambda formalism
• Chemlambda and lambda calculus
• Propagators, distributors, multipliers and guns
• The Y combinator and self-multiplication

from the article M. Buliga, L.H. Kauffman, Chemlambda, universality and self-multiplication,  arXiv:1403.8046 [cs.AI],  presented  by Louis Kauffman in the ALIFE 14 conference, 7/30 to 8/2 – 2014 – Javits Center / SUNY Global Center – New York.  Here is a link to the published  article, free, at MIT Press.

_________________________________________________________

Tags. I shall use the name “tag” instead of “actor” or “type”, because is more generic (and because in future developments we shall talk  more about actors and types, continuing from the post Actors as types in the beta move, tentative).

Every port of a graphical element (see part II)  and the graphical element itself can have tags, denoted by :tagname.

There is a null tag “null” which can be omitted in the g-patterns.

As an example, we may see, in the most ornate way, graphical elements like this one:

L[x:a,y:b,z:c]:d

where of course

L[x:null,y:null,z:null]:null    means L[x,y,z]

The port names are tags, in particular “in” out” “middle” “left” and “right” are tags.

Any concatenation of tags is a tag.  Concatenation of tags is denoted by a dot, for example “left.right.null.left.in”.  By the use of “null” we have

a.null –concat–> a

null.a –concat–> a

I shall not regard concat as a move in itself (maybe I should, but that is for later).

Further in this post I shall not use tags for nodes.

Moves with tags. We can use tags in the moves, according to a predefined convention. I shall take several  examples.

1. The FAN-IN move with tags. If the tags a and b are different then

FI[x:a, y:b, z:c] FO[z:c,u:b, v:a]

–FAN-IN–>

Arrow[x:a,v:a] Arrow[y:b,u:b]

Remark that the move is not reversible.

It means that you can do FAN-IN only if the right tags are there.

2. COMB with tags.

L[x:a, y:b, z:c] Arrow[y:b, u:d]

–COMB–>

L[x:a, u:d,z:c]

and so on for all the comb moves which involve two graphical elements.

3. DIST with tags.  There are two DIST moves, here with tags.

A[x:a,y:b,z:c] FO[z:c,u:d,v:e]

–DIST–>

FO[x:a, w:left.d, p:right.e]   FO[y:b, s:left.d, t:right.e]

A[w:left.d, s:left.d, u:d]   A[p:right.e, t:right.e, v:e]

In graphical version

and the DIST move for the L node:

L[y:b, x:a, z:c] FO[z:c, u:d, v:e]

–DIST–>

FI[p:right, w:left, x:a] FO[y:b, s:left, t:right]

L[s:left, w:left,u:d]  L[t:right, p:right, v:e]

In graphical version:

4. SHUFFLE. This move replaces CO-ASSOC, CO-COMM. (It can be done as a sequence of CO-COMM and CO-ASSOC; conversely, CO-COMM and CO-ASSOC can be done by SHUFFLE and LOC PRUNING, explanations another time.)

FO[x:a, y:b, z:c]  FO[y:b, w:left, p:right] FO[z:c, s:left, t:right]

–SHUFFLE–>

FO[x:a, y:left, z:right]  FO[y:left, w, s] FO[z:right, p, t]

In graphical version:

____________________________________________________________

# How not to do the beta move: use emergent algebra instead

In the frame of chemlambda and g-patterns, here is how not to do the beta move. We pass from chemlambda to a slightly enlarged version, see the graphical formalism of projective conical spaces, which would correspond to an only local moves version of the whole GLC, with the emergent algebra nodes and moves.

Then we do emergent algebra moves instead.

Look, instead of the beta move (see here all moves with g-patterns)

L[a,d,k] A[k,b,c]

<–BETA–>

Arrow[a,c] Arrow[b,d]

lets do for an epsilon arbitrary the epsilon beta move

Remark that I don’t do the beta move, really. In g-patterns the epsilon beta move does not replace the LEFT pattern by another, only it ADDS TO IT.

L[a,d,k] A[k,b,c]

— epsilon BETA –>

FO[a,e,f]  FO[b,g,h]

L[f,i,k] A[k,h,j]

epsilon[g,i,d] epsilon[e,j,c]

Here, of course,  epsilon[g,i,d] is the new graphical element corresponding to a dilation node of coefficient epsilon.

Now, when epsilon=1 then we may apply only ext2 move and LOC pruning (i.e. emergent algebra moves)

and we get back the original g-pattern.

But if epsilon goes to 0 then, only by emergent algebra moves:

that’s it the BETA MOVE is performed!

What is the status of the first reduction from the figure? Hm, in the figure appears a node which has a “0” as decoration. I should have written instead a limit when epsilon goes to 0… For the meaning of the node with epsilon=0 see the post Towards qubits: graphic lambda calculus over conical groups and the barycentric move. However, I don’t take the barycentric move BAR, here, as being among the allowed moves. Also, I wrote “epsilon goes to 0”, not “epsilon=0”.

__________________________________________________________

epsilon can be a complex number…

__________________________________________________________

Questions/exercises:

• the beta move pattern is still present after the epsilon BETA move, what happens if we continue with another, say a mu BETA move, for a mu arbitrary?
• what happens if we do a reverse regular BETA move after a epsilon beta move?
• why consider “epsilon goes to 0” instead of “epsilon = 0”?
• can we do the same for other moves, like DIST, for example?

__________________________________________________________

# Lambda calculus and the fixed point combinator in chemlambda (VII)

This is the 7th  (continuing from part I  and part II  and part III and part IV and part V and part VI)  in a series of expository posts where we put together in one place the pieces from various places about:

• how is treated lambda calculus in chemlambda
• how it works, with special emphasis on the fixed point combinator.

I hope to make this presentation  self-contained. (However, look up this page, there are links to online tutorials, as well as already many posts on the general subjects, which you may discover either by clicking on the tag cloud at left, or by searching by keywords in this open notebook.)

_________________________________________________________

This series of posts may be used as a longer, more detailed version of sections

• The chemlambda formalism
• Chemlambda and lambda calculus
• Propagators, distributors, multipliers and guns
• The Y combinator and self-multiplication

from the article M. Buliga, L.H. Kauffman, Chemlambda, universality and self-multiplication,  arXiv:1403.8046 [cs.AI],  which is accepted in the ALIFE 14 conference, 7/30 to 8/2 – 2014 – Javits Center / SUNY Global Center – New York, (go see the presentation of Louis Kauffman if you are near the event.) Here is a link to the published  article, free, at MIT Press.

_________________________________________________________

In this post I take a simple example which contains beta reduction and self-multiplication.

Maybe self-multiplication is a too long word. A short one would be “dup”, any tacit programming language has it. However, chemlambda is only superficially resembling to tacit programming (and it’s not a language, arguably, but a GRS, nevermind).

Or “self-dup” because chemlambda has no “dup”, but a mechanism of self-multiplication, as explained in part VI.

Enough with the problem of the right denomination, because

“A rose by any other name would smell as sweet”

as somebody wrote, clearly not  believing that the limit of his world is the limit of his language.

Let’s consider the lambda term (Lx.xx)(Ly.yz). In lambda calculus there is the following string of reductions:

(Lx.xx)(Ly.yz) -beta-> (Ly.yz) (Lu.uz) -beta-> (Lu.uz) z -beta-> zz

What we see? Let’s take it slower. Denote by C=xx and by  B= Ly.yz. Then:

(Lx.C)B -beta-> C[x:=B]  = (xx)[x:=B]  =  (x)[x:=B]  (x)[x:=B] = BB = (Ly.yz) B -beta-> (yz)[y:=B] = (y)[y:=B] (z)[y:=B] =  Bz = (Lu.uz)z -beta=> (uz)[u:=z] = (u)[u:=z] (z)[u:=z]  = zz

Now, with chemlambda and its moves performed  only from LEFT to RIGHT.

The g-pattern which represents (Lx.xx)(Ly.yz) is

L[a1,x,a] FO[x,u,v] A[u,v,a1] A[a,c,b]  L[w,y,c] A[y,z,w]

We can only do a beta move:

L[a1,x,a] FO[x,u,v] A[u,v,a1] A[a,c,b]  L[w,y,c] A[y,z,w]

<–beta–>

Arrow[a1,b] Arrow[c,x] FO[x,u,v] A[u,v,a1] L[w,y,c] A[y,z,w]

We can do two COMB moves

Arrow[a1,b] Arrow[c,x] FO[x,u,v] A[u,v,a1] L[w,y,c] A[y,z,w]

2 <–COMB–>

FO[c,u,v] A[u,v,b] L[w,y,c] A[y,z,w]

Now look, that is not a representation of a lambda term, because of the fact that FO[c,u,v] is “in the middle”, i.e. the middle.in port of the FO[c,u,v] is the out port of B, i.e. the right.out port of the lambda node L[w,y,c]. On the same time, the out ports of FO[c,u,v] are the in ports of A[u,v,b].

The only move which can be performed is DIST, which starts the self-dup or self-multiplication of B = L[w,y,c] A[y,z,w] :

FO[c,u,v] A[u,v,b] L[w,y,c] A[y,z,w]

<–DIST–>

FI[e,f,y] FO[w,g,h] L[h,e,v] L[g,f,u] A[u,v,b] A[y,z,w]

This is still not a representation of a lambda term. Notice also that the g-pattern which represents B has not yet self-multiplied. However, we can already perform a beta move  for L[g,f,u] A[u,v,b] and we get (after 2 COMB moves as well)

FI[e,f,y] FO[w,g,h] L[h,e,v] L[g,f,u] A[u,v,b] A[y,z,w]

<–beta–>

FI[e,f,y] FO[w,g,h] L[h,e,v] Arrow[g,b] Arrow[v,f] A[y,z,w]

2 <–COMB–>

FI[e,f,y] FO[w,b,h] L[h,e,f] A[y,z,w]

This looks like a weird g-pattern. Clearly is not a g-pattern coming from a lambda term, because it contains the fanin node FI[e,f,y].  Let’s write again the g-pattern as

L[h,e,f]  FI[e,f,y]  A[y,z,w] FO[w,b,h]

(for our own pleasure, the order of the elements in the g-pattern does not matter)  and remark that A[y,z,w] is “conjugated” by the FI[e,f,y] and FO[w,b,h].

We can apply another DIST move

L[h,e,f]  FI[e,f,y]  A[y,z,w] FO[w,b,h]

<–DIST–>

A[i,k,b] A[j,l,h] FO[y,i,j] FO[z,k,l] FI[e,f,y] L[h,e,f]

and now there is only one move which can be done, namely a FAN-IN:

A[i,k,b] A[j,l,h] FO[y,i,j] FO[z,k,l] FI[e,f,y] L[h,e,f]

<–FAN-IN–>

Arrow[e,j] Arrow[f,i] A[i,k,b] A[j,l,h] FO[z,k,l] L[h,e,f]

which gives after 2 COMB moves:

Arrow[e,j] Arrow[f,i] A[i,k,b] A[j,l,h] FO[z,k,l] L[h,e,f]

2 <–COMB–>

A[f,k,b] A[e,l,h] FO[z,k,l] L[h,e,f]

The g-pattern

A[f,k,b] A[e,l,h] FO[z,k,l] L[h,e,f]

is a representation of a lambda term, finally: the representation of (Le.ez)z. Great!

From here, though, we can apply only a beta move at the g-pattern A[f,k,b]  L[h,e,f]

A[f,k,b] A[e,l,h] FO[z,k,l] L[h,e,f]

<–beta–>

Arrow[h,b] Arrow[k,e] A[e,l,h] FO[z,k,l]

2 <–COMB–>

FO[z,k,l] A[k,l,b]

which represents zz.

_____________________________________________________