The project page moved to chemlambda.github.io. This page is kept for historical reasons.
First are presented the chemical reactions of the artificial chemistry chemlambda (see the demos). These chemical reactions are technically called "graph rewrites", or "moves", or even "rules".
Look further after the moves presentation to see the description of the algorithms used in the demos.
The molecules of chemlambda are made by 7 elementary molecules which are called: A, L, FI, FO, FOE, T, Arrow. Every elementary molecule is made by a main atom, represented as a big colored circle, and some smaller atoms, called ports. A, L, FI, FO, FOE have 3 ports each, Arrow has two ports, and T has one port.
Molecules, i.e. the chemlambda graphs, appear as .mol files, it is important to understand the notation. The program works with the mol files and produces a html file which contains the visualisation of the execution of the algorithm from the main script.
Everything is coded by color, radius of the circle and, for links, there are inner and outer links.
The colours are: " in_col", " out_col", " red_col" (yes, I know), " green_col", " arrow_col" and " term_col". The colour palette does not really matter, of course, for the chemistry (see this older ntroduction about the molecules with a different palette).
Here is the list of nodes with the types of their ports, and the way they are written in the mol file. The colours are as in the visualisations convention.
L middle.in left.out right.out , is inspired from the lambda abstraction.
A left.in right.in middle.out , is inspired from application operation.
FI left.in right.in middle.out , has no correspondent in lambda calculus, name means "fan-in".
FO middle.in left.out right.out , has no correspondent in lambda calculus, name means "fan-out".
FOE middle.in left.out right.out , has no correspondent in lambda calculus, name means "extra fan-out".
Arrow middle.in middle.out , has no correspondent in lambda calculus, is a simple solution for application of some of the moves. Is inspired from Louis Kauffman proposal to use commutative polynomials for the graphical elements (where the variables of the polynomials play the roles of the ports). Louis used on July 3rd 2014 the Mathematica symbolic reduction for polynomial commutative algebra in order to reduce the fixed point combinator in graphic lambda calculus, thus making the first visualisation.
T middle.in , called "termination" node, is used in relation to lambda calculus in place of variables x appearing in terms Lx.A, where A does not contain x.
FRIN middle.out , is a "free in" node, used for edges with a free source. (Thus, if your mol file has a port variable "a" which appears only once, in a port of type out, then the main script adds "FRIN a" to the mol file.)
FROUT middle.in , is a "free out" node, used for edges with a free target. (Thus, if your mol file has a port variable "a" which appears only once, in a port of type in, then the main script adds "FROUT a" to the mol file.)
Remark that the colours and the relative size of the circles are enough to encode all the information. For example the colours of nodes and ports allows to discern which is L 1 2 3 and which is FI 1 2 3 .
Very important: the moves show you which chemical reactions are allowed, NOT how they happen. Indeed, the same chemical reactions may be used with different models about how they happen. This is very important to mention, because people tend to think that chemical reactions have to be regarded in a chemical reaction network frame, or in other context they are familiar with. But there is no logical constraint on that. WHAT happens and HOW it happens are two separate things in chemlambda.
So let's free our minds from unnecessary ingredients and let's concentrate on the WHAT part. Click on the button with the move name to see what happens.
In the following you see the moves written in the mol convention, and also a visualization of the moves. For each move you can CLICK on the move name to see what is happening. You can move the atoms by click and drag.
BETA and FAN-IN family
L 1 2 c , A c 4 3 - - > Arrow 1 3 , Arrow 4 2
FI 1 4 c , FOE c 2 3 - - > Arrow 1 3 , Arrow 4 2
DIST family
FO 1 2 c , FOE c 3 4 - - > FI j i 2 , FO k i 3 , FO l j 4 , FOE 1 k l
FI 1 4 c , FO c 2 3 - - > FO 1 i j , FI i k 2 , FI j l 3 , FO 4 k l<
L 1 2 c , FOE c 3 4 - - > FI j i 2 , L k i 3 , L l j 4 , FOE 1 k l
L 1 2 c , FO c 3 4 - - > FI j i 2 , L k i 3 , L l j 4 , FOE 1 k l
A 1 4 c , FOE c 2 3 - - > FOE 1 i j , A i k 2 , A j l 3 , FOE 4 k l
A 1 4 c , FO c 2 3 - - > FOE 1 i j , A i k 2 , A j l 3 , FOE 4 k l
PRUNING family
A 1 2 3 , T 3 - - > T 1 , T 2 (same for FI instead of A )
L 1 2 3 , T 3 - - > T 1 , T c , FRIN c
FO 1 2 3 , T 2 - - > Arrow 1 3 (same for FOE instead of FO )
FO 1 2 3 , T 3 - - > Arrow 1 2 (same for FOE instead of FO )
COMB move and COMB cycle.
The cycle is a rapid application of COMB moves, whenever there are Arrow elements with the "in" port connected to a port which does not belong to another Arrow.
any node M 1 , Arrow 1 2 - - > M 2
Exemplified here with a BETA move followed by a COMB cycle which eliminates all the Arrow elements, excepting the one which has its in port connected to its out port (so connected to another Arrow port).
Very important: chemlambda puts the INDIVIDUAL molecules at the center of interest, not populations of those.
That being said, of course that one can use a chemical reaction network ingredient for the HOW part, but this is no mandatory.
Although understanding SPACE is a motivation for inventing chemlambda, SPACE is not a part of the WHAT, instead ot is a part of the HOW. We shall discuss about space later. For the moment I just say that chemlambda is superior to any other artificial chemistry which is dependent on a fixed grid, lattice, 2D space, 3D space. I don't use the naive hypothesis that space is something externally fixed, rigid, given, etc, for example I reject any hypothesis which introduces space as a vector of numbers (coordinates), as a name (for example an IP address) or as a relation (for example a name of a channel).
A good source for understanding the construction of chemlambda is this page from my open notebook. There you will find, for example, the idea that the moves of chemlambda are akin chemical reactions which involve enzymes. Each move has an enzyme, but they are invisible in these demos. This is a subject which will be touched later, because it sits in between the WHAT and the HOW.
About the algorithms used for this demo (i.e. about the HOW part, as presented until now.)
Chemlambda is a graph-rewriting formalism with some of the moves (graph-rewrites) inspired from lambda calculus, like for example the BETA move, which is a variant of the Wadsworth-Lamping treatment of the beta move on syntactic trees of lambda terms. But there is a difference: in chemlambda there are no correct molecules (graphs).
Another resemblance is with the Alchemy of Fontana and Buss. They also propose to look at lambda calculus as an artificial chemistry. The main difference is that while in chemlambda application and abstraction are treated on the same par, as atoms in the molecule, in Alchemy application is seen as a chemical reaction and abstraction is seen as a reactive locus in a molecule.
One needs to add to chemlambda a reduction model (which says basically how to apply the moves and what to do if two or more moves attempt to modify the same node of the graph). Any reduction model will do, with the condition to be:
local (the algorithm for deciding which move to apply or which solves conflicts has to be formulated so that it works with an input consisting of a graph with at most N nodes and links, with N fixed a priori)
geometrical (the result of the algorithm is the same regardless of the internal numbering, ordering or naming of the variables from the input)
if it is distributed, then it has to be asynchronous (because of locality in time as well) and decentralized, in the sense that the "local" constraint applies also in space, so the algorithm running in one place has to be able to solve moves and conflicts on its piece of graph based on an a priori bounded number N of graph nodes, links and messages exchanged with other places.
In the demos there is used the most simple algorithm, called for this reason the "stupid" one, in order to show that even so the results are interesting. This algorithm may turn out to be less stupid than I thought, in particular because it may lead to molecular computers [7].
The algorithm takes as input an initial graph, then there is a cycle where, at each step (deterministically or randomly):
are identified the pieces of graph where moves apply
according to a priority of moves (i.e. in this case first identify the patterns for the move FO-FOE, then block the nodes which involve that move, then look further for the other moves DIST which involve free nodes, then block the nodes involved, then look for the BETA and FAN-IN moves, block the nodes, then look for PRUNING moves, block the nodes)
in the random case a coin is flipped for each proposed move and the move is applied or not, accordingly,
moves are applied
there is a COMB cycle, which search for the application of all COMB moves (which eliminate the Arrow elements) until there is no possibility of applying further COMB moves (which does not mean that all Arrow elements are eliminated)
The effect of this algorithm is equivalent, in case we start from a graph which represents a lambda term, to a massively parallel reduction of the term, but one not involving any variable passing, nor evaluation steps, which is already weird enough.
On top of this, if we restrict to graphs coming from lambda terms, one has to take care that: (a) there is no eta reduction, it's pure lambda beta, so "functional" is not appropriate to use because functions need eta reduction (b) even if the initial and final graphs (if there is a final graph) correspond to lambda terms, typically the intermediary ones do not, see for example the bw version of the predecessor reduction. That is because instead of passing variables and evaluations, chemlambda uses a different strategy which is akin to signal transduction .
In the present embodiment there is no care to make the process to be conservative, but this is not a serious problem, because there are several ways of solving this.
Each move is seen as an interaction between a (part of a) molecule-graph with an invisible enzyme, one enzyme per move. One can make the enzymes visible, even use them as a resource, introduce moves between enzymes, this time conservative, or even transform the enzymes into chemlambda graphs as well, by a sort of bootstrapping.
References:
[1] (journal)(arxiv) - M. Buliga, Graphic lambda calculus. Complex Systems 22, 4 (2013), 311-360
[2] (doi)(arxiv) - M. Buliga, Chemical concrete machine (2013).
