[Push] On re-entrant PUSH programs and how prefix is postfix
Lee Spector
lspector at hampshire.edu
Wed Feb 4 17:30:12 EST 2004
Maarten,
I really like this re-entrant extension! I went to some pains a long
time ago to implement something similar for Lisp-style expressions
(primarily for use in ErunticLab, which used GP-like control/evolution
in a grid-based alife environment). ErunticLab is probably not very
interesting to anyone anymore, but the "CodeStepper" utility may be of
slightly more lasting interest (it's at
http://hampshire.edu/lspector/CodeStepper-v2.1.lisp). Amusingly enough
in relation to your message, CodeStepper works by translating the
prefix Lisp code into postfix!
I'm not as sold on the prefix version of Push you've outlined (hsuP?).
Postfix and stacks just seem like a natural pairing to me -- you push
things on stacks first and then call instructions that operate on
them... But maybe I have to meditate on your examples some more.
Also: I never got back to you on CODE.CALL, which I also think is a
very nice solution to the "safe environment" problem. I'm including
your message on that below in case others on the list have comments. (I
hope that's okay!)
When I get past a couple of deadlines and have time to do some
revisions I plan to look into both of these more, probably implement
them, and probably add them to the spec. They both seem quite useful.
(The re-entrant thing would probably change the way we deal with Push
code running via the plugin in the BREVE simulation environment...)
In other news: I've just added to my development version of the Lisp
Push2 code the following instructions:
CODE.FROMINTEGER
CODE.FROMFLOAT
CODE.FROMBOOLEAN
CODE.FROMNAME
CODE.DO*TIMES (pops and executes the top code a number of times, with
the number
taken from integer stack)
CODE.DO*COUNT (like DO*TIMES but also pushes index before each
iteration)
The "FROM" ones are just translations that got overlooked in the
Push1->Push2 transition (they used to be things you could do with
CONVERT). They just move the items from the various stacks to the code
stack. The other two are obvious iterators -- although I've sometimes
used similar things for particular problems I had kept the spec
"recursively pure," but now that seems pretty silly. So I plan to
migrate these to the spec, the posted lisp code, and (Hi Jon!) to the
C++ code in the not-too-distant future.
-Lee
--- Maarten's message on CODE.CALL ---
From: mkeijzer at xs4all.nl
Subject: Push2 envs
Date: January 29, 2004 7:05:27 AM EST
To: lspector at hampshire.edu
Reply-To: mkeijzer at xs4all.nl
Hi Lee,
though you're probably frantically busy with assigning papers to,
amongst
others, me, just a thought about the environment stuff in Push2. I
think it's
possible, and maybe most elegant but opinions might differ, to implement
exectuting code in a safe environment with just a single additional
primitive, tentatively called CODE.CALL (or CODE.EXEC, or whatever).
What
this one does is exactly what CODE.DO& does, but instead of leaving the
embedded environment in a read-only state for further inspection, it
will
pack this entire environment in a CODE statement and pushes it on the
caller's CODE stack. This piece of code, when executed in a fresh
environment
would unwrap to exactly the end environment of the CALL statement.
Thus: if the end environment of the CALL is:
INT STACK: (1 2 3)
BOOL STACK: (True)
FLOAT STACK: ()
CODE STACK: ( (CODE.CALL) 1)
It will create the code statement:
(
(3 2 1)
(True)
()
(CODE.QUOTE 1 CODE.QUOTE (CODE.CALL) )
)
Nicely bracketed for easy inspection.
Just a thought,
-Maarten-
On Feb 4, 2004, at 4:28 PM, Maarten wrote:
> Hi all,
>
> here's a note on evaluating programs in the push language. As Lee might
> remember, in the early days of push (gecco SF) I asked if push could
> be used
> in time-slicing environments --- mainly because I foresaw problems with
> non-halting programs (in that non-halters by definition take the most
> computational resources). This was safely ignored by Lee, who just
> uses an
> upper bound on execution time. I still think that for evolving
> programs,
> complete control over the execution of the programs is important.
>
> Now I've got my own implementation in python running (will make this
> available
> at some point), and have taken the opportunity to implement my own
> 'reentrant' push interpreter. It turned out to be deceptively simple,
> with a
> small twist that prefix push programs are easier (faster) to interpret
> than
> postfix programs. This was an unforeseen side-effect, and because I
> think
> prefix is easier to read/write than postfix, I'm posting the algorithm
> here.
> If you don't care, you can stop reading now.
>
> Ok, a re-entrant interpreter. What I wanted to achieve is to run a push
> program for some time-steps, abort it after the limit is reached and
> pick up
> the computation where it left of whenever I so choose. With a recursive
> interpreter, this is hard. Stopping the execution after a number of
> steps
> isn't that big a deal, but re-entering it again... don't see it happen
> that
> easily (but then again, I never understood what call with current
> continuation does in scheme either.)
>
> How I finally chose to implement it is with YAS (yet another stack),
> this time
> an execution stack. This one is similar to the CODE stack, but holds
> everything that is yet to be executed. It has no operators defined on
> it.
> Whenever for instance a DO* is executed, the statement will push the
> top of
> the code stack on this execution stack, and returns. DO will first
> push a
> CODE.POP statement and subsequently the code (while leaving the code
> on top
> of the code stack)
>
> Whenever an execution is performed, the interpreter will pop the
> execution
> stack: if it's an instruction, it will get executed (in the case of
> DO(*)
> this will add stuff on the execution stack, while in the case of
> QUOTE, the
> next item on the execution stack will get popped and pushed on the CODE
> stack.). If however the top of the execution stack is a piece of CODE
> itself
> (a list), something interesting happens: first the elements of the
> list are
> pushed on the executions stack, and until the top item is an
> instruction this
> is repeated. BUT: to implement the postfix syntax of PUSH, they need
> to be
> pushed in REVERSE order. If I were to push them in normal (efficient)
> order,
> we would get a prefix interpretation of a push program (except of
> course for
> CODE.QUOTE, which would become postfix). This is normal with popping
> stacks
> on other stacks, but given that this seems to be an efficient way to
> implement a reentrant (and iterative) interpreter, it might deserve
> some
> consideration.
>
> An example might help: suppose we have the following piece of code:
>
> Code Stack: [ ( (4 3 2) (+ *) ) ]
> Exec Stack: [ DO* ]
>
> (types ommitted for brevity, using [a,b,c] syntax to indicate a stack
> and (a b
> c) for a list: for readibility)
>
> Ok, next instruction: DO* gets popped from the execution stack, and
> will push
> the top of the code stack on the execution stack:
>
> Exec Stack: [ ( (4 3 2) (+ *) ) ]
>
> Next instruction: the top of the execution stack is a list, so the
> elements
> will get pushed in REVERSE order, first (+ *)
>
> Exec Stack: [(+*)]
>
> then (4 3 2)
>
> Exec Stack:[ (4 3 2) , (+ *) ]
>
> Again, as the top of the stack is still a list, the process is
> repeated: first
> push 2, then 3, then 4 (So REVERSE order) to get:
>
> Exec Stack: [ 4, 3, 2, (+ *) ]
>
> Now we're ready to evaluate the next arguments, but note that we can
> abort the
> calculation here, and pick it up whenever we feel like it. In the end,
> this
> will have executed 4,3,2,+,* and results in 20.
>
> This is how it works now, and it works exactly like a normal,
> recursive,
> interpreter. The only thing I don't like is that I have to reverse the
> lists
> and pop them on the execution stack whenever such a list. Funnily
> enough, if
> one were to not do that (just push the car of the list first), the
> interpretation becomes prefix. Same example:
>
> Code Stack: ( (* +) (2 3 4) ]
> Exec Stack: [DO*]
>
> Now, after pushing the code on the execution stack, we will unwrap it
> by first
> pushing (* +), and then pushing (2 3 4): this leads to
>
> Exec Stack: [ (2 3 4), (* +) ]
>
> and another round: push 2,3,4 in order:
>
> Exec Stack: [ 4, 3, 2, (* +) ]
>
> Almost exactly the same situation as above, only now CODE is prefix
> while
> execution is postfix. It is still reentrant: by keeping the execution
> stack
> together with the other stacks we can pick up calculations whenever
> we want
> to continue the evaluation. Continuing the example: execution of 4,3,2
> will
> lead to:
>
> Int Stack: [2,3,4]
> Exec Stack: [ (* +) ]
>
> Another round of pushing:
>
> Int Stack: [2,3,4]
> Exec Stack: [+,*]
>
> and the net result is 20 as above
>
> Maybe not too big a deal, but I do see a very efficient C(++)
> implementation
> lurking here, which is reentrant and where code is prefix. I
> personally like
> prefix, and maybe genetic programs like it too (I'm pretty sure it does
> actually, but that's another discussion). I post it here maybe for some
> discussion, but mostly for your information. The reversing of lists
> can be
> circumvented quite easily, so I highly doubt it's an efficiency issue.
>
> With prefix CODE (yet postfix execution), the principle of least
> surprise is
> more easily implemented. Take for example the snippet:
>
> (- 4 3)
>
> One would expect this to evaluate to 1. With the current push
> definition, this
> does not happen: the execution stack will be [3 4 -] and the
> definition of
> minus subtracts 4 from 3, resulting in -1. But ok, this could be
> fixed, yet
> is not nice, as many operators need to be reconsidered...
>
> So, all in all, given the amount of change involved (a reversal of
> practically
> anything no less, and reconsideration of asymetric operators) please
> consider
> this mainly a curiosum. I'm perfectly happy to live with reversing the
> code
> everytime I want to push it on the execution stack, but might, for my
> own
> experiments (Lee: I'm planning to see if I can get paper #340 to work
> in
> push) go with a prefix approach... not sure though.
>
> Just a small sample, with all usual push interpretation conventions in
> place,
> but only by avoiding to reverse the list in my implementation, the
> infamous
> factorial function is the following:
>
> ( CODE.IF
> INTEGER.< 2 INTEGER.DUP
> (INTEGER.* CODE.DO INTEGER.- 1 INTEGER.DUP CODE.DUP)
> CODE.QUOTE
> (INTEGER.POP 1)
> CODE.QUOTE
> )
>
> Note that the all-important control statement CODE.IF is now at the
> top of the
> list, and 'maybe' the thing is slightly more comprehensible.
>
> As I said, FYI,
>
> -Maarten-
>
>
>
>
>
>
>
> _______________________________________________
> Push mailing list
> Push at lists.hampshire.edu
> http://lists.hampshire.edu/mailman/listinfo/push
>
>
--
Lee Spector
Dean, Cognitive Science + Associate Professor, Computer Science
Cognitive Science, Hampshire College, Amherst, MA 01002
lspector at hampshire.edu, http://hampshire.edu/lspector/
Phone: 413-559-5352, Fax: 413-559-5438
More information about the Push
mailing list