[Aptitude-devel] external solver support?

[Stefano Zacchiroli]

On Thu, Sep 11, 2008 at 07:58:12AM -0700, Daniel Burrows wrote:
>   Looks like an interesting project.  I do wonder how much work we
> really need on dependency solvers: aptitude's is quite naive, yet it
> solves virtually everything I throw at it in seconds and typically
> produces reasonable results.  The main deficiency I would like to fix
> (but I'm not sure how) is that its answers are not always very
> predictable: from a practical point of view, we would like package
> maintainers to be able to specify things like the default resolution
> of a dependency, and aptitude doesn't have much support for that.  A
> second deficiency is that I would like to be able to partition the
> dependency problem into "independent sub-problems" -- not just
> algorithmically, but also interactively, so that the user can explore
> the individual parts of the problem rather than having to deal with the
> whole thing at once.  That will require a radical change to how the
> resolver is defined and used; again, not really something that you can
> accomplish with a plug-in architecture.  A third issue is that the
> resolver should know about which packages are going to be unused and
> take that into account (that would make it less eager to, e.g., remove
> all of Gnome to solve a dependency).
> 
>   So I guess the first and third points are fixable by dropping new
> solvers in.  The third is a pretty simple matter of finding a
> reasonably efficient way to add a list of unused packages to each
> search node.  Do you have ideas about how to fix the first one without
> compromising speed or quality of results too much?

Not yet, we are still working on the infrastructure to let people with
experience in solving strategies work on it. The biggest deal for us ATM
is closing the gap between "we", Debian people, who have access to a
great deal of complex, real-life dependency solving problems [1] and
"them", SAT and other constraint solving people, who have experience in
solving strategies but have no idea on how to find a corpus of problems
on which start experimenting.

Once we have closed this gap, we will start discussing about algorithms
and strategies.

Yes, the *interactive* UI problem are out of the game for now, but I
can't stop thinking that most of the interactiveness part can be
addressed by a more expressive request language to be fed to the package
manager (think about APT pinning). Having that one can later on hide the
language using an interactive UI, still retaining a simple
non-interactive solver. OK, this can induce duplicated work for the
solver, but one can than cache clauses or stuff like that ...

[1] we have found even simple examples in which all solvers we have in
    Debian fail to find a solution where on exists and can be easily
    found by any SAT solvers

>   In point 4, you mention a tradeoff between efficiency and the search
> for a better solution.  Another tradeoff that you should keep in mind is
> the tradeoff between algorithmic sophistication and comprehensibility.
> That's comprehensibility for external developers (who need a reasonable
> model of how the thing works and what their adjustments of its
> parameters will do), for users (who need to understand why it produced
> the result that it did), and even for internal developers (someday
> someone who doesn't understand what you did will have to maintain your
> code, and it might be you. :-) ).  Along with comprehensibility (but not
> identical to it) is simplicity/robustness -- dragging in a bunch of
> external code-bases (SAT-solvers, theorem provers, etc) seems problematic
> to me.

Well, you are assuming that the solver code is something which requires
active maintenance and I'm not convinced about that. I still hope we can
find *the* good solver and be done with that, but of course I understand
your concern.

> I also heard a rumor at one point that you were considering
> writing solvers in O'Caml, which doesn't seem to me like a viable choice
> for a core system tool.

That's not a big deal, and that's why I would like to have the ability
to invoke _external_ solvers which can be written in whatever language.
If people like to write them in OCaml they can do it, if the algorithm
works nothing inhibit to then implement it in whatever other languages.
Again I've a political point here: if the people working on algorithms
like to program in OCaml I don't want to stop them, I would like to be
able to tell them something like: «go implement this binary API, then we
can try your solver with aptitude».

>   I guess what I'm saying is: I'm happy to pay costs on the simplicity/
> comprehensibility side of the ledger if there's a corresponding benefit.
> I'm somewhat skeptical that there's enough room to get a big benefit from
> purely algorithmic changes, and I'm worried about making apt more
> complicated, particularly given that we already can't find enough people
> to maintain it.  Adding even more complexity invites the Gnucash Syndrome.

The only additional layer I want to add to apt/aptitude is a clear
interface between the package manager and the solver, possibly the
*same* interface for the two. How do you consider this? Would it be an
excessive cost according to your point of view? (OK, it is hard to tell
without having yet the interface, but if yours is a "no-way" it would be
pointless to start thinking about one :-))

