Translation of Turner combinators in O(n log n) space. (English) Zbl 0558.68028
A practical method for representing Turner Combinators is presented, which needs only O(n log n) space in the worst case for translating lambda expressions of length n. No precomputation is necessary in our translation, which should be contrasted with Burton’s proposal. The runtime system can be implemented with virtually no essential change to Turner’s reduction machine.
MSC:
| 68Q65 | Abstract data types; algebraic specification |
| 03B40 | Combinatory logic and lambda calculus |
| 68N01 | General topics in the theory of software |
| 68Q25 | Analysis of algorithms and problem complexity |
| 03-04 | Software, source code, etc. for problems pertaining to mathematical logic and foundations |
References:
| [1] | Abdali, S. K., An abstraction algorithm for combinatory logic, J. Symbolic Logic, 41, 1, 222-224 (1976) · Zbl 0331.02012 |
| [2] | Burton, F. W., A linear space translation of functional programs to Turner combinators, Inform. Process. Lett., 14, 5, 201-204 (1982) · Zbl 0507.03004 |
| [3] | Hughes, R. J.M., Super-combinators, (Conf. Rec. 1982 ACM Symp. on LISP and Functional Programming (1982)), 1-10 |
| [4] | Kennaway, J. R., The complexity of a translation of λ-calculus to combinators, (Rept., School of Computing Studies and Accountancy (1982), University of East Anglia: University of East Anglia Norwich) |
| [5] | Turner, D. A., A new implementation technique for applicative languages, Software-Practice and Experience, 9, 31-49 (1979) · Zbl 0386.68009 |
| [6] | Turner, D. A., Another algorithm for bracket abstraction, J. Symbolic Logic, 44, 2, 267-270 (1978) · Zbl 0408.03013 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
