On Fri, Sep 19, 2008 at 07:19:15AM -0700, Daniel Burrows wrote: > > [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 > Really? The only cases I'm aware of that occur in the wild are things > like the bug that was recently reported against apt, which involve a full > system upgrade with lots of complicated dependencies.
Yup, but I wasn't the guy doing the tests and I don't know if the reason you mention or not. I'll look for the actual examples and forward them. > > 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». > > Mhm. I don't see a problem with enabling this, but someone should > rewrite the solver in C++ if you want it included in apt (at least, > that's my opinion). This isn't so much a technical objection (although Yes, OK, no problem. These, and related concerns, are typical project management / software engineering problem, we will think about them once we have something working :) > > 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 :-)) > > I don't see a problem with having this sort of an interface present. > I just want to make sure you're aware of the problems before you run up > against them. :-) ACK. > > 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 ... > > But dependency resolution is *inherently* about multi-criteria > optimization. Throwing a SAT solver at the problem, if they aren't > rigged for this sort of thing (and I don't know if they are as I haven't > used them myself) is probably not going to produce terribly good results. Not really. It is true that plain SAT solving is quite pointless for dependency resolution *on a user machine* (you have no guarantee of the minimality of the found solution, but we really don't want to install half of the archive of extra packages when the user request was just one package). But it is not necessarily pointless for other needs of dependency resolutions. A good, and used, example of that is the EDOS tools we are using within Debian QA. They use SAT solving to discover that it is possible, in some way, to install a given package, so this package is worth to be shipped in the Debian archive. If there is no way whatever to install a given package, it is probably not worth to distribute it at all. So, some instances of dependency resolution problems can properly be addressed also by plain SAT solving, but I understand your point of view: on the package manager side you always have something to optimize, at least minimality of what you add to the system. The game starts to be interesting adding more criteria of course ... (e.g., the policies implemented in the SMART package manager). > > "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. > > You can probably base it on the protocol used to communicate with > download helpers. OK, even though that protocols are plain text, right? Or there are some cases in which binary data are passed directly to apt? ... well, never mind, I'll need to have a look at that code anyhow. > > 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). > > Hm, I suppose. The binary format is going to be harder to debug, but > I guess it should be pretty stable. ACK. > > If possible, I would prefer to work on a simplified model. Ideally, the > > interface should not be apt-specific. > > Have I pointed you at my little write-up of aptitude's model yet? > http://people.debian.org/~dburrows/model.pdf > Nothing very exciting, but it might give you some ideas. Nope, I wasn't aware of it, I'll have a look. In exchange, I have to point you to the EDOS dependency model: http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/edos-ase06.pdf . At first sight of your work, this EDOS paper makes not attempt to discuss algorithms (for example the optimizations implemented by edos-{deb,rpm}check are not discussed}, but it does illustrate the dependency model we have used thus far. Cheers. -- Stefano Zacchiroli -*- PhD in Computer Science \ PostDoc @ Univ. Paris 7 [EMAIL PROTECTED],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
signature.asc
Description: Digital signature
_______________________________________________ Aptitude-devel mailing list [email protected] http://lists.alioth.debian.org/mailman/listinfo/aptitude-devel
