Function calls and the ENV concept
March 15, 2011by Maarten Keijzer (maarten)
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.
- 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)
- every execution slice that is allocated to this env will go to this new interpreter instead, until…
- 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)
- done
March 19th, 2011 at 1:20 pm
Thanks Maarten! Interesting and clean, and maybe related to something I’m about to post about monads…
March 19th, 2011 at 1:50 pm
[…] Function calls and the ENV concept […]
March 26th, 2011 at 4:19 pm
This seems like it provides isolation in only one direction; the callee environment is isolated from changes in the caller, since it receives only a small slice of the caller environment, but the caller is not isolated from the callee, since the entire callee environment is returned to the caller, and so any changes in the callee code will tend to disrupt the caller state. Perhaps instead of returning the entire environment, ENV.DO could just push the top of the CODE stack from the callee environment onto the top of the EXEC stack in the callee?
My uninformed hunch is that isolation would only provide benefit in the very long run; for example, in an artificial life application, where genomes have to continually adapt to a complex, changing environment, modularity might provide more benefit because it could permit multiple traits to evolve independently. In a GP application where the fitness function is fixed and relatively simple, it seems less likely that modular isolation would provide much benefit. However, I have no evidence to support any of this.
March 27th, 2011 at 4:34 am
It actually does supply isolation in both directions. Note that, before the caller takes on board the environment of the callee, the callee has finished execution. So there is no code to be run: the code on the code stack being protected through quotes.
Effectively what happens is that the callee runs some code provided by the caller, runs it until completion, and the return value of the callee is the contents of all stacks. If the caller pushes this result on its EXEC stack, it will effectively append the callee’s stacks to the caller’s, while if it pushes it on the CODE stack, it will work much as you describe.
In the first case, it provides isolation of the stack contents pre-call. There is no way that running the program in a seperate env will tamper with the stack contents of the caller. When it is done, it will only append to it. In the second case, isolation is total, the caller takes the env of the callee as a piece of code on the code stack, ready to be examined (or discarded).
March 27th, 2011 at 4:59 pm
I suppose it depends on exactly how you define isolation. Of course the isolation can’t be complete because if the caller is completely isolated from the callee, it can’t get any output. It’s just a question of how broad the communication channel is. My concern is that this design makes it too hard for the callee to avoid communicating information back to the caller: many if not most mutations to the callee code will result in a different set of final stack depths. This will tend to disrupt the subsequent behavior of the caller: the fact that the stacks prior to the ENV.DO retain their contents after the ENV.DO is irrelevant if the code after the call is unable to access those contents, and since the stack contents are accessed positionally, a change in stack depth is tantamount to destroying that data.
This all assumes you return on the EXEC stack; if you return on the CODE stack, this argument is mitigated somewhat, but it’s unclear to me how much scope the caller has to process the top of the CODE stack in a way that protects it from these types of changes.
The point of my suggestion (return the top of the CODE stack only) was to narrow the communication channel from callee to caller, ensuring that the callee has a substantial amount of flexibility to modify its implementation (or rather, to have its implementation mutated) without affecting its interface, since any mutation that leaves the top of the CODE stack unchanged is benign. This ability to evolve the caller and callee independently is critical to the benefit that I speculate this kind of isolation can provide.