Lambda calculus

This is a formal description of a small functional language (that looks a bit like Elixir). We will build it from the ground up, starting with the basic data structures and then define how expressions are evaluated. Even if the language is very small we will have some points in the design were we need to do a choice; depending on our choices our language will have different properties.

• lambda.pdf
• evaluation.pdf

Lambda calculus

All functional programming languages have their roots in lambda calculus. You should have a basic understanding of this calculus since many of the properties of our language example is described in terms of lambda expressions and how they are evaluated. Read the following tutorial and do the programming exercises in order to better understand what we are talking about. 

• Lambda Calculus

The operational semantics

We use a simplified functional programming language to describe properties of different alternatives. I've summarized the lectures that presents the operational semantics.

• Operational Semantics

Going further

In this very limited description we have omitted a few things. If you want to know more how functional programming languages are defined you can look at the following two references:

• The Implementation of Functional Programming Languages by Simon L. Peyton Jones. This is the classical book in the area. You don't have to read the whole book but do take a look at the first set of chapters. You will see how the approach is very close to how we have worked. In the book a functional programming language, Miranda, is defined in terms of lambda calculus. Lambda expressions are then given an operational semantics by being expressed as abstract machine instructions.
• Teaching Creative Computer Science , Simon Peyton Jones at TEDx: