The Strange Loop conference

[Andrei Alexandrescu]

On 9/21/11 3:34 PM, Peter Alexander wrote:
> The problem it's simply intractable to do lazy computation in D while
> maintaining the 'correct' static typing.
>
> For example, in Haskell, map (correctly) has the signature:
>
> map :: (a -> b) -> [a] -> [b]
>
> but in D, std.map has the signature (expressed in some Haskell/D
> pseudocode)
>
> map :: (a -> b) -> [a] -> Map!((a -> b), [a])

I think it really is

map :: (a -> b) -> Range1!a -> Map!((a -> b), Range1!a)

i.e. the type of the input range is not fixed to be a built-in list. 
That makes D's map more general than Haskell's, but also more difficult 
to implement. For example, Haskell's implementation does not need to 
worry about O(1) access to the nth element of the result.

> To get the same kind of signature as Haskell, you'd need to use eager
> computation in D, but that's horrendously inefficient in most cases.
> Alternatively, you can use interfaces, but then you lose type
> information in a lot of situations.
>
> The problem with the D situation is that if I have a function:
>
> void foo(int[])
>
> then it can't be called with:
>
> foo(map!"2*a"([1, 2, 3]));
>
> I'm forced to either:
> (a) use eager computation by wrapping it in array(...)
> (b) change foo to be a template

This is exactly as it should be. For whatever reason, foo wants an 
array. For a good reason, map returns a lazy sequence that depends upon 
the type of its input. You necessarily need to force computation into an 
array because foo needs an array and because D arrays are eager.

This is tantamount to saying that D is not as good as Haskell at lazy 
computation. Fine - lazy computation is Haskell's turf.

> What if foo is a virtual member function? Those can't be templates.

Then it would need to take a dynamic Range as parameter, parameterized 
with the element type.

> What if foo recursively maps to itself? e.g.
>
> auto foo(Range)(Range r)
> {
> if (r.length == 1)
> return r.front;
> r.popFront();
> return map!"2*a"(r);
> }

Hm, this is not recursive (and should work).

> Someone in D.learn tried to write quickSort in a similar way, but it
> obviously doesn't work because of the infinite number of template
> instantiations. To simulate lazy computation in D, you require a type
> transformation, which doesn't work with recursion. You're only choice is
> to abstract away to some sort of IRange!T interface to remove the type
> divergence, but then you lose performance, and in some cases, type
> information.

But Haskell has lost the performance argument right off the bat.

You are mixing tradeoffs here. There are pretty immutable rules of what 
can and cannot be done, many of which are consequences of a handful of 
simple facts. You want Haskell capability with D performance. You can't 
have that.

> Of course, if every function that accepts a range becomes a template
> then you have the practical problem of managing the number of template
> instantiations. Code bloat is still a real problem with heavy template
> usage.
>
> Finally, map in Haskell just makes sense. You have a list of a's, a
> function of 'a to b' and you get a list of b's out the other end. It's
> simple, it's exactly what you want, and it just works. You can't say the
> same in D.

D's map is superior to Haskell's. There is no contest.

Again, Haskell's map forces only ONE range abstractions to fit 
everybody. D's map allows anyone to choose their own map abstraction, 
and is clever enough to define another map abstraction based on it that 
offers maximum capability and maximum efficiency.

(In addition, Hakell's map forces ONE higher-order function 
representation, whereas D works with a function alias, function, or 
delegate.)

> Of course, what D's lazy ranges do give you is performance in the simple
> cases*. There's no indirect function calls, which means things can be
> inlined, and you save yourself a few potential cache misses. We just
> have to accept that this performance is at the expense of simplicity and
> expressability.

You could have indirect calls in D.

> * I say simple cases because Haskell compiler can do deforestation
> optimisations, which are essentially intractable in D due to its
> imperative roots.

D also allows things that are essentially impossible in Haskell, such as 
quicksort.


Andrei