On 11/11/2010 05:19 PM, Warp wrote:
> Invisible<voi### [at] devnull>  wrote:
>> I always used to think that creating a data structure who's size is not
>> statically known required handling it by reference. However, C++ somehow
>> manages to do this by value, so it seems my assumptions are incorrect.
>
>    No, dynamically allocated objects can only be handled with a pointer.
> You can of course wrap that pointer so that it looks and behaves like
> the allocated object itself, but as if handled by-value (including being
> scope-bound).
>
>    For example you can handle an instance of std::vector or std::string
> by value, but internally they contain a pointer to dynamically allocated
> memory (which they manage).

I see. (I think!) So, presumably, when you copy std::vector "by value", 
all it's actually copying is the reference to the real data?

>> In fact, thinking about it, you probably /could/ implement Haskell
>> without GC. It would just be far less efficient, that's all.
>
>    It would be less efficient because it would require always deep-copying
> data when it's passed around?

That's one reason.

The other reason is that Haskell expressions are not restricted to being 
*trees*. They can be general *graphs*. This is how you implement a 
common sub-expression such that it only gets computed once - a very 
useful thing to be able to do (obviously). I'm not quite sure how this 
would interact with a non-GC implementation.

>> The real situation is of course a bit more complicated than this, but
>> you get the idea.
>
>    It looks like a really inefficient way of computing a simple calculation.

It is. That's why there's an entire optimiser pass dedicated to removing 
all these steps if possible. If a, b and x are just plain ordinary 
integers, it's highly likely that the final machine code will just chuck 
those variables into machine registers and do the usual binary 
arithmetic directly.

Of course, all of this graph reduction /is/ pointless for a simple piece 
of arithmetic. But if we choose a less trivial example, it becomes clear 
why it's useful. For example, that old chestnut of the Fibonacci 
function where the output depends on the output. That's impossible in a 
normal language, but trivial in Haskell.

(Obviously no programmer in history has actually /needed/ the Fibonacci 
numbers. And if they did, there's a well-known O(1) algorithm for them 
anyway. It's just an example.)

Post a reply to this message