Tag Archives: graphic lambda calculus

chemlambda, computation, discussion, distributed GLC, Open Science

HVM rediscovers Kauffman’ Arrow and GLC actors

September 15, 2023 chorasimilarity Leave a comment

To me it looks like this, see page 6 of this pdf.

Back in 2013, Louis Kauffman invented the Arrow node in the Graphic Lambda Calculus formalism, exactly for such a need. He used Mathematica for the first attempts to automatically reduce GLC.

Here are the extended slides of the ALIFE talk, and you see at page 44 this: ” $H[a\rightarrow b]$ represents an edge from node a to node b. This means that we can translate our rule driven formalism to graphical representation by just stripping the $H[a\rightarrow b]$ from each edge rep.”.

At page 46:

See History of Chemlambda for details.

In the first article about molecular computers you see the COMB rewrites. They are part of any chemlambda or chemSKI chemistries.

Moreover, in arXiv:1312.4333, joint with Kauffman we proposed GLC actors, where we describe actors as colors and discuss about what is now called locked or lock free… Of course that this is an obvious problem which has many possible solutions. This has to be a solved problem from the start (not in the middle, wtf??) of any project which claims it does local graphical reductions.

In the old, awk based chemlambda-gui, I implemented these actors as colors and performed simulations to see how the things behave. Colored mol files appear as “mola”.

For example two Ackermann functions sharing a part of their input look like this.

Conclusion: I understood recently that things (some) mathematicians find trivial and obvious to consider are SF for (some) programmers (sorry about that but I’m full of it!). Chemlambda probably contains ideas so advanced just because we mathematicians we think you programmers already and since a long time solved these obvious problems.

I wrote about this project previously. While initially I appreciated it, now…

chemlambda, lambda calculus, Open Science

Why approximate sum is composition

March 14, 2023 chorasimilarity 1 Comment

Here are some explanations about this post.

We shall use the section Commands of the Pure See draft, in order to translate from lambda calculus to dilation structures first introduced in this article.

Mind that we just use the translation suggested in pure see from lambda calculus to dilations. Only this! We shall not use the SHUFFLE schema.

According to this translation we have the following.

A lambda term

$b = \lambda x.a$

corresponds to a node “L” with mol notation

$L a x b$

or to the dilation expression

$b = \delta_{1-z}^{a} x$

which is formally equivalent to

$b = \delta_{z}^{x} a$

So all in all we have the translation

$b = \lambda x.a$ corresponds to $b = \delta_{z}^{x} a$

Likewise we have, for application, the translation

$c = a b$ corresponds to $c = \delta_{1/z}^{b} a$

For the beta rewrite (written locally)

$c = (\lambda x.a) b$ rewrites to $x = b$ and $c = a$

we translate it into

$c = \delta_{1/z}^{b} \delta_{z}^{x} a$ rewrites to $x = b$ and $c = a$

Now see this as a correspondence between beta and modus ponens and interpret it as

if $x = b$ then $c = \delta_{1/z}^{b} \delta_{z}^{x} a$ rewrites as $c =a$

which will allow us to transform a lambda calculus like reduction into an algebraic proof.

Let’s use this translation.

The composition term in lambda calculus is

$(B a) b = \lambda x. (a (b x))$

which translates into (see definition 11 from the dilation structures article)

$\Sigma_{1/z}^{x}(b,a) = \delta_{z}^{x} \delta_{1/z}^{\delta_{1/z}^{x} b} a$

This is called the approximate sum based at $x$ , of $b$ and $a$ .

If, in lambda calculus, we denote composition as an operation

$a \circ b = (B a) b$

then we can prove the following:

$a \circ (b \circ c) = (B a) ((B b) c) = \lambda x. (a ((\lambda y.(b(cy))x)$

reduces to

$y = x$ and $a \circ (b \circ c) = \lambda x. (a(b(cx)))$

This translates into dilation structures as

$\Sigma_{1/z}^{x}(\Sigma_{1/z}^{y}(c,b),a) = \delta_{z}^{x} \delta_{1/z}^{\delta_{1/z}^{x} \delta_{z}^{y} \delta_{1/z}^{\delta_{1/z}^{y} c} b} a$

reduces to

$y = x$ and

$\Sigma_{1/z}^{x}(\Sigma_{1/z}^{y}(c,b),a) = \delta_{z}^{x} \delta_{1/z}^{ \delta_{1/z}^{\delta_{1/z}^{x} c} b} a$

Likewise, in lambda calculus

$(a \circ b) \circ c = (B ((B a) b)) c = \lambda x. (\lambda u.(a(bu)) (cx))$

reduces to

$u = c x$ and

$(a \circ b) \circ c = \lambda x. (a(b(cx)))$

reduces to

$u = \delta_{1/z}^{x} c$ and

$\Sigma_{1/z}^{x}(c \Sigma_{1/z}^{u}(b,a)) = \delta_{z}^{x} \delta_{1/z}^{\delta_{1/z}^{\delta_{1/z}^{x} c} b} a$

In lambda calculus, we see that

$(a \circ b) \circ c$ and $(a \circ b) \circ c$ reduce to the same term $\lambda x. (a(b(cx)))$

In dilation structures we see that

if $y = x$ and $u = \delta_{1/z}^{x} c$ then

$\Sigma_{1/z}^{x}(\Sigma_{1/z}^{y}(c,b),a)$ and $\Sigma_{1/z}^{x}(c \Sigma_{1/z}^{u}(b,a))$ reduce to the same expression

$\delta_{z}^{x} \delta_{1/z}^{\delta_{1/z}^{\delta_{1/z}^{x} c} b} a$

which gives the algebraic proof of

$\Sigma_{1/z}^{x}(\Sigma_{1/z}^{x}(c,b),a) = \Sigma_{1/z}^{x}(c, \Sigma_{1/z}^{ \delta_{1/z}^{x} c}(b,a))$

called the approximate associativity of the approximate sum (Proposition 5, relation (4.7) from the dilation structures article).

The point is that the translation from lambda calculus to dilation structures gives us the algebraic proof, we don’t have to use any ingenuity to obtain the proof!

On further examination we see that, for example, expressions like the approximate difference do not correspond to a pure lambda term and that not any dilation structure version of the beta rewrite is a translation of a lambda calculus beta rewrite. But this is not a problem, because what we actually use from lambda calculus is the purely local version of the beta rewrite, or the graphic beta rewrite, or better said the true image is at the level of graph rewrites and both dilation structures and lambda calculus are graph decorations (semantics) of the true structure.

chemlambda

Graphic lambda calculus and chemlambda(III)

January 25, 2019 chorasimilarity 3 Comments

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:

Github repository (awk, html, js), see also a Haskell implementation written by synergistics.
Demos pages with lots of examples and explanations
M. Buliga, Molecular computers (2015, html) (2018, arXiv) (2018, figshare), main article source for the exact syntax and list of rewrites. [but the awk implementation has the final authority, as I shall explain]
M. Buliga, Build a molecular computer, The Journal of Brief Ideas (2015)
M. Buliga, The Chemlambda collection of simulations (2017, figshare) contains hundreds of simulation results, many of those used to make the animations from the now deleted chemlambda G+ collection.
M. Buliga, The library of chemlambda molecules (2016, github) contains 427 molecules (graphs) with interesting behaviour [and some more which are useful for variants of chemlambda v2, will be explained later]
For context, consult this page for a more exhaustive list.

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)

chemlambda, distributed GLC

Graphic lambda calculus and chemlambda (II)

January 23, 2019 chorasimilarity 2 Comments

UPDATE: The article Graph rewrites, from emergent algebras to chemlambda explains the history of the subject, will all the needed informations.

__________________________

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:

the duplication of the combinator S in chemlambda v1, without using CO-COMM or CO-ASSOC, fails.
the duplication of the same combinator in chemlambda v2 works well.

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:

ycombi

See this page for a list of works, tagged with the version of chemlambda used.

(continues with part III)

chemlambda

Graphic lambda calculus and chemlambda (I)

January 21, 2019 chorasimilarity 3 Comments

UPDATE: The article Graph rewrites, from emergent algebras to chemlambda explains the history of the subject, will all the needed informations.

________

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:

M. Buliga, L.H. Kauffman, GLC actors, artificial chemical connectomes, topological issues and knots, (link to arXiv version)
M. Buliga, L.H. Kauffman, Chemlambda, universality and self-multiplication, (link to arXiv version) (link to MIT Press article)

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)

