Push

I just watched a tutorial on monads (http://www.vimeo.com/20717301), and I was thinking about it in the context of the fact that Push instructions in some versions of Push (e.g. clojush) are all implemented as functions that take and return complete Push interpreter states. Very monad-like, I think. Mulling this a bit more I think there’s probably a nice way to use related ideas to provide a more elegant and uniform approach to several issues that have come up recently, including:

• Protected state, as raised by Geoffrey Romer on the Push list and also addressed by Maarten Keijzer here.
• The various uses to which the “auxiliary” stack has been put in some versions of Push, for problem inputs and other non-stack-like kinds of storage (e.g. tag bindings).
• The handling of abnormal conditions (insufficient arguments, maybe semantic errors like division by zero).
• More radical changes to the stack-based paradigm, e.g. Kyle Harrington’s experiments with a version of Push using bi-directional tapes instead of stacks.

I had previously mulled using the name Mush for a version of Push based around Maps (as in “hash maps”) rather than stacks, with stacks being just one kind of value to which something could map. In fact that’s what’s going on under the hood in clojush anyway. But maybe with some monad concepts mixed in the M in Mush could stand for “monad” instead (or in addition).

I haven’t thought this through to its logical conclusion; I’m sharing it in case anyone else would like to…

This message in response to a request from Lee to try to explain what the ENV concept was and how it relates to function isolation in Push.

The concept is really simply and relies upon a single observation: given a push program and its current state (i.e., the states of the stacks), can we construct a program that, when run on an ’empty’ interpreter (an environment, ENV), will reproduce the exact state of the running program. This is possible.

Suppose you execute a program ( CODE.QUOTE (a b) 1 2 + 3 *), and everything before the ‘*’ sign has executed. If we want to describe what is going on we can say something like:

The INT stack contains a 3 followed by a 3

The Code stack contains the program (a b)

The EXEC stack contains the single instruction ‘*’

We could however also say that the ENV is described by the program

(  3 3 CODE.QUOTE (a b) * )

[Updated 19th March, the code above had a plus where it should be multiplication]

Which effectively, when run in a clean environment, will reconstruct the original situation. It’s not that hard to create a program like this from within any given interpreter (and it’s a great way to achieve persistence, serialization, etc.).

I’ve always taken this method of creating a program out of an environment to be the ideal return value of a function call. This has lead me to define a function call in Push3 as follows.

1. ENV.DO will take the top of the code stack and start running this piece of code in a new interpreter (puts it on the EXEC stack there)
2. every execution slice that is allocated to this env will go to this new interpreter instead, until…
3. When the execution stack of the new interpreter is empty, i.e., it is done, create a program of the ENV, and treat that as a return value by either putting it on the CODE stack or directly on the EXEC stack (I usually pick the latter)
4. done