Variable abstraction in O(n log n) space (Q1090671): Difference between revisions

Turner's translation of lambda calculus into combinators in known to cause in the worst case a quadratic expansion in the size of an expression. This paper defines a more systematic translation into a notation of ''director strings'' closely related to Turner's combinators. The notation admits an obvious compaction by run-length encoding, which reduces the size of the translation of a lambda expression of size n to O(n log n). The time to make the translation is still quadratic in the worst case, but by combining director strings with supercombinators this can also be reduced to O(n log n). There is a simple linear translation of a director string expression into Turner's combinators, and hence into any other set of combinators sufficiently expressive to represent all lambda expressions. Up to a constant factor, evaluation of director string expressions takes the same time as the corresponding Turner combinator expressions. In practical implementations of functional languages, director strings have been found to give a significant, though not dramatic, improvement in execution speed. The work reported in this paper predates, and is independent of, \textit{K. Noshita}'s paper proving some of the same results [ibid. 20, 71-74 (1985; Zbl 0558.68028)].