O'Reilly logo

Practical Foundations for Programming Languages by Robert Harper

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

17 The Untyped λ-Calculus

Types are the central organizing principle in the study of programming languages. Yet many languages of practical interest are said to be untyped. Have we missed something important? The answer is no: the supposed opposition between typed and untyped languages is illusory. In fact, untyped languages are special cases of typed languages with a single recursive type. Far from being untyped, such languages are unityped.

In this chapter we study the premier example of a unityped programming language, the (untyped) λ-calculus. This formalism was introduced by Church in the 1930s as a universal language of computable functions. It is distinctive for its austere elegance. The λ-calculus has but one “feature,” the higher-order ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required