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

AbstractWe 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, Gérard, 1997. The Zipper. Journal of Functional Programming, 7(5):549–554. Functional Pearl] 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, Sorin, David Grove, and Craig Chambers. 2002. Composing dataflow analyses and transformations. Conference Record of the 29th Annual ACM Symposium on Principles of Programming Languages, in SIGPLAN Notices, 31(1):270–282]