>   Er, I hope that doesn't sound too negative.  If I take my apt/aptitude
> maintainer hat off, I'd love to just sit around and play with constraint
> solving algorithms, but as a project maintainer I also have to think
> about what's best for the long-term viability of the codebase.  Maybe

Yes, definitely. But as a project maintainer having a clear-cut
interface like the one I mentioned would be a benefit anyhow, wouldn't
it?

>   I'm curious how you intend to run a competition for upgrade tools.
> In contrast to SAT-solvers and theorem provers, with dependency
> resolvers you have to pick a *good* solution, not just any solution,
> and the really hard thing is that there's no well-defined way to know
> whether one solution is really better than another!  It seems to me
> that this would present a bit of a problem when grading algorithms.

I feel we are getting off-topic here :), but anyhow ...

It is not true that we are already at the point where we only care for
the *good* solution. With our current package managers there are cases
in which solutions exist, but they can't be found by our tools. This is
a first deficiency to be addressed, but is entirely implementative and
not algorithmic.

Then of course we will move to finding the *best* solution, and that
need to be done according to criteria. There are some "reasonable"
criteria one can use by default, like SMART's policies (minimize
download size, consider priority in alternatives, minimize installed
size, ...). In the beginning we will just set some of them.

Then, we would like to move to user-specified optimization criteria. The
idea is to find a small language (like APT pinning, but with a clear
formalization, and with access to package properties) the user can write
down in a configuration file and optimize wrt that. Algorithmically, at
this point you will be leaving plain SAT solving and enter the harder
area of multi-criteria optimization ...

> > Yes, UI is a problem, and of course the problem is whether or not there
> > is an API which will make happy everybody. My idea is to start drafting
> > one that will satisfy aptitude needs and see how flexible we can get it.
> 
>   OK.  I think the first question is, how are you going to actually
> implement a plugin system?  Will you run the resolver in-process as a
> shared object, or via some sort of pipe interface like a download method?

"plugin system" is quite a mouthful :), my goal would be the ability in
apt/aptitude to invoke an *external process* as a solver. The
requirement of the process to be external is on one hand to leverage
implementation of solvers in whatever language, on the other to enable
shipping solvers in Debian packages other than apt/aptitude.

When I initially discussed the issue with Micheal Vogt the idea which
popped up was to use some sort of pipe interface to an external process.
How do you feel about that?

> otherwise I suggest a two-way protocol where the resolver asks for
> information as it needs it (that's on the grounds that it's probably too
> expensive to pass all the state over a pipe and parse it at the other
> end).  For instance: "tell me what's broken", "tell me what I can
> install to resolve this dependency", etc.

Well, at least initially I think the whole state should be passed to the
solver. I've a rough idea that sending that all in a binary format would
be something like 400Kb, it shouldn't be that slow through a pipe (but
more benchmarks are needed of course).

>   Do you want the resolvers to work on the raw apt cache or on a
> simplified model of it?  In aptitude, the code to resolve packages [0]

If possible, I would prefer to work on a simplified model. Ideally, the
interface should not be apt-specific.

>   [0] src/generic/problemresolver/problemresolver.h
>   [1] src/generic/apt/aptitude_resolver_universe.{cc,h}
> 
>   Once I know the general shape of what you're trying to do, I could
> help design an API/ABI that aptitude could use.

Thanks!

>   I would like to reiterate my strong opinion that package dependency
> resolution is not fundamentally an algorithmic problem: it's a UI
> problem with algorithmic elements.  Designing better and better
> algorithms is a worthy goal, but if you take that as your main target,
> you could risk of chasing diminishing algorithmic returns at the expense
> of the overall usefulness of your program.

I fully understand and partially agree. I still believe that UI can be
something written to mask the algorithmic details and to be used to
iteratively create a problem specification. Actually, I've also been
studying various UI/HCI topics, but this it not in the focus of Mancoosi
right now. Of course this doesn't inhibit in addressing the problem from
two sides with people interested in that and finding an useful synergy.

Cheers.

-- 
Stefano Zacchiroli -*- PhD in Computer Science \ PostDoc @ Univ. Paris 7
zack@{upsilon.cc,pps.jussieu.fr,debian.org} -<>- http://upsilon.cc/zack/
I'm still an SGML person,this newfangled /\ All one has to do is hit the
XML stuff is so ... simplistic  -- Manoj \/ right keys at the right time
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://lists.alioth.debian.org/pipermail/aptitude-devel/attachments/20080912/c369714a/attachment.pgp