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

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.

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

_________________________________________________________

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)

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

structure_7

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

structure_8

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

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

structure_10

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

800px-Anaphase.svgfollowed by telophase [source]

Telophase.svg____________________________________________________

 

 

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

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.

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

_________________________________________________________

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:

 

structure_1

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:

structure_2

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]

structure_3

(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

beta_move_exp

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

beta_move_exp_2

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.

structure_4

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:

structure

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

structure_5

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

structure_6

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.

___________________________________________________

 

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

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

_________________________________________________________

2.  Lambda calculus terms as seen in  chemlambda .

In this post is explained how to associate to any untyped lambda calculus term a g-pattern.

Important. Not any g-pattern, i.e. not any pattern, and not any molecule from chemlambda is associated to a lambda term!

Recall first what is a(n untyped) lambda term.

<lambda term> ::= <variable> |  ( <lambda term> <lambda term> ) | ( L <variable> . <lambda term>)

The operation which associates to a pair of lambda terms A and B the term AB is called application.

The operation which associates to a variable x and a term A the term Lx.A  is called (lambda) abstraction.

Every variable which appears in a term A is either bound or free. The variable x is bound if it appears under the scope of an abstraction, i.e. there is a part of A with the form Lx. B .

It it allowed to rename the bound variables of a term. This is called alpha renaming or alpha conversion. Two terms which differ only by alpha renaming are considered to be the same one.

It is then possible to rename the bound variables of a term such that if x is a bound variable then it appears under the scope of only one abstraction and moreover it does not appear as a free variable.

Further is an algorithm   which transforms a lambda term, in this form which eliminates the ambiguities of the names of bound variables, into a g-pattern. See the post Conversion of lambda calculus terms into graphs for an algorithm which transforms a general lambda term into a GLC graph.

In this algorithm, a variable is said to be “fresh” if it does not appear before the step of the algorithm in question.

We start from declaring that we shall use (lambda terms) variables as port variables.

 

Let  Trans[a,A]  be the translation operator, which has as input a variable  and a lambda term and as output a mess (see part II for the definition of a mess:  “A mess is any finite multiset of graphical elements in grammar version.”)

The algorithm defines Trans.

We start from an initial pair a0,  A0 , such that a0 does not occur in A0.

Then we define Trans recursively by

  • Trans[a, AB] = A[a', a", a]  Trans[a',A] Trans[a",B]  with  a’ and a” fresh variables,
  • Trans[a, Lx.A] = L[a',x,a] Trans[a',A]  with a’ a fresh variable
  • Trans[a,x] =  Arrow[x,a]  .

Practically, Trans gives a version of the syntactic tree of the term, with some peculiarities related to the use of the grammar version of the graphical elements instead of the usual gates notation for the two operations, and also the strange orientation of the arrow of the lambda node which is decorated by the respective bound variable.

Trans[a0,A0] is a mess and not a g-pattern because there may be (port) variables which occur more than twice. There are two  possible cases for this:

  • (a) either a port variable occurs once as an  out port variable and more than once as an  in port variable,
  • (b)  or it does not occur as an out port variable but it occurs more than once as an in port variable,

Let’s see examples:

  • (a)  start with a0 = a and A0 = Lx.(xx) .  Then Trans[a,Lx.xx] = L[a1,x,a] Trans[a1, xx] = L[a1, x, a] A[a2,a3,a_1] Trans[a2,x] Trans[a3,x] = L[a1,x,a] A[a2,a3,a1] Arrow[x,a2] Arrow[x,a3]

 

first_ex

As you see the port variable x appears 3 times, once as an out port variable, in L[a1,x,a] , and twice as an in port variable, in Arrow[x,a2] Arrow[x,a3] .

  • (b)  start with a0 = a and A0 = (xz)(yz) . Then Trans[a,(xz)(yz)] = A[a1,a2,a] Trans[a1,xz] Trans[a2,yz] = A[a1,a2,a] A[a3,a4,a1] Trans[a3,x] Trans[a4,z] A[a5,a6,a2] Trans[a5,y] Trans[a6,z] = A[a1,a2,a] A[a3,a4,a1]  Arrow[x,a3]  Arrow[z,a4]  A[a5,a6,a2]  Arrow[y,a5] Arrow[z,a6]

 

second_ex

In this case the port variable z does not occur as a out port variable, but it appears twice as a in port variable, in Arrow[z,a4] Arrow[z,a6].

 

To pass from a mess to a g-pattern is easy now: we shall introduce fanout nodes.

Indeed, an FO  tree with free in port a and free out ports a1, a2, …, aN  is, by definition, ANY g-pattern formed by the rules:

  •  FO[a,a1,a2]  is an FO tree
  • if  FOTREE[a,a1,...,aN] is an FO tree which has a as the only free in port variable and a1, …, aN the only free out port variables, then for every j=1,…,N and for any u,v fresh port variables  FOTREE[a,a1,...,aN] FO[aj,u,v]  is an FO tree with a as the only free port in variable and a1, …, aN, u, v  with the aj removed from the list as the free out port variables.

Remark that by a sequence of CO-COMM and  CO-ASSOC moveswe can pass from any FO tree with free in port variable a and free out port variables a1, …, aN to any other FO tree with the same free in or out port variables.

We shall not choose a canonical FO tree associated to a pair formed by one free in port variable and a finite set of free out port variables, for this reason. (However, in any algorithm where FO trees have to be constructed, such a choice will be embedded in the respective algorithm.]

In order to transform the mess which is outputted by the Trans operator, we have to solve the cases (a), (b) explained previously.

(a) Suppose that there is a port variable x which satisfies the description for (a), namely that x occurs once as an  out port variable and more than once as an  in port variable. Remark that, because of the definition of the Trans operator, the port variable x will appear at least twice in a list Arrow[x,a1] … Arrow[x,aN] and only once somewhere in a node L[b,x,c].

Pick then an FO tree FOTREE[x,a1,...,aN]  with the only free in port variable x and the only free out port variables a1, …, aN. Erase then from the mess outputted by Trans the collection Arrow[x,a1] … Arrow[x,aN]  and replace it by FOTREE[x,a1,...,aN].

In this way the port variable x will occur only once in a out port, namely in L[b,x,c] and only once in a in port, namely the first FO[x,...] element of the FO tree FOTREE[x,a1,...,aN].

Let’s see for our example, we have

Trans[a, Lx.xx] = L[a1,x,a] A[a2,a3,a1] Arrow[x,a2] Arrow[x,a3]

so the variable x appears at an out port in the node L[a1,x,a] and at in ports in the list Arrow[x,a2] Arrow[x,a3] .

There is only one FO tree with the free in port x and the free out ports a2, a3, namely FO[x,a2,a3].  Delete the list Arrow[x,a2] Arrow[x,a3] and replace it by FO[x,a2,a3]. This gives

L[a1,x,a] A[a2,a3,a1] FO[x,a2,a3]

which is a g-pattern! Here is what we do, graphically:

fo_first_ex

(b) Suppose that there is a port variable x which satisfies the description for (b), namely that x  does not occur as an out port variable but it occurs more than once as an in port variable. Because of the definition of the Trans operator, it must be that x will appear at least twice in a list Arrow[x,a1] … Arrow[x,aN] and nowhere else.

Pick then a FO tree FOTREE[x,a1,...,aN] with the only free in port variable x and the only free out port variables a1, …, aN.

Delete Arrow[x,a1] … Arrow[x,aN]  and replace it by FOTREE[x,a1,...,aN] .

In this way the variable x will appear only once, as a free in port variable.

For our example, we have

Trans[a,(xz)(yz)] =  A[a1,a2,a] A[a3,a4,a1]  Arrow[x,a3]  Arrow[z,a4]  A[a5,a6,a2]  Arrow[y,a5] Arrow[z,a6]

and the problem is with the port variable z which does not occur in any out port, but it does appear twice as an in port variable, namely in Arrow[z,a4]  Arrow[z,a6] .

We delete Arrow[z,a4]   Arrow[z,a6] and replace it by FO[z,a4,a6] and we get the g-pattern

A[a1,a2,a] A[a3,a4,a1]  Arrow[x,a3]  FO[z,a4,a6]  A[a5,a6,a2]  Arrow[y,a5]

In graphical version, here is what has been done:

fo_second_ex

 

OK, we are almost done.

It may happen that  there are out port variables which appear  from  Lx.A with x not occuring in A (i.e. free).  For example let’s start with a0=a and  A0 = Lx.(Ly. x) . Then Trans[a,Lx.(Ly.x)] = L[a1,x,a] Trans[a1, Ly.x] = L[a1,x,a] L[a2,y,a1] Trans[a2,x] = L[a1,x,a] Arrow[x,a2] L[a2,y,a1].

There is the port variable y which appears only as an out port variable in a L node, here L[a2,y,a1], and not elsewhere.

For those port variables x which appear only in a L[a,x,b] we add a termination node T[x].

In our example L[a1,x,a] Arrow[x,a2] L[a2,y,a1] becomes L[a1,x,a] Arrow[x,a2] L[a2,y,a1] T[y]. Graphically this is

third_ex

We may still have Arrow elements which can be absorbed into the nodes ports, therefore we close the conversion algorithm by:

Apply the COMB moves (see part III)  in the + direction and repeat until there is no place to apply them any more.

 

Exercice: Consider the Y combinator

Y = Lf.(  (Lx. f(xx))    (Ly. f(yy))   )

Find it’s conversion as a g-pattern.

________________________________________________________________

Do you know these guys?

We need CS collaborators for our project.  The project is about a computation model (Distributed GLC) which is:

  • decentralized
  • asynchronous
  • based on message passing
  • Actor Model style
  • using a Graph Rewriting System called chemlambda.

Here is the portrait of the ideal collaborator:

  • is a big fan of functional programming, but not a fanatic
  • understands the difference between the Actor Model and process calculi
  • has some understanding of real world asynchronous computation, on the Internet
  • is at ease with graph rewriting systems, say he has read Functional programming and parallel graph rewriting

 

Oh, and can discuss over the border with  quick learning mathematicians.

ALTERNATIVELY:

  • has money to fund us and
  • a supply of docile programmers who do what we need first, then optimize the programs after they see by example that, from some obscure reasons, they really work.

 

If interested please call and let’s make stuff that counts!

______________________________________________________________

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

This is the 3rd  (continuing from part I  and part II)  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.)

_________________________________________________________

1.  The chemlambda formalism continued: graph rewrites.

Now we have all we need to talk about graph rewrites.

For clarity, see  part II for the notion of  “pattern”. Its meaning depends on what we use: the graphical version of the grammar version. In the graphical version a pattern is a chemlambda graph with the free ports and invisible nodes decorated with port variables. In the grammar version we have the equivalent notion of a g-pattern, which is a way to write a pattern as a multiset of graphical elements.

It is allowed to rename the port variables in a g-pattern, such that after the renaming we still get a g-pattern. That means that if M is a g-pattern  and f is  any one-to-one function from V(M) to another set of port variables A, then we may replace any port variable x from V(M) by f(x).  We shall not think about this (sort of alpha renaming for g-patterns) as being a graph rewrite.

 

I shall use the following equivalent names further:

  • “graph rewrite”
  • “move”
  • “reduction”

In simple words, a graph rewrite is a rule which says: “replace the pattern   graph_{1} by the pattern graph_{2}“.

 

Let’s see more precisely then what is a graph rewrite. (Technically this is a simple form of graph rewrite, which is not dependent on context, later we may speak about more involved forms. First let’s understand exactly this simple form!)

In order to define a graph rewrite, or move, we need two g-patterns, call them graph_{1} and graph_{2}, such that (perhaps after a renaming of port variables):

  • they have the same set of FV_in port variables
  • they have the same set of FV_out variables

A move is a pair of such g-patterns. The graph_{1} is called the LEFT pattern of the move, the graph_{2} is called the RIGHT pattern of the move.

The move can be performed from LEFT to RIGHT, called sometimes the “+” direction: replace the LEFT pattern by the RIGHT pattern.

Likewise, the move can be performed from RIGHT to LEFT, called sometimes the “-” direction: replace the RIGHT pattern with the LEFT pattern.

Technically, what I describe here can be made fully explicit as a DPO graph rewriting.

Even if the moves are reversible (they can be performed in the + or – direction), there is a preference to use only the “+” direction (and to embed, if needed, a move performed in the “-” direction into a sequence of moves, called “macro”, more about this later).

The “+” direction is not arbitrarily defined.

_________________________________________________________

OK, enough with these preparations, let’s see the moves.

We shall write the moves in two ways, which are equivalent.

When expressed with g-patterns, they are written as

LEFT pattern  <–name of move–>  RIGHT pattern

When expressed with patterns (i.e graphical), they appear as

move_genericThe port names appear in blue. The name of the move appears in blue, the LEFT is on the left, the RIGHT is on the right, the move is figured by a blue arrow.

Pedantic, but perhaps useful rant.     For some reason, there are people who confuse graphs (which are clearly defined mathematical objects) with their particular representations (i.e. doodles), taking them “literally”.  Graphs are graphs and doodles are doodles. When people use doodles for reasoning with graphs, this is for economy of words reasons, the famous “a picture is worth a thousand words”.  There is nothing wrong with using doodles for reasoning with graphs, as long as you know the convention used. Perhaps the convention is so intuitive that it would need 1000000 words to make it clear (for a machine), but however there is a simple criterion which helps those who don’t trust their sight: you got it right if you understand what the doodle means at the graph level.

Look again at the previous picture, which shows you what a generic move looks like. The move (from LEFT to RIGHT) consists into:

  • cutting the arrows and name them by free port variables (here used 1,…, 5)
  • replacing the LEFT pattern by the RIGHT pattern such that it respects the free port variables (1 to 1, 2 to 2, …)
  • gluing back the arrows with the rest of the graph, which is not depicted in the move.

How simple is that?

To make it even more simple, we use the following visual trick: use the relative placements of the free ports in the doodle  as the port variables.

If look carefully at the previous picture, then you notice that you may redraw it (without affecting what the doodle means at the graph level) by representing  the free ports of the RIGHT in the same relative positions as the free ports from the left.

The drawing would then look like this:

move_generic_2

Then you may notice that you don’t need to write the port variables on the doodles, because they have the same relative positions, so you may as well describe the move as:

move_generic_3

This is the convention used everywhere in the doodles from this blog (and it’s nothing special, it’s used everywhere).

I shall close the pedantic rant by saying that there is a deep hypocrisy in the claim that there is ANY need to spend so much words to make clear things clear, like the distinction between graphs and doodles, and relative positions and so on. I ask those who think that text on a page is clear and (a well done) doodle is vague: do you attach to your text a perhaps sound introduction which explains that you are going to use latin letters, that no, the letter and it’s image in the mirror are not the same, that words are to be read from left to right, that space is that character which separates two words, that if you hit the end of a text line then you should pass to the line from behind, that a line is a sequence of characters separated by an invisible character eol, …..? All this is good info for making a text editor, but you don’t need to program a text editor first in order to read a book (or to program a text editor).  It would be just crazy, right?  Our brains use exactly the same mechanisms to parse a doodle as a text page and a doodle as a depiction of a graph. Our brains understand very well that if you change the text fonts then you don’t change the text, and so on. A big hypocrisy, which I believe has big effects in the divide between various nerd subcultures, like IT and geometers, with a handicapping effect which manifests into the real life, under the form of the products the IT is offering. Well, end of rant.

 

Combing moves. These moves are not present in the original chemlambda formalism, because they  are needed at the level of the g-patterns. Recall  from part I that Louis Kauffman proposed to use commutative polynomials as graphical elements, which brings the need to introduce the Arrow element A[x,y]. This is the same as introducing invisible nodes in the chemlambda molecules (hence the passage from molecules to patterns). The combing moves are moves which eliminate (or add) invisible nodes in patterns. This corresponds in the graphical version to decorations (of those invisible nodes) on arrows of the molecules.

A combing move eliminates an invisible node (in the + direction) or adds an invisible node (in the – direction).

A first combing move is this:

Arrow[x,y] A rrow[y,z]  <–comb–> Arrow[x,z]

or graphically remove (or add) a (decoration of an) invisible node :

comb_1

Another combing move is:

Arrow[x,x] <–comb–> loop

or graphically an arrow with the in and out ports connected  is a loop.

Another family of combing moves is that if you connect an arrow to a port of a node then you can absorb the arrow into the port:

L[x,y,z] Arrow[u,x]  <–comb–> L[u,y,z]

L[x,y,z] Arrow[y,u] <–comb–> L[x,u,z]

L[x,y,z] Arrow[z,u] <–comb–> L[x,y,u]

______________________________________

FO[x,y,z] Arrow[u,x]  <–comb–> FO[u,y,z]

FO[x,y,z] Arrow[y,u] <–comb–> FO[x,u,z]

FO[x,y,z] Arrow[z,u] <–comb–> FO[x,y,u]

______________________________________

A[x,y,z] Arrow[u,x]  <–comb–> A[u,y,z]

A[x,y,z] Arrow[u,y] <–comb–> A[x,u,z]

A[x,y,z] Arrow[z,u] <–comb–> A[x,y,u]

______________________________________

FI[x,y,z] Arrow[u,x]  <–comb–> FI[u,y,z]

FI[x,y,z] Arrow[u,y] <–comb–> FI[x,u,z]

FI[x,y,z] Arrow[z,u] <–comb–> FI[x,y,u]

______________________________________

Now, more interesting moves.

The beta move.     The name is inspired from the beta reduction of lambda calculus (explanations later)

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

or graphically

beta_move_exp

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

beta_move_exp_2

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 FAN-IN move. This is a move which resembles the beta move.

FI[a1,a4,x] FO[x,a2,a3]

<–FAN-IN–>

Arrow[a1,a3]  Arrow[a4,a2]

(I wrote it like this because it does not fit in one line)

Graphically, with the obvious convention from the pedantic rant, the move is this:

fanin_move_exp

The FAN-OUT moves.  There are two moves: CO-COMM  (because it resembles with a diagram which expresses co-commutativity) and CO-ASSOC (same reason, but for co-associativity).

FO[x,a1,a2]  <–CO-COMM–> FO[x,a2,a1]

and

FO[a1,u,a2] FO[u,a3,a4]

<-CO-ASSOC->

FO[a1,a3,v] FO[v,a4,a2]

or graphically:

convention_3

The DIST moves. These are called distributivity moves. Remark that the LEFT pattern is simpler than the RIGHT pattern in both moves.

A[a1,a4,u] FO[u,a2,a3]

<–DIST–>

FO[a1,a,b] FO[a4,c,d] A[a,c,a2] A[b,d,a3]

and

L[a1,a4,u] FO[u,a2,a3]

<–DIST–>

FI[a1,a,b] FO[a4,c,d] L[c,b, a2] L[d,a,a3]

 

or graphically:

convention_6

The LOCAL PRUNING moves. These are used with the termination node. There are four moves:

FO[a1,a2,x] T[x] <–LOC-PR–> Arrow[a1,a2]

L[a1,x,y] T[x] T[y] <–LOC-PR–> T[a1]

FI[a1,a2,x] T[x] <–LOC-PR–> T[a1] T[a2]

A[a1,a2,x] T[x] <–LOC-PR–> T[a1] T[a2]

 

or graphically

convention_4

 

____________________________________________________________

Artificial Life 14 from MIT Press, freely available under Creative Commons licenses

Thanks to the organizers of the ALIFE 14 conference, 7/30 to 8/2 – 2014 – Javits Center / SUNY Global Center – New York! That’s the way to do it [source]:

“The proceedings of ALIFE 14 are now available from MIT Press. The full proceedings, as well as individual papers, are freely available under Creative Commons licenses.

http://mitpress.mit.edu/books/artificial-life-14

Great!

______________________________________________________

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

This is the second  (continuing from part I)  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.)

