Paul William Berg

As I brought up in a previous post, a problem with Koza style genetic programming (GP) is the absence of recursion and any type of variable binding which causes means that the algorithm must unroll all loops and repeat statements because it can't bind statements to variables in order to perform loops. So, in the spirit of Tina Yu, we decide to introduce lambda expression to the set of primitives.

This introduces a new class of problems altogether. The lambda calculus uses binds a variable to a term which is then accessible in the closure, for instance \x->(\y->x+y) is the function f(x) that binds x to the variable "x" and substitutes the value of x with any x in the body, here "\y->x+y". In this case, the body returned is a new function f'(y) that takes a value, binds it to y and substitutes it in the body, "x+y". The body, being a term composed of primitives can now be solved, so that (\x->(\y->x+y) 1 2 ==> (\y->1+y) 2 ==> 1+2 ==> 3.

Here lies the problem. When we are writing these expressions, we can arbitrarily assign any name for the variables. When the computer writes a parse tree, it must have a convention for coming up with names, as general rules of thumb for us humans, like "the name should be descriptive" are ill defined to a computer. We can choose random strings for this and in GP when generating the sub tree, we can add the new variable to the list of primitives to be selected from. This leads to a problem in crossover, however. Naive traditional crossover will swap subtrees and invariable tend to lift bound variables out of expressions and make them free, where they will then be evaluated in an unbound environment. That means we would either have to provide a default value for "free" variables, or we could create a complex crossover algorithm that only swaps terms that contain variables that will be bound in their new context. This is a rather strict constraint for our crossover and may make crossover less useful to us (or possibly more useful by limiting legal points of crossover to places where it is syntactically correct, but my intuition is that this will not be a useful constraint, partially because of the fact that crossover will work more and more normally as the depth of the tree increases and the environment becomes saturated with bindings, while crossover becomes less normal near the tree roots... a rather arbitrary constraint and it just doesn't feel elegant.) We can partially alleviate the problem by having a finite number of primitive variables to choose from, rather than an infinite number of random variables, but this still suffers from the same issues.

IN comes Bruijn variables. We can get rid of names altogether and simply use binding depth. In other words, the above example can be expressed as: \->\->_1 + _0 where _0 refers to the "most recent" lambda and _1 refers to a lambda once removed. This seems alot better, but still has that issue that deeply nested subtrees cannot be lifted nearer the root of the tree without introducing default values. Again, if the subtree contains the expression: _128 + 5, we must either only crossover that subtree to positions that are 128 lambdas deep, or we must determine that _128 has an arbitrary default value when unbound. More elegant, but still feels crufty.

Enter the perfect solution. Instead of introducing lambda as a primitive, lets introduces 2 other primitives.
K(x,y) -> x
S(x,y,z) -> (x(z))(y(z))

Let's also introduce, for the sake of simplicity of discussion:
I(x) -> x

which is just the identity function, and can be expressed in terms of S and K as the partial application S(K,K)

K is a simple function that takes 2 terms and returns the first, of type a->b->a
S is a function that takes three terms, applies the first term to the last and then applies that result to the second term applied to the last and is of type ((a->(b->c))->((a->b)->(a->c))). I is simply of type a->a of course.

The beauty of this is that we can factor out the concept of "variables" from the language and simply express them in terms of S and K. We can, in fact, implement the entire lambda calculus in terms of s and k. For instance, let's do \x->add(x,x), a simple function that doubles. This becomes:
S(K(add),I,I) so that ((\x->add(x,x)) 2) is the same as saying ((S(K(add),I,I) 2)... we have abstracted away variables in terms of 2 simple functions.

An additional gain here is that since lambda calculus can be implemented in terms of S and K, so can the Y combinator as:
Y -> S (K (S I I)) (S (S (K S) K) (K (S I I)))

So, we may choose to make Y available as a primitive, or let the genetic algorithm evolve it itself as needed, which gives our language full recursion.

All problems solved. Of course, if we want to have the Y combinator available, we need to move from a simple type inference to a fixed point inference in order to allow for those pesky infinite types... but that is not insurmountable. I think I will also need union types that can dispatch conditionally on type of expression in order so that I can deconstruct a return type a and get something useful out of it. But that can wait for later.

My brain hurts.