[Haskell-cafe] GHC extensions

[William Yager]

On Fri, Apr 5, 2019 at 11:19 PM Michel Haber <michelhaber1994 at gmail.com>
wrote:

> Hello Cafe,
>
> So I've been learning a bit about the GHC extensions from
> https://github.com/i-am-tom/haskell-exercises. But the lessons say
> nothing about how the extensions work behind the scenes.
>
> For example, I've assumed that RankNTypes would require something similar
> to dynamic dispatch in imperative languages in order to work. But this is
> just an assumption.
>

Sometimes, when you use a universally  quantified type (forall a . ...),
the only way to construct it is to use some kind of dynamic dispatch. For
example, if you have a GADT

data SomeShow where
    SomeShow :: forall a . Show a => a -> SomeShow

In the absence of extremely aggressive inlining (which GHC might be able to
do, I'm not sure), the only way to operate on such an object is to pass a
vtable full of dynamic function pointers for the "Show" typeclass along
with the "a" value.

However, if you have a function like

foo :: Bar c => (forall a . Bar a => a -> b) -> c -> b
foo = id

Even though there's a rank-2 type here, I would reasonably expect GHC to be
able to construct this function with no additional overhead whatsoever.
After all, it's just the identity function.

There are a few things to think about that might help reveal why these
sorts of abstractions can be free.

* A "=>" arrow is just like a "->" arrow except it's the compiler's job to
pass in the argument to a "=>" function. If the compiler could optimize a
"->" function, it could probably optimize a similar "=>" function.
* Existential quantification *restricts* the behavior of a value, rather
than expanding it.
* The semantics of the program are the same after you erase all the type
information.
* Existential quantification doesn't stop the inliner from working.


> So I was wondering where I can get a quick succinct read (or a summary at
> least) about how these extensions are implemented, as well as their
> performance cost (or gain!).
>
> Also if someone knows other tutorials and lessons for these, and other
> extensions, please feel free to share them :p
>

As a heuristic, I would hand-wavily claim that GHC typically tries its
hardest to avoid type-level abstractions introducing value-level
performance overhead, but it also doesn't try especially hard to use
type-level abstractions to inform the optimizer.  I think it's unlikely
that turning on fancy type-system features will make your code go *faster*,
but as long as you're careful it probably also won't go slower.

My guess is that this stuff changes so fast that the only practical place
to write this stuff down is the GHC source code.

Cheers,
Will


>
> Thank you,
> Michel :)
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20190408/0c546b09/attachment.html>