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.


aditya said...

Good post thanks for share information.
iteducation learning
highe ducation here
iteducation course
first education info
itlesson education

uncontested divorce in va said...

Thanks for sharing beautiful content. I got information from your blog.Keep sharing
uncontested divorce in va
separation before divorce
Commercial Contract Disputes