Fair enough. Thanks for clearing that up! I'll take a look at Tina's work
and also see if perhaps we don't actually need a polymorphic type system;
I'm beginning to doubt that the it is all that necessary.

Now correct me if I'm wrong but I believe I can still get structural
typing. That is I can get types like Int -> Int, (Int, Int), Either Int
Double, [Int], etc... as long as I keep polymorphism out. This seems valid
to me sense you could, just like atomic types, compare the canonical
strings of two types to determine equality (or in practice just compare
them structurally).

For instances there could be a sub class of GPType call GPPairType in which
the compatibility function would return true if a) the other type were a
GPTypePair and b) the two respective types are also compatible. I don't see
the same issue arising here at all. The only issue I can see is that
perhaps this would not play nice with GPSetType if GPSetType assumed all
it's elements were GPAtomicType. Does it make this assumption or am I safe
in having sets of pairs?

On Sat, Jan 11, 2014 at 10:09 PM, Sean Luke <[log in to unmask]> wrote:

> 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.
> Sean
> 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