Lambda Calculus Tutorial

Programming Languages Group 16

Cody Robbins [robbic3@rpi.edu]
Jonathan Dance [dancej@rpi.edu]
Jeffrey Lynch [lynchj2@rpi.edu]
Matthew Cherian [cherim@rpi.edu]

Abstract

The lambda calculus was developed in 1936 by Lorenzo Church, and is a mathematical system for defining computable functions (i.e., a model of computation). Church’s lambda calculus is equivalent in power to the Turing machine, although Church and Turing both developed their respective models of computation independently. We attempt to explain to the fundamental principles of the lambda calculus in a clear, concise, and easy to understand fashion. We provide examples and self-tests to facilitate in the conceptualization of the material.

Table of Contents

  1. Introduction
  2. Syntax of the Lambda Calculus
  3. Evaluation Strategies
  4. Reductions
  5. Church Numerals

Download the entire tutorial as a gzipped tar


Created April 15, 2002