Perl Contains the Lambda Calculus

(How to write a 163 line program to compute 1+1)

Length: 90 minutes

Prerequisites: None.


Lambda-Calculus (pronounced `lambda calculus') is a model of computation invented by Alonzo Church in 1934. It's analogous to Turing machines, but it's both simpler and more practical. Where the Turing machine is something like a model of assembly language, the lambda-calculus is a model of function application. Like Turing machines, it defines a simplified programming language that you can write real programs in. Writing Turing machine programs is like writing in assembly language, but writing lambda-calculus programs is more like writing in a higher-level language, because it has functions.

The two legal operations in the lambda-calculus are to construct a function of one argument with a specified body, and to invoke one of these functions on an argument. What can be in the body of the function? Any legal expression, but expressions are limited to variables, function constructions, and function invocations. What can the argument be? It has to be another function; functions are all you have. With this tiny amount of machinery, we can construct a programming language that can express any computation that any other language can express.

Unlike most popular programming languages, Perl is powerful enough to express the lambda-calculus directly, without the need to write a simulator. This means that if you want to try programming in the lambda-calculus, you can do it directly in Perl, without having to implement a program to parse and evaluate lambda-calculus expressions first. Perl's parser will parse lambda-expressions, if you write them properly, and its evaluator will evaluate them.

In the lambda-calculus, a function with formal parameter x and body B is denoted lambdax.B. In Perl, we write sub { my $x = shift; B }.

To apply the function P to an argument Q, the usual lambda-calculus notation is just (P Q). In Perl, we write $P->($Q).

The only expressions not of either of these two forms are simple variables. To apply the function lambdav.B to some argument A is simple. The result is just B, but with any occurrences of v replaced with A instead. For example (lambdax.(x (x y))(P Q)) reduces to ((P Q) ((P Q) y))---we replaced all the x's with (P Q)s.

By convention, function application is taken to be left-associative, so that (P Q R) is short for ((P Q) R).

From these few materials we can construct a programming system capable of performing arithmetic, constructing lists and trees, and expressing arbitrary recursive functions on these objects.

Complete Slides

  1. Perl and the Lambda Calculus
  2. What is the Lambda Calculus?
  3. Turing Machine
  4. Turing Machines
  5. Lambda-Calculus
  6. Lambda-Calculus
  7. Abstraction
  8. Application
  9. Application Example
  10. Application
  11. Abstraction Again
  12. Goal
  13. Values
  14. Church-Rosser theorem
  15. Undefined Values
  16. Currying
  17. Currying
  18. Boolean Values
  19. Boolean Value Example
  20. Boolean Value Example
  21. Data Structures
  22. Ordered Pairs
  23. Ordered Pair Example
  24. Ordered Pair Example
  25. Numbers
  26. Number Example
  27. Arithmetic
  28. Recursion
  29. Fixed Points
  30. ``I think you should be more explicit here in step two...''
  31. Return from Digression
  32. OK, We're Done
  33. Building an Interpreter
  34. There's a Catch
  35. Applicative Order Solution
  36. Applicative Order Solution
  37. Lambda-Calculus in Perl
  38. Thank You!

Additional Materials

Return to: Universe of Discourse main page | Perl Paraphernalia | Other Classes and Talks