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

This is the first 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 as easy to follow as possible, particularly by trying to make is self-contained. (However, look up this page, there are links to online tutorials, as well as already many posts on the general subjects, which you may discover either by clicking on the tag cloud at left, or by searching by keywords in this open notebook.)

_________________________________________________________

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

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

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

_________________________________________________________

1.  The chemlambda formalism.

Chemlambda has been introduced with the name “chemical concrete machine” (as an allusion to Berry and Boudol CHAM)  in the article M. Buliga, Chemical concrete machine, arXiv:1309.6914 [cs.FL] , also available on figshare here: (doi).

 

Chemlambda is a graph-rewrite system.  From the linked wiki page, only slightly edited:

Graph transformation, or graph rewriting, concerns the technique of creating a new graph out of an original graph algorithmically.

Graph transformations can be used as a computation abstraction. The basic idea is that the state of a computation can be represented as a graph, further steps in that computation can then be represented as transformation rules on that graph. Such rules consist of an original graph, which is to be matched to a subgraph in the complete state, and a replacing graph, which will replace the matched subgraph.

Formally, a graph rewriting system usually consists of a set of graph rewrite rules of the form L \rightarrow R, with L being called pattern graph (or left-hand side) and R being called replacement graph (or right-hand side of the rule). A graph rewrite rule is applied to the host graph by searching for an occurrence of the pattern graph (pattern matching) and by replacing the found occurrence by an instance of the replacement graph.”

In order to define chemlambda we need two ingredients:

  • the graphs used in the formalism
  • the graph rewrites.

 

A chemlambda graph (aka a molecule) is any graph made by a finite number of the following graphical elements:

4_chem

A BNF form would be:

<graphical-element> ::= <lambda> | <fanout> |  <appl> | <fanin> | <arrow>  | <loop> | <termin>

<middle.in>::= port  variable

<middle.out>::= port  variable

<left.in> ::= port variable

<left.out> ::= port variable

<right.in> ::= port variable

<right.out>::= port variable

<lambda>: := L[<middle.in>,<left.out>,<right.out>]

<fanout>::= FO[<middle.in>,<left.out>,<right.out>]

<appl>::= A[<left.in>,<right.in>,<middle.out>]

<fanin>::=FI[<left.in>,<right.in>,<middle.out>]

<arrow>::= Arrow[<middle.in>,<middle.out>]

<loop>::= loop

<termin>::= T[<middle.in>]

This notation is inspired from Louis Kauffman proposal to use commutative polynomials for the graphical elements (then, the variables of the polynomials play the roles of the ports). Louis hacked on July 3rd 2014  the Mathematica symbolic reduction  for polynomial commutative algebra in order to reduce the fixed point combinator in GLC automatically.  I take his approach and  use it here for the grammar notation of chemlambda molecules.

Let’s see first the names of the elements, then let’s discuss more details about them.

  • (a) is the lambda node, it has one in arrow, called the port middle.in and two out arrows, which are NOT interchangeable, called left.out (the one from the left of the middle.in arrow port) and right.out (the one from the right of middle.in port).
  • (b) is the fanout node. As the lambda node, it has one in arrow, called the port middle.in, and two out arrows, called the ports left.out and right.out , following the same graphical conventions for representing it, as previously.   
  • (c) is the application node. It has only one arrow out, called the port middle.out, and two in arrows, which are NOT interchangeable. The two arrow ports are called left.in (the one from the left of the middle.out port) and right.in (the one from the right of the middle.out port).
  • (d) is the fanin node. It has the same configuration of ports as the application node
  • (e) there are three graphical elements there, let’s take them in order.  (up) is an arrow. Now, in chemlambda are allowed arrows with one, or both ends free (i.e. not connected to a chemlambda node). Also (middle) loops with no nodes are accepted.  (down) termination node, with only one port in.

A  shorter, geometrical way to say all this is that the 3valent nodes are all locally planar.

A chemlambda graph is called “molecule”, and it is made by a finite number of graphical elements, i.e.

