Date: May 3, 2002, 11am

Place: Columbia

Purely functional languages are typically compiled by first applying many correctness preserving rewrite rules on an abstract syntax tree, and then giving the simplified final abstract syntax tree a direct operational interpretation. Purely functional languages *can* capture stateful operations using runST and the ST monad, but these stateful operations are compiled to purely functional, linearly threaded code.

In this talk, we turn this traditional compilation model inside out, and embrace runST and the ST monad as our target. Pure functions like map, filter and sort are given an imperative rendering, and we use the worker/wrapper paradigm to perform impedance matching between purely functional interfaces and imperative implementations. To enable the generation of imperative code, we will introduce a number of separate translation systems and fusion laws, including the State Fusion Law, that allows us to tie together independent islands of runST invoked stateful computations into larger islands.

The whole translation provides a road-map from a strict purely functional language (such as used inside TIMBER) to a stateful functional program that uses imperative idioms, like the iterator pattern and call-by-reference. The intent of this work is to complete the translation by rendering the stateful functional program into Java, and we will give evidence that the program can be translated into good imperative code.

I'd appreciate group feedback on the translation, and I am looking for volunteers to help with some of the theory behind the transformations used :-)