Evaluation

We've now come to a point where we can get to the core of the interpreter - the code that evaluates Lisp expressions. This bit demonstrates a number of Haskell features: type inference (along with optional type declarations), pattern matching, additional power of algebraic data types, functions as first class objects, and power of higher order functions. Let's view the code snippet and discuss these features one by one.

eval :: Expr -> Expr
eval (BlaiseInt n) = BlaiseInt n
eval (BlaiseSymbol s) = ctx Map.! s
eval (BlaiseFn f) = BlaiseFn f
eval (BlaiseList (x:xs)) = apply (eval x) (map eval xs)
        where apply :: Expr -> [Expr] -> Expr
              apply (BlaiseFn f) args = f args

This code defines a single function, eval, that evaluates our Lisp expression. The code looks strange if you're unfamiliar with Haskell but it's just a matter of learning a few powerful features before you can warm up to it. Let's start with type inference.

The first line is a type declaration - we tell the compiler that eval is a function that takes a single argument of type Expr and returns a value of the same type. Notice that the declaration is separate from the rest of the code - it almost gives you a hint that it isn't always necessary. If you open the interpreter's source code you'll notice that functions very rarely have type declarations. To the uninitiated it may seem that Haskell is a dynamically typed language but it isn't - everything is resolved at compile time. Haskell does this with type inference and it works surprisingly well. Most of the time you don't have to specify types - Haskell will figure them out for you. Sometimes it will get confused and you'll have to add a type declaration but that's an exception rather than the rule. If you're confused about what the type of something is, you can always start an interpreter and ask (:t something). Most of the type declarations in Blaise aren't necessary - I only put them there for clarity (I wonder how many lines of code I'd save if I removed them). After you get used to type inference it's really hard to come back to work and write my share of Java code:

ReallyLongClassName i = (ReallyLongClassName)foo.getBar();

The next line is first in a series of pattern matches. This feature is a mix of virtual functions, regular expressions performed on live data structures, and an abstraction over large switch statements. The four lines after the type declaration specify four cases of pattern matching and what the value of the eval function should be in those cases. For example, the second line states: "if the first (and only) argument is a blaise integer, just let it return itself" (because a value of 5 is 5).

In the example above pattern matching does something similar to what virtual functions do in Java - it executes different code depending on the type of the argument (in Haskell's case we can look at the type as well as the constructor of the algebraic data type, among other things). However, the abstraction is much more powerful. In principle, virtual functions are just a large switch statement like the one in the pseudo-code below:

if(typeof(something) == someType) {
    doSomething();
} else if(typeof(something) == someOtherType) {
    doSomethingElse();
}

Traditional object oriented languages let us abstract ourselves from writing such switches and take the task upon themselves freeing us up to do more important work. Haskell does the same thing, however, it doesn't limit the abstraction to types - we can get the compiler to write such switches based on any component we're interested in abstracting! We can, for example, get the compiler to write code for us that will cause the runtime to only execute a particular function if the first argument is equal to five, or if the second element in a list is equal to three. We could do that in traditional languages with if statements and switches but Haskell does this for us in a much more elegant and expressive way. After all, why are we only allowed to create virtual functions based on the type of the object they belong to? Why can't we define "virtuality" based on the type (or value) of the function's third argument, for example? Interestingly, this is one of the reasons why Haskell isn't object oriented - it's functions don't need to belong to objects because the compiler and the runtime system allow us to abstract over any argument's type and structure (contrast that to being able to abstract only over an implicit this)!

In our case eval also takes advantage of functions being first class objects. Take a look at how we evaluate a symbol - we simply grab its value from the map. At this point the symbols are predefined and added to the map on startup like so:

ctx = Map.fromList [("*", BlaiseFn blaiseMul)]

In this case we added a multiplication operator. Now if we try to evaluate "*", we're going to get a function from the map that we can call! This is similar to getting an instance of a class that implements multiplication, except we don't have to deal with the boilerplate - Haskell will do the work behind the scenes.

We also use higher order functions (functions that take other functions in arguments) in order to evaluate the function's arguments. Take a look at how we use map - Haskell's function to iterate over a list. We pass it a function and a list, and map iterates the list and calls our function on each member. We could do this with a for statement (or if we're lucky with a foreach), but we don't have to - Haskell lets us build abstractions over boilerplate code we write over and over again without waiting for the compiler developers to write them for us (of course map is a standard part of Haskell but if it weren't we could easily implement it ourselves).