<div dir="ltr"><div dir="ltr"><div dir="ltr"><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Fri, Apr 5, 2019 at 11:19 PM Michel Haber <<a href="mailto:michelhaber1994@gmail.com">michelhaber1994@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div>Hello Cafe,</div><div><br></div><div>So I've been learning a bit about the GHC extensions from <a href="https://github.com/i-am-tom/haskell-exercises" target="_blank">https://github.com/i-am-tom/haskell-exercises</a>. But the lessons say nothing about how the extensions work behind the scenes.</div><div><br></div><div>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.</div></div></div></blockquote><div><br></div><div>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</div><div><br></div><div>data SomeShow where</div><div>    SomeShow :: forall a . Show a => a -> SomeShow</div><div><br></div><div>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. </div><div><br></div><div>However, if you have a function like</div><div><br></div><div>foo :: Bar c => (forall a . Bar a => a -> b) -> c -> b</div><div>foo = id</div><div><br></div><div>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.</div><div><br></div><div>There are a few things to think about that might help reveal why these sorts of abstractions can be free.</div><div><br></div><div>* 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.</div><div>* Existential quantification *restricts* the behavior of a value, rather than expanding it.</div><div>* The semantics of the program are the same after you erase all the type information.</div><div>* Existential quantification doesn't stop the inliner from working.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div><br></div><div>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!).</div><div><br></div><div>Also if someone knows other tutorials and lessons for these, and other extensions, please feel free to share them :p<br></div></div></div></blockquote><div><br></div><div>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.</div><div><br></div><div>My guess is that this stuff changes so fast that the only practical place to write this stuff down is the GHC source code.</div><div><br></div><div>Cheers,</div><div>Will</div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div></div><div><br></div><div>Thank you,<br></div><div>Michel :)<br></div></div></div>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
To (un)subscribe, modify options or view archives go to:<br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
Only members subscribed via the mailman list are allowed to post.</blockquote></div></div></div>