Introduction
Evidence for evolution of organisms in an ecosystem is ubiquitous. The power of Darwinism in explaining the variation in life forms on earth is overwhelming. Experiments in artificial life were able to duplicate many aspects of evolution.
The remaining mystery of life on earth is in the origins of the first living organisms. Tierra and Avida both start of with a population of "functioning" organisms and focus on the evolution of their code base, a metaphor for the genome. This post is about looking at that first step: the transition of dead matter into the first biological agents with some properties of life.
Simulation of chemistry is computationally complex. It would also be hard to create an environment with more potential than the one we have around us. Therefore, we will be using combinatory logic as a metaphor for chemistry. More expressive, computationally simpler, and Turing-equivalent.
Combinatory Logic
Combinatory logic is referring to variable-free variants of Lambda calculus. Combinatory logic offers function application as its sole operation. Function application is denoted by juxtaposition and associates to the left. Brackets are used to specify a different association. As for lambda calculus, all computation is realized through term rewriting, also called reduction.
One variant of combinatory logic, SKI Combinator Calculus, uses an alphabet of three letters, I, K and S, also called combinators. The rewrite rules for this calculus are few and simple:
Ix -> x Kxy -> x Sfgx -> fx(gx)Here, the combinator
I represents the identity function, as, applied to x, it yields x.
The combinator K is the constant function generator, as K applied to x is the constant x-function.
Finally, the combinator S is called the steering function.
It distributes its third argument over the first and the second argument, and yields the application of both results.
In order to get some familiarity with term rewriting, we will write out the reduction of
SKK applied to x.
SKKx -> Kx(Kx) -> xThe reduction shows that
SKK applied to x yields x, for any x.
Apparently, SKK is semantically equivalent to the I combinator, and the latter is redundant in SKI combinator calculus.
This means we could do with the combinators K and S only, without losing computational power.
Combinatorial Soup
For our experiment we will simulate a combinatorial soup, a metaphor for the primordial soup, as a pool of expressions in SKI combinator calculus. The pool will be initialized with random combinators out of the alphabet,
I, K and S.
Chemical interaction will be replaced by function application, meaning that for randomly chosen expressions a and b,
a will be replaced by ab (a applied to b) and b will be replaced by ba (b applied to a).
In our experiment, we will use no locality, in the sense that interactions occur between two randomly chosen expressions, regardless of their location. One might say the soup is served very hot.
Self-Replication
Given this setup, on most occasions the simulation results in a homogeneous soup, populated with specific combinatorial expressions. The shortest of these expressions, consisting of only 10 primitive combinators, is:
S(K(SSK))(K(K(SSK)))This expression is self-replicating: when applied to any other expression, it yields a copy of itself, as illustrated by the following reduction sequence:
S(K(SSK))(K(K(SSK)))x -> K(SSK)x(K(K(SSK))x) -> SSK(K(K(SSK))x) -> S(K(K(SSK))x)(K(K(K(SSK))x)) -> S(K(SSK))(K(K(K(SSK))x)) -> S(K(SSK))(K(K(SSK)))The property of self-replication is not a trivial thing. The reduction is not merely making a copy of the original, as this would be kind of cheating. In fact, copying would be impossible, as there is no introspection in combinatory logic.
During the reduction the expression is thouroughly consumed. The fact that a copy of the expression is eventually reproduced implies that the structure of the expression is somehow encoded implicitly in the expression itself.
Another expression that frequently occurs is somewhat more complex with 11 primitive combinators:
S(K(SIK))(K(S(K(SIK))))As before, this expression is self-replicating, as illustrated by the following reduction sequence:
S(K(SIK))(K(S(K(SIK))))x -> K(SIK)x(K(S(K(SIK)))x) -> SIK(K(S(K(SIK)))x) -> I(K(S(K(SIK)))x)(K(K(S(K(SIK)))x)) -> K(S(K(SIK)))x(K(K(S(K(SIK)))x)) -> S(K(SIK))(K(K(S(K(SIK)))x)) -> S(K(SIK))(K(S(K(SIK))))Many larger variants are arising on other occasions, all sharing the same property of self-replication.
An Alternative Alphabet
Different variations of combinatory logic have been defined, each based on a specific alphabet, their own set of primitive combinators, and each with their own set of rewrite rules. One such variant is the BCKW-system, which uses the combinators ... indeed.
The semantics of the BCKW-system are defined by the following rewrite rules:
Bxyz -> x(yz) Cxyz -> xyz Kxy -> y Wxy -> xyyHere,
B and C can be seen as restricted versions of the S combinator, simplifying reduction at the functor or argument side respectively.
Repeating the experiment with a combinatorial soup based on this alphabet yields similar results. As this variant is somewhat more expressive, the shortest expression that appears counts only 7 primitive combinators:
C(K(WC))(K(WC))Self-replication of this expression is demonstrated by the following reduction sequence:
C(K(WC))(K(WC))x -> K(WC)x(K(WC)) -> WC(K(WC)) -> C(K(WC))(K(WC))A variant consisting of 9 primitive combinators is:
C(C(KW)C)(C(KW)C)The demonstration of self-replication is left as an exercise.
One-Point Basis
We will close the experiment using a variant of combinatory logic with a one-point basis. Let's define the combinator
X as:
X := x.xSKWe are using lambda notation for the definition of
X, as explained on Wikipedia under combinatory logic.
Both
K and S have semantic equivalents that can be expressed in function of X, as for example:
K := X(X(XX)) S := X(X(X(XX)))This means that the variant of combinatory logic with only
X as an alphabet is computationally equivalent to the other variants.
However, we do not have a reduction rule for X that is expressed in terms of X only.
More problematically, if we substitute K and S in the definition of X, we get an expression that has no normal form: the reduction never stops.
As an alternative, we will reduce expressions in
X using the definition in terms of K and S,
and if that reduction results in a normal form, substitute K and S by their equivalents expressed in terms of X, without any further reduction.
This way, we avoid the problem of infinite reduction inherent to the definition of X and we get a kind of normal form for many expressions.
Repeating the experiment with a combinatorial soup based on this one-point basis and this single rewrite rule again yields similar results. As this variant of combinatory logic is significantly less expressive, the shortest self-replicating expression that appears requires 45 primitive combinators:
X(X(X(XX)))(X(X(XX))(X(X(X(XX)))(X(X(X(XX))))(X(X(XX)))))(X(X(XX))(X(X(XX))(X(X(X(XX)))(X(X(X(XX))))(X(X(XX))))))As before, the demonstration of self-replication is left as an exercise, but make sure to have enough paper at hand.
Conclusions
In terms of artificial life and the mystery of the origin of life, the results of the experiment are not convincing. The fitness function is endogenous, but with the best of intentions, the resulting "organisms" cannot be called protocells. Also, the system is not "open-ended": after a while, no new forms are arising and the soup becomes stable in its composition.
In terms of playing with combinatory logic and self-organization however, the results obtained are interesting and may be an inspiration for future work. We could add locality, using a 3D structure for the ecosystem and limit interactions in space. Also, we might introduce occasional errors in term rewriting, as a kind of mutation. This would change proximity of "organisms" and allow the exploration of new tracks in "animal space", as introduced by Richard Dawkins in The Blind Watchmaker. It might be a first step in coming to an "open-ended" system ?
Another orientation might be to make the fitness function exogenous, measuring resource consumption, such as the size of expressions or the number of reduction cycles required to reduce. Alternatively, we could introduce fitness scoring in function of the ability to perform specific tasks, in number theory for example, and evolve useful functions.
Or we could use the ability for self-interpretation as a fitness function ...
Combinator Representation and Reduction
To complete this post we will present the essentials of the implementation of combinators in Java as it was used to run these simulations. The implementation makes a clear separation between representation and reduction, such that these aspects can be used independently of one another.
Combinators are immutable. All combinators implement the
Combinator interface.
public interface Combinator {
public Combinator apply(Combinator a);
public Combinator reduce();
}
The apply function is used to create the representation of function application.
The reduce function implements a single step in term reduction: it applies a single rewrite rule and returns the resulting combinator.
If no reduction is possible, reduce returns the combinator itself, unmodified.
The expression is said to be in normal form.
The
Apply class is a generic representation of an application.
It is also the sole class used to build the structure of expressions.
public class Apply implements Combinator {
protected Combinator f;
protected Combinator a;
public Apply(Combinator f, Combinator a) {
this.f = f;
this.a = a;
}
...
public Combinator reduce() {
Combinator g = f.reduce();
if (f!=g) return g.apply(a);
Combinator b = a.reduce();
if (a!=b) return f.apply(b);
return this;
}
}
The class provides a default implementation of the reduce function that offers the semantics of lazy evaluation, also known as outer-most reduction.
It tries to reduce the functor of the application.
Only if unsuccessful, it continues with trying to reduce the argument of the application.
Given these building blocks, the
I combinator can be realized in a simple way.
public class I implements Combinator {
...
public Combinator apply(Combinator a) {
return new Apply(this, a) {
public Combinator reduce() {
return a;
}
};
}
}
The apply function returns an anonymous class extending the Apply class.
The anonymous class overrides the reduce function to implement the semantics of the I combinator.
Read this as: apply returns a combinator that, when reduced, returns its argument.
In a similar way, the
K combinator can be realized.
public class K implements Combinator {
...
public Combinator apply(Combinator a) {
return new Apply(this, a) {
public Combinator apply(Combinator b) {
return new Apply(this, b) {
public Combinator reduce() {
return a;
}
};
}
};
}
}
As the K combinator requires two arguments in order to be reduced, nested anonymous classes are used.
In this case, the first level overrides the apply function of Apply, while the second level overrides the reduce function.
And we need an extra level of anonymous classes for the implementation of the
S combinator.
public class S implements Combinator {
...
public Combinator apply(Combinator a) {
return new Apply(this, a) {
public Combinator apply(Combinator b) {
return new Apply(this, b) {
public Combinator apply(Combinator c) {
return new Apply(this, c) {
public Combinator reduce() {
return a.apply(c).apply(b.apply(c));
}
};
}
};
}
};
}
}
Conclusion
The combination of a single, generic representation class for application and creating nested anonymous classes in the apply function provides an elegant way to implement primitive combinators. It also significantly simplifies the implementation of currying.
