Cite as:
chemSKI & chemlambda. © Marius Buliga (2020), https://mbuliga.github.io/chemski/chemski.html

Version 24.08.2020

See also:
All chemlambda projects


German Kruszewski posed the problem of a graph-rewriting version of his and Tomas Mikolov Combinatory Chemistry: Towards a Simple Model of Emergent Evolution, arXiv:2003.07916 in chemlambda style.

chemSKI is a purely local graph rewrite system for the SKI combinators calculus which answers this problem.

In chemSKI there are two 1-valent nodes, for the combinators I and K, and two 3-valent nodes, for the combinator S and for the application (A like in chemlambda). There are also two 1-valent nodes, FRIN (free in) and FROUT (free out) and a 2-valent node Arrow, which serve the same roles as in chemlambda, namely to cap the free half-edges of the graph or to allow simultaneous application of rewrites, followed by the deletion of the introduced Arrow nodes by the rewrite COMB (which "combs" the graph).

The rewrites concerning the node S are different, according to the existence of an edge between S node ports 1 and 2 (in this case S represents the combinator S) or not (in this case S is a fanout node).

There is a variant of chemSKI which is fully compatible with chemlambda rewrites, called "chemSKI+λ" where the occurences of the node S when there is no edge between ports 1 and 2 are replaced with a chemlambda node FOE. You can toggle between chemSKI and chemSKI+λ by using the "change" button.

You can explore the differences between chemSKI and chemSKI+λ by using the parser window and button "λSKI -> mol".

The parser transforms any mix of SKI with lambda calculus (where the letters "S", "K", and "I" are always interpreted as combinators, not lambda calculus variables) into a mol file (i.e. into a graph). This graph can be reduced with chemSKI plus chemlambda or chemSKI+λ plus chemlambda.

In the case of chemSKI the chemlambda nodes do not interpret the node S as a fanout, nor the pure chemSKI nodes (I,S,K) do not see FO and FOE as fanouts. Differently, if you change to the chemistry chemSKI+λ then the reductions work better, with the price of mixing the FO and FOE nodes into the pure chemSKI formalism.

before:

chosen:

after:

mol before:

mol after: