17.10.1 Introduction to the algorithms

The compiler implements three algorithms: basic, waddell, scc. The default and more advanced is scc; there is little reason to use the other algorithms when processing real code.

The basic transformation is the one that defines the letrec syntax from the R5RS standard document.

The waddell transformation focuses on generating fix structures representing recursive binding forms for unassigned lambda expressions. To understand this algorithm, and the code, we must read the following paper:

[WSD] Oscar Waddell, Dipanwita Sarkar, R. Kent Dybvig. “Fixing Letrec: A Faithful Yet Efficient Implementation of Scheme’s Recursive Binding Construct”.

The scc algorithm is an evolution of the waddell transformation that better processes bindings, taking into account their actual dependency graph. To understand this algorithm, and the code, we must read the following paper:

[SCC] Abdulaziz Ghuloum, R. Kent Dybvig. “Fixing Letrec (reloaded)”. Workshop on Scheme and Functional Programming ’09.

the described algorithm makes use of Tarjan’s algorithms to partition the nodes of a graph into Strongly Connected Components (SCC):

Tarjan, Robert Endre. “Depth–first search and linear graph algorithms”. SIAM Journal on Computing 1 (2): 146-160, 1972.

for details on the SCC algorithm, we can also refer to the Wikipedia article “Tarjan’s strongly connected components algorithm”⁵.