convention_2

the CO-COMM and CO-ASSOC rewrites

convention_3

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

convention_6

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

convention_4

and elimination of loops

convention_5

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

lafont-2

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.]

(continues with part II)

distributed GLC

How space is born (0)

September 14, 2014 chorasimilarity Leave a comment

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.

________________________________________________________________

distributed GLC

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

August 14, 2014 chorasimilarity Leave a comment

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:

____________________________________________________________

Uncategorized

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

August 11, 2014 chorasimilarity Leave a comment

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?

__________________________________________________________

distributed GLC

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

July 30, 2014 chorasimilarity 4 Comments

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.

_________________________________________________________

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.

_____________________________________________________

distributed GLC

Lambda calculus and the fixed point combinator in chemlambda (VI)

July 22, 2014 chorasimilarity 6 Comments

This is the 6th (continuing from part I and part II and part III and part IV and part V) 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.

_________________________________________________________

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

_________________________________________________________

In this post I want to concentrate on the mechanism of self-multiplication for g-patterns coming from lambda terms (see part IV where the algorithm of translation from lambda terms to g-patterns is explained).

Before that, please notice that there is a lot to talk about an important problem which shall be described later in detail. But here is it, to keep an eye on it.

Chemlambda in itself is only a graph rewriting system. In part V is explained that the beta reduction from lambda calculus needs an evaluation strategy in order to be used. We noticed that in chemlambda the self-multiplication is needed in order to prove that one can do beta reduction as the beta move.

We go towards the obvious conclusion that in chemlambda reduction (i.e. beta move) and self-multiplication are just names used for parts of the computation. Indeed, the clear conclusion is that there is a computation which can be done with chemlambda, which has some parts where we use the beta move (and possibly some COMB, CO-ASSOC, CO-COMM, LOC PRUNING) and some other parts we use DIST and FAN-IN (and possibly some of the moves COMB, CO-ASSOC, CO-COMM, LOC PRUNING). These two parts have as names reduction and self-multiplication respectively, but in the big computation they mix into a whole. There are only moves, graphs rewrites applied to a molecule.

Which brings the problem: chemlambda in itself is not sufficient for having a model of computation. We need to specify how, where, when the reductions apply to molecules.

There may be many variants, roughly described as: sequential, parallel, concurrent, decentralized, random, based on chemical reaction network models, etc

Each model of computation (which can be made compatible with chemlambda) gives a different whole when used with chemlambda. Until now, in this series there has been no mention of a model of computation.

There is another aspect of this. It is obvious that chemlambda graphs form a larger class than lambda terms, and also that the graph rewrites apply to more general situations than beta reduction (and eventually an evaluation strategy). It means that the important problem of defining a model of computation over chemlambda will have influences over the way chemlambda molecules “compute” in general.

The model of computation which I prefer is not based on chemical reaction networks, nor on process calculi, but on a new model, inspired from the Actor Model, called the distributed GLC. I shall explain why I believe that the Actor Model of Hewitt is superior to those mentioned previously (with respect to decentralized, asynchronous computation in the real Internet, and also in the real world), I shall explain what is my understanding of that model and eventually the distributed GLC proposal by me and Louis Kauffman will be exposed in all details.

4. Self-multiplication of a g-pattern coming from a lambda term.

For the moment we concentrate on the self-multiplication phenomenon for g-patterns which represent lambda terms. In the following is a departure from the ALIFE 14 article. I shall not use the path which consists into going to combinators patterns, nor I shall discuss in this post why the self-multiplication phenomenon is not confined in the world of g-patterns coming from lambda terms. This is for a future post.

In this post I want to give an image about how these g-patterns self-multiply, in the sense that most of the self-multiplication process can be explained independently on the computing model. Later on we shall come back to this, we shall look outside lambda calculus as well and we shall explore also the combinator molecules.

OK, let’s start. In part V has been noticed that after an application of the beta rule to the g-pattern

L[a,x,b] A[b,c,d] C[c] FOTREE[x,a1,…,aN] B[a1,…,aN, a]

we obtain (via COMB moves)

C[x] FOTREE[x,a1,…,aN] B[a1,…,aN,d]

and the problem is that we have a g-pattern which is not coming from a lambda term, because it has a FOTREE in the middle of it. It looks like this (recall that FOTREEs are figured in yellow and the syntactic trees are figured in light blue)

The question is: what can happen next? Let’s simplify the setting by taking the FOTREE in the middle as a single fanout node, then we ask what moves can be applied further to the g-pattern

C[x] FO[x,a,b]

