January 2014


Options: Use Monospaced Font
Show Text Part by Default
Show All Mail Headers

Message: [<< First] [< Prev] [Next >] [Last >>]
Topic: [<< First] [< Prev] [Next >] [Last >>]
Author: [<< First] [< Prev] [Next >] [Last >>]

Print Reply
Sean Luke <[log in to unmask]>
Reply To:
ECJ Evolutionary Computation Toolkit <[log in to unmask]>
Sat, 11 Jan 2014 23:09:50 -0500
text/plain (76 lines)
Jake, your example implies a much more complex typing system than ECJ provides.  Notably, "Forall" implies an arbitrary number of possible types.  Set typing is explicitly more constrained than this: it only permits sets of a predefined and finite number of possible symbols.

Set typing is a very simple and limited typing scheme, more powerful than "classic" STGP, but rather less powerful than polymorphic typing schemes.  Hindley–Milner it is not.  The goals of the typing mechanism is to allow very fast, essentially constant-time, type constraint determination; and to have a typing which can be done entirely locally without either (1) having to do inference throughout the tree or (2) having to update the resulting typing of nodes throughout the tree. 

If what you need is a polymorphic type system, or at any rate a richer set of type constraints than ECJ's simple system, you're on your own.  It is not easy to build such systems into a GP framework in a way which is compatible with many other elements, notably mutation and common tree builders.  If you want to go after this, Tina Yu did her thesis work in that, and Maarten Keijzer also did work in it (and I think some of his code made its way into EO).  But in truth I think the easiest approach is to use Grammatical Evolution instead.  ECJ has a rudimentary GE framework which will probably serve your needs.


On Jan 11, 2014, at 5:29 PM, Jake Ehrlich wrote:

> "constraints placed on the nodes to enforce rules about which nodes can connect to which nodes" I couldn't agree more but I guess I don't see how to express certain constraints in this particular framework.
> say you have a function F : (forall a. a -> a) -> Int (where ':' means "of type") and a function G : (Int -> Int) -> Int. As well say there are two expressions, X : forall a. a -> a and Y : Int -> Int
> Assume two trees (call them A and B) have forms (F X) and (G Y) respectively and A and B are selected for crossover. The nodes for X and Y are chosen to be swapped. sense X's type unifies with Int -> Int and Y's type unifies with forall a. a -> a the crossover is allowed. That said it should not be allowed that Y be passed to F. The expression (F Y) is ill-typed. On the other hand the expression (G X) is fine and perfectly valid.
> How then can I express the constraint that Y can not be passed to F but that X can be passed to G? Sense compatibleWith is commutative and the constraint I specify is not it would appear that this cannot be expressed using compatibleWith; something else must be needed.
> I like functional programming and type systems, hence the choice of types. I can reformulate this in terms of Java or some other language however. For instance say there is an interface class "Shape" and another class "Square". say F : Square -> Int, G : Shape -> Int, X has type Square, and Y has type Shape. The same issue arises F Y is ill-typed but G X is not.
> The issue seems to arise anytime a return type is allowed to be more than atomic, that is there is a notion of more than 1 type "belonging" to the return type weather it be parametric polymorphism, set types, or subclass polymorphism.
> Am I missing something and/or is there a way to express the desired constraint?
> On Jan 11, 2014 10:21 AM, "Sean Luke" <[log in to unmask]> wrote:
> Types are not data passed between nodes.  They are merely constraints placed on the nodes to enforce rules about which nodes can connect to which nodes.
> Now, it's true that types often are correlated with the kinds of data that nodes send to each other, but that's hardly a requirement.  For example, we're using types right now simply to force certain kinds of nodes to appear in the top area of a tree but not down near the leaf nodes.
> The most common situation you'll find is argument types which are set types, and return types which are atomic types.  For example, you might have a node which returns int plugged into an argument which can accept int or double.  You've seen that before in real programming languages I'm sure: the + operator in most programming languages can take floats, ints, doubles, longs, bytes, indeed in some cases strings.
> All you have to do is handle multiple kinds of data in your GPData object.  The typing mechanism merely guarantees that when a node receives a GPData object, what you receive has been constrained in a way that you had specified.
> Sean
> On Jan 11, 2014, at 10:52 AM, Jake Ehrlich wrote:
> > OK that explains more. Thanks for the clarification
> >
> > As to the example, yes you understood. I am still confused however on how something of type {s, i} can be passed in to something expecting an integer. What if that something returned a string?
> >
> > On Jan 11, 2014 8:59 AM, "Sean Luke" <[log in to unmask]> wrote:
> > On Jan 11, 2014, at 2:00 AM, Jake Ehrlich wrote:
> >
> > > In the documentation for it says "Then a random
> > > node is chosen in each tree such that the two nodes have the same return
> > > type". Does "same return type" in that quote mean that the types "fit" by
> > > GType's compatibleWith method?
> >
> > The documentation is misleading.  The correct form is:
> >
> > Two nodes M and N are chosen.  Let R(N) and R(M) be the return types of
> > M and N respective.  Let A(N) and A(M) be the types of the argument slots
> > which N and M respectively fill in their parents.  Then M and N are only
> > valid if R(N) is type compatible with A(M) and R(M) is type compatible
> > with A(N).
> >
> > > First off as I understand it GType.compatibleWith is assumed to be
> > > commutative (that is t1.compatibleWith(init, t2) is true if and only if
> > > t2.compatibleWith(init, t1) is true). Is this correct or is it just one way?
> >
> > compatibleWith is commutative.
> >
> >
> > > Say you have a node X of type {string, int} (a set type) and another node Y of
> > > type int (an atomic type). X and Y are being passed in as parameters of type
> > > {string, int} and int respeticvlly. These return types are "compatible" ("fit") by
> > > the definition of compatibleWith for GPAtomicType and GPSetType yet you
> > > shouldn't be allowed to swap them sense the parameter type of X's parent
> > > can't handle a string, only an int.
> >
> > Let me make sure I understand what you're saying.  Node X is of return type {s,i} and it's attached to an argument slot of type {s,i}.  And node Y is of return type i and is attached to an argument slot of type i. If you swapped them, then node X would now be in the argument slot i (which it is type-compatible with) and node Y would now be in argument slot {s,i} (which it is also type-compatible with) so everything would be fine.
> >
> > Sean