Translation of Turner combinators in O(n log n) space (Q802308)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Translation of Turner combinators in O(n log n) space |
scientific article |
Statements
Translation of Turner combinators in O(n log n) space (English)
0 references
1985
0 references
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.
0 references
lambda calculus
0 references
functional programming
0 references
algorithm
0 references