Clearly we can apply DIST moves. There are two DIST moves, one for the application node, the other for the lambda node.

There is a chain of propagation of DIST moves through the syntactic tree of C, which is independent on the model of computation chosen (i.e. on the rules about which, when and where rules are used), because the syntactic tree is a tree.

Look what happens. We have the propagation of DIST moves (for the application nodes say) first, which produce two copies of a part of the syntactic tree which contains the root.

At some point we arrive to a pattern which allows the application of a DIST move for a lambda node. We do the rule:

We see that fanins appear! … and then the propagation of DIST moves through the syntactic tree continues until eventually we get this:

So the syntactic tree self-multiplied, but the two copies are still connected by FOTREEs which connect to left.out ports of the lambda nodes which are part of the syntactic tree (figured only one in the previous image).

Notice that now (or even earlier, it does not matter actually, will be explained rigorously why when we shall talk about the computing model, for the moment we want to see if it is possible only) we are in position to apply the FAN-IN move. Also, it is clear that by using CO-COMM and CO-ASSOC moves we can shuffle the arrows of the FOTREE, which is “conjugated” with a fanin at the root and with fanouts at the leaves, so that eventually we get this.

The self-multiplication is achieved! It looks strikingly like the anaphase [source]

followed by telophase [source]

____________________________________________________

distributed GLC

Lambda calculus and the fixed point combinator in chemlambda (V)

July 20, 2014 chorasimilarity 9 Comments

This is the 5th (continuing from part I and part II and part III and part IV) 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.

_________________________________________________________

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

_________________________________________________________

2. Lambda calculus terms as seen in chemlambda continued.

Let’s look at the structure of a molecule coming from the process of translation of a lambda term described in part IV.

Then I shall make some comments which should be obvious after the fact, but useful later when we shall discuss about the relation between the graphic beta move (i.e. the beta rule for g-patterns) and the beta reduction and evaluation strategies.

That will be a central point in the exposition, it is very important to understand it!

So, a molecule (i.e. a pattern with the free ports names erased, see part II for the denominations) which represents a lambda term looks like this:

In light blue is the part of the molecule which is essentially the syntactic tree of the lambda term. The only peculiarity is in the orientation of the arrows of lambda nodes.

Practically this part of the molecule is a tree, which has as nodes the lambda and application ones, but not fanouts, nor fanins.

The arrows are directed towards the up side of the figure. There is no need to draw it like this, i.e. there is no global rule for the edges orientations, contrary to the ZX calculus, where the edges orientations are deduced from from the global down-to-up orientation.

We see a lambda node figured, which is part of the syntactic tree. It has the right.out port connecting to the rest of the syntactic tree and the left.out port connecting to the yellow part of the figure.

The yellow part of the figure is a FOTREE (fanout tree). There might be many FOTREEs, in the figure appears only one. By looking at the algorithm of conversion of a lambda term into a g-pattern, we notice that in the g-patterns which represent lambda terms the FOTREEs may appear in two places:

with the root connected to the left.out port of a lambda node, as in the g-pattern which correspond to Lx.(xx)
with the root connected to the middle.out port of an Arrow which has the middle.in port free (i.e. the port variable of the middle.in of that Arrow appears only once in that g-pattern), for example for the term (xx)(Ly.(yx))

As a consequence of this observation, here are two configurations of nodes which NEVER appear in a molecule which represents a lambda term:

Notice that these two patterns are EXACTLY those which appear as the LEFT side of the moves DIST! More about this later.

Remark also the position of the the insertion points of the FOTREE which comes out of the left.out port of the figured lambda node: the out ports of the FOTREE connect with the syntactic tree somewhere lower than where the lambda node is. This is typical for molecules which represent lambda terms. For example the following molecule, which can be described as the g-pattern L[a,b,c] A[c,b,d]

(but with the port variables deleted) cannot appear in a molecule which corresponds to a lambda term.

Let’s go back to the first image and continue with “TERMINATION NODE (1)”. Recall that termination nodes are used to cap the left.out port of a lambda lode which corresponds to a term Lx.A with x not occurring in A.

Finally, “FREE IN PORTS (2)” represents free in ports which correspond to the free variables of the lambda term. As observed earlier, but not figured in the picture, we MAY have free in ports as ones of a FANOUT tree.

I collect here some obvious, in retrospect, facts:

there are no other variables in a g-pattern of a lambda term than the port variables. However, every port variable appears at most twice. In the graphic version (i.e. as graphs) the port variables which appear twice are replaced by edges of the graph, therefore the bound lambda calculus variables disappear in chemlambda.
moreover, the free port in variables, which correspond to the free variables of the lambda term, appear only once. Their multiple occurrences in the lambda term are replaced by FOTREEs. All in all, this means that there are no values at all in chemlambda.
… As a consequence, the nodes application and lambda abstraction are not gates. That means that even if the arrows of the pattern graphs appear in the grammar version as (twice repeating) port variables, the chemlambda formalism has no equational side: there are no equations needed between the port variables. Indeed, no such equation appears in the definition of g-patterns, nor in the definition of the graph rewrites.
In the particular case of g-patterns coming from lambda terms it is possible to attach equations to the nodes application, lambda abstraction and fanout, exactly because of the particular form that such g-patterns have. But this is not possible, in a coherent way (i.e. such that the equations attached to the nodes have a global solution) for all molecules!
after we pass from lambda terms to chemlambda molecules, we are going to use the graph rewrites, which don’t use any equations attached to the nodes, nor gives any meaning to the port variables other than that they serve to connect nodes. Thus the chemlambda molecules are not flowcharts. There is nothing going through arrows and nodes. Hence the “molecule” image proposed for chemlambda graphs, with nodes as atoms and arrows as bonds.
the FOTREEs appear in some positions in a molecule which represents a lambda term, but not in any position possible. That’s more proof that not any molecule represents a lambda term.
in particular the patterns which appear at LEFT in the DIST graph rewrites don’t occur in molecules which represent lambda terms. Therefore one can’t apply DIST moves in the + direction to a molecule which represents a lambda term.
Or, otherwise said, any molecule which contains the LEFT patterns of a DIST move is not one which represents a lambda term.

_______________________________________________________

3. The beta move. Reduction and evaluation.

I explain now in what sense the graphic beta move, or beta rule from chemlambda, corresponds to the beta reduction in the case of molecules which correspond to lambda terms.

Recall from part III the definition of he beta move

”

L[a1,a2,x] A[x,a4,a3] <–beta–> Arrow[a1,a3] Arrow[a4,a2]

