On the Complexity of the Standard Translation of Lambda Calculus into Combinatory Logic

Łukasz Lachowski

Abstrakt

We investigate the complexity of the standard translation of lambda calculus into combinatory logic. The main result shows that the asymptotic growth rate of the size of a translated term is Ø(n3) in worst-case, where n denotes the size of the lambda term.

Słowa kluczowe: combinatory logic, lambda calculus, complexity analysis, functional programming.
References

H.P. Barendregt, The Lambda Calculus: Its Syntax and Semantics, College Publications, London 2012.

D.A. Turner, Another Algorithm for Bracket Abstraction, The Journal of Symbolic Logic 44:2 (1979), 729-740.

S. Broda and L. Damas, Compact bracket abstraction in combinatory logic, The Journal of Symbolic Logic 62:3 (1997), 729-740.

A. Church, An Unsolvable Problem of Elementary Number Theory, American Journal of Mathematics 58:2 (1936), 345-363.

H.B. Curry, Grundlagen der Kombinatorischen Logik, American Journal of Mathematics 3 (1930), 509-536.

M.S. Joy, On the ecient implementation of combinators as an object code for functional programs, PhD Thesis University of East Anglia (1985).

R. Kennaway and M.R. Sleep, Variable Abstraction in O(n log n) Space, Information Processing Letters 24:5 (1987), 343-349.

L. Lachowski, l2cl, A computer program which searches for worst-case instances of the standard translation. https://bitbucket.org/zbyszko/l2cl, 2017.

K. Noshita, Translation of Turner Combinators in O(n log n) Space, Information Processing Letters 20:2 (1985), 71-74.

M. Schon nkel, Uber die Bausteine der mathematischen Logik, Mathematische Annalen 92:3 (1924), 305-316.

D.A. Turner, Another Algorithm for Bracket Abstraction, The Journal of Symbolic Logic 44:2 (1979), 267-270.

Czasopismo ukazuje się w sposób ciągły on-line.
Pierwotną formą czasopisma jest wersja elektroniczna.