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