or graphically

If we use the visual trick from the pedantic rant, we may depict the beta move as:

i.e. we use as free port variables the relative positions of the ports in the doodle. Of course, there is no node at the intersection of the two arrows, because there is no intersection of arrows at the graphical level. The chemlambda graphs are not planar graphs.”

The beta reduction in lambda calculus looks like this:

(Lx.B) C –beta reduction–> B[x:=C]

Here B and C are lambda terms and B[x:=C] denotes the term which is obtained from B after we replace all the occurrences of x in B by the term C.

I want to make clear what is the relation between the beta move and the beta reduction. Several things deserve to be mentioned.

It is of course expected that if we translate (Lx.B)C and B[x:=C] into g-patterns, then the beta move transforms the g-pattern of (Lx.B)C into the g-pattern of B[x:=C]. This is not exactly true, in fact it is true in a more detailed and interesting sense.

Before that it is worth mentioning that the beta move applies even for patterns which don’t correspond to lambda terms. Hence the beta move has a range of application greater than the beta reduction!

Indeed, look at the third figure from this post, which can’t be a pattern coming from a lambda term. Written as a g-pattern this is L[a,b,c] A[c,b,d]. We can apply the beta move and it gives:

L[a,b,c] A[c,b,d] <-beta-> Arrow[a,d] Arrow[b,b]

which can be followed by a COMB move

Arrow[a,d] Arrow[b,b] <-comb-> Arrow[a,d] loop

Graphically it looks like that.

In particular this explains the need to have the loop and Arrow graphical elements.

In chemlambda we make no effort to stay inside the collection of graphs which represent lambda terms. This is very important!

Another reason for this is related to the fact that we can’t check if a pattern comes from a lambda term in a local way, in the sense that there is no local (i.e. involving an a priori bound on the number of graphical elements used) criterion which describes the patterns coming from lambda terms. This is obvious from the previous observation that FOTREEs connect to the syntactic tree lower than their roots.

Or, chemlambda is a purely local graph rewrite system, in the sense that the is a bound on the number of graphical elements involved in any move.

This has as consequence: there is no correct graph in chemlambda. Hence there is no correctness enforcement in the formalism. In this respect chemlambda differs from any other graph rewriting system which is used in relation to lambda calculus or more general to functional programming.

Let’s go back to the beta reduction

(Lx.B) C –beta reduction–> B[x:=C]

Translated into g-patterns the term from the LEFT looks like this:

L[a,x,b] A[b,c,d] C[c] FOTREE[x,a1,…,aN] B[a1,…,aN, a]

where

C[c] is the translation as a g-pattern of the term C, with the out port “c”
FOTREE[x,a1,…,aN] is the FOTREE which connects to the left.out port of the node L[a,x,b] and to the ports a1, …, aN which represent the places where the lambda term variable “x” occurs in B
B[a1,…,aN.a] is a notation for the g-pattern of B, with the ports a1,…,aN (where the FOTREE connects) mentioned, and with the out port “a”

The beta move does not need all this context, but we need it in order to explain in what sense the beta move does what the beta reduction does.

The beta move needs only the piece L[a,x,b] A[b,c,d]. It is a local move!

Look how the beta move acts:

L[a,x,b] A[b,c,d] C[c] FOTREE[x,a1,…,aN] B[a1,…,aN, a]

<-beta->

Arrow[a,d] Arrow[c,x] FOTREE[x,a1,…,aN] B[a1,…,aN, a]

and then 2 comb moves:

Arrow[a,d] Arrow[c,x] C[c] FOTREE[x,a1,…,aN] B[a1,…,aN, a]

<-2 comb->

C[x] FOTREE[x,a1,…,aN] B[a1,…,aN,d]

Graphically this is:

The graphic beta move, as it looks on syntactic trees of lambda terms, has been discovered in

Wadsworth, Christopher P. (1971). Semantics and Pragmatics of the Lambda Calculus. PhD thesis, Oxford University

This work is the origin of the lazy, or call-by-need evaluation in lambda calculus!

Indeed, the result of the beta move is not B[x:=C] because in the reduction step is not performed any substitution x:=C.

In the lambda calculus world, as it is well known, one has to supplement the lambda calculus with an evaluation strategy. The call-by-need evaluation explains how to do in an optimized way the substitution x:=C in B.

From the chemlambda point of view on lambda calculus, a very interesting thing happens. The g-pattern obtained after the beta move (and obvious comb moves) is

C[x] FOTREE[x,a1,…,aN] B[a1,…,aN,d]

or graphically

As you can see this is not a g-pattern which corresponds to a lambda term. That is because it has a FOTREE in the middle of it!

Thus the beta move applied to a g-pattern which represents a lambda term gives a g-patterns which can’t represent a lambda term.

The g-pattern which represents the lambda term B[x:=C] is

C[a1] …. C[aN] B[a1,…,aN,d]

or graphically

In graphic lambda calculus, or GLC, which is the parent of chemlambda we pass from the graph which correspond to the g-pattern

C[x] FOTREE[x,a1,…,aN] B[a1,…,aN,d]

to the g-pattern of B[x:=C]

C[a1] …. C[aN] B[a1,…,aN,d]

by a GLOBAL FAN-OUT move, i.e. a graph rewrite which looks like that

if C[x] is a g-pattern with no other free ports than “x” then

C[x] FOTREE[x, a1, …, aN]

<-GLOBAL FAN-OUT->

C[a1] …. C[aN]

As you can see this is not a local move, because there is no a priori bound on the number of graphical elements involved in the move.

That is why I invented chemlambda, which has only local moves!

The evaluation strategy needed in lambda calculus to know when and how to do the substitution x:C in B is replaced in chemlambda by SELF-MULTIPLICATION.

Indeed, this is because the g-pattern

C[x] FOTREE[x,a1,…,aN] B[a1,…,aN,d]

surely has places where we can apply DIST moves (and perhaps later FAN-IN moves).

That is for the next post.

___________________________________________________

Uncategorized

Notes for gamification of chemlambda

June 26, 2014 chorasimilarity Leave a comment

Here are some obvious notes which are filed here about chemlambda graphs in GraphML. Hope they may be used with … ? … why not Liviz.js to get quick something OS to play with.

In the previous post The Quantomatic GUI may be useful for chemlambda (NTC vs TC, III) is mentioned the quantomatic gui, which can easily do all this, but is not free. Moreover, the goals for the gui proposed here are more modest and easily attainable. Don’t care about compatibility with this or that notion from category theory because our approach is different and because the gui is just step 0. So any quick and dirty, but effective code will do, I believe.

