[Push] On re-entrant PUSH programs and how prefix is postfix

[Maarten]

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-