Comparison of Closure Reduction and Combinatory Reduction Schemes.
Tetsuo Ida, Akihiko Konagaya · 1984
We analyze the efficiencies of closure reduction and combinatory reduction schemes by introducing a labelled tree representing a λ-term. Translation of a λ-term into combinatory terms, i.e. bracket abstraction, can be viewed as attaching labels S, B, C, K, I to each node. Similarly, a node of a tree representing a λ-term can be labelled depending upon the presence of free variables in the subtrees. Resulting labelled trees which represent a λ-term and the translated combinatory term are made similar, i.e. whose underlying trees are the same. We can then make performance comparisons in terms of the cost involved in traversing the labelled trees by machine models reflecting the essential behaviors of Turner's combinatory reducer and a closure reducer. Our work is an elaboration of Turner's and Peyton Jones's experiments of combinatory reductions. However, our approach is not to resort to actual runs of programs, but is more theoretical, based on abstract machine models working on labelled trees.