______________________________

Recall the idea: gamification of chemlambda.

get quick a chemlambda GUI, as described in A user interface for GLC and use it, with a collection of predefined goals to make a gamification of chemlambda.
obviously that means choosing a format for representing the graphs and moves, many variants here, in this post is described such a choice — GraphML. The work consists into transforming the definitions of graphs and moves into a chosen format.
the various buttons and options from the post describing the gui are simple scripts, perhaps in javascript? of the kind: find and replace predefined patterns by others, all involving up to 4 nodes and 8 arrows, so almost a no brainer, consisting in writing into the chosen format which are the patterns (i.e. the configurations of at most 4 nodes and 8 arrows ) which are involved in the chemlambda moves and which are the replacement rules (i.e. transforming the definition of chemlambda moves into code)
open the possibility to define arbitrary patterns (named here “macros”) and arbitrary moves (named here “macro moves”)
transform into code the algorithm described in Conversion of lambda calculus terms into graphs , with the care to use instead chemlambda. This is good for having a button for importing lambda terms into chemlambda easily.
with all this done, pick a visualization tool which is open, looks good and is easy to use, like the one previously mentioned.
write some scripts for converting to and from GraphML (or whatever other choice one likes) to the input of the viz tool.
pick some examples, transform them into challenges and make public the game.

___________________________

For those with a non functional right hemisphere, here is the GraphML description of chemlambda graphs and what would mean to do a move.

I use this source for GraphML.

A chemlambda graph is any graph which is directed, with two types of 3-valent nodes and one type of 1-valent node, with the nodes having some attributes. [For mathematicians, is an oriented graph made by trivalent, locally planar nodes, and by some 1-valent nodes, with arrows which may have free starts or free ends, or even loops.]

Moreover, we accept arrows (i.e. directed edges) with free starts, free ends, or both, or with start=end and no node (i.e. loops with no node). For all those we need, in GraphML, to use some “invisible” nodes [multiple variants here, only one is described.]

Here are the trivalent, locally planar nodes:

application node

<node id=”n0″ parse.indegree=”2″ parse.outdegree=”1″>
<data key=”d0″>green</data>
<port name=”middle_out”/>
<port name=”left_in”/>
<port name=”right_in”/>
</node>

fanin node

lambda node

fanout node

<node id=”n2″ parse.indegree=”1″ parse.outdegree=”2″>
<data key=”d0″>green</data>
<port name=”middle_in”/>
<port name=”left_out”/>
<port name=”right_out”/>
</node>

termination node

(where “term” denotes a color we agree to use for the termination node, in xfig made drawings this node appears like this –>–| )

two invisible nodes 1 valent

<node id=”n5″ parse.indegree=”0″ parse.outdegree=”1″>
<data key=”d0″>invisible</data> </node>

<node id=”n6″ parse.indegree=”1″ parse.outdegree=”0″>
<data key=”d0″>invisible</data> </node>

(where “invisible” should be something to agree to use)

invisible node 2 valent

<node id=”n7″ parse.indegree=”1″ parse.outdegree=”1″>
<data key=”d0″>invisible</data> </node>

Uses of invisible nodes:

in chemlambda graphs we admit arrows which start from one of the 3 valent nodes but the end is free. Instead of the free end we may use the invisible node with id=”n6″ from before.

There are also accepted arrows which end in a 3 valent node or in a 1 valent termination node, but their start is free. For those we may use the invisible node with id=”n5″ from before.

There are accepted arrows with free starts and ends, so we represent them with the help of invisible nodes with id=”n5″ and id=”n6″.

Finally, we accept also loops, with no nodes, these are represented with the help of the 2 valent invisible nodes line the one with id=”n7″

____________________________________________

Examples:
(a) – recognize pattern for beta move
(b) – perform (when called) the beta move

(a) recognize pattern for beta move.

– input is a chemlambda graph (in GraphML)

– output is the same graph and some supplementary file of annotations of the graph.

This program looks in the input graph for all patterns where the beta move can be applied. This pattern looks like this in the GraphML convention:

<node id=”n101″ parse.indegree=”2″ parse.outdegree=”1″>
<data key=”d0″>green</data>
<port name=”middle_out”/>
<port name=”left_in”/>
<port name=”right_in”/>
</node>
<node id=”n102″ parse.indegree=”1″ parse.outdegree=”2″>
<data key=”d0″>red</data>
<port name=”middle_in”/>
<port name=”left_out”/>
<port name=”right_out”/>
</node>
<edge source=”n102″ target=”n101″ sourceport=”right_out” targetport=”left_in”/>
<edge source=”n106″ target=”n102″ sourceport=”???_1″ targetport=”middle_in”/>
<edge source=”n102″ target=”n103″ sourceport=”left_out” targetport=”???_2″/>
<edge source=”n105″ target=”n102″ sourceport=”???_3″ targetport=”right_in”/>
<edge source=”n101″ target=”n104″ sourceport=”middle_out” targetport=”???_4″/>

Here “???_i” means any port name.

If such a pattern is found, then the collection of id’s (of edges and nodes) from it is stored in some format in the annotations file which is the output.

(b) perform (when called) the beta move

When called, this program takes as input the graph and the annotation file for beta moves pattern and then wait for the user to pick one of these patterns (i.e. perhaps that the patterns are numbered in the annotation file, the user interface shows then on screen and the user clicks on one of them).

When the instance of the pattern is chosen by the user, the program erases from the input graph the pattern (or just comments it out, or makes a copy first of the input graph and then works on the copy, …) and replaces it by the following:

It works only when the nodes n101 or n102 are different than the nodes n103 ,n104, n105, n106, because if not then when erased leads to trouble. See the post Graphic beta move with details.

As an alternative one may proceed by introducing invisible nodes which serve as connection points for the arrows from n106 to n104 and n101 to n103, then erase the nodes among n101, n102 which are not among n103, n104, n105, n106 .

___________________________________________

A concrete example:

The input graph is the one from the first row of the figure:

<node id=”n1″ parse.indegree=”0″ parse.outdegree=”1″>
<data key=”d0″>invisible</data>
<port name=”out”/>
</node>
<node id=”n2″ parse.indegree=”0″ parse.outdegree=”1″>
<data key=”d0″>invisible</data>
<port name=”out”/>
</node>
<node id=”n3″ parse.indegree=”1″ parse.outdegree=”0″>
<data key=”d0″>invisible</data>
<port name=”in”/>
</node>
<node id=”n4″ parse.indegree=”1″ parse.outdegree=”0″>
<data key=”d0″>invisible</data>
<port name=”in”/>
</node>

