An Applicative Control-Flow Graph Based on Huet's Zipper

Norman Ramsey and João Dias

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).