News for hackers. Stuff that matters.
Re:Thoughts on “Dependency hell is NP-complete” by thinkpad20 on Saturday December 17, 2016 @03:15AM (#13199844)
Nix has a different approach to the problem, with its own set of benefits and drawbacks: packages do not specify version ranges of their dependencies at all; instead they reference them via variables (most commonly -- more generally they can be any arbitrary expression). For example if I'm writing a python package which depends on flask, I might list `flask` as a dependency of my package, or perhaps `flask11` or something.

    # pseudocode
    my_package = buildPythonPackage {
      name = "my_package";
      source = ./path/to/source;
      dependencies = [flask];
    };
Whatever that variable resolves to is the thing which will be built (and is itself defined in a similar way), so "version resolution" is replaced with a pure computation, the evaluation of an expression.

This approach offers a great deal of advantages, including very fast (roughly linear) calculation of what to build, full determinism in what gets built, and the ability to specify any arbitrary nix expression as a dependency, say some C library or a command-line tool, rather than being limited just to specifying packages written for your particular language.

However, of course, it does come with some drawbacks. Among them is the requirement that you often can't simply use nix out-of-the-box to build your code; depending on how developed the nix ecosystem is for a particular language, you might have to figure out for language X how packages are built, tested, installed, and linked together, and write the appropriate abstractions in nix. It also means that you won't automatically pick up later versions of a dependency when you (re)build it, which means you might miss out on updates. However, this latter drawback is arguably a benefit, because by the same token you won't accidentally pull in regressions due to an update in a dependency.

Re:Thoughts on “Dependency hell is NP-complete” by skrebbel on Saturday December 17, 2016 @03:30AM (#13199877)
I don't understand this. You're saying that the way the dependencies are written down (with code, not declarations) changes the NP-completeness characteristics of dependency resolution.

I strongly doubt that, just like a search in an unindexed database table is O(N) no matter whether you write it as an SQL query or a for loop.

What assumptions about dependencies does Nix make / weaken that makes resolution linear-time? Any of those 4 Russ Cox lists? Or did Nix come up with some genius insight that shows that there's more than 4 core assumptions in the NP Completeness proof and the 5th one is the one that can be safely dropped?

Re:Thoughts on “Dependency hell is NP-complete” by DougBTX on Saturday December 17, 2016 @04:15AM (#13199965)
> > Whatever that variable resolves to

The "fifth" or perhaps "zeroth" assumption is that the versions of all the dependencies must be resolved by a single system. If the developer does half the work by e.g., defining explicitly what flask is, then the remaining part of the system won't have to be NP complete any more.

I think that's what the parent post means by "won't automatically pick up later versions of a dependency". Since it isn't doing full dependency resolution, it doesn't need to solve the whole problem, but also doesn't give all the benefits.

Re:Thoughts on “Dependency hell is NP-complete” by smallnamespace on Saturday December 17, 2016 @12:51PM (#13201599)
Even though the developer does half the work, the system of 'Nix-using developer + Nix' is still constrained by NP-completeness, so in practice the two combined will not be able to solve the 'dependency resolution problem' in its full generality without a potentially exponential search.

So the real question is, which assumption does the package of 'Nix-using developer + Nix' give up?

Re:Thoughts on “Dependency hell is NP-complete” by cwp on Saturday December 17, 2016 @01:34PM (#13201772)
It violates assumption #4. With nix, you can have multiple versions of a package installed.
Re:Thoughts on “Dependency hell is NP-complete” by Zalastax on Saturday December 17, 2016 @08:19AM (#13200603)
As far as I can tell Nix doesn't do dependency resolution at all [1]. Hard linking every dependency is a solution but is undecireable for most systems. I don't want to specify versions for sub-dependencies so I want them to be automatic and we have the NP-problem again. It might be a smaller set of possibilities if most versions are pinned but it's still NP. [1]: https://medium.com/@charlesstrahan/as-a-nix-nixpkgs-nixos-co...
Re:Thoughts on “Dependency hell is NP-complete” by cwp on Saturday December 17, 2016 @01:04PM (#13201643)
If by "dependency resolution" you mean solving the SAT-equivalent constraint problem the article talks about, then yes, Nix does not do that.

But, it does solve the simpler problem of installing a package along with the all of its transitive dependencies. Nix packages specify the exact version of each package it depends on, so you never have to recursively specify sub-dependencies. Installation is just a matter of walking an acyclic graph. It's not NP complete.

Re:Thoughts on “Dependency hell is NP-complete” by zzzcpan on Saturday December 17, 2016 @01:35PM (#13201781)
Actually, his 4th assumption is somewhat broken. A package manager that does automatic upgrades can choose to upgrade all affected packages as a some sort of transaction always keeping a single version and all dependencies resolved without an NP problem.
Re:Thoughts on “Dependency hell is NP-complete” by digi_owl on Saturday December 17, 2016 @09:29AM (#13200821)
I would have figured that a bigger strength of Nix in all this is that it does not have assumption 4. With Nix you can have any number of variants of a dependency installed, and each package will find the one it needs.
Re:Thoughts on “Dependency hell is NP-complete” by cwp on Saturday December 17, 2016 @12:54PM (#13201611)
Yes. Exactly right.