[comment: these are the four free ends of arrows which are numbered in the figure by “1”, … , “4”. So you have a graph with two inputs and two outputs, definitely not a graph of a lambda term! ]

<node id=”n105″ parse.indegree=”2″ parse.outdegree=”1″>
<data key=”d0″>green</data>
<port name=”middle_out”/>
<port name=”left_in”/>
<port name=”right_in”/>
</node>
<node id=”n106″ parse.indegree=”2″ parse.outdegree=”1″>
<data key=”d0″>green</data>
<port name=”middle_out”/>
<port name=”left_in”/>
<port name=”right_in”/>
</node>
<node id=”n108″ parse.indegree=”2″ parse.outdegree=”1″>
<data key=”d0″>green</data>
<port name=”middle_out”/>
<port name=”left_in”/>
<port name=”right_in”/>
</node>

[comment: these are 3 application nodes]

[comment: these are 3 lambda abstraction nodes]

This graph reduces via 3 beta reductions to

____________________________________________

For this choice which consists into using invisible nodes, a new program is needed (which may be useful for other purposes, later)

(c) arrow combing

The idea is that a sequence of arrows connected via 2-valent invisible nodes should count as an arrow in a chemlambda graph.

So this program does exactly this: if n1001 is different than n1002 then replaces the pattern

<node id=”n7″ parse.indegree=”1″ parse.outdegree=”1″>
<data key=”d0″>invisible</data>
<port name=”in”/>
<port name=”out”/>
</node>
<edge source=”n1001″ target=”n7″ sourceport=”???_1″ targetport=”in”/>
<edge source=”n7″ target=”n1002″ sourceport=”out” targetport=”???_2″/>

_________________________________________

distributed GLC

The Quantomatic GUI may be useful for chemlambda (NTC vs TC, III)

June 25, 2014 chorasimilarity 1 Comment

Since I discovered Quantomatic (mentioned in NTC vs TC I), I continued to look and it seems that it already has, or almost, the GUI which is the step 0 in the Distributed GLC project.

This is a very good news for me, because I tend to consider that possibly complex tasks are simple, therefore as any lazy mathematician will tell you, it is always good if some piece of work has been done before.

In the post A user interface for GLC I describe what we would need and this corresponds, apparently, to a part of what the Quantomatic GUI can do.

See Aleks Kissinger Pictures of Processes: Automated Graph Rewriting for Monoidal Categories and Applications to Quantum Computing, DPhil thesis, [arXiv:1203.0202] , Chapter 9.

Without much ado, I shall comment on the differences, with the hope that the similarities are clear.

Differences. I shall use as an anchor for explaining the differences the homepage of Aleks Kissinger, because is well written and straightforward to read. Of course, this will not mean much if you don’t know what I am talking about concerning NTC vs TC, chemlambda or distributed GLC.

1. Aleks explains

“But “box-and-wire” diagrams aren’t just for physics and multilinear algebra. In fact, they make sense whenever there is a notion a “map”, a procedure for composing maps (i.e. vertical composition), and a procedure for putting two maps “side-by-side” (horizontal composition). That is, this notation makes sense in any monoidal category.”

Here is a first difference from chemlambda, because the chemlambda graphs are open graphs (in the sense that they also have arrows with one or both ends free, as well as loops), but otherwise a chemlambda graph has not any preferred external order of examination. The arrows of the graph are not “wires” and the nodes are not “boxes”. There is no meaning of the vertical or horizontal composition, because there is no vertical and no horizontal.

2. Another quote from Aleks page:

“In Open Graphs and Monoidal Theories, Lucas Dixon and I defined the category of open-graphs and described how double-pushout graph rewriting, as defined in e.g. Ehrig et al⁵, can be applied to open-graphs.”

This marks the second basic difference, which consists into the effort we make to NOT go global. It is a very delicate boundary between staying local and taking a God’s pov, and algebra is very quickly passing that boundary. Not that it breaks a law, but it adds extra baggage to the formalism, only for the needs to explain things in the algebraic way.

Mind that it is very interesting to algebraize from God’s pov, but it might be also interesting to see how far can one go without taking the global pov.

3. Maybe as an effect of 1. they think in terms of processes, we think in terms of Actors. This is not the same, but OMG how hard is to effect, only via words exchanges, the brain rewiring which is needed to understand this!

But this is not directly related to the GUI, which is only step 0 for the distributed GLC.

_______________________________________

Putting these differences aside, it is still clear that:

chemlambda graphs are what they call “open graphs”
there are some basic tools in the Quantomatic gui which we need
mixing our minimal, purely local constraint on reasoning with their much more developed global point of view can be only fruitful, even if the goals and applications are different.

_______________________________________

What do you think about this?

_______________________________________

distributed GLC

My first NSF experience and the future of GLC

June 19, 2014 chorasimilarity 1 Comment

Just learned that the project “Secure Distributed Computing with Graphic Lambda Calculus” will not be funded by NSF.

I read the reviews and my conclusion is that they are well done. The 6 reviewers all make good points and a good job to detect strong points and weaknesses of the project.

Thank you NSF for this fair process. As the readers of this blog know, I don’t have the habit to hide my opinions about bad reviews, which sometimes may be harsh. Seen from this point of view, my thanks look, I hope, even more sincere.

So, what was the project about? Distributed computing, like in the “GLC actors, artificial chemical connectomes, topological issues and knots” arXiv:1312.4333 [cs.DC], which was branded as useful for secure computing. The project has been submitted in Jan to Secure and Trustworthy Cyberspace (SaTC) NSF program.

The point was to get funding which allows the study of the Distributed GLC, which is for the moment fundamental research. There are reasons to believe that distributed GLC may be good for secure computing, principal among them being that GLC (and chemlambda, actually the main focus of research) is not based on the IT paradigm of gates and wires, but instead on something which can be described as signal transduction, see How is different signal transduction from information theory? There is another reason, now described by the words “no semantics“.

But basically, this is not naturally a project in secure computing. It may become one, later, but for the moment the project consists into understanding asynchronous, decentralized computations performed by GLC actors and their biological like behaviour. See What is new in distributed GLC?

Together with Louis Kauffman, we are about to study this, he will present at the ALIFE 14 conference our paper Chemlambda, universality and self-multiplication, arXiv:1403.8046.