<molecule> ::= <graphical-element> | <molecule> <molecule>

with the convention that:

  • the order of the writing of the graphical elements of the molecule does NOT matter (one can permute the graphical elements in the grammar notation of the molecule)
  • any in port is connected with at most one out port
  • any out port is connected with at most one in port
  • any concatenation of two arrows is an arrow or a loop
  • any concatenation of an arrow and a port is a port.

If we use a grammar for this (some might like the 1000 words instead of the picture) that means that a <molecule> is well written if:

  • any port variable appears at most twice; when it appears twice then one of the appearances is a  port in (i.e. <middle.in> |  <left.in>  | <right.in>) and the other appearance is a port out (i.e. <middle.out> | <left.out> | <right.out>)
  • when a port variable appears only once then we call it a free port variable. The collection of free port variables (in grammar notation) is denoted by FV(<molecule>).  In the graphical notation we shall add, when needed, the free port variables in blue. Notice however that the graphical notation will make a difference between molecules, which are graphs with free ports NOT tagged with a port variable, and patterns, which are  graphs with free ports tagged with different port variables. This difference does not exist at the level of the grammar notation (helas!).
  • for the concatenation of arrows or concatenation of arrows or ports, this means that at the grammar level we have to introduce some combing rewrites, more about this later.
  • at the level of grammar we have all the kitchen with port variables which asks to well manage them and rename them consistently. At the graphic level this problem does not exist, with the exception of port variables which are free, which may be used for the definition of graph rewrites.

Question: why in graphical notation are needed only two colours for the 3valent nodes?

Answer: because the lambda node and the fanout node have the same type, therefore we colour the first red and the second green. Likewise the fanin node and the application node have the same type, so we colour the first red and the second green.

Let’s see some simple examples. (You can click on the figure to make it bigger.)

molecules_ex

First row: at the left is a molecule in graphical notation. At the right is the same molecule in grammar notation.  Look at the arrow which appears vertical in the graphical notation from the left, where is it in the grammar notation? Well look at the port variable “e”. It appears in the right.out port of the node lambda L[a,b,e] and also in the left.in port of the node application A[e,d,c].

In the grammar notation the same graph may be written as

L[a,b,e] Arrow[e,f] A[f,d,c]

but this is for the next time, when we shall talk about the combing rewrites. (What will happen is that the Arrow[e,f] will disappear because it connects the out port named with the variable “e” with the middle.in port of the Arrow[e,f], which makes the Arrow element redundant.)

Second row:   At the left a graph made by two arrows and two loops. Notice two things:

  • it does not matter if the arrows cross, there is no node there, only an artifact of the drawing a graph  in the plane of the screen,
  • also, even if on the screen we see two oriented loops with opposed orientation in the plane of the screen, as graphical elements the two loops (which have no node, in particular no 3valent node) are the same. “Locally planar” constraint act only as a cyclical order of ports of the 3valent nodes (which combined with the fact that each of the four 3valent nodes has one port which is special, the one called “middle”, gives then a non-ambiguous notion of “left”  and “right” ports).

At the right we see the grammar notation of the same graph.

Third row: Here is a more consistent graph (at the left) and it’s grammar notation at the right. There are 3 nodes, fanout, lambda and termination nodes. Notice  that the port variable “a” appears only in L[a,b,a] which corresponds to the fact that the right.out port and the middle,in port of that lambda node are connected (both being tagged with the port variable “a”.

_________________________________________________________

Here are the 1000 words which are needed to properly explain the notion of a molecule in chemlambda (i.e. if you don’t trust your sight). Such a description is of course useful for writing programs.

After this straightforward description, perhaps extremely boring one, because it can be immediately deduced from the short definition, next time we shall see the graph rewrites of chemlambda.

_________________________________________________________

 

Advertisements

12 thoughts on “Lambda calculus and the fixed point combinator in chemlambda (I)”

Leave a Reply

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

WordPress.com Logo

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

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s