_________________________________________________________

1.  The chemlambda formalism continued: molecules, patterns and g-patterns.

 

Chemlambda works with graphs which are called “molecules”. In the last post was proposed also a grammar version of molecules, based on the idea that a molecule is made by a finite number of graphical elements, each graphical element having ports, the ports are marked with “port variables”; two ports connect (in the graphical version) is the same as the repetition of a port variable in the grammar version of a molecule.

Here are the graphical elements, along with their grammar versions:

  • lambda node

lambda_graph_elem

 

  • fanout node

fanout_graph_elem

  • application node

appl_graph_elem

  • fanin node

fanin_graph_elem

  • arrow

arrow_graph_elem

  • termination node

termin_graph_elem

  • loop

loop_graph_elem

There is only one loop element. The orientation of the loop, as represented in a drawing, is not relevant!

_________________________________________________________

A chemlambda  graph   is any graph made by a finite number of graphical elements, such that there is no conflict of orientation of arrows (i.e. the ports named “in” may connect only with the ports named “out”).

By convention, an arrow graphical element which has no free port (i.e. which has the middle.in port and the middle.out port connected) is represented as an arrow between “invisible nodes”. The ports of an arrow element which are connected are called “invisible ports”.

A molecule is a chemlambda graph without invisible nodes.

