4 ms·

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; in

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.

skrebbel 10y ago
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?
- DougBTX 10y ago
  > > 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.
  - smallnamespace 10y ago
    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?
    - cwp 10y ago
      It violates assumption #4. With nix, you can have multiple versions of a package installed.
- Zalastax 10y ago
  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-contributor-i-figured-id-clear-up-a-few-things-947f8583217e https://medium.com/@charlesstrahan/as-a-nix-nixpkgs-nixos-co...
  - cwp 10y ago
    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.
digi_owl 10y ago
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.
- cwp 10y ago
  Yes. Exactly right.

skrebbel 10y ago

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?

DougBTX 10y ago
> > 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.
- smallnamespace 10y ago
  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?
  - cwp 10y ago
    It violates assumption #4. With nix, you can have multiple versions of a package installed.
Zalastax 10y ago
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-contributor-i-figured-id-clear-up-a-few-things-947f8583217e https://medium.com/@charlesstrahan/as-a-nix-nixpkgs-nixos-co...
- cwp 10y ago
  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.

digi_owl 10y ago

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.

cwp 10y ago
Yes. Exactly right.