... | ... | @@ -5,21 +5,66 @@ |
|
|
|
|
|
GHC is still busy as ever. The GHC 7.0 branch has come and gone, and now that the branch has been closed we have finally made the long-planned switch from darcs to git. Meanwhile, we are busily working towards the 7.2 branch, and hope to make the 7.2.1 release in June. Some of the forthcoming highlights are:
|
|
|
|
|
|
- **Simon PJ: New coercions**
|
|
|
- In the autumn, Dimitrios and Simon PJ implemented a completely
|
|
|
new constraint solver for the type checker; we also complete an
|
|
|
epic JFP paper describing how it works [ http://research.microsoft.com/\~simonpj/papers/constraints/ OutsideIn](http://research.microsoft.com/~simonpj/papers/constraints/ OutsideIn). The new
|
|
|
solver is far more tractable and maintainable than the old type
|
|
|
checker, and has fixed many outstanding problems. We are still
|
|
|
shaking out the last bugs, and we have some nifty ideas for improving
|
|
|
performance. Based on this new foundation, we are planning to
|
|
|
develop the type system further, notably by adding a richer kind
|
|
|
system along the lines of Conor McBride's SHE system [ http://personal.cis.strath.ac.uk/\~conor/pub/she/ SHE](http://personal.cis.strath.ac.uk/~conor/pub/she/ SHE).
|
|
|
|
|
|
- GHC's intermediate language (which we call "Core") is a simple,
|
|
|
explicitly-typed lambda in the style of System F. Core is far,
|
|
|
far simpler than Haskell (`CoreExpr` has only eight data
|
|
|
constructors), so GHC can type-check Core very fast and reliably.
|
|
|
In theory, such a typecheck is redundant (since the original
|
|
|
Haskell program was typechecked), but in practice, typechecking
|
|
|
Core is a very powerful internal consistency check on GHC itself:
|
|
|
many compiler bugs generate type-incorrect Core. This consistency
|
|
|
check is run by `-dcore-lint`.
|
|
|
|
|
|
- **Simon PJ: generics**
|
|
|
|
|
|
- **Simon PJ: Any update? Any regressions remaining?** Previous entry: *As long promised, Simon PJ and Dimitrios have spent a good chunk of the summer doing a **complete rewrite of the constraint solver in the type inference engine**. Because of GHC's myriad type-system extensions, especially GADTs and type families, the old engine had begun to resemble the final stages of a game of Jenga. It was a delicately-balanced pile of blocks that lived in constant danger of complete collapse, and had become extremely different to modify (or even to understand). The new inference engine is much more modular and robust; it is described in detail in our paper [ http://haskell.org/haskellwiki/Simonpj/Talk:OutsideIn OutsideIn](http://haskell.org/haskellwiki/Simonpj/Talk:OutsideIn OutsideIn). A blog post describes some consequential changes to let generalisation [ http://hackage.haskell.org/trac/ghc/blog/LetGeneralisationInGhc7 LetGen](http://hackage.haskell.org/trac/ghc/blog/LetGeneralisationInGhc7 LetGen).*
|
|
|
|
|
|
> *As a result we have closed dozens of open type inference bugs, especially related to GADTs and type families.*
|
|
|
|
|
|
- **Simon Marlow: Any update?** Previous entry: *In joint work with Phil Trinder and his colleagues at Herriot Watt, Simon M designed implemented a new **parallel strategies library**, described in their 2010 Haskell Symposium paper [ http://www.haskell.org/\~simonmar/papers/strategies.pdf Seq](http://www.haskell.org/~simonmar/papers/strategies.pdf Seq).*
|
|
|
>
|
|
|
> With the advent of GADTs and type families, the type system of the
|
|
|
> Core had to grow a little. For a few
|
|
|
> years we have been using an extension of System F, called System
|
|
|
> FC, as described in our 2007 paper [ http://research.microsoft.com/\~simonpj/papers/ext-f/ FC](http://research.microsoft.com/~simonpj/papers/ext-f/ FC). However, the way that System FC
|
|
|
> was actually *implemented* in GHC's Core language was a bit unsatisfactory
|
|
|
> so, with help from **Brent Yorgey**, Simon PJ is busy re-engineering it.
|
|
|
> In particular, FC has *coercion terms*, and these will now
|
|
|
> be represented by their own data type `Coercion`, rather than being
|
|
|
> squeezed into `Type`. Moreover, these coercion terms can get big,
|
|
|
> so there's a new "coercion optimiser" to replace big coercions by
|
|
|
> equivalent smaller ones. All this is described in our new paper [ NewFC](http://research.microsoft.com/~simonpj/papers/ext-f/).
|
|
|
> These changes will (finally) complete the type-family story by
|
|
|
> making so-called "equality superclasses" work for the first time in GHC 7.2.
|
|
|
|
|
|
- **Pedro Magalhães** has nearly completed his implementation of the
|
|
|
**derivable type classes** mechanism described in his 2010
|
|
|
Haskell Symposium paper [ http://www.dreixel.net/research/pdf/gdmh_nocolor.pdf Derivable](http://www.dreixel.net/research/pdf/gdmh_nocolor.pdf Derivable). It will be in GHC 7.2.
|
|
|
|
|
|
- **Edward Yang** has spearheaded a flurry of work on the new
|
|
|
code generation backend (`-fuse-new-codegen`, the rewrite of
|
|
|
the part of GHC that turns STG syntax into C--). Hoopl is now
|
|
|
fully part of GHC [ http://research.microsoft.com/\~simonpj/papers/c--/ Hoopl](http://research.microsoft.com/~simonpj/papers/c--/ Hoopl), and the new path uses it extensively; we’ve
|
|
|
ironed out most of the bugs in the backend; and now we’re
|
|
|
working on new optimization passes and fixing inefficiencies to
|
|
|
get the generated code as good (or better) than the old code
|
|
|
generator. We’re still not at the point where the new code
|
|
|
generator will generate better code, but we’re pretty close!
|
|
|
Stay tuned.
|
|
|
|
|
|
- Simon Marlow and **Ryan Newton** have developed a neat new library for deterministic parallel progarmming in Haskell; read their ICFP submission [ http://research.microsoft.com/\~simonpj/papers/parallel/ DetPar](http://research.microsoft.com/~simonpj/papers/parallel/ DetPar). The model is monadic and has explicit control over granularity, but allows dynamic construction of dataflow networks that are scheduled at runtime, while remaining deterministic and pure.
|
|
|
|
|
|
- **Simon Marlow: any update?** Previous entry: *Simon Marlow is working on a new garbage collector that is designed to improve scaling of parallel programs beyond small numbers of cores, by allowing each processor core to collect its own local heap independently of the other cores. Some encouraging preliminary results were reported in a [ blog post](http://hackage.haskell.org/trac/ghc/blog/2010/9#new-gc-preview). Work on this continues; the complexity of the system and the number of interacting design choices means that achieving an implementation that works well in a broad variety of situations is proving to be quite a challenge.*
|
|
|
|
|
|
|
|
|
We are fortunate to have a growing team of people willing to roll up their
|
|
|
sleeves and help us with GHC. Amongst those who have been active recently are:
|
|
|
|
|
|
- Mark Lentczner and Dan Knapp have been working on cross-compilation support
|
|
|
- Continued work on the new I/O manager by Johan Tibbe.
|
|
|
- Various improvements and build fixes for OS X, from PHO, Greg Wright, Thorkil Naur and William Knop
|
|
|
- Solaris fixes from Karel Gardas and Christian Maeder
|
|
|
- Gentoo fixes (for SE Linux and x86 FreeBSD support) from Sergei Trofimovich
|
... | ... | @@ -39,32 +84,19 @@ sleeves and help us with GHC. Amongst those who have been active recently are: |
|
|
At GHC HQ we are having way too much fun; if you wait for us to
|
|
|
do something you have to wait a long time. So don't wait; join in!
|
|
|
|
|
|
## Language developments, especially types
|
|
|
|
|
|
**Simon PJ: Any updates on the below?**
|
|
|
## Other developments
|
|
|
|
|
|
|
|
|
GHC continues to act as an incubator for interesting new language developments.
|
|
|
Here's a selection that we know about.
|
|
|
|
|
|
- *Pedro Magalhaes is implementing the **derivable type classes** mechanism described in his 2010 Haskell Symposium paper [ http://www.dreixel.net/research/pdf/gdmh_nocolor.pdf Derivable](http://www.dreixel.net/research/pdf/gdmh_nocolor.pdf Derivable). I plan for this to replace GHC's current derivable-type-class mechanism, which has a poor power-to-weight ratio and is little used.*
|
|
|
|
|
|
- *Stephanie Weirich and Steve Zdancewic had a great sabbatical year at Cambridge. One of the things we worked on, with Brent Yorgey who came as an intern, was to close the embarrassing hole in the type system concerning **newtype deriving** (see Trac bug [\#1496](https://gitlab.haskell.org//ghc/ghc/issues/1496)). I have delayed fixing until I could figure out a Decent Solution, but now we know; see our 2011 POPL paper [ http://www.cis.upenn.edu/\~sweirich/newtypes.pdf Newtype](http://www.cis.upenn.edu/~sweirich/newtypes.pdf Newtype). Brent is working on some infrastructal changes to GHC's Core language, and then we'll be ready to tackle the main issue.*
|
|
|
|
|
|
- *Next after that is a mechanism for **promoting types to become kinds**, and data constructors to become types, so that you can do *typed* functional programming at the type level. Conor McBride's SHE prototype is the inspiration here [ http://personal.cis.strath.ac.uk/\~conor/pub/she/ SHE](http://personal.cis.strath.ac.uk/~conor/pub/she/ SHE). Currently it is, embarrassingly, essentially untyped.*
|
|
|
|
|
|
- ***Template Haskell** seems to be increasingly widely used. Simon PJ has written a proposal for a raft of improvements, which we plan to implement in the new year [ http://hackage.haskell.org/trac/ghc/blog/Template%20Haskell%20Proposal TemplateHaskell](http://hackage.haskell.org/trac/ghc/blog/Template%20Haskell%20Proposal TemplateHaskell).*
|
|
|
- **Jeff Epstein**, in collaboration with Andrew Black, has implemented a library that brings Erlang's programming model to Haskell programmers. In particular, you can write a Haskell program that runs on a cluster of machines that do not share memory. It is all based on a modest but powerful language extension that makes it possible for a programmer to work with "static" functions; that is, ones consisting of pure code with no free variables. The paper that describes all this is called "Haskell for the cloud" [ http://research.microsoft.com/\~simonpj/papers/parallel/ Cloud](http://research.microsoft.com/~simonpj/papers/parallel/ Cloud).
|
|
|
|
|
|
- *Iavor Diatchki plans to add **numeric types**, so that you can have a type like `Bus 8`, and do simple arithmetic at the type level. You can encode this stuff, but it's easier to use and more powerful to do it directly.*
|
|
|
- **Max Bolingbroke** continues his !PhD work on supercompilation, with a nice new paper [ http://research.microsoft.com/\~simonpj/papers/supercompilation/ ImprovingSupercompilation](http://research.microsoft.com/~simonpj/papers/supercompilation/ ImprovingSupercompilation). The plan is to make his supercompiler part of GHC, over the next year or so.
|
|
|
|
|
|
- *David Mazieres at Stanford wants to implement **Safe Haskell**, a flag for GHC that will guarantee that your program does not use `unsafePerformIO`, foreign calls, RULES, and other stuff stuff.*
|
|
|
|
|
|
## Packages and the runtime system
|
|
|
|
|
|
> **Simon Marlow: any update?** Previous entry: *Simon Marlow is working on a new garbage collector that is designed to improve scaling of parallel programs beyond small numbers of cores, by allowing each processor core to collect its own local heap independently of the other cores. Some encouraging preliminary results were reported in a [ blog post](http://hackage.haskell.org/trac/ghc/blog/2010/9#new-gc-preview). Work on this continues; the complexity of the system and the number of interacting design choices means that achieving an implementation that works well in a broad variety of situations is proving to be quite a challenge.*
|
|
|
|
|
|
>
|
|
|
> The new code generation backend (`-fuse-new-codegen`, the rewrite of the part of GHC that turns STG syntax into C--) has seen a flurry of work, spearheaded by Edward Z. Yang. At this point, we’ve ironed out most of the bugs in the backend, and now we’re working on new optimization passes and fixing inefficiencies to get the generated code as good (or better) than the old code generator. We’re still not at the point where the new code generator will generate better code, but we’re pretty close!
|
|
|
- **Ranjit: would you like to add a para?**
|
|
|
|
|
|
## The Parallel GHC Project
|
|
|
|
... | ... | @@ -80,7 +112,7 @@ Microsoft Research is funding a 2-year project to develop the real-world use of |
|
|
with consulting and engineering support from Well-Typed. Each organisation is working on its own particular project making use of parallel Haskell. The overall goal is to demonstrate successful serious use of parallel Haskell, and along the way to apply engineering effort to any problems with the tools that the organisations might run into.
|
|
|
|
|
|
|
|
|
For more details, see the **link:**parallel GHC project entry.
|
|
|
For more details, see the **link:**parallel GHC project entry, and the project home page [ http://www.haskell.org/haskellwiki/Parallel_GHC_Project ParallelGhcProject](http://www.haskell.org/haskellwiki/Parallel_GHC_Project ParallelGhcProject)
|
|
|
|
|
|
## Data Parallel Haskell
|
|
|
|
... | ... | @@ -92,27 +124,27 @@ We have pushed back the release of a stable version of the main DPH libraries ag |
|
|
|
|
|
## Bibliography
|
|
|
|
|
|
**TODO Remove redundant entries**
|
|
|
- \[Cloud\] "Haskell for the cloud", Epstein, Black, Peyton Jones, submitted to ICFP 2011, [ http://research.microsoft.com/\~simonpj/papers/parallel/](http://research.microsoft.com/~simonpj/papers/parallel/)
|
|
|
|
|
|
- \[Bryan\] "A brief tale of faster equality", Bryan O'Sullivan blog post, Oct 2010, [ http://www.serpentine.com/blog/2010/10/19/a-brief-tale-of-faster-equality/](http://www.serpentine.com/blog/2010/10/19/a-brief-tale-of-faster-equality/).
|
|
|
- \[Derivable\] "A generic deriving mechanism for Haskell", Magalhães, Dijkstra, Jeuring and Löh, Haskell Symposium 2010, [ http://www.dreixel.net/research/pdf/gdmh_nocolor.pdf](http://www.dreixel.net/research/pdf/gdmh_nocolor.pdf).
|
|
|
|
|
|
- \[Containers\] "The performance of the Haskell containers package", Straka, Haskell Symposium 2010, [ http://research.microsoft.com/\~simonpj/papers/containers/containers.pdf](http://research.microsoft.com/~simonpj/papers/containers/containers.pdf)
|
|
|
- \[DetPar\] "A monad for deterministic parallelism", Marlow, Newton, and Peyton Jones, submitted to ICFP 2011, [ http://research.microsoft.com/\~simonpj/papers/parallel/](http://research.microsoft.com/~simonpj/papers/parallel/)
|
|
|
|
|
|
- \[Derivable\] "A generic deriving mechanism for Haskell", Magalhães, Dijkstra, Jeuring and Löh, Haskell Symposium 2010, [ http://www.dreixel.net/research/pdf/gdmh_nocolor.pdf](http://www.dreixel.net/research/pdf/gdmh_nocolor.pdf).
|
|
|
- \[FC\] "System F with type equality coercions", Sulzmann, Chakravarty, Peyton Jones, TLDI 2007, [ http://research.microsoft.com/\~simonpj/papers/ext-f/](http://research.microsoft.com/~simonpj/papers/ext-f/)
|
|
|
|
|
|
- \[LetGen\] "Let generalisation in GHC 7.0", Peyton Jones, blog post Sept 2010, [ http://hackage.haskell.org/trac/ghc/blog/LetGeneralisationInGhc7](http://hackage.haskell.org/trac/ghc/blog/LetGeneralisationInGhc7)
|
|
|
- \[Hoopl\] "A modular, reusable library for dataflow analysis and transformation", Dias, Ramsey, and Peyton Jones, Haskell Symposium 2010, [ http://research.microsoft.com/\~simonpj/papers/c--/](http://research.microsoft.com/~simonpj/papers/c--/)
|
|
|
|
|
|
- \[Newtype\] "Generative Type Abstraction and Type-level Computation", Weirich, Zdancewic, Vytiniotis, and Peyton Jones, POPL 2010, [ http://www.cis.upenn.edu/\~sweirich/newtypes.pdf](http://www.cis.upenn.edu/~sweirich/newtypes.pdf)
|
|
|
- \[ImprovingSupercompilation\] "Improving supercompilation: tag-bags, rollback, speculation, normalisation, and generalisation", Bolingbroke and Peyton Jones, submitted to ICFP 2011, [ http://research.microsoft.com/\~simonpj/papers/supercompilation/](http://research.microsoft.com/~simonpj/papers/supercompilation/)
|
|
|
|
|
|
- \[Llvm\] "An LLVM Backend for GHC", Terei and Chakravarty, Haskell Symposium 2010, [ http://www.cse.unsw.edu.au/\~davidt/downloads/ghc-llvm-hs10.pdf](http://www.cse.unsw.edu.au/~davidt/downloads/ghc-llvm-hs10.pdf)
|
|
|
- \[NewFC\] "Practical aspects of evidence-based compilation in System FC", Vytiniotis and Peyton Jones, submitted to ICFP 2011, [ http://research.microsoft.com/\~simonpj/papers/ext-f/](http://research.microsoft.com/~simonpj/papers/ext-f/)
|
|
|
|
|
|
- \[Seq\] "Seq no more", Marlow, Maier, Trinder, Loidl, and Aswad, Haskell Symposium 2010, [ http://www.haskell.org/\~simonmar/papers/strategies.pdf](http://www.haskell.org/~simonmar/papers/strategies.pdf)
|
|
|
- \[OutsideIn\] "Modular type inference iwth local assumptions", Vytiniotis, Peyton Jones, Schrijvers, and Sulzmann, Journal of Functional Programming (to appear), [ http://research.microsoft.com/\~simonpj/papers/constraints/](http://research.microsoft.com/~simonpj/papers/constraints/)
|
|
|
|
|
|
- \[SHE\] The Strathclyde Haskell Enhancement, Conor McBride, 2010, [ http://personal.cis.strath.ac.uk/\~conor/pub/she/](http://personal.cis.strath.ac.uk/~conor/pub/she/)
|
|
|
- \[ParallelGhcProject\] "The Parallel GHC Project home page", [ http://www.haskell.org/haskellwiki/Parallel_GHC_Project](http://www.haskell.org/haskellwiki/Parallel_GHC_Project)
|
|
|
|
|
|
- \[TemplateHaskell\] New directions for Template Haskell, Peyton Jones, blog post October 2010, [ http://hackage.haskell.org/trac/ghc/blog/Template%20Haskell%20Proposal](http://hackage.haskell.org/trac/ghc/blog/Template%20Haskell%20Proposal)
|
|
|
- \[Repa\] "Regular, shape-polymorphic parallel arrays in Haskell", Keller, Chakravarty, Leshchinskiy, Peyton Jones, and Lippmeier, ICFP 2010. Paper: [ http://research.microsoft.com/\~simonpj/papers/ndp/](http://research.microsoft.com/~simonpj/papers/ndp/), Hackage package: [ http://hackage.haskell.org/package/repa](http://hackage.haskell.org/package/repa)
|
|
|
|
|
|
- \[Hoopl\] Hoopl: A Modular, Reusable Library for Dataflow Analysis and Transformation, [ http://research.microsoft.com/en-us/um/people/simonpj/papers/c--/dfopt.pdf](http://research.microsoft.com/en-us/um/people/simonpj/papers/c--/dfopt.pdf)
|
|
|
- \[SHE\] The Strathclyde Haskell Enhancement, Conor McBride, 2010, [ http://personal.cis.strath.ac.uk/\~conor/pub/she/](http://personal.cis.strath.ac.uk/~conor/pub/she/)
|
|
|
|
|
|
- \[Stencil\] Efficient Parallel Stencil Convolution in Haskell, Lippmeier et al., [ http://www.cse.unsw.edu.au/\~benl/papers/stencil/stencil-icfp2011-sub.pdf](http://www.cse.unsw.edu.au/~benl/papers/stencil/stencil-icfp2011-sub.pdf)
|
|
|
|
... | ... | |