There is much more to tell about this, parts were told already here at chorasimilarity.

From this moment I believe that instead of thinking security and secrecy, the project should be open to anybody who wishes to contribute, to use or to criticize. That’s the future anyway.

______________________________________________________

Uncategorized

Zipper logic appeared in math.CO (combinatorics)

May 26, 2014 chorasimilarity 1 Comment

Today, a week after the submission, the article Zipper Logic arXiv:1405.6095 appeared in math.CO , math GT, and not in math.LO , math.GT.

Actually, combinatorics, especially lately, is everywhere, being probably one of the most dynamic research fields in mathematics.

There is a small world connection of zipper logic with combinatorics, because zipper logic is a variant of chemlambda, which is a variant of GLC, which has an emergent algebra sector arXiv:1305.5786 section 5 , which is a sort of approximate algebraic structure, alike, but not the same as the approximate groups arXiv:1110.5008 .

____________________________________

Uncategorized

Birth and death of zipper combinators (I)

April 23, 2014 chorasimilarity 1 Comment

Because zipper logic is a graph rewriting system which does not use variable names, just like GLC and chemlabda, it needs ways to multiply, distribute or kill things.

See Chemlambda, universality and self-multiplication for multiplication, distribution or propagation phenomena.

In this post we shall see how zipper combinators die or are born, depending on the sense of reading the moves. This can happen in several ways, one of them explained in this post.

This can also be seen as the statement: we can do garbage collection in chemlambda, GLC or zipper logic.

____________________________________

Zipper combinators. The set of zipper combinators is the smallest set of zipper graphs with the properties:

it contains the S, K, I zipper graphs defined in the next figure

for any natural number $n >0$ and for any $n+1$ zipper combinators, the zipper graph obtained by connecting the out arrows of the zipper combinators to the in arrows of the $(+n)$ half-zipper is a zipper combinator.

any zipper graph which is obtained by applying a zipper logic move to a zipper combinator is a zipper combinator.

I want to prove that for any zipper combinator $A$ , there is a number $n$ and a succession of $n$ LOCAL PRUNING, CLICK and ZIP moves such that:

Proof. Becauseof the LOC PRUNING move satisfied by $latex (+)$ half-zippers, it follows that by a finite number of these moves we can achieve the effect described in the next figure, for any zipper combinator $A$ (of course, the number of these moves depends on $A$ ):

It is left to prove that the free arrow ending with a termination node can “eat”, one by one, all the $I, K, S$ zipper combinators.

For the $I$ combinator, it happens like this:

The case of the combinator $K$ is described next:

The combinator $S$ is absorbed by the following succession of moves:

The proof is done.

_____________________________________

We can read all backwards, by saying that an arrow connected to a termination node can give birth to any zipper combinator, with the out arrow connected to a termination node.

_____________________________________

Uncategorized

GLC local moves poster

April 15, 2014 chorasimilarity 1 Comment

Here are all GLC local moves in one image, including the emergent algebra moves R1a, R1b, R2, ext2.

distributed GLC

Bacterial conjugation is beta reduction

April 12, 2014 chorasimilarity 1 Comment

I come back to the idea from the post Click and zip with bacterial conjugation , with a bit more details. It is strange, maybe, but perhaps is less strange than many other ideas circulating on the Net around brains and consciousness.

The thing is that bacteria can’t act based on semantics, they are more stupid than us. They have physical or chemical mechanisms which obviate the need to use semantics filters.

Bacteria are more simpler than brains, of course, but the discussion is relevant to brains as collections of cells.

The idea: bacterial conjugation is a form of beta reduction!

On one side we have a biological phenomenon, bacterial conjugation. On the other side we have a logic world concept, beta reduction, which is the engine that moves lambda calculus, one of the two pillars of computation.

What is the relation between semantics, bacterial conjugation and beta reduction?

Lambda calculus is a rewrite system, with the main rewrite being beta reduction. A rewrite system, basically, says that whenever you see a certain pattern in front of you then you can replace this pattern by another.

Graphic lambda calculus is a graph rewrite system which is more general than lambda calculus. A graph rewrite system is like a rewrite system which used graphs instead of lines of text, or words. If you see certain graphical patterns then you can replace them by others.

Suppose that Nature uses (graphical) rewrite systems in the biological realm, for example suppose that bacteria interactions can be modeled by a graph rewrite system. Then, there has to be a mechanism which replaces the recognition of pattern which involves two bacteria in interaction.

When two bacteria interact there are at least two ingredients: spatial proximity (SP) and chemical interaction (CI).

SP is something we can describe and think about easily, but from the point of view of a microbe our easy description is void. Indeed, two bacteria in SP can’t be described as pairs of coordinate numbers which are numerically close, unless if each of the microbes has an internal representation of a coordinate system, which is stupid to suppose. Moreover, I think is too much to suppose that each microbe has an internal representation of itself and of it’s neighbouring microbes. This is a kind of a bacterial cartesian theater.

You see, even trying to describe what could be SP for a pair of bacteria does not make much sense.

CI happens when SP is satisfied (i.e. for bacteria in spatial proximity). There is of course a lot of randomness into this, which has to be taken into account, but it does not replace the fact that SP is something hard to make sense from the pov of bacteria.

In Distributed GLC we think about bacteria as actors (and not agents) and about SP as connections between actors. Those connections between actors change in a local, asynchronous way, during the CI (which is the proper graph rewrite, after the pattern between two actors in SP is identified).

In this view, SP between actors, this mysterious almost philosophical relation which is forced upon us after we renounce at the God eye point of view, is described as an edge in the actors diagram.

Such an edge, in Distributed GLC, it is always related to an oriented edge (arrow) in the GLC (or chemlambda) graph which is doing the actual computation. Therefore, we see that arrows in GLC or chemlambda graphs (may) have more interpretation than being chemical bonds in (artificial) chemistry molecules.

Actually, this is very nice, but hard to grasp: there is no difference between CI and SP!

Now, according to the hypothesis from this post and from the previous one, the mechanism which is used by bacteria for graph rewrite is to grow pili.

The following image (done with the tools I have access to right now) explains more clearly how bacterial conjugation may be (graphic) beta reduction.

In the upper part of the figure we see the lambda abstraction node (red) and the application node (green) as encoded by crossings. They are strange crossings, see the post Zipper logic and knot diagrams . Here the crossings are representing with a half of the upper passing thread half-erased.

