Avoiding Quadratic Blow-up During Compilation
Please log in to watch this conference skillscast.
There are three main sources of of quadratic blow-up in the ghc core code generated during compilation. First, we cannot refer to or update a field of records without mentioning all the fields of that record, where it should be noted that type class dictionaries are also records. Second, lack of type level sharing results in a lot of duplication when using data types with constructors that reflect some kind of inductive structure. Third, type family reduction results in large type equality coercions.
In this talk we will take a closer look at each of these problems. We will see how the large-records library manages to circumvent all of these problems, but we will also discuss the principles involved in the hope that you can apply those in your own code. Although it would be good to tackle these problems at a more fundamental level, this talk focuses on how to deal with these problems with current-day ghc, not a hypothetical future one.
YOU MAY ALSO LIKE:
Thank you to our sponsors and partners
Gold
Bronze
Avoiding Quadratic Blow-up During Compilation
Edsko de Vries
Edsko has been using Haskell for nearly 20 years, and has been a professional Haskell consultant with Well-Typed for roughly half that time. He holds a PhD in advanced (substructural) type systems for pure functional languages from Trinity College, Dublin.
As a Well-Typed consultant, he has provided training across the world, from Johannesburg to Boston to Singapore. He has worked on a large variety of projects, both open source as well as closed source for specific clients. Some of the open source projects he has contributed to are Cloud Haskell, Hackage, the Hackage security library, ghc, Ziria (a DSL developed by Microsoft) and cabal. Some general purpose libraries he has (co)developed include generics-sop, nothunks, recover-rtti and large-records.
The last few years he has worked as a consultant with IOHK on the Cardano blockchain, where he was responsible for the overall architecture of the consensus layer, designed the hard fork combinator, and did research on formal specification of a crypto wallet and invented a novel coin selection algorithm.