Tuesday, February 19, 2013

Evaluating, compiling and running arithmetical expressions.

Partly reminded to do this by recent FB posts by Graham Hutton and Andy Gill, I used foils and OHP pens to deliver my last lecture in the functional programming course "live". I like the sense of tension you get from writing stuff "out there" and interacting with the class in a more thoroughgoing way than seems to happen with pre-prepared slides.

What did I cover? The aim was to hammer home the message about the data driving the programming, and I took the example of processing arithmetical expressions, writing an evaluator, a virtual machine and a compiler … I didn't cover parsing, but that can come in the second half of the course: Stefan?

So, we started with a data type for expressions, with literals, +, - and *.

data Exp = Lit Int 
         | Add Exp Exp
         | Sub Exp Exp
         | Mul Exp Exp
          deriving (Show)

with the expression 2+((3-(-3))*3) represented by

(Lit 2) `Add` (((Lit 3) `Sub` (Lit (-3))) `Mul` (Lit 3))

The first thing to define is the evaluator, which has a straightforward data-directed definition:

eval :: Exp -> Int

eval (Lit n)       = n
eval (Add ex1 ex2) = eval ex1 + eval ex2
eval (Sub ex1 ex2) = eval ex1 - eval ex2
eval (Mul ex1 ex2) = eval ex1 * eval ex2

What sort of machine should we use to evaluate the expressions? The simplest approach is to build a stack machine, which can either push literals, or apply an operation to the top elements on the stack (from my slides):

Here's the type of code.

data Code = PushLit Int
          | DoAdd
          | DoSub
          | DoMul
            deriving (Show)

We can describe this machine by giving the function that runs a program, when we represent the stack by a list of integers, and the program by a list of code.

type Program = [Code]
type Stack = [Int]

run :: Program -> Stack -> Stack

run [] stack 
        = stack
run (PushLit int : program) stack 
        = run program (int : stack)
run (DoAdd : program) (v1:v2:stack)
        = run program (v1 + v2 : stack)
run (DoSub : program) (v1:v2:stack)
        = run program (v1 - v2 : stack)
run (DoMul : program) (v1:v2:stack)
        = run program (v1 * v2 : stack)
run _ _ = []

An alternative here would be to give the oneStep function, and then to define run in terms of that: that's an exercise for the reader.

The final piece of the puzzle is to define the compiler:

compile :: Exp -> Program

compile (Lit n) 
        = [PushLit n]
compile (Add ex1 ex2)
        = compile ex2 ++ compile ex1 ++ [DoAdd]
compile (Sub ex1 ex2)
        = compile ex2 ++ compile ex1 ++ [DoSub]
compile (Mul ex1 ex2)
        = compile ex2 ++ compile ex1 ++ [DoMul]

VoilĂ !

Why do I like this example so much?

  • It shows Haskell's strengths: I think my students get fed up of me comparing Haskell with Java, but this is a case where it really shines. The types make it very clear what's going on; the algebraic types guide the definitions, and we can even prove it correct …
  • What is the statement of correctness? That evaluation is the same as compiling and running:
    run (compile exp) [] = [eval exp]
    but there's a bit of work to do to get the right induction hypothesis (exercise).
  • There are lots of nice generalisations: we can introduce local definitions with a let construct, or indeed allow (updatable) variables within expressions. All these can be added in a nice type-directed way.
  • There are lots of related exercises too: e.g. generate truth tables for Boolean expressions, and using these write tautology checkers.

So, a very enjoyable last lecture on Haskell.

Tuesday, February 12, 2013

Teaching Haskell … but for the last time for a while.

For one reason or another, I haven't been teaching functional programming at Kent for a few years, so it's interesting to be back doing it, and to reflect on that.

The last time I was involved was when we were teaching Haskell in the first year, starting in the second term, and following up on Java which had been taught from the start. We came to the conclusion that this wasn't ideal: instead of reinforcing each other, it seemed perverse to start with a second paradigm before the first one was properly internalised. This time I'm teaching in the second term of the second year … just like we did twenty years ago, in fact … and it seems to be going much better.

One thing that's really helpful is to be able to discuss features of Haskell using Java as a reference point.   For example, what does it mean to belong to a class? Well, you have to implement the interface that's given by the class declaration. Seems to demystify the idea.

Sometimes Haskell is so much better: data types with multiple constructors (e.g simple geometric shapes such as circles and rectangles) just work in Haskell. No ugly abstract base classes and subtyping, no problem with binary methods, the joys of pattern matching … great stuff.

Types play an important role: the first and most important piece of documentation for any function, but also a way of discovering things in the library thanks to hoogle. If you've not tried this out, give it a go: it works for monotypes, such as Char -> Bool, just as much as for complicated polymorphic examples. Really useful, and appreciated by the students.

On the other hand, some things are difficult for the beginner. It's too easy to overlook concrete syntax when you understand it well - indeed the whole point is that the syntax almost disappears, and you perceive the intention, or the semantics immediately - but that's just not the case for beginners, and the novelty of the Haskell syntax can be a problem. Just function application looks unfamiliar, and the layout sensitivity can trip people up too. Other little irritations: length (of a list) returns a fixed size Int, as does replicate: we should probably use the generic versions from scratch and ignore Int altogether?

Funny things you wouldn't think of. A colleague sitting in on the lectures noted that the (x:xs) notation could be a problem: sometimes it wasn't clear when I was saying "x is" and when I was saying "exes". Perhaps I need to say "excess" instead, or maybe ditch that notation altogether?

I've been lucky enough to have inherited Olaf Chitil's slides (though I think some of my DNA is in there from a number of generations back) which are great. The problem is I'm never happy with using someone else's slides - or indeed my own from a previous year - so start rewriting them. Even when this is the last time they will be used, because next year we're trying something different …

As a root and branch curriculum review we looked at what we taught in the second year of our programmes as core material, and found that we wanted to include about 180 credits worth of material in a 120 credit year. Together with all the other material we saw as core, we wanted to carry on teaching functional programming, and also to teach concurrency (which we currently do in occam-pi, optionally to second and final years), but we didn't have enough time to teach two separate languages. So, we decided to use a language with both: that could be Clojure, we could look at Haskell's various concurrency extensions, but we'll be working with Erlang next year.

Not everyone was happy with this … indeed I'm not 100% sure … but it will be really interesting to look at Erlang as a practical functional/concurrent language, and use it as a base for exercises and projects, as well as a comparison point for other approaches like Haskell, occam-pi. I'll report back in a year's time …

Back on track in the blogosphere

Back again to my blog after about 6 weeks off. What was the problem? It wasn't that I didn't have anything to say, because lots of things were going on: teaching a functional programming (Haskell) undergrad course for the first time in ages, convening a module for new lecturers at Kent on developing as a researcher, doing project work on both Release and PROWESS, as well as getting to some films, concerts and so on. I'll be blogging about some of these in the next few days, I hope.

No, I think the problem was that I didn't have enough train journeys to go on. Somehow the ambiance and length of a train journey is just right for getting thoughts marshalled and into blogger. As you might guess, I'm writing this on the train: en route to Swindon for a two day grant review panel at EPSRC. There certainly should be another post in a couple of day's time, on my way home, if not before …