An Applicative Control-Flow Graph Based on Huet's Zipper
We are using ML to build a compiler that does low-level optimization.
To support optimizations in classic imperative style, we built a
control-flow graph using mutable pointers and other mutable state in
the nodes.
This decision proved unfortunate: the mutable flow graph was big and
complex, and it led to many bugs.
We have replaced it by a smaller, simpler,
applicative flow graph based on Huet's huet:zipper zipper.
The new flow graph is a success;
this paper presents its design and shows how
it leads to a gratifyingly simple implementation of the dataflow
framework developed by lerner:composing.
Full paper
The paper is available as
US Letter PostScript (407K),
US Letter PDF (194K),
and
US Letter TeX DVI (106K).