|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |