On the Complexity of the Standard Translation of Lambda Calculus into Combinatory Logic
On the Complexity of the Standard Translation of Lambda Calculus into Combinatory Logic
Author(s): Łukasz LachowskiSubject(s): Economy
Published by: Wydawnictwo Uniwersytetu Jagiellońskiego
Keywords: combinatory logic; lambda calculus; complexity analysis; functional programming
Summary/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.
Journal: Reports on Mathematical Logic
- Issue Year: 2018
- Issue No: 53
- Page Range: 19-42
- Page Count: 24
- Language: English