blog.well-typed.com

One issue that came up several times at the hackathon—especially when talking to the Yi hackers—is the dreaded diamond dependency problem. This happens when you have 4 packages in a diamond shaped dependency graph:

The problem arises when we have package B and C already installed but built against different versions of D and then we try to use both packages B and C together in package A:

This can work ok but only if packages B and C do not expose types defined in D in their interfaces. If they do then package A will not be able to use functions from B and C together because they will not be working with the same type. That is you’ll get a type error.

To pick a concrete example, suppose package D is bytestring and we have both bytestring-0.9.0.1 and 0.9.0.4 installed. Lets say B is utf8-string and C is regex-base. Lets say that package A is the Yi editor program. So the point is, at some place in the code in Yi we want to pass a bytestring produced as the result of UTF-8 decoding as input to one of the regex functions. But this does not work because the functions in the utf8-string package are using the ByteString type from bytestring-0.9.0.1 while the regex functions in the regex package are using the ByteString type from bytestring-0.9.0.4. So we get a type error when we try to compile Yi:

Couldn't match expected type `bytestring-0.9.0.4:Data.ByteString.ByteString'
against inferred type `bytestring-0.9.0.1:Data.ByteString.ByteString'

As far as GHC knows, these two types are totally unrelated!

This is obviously extremely annoying. There is also no easy solution. In this example we’re assuming that packages B and C have already been built, so there is actually no way to sensibly use the two packages together without rebuilding on of them against a different version of package D. In this case the obvious solution is to rebuild B to use the D-1.1 rather than D-1.0. The problem with rebuilding a package of course is it breaks all other packages that have already been built against it. It isn’t clear that you want a package manager to go automatically rebuilding lots of apparently unrelated packages.

In the longer term the best solution would seem to be to do what Nix does. In the above example, instead of replacing package B built against D-1.0 with B built against D-1.1, Nix would add
another instance of B built against D-1.1. So the original instance of B would remain unchanged and nothing would break. It’s the functional approach: we never mutate values (installed packages) we just create new ones and garbage collect old one when they are no longer needed.

In practice it means we have to identify installed packages using some hash of the package and the hashes of all dependent packages. jhc already does this and there are moves afoot to do something similar for GHC, though aimed more at tracking API/ABI changes. For sane source based package management, I think it’s the right direction to take.

I should note that this is not a new problem. You’ve been able to construct this problem ever since ghc started to allow multiple versions of the same package to be installed at once. We are just noticing it a lot more frequently now because we split up the base package and allow those split-out packages to be upgraded.

The current state of play is that Cabal warns of this problem but doesn’t really help you solve it. For the above example we’d get:

$ cabal configure
Configuring A-1.0...
Warning: This package indirectly depends on multiple versions of
the same package. This is highly likely to cause a compile failure.
package B-1.0 requires D-1.0
package C-1.0 requires D-1.1

I am very pleased to be mentoring Andrea Vezzosi (aka Saizan) on a Google Summer of Code project to develop a make-like dependency framework for use in Cabal. I’m really looking forward to working with Saizan on this. It should be a fun and useful project.

Congratulations to Saizan and good luck with the project!

The project itself is to start prototyping one of the big features we need for Cabal to become a really excellent build system. At the moment Cabal calls out to ghc --make to do the hard work of figuring out what needs to be rebuilt. This only works for .hs files of course while we need it to work for all preprocessors. More generally there are a lot of things that Cabal does that would benefit from being done in a dependency style — not just limited to running external programs that update files. In addition everyone has multi-core CPUs now and we’d like to do parallel builds.

The Real World Haskell book is now available for pre-order!

I’ve just ordered my copy from Amazon UK for £30.99 and it’s available from Amazon in the US for $49.99.

I’d like to be able to recommend a canonical “learning Haskell” bookshelf. The slot for an introductory book has been filled by the excellent Programming in Haskell (you can read my review). Judging by the material the Real World Haskell book aims to cover, it looks like it should be a pretty good complement, mostly picking up where Programming in Haskell leaves off and covering the language techniques and tools you need to get started writing serious programs.

We ended up with quite a big group of people interested in various aspects of Cabal, cabal-install and Hackage. So I ended up spending much more time talking than hacking. I’m sure that’s a good thing though. Hackathons should be about sharing ideas, brainstorming and experimenting.

I arrived at the hackathon with ideas about three main areas I wanted to get people to work on:

• a make-like dependency framework for the Cabal library
• a package dependency resolver for cabal-install
• cabal-install/hackage build reporting

In fact these are more or less exactly the topics for proposed Google Summer of Code projects, but there’s no harm in starting early and exploring possible solutions.

I expounded a bit on the dependency framework issue though we didn’t end up working on that in the end. It’s actually an interesting research problem. I’ll write about it another time.

Josef Svenningsson got interested in the cabal-install dependency resolver issue. He spent much of the hackathon prototyping a BDD-style approach. Hopefully Josef will post his current ideas to the cabal-devel mailing list in the next week or so.

Thomas Schilling (aka nominolo) worked on the last remaining feature we wanted to get into Cabal-1.4. When configuring a package want to be able to specify additional constraints on the versions of dependent packages. As a developer we might want this just to be able to test building a package against an old rather than the latest version of a dependency. The reason we really want it for Cabal-1.4 though is so that we can use it in cabal-install. In cabal-install we want to work out up front exactly how we will configure a whole set of packages. We need a way to get Cabal to configure a package exactly how we wanted it in our global plan, rather than making some local decision. Thomas got this finished and I’ll be integrating the patches some time soon.

Lennart Kolmodin (with some help from David Waern and myself) spent quite a while hacking on build reporting in cabal-install. The idea here is that we want to get cabal-install to report build success and failure back to the hackage server so we can discover what packages build in what environments. On the client side most of the work involves information plumbing — gathering information from various places within Cabal to include into a build report. We realised that most of the information for a build report is discovered once we’ve decided how we’re going to configure the package. So we spent most time hacking on some code I’d written previously for representing installation plans and extending it to collect information on the outcome of installation. We managed to get it integrated though it still needs more work because our new InstallPlan type has a much more demanding notion of validity than the abstraction it replaces, so the current dependency resolver needs to be updated to produce valid InstallPlans.

Hac4 is now over, everyone has arrived home safely and all the equipment has been returned. 27 people attended, though not everyone could come every day. 10 attendees travelled from several European countries and from the US. People hacked on lots of projects, including Yi, Cabal, ByteString, a new web application interface, QuickCheck, CGI, first-order logic reasoning, Allegro bindings, Haddock, the community server, HAppS-HSP, replacing libgmp in GHC, Squiggle, restricted monads, and more.

We also decided to set up a Haskell Hackathon Steering Committee which will help find hosts for future hackathons and aid the local organizers.

Thanks to sponsorship from Credit Suisse and Galois, we could provide food for everyone during the whole hackathon. This made it possible to keep the group together and keep hacking (some stayed well into the night). The Department of Computer Science and Engineering at Chalmers University of Technology and University of Gothenburg provided space and networking. 

A big thank you to everybody who made this happen by sponsoring, attending and helping out with the organization!

Pictures from the third and last day of Hac4:

Some pictures from the second day of Hac4:

The 4th Haskell Hackathon has started, and all of Well-Typed is here.

Some pictures from the first day:

It’s been many months in the planning but we finally announced our new Haskell consultancy company - Well-Typed LLP.

We received many messages of support and advice. We’re most grateful for all this goodwill from the community.

There’s now one more argument you can make when selling Haskell in your organisation - there’s now a company dedicated to supporting your language of choice.

The next six months are going to be pretty exciting.