So now I have a new question: how do RPM-based distros manage without this feature.
I don't use RPM distributions, so I can't answer that question. In Debian, we've gotten along fine for a long time without a complete resolver [0] (the resolvers most users use are still incomplete) because the problem is so easy. The situations users usually run into can be solved with a greedy algorithm like your initial suggestion; with a few extra heuristics you can cover many other typical scenarios (such as the one I posted above). When users hit a situation that it can't solve, they either add instructions to force a resolution, or they ask for help on a mailing list and someone tells them how to add instructions that force a resolution.:-) I presume that users of RPM distributions do something similar.
The main impetus behind the aptitude resolver was that I wanted to improve the UI by providing user-visible explanations for the resolver's decisions and by allowing users to interactively guide the resolver towards a solution (for instance, by telling it that they don't want it to install a particular package version). I also wanted to add support for installing versions other than the current "candidate" [1]. That I could make it complete at the same time was the icing on the cake. (but some very useful icing for people who have complicated dependency situations!)
Daniel
[0] "complete" here means "able to find any solution to a dependency problem". Actually, aptitude only guarantees that it will find minimal solutions, but that's what you want (if "install A" solves a dependency problem, it's possible that "install A and install B" also does; aptitude might return both of these or only the smaller one -- ideally it would only ever return the smaller one, but I wasn't able to find a technique that would quickly minimize solutions).
[1] An apt term: the candidate version of a package is the version that apt will select to install if it's told to install that package. If versions 1, 2, and 3 of A are available and 2 is the candidate, apt-get install A will install version 2. The standard dependency resolver can't handle situations where a version other than the candidate is needed to resolve a dependency.
You have a later version of B depending on an earlier version of C! How often does that happen?
Not often. I was coming up with a simple and contrived example off the top of my head late at night, and it doesn't look much like what happens in real archives. But, of course, the choices of Cv1 and Cv2 are arbitrary; you could swap them and have the same situation:
A (v1) Depends: B (v1), C (v1) A (v2) Depends: B (v2), C (v1) B (v1) Depends: C (v1) B (v2) Depends: C (v2)
The point is that you have to backtrack to solve this (unless you happen to pick a satisfying solution with your first choice of version for each package), which your pseudocode doesn't do. Even that isn't enough, though:
A (v1) Depends: B (v1), C (v1) A (v2) Depends: B (v1), C (v1) B (v1) Depends: C (v1) B (v2) Depends: C (v2)
If the user asks to install B v2, you have to consider removing A to install it (because Bv2 requires Cv2, and all versions of A need Cv1). Note that the simple approach of walking through the dependencies of B and trying each one won't help here, because it's not a dependency of B that's broken. You need to look at the reverse dependencies of C too, and in a larger archive A might have reverse dependencies that also need to be taken care of once it's removed.
I've written a little bit about some of these issues at http://people.debian.org/~dburrows/model.pdf. You can find a lot of this in a basic AI textbook or in the theory behind constraint solving algorithms too, though; that link just applies some standard techniques to the problem of dependency resolution.
Package dependency resolution is actually NP-complete. The main complication you missed is versioned dependencies -- you have to pick a collection of versions that are consistent with one another. For instance, if packages A, B, and C have versions 1 and 2 each, with
A (v1) Depends: B (v1), C (v2)
A (v2) Depends: B (v2), C (v2)
B (v1) Depends: C (v2)
B (v2) Depends: C (v1)
you need to recognize that the only consistent installation is Av1, Bv1, and Cv2. This example is trivial, but multiply it by about a factor of 10,000 and you get Debian.:-)
I don't know any reason you couldn't try this out, but I don't know enough about the Yum equivalent of Packages files to generate one. Anyone who wants to create a yumsudoku.py is welcome to.:-)
I thought GNUCash had decent features, and happily used it for almost a year. Then an upgrade to either GNUCash or Mandrake (can't remember which now) caused it to crash every time I tried to print something. Having invoices to print monthly, this was a show-stopper, so I switched over to SQL-Ledger.
I would have sworn that somewhere in Episode IV, ObiWan calls Darth Vader, "Darth," as if it's a first name and "Vader" is a last name.
It's in the light-saber battle.
VADER: Your powers are weak, old man. When I met you, I was but the learner; now I am the master. OBI-WAN: Only a master of evil, Darth.
...which, IMO, has to be one of the worst bits of dialogue ever. But anyway, there you are.
I agree with your thesis, by the way; it's quite clear that the whole "Darth is a title" thing was made up after the fact. Probably Lucas just liked the way the name sounded (Dooku anyone?).
If they want money, make a damn release, or die. It's really THAT simple.
While everyone else is yammering about the release schedule, I thought I should point out (shouting into the void though it may be) that nothing in Branden's missive said Debian needs money. While I don't have access to a detailed history of the Project's finances, I would bet we have about as much money as we ever have had.
Debian is just not a cash-intensive operation, because most requirements are filled either by volunteer work or in-kind donations (i.e., donations of hardware and bandwidth).
Believe it or not, it's the truth. See, for instance, the list of hardware donors, official mirror hosts, and partners (companies that have given significant resources to the project). I also know that the conferences have been sponsored by Lindows (excuse me, Linspire), and several prominent developers work for HP, Progeny, and Ubuntu.
It seems to me that even people who aren't very well-paid can have a pretty good standard of living in this country.
Maybe it's been a while since you were in college, but these days, thanks to tuition increases that beat inflation every year for decades, we have a lovely institution known as the "school loan". Basically this means that unless you go to an incredibly cheap school, you get stuck in debt up to your eyebrows when you graduate. After being a graduate student, I think I could probably live comfortably for now on $20k-$30k a year...except that my loan payments would eat up half or more of my paychecks if I did. And that figure is while a lot of them are still in deferment because I'm a student!
I'm rather lucky in that my grandparents put a decent sum of money into a trust to pay my school bills, so I won't be totally screwed if I don't get a high-paying job right after graduation. But if this weren't the case (and I doubt it is for most students) I wouldn't have any choice but to take the most financially rewarding job offer I could get my hands on.
I'd imagine it would also speed up stuff like initializing an array to zero, although I doubt most programs spend a (relatively) large amount of time doing that.
she said and I do qoute... "having to deal with all those advertisments made me feel dirty."
Way too true. I feel like I need a metaphorical shower every time I happen to catch a bit of cable TV. The thought of actually being acclimated to that stuff, to the point of not noticing it -- well, "horrifying" would be an understatement.
Next month, Nasa will launch the £138m Swift probe, which will sweep up to one sixth of the sky at a time, looking for sudden bursts. If all goes well, the probe could catch two three explosions a week.
Did you expect better from Disney? They make kids movies, and the Hitchhiker can't be made into a kids movie. Kids wouldn't appreciate it.
I think it's rather that some adults are afraid kids will appreciate its satirical and slightly cynical look at the world we live in. Disney movies are parent-friendly before they're kid-friendly because, well, guess who pays for them? (see, eg, their sanitizing of fairy tales)
Well, so long as it looked nothing whatsoever like Java -- which I guess would be the case if it met all my criteria -- yes;-). I really like a lot of things about the basic Python syntax, aside from the stuff that makes even a grafted-on static typer impossible (like poking around in the local variable bindings at runtime, for instance); it strikes (IMO) a good balance between being concise and convenient to use while still being clear and unambiguous.
I should admit that the largest Python program I've written so far is about 6k lines, but even there I've run into bugs that would have been caught by a static type system. At that level it's just a nuisance, but my intuition is that it would get worse as the complexity of the code got larger.
That's true, but regardless, this isn't a new issue. I also doubt that it has as much importance as some people think -- I hate writing large programs in dynamically typed languages, but I nonetheless find myself doing a lot of coding in them because of the other features that few statically-typed languages support, like (in rough order of importance):
Reliable, portable, free implementations
Automatic memory management
Large standard and third-party code libraries
First-class functions
Built-in collection types (growable arrays and dictionaries)
Sensible module handling
Streamlined syntax
Macros
Most statically typed languages miss out on one or more of these, and all of them have a much more dramatic impact on how quickly I can get anything done in the language than the lack of static typing does -- static typing doesn't get really useful until you have a big interconnected system (and of course the above properties help keep the size of your own program down by eliminating lots of).
I may spend a lot of time cursing at the lack of static typing, but the fact is that the inconvenience of missing the above features is enough to keep me using Python et al. The most annoying thing is that none of them are particularly tied to dynamic typing, except in the sense that it's simpler to implement a dynamically typed language, because there's a lot of theory involved in type systems (especially if you want to do any sort of inference).
Either Perl regexps are not Turing complete, or Larry Wall has solved the halting problem....or the Perl regexp matcher sometimes goes into infinite loops. (NB: I don't know which of these three is actually the case, except that it's not the second one;-) )
I thought the first two books in the original series were quite good, but the new one...in broad strokes it's interesting, but Card seems to spend half his time setting up straw men of his political opponents so he can knock them down. The earlier books had religious undertones, but they were universal enough that almost anyone (including, eg, the oh-so-dreaded "secular humanists") could appreciate them. In contrast, I get the feeling you have to be a fundamentalist in order to really enjoy the Shadow series (as well as the extra-Ender stuff I've read by Card).
Open source projects are on the whole better, or at least achieve success more quickly on software engineering problems than computer science problems.
Of course, exactly the same is true of any other type of software project;-).
Slashdot Mirror
So now I have a new question: how do RPM-based distros manage without this feature.
I don't use RPM distributions, so I can't answer that question. In Debian, we've gotten along fine for a long time without a complete resolver [0] (the resolvers most users use are still incomplete) because the problem is so easy. The situations users usually run into can be solved with a greedy algorithm like your initial suggestion; with a few extra heuristics you can cover many other typical scenarios (such as the one I posted above). When users hit a situation that it can't solve, they either add instructions to force a resolution, or they ask for help on a mailing list and someone tells them how to add instructions that force a resolution. :-) I presume that users of RPM distributions do something similar.
The main impetus behind the aptitude resolver was that I wanted to improve the UI by providing user-visible explanations for the resolver's decisions and by allowing users to interactively guide the resolver towards a solution (for instance, by telling it that they don't want it to install a particular package version). I also wanted to add support for installing versions other than the current "candidate" [1]. That I could make it complete at the same time was the icing on the cake. (but some very useful icing for people who have complicated dependency situations!)
Daniel
[0] "complete" here means "able to find any solution to a dependency problem". Actually, aptitude only guarantees that it will find minimal solutions, but that's what you want (if "install A" solves a dependency problem, it's possible that "install A and install B" also does; aptitude might return both of these or only the smaller one -- ideally it would only ever return the smaller one, but I wasn't able to find a technique that would quickly minimize solutions).
[1] An apt term: the candidate version of a package is the version that apt will select to install if it's told to install that package. If versions 1, 2, and 3 of A are available and 2 is the candidate, apt-get install A will install version 2. The standard dependency resolver can't handle situations where a version other than the candidate is needed to resolve a dependency.
B (v1) Depends: C (v2)
B (v2) Depends: C (v1)
You have a later version of B depending on an earlier version of C! How often does that happen?
Not often. I was coming up with a simple and contrived example off the top of my head late at night, and it doesn't look much like what happens in real archives. But, of course, the choices of Cv1 and Cv2 are arbitrary; you could swap them and have the same situation:
A (v1) Depends: B (v1), C (v1)
A (v2) Depends: B (v2), C (v1)
B (v1) Depends: C (v1)
B (v2) Depends: C (v2)
The point is that you have to backtrack to solve this (unless you happen to pick a satisfying solution with your first choice of version for each package), which your pseudocode doesn't do. Even that isn't enough, though:
A (v1) Depends: B (v1), C (v1)
A (v2) Depends: B (v1), C (v1)
B (v1) Depends: C (v1)
B (v2) Depends: C (v2)
If the user asks to install B v2, you have to consider removing A to install it (because Bv2 requires Cv2, and all versions of A need Cv1). Note that the simple approach of walking through the dependencies of B and trying each one won't help here, because it's not a dependency of B that's broken. You need to look at the reverse dependencies of C too, and in a larger archive A might have reverse dependencies that also need to be taken care of once it's removed.
I've written a little bit about some of these issues at http://people.debian.org/~dburrows/model.pdf. You can find a lot of this in a basic AI textbook or in the theory behind constraint solving algorithms too, though; that link just applies some standard techniques to the problem of dependency resolution.
Daniel
Package dependency resolution is actually NP-complete. The main complication you missed is versioned dependencies -- you have to pick a collection of versions that are consistent with one another. For instance, if packages A, B, and C have versions 1 and 2 each, with
A (v1) Depends: B (v1), C (v2)
A (v2) Depends: B (v2), C (v2)
B (v1) Depends: C (v2)
B (v2) Depends: C (v1)
you need to recognize that the only consistent installation is Av1, Bv1, and Cv2. This example is trivial, but multiply it by about a factor of 10,000 and you get Debian. :-)
Daniel
I don't know any reason you couldn't try this out, but I don't know enough about the Yum equivalent of Packages files to generate one. Anyone who wants to create a yumsudoku.py is welcome to. :-)
Daniel
I thought GNUCash had decent features, and happily used it for almost a year. Then an upgrade to either GNUCash or Mandrake (can't remember which now) caused it to crash every time I tried to print something. Having invoices to print monthly, this was a show-stopper, so I switched over to SQL-Ledger.
I wonder if this could be Debian bug #347390?
Daniel
It's in the light-saber battle.
VADER: Your powers are weak, old man. When I met you, I was but the learner; now I am the master.
OBI-WAN: Only a master of evil, Darth.
I agree with your thesis, by the way; it's quite clear that the whole "Darth is a title" thing was made up after the fact. Probably Lucas just liked the way the name sounded (Dooku anyone?).
Daniel
Unfortunately, there is no "undo" command
Yes, there is.
the only way of resetting aptitude seems to be to apt-get --purge and then reinstall it.
You can also execute the "keep" command to clear the actions that have been set on a bunch of packages, but I believe that's not available in woody.
Daniel
Darnit, I knew I'd regret finally finishing my thesis and graduating...
Daniel
Yes, because my machines boot real well over HTTP.
Daniel
I don't know about security, but I can think of some good reasons to spread Debian machines and other assets around.
Daniel
If they want money, make a damn release, or die. It's really THAT simple.
While everyone else is yammering about the release schedule, I thought I should point out (shouting into the void though it may be) that nothing in Branden's missive said Debian needs money. While I don't have access to a detailed history of the Project's finances, I would bet we have about as much money as we ever have had.
Debian is just not a cash-intensive operation, because most requirements are filled either by volunteer work or in-kind donations (i.e., donations of hardware and bandwidth).
Daniel
The difference is, Microsoft HAS made several releases since 1998. Debian hasn't.
Actually, Debian has made several releases since 1998. Hamm was released in 1998, slink in 1999, potato in 2000, and woody in 2002.
Daniel
Believe it or not, it's the truth. See, for instance, the list of hardware donors, official mirror hosts, and partners (companies that have given significant resources to the project). I also know that the conferences have been sponsored by Lindows (excuse me, Linspire), and several prominent developers work for HP, Progeny, and Ubuntu.
Daniel
It seems to me that even people who aren't very well-paid can have a pretty good standard of living in this country.
Maybe it's been a while since you were in college, but these days, thanks to tuition increases that beat inflation every year for decades, we have a lovely institution known as the "school loan". Basically this means that unless you go to an incredibly cheap school, you get stuck in debt up to your eyebrows when you graduate. After being a graduate student, I think I could probably live comfortably for now on $20k-$30k a year...except that my loan payments would eat up half or more of my paychecks if I did. And that figure is while a lot of them are still in deferment because I'm a student!
I'm rather lucky in that my grandparents put a decent sum of money into a trust to pay my school bills, so I won't be totally screwed if I don't get a high-paying job right after graduation. But if this weren't the case (and I doubt it is for most students) I wouldn't have any choice but to take the most financially rewarding job offer I could get my hands on.
Daniel
I'd imagine it would also speed up stuff like initializing an array to zero, although I doubt most programs spend a (relatively) large amount of time doing that.
Daniel
she said and I do qoute... "having to deal with all those advertisments made me feel dirty."
Way too true. I feel like I need a metaphorical shower every time I happen to catch a bit of cable TV. The thought of actually being acclimated to that stuff, to the point of not noticing it -- well, "horrifying" would be an understatement.
Daniel
Not to mention that
Next month, Nasa will launch the £138m Swift probe, which will sweep up to one sixth of the sky at a time, looking for sudden bursts. If all goes well, the probe could catch two three explosions a week.
Swift launched last November!
Daniel
Did you expect better from Disney? They make kids movies, and the Hitchhiker can't be made into a kids movie. Kids wouldn't appreciate it.
I think it's rather that some adults are afraid kids will appreciate its satirical and slightly cynical look at the world we live in. Disney movies are parent-friendly before they're kid-friendly because, well, guess who pays for them? (see, eg, their sanitizing of fairy tales)
Daniel
If joeyh's comments are anything like right, I'm not surprised. Something about people who do not learn from history comes to mind...
Daniel
Well, so long as it looked nothing whatsoever like Java -- which I guess would be the case if it met all my criteria -- yes ;-). I really like a lot of things about the basic Python syntax, aside from the stuff that makes even a grafted-on static typer impossible (like poking around in the local variable bindings at runtime, for instance); it strikes (IMO) a good balance between being concise and convenient to use while still being clear and unambiguous.
I should admit that the largest Python program I've written so far is about 6k lines, but even there I've run into bugs that would have been caught by a static type system. At that level it's just a nuisance, but my intuition is that it would get worse as the complexity of the code got larger.
Daniel
Most statically typed languages miss out on one or more of these, and all of them have a much more dramatic impact on how quickly I can get anything done in the language than the lack of static typing does -- static typing doesn't get really useful until you have a big interconnected system (and of course the above properties help keep the size of your own program down by eliminating lots of).
I may spend a lot of time cursing at the lack of static typing, but the fact is that the inconvenience of missing the above features is enough to keep me using Python et al. The most annoying thing is that none of them are particularly tied to dynamic typing, except in the sense that it's simpler to implement a dynamically typed language, because there's a lot of theory involved in type systems (especially if you want to do any sort of inference).
Daniel
These two statements encapsulate the received wisdom on the static-vs-dynamic issue. It will take several years to decide the issue.
You say it as if this is a new issue. Have you ever heard of Lisp?
Daniel
Either Perl regexps are not Turing complete, or Larry Wall has solved the halting problem. ...or the Perl regexp matcher sometimes goes into infinite loops. (NB: I don't know which of these three is actually the case, except that it's not the second one ;-) )
Daniel
I thought the first two books in the original series were quite good, but the new one...in broad strokes it's interesting, but Card seems to spend half his time setting up straw men of his political opponents so he can knock them down. The earlier books had religious undertones, but they were universal enough that almost anyone (including, eg, the oh-so-dreaded "secular humanists") could appreciate them. In contrast, I get the feeling you have to be a fundamentalist in order to really enjoy the Shadow series (as well as the extra-Ender stuff I've read by Card).
Daniel
Open source projects are on the whole better, or at least achieve success more quickly on software engineering problems than computer science problems.
;-).
Of course, exactly the same is true of any other type of software project
Daniel