Abdulaziz Ghuloum and R. Kent Dybvig. Fixing letrec (reloaded). Proceedings of the 2009 Workshop on Scheme and Functional Programming, 57-65, August 2009. (bibtex).

The Revised^6 Report on Scheme introduces three fundamental changes involving Scheme's recursive variable binding constructs. First, it standardizes the sequential recursive binding construct, letrec*, which evaluates its initialization expressions in a strict left-to-right order. Second, it specifies that internal and library definitions have letrec* semantics. Third, it prohibits programs from invoking the continuation of a letrec or letrec* init expression more than once. The first two changes increase the incentive for handling letrec* efficiently, while the third change gives the compiler more options for transforming letrec and letrec* expressions.

This paper extends an earlier effort of Waddell, Sarkar, and Dybvig to handle the Revised^5 Report letrec and (the then nonstandard) letrec* efficiently. It presents more aggressive transformations for letrec and letrec* that take advantage of the new prohibition on invoking the continuations of initialization expressions multiple times. The implementation employs Tarjan's algorithm for finding strongly connected components in a graph that encodes the dependencies among the bindings.