Announcing decision diagrams

[Duncan Coutts]

Hi Josef,


On Tue, 2008-04-29 at 14:19 +0200, Josef Svenningsson wrote:
> Hi,
> 
> A few weeks ago during the Hackathon in Gothenburg I started working
> on a library for decision diagrams. The purpose was to use it in
> cabal-install when figuring out which packages should be installed and
> which version of them to choose. Why do we need something as complex
> as decision diagrams for that? Simply because the problem is
> NP-complete in general. Now, heuristics might do a good job at solving
> this problem but it might be wise to have something like this library
> as a fall-back.
> 
> So, I'm happy to announce the first version of my decision diagram
> library.  The darcs repo can be found here:
> http://www.cs.chalmers.se/~josefs/decisiondiagram

Thanks for publishing this.

> The status of the library is as follows: I'm beginning to trust the
> correctness of the implementation. There are a few tests in place and
> although I have more tests in mind the testing that I have already
> done gives me quite a bit of confidence. As to the speed of the
> library: it's pretty poor. I've used most of the tricks in the book on
> implementing decision diagrams so complexity  wise it should be like
> any other BDD implementation except for a few log factors here and
> there. But I haven't cared anything about constant factors, so the
> wall clock performance is pretty weak. As a benchmark I wrote a small
> sudoku solver but my library choked on even an easy puzzle. I
> nevertheless feel that this library is a good starting point and that
> it will be able to handle all current packages that we have easily.

Yes, we typically expect 'easy' instances of the problem. Though we
would like to be able to handle large easy instances too, like trying to
install the latest version of every package on hackage simultaneously.

Perhaps we should have a go with profiling and see if there is anything
obvious.

> I am aware that the is a GSOC project coming up which is supposed to
> tackle this issue as well. This package is by no means meant to
> supersede that project before it has begun. I think we can benefit
> from several approaches here since the underlying problem is
> NP-complete and thus it's probably wise to evaluate more than one
> option.

Actually it didn't get funded as a GSoC project but Maciej Wos is
looking at this problem for his 4th year project. As you say, the design
space is very wide so I would not want to discourage you or anyone from
looking at it.

> I haven't looked into how to use this package in cabal-install yet,
> but I suspect it will be fairly easy. I'd appreciate any comments and
> help on that though since I'm not familiar with the cabal-install code
> base yet.

I want to make the resolver a bit more easily replaceable. 

I think we can take the resolver as a parameter:

type DependencyResolver =
          OS -> Arch -> CompilerId
       -> PackageIndex InstalledPackageInfo
       -> PackageIndex GenericPackageDescription
       -> [Dependency]
       -> Either InstallPlan ErrorMessage

So we have some parameters about the environment which we need to
resolve package conditionals. Conditions can be based on the OS, the CPU
architecture or the compiler we're going to use.

Then we have the set of installed packages and the set of packages that
are available but not yet installed. The installed package have fixed
dependencies while the not yet installed packages have conditional
dependencies on version ranges.

An install plan is a set of packages to be installed along with all the
installed packages they are going to use. It specifies for each package
to be installed exactly what flag assignment to use and what versions of
package dependencies we are going to use. An install plan has to be
acyclic, complete and consistent. The graph of dependencies must be
acyclic. The plan must be complete in the sense that every dependency
must also be in the plan. Plan consistency means that for each package
name in the plan there must be only one version of that package.

Together these constraints ensure that the plan is feasible.

Duncan