Fixing Letrec: A Faithful Yet Efficient Implementation of Scheme's Recursive Binding Construct

A Scheme letrec expression is easily converted into more primitive constructs via a straightforward transformation given in the Revised⁵ Report. This transformation, unfortunately, introduces assignments that can impede the generation of efficient code. This article presents a more judicious transformation that preserves the semantics of the revised report transformation and also detects invalid references and assignments to left-hand-side variables, yet enables the compiler to generate efficient code. A variant of letrec that enforces left-to-right evaluation of bindings is also presented and shown to add virtually no overhead. A preliminary version of this article was presented at the 2002 Workshop on Scheme and Functional Programming [15].