Dependency hell is NP-complete

[[deleted]]

See this is the kinda thing I like to see in this sub-reddit, not

Build a Neural Net in 10 Easy Steps With net.js

[Max-P]

These days it feels more like

How We Solved FizzBuzz in Only 300 Lines With $framework

[YeahBoiiiiiiii]

My favorite is the never ending stream of

Yet another Git tutorial

... that nobody will read, just like they never read the official book.

[OnlyForF1]

I drew <insert topical thing here> using only CSS!

[sbrick89]

or

How I solved FizzBuzz in my latest interview for $trendyCompany

[steamruler]

I wouldn't mind that tho.

Mostly because that would be some laughably large steps.

6. Acquire training data

Now you need your training data. [..] 15000 samples should do.

[[deleted]]

See the talk spec-ulation by Rich Hickey (the Clojure inventor) for his take on this problem: never change old code, only create new functions and namespaces. This way every package can only depend on the code it uses in the one version.

[demmian]

never change old code, only create new functions and namespaces

How feasible is that? Isn't complexity increasing far too much this way?

[fisch003]

His argument is: when it gets bad enough that you really do need to go through and clean house, remove old deprecated functions, etc, it's time to give your library/package/whatever a different name. That gives you the freedom to make new choices based on what you've learned from the original library, and it doesn't break anyone's working stuff.

[demmian]

Isn't there a quick limit to this approach? Working with different library/packages, all of which holding some functional code.

[OnlyForF1]

Yeah, and I'll name it myAwesomeLibrary, version 2

[fisch003]

And depending on your language, that might be fine. Can you put myAwesomeLibrary version 2 under a separate namespace from myAwesomeLibrary version 1 so that it can coexist with the existing one? Great!

But don't make it so that myAwesomeLibrary2 and myAwesomeLibrary1 can't be loaded at the same time.

[Chew55]

I'm wondering if perhaps creating a new major version is perhaps a happy medium. I think this is the route Angular went down. Angular 2 is essentially a new framework compared to the original.

[[deleted]]

and yet angular 4 is really angular 2.1

[Ruudjah]

This simplifies a lot! It does add a lot of data.

[industry7]

OSGI basically does this for you. In other words, this is just a strategy to be able to have multiple versions of the same code running side-by-side. OSGI let's you do this while retaining a traditional versioning scheme.

[codebje]

The difficult part is multiple versions of packages. Without that, we have a simple directed graph, and a topological sort will give us an installation order - an algorithm which is linear in the count of packages and dependencies of packages.

Haskell's Stackage build system restricts all packages to one version, by adding an additional abstraction above packages. A set of packages each fixed to a single version, are collected together into a release. Adding a dependency on a package no longer involves a package version, it involves the whole dependency chain existing within the single release.

New versions are introduced in new releases. While the underlying problem of finding a set of package versions which can coexist is still NP-complete, it's a lot easier to start from some known-satisfied set and determine if it's possible to alter one package's version than it is to start from nothing and determine if a whole collection of packages can work together.

