[Push] Re: Java Push
Lee Spector
lspector at hampshire.edu
Sun Dec 8 04:56:57 EST 2002
Hi Russ,
I'm cc-ing this to the Push mailing list since I think some of the other
subscribers might also be interested in these issues or have something to
add -- I hope you don't mind (let me know if you do!).
I'm just gotten to Australia for the ALife conference and am still
jet-lagged (if I'm calculating it right I've been up for 45 hours except
for sporadic naps during 20 hours of flight time!) BUT I want to give you a
quick reply now because I'm not sure when I'll next have the chance. Please
do follow-up if I miss something and we can continue the discussion when
I'm in better shape.
In my implementation EXPRESSION is just an "abstract" type, meaning it
doesn't have a stack or really exist in the running Push interpreter at
all. The reason it exists is so that there can be other types (with stacks)
for the manipulation of code, aside from the CODE type/stack which is the
one that DO, DO*, IF, and MAP use. The main reason I did this was for
Pushpop, in which another sub-type of EXPRESSION, called CHILD, is used to
build offspring (in lieu of traditional, hand-coded mutation/crossover
operators). But I don't use CHILD when I run PushGP anyway, so the only
EXPRESSION type/stack is CODE -- since you have this I think we're doing
the same thing. As an aside, however, Keith Downing, who has also
implemented his own Push interpreter, uses an auxiliary "data" EXPRESSION
stack just as a scratch-space for code manipulation, and this seems to me
to be a good idea.
On Parity: We have tried to evolve general parity functions (that work for
any input size) but only succeeded up to finite sizes -- in other words
while we could evolve programs that worked for all inputs of all lengths up
to some limit (I don't remember how high we went, maybe 8 or 10) the
resulting programs were never truly general. What almost always evolved
were strategies based on code duplication (some finite number of times)
rather than input-limited recursion. Of course the evolved programs were
just as good as the "general" versions with respect to the (finite) fitness
test, and indeed we were running up against the ubiquitous problem of
under-determination in machine learning: there are infinitely many ways to
generalize any finite training set, and the system has no reason to believe
that any one is better than the others. The solutions that I said didn't
generalize really did generalize in SOME way, but just not in the way that
Parity generalizes. Alan Robinson and I came to think that the kind of
generalization we were getting was just an artifact of the instruction set
and biases inherent within it in the context of the larger PushGP system.
In other words it just happens to be easier (in the context of the
instruction set and PushGP's operators, etc) to come up with the
duplication-based strategies than the input-limited recursion strategies.
It would be interesting to see what changes could reverse this bias, but we
haven't done that.
Alan experimented with a couple of different ways of encoding input to
Parity but the one that worked best (and that we used most) was to push
each of the Boolean values individually onto the Boolean stack before
running the evolved program. If I recall correctly two other schemes that
we tried were to push an expression containing all of the Boolean inputs or
to push nothing but to provide instructions for each of the input variables
(e.g. IN3, which would push the value of the 3rd Boolean input onto the
Boolean stack).
On MAP: I believe your description is indeed exactly what I do. Four fine
points: 1) If the first thing on the code stack isn't a list I make it into
one (a list with a single element), 2) when you do your step b.3 you should
also pop each item from the code stack as it is "collected," 3) if the
resulting list is larger than *max-points-in-program* then don't push it,
and 4) be sure the resulting list is in the order of the executions, not
reversed. I'll include my Lisp source below in case that helps.
The new control structures that you are working with sound really
interesting! I hadn't thought of multiple-quote primitives...
Let me know what gaps I've left...
-Lee
P.S. Thanks for all of the interesting EVEN solutions!
P.P.S. Here's my MAP source:
(defun &map (type)
"Treats the item on top of the stack of the given type as a
list (coercing it to a list if necessary) and the second element
as a body of code to apply iteratively to each element of the list.
The arguments are both popped prior to the recursive evaluations.
The results are collected and pushed as a list."
(unless (null (rest (pushtype-stack type)))
(let ((the-list (ensure-list (first (pushtype-stack type))))
(the-code (second (pushtype-stack type))))
;; clear the args
(pop (pushtype-stack type))
(pop (pushtype-stack type))
;; do the mapping
(let ((results nil))
(dolist (item the-list)
(push item (pushtype-stack type))
(evalpush the-code)
;; extract, save, and remove the result
(push (first (pushtype-stack type)) results)
(pop (pushtype-stack type))
(when (> (count-points results) ;; escape if result is bloating
*max-points-in-program*)
(return nil)))
(unless (> (count-points results)
*max-points-in-program*)
(push (reverse (copy-tree results))
(pushtype-stack type)))))))
---
Hi Lee,
Would you answer a couple of questions for me regarding your instruction
set and how you solved the parity problem.
In my current implementation, I didn't implement any Expression stacks
other than the Code stack. That was sufficient to solve the even-problem.
(I have lots of solutions to that. My favorite is: quote (true false) nth
exe. [exe is your do.]. Here is another cute one: (first) nthPoint isAtomic
not. [first is your car, and it puts "(first)" on top of the code stack.
nthPoint selects the nth subtree of that expression. Like nth, it wraps
around. The 0th subtree is the entire expression, "(first)" in this case;
the first subtree is the one leaf, "first" in this case. isAtomic then asks
if it is atomic, which is the inverse of the correct answer, and not
inverts the answer.)
But I haven't been able to solve the Binary-to-Integer problem. I start
with 0 on the Integer stack and some sequence of bits on the Boolean stack
(high order on top) and expect the Integer equivalent to end up on the
Integer stack. I even added some specialized instructions so that the
following would be a solution: isEmptyB exitIfTrue double castBI + exe.
(isEmptyB pushes true onto the Boolean stack if it had been empty;
exitIfTrue terminates if the top element of the Boolean Stack is True;
castBI pops the Boolean Stack and pushes 0 or 1 onto the Integer Stack
depending on what was popped from the Boolean Stack; double doubles the top
element of the Integer Stack.) After running for a very long time, no
solution emerged.
I'm now trying an even simpler problem, the "length" problem, in which I
again push 0 onto the Integer Stack and a number of true/false values onto
the Boolean stack. I want a count of the number of Boolean elements to
appear on the Integer Stack. I added more instructions so that the
following would be a solution: isEmptyB exitIfTrue popB incr exe. (popB
pops the Boolean Stack; incr increments the top element of the Integer
Stack.)
So my questions are:
1. How much does your system depend on the Expression stack (which I don't
have)?
2. What is your input to the parity problem?
3. How exactly does Map work? Is this correct?
a. pop the Code stack twice;
b. for each element in the list which was first on the code stack,
b.1. push it onto the code stack;
b.2 execute what was originally the second element on the code stack
b.3 collect in a list the top element of the code stack after each such
execution
c. push that list back onto the code stack?
Also, you talk about the parity problem as a number of separate problems,
one for each arity. Are you able to solve the general parity problem,
where the number of bits is not specified in advance? The problems I
mentioned above seem to be of that sort, where the size of the input is not
specified in advance.
I've also been playing around with some additional control structures,
hoping they would help. ifQ Condition Then-Part Else-Part is if in the
normal direction. I call it ifQ because the three components are
essentially quoted before being executed. Similarly, there is whileQ
condition body. Finally, there is exitIfTrue and returnIfTrue, which
terminate the entire program or terminate the current recursion
respectively if the Boolean stack contains true. returnIfTrue would allow
this solution to the length problem: isEmptyB returnIfTrue popB 1 exe +,
whereas with exitIfTrue , it would have to be: isEmptyB returnIfTrue popB
1 + exe.
I've also defined many variations on your do:
exe is do;
exe* is do*
exeExit is exe, but terminate if the same expression is about to executed
again, i.e., block recursion. This is used when exe is intended to succeed
by using up the allowable cycles. Another way of looking at it is that it
executes an expression as a program's "last wishes."
exeReturn is similar but, like returnIfTrue, it blocks the recursion and
then returns from the current recursion and continues the computation.
Thanks.
-- Russ
--
Lee Spector
Dean, School of Cognitive Science
Associate Professor of Computer Science lspector at hampshire.edu
Cognitive Science, Hampshire College http://hampshire.edu/lspector/
Amherst, MA 01002 413-559-5352, Fax: 413-559-5438
More information about the Push
mailing list