Re: APT SAT solvers and stuff [WAS: Re: Bug#683786: apt-get cross build dependency resolution of arch:all, m-a:none packages]
On Mon, Aug 6, 2012 at 2:16 PM, Julian Andres Klode <jak@debian.org> wrote:
> On Mon, Aug 06, 2012 at 01:05:13AM +0200, David Kalnischkies wrote:
>> (We have a big FIXME for this in the build-dep code and I hope to get
>> this code replaced by reusing our "normal" solver more, so this might
>> get better in the future, but probably never really solved until we have
>> a SAT (or its technical superior successor [invented by me] XYZ) solver…)
>
> On the topic of solvers: SAT solvers don't really work. A pure SAT solver
This is what i meant with "technical superior successor XYZ",
the [remark] was just wishful thinking. ;)
RPM-world has many reports about the "better than sliced bread" SAT
solvers they deploy nowadays, but they have different semantics so
I am not convinced their (claimed) success can be mapped one on one
to a DEB environment.
> Furthermore, it seems that libsolv has rudimentary Debian support (by
> parsing sources.list and Packages files itself, and broken support
> for some architectures). I don't know whether it might be worthwhile
> to integrate APT with libsolv (by making libsolv generate its structures
> using the apt-pkg library instead of ad-hoc self-parsing) and use that for
> solving dependencies, and I don't know how it handles unsatisfiable
> Recommends. If it can handle that, and produces good results, it
> might be a good idea to work on this for jessie.
I think our way forward should be exploring the available options like
aspcud by using the external dependency resolver interface.
(buzzwords: EDSP in APT and CUDF)
This is of course far from being speedy compared to an internal
solver in APT but as CUDF is an independent format any package
manager can benefit from this exploration and therefore implementers
can be attracted by the bigger target audience.
(And after all, for many usecases the speed of the resolver can be
ignored as download and installation will take way longer.)
>From my limited personal experience as (undergraduate) research assistant
I can conclude that researchers tend to favor "obscure" languages¹ in the
Lisp or ML family tree rather than "general" languages like C for the first
iteration as these tend to be more managed and therefore easier to use.
So requiring a C implementation or alike just limits us to already well
explored options rather than allowing to test "the next big thing™".
There is no problem in moving from a general-propose solver written in
whitespace talking in CUDF to a optimized reimplementation specifically
made for the needs of the debian world later on if we so desire.
(Beside that I am not completely convinced that there is really a one
size fits all solution to really good package management given that
a solver can have only so many options before you basically develop
a new solver written in a turing-complete configuration file)
Best regards
David Kalnischkies
¹ no offense. I like them and I am paid to write in them,
but I e.g. don't see me writing a low-level package manager in F#.
Reply to: