Show version

Version created by Johan Montelius 2018-01-12 11:03

Show < previous | next >
Compare < previous | next >

Evaluating expressions

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. 

Before this lecture you should be up and running in Elixir to the level that you can run small tests in the Elixir shell. You should also have read chapter 1 and 2 in the course book.

Note - again, the lectures will not describe how to work with Elixir and the programming environment, this is something that you should learn by reading the online material.

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. 

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.

Before the lecture

You should have an Elixir system up and running and should have started to write smaller functions.

After the lecture

Start with the first assignment. Make sure that you start early so that you can make best use of the scheduled hours where teaching assistants will help you.

Elixir concepts

The only concepts that we will use so far are simple data structures: atoms, integers and tuples, and how to do pattern matching over these.

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: 

Feedback News