Under the exotic syntax, what's really going on with Haskell?



Let's start by taking a short look at how an OO language works.

In an ideal OO language, conceptually every item of data is an object, 
and every operation on that data is a method call. For, conceptually, 
when you say "2 + 3", what happens is that a "2" object is created, a 
"3" object is created, and then the "+" method is invoked.

Now in reality, if you really are created heap-allocated objects and 
doing dynamic method lookup every time you perform even the most trivial 
arithmetic, the system is going to eat RAM like candy and run slower 
than molasses. So every language that does this has something happening 
under the covers to take away the overhead for certain hard-wired kinds 
of objects. But still, *in principle* everything is objects and methods.

So, ignoring the machinery for defining classes for a moment, code 
written in an OO language can create variables, read/write them, take 
conditional branches (if/then/else, for, while, etc.) and invoke 
methods. (Object creation can be regarded as a special case of a method 
call. Indeed, in some languages it *is* a method call.)

Obviously I'm glossing over a whole heap of important details about OOP. 
But then, everybody already knows all about OOP, so I don't think I need 
to repeat that detail.



So, what is Haskell's execution model then?

Haskell as Algebraic Data Types (ADTs - not to be confused with 
_Abstract_ Data Types, which are something completely different). An 
object is something like a C "struct" or a Pascal "record", but an ADT 
is more like what C calls a "union".

An ADT consists of one or more named "constructors", and each such 
constructor has zero or more "fields" of programmer-specified type. The 
fields can optionally be given names.

At one end of the spectrum, you can define "record types". For example, 
you might define a "date" type that has a single constructor, with 
fields named "day", "month" and "year". Nothing especially unusual there.

At the other end of the spectrum, you can define "enumeration types". 
That is, types with multiple nullary constructors. (A nullery 
constructor meaning a constructor with zero fields.) An obvious example 
is "bool", with its "true" and "false" constructors. A less obvious 
example might be "AccessMode", with "ReadMode", "WriteMode" and 
"AppendMode" as constructors.

Other languages have records. A few other languages have true 
enumerations. But Haskell has ADTs, which are a weird hybrid of the two. 
The only other language I can think of that approaches this is C with 
its "union" construct.

Put simply, you can have multiple constructors each with multiple 
fields. What does this actually mean? It means that a data structure of 
a single type can have more than one possible structure. For example, 
you could make a "point" type that can hold both 2D and 3D types. Or a 
"colour" type that can hold both RGB and CYMK colours.

The thing is, usually you would *want* these to be seperate types. So 
this is really a poor example.

For a better example, suppose for argument's sake that we want a binary 
tree that holds data in its leaves only, and no other auxilery 
information. You can do this by defining a "tree" type with two 
constructors: "leaf", which has a single field for the data item, and 
"branch", which has two fields, one for each subtree.

This is the intended use case for ADTs. Every tree node is either a leaf 
or a branch. Every function that processes trees needs to handle both. 
If you replace a simple binary tree with a complex parse tree, with 
different node types for each possible kind of statement or 
subexpression, you start to see the utility and power of ADTs.

Notionally, *everything* is an ADT. The integer type is just an 
enumeration type that has 2^32 constructors, which just happen to be 
named "1", "2", "3"... Similar remarks apply to the character type. 
Obviously these types are "special" to the compiler, but to the casual 
Haskell programmer, there is no *visible* difference. They are just 
normal ADTs with a special syntax.



ADTs dovetail with a Haskell feature called "pattern matching". Haskell 
actually allows sophisticated multi-level patterns, but these can be 
easily translated into nested single-level pattern matches. (And, 
indeed, the compiler performs this translation.)

A single-level pattern match takes a value, inspects it, and does a 
multi-way branch based on which constructor it finds. For example, a 
function working on a tree would execute one code path for a leaf node, 
and another code path for a branch node. The pattern can also can 
variables to the fields of a constructor; this is in fact the only way 
to access those fields.

Pattern matching is in fact the only conditional execution primitive in 
Haskell. (For example, the if/then/else expression is really just syntax 
sugar for pattern matching against "true" and "false".)

In addition, Haskell is a "lazy" language. Data is not computed unless 
or until it is actually "needed". Pattern matching is the thing that 
"needs" results to be computed. You can't decide which execution path to 
take if the data has not been computed yet. So pattern matching is the 
thing that actually makes computations run. (The other thing is I/O 
operations, since you can't output something that hasn't been computed yet.)

A common mistake is to think of data as either "evaluated" or 
"unevaluated". While something like an integer either exists or it 
doesn't, more complex compound data structures can exist partially. For 
example, the list [1,2,3] consists of 7 data objects - three list nodes, 
a list end marker, and three integers. A list node cannot exist before 
the node ahead of it exists, but beyond that, any combination of these 7 
objects may or may not have been computed at any moment in time.

A single-level pattern match only computes the top level of a value. 
Technically, it reduces a value to Weak Head-Normal Form (WHNF). That 
is, it evaluates it just enough to find out which constructor is 
present. Any fields the constructor has remain unevaluated. (Unless 
there are strictness annotations, but forget about that for now.)

For completeness, when something has been *totally* evaluated, this is 
Normal Form (NF).

So, to recap, a single-level pattern match performs the following actions:

1. Evaluate a value to WHNF.

2. Perform a multi-way conditional jump based on the constructor found.

3. Optionally bind variables to the fields of the constructor.

This is the only construct for accessing the fields of a data structure 
(even if there is only a single constructor for that type), and one of 
the only ways to make stuff actually evaluate. (Notionally, you could 
claim that I/O evaluates stuff because it returns data to the Runtime 
System which then pattern matches against it.)

Pattern matching is used for directly manipulating data structures. 
Typically you define a data type, use pattern matching to define the 
functions that operate on it in the most primitive way, and then define 
complex functions in terms of the simpler ones. Indeed, it is common to 
define a type, and export its name but *not* its internal structure. 
This allows encapsulation in a mannar similar to OOP. (Not inheritance 
or dynamic binding, just encapsulation.)



Now we're starting to get a feel for how Haskell works. Every value 
notionally consists of a "tag" (the constructor) which indicates what 
fields will follow (if any). Pattern matching forces expressions to 
execute, and does a multi-way conditional jump based on the tag found in 
the result, binding local variables to the fields so they can be accessed.

In fact, the entire Haskell language gets compiled down to just 6 
primitive operations:

1. Create a data literal.

2. Create an anonymous function.

3. Call a function with some arguments.

4. Create a variable and bind it to an unevaluated expression.

5. Read a value from a variable.

6. Pattern match.

That's the entire Haskell language, right there. Everything that Haskell 
can do is represented here. This is the actual internal representation 
that GHC uses when compiling Haskell code. In particular:

- Primitive #4 is the *only* place where memory is allocated.

- Primitive #6 is the *only* place where unevaluated expressions get 
evaluated. It is also the only place where conditional branching happens.

Bear in mind that GHC's internal code representation has different 
properties to the original Haskell source code. (For example, creating a 
variable in Haskell doesn't _necessarily_ mean that any memory will be 
allocated. The compiler might optimise the variable away.)

Post a reply to this message