Paul William Berg

I had visions of using Hindley-Milner style strong typing to constrain the search space of a Koza GP tree. After much struggling with the concept in my head, and not being totally up on my pi calculus, I think I have grokked the impasse. The problem is this:

Say we have a program tree: (+ X Y)

In this case it appears that strong typing is highly adventageous in that it constrains the selection of X and Y to those nodes that yield numbers. A node encoding the string "hello world" would never be chosen for X, as the type inferrence just wouldn't work out. Here's the rub. Let's say we have a "communicate data" function to communicate some unknown data across a network. We can tag this data with a type. But, how do we type the parse tree?

(let ((data (recieve-data))
  (if (number? data) data #f))

This infers to an intersection of {number, bool}. Well, we can't very well send that to +, now can we? We have to get rid of the bool somehow. We can arbitrarily assign a default, which might work for this simple case, but as we grow in functionality, this becomes rather unweildy:

(let ((data (recieve-data))
  (cond ((number? data) ...)
        ((procedure? data) ...)
        ((string? data) ...)))

The inference of this mess is across the board, especially if you allow that procedure in there which could return any tagged type. This requires you to allow a base type, datum, from which all types are derived. However, you are still left with the problem that once this let clause returns, you cannot, at tree-construction (compile) time, deduce what type was returned, therefore you can never, ever upcast to a number and pass it to +. Since +, and all other basic functions, can never be upstream from a run-time infered type, the expressivity of the language is unduly constrained. What this all seems to mean is that STGP is only useful for trivial type systems. I am going to re-read Tina Yu's doctorial thesis and see if there isn't some trick in there, but I'm pretty sure that that research was not not dealing with problems involving tagged data, but rather, the function type was not a fully fledged type and therefore it was not a problem for the system. I'm thinking that partially constraining types isn't very useful, in that we constrain trees to only allow function parameters that infer an intersection that could possibly hold the appropriate type. My hunch is that the vast majority of trees will infer down to datum (the intersection of all types) at which point you haven't constrained much at all and lose the benefit of typing altogether.

On the positive side, I have learned that type inferrence algorithms are probably the biggest pain in the ass algorithms I have ever come across in my life, and the idea that they don't work here is comforting to me as that means I don't have to write one. I am pretty sure that the increased search space will be made up for by the fact that I will be using a hierarchical evolutionary algorithm that keeps the population from converging on a solution.

My big problem now is how to encode variable bindings into a Koza tree. I would love to be able to encode this:

(+
  5
  (apply
    (lambda (x)
      (/ x 2))
    4))

I particularly want the lambda to be able to be constructed at run time, not evolved seperately as Koza did, so that we can have lexical closures. The messiness is in the "x". Where do we come up with the variables? I could use an infinite amount of symbols, by allowing the evolutionary algorithm to supply just text, but this leads me to hypothosise that the search space would be so huge that the terms of the lambda would never be referenced in the body. My thoughts are to supply a set number of globally bound variables, perhapse rebinding the ephemeral constant pool. This seems more adept, but still seems messy IMHO. Also, the ephemeral constants, if used, may be too numerous as to be almost as bad as raw symbol creation. The algorithm does me no good if the search space is so large that it cannot be computationally explored in my lifetime.

Suggestions? Am I offbase with my thinking on type inference?