FAQ

Reports on Mathematical Logic

logo of Jagiellonian University in Krakow

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

Publication date: 06.09.2018

Reports on Mathematical Logic, 2018, Number 53, pp. 19 - 42

https://doi.org/10.4467/20842589RM.18.002.8835

Authors

Łukasz Lachowski
Department of Theoretical Computer Science, Faculty of Mathematics and Computer Science, Jagiellonian University
All publications →

Abstract

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.

 

Received 8 June 2017

This work was partially supported by the grant 2013/11/B/ST6/00975 funded by the Polish National Science Center.

AMS subject classification: 03B40, 68Q25, 68N18.

References

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

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

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

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

[5] H.B. Curry, Grundlagen der Kombinatorischen Logik, American Journal of Mathematics 3 (1930), 509–536.

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

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

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

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

[10] M. Sch¨onfinkel, Uber die Bausteine der mathematischen Logik, ¨ Mathematische Annalen 92:3 (1924), 305–316.

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

Information

Information: Reports on Mathematical Logic, 2018, pp. 19 - 42

Article type: Original research article

Titles:

English:

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

Authors

Department of Theoretical Computer Science, Faculty of Mathematics and Computer Science, Jagiellonian University

Published at: 06.09.2018

Article status: Open

Licence: CC BY-NC-ND  licence icon

Percentage share of authors:

Łukasz Lachowski (Author) - 100%

Article corrections:

-

Publication languages:

English

View count: 4740

Number of downloads: 1770