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.

• evaluation.pdf 
• functions.pdf

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. 

• lambda.pdf

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 (it's not following the slides exactly so don't be confused).

• operational.pdf 

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.

• Elixir: Basic types - arithmetic
• Elixir: Basic types - atoms
• Elixir: Basic types - tuples
• Elixir: Pattern matching

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: 

How did we cheat?

We have done some hand waving in our description. It's not a complete operational semantics since we are a bit informal when we say things like "this rule is applied if...". In a proper description we would have to describe exactly how we find out if a rule is to be applied. We would for sure have to introduce a computational stack in order to evaluate sub-expressions etc.  If we would define a complete operational semantic we would not leave this undefined.If we do not have a precise operational semantics then how can we say anything about the run-time complexity of programs.

Nor have we described how functions should be represented or how higher order functions should work but this will actually be only smaller extensions to the given description.