A Tutorial Introduction to the Lambda Calculus

a tutorial introduction to the lambda calculus. Raul Rojas . FU Berlin, WAS 97/98. Abstract. This document is a brief and painless introduction to the tutorial λ ….

More PDF Content

A Tutorial Introduction to the Lambda Calculus, Contents:

  1. Definition
    1.1 Free and bound variables
  2. Arithmetic
    2.1 Addition
    2.2 Multiplication
  3. Conditionals
    3.1 Logical operations
    3.2 A conditional test
    3.3 The predecessor function
    3.4 Equality and inequalities
  4. Recursion
  5. Projects for the reader

Projects for the reader

  1. Define the functions “less than” and “greater than” of two numerical arguments.
  2. Define the positive and negative integers using pairs of natural numbers.
  3. Define addition and subtraction of integers.
  4. Define the division of positive integers recursively.
  5. Define the function n! = n · (n − 1) ··· 1 recursively.
  6. Define the rational numbers as pairs of integers.
  7. Define functions for the addition, subtraction, multiplication and division of rationals.
  8. Define a data structure to represent a list of numbers.
  9. Define a function which extracts the first element from a list.
  10. Define a recursive function which counts the number of elements in a list.
  11. Can you simulate a Turing machine using λ calculus?

 

Download A Tutorial Introduction to the Lambda Calculus pdf from www.soe.ucsc.edu, 9 pages, 141.15KB.