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
- termination node
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).
A 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.
- 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.