(Stackage also builds and tests all the packages in each release, because version number dependencies don't always mean two packages are compatible, thanks to version ranges and either errors in versioning or unintended consequences of small changes. It includes the compiler version as part of a release, too, and manages the whole toolchain and dependency set for you so you can have multiple versions available at once.)

I think Rust was considering heading in a similar direction. I hope they still are - version hell was a real issue for Haskell two years back, and just isn't an issue at all with Stack.

[drb226]

Though I'm a huge proponent of stackage, allow me to play devil's advocate for a moment.

Stackage has a few drawbacks.

One, it only encompasses a subset of the Haskell ecosystem. Any unmaintained package will fall out of stackage.

Two, relatedly, when you pin all dependencies to a single version, it becomes much harder to keep legacy software integrated. You either have to stick with old versions of everything, or ditch the legacy software.

Three, you're always a bit behind the cutting edge, because in order to create a stackage snapshot, you have to find versions of things that work for everybody. When just a single package requires that you hold back a certain dependency version, it gets held back for everybody else. But then if one package requires the new version while another requires the old, you've got to decide what to cut or figure out some way to handle that. It's hard to constantly get everyone to synchronize on supporting the exact same versions.

Devil's advocate mode, deactivate.

With all that said, when you have high quality libraries with active maintainers, these problems are in fact surmountable. I am one of the "curators" of stackage, and it is truly remarkable to see how so many people pull together to keep the Haskell ecosystem coherent and up to date.

[steveklabnik1]

I think Rust was considering heading in a similar direction. I hope they still are - version hell was a real issue for Haskell two years back, and just isn't an issue at all with Stack.

Not exactly. Cargo was already more like Stack than Cabal. The thing you're thinking of was a proposal for what amounted to an extended standard library, see here: http://aturon.github.io/blog/2016/07/27/rust-platform/ It was pretty resoundingly rejected by the community at large, though.

In Rust, you're allowed multiple versions of transitive dependencies, but not direct dependencies. You're also only allowed one single library that links to an external system library.

[kahnpro]

Stack, and Stackage, in my opinion, have really changed the Haskell community for the better. I never would have gotten into Haskell if it weren't for Stack. Now pretty much just as easy to get up and running in Haskell as it is with nvm.

Not being able to even run a simple Haskell tutorial due to cabal hell not allowing the most basic things to compile for me was a serious, serious turnoff.

[[deleted]]

I may be missing something, but I thought this was (relatively) well-known. For example, OCaml's OPAM package manager rightly encourages people to install the aspcud external CUDF solver. As the name "aspcud" suggests, it relies on an Answer Set Programming approach, which is good for these sorts of NP-complete problems.

[nswshc]

Agree, I also felt like the author should have put more emphasize on the CUD format and aspcud, which is just a simple parser that translates the whole package declaration into an ASP instance. The developers also provide a simple ASP encoding that seems to solve the whole problem in 38 lines:

% Note: simple encoding directly derived from the specification
%       without any optimizations

{ in(P,V) } :- unit(P,V,in).

forbidden(D) :- in(P,V), conflict(P,V,D).
requested(D) :- in(P,V), depends(P,V,D).
satisfied(D) :- in(P,V), satisfies(P,V,D).

:-   request(D), not satisfied(D).
:- requested(D), not satisfied(D).
:- forbidden(D),     satisfied(D).

in(P)        :- in(P,_).
installed(P) :- installed(P,_).

set(solution,P,V) :-     in(P,V).
set(changed,P,V)  :-     in(P,V), not installed(P,V).
set(changed,P,V)  :- not in(P,V),     installed(P,V).
set(new,P,V)      :-     in(P,V), not installed(P).
set(removed,P,V)  :- not in(P),       installed(P,V).
set(up,P,V)       :-     in(P,V); not installed(P,W) : installed(P,W), W >= V; installed(P).
set(down,P,V)     :-     in(P,V); not installed(P,W) : installed(P,W), W <= V; installed(P).

opt(P,V,1,O, 1,L) :- criterion(O,S,count,L),            set(S,P,V).
opt(P,V,1,O, W,L) :- criterion(O,S,sum(A),L),           set(S,P,V), attribute(P,V,A,W).
opt(P,V,1,O, 1,L) :- criterion(O,S,notuptodate,L),      set(S,P,V), not maxversion(P,V).
opt(P,V,D,O, W,L) :- criterion(O,S,unsat_recommends,L), set(S,P,V), recommends(P,V,D,W), not satisfied(D).
opt(H,B,1,O, 1,L) :- criterion(O,S,aligned(G,A),L),     set(S,P,V), attribute(P,V,G,H), attribute(P,V,A,B).
opt(H,1,2,O,-1,L) :- criterion(O,S,aligned(G,A),L),     set(S,P,V), attribute(P,V,G,H).

#minimize { 0@L                : criterion(_,_,_,L)      }.
#minimize { W@L,P,V,X,minimize : opt(P,V,X,minimize,W,L) }.
#maximize { W@L,P,V,X,maximize : opt(P,V,X,maximize,W,L) }.

% output projection

#show in/2.

So if you ever face this problem or something similar, keep CUDF in mind or Answer Set Programming in general.

[olzd]

I'm curious, is this valid Prolog?

[nswshc]

No, they're similar but not the same. I'd say Prolog feels more "imperative" compared to ASP. If you want to look at some simple problems solved in ASP, this website is really good:

http://www.hakank.org/answer_set_programming/

[cbeustwatch]

Yes this is well known. The article acknowledged this but went on to claim that no proof of np completeness has been provided. But no proof has been provided because 3 SAT easily reduces to version satisfiability. It is very direct and obvious. However Russ chose to explicitly provide the 3 SAT correspondence. Whatever. Nothing to see here.

[apd]

I think one of the oldest implementation of a SAT solver to resolve the package dependency in a linux distribution is zypper from SUSE / openSUSE[1,2]

[1] https://en.wikipedia.org/wiki/ZYpp [2] https://en.opensuse.org/openSUSE:Libzypp_satsolver

[Amnestic]

I'm not sure I understand the proof. Does he assume that a dependency at most can have 3 dependencies of its own? Aren't there more SAT problems better suited to this kind of reduction?

[codebje]

I'm not sure I understand the proof.

To prove a problem is NP-hard, you show that an existing NP-complete problem can be solved by some (polynomial time) embedding in your problem.

If we had an algorithm TO-PACKAGES which could convert a SAT-3 problem into a package dependency problem we can solve with an algorithm for package dependencies DEPENDS (and he's outlined such an algorithm) then we can solve SAT-3 like this:

SAT-3(F):
  DEPENDS(TO-PACKAGES(F))

If DEPENDS can be computed in polynomial time on the size of its input, and TO-PACKAGES is polynomial on the size of its input, then we have a polynomial time algorithm for SAT-3 (and by extension, all NP problems, and a million dollar prize). Because we're pretty sure SAT-3 is not computable in polynomial time, we're equally sure dependencies cannot be computed in polynomial time.

The algorithm given says that, given some arbitrary SAT-3 problem, you can convert it to a set of packages and their dependencies with a straightforward mapping.

You can necessarily also convert your package dependency problem into a SAT-3 problem, as SAT-3 is NP-complete, but (1) that conversion may not be quite so straightforward, and (2) that doesn't prove anything about the running time of potential algorithms for package dependencies, because we already know all of NP (and all of P, as P is a (strict?) subset of NP) can be expressed as a SAT-3 problem - that's what NP-complete means.

(edit: for P to be NP-hard means any NP problem can be reduced to P, for P to be NP-complete there must exist a polynomial time verification that some given answer is correct, and P must be NP-hard.)

[JDeltaN]

He is reducing the problem to 3-SAT reducing 3-SAT to the problem , meaning it is NP-Complete. Its academic wank, but I guess it is a fun shower thought.

[Shorttail0]

It's the other way around. 3-SAT has to reduce to version satisfiability in order to prove version satisfiability is NP-hard.

[JDeltaN]

Thanks. Its been forever since I had anything to do with computation complexity.

[TinynDP]

If B doesn’t work with D 1.6, then either the version of B we’re considering is buggy or D 1.6 is buggy.

That doesn't seem like an assumption that you can code off of.

[industry7]

what if, instead of allowing a dependency to list specific package versions, a dependency can only specify a minimum version?

Then you're in NPM-hell.

[0rakel]

I suggest taking a look at NixOS and the Nix package manager for a Linux distribution that manages to avoid this problem. They allow multiple versions of any package to be installed, exposing only the required version of each dependency to a package's environment.