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.) Here is a link to the published  article, free, at MIT Press.


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



  • fanout node


  • application node


  • fanin node


  • arrow


  • termination node


  • loop


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 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:


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




18 thoughts on “Lambda calculus and the fixed point combinator in chemlambda (II)”

Leave a Reply

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

You are commenting using your 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