Models of the Lambda Calculus: An Introduction

Abstract

The -calculus is a symbolic formalism for describing and calculating with functions. To give meaning to expressions in the -calculus they must be interpreted in terms of standard mathematical objects such as sets and functions. Each such interpretation is called a model of the -calculus. Because the concept of function embodied in the -calculus is very general—for example, a -calculus function can be applied to itself—we cannot model -calculus functions as ordinary mathematical functions. Consequently such models require some new ideas that turn out to have applications in other areas of mathematics, and in computer science as well. This paper presents an introduction to models of the -calculus that is largely self-contained, although most technical details are omitted. It starts with a brief exposition of the -calculus itself, followed by some basic theory of -models in general and then descriptions of two specific models, including Dana Scott’s , the first non-trivial model discovered. It concludes with suggestions for further reading.