3 ms·

I was also originally surprised to realize that this problem is NP-hard. It makes sense though: it involves both universal (for all requirements & dependencies)

I was also originally surprised to realize that this problem is NP-hard. It makes sense though: it involves both universal (for all requirements & dependencies) and existential (there exist packages & versions) quantifiers. Julia's package manager [1] actually uses a custom belief propagation algorithm [2] to find an optimal set of package versions to satisfy given requirements. Originally it used linear programming, but belief propagation is much more efficient and solves the problem optimally in all realistic cases we've tested it on. Using a SAT solver would be another approach, but there is still the issue that you don't just want to find one satisfactory solution, but the optimal one with the freshest versions of the least number of packages. Since SAT isn't an optimization problem, it doesn't give you that. [1] http://docs.julialang.org/en/latest/manual/packages/ http://docs.julialang.org/en/latest/manual/packages/ [2] http://en.wikipedia.org/wiki/Belief_propagation http://en.wikipedia.org/wiki/Belief_propagation

chubot 12y ago
Wow! This looks amazing. I have been working on productionization of R code, i.e. allowing people to ship their prototypes instead of rewriting algorithms in another language, so I am very interested in this problem. I have also looked at lot at R's metadata format (CRAN), which, like Debian/Ubuntu, is very successful, despite being unsound. It looks like METADATA.jl is versioned, while R punts on that... the version constraints in the "head" PACKAGES file are mutated regularly and it becomes impossible to install older versions of packages with correct dependencies. This is not only bad for productionization, but for reproducible science (related: http://arxiv.org/abs/1303.2140 http://arxiv.org/abs/1303.2140). I noticed in the docs there is a local package dir like: "/Users/stefan/.julia/v0.3". If this is settable for individual Julia processes rather than being a system-wide global, then I will be very happy :) Pretty much all language-specific package managers started out with this as a global, and then as they evolved to "production quality", there were some truly horrible hacks layered on top: Python's virtualenv, Ruby's bundler, R devtools, etc. I was a little skeptical about Julia at first (mainly the "one language for everything" philosophy), but I have seen lots of very impressive stuff so far. This is definitely worthy of more attention/exposition, since it will be probably the first "principled" package manager in wide/"practical" use.
- StefanKarpinski 12y ago
  > I noticed in the docs there is a local package dir like: "/Users/stefan/.julia/v0.3". If this is settable for individual Julia processes rather than being a system-wide global, then I will be very happy :) It's controllable via the JULIA_PKGDIR environment variable, so yes, it can easily be per-process; you can also easily change it while a process is running, which allows you to do operations on multiple different package directories. > I was a little skeptical about Julia at first (mainly the "one language for everything" philosophy), but I have seen lots of very impressive stuff so far. There's a subtlety to this philosophy: it's intended to be a language in which you can do everything, not in which you must do everything. It's very easy to call C, Fortran and Python from Julia.

chubot 12y ago

Wow! This looks amazing. I have been working on productionization of R code, i.e. allowing people to ship their prototypes instead of rewriting algorithms in another language, so I am very interested in this problem. I have also looked at lot at R's metadata format (CRAN), which, like Debian/Ubuntu, is very successful, despite being unsound. It looks like METADATA.jl is versioned, while R punts on that... the version constraints in the "head" PACKAGES file are mutated regularly and it becomes impossible to install older versions of packages with correct dependencies. This is not only bad for productionization, but for reproducible science (related: http://arxiv.org/abs/1303.2140 http://arxiv.org/abs/1303.2140). I noticed in the docs there is a local package dir like: "/Users/stefan/.julia/v0.3". If this is settable for individual Julia processes rather than being a system-wide global, then I will be very happy :) Pretty much all language-specific package managers started out with this as a global, and then as they evolved to "production quality", there were some truly horrible hacks layered on top: Python's virtualenv, Ruby's bundler, R devtools, etc. I was a little skeptical about Julia at first (mainly the "one language for everything" philosophy), but I have seen lots of very impressive stuff so far. This is definitely worthy of more attention/exposition, since it will be probably the first "principled" package manager in wide/"practical" use.

StefanKarpinski 12y ago
> I noticed in the docs there is a local package dir like: "/Users/stefan/.julia/v0.3". If this is settable for individual Julia processes rather than being a system-wide global, then I will be very happy :) It's controllable via the JULIA_PKGDIR environment variable, so yes, it can easily be per-process; you can also easily change it while a process is running, which allows you to do operations on multiple different package directories. > I was a little skeptical about Julia at first (mainly the "one language for everything" philosophy), but I have seen lots of very impressive stuff so far. There's a subtlety to this philosophy: it's intended to be a language in which you can do everything, not in which you must do everything. It's very easy to call C, Fortran and Python from Julia.