Now, suppose that the lambda node is (or is managed by) a bacterial cell and that the application node is (managed by) anther bacterium cell. The fact that they are in SP is represented in the first line under the blue separation line in the picture. At the left of the first row (under the blue horizontal line) , SP is represented by the arrow which goes from the lambda node (of the bacterium at left) and the application node (of the bacterium at right). At the right of the first row, this SP arrow is represented as the upper arc which connects the two crossings.

Now the process of pattern recognition begin. In Nature, that is asymmetric: one of the bacterial cells grow a pilus. In this diagrammatic representation, things are symmetric (maybe a weakness of the description). The pilus growth is represented as the CLICK move.

This brings us to the last row of the image. Once the pattern is recognized (or in place) the graph reduction may happen by the ZIP move. In the crossing diagram this is represented by a R2 move, which itself is one of the ways to represent (graphic) beta moves.

Remark that in this process we have two arcs: the upper arc from the RHS crossing diagram (i.e the arc which represents the SP) and the lower arc appeared after the CLICK move (i.e. the pilus connecting the two bacteria).

After the ZIP move we get two (physical) pili, this corresponds to the last row in the diagram of bacterial conjugation, let me reproduce it again here from the wiki source:

After the ZIP move the arc which represents SP is representing a pilus as well!

____________________________________

distributed GLC

Click and zip with bacterial conjugation

April 9, 2014 chorasimilarity 2 Comments

Bacterial conjugation may be a tool for doing the CLICK and ZIP in the real world. Alternatively, it may serve as inspiration for designing the behaviour 1 of a GLC actor in distributed GLC.

The description of bacterial conjugation, as taken from the linked wiki page:

Conjugation diagram 1- Donor cell produces pilus. 2- Pilus attaches to recipient cell and brings the two cells together. 3- The mobile plasmid is nicked and a single strand of DNA is then transferred to the recipient cell. 4- Both cells synthesize a complementary strand to produce a double stranded circular plasmid and also reproduce pili; both cells are now viable donors.

Step 2 looks like a CLICK move from zipper logic:

Step 4 looks like a ZIP move:

Not convinced? Look then at the CLICK move as seen when zippers are made of crossing diagrams:

On the other side, the ZIP move is a form of graphic beta move. Which is involved in the behaviour 1 of GLC actors.

Imagine that each bacteria is an actor. You have a pair of (bacteria/actors) which (are in proximity/connected in the actor diagram) and they proceed to (bacterial conjugation/behaviour 1). In the most general form, which actually involves up to 6 actors, the bacteria :a and :b interact like this:

(in this figure we see only two nodes, each one belonging to one actor.) The case of bacterial conjugation is when there are only two actors, i.e. :a = :c = :f and :b = :d = :e . Each of the new arrows which appeared after the graphic beta move could be seen as a pilus.

Easy to describe it, but the mechanism of bacterial conjugation is fascinating. Can it be harnessed for (this type of) computation?

UPDATE: searching for “plasmid computing”, found Computing with DNA by operating on plasmids by T. Head, G. Rozenberg, R.S. Bladergroen, C.K.D. Breek, P.H.M. Lommerse, H.P. Spaink, BioSystems 57 (2000) 87 – 93.

They have a way to compute with plasmids. In this post is argued that bacterial conjugation itself (regardless of the plasmid involved) can be used as the main graph rewrite for doing (a graphic version of) lambda calculus, basically.

_____________________________

distributed GLC

Why Distributed GLC is different from Programming with Chemical Reaction Networks

March 23, 2014 chorasimilarity Leave a comment

I use the occasion to bookmark the post at Azimuth Programming with Chemical Reaction Networks, most of all because of the beautiful bibliography which contains links to great articles which can be freely downloaded. Thank you John Baez for putting in one place such an essential list of articles.

Also, I want to explain very briefly why CRNs are not used in Distributed GLC.

Recall that Distributed GLC is a distributed computing model which is based on an artificial chemistry called chemlambda, itself a variant (slightly different) of graphic lambda calculus, or GLC.

There are two stages of the computation:

define the initial participants at the computation, each one called an “actor”. Each actor is in charge of a chemlambda molecule. Molecules of different actors may be connected, each such connection being interpreted as a connection between actors. If we put together all molecules of all actors then we can glue them into one big molecule. Imagine this big molecule as a map of the world and actors as countries, each coloured with a different colour. Neighbouring countries correspond to connected actors. This big molecule is a graph in the chemlambda formalism. The graph which has the actors as nodes and neighbouring relations as edges is called the “actors diagram” and is a different graph than the big molecule graph.
Each actor has a name (like a mail address, or like the colour of a country). Each actor knows only the names of neighbouring actors. Moreover, each actor will behave only as a function of the molecule it has and according to the knowledge of his neighbouring actors behaviour. From this point, the proper part of the computation, each actor is by itself. So, from this point on we use the way of seeing of the Actor Model of Carl Hewitt. Not the point of view of Process Algebra. (See Actor model and process calculi.) OK, each actor has 5 behaviours, most of them consisting into graph rewrites of it’s own molecule or between molecules of neighbouring actors. These graph rewrites are like chemical reactions between molecules and enzymes, one enzyme per graph rewrite. Finally, the connections between actors (may) change as a result of these graph rewrites.

That is the Distributed GLC model, very briefly.

It is different from Programming with CRN because of several reasons.

1. Participants at the computation are individual molecules. This may be unrealistic for real chemistry and lab measurements of chemical reactions, but this is not the point, because the artificial chemistry chemlambda is designed to be used on the Internet. (However, see the research project on single molecule quantum computer).

2. There is no explicit stochastic behaviour. Each actor in charge of it’s molecule behaves deterministically. (Or not, there is nothing which stops the model to be modified by introducing some randomness into the behaviour of each actor, but that is not the point here). There are not huge numbers of actors, or some average behaviour of those.

That is because of point 1. (we stay at the level of individual molecules and their puppeteers, their actors) and also because we use the Actor Model style, and not Process Algebra.

So, there is an implicit randomness, coming from the fact that the computation is designed Actor Model style, i.e. such that it may work differently, depending on the particular physical timing of messages which are sent between actors.

3. The computation is purely local. It is also decentralized. There is no corporate point of view of counting the number of identical molecules, or their proportion in a global space – global time solution. This is something reasonable from the point of view of a distributed computation over the Internet.

__________________________________

All this being said, of course that it would be interesting to see what happens with CRNs of reactions of molecules in chemlambda. May be very instructive, but this would be a different model.

That is why Distributed GLC does not use the CRN point of view.

__________________________________

computing with space | open notebook