By convention, we identify a chemlambda graph with the molecule obtained  by erasing the invisible nodes.

A pattern is a chemlambda graph with the free ports and invisible nodes decorated with different port variables.

Let’s give a name for the grammar version of a pattern.

A mess is any finite multiset of graphical elements in grammar version. The port variables of a mess  is the set of port variables which appear as arguments in the graphical elements  of the mess. The set of port variables of a mess M  is denoted by V(M).

g-pattern is a mess with the properties:

  • any port variable appears at most twice,
  • if a port variable appears twice then it appears in a pair of “in” and “out” ports.

Simple examples:

  • A[x,x,y] is a mess which is not a g-pattern, because the port variable x appears in TWO “in” ports
  • A[x,y,x]  and A[y,x,x] are g-patterns
  • FO[x,y,y] is a mess which is not a g-pattern, because the port variable y appears in TWO “out” ports.
  • L[a,b,c] A[a,d,b] A[x,y,d] is a g-pattern
  • L[a,b,c] A[a,d,b] A[a,y, d]  is a mess which is not a g-pattern, because the port variable “a” appears in 3 places
  • L[a,b,c] A[u,d,b] A[z,y, d] FO[a,u,z] is a g-pattern

 

 

The set of  free variables of a g-pattern M is the set of port variables which appear only once. This set is denoted by FV(M) and it decomposes into a disjoint union of  FV_in (M) and  FV_out(M) of free port variable which appear in a “in” port and free port variables which appear in a “out” port.

