Translation of Turner combinators in O(n log n) space

DOI10.1016/0020-0190(85)90066-3MaRDI QIDQ802308zbMATH OpenOpenAlexFDO

Authors Kohei Noshita

Publication date 1985

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(85)90066-3

zbMATH Keywords

algorithmfunctional programminglambda calculus

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to mathematical logic and foundations (03-04) Combinatory logic and lambda calculus (03B40) General topics in the theory of software (68N01) Analysis of algorithms and problem complexity (68Q25) Abstract data types; algebraic specification (68Q65)

Review text

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.

Recommendations

• Variable abstraction in O(n log n) space
• The BC-chain method for representing combinators in linear space
• scientific article; zbMATH DE number 3909738
• scientific article; zbMATH DE number 3905831
• A fast algorithm for translating combinator expressions with BC-chains

Cites work

• A linear space translation of functional programs to Turner combinators
• A new implementation technique for applicative languages
• An abstraction algorithm for combinatory logic
• Another algorithm for bracket abstraction

Cited in

(7)

• The BC-chain method for representing combinators in linear space
• Variable abstraction in O(n log n) space
• A fast algorithm for translating combinator expressions with BC-chains
• A set of combinators for abstraction in linear space
• Extending SMT solvers to higher-order logic
• scientific article; zbMATH DE number 3905831 (Why is no real title available?)
• scientific article; zbMATH DE number 3909738 (Why is no real title available?)

This page was built for publication: Translation of Turner combinators in O(n log n) space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q802308)