Tuesday, August 01, 2006

A stack is a context zipper

An evaluation context is a tree, and the stack is a zipper representation of the tree, allowing the part that changes the most--the hole--to be updated in constant time. In a context-sensitive reduction semantics, which models control as a stack, the "focus-down" rules unzip the context all the way down to its redex.

One cool thing you can do with this is reconstruct the source program. Given an expression evaluation stack, first replace the hole with the current expression being evaluated, then zip the context back up, and voilà! the original source code. I'm doing this in my JavaScript stepper to provide an intuitive visualization of the evaluation context within each function activation.

The only catch is to handle cycles in the source code, either due to recursion or loops. I don't have to worry about recursion, because I'm only doing this for individual function activations. Loops shouldn't be too much trouble, since they never accumulate stack.