|
![](/i/fill.gif) |
> My comment might not have been 100% in line with what you were asking
> about. I just thought it was an interesting point. In a language where
> you can't modify memory once you've allocated it, is there any semantic
> difference between allocating it on the heap or allocating it inline
> somewhere? I don't think so.
The Haskell language specification describes the syntax of the language
and approximately how to execute it. However, it is silent on
implementation details such as calling conventions. (This is not an
oversight.)
The language spec says nothing about what goes on the heap, what goes on
the stack, what goes in registers, etc. In Haskell, I can say "print (x
+ 1)". Now, whether the value of "x" is in a register, on the stack, on
the heap somewhere, and so on makes absolutely no difference to the code
I just wrote there. One Haskell implementation might do it one way, and
another might do it a completely different way, and the program will
still run the same way.
In practise, when people say "Haskell does X", what they really mean is
"the only currently available production-grade Haskell implementation
(i.e., GHC) does X". Which isn't quite the same statement.
The simplest and easiest way to implement Haskell is for *everything* to
be a heap-allocated dynamic object. Obviously this has quite laughable
performance, and so real Haskell implementations go out of their way to
be more efficient where possible. Haskell is particularly helpful in
this regard, since it has no specified calling convention that you have
to adhere to, and everything is immutable, so it doesn't matter where
it's stored or whether you copy it.
Darren is quite right: Since [almost] everything is immutable, you can't
distinguish between a thing and a reference to a thing. You can't
distinguish between two pointers to the same thing and two pointers to
things that are identical. (I.e., there is no difference between
value-equal and reference-equal.) You can't distinguish copies from each
other. Heck, you can't even distinguish an evaluated result from an
unevaluated result!
This gives people trying to implement Haskell considerable design freedom.
In fact, consider this:
repeat x = x : repeat x
Semantically, this generates an infinite list with all elements equal to
x. But how is it implemented? Does it return a circular list, or does it
actually *execute* an infinite function-call loop?
The answer is... it doesn't matter. From within Haskell, it is
impossible to tell the difference.
Note that this is different from saying that there *is* no difference.
For example, a circular list clearly takes less storage space (and less
CPU time to manage) than an infinite loop that allocates another new
list node on each cycle. (To say nothing of cache locality and so on.)
In other words, there are a whole raft of design decisions that make
absolutely no difference to Haskell (i.e., your programs will still work
right), but potentially make a very big difference to run-time performance.
Since it does affect performance, GHC (and probably other
implementations) allow you to have some limited control over some of
these things using compiler pragmas, command line switches and so on.
But for the most part, the compiler internally uses sophisticated
algorithms to attempt to determine the best choices automatically on a
case-by-case basis. (And if you doubt this, check out the extensive
published literature output of the GHC team.)
Final note: If I start dealing with mutable data structures, now it
*does* matter whether you're talking about value-equity or
reference-equity. Since, in a multi-threaded scenario, value-equity
could potentially change at any moment, all the mutable containers
implement reference-equity.
Comparing two things for equity is a pure operation, which you can do
anywhere, at any time. If you want to compare two mutable objects for
value-equity, you must do it by hand. This involves manually fetching
the contents of the container - and thereby fixing exactly which moment
in time the comparison occurs at, since fetching the contents of a
mutable structure is an impure operation which must be explicitly
sequenced with respect to other impure operations in the same thread.
In summary, once again Haskell's type system forces us to stop, think,
and do the semantically correct thing.
Post a reply to this message
|
![](/i/fill.gif) |