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:
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]
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]
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.
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]
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]
FO[x:a, y:left, z:right] FO[y:left, w, s] FO[z:right, p, t]
In graphical version: