[Haskell-cafe] Looking for practical examples of Zippers
claus.reinke at talk21.com
Wed Apr 1 08:34:21 EDT 2009
>my quest for data structures continues. Lately I came across "Zippers".
>Can anybody point be to some useful examples?
Once upon a time, there was a hardware implementation of a lambda
calculus based functional language (mostly, I was told, to show that it
could be done:-). The program representation was a string of symbols
(graph reduction came later; implementation of graph reduction on
stock hardware came much later) in a constructor syntax (think fully
applied data constructors in Haskell, each constructor annotated with
The problem: if you were to do beta-reductions somewhere in the
middle of such a string, you'd have to make space or fill gaps, to
adjust for the differing lengths of redex and reduced, not to mention
the issue of finding and identifying the redices in the first place.
Working in hardware, you couldn't quite ignore those details.
The solution: use a hardware zipper representation, consisting of a
system of 3 main stacks (there were auxiliary stacks to handle things
like substitution), often likened to a railway shunting yard:
To traverse a program expression:
- the program starts on the input stack, in pre-order form (the
constructors before their arguments).
- take a constructor from the front of the input stack, put it on
the control stack, initialising a counter for the arguments.
- while there are still arguments left, recursively traverse them
from input to output stack, decrementing the constructor
- after all parameters of the constructor on top of the control
stack have been traversed to the output stack, move the
constructor to the output stack
- the program ends up on the output stack, in post-order form
(the constructors after their arguments, though still on top
of them, stack-wise).
That way, all sub-expressions would, at some point of the
traversal, appear on the top of the three stacks, so if there
was a redex on top (application constructor on control,
function on one stack, argument on the other stack), the
processor could replace the redex by a reduced expression
without having to make room or fill gaps, or look anywhere
but at the top of the stacks.
There was even a special graphical notation, to specify the
elaborate mix of control- and data-flow going on, but at the
heart of it all was that traversal scheme over a shunting yard
of stacks, based on a zipper in hardware.
More information about the Haskell-Cafe