Programming in the λ-Calculus: From Church to Scott and Back
2013
Although the λ-calculus is well known as a universal programming language, it is seldom used for actual programming or expressing algorithms. Here we demonstrate that it is possible to use the λ-calculus as a comprehensive formalism for programming by showing how to convert programs written in functional programming languages like Clean and Haskell to closed λ-expressions. The transformation is based on using the Scott-encoding for Algebraic Data Types instead of the more common Church encoding. In this way we not only obtain an encoding that is better comprehensible but that is also more efficient. As a proof of the pudding we provide an implementation of Eratosthenes' prime sieve algorithm as a self-contained, 143 character length, λ-expression.
Keywords:
- First-generation programming language
- Programming domain
- Protocol (object-oriented programming)
- Functional logic programming
- Higher-order programming
- Fifth-generation programming language
- Algorithm
- Programming language theory
- Third-generation programming language
- Computer science
- Reactive programming
- Declarative programming
- Inductive programming
- Programming language
- Artificial intelligence
- Programming paradigm
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
12
References
8
Citations
NaN
KQI