Programming in the λ-Calculus: From Church to Scott and back

The work

AuthorsJan Martin Jansen
Typeincollection
Year2013
Citekeyjansen2013programming

Where it appeared

Published inThe Beauty of Functional Code
PublisherSpringer
Pages168--180

Identifiers

DOI10.1007/978-3-642-40355-2_12

Abstract

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.

A copy is held

pdf, 286.3 kB. Not published — it may be under copyright. The facts and links here are.

How it got here

How it got hereimport via bibtex
Added2026-08-11 00:00 UTC
Approved bya person 2026-08-16 15:34 UTC

Filed under

the-copy-is-not-the-work what-a-program-means

Cite it as

@incollection{jansen2013programming,
  title        = {Programming in the λ-Calculus: From Church to Scott and back},
  author       = {Jan Martin Jansen},
  year         = {2013},
  booktitle    = {The Beauty of Functional Code},
  pages        = {168--180},
  publisher    = {Springer},
  doi          = {10.1007/978-3-642-40355-2_12},
}

This record lives at https://refs.drheap.org/jansen2013programming/ and will keep doing so.