The BC-chain method for representing combinators in linear space

DOI10.1007/BF03037065zbMath0594.68034OpenAlexW2081318197MaRDI QIDQ1077160

Teruo Hikita, Kohei Noshita

Publication date: 1985

Published in: New Generation Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf03037065

zbMATH Keywords

space complexityfunctional programslambda expressionscombinator graphcombinator implementationnormal order reductionTurner combinators

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)

Related Items (3)

A fast algorithm for translating combinator expressions with BC-chains ⋮ A set of combinators for abstraction in linear space ⋮ Complexity of the combinator reduction machine

Cites Work

• Unnamed Item
• Translation of Turner combinators in O(n log n) space
• A linear space translation of functional programs to Turner combinators
• Director strings as combinators
• An abstraction algorithm for combinatory logic
• A new implementation technique for applicative languages
• Another algorithm for bracket abstraction

This page was built for publication: The BC-chain method for representing combinators in linear space