 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> 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.)
And in Smalltalk, conditional branches are also method calls. You send two
"blocks" to a boolean, and it executes the appropriate one. E.g., you call
(x == 5) ifTrue: [y print] ifFalse: [z print]
So (x == 5) sends the == message to x with the argument 5, and that returns
either true or false. The methos "ifTrue:ifFalse:" in "true" evaluates and
returns the first argument. The method of the name in "false" evaluates and
returns the second argument. So, technically, you don't need conditionals
either, just deferred evaluation (aka lambda expressions).
> 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 langruage I can think of that approaches this is C with
> its "union" construct.
Ada and Hermes and heh. Heck even Visual Basic has such as "variant" type. I
think Pascal has the same thing too.
That's pretty cool, tho. I love languages where a very simple idea is taken
to extremes.
--
Darren New, San Diego CA, USA (PST)
The question in today's corporate environment is not
so much "what color is your parachute?" as it is
"what color is your nose?"
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> 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.)
>
> And in Smalltalk, conditional branches are also method calls.
Oh yeah - I'd forgotten about that...
Looping too. ;-)
>> 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 langruage I can think of that approaches this is C
>> with its "union" construct.
>
> Ada and Hermes and heh.
Not things I'm familiar with.
It did seem for a while that every single language I leaned was just new
syntax for basically the same stuff. Every language has named functions
or procedures or subroutines or whatever you want to call them. Every
language has if/then/else, while, for, etc. Every language has local and
global variables. So it's just a question of what the syntax looks like,
and what "features" the language has. (E.g., in Pascal, you can only
loop over numbers, while C lets you write for-loops which don't even
*have* an index variable.)
And then I learned Haskel, which is *completely different*. ;-)
> Heck even Visual Basic has such as "variant" type.
Is VB statically-typed yet?
> I think Pascal has the same thing too.
Not any dialect I've seen.
> That's pretty cool, tho. I love languages where a very simple idea is
> taken to extremes.
Yeah, it's nice. Haskell is a graph-rewrite system. I mean, if you want
any kind of performance, you'll want to hack the basic model a little to
take advantage of the native machine capabilities. But basically, it's a
G-maching. (In the case of GHC, a spineless, tagless G-machine...)
Smalltalk has a nice idea: Absolutely everything is an object. Including
the entire fricking IDE. Shame about the performance though, eh?
(Actually, the most annoying thing is the lack of static typing.)
Lisp has a nice idea: Everything is a tree. Shame the underlying simple
idea had to be implemented in such an over-complicated and arbitrary way.
Although, arguably Haskell has just *so much* syntax sugar it's hard to
see the simple structure underneith. Hence this post. ;-)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New <dne### [at] san rrcom> wrote:
> And in Smalltalk, conditional branches are also method calls. You send two
> "blocks" to a boolean, and it executes the appropriate one. E.g., you call
> (x == 5) ifTrue: [y print] ifFalse: [z print]
> So (x == 5) sends the == message to x with the argument 5, and that returns
> either true or false. The methos "ifTrue:ifFalse:" in "true" evaluates and
> returns the first argument. The method of the name in "false" evaluates and
> returns the second argument. So, technically, you don't need conditionals
> either, just deferred evaluation (aka lambda expressions).
Could a simple conditional be more awkward than that?
(I can only imagine how hard it is for compilers to optimize that into a
regular machine code conditional construct.)
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Yet another chapter in your ongoing series of tutorials "Haskell for povray
dummies"? Fascinating effort to try to sell an obscure, niche language to an
obscure, niche audience. :)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> Could a simple conditional be more awkward than that?
Sure! I can think of ways to make it much more complicated. ;-)
> (I can only imagine how hard it is for compilers to optimize that into a
> regular machine code conditional construct.)
At a simple level, you could just scan the source when you compile it,
and replace any calls to the #ifTrue:ifFlase: method (and friends) with
the appropriate machine instructions.
Then again, Smalltalk is an interpretted language. Speed is quite
clearly *not* its main objective.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
nemesis wrote:
> Yet another chapter in your ongoing series of tutorials "Haskell for povray
> dummies"?
I don't believe you need to use POV-Ray or be dumb in order to
understand Haskell. ;-)
> Fascinating effort to try to sell an obscure, niche language to an
> obscure, niche audience. :)
I'd argue that POV-Ray isn't exactly "niche", by any reasonable standard.
Also, note that I didn't once say "you should use Haskell because..." or
"Haskell is better because...". All I said was "this is how it works".
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> And then I learned Haskel, which is *completely different*. ;-)
Try then APL, or LISP, or FORTH.
>> Heck even Visual Basic has such as "variant" type.
> Is VB statically-typed yet?
AFAIK, it has always been statically typed since before they put the word
"visual" on front.
>> I think Pascal has the same thing too.
> Not any dialect I've seen.
Yeah. Google for "pascal variant record". It's a case statement inside the
record declaration.
> Smalltalk has a nice idea: Absolutely everything is an object. Including
> the entire fricking IDE. Shame about the performance though, eh?
The performance was actually pretty good when you put it on a CPU built for
it. Of course it's going to run like crap on a CPU designed for a
statically typed stack-oriented language like C or Pascal.
--
Darren New, San Diego CA, USA (PST)
Yes, we're traveling togeher,
but to different destinations.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> At a simple level, you could just scan the source when you compile it,
> and replace any calls to the #ifTrue:ifFlase: method (and friends) with
> the appropriate machine instructions.
Internally, that's what it does. Of course, if you send that to something
that isn't a boolean, *then* you get an even bigger overhead.
> Then again, Smalltalk is an interpretted language. Speed is quite
> clearly *not* its main objective.
This is not something that noticably slows things down, tho. When
*everything* is a message dispatch, you can design your microcode to do that
efficiently.
--
Darren New, San Diego CA, USA (PST)
Yes, we're traveling togeher,
but to different destinations.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> And then I learned Haskel, which is *completely different*. ;-)
>
> Try then APL, or LISP, or FORTH.
Tried Lisp, didn't like it. Too much backwards compatibility making it
way, way more complicated than it should be.
I guess that's one nice thing about Haskell's avoidance of success...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|
