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

DOI10.1016/0020-0190(85)90066-3zbMath0558.68028OpenAlexW1974989319MaRDI QIDQ802308

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

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

Related Items

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, Extending SMT solvers to higher-order logic, A set of combinators for abstraction in linear space

Cites Work

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