Evaluating expressions

This is a formal description of a small functional language (that looks a bit like Erlang). 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 Erlang to the level that you can run small tests in the Erlang 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 Erlang and the programming environment, this is something that you should learn by reading the course book and following the online material.

Before the lecture

You should have an Erlang system up and running and should have started to write smaller functions. You should have seen the Erlang Express lectures on:

• Erlang Data Types
• Variables and Pattern Matching

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.

Go through the next lecture in Erlang Express.

• Functions and Modules

•  The Erlang Shell

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.