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

[Maarten]

Hi Lee,

> I'm not as sold on the prefix version of Push you've outlined (hsuP?).

To be quite honest, I didn't expect you to be. You might want to decide at 
some point if you're a lisp-head or a forth-head though! Personally, I prefer 
infix :-/

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

The prefix stuff works nicely for the more functional operations, like 
arithmetic. It becomes a bit more awkward for the explicit stack 
manipulations, though it's not too bad (I do have to mention I haven't 
explored it in depth though). In prefix, 

(BOOL.YANK 3 TRUE FALSE FALSE CODE.YANK BOOL.OR FALSE TRUE )

can be interpreted as taking the result of the fourth boolean operation to the 
left of the operation. In this case, it would be the OR. For this 
interpretation, you do not need stacks. It's a 'regular' lisp program flow 
where types are mixed.

The CODE.YANK is there to slightly confuse the issue. If you imagine a CODE.DO 
there, it would become a bit more hairy, as you would have to figure out 
which code will be executed in the middle and what it's boolean 'return 
values' are... In short, though the stacks are still there, the set of stacks 
can be considered the 'type' on which each operation works. The OR function 
for instance will get a set of lists (the type) as input, take the boolean 
list and ORs the first two on the list, returning it together with the other 
'unchanged' list. This looks a bit like Peter Martin's polymorphic GP system. 
Nothing is lost, nothing is gained. It all boils down to what you're most 
comfortable with.

However.

I think the main advantage of prefix lies in the ability to get the most 
important code at the front of the list, instead of the back. If you are to 
do any kind of arithmetic, in postfix, the most important (root) node will be 
at the back of the expression. Given that most code manipulating operators 
are lisp-inspired, this back is not as easily accessible as the front. This 
might hinder evolution considerably. In the past, I have experimented a bit 
with prefix versus postfix in my logic programming approach, and found that 
prefix seemed to work better. This is an unpublished 'seemed', so don't take 
my word for it. In any case, having the code that produces the final result 
to be most easily accessed might be something to consider. 

This is a an empirical question though. There are also a few practical 
advantages, one is that the idiom 'operate on second element' in the case of 
binary functions can be replaced with the more cleaner 'operate on first 
element'.  I'm assuming that this idiom was introduced for readibililty 
purposes, as I think a full postfix interpreter would have nothing of that 
kind of thing.

But as I said, it's just a thought, I'm not seriously suggesting to reverse 
everything.

-Maarten-

PS. when implementing push I noticed that for an imperative solution, both 
SHOVE and YANK are relatively expensive as they induce copying (large) parts 
of the stack. I noticed that both can be implemented using the fast SWAPNTH 
(take value from the integer stack and swap that nth element with the first). 
Maybe add SWAPNTH?

PPS. Another thought: why CODE.FROMBOOLEAN etc., and not simply add a generic 
function TOCODE (or simply QUOTE??) ? Saves on the syntax, CODE.TOCODE is a 
NOOP, and there is precedence for having TYPE.OP operate on a different stack 
than TYPE (TYPE.= pushes on the boolean stack, CODE.NULL, CODE.ATOM,  does 
that too, not to speak of CODE.SIZE, CODE.POSITION, CODE.LENGTH that operate 
on the integer stack.)

PPPS. no stopping me now... just an observation on the reentrant interpreter. 
CODE.QUOTE could be called CODE.FROMEXEC, while CODE.DO* could be called 
EXEC.FROMCODE... This is not a suggestion for a name change (far from it), 
but simply to illustrate the duality between (quoted) code (on the code 
stack) and executable code (on the execution stack).