There are g-patterns which have an empty set of port variables: for example   V(loop)  is the empty set.

The set of invisible variables of a g-pattern M, denoted by Inv(M),  is made by those variables of M which are not free and they appear in one of the ports of an arrow element.

As an illustration, consider this:

ex_pattern

  • up is a pattern, with free ports decorated by a1, a4, a5 and with invisible nodes decorated by a2, a3
  • in the middle is the corresponding g-pattern, with one free port variable of type “in” a1,  invisible variables a2, a3 and two free port variables of type “out” a4, a5
  • down, the molecule obtained from the pattern from the  up side, with invisible nodes erased and with no decoration of its free ports.

 

_________________________________________________________

computing with space | open notebook

computing with space | open notebook

cemerick

Against all odds.

The Quilt Project

writings on data, communication, and computation

Low Dimensional Topology

Recent Progress and Open Problems

Towards a 2nd Renaissance

The Internet of Things & Services: Renaissance Re-Born

kauffman2013

A fine WordPress.com site

Voxel-Engine

An expirimental non-gpu 3d voxel engine.

Theory, Evolution, and Games Group

The EGG studies theoretical computer science, evolution, and game theory.

semanto.me

freedom to grok

outfind.ca *

Out think, out search, out find * A blog by Olivier Charbonneau, Business Librarian at Concordia University (Montréal)

Sauropod Vertebra Picture of the Week

SV-POW! ... All sauropod vertebrae, except when we're talking about Open Access

isomorphismes

computing with space | open notebook

DIANABUJA'S BLOG: Africa, The Middle East, Agriculture, History and Culture

Ambling through the present and past with thoughts about the future

Retraction Watch

Tracking retractions as a window into the scientific process

Shtetl-Optimized

computing with space | open notebook

Theoretical Atlas

He had bought a large map representing the sea, / Without the least vestige of land: / And the crew were much pleased when they found it to be / A map they could all understand.

Gödel's Lost Letter and P=NP

a personal view of the theory of computation

Gowers's Weblog

Mathematics related discussions

Research and Lecture notes

by Fabrice Baudoin

The "Putnam Program"

Language & Brains, Machines & Minds

What's new

Updates on my research and expository papers, discussion of open problems, and other maths-related topics. By Terence Tao

Follow

Get every new post delivered to your Inbox.

Join 75 other followers

%d bloggers like this: