1 |
I'll answer this one as this seems a bit more substantial and I would really |
2 |
like to keep the discussion on this list. |
3 |
|
4 |
On Friday 05 December 2003 04:26, Paul de Vrieze wrote: |
5 |
> Prolog != AI |
6 |
> AI != undeterministic |
7 |
Quite often these are synonimous (or were, when I was looking into this. But I |
8 |
must admit this was quite some time ago), but strictly speaking you are |
9 |
right. I'll update that section of the page. |
10 |
|
11 |
> prolog is very good at graph traversal tasks (which is what AI in many |
12 |
> cases involves and why in AI prolog is used a lot) as the mode of operation |
13 |
> is basically a depth-first backtracking search algorithm (about 10 lines of |
14 |
> pseudocode). For that reason I think it is a good candidate for the new and |
15 |
> improved dependency algorithm. |
16 |
Shouldn't it be breadth-first? With depth first you might need to do |
17 |
adjustments to the formed list occasionally, if multiple nodes go to the same |
18 |
dependency in a different number of steps. I think I was able to produce the |
19 |
example of such situation, but I would appreciate any good pointers to a |
20 |
theory :). |
21 |
|
22 |
As fot the lines of code, that's anecdotal. |
23 |
(adding from the other email:) |
24 |
> Also, your code (which is about 1000 lines long) |
25 |
> does -only- a simple dfs and topological ordering, while I can do the |
26 |
> same in about 10 lines in prolog and have backtracking for free. I |
27 |
|
28 |
The *traversal* code (btw I use BFS traversal there, not DFS) is completely |
29 |
localized in bc-graphs-directed-bfs_traverse.adb and is about the same 10 |
30 |
lines :) and is completely generic. |
31 |
The rest of 990 lines deal with such mundane tasks as reading the (possibly |
32 |
misformed) ebuilds and dealing with user (inluding minimalistic help). |
33 |
Essentially just doing what you describe here: |
34 |
|
35 |
> While prolog is very good for such tasks I don't think it is suited to |
36 |
> implement the core of portage. This is not because I think prolog is a |
37 |
> problem, it is because I think that such languages are not suited for |
38 |
> procedural dispatch, divide, etc. tasks. That is something that C is good |
39 |
|
40 |
|
41 |
> Then about caching |
42 |
Well, I stated in the writeup that this is a simplistic design only relevant |
43 |
for the prototype. However I'll try to explain my reasoning for the future |
44 |
discussions. |
45 |
(To drobbins: yes, I am afraid we are pulling the "discussion before |
46 |
requirements" thing again here. But this it the core and unavoidable part of |
47 |
the design, so it will definitely be there. Also I am trying to localize the |
48 |
discussion to this list only). |
49 |
|
50 |
Thus note, all the comments below concern this hypothetical design I used in |
51 |
language demonstration, but that will probably be rethought for the real |
52 |
design. |
53 |
|
54 |
> While you have a point with your prediction on number of packages, most of |
55 |
> those packages involve leaf packages. That means that the number of |
56 |
> dependencies per leaf package will probably not increase. However the |
57 |
> amount of packages totally not regarded will grow. For this portage should |
58 |
> do some kind of on-demand loading of packages. I see no need whatsoever to |
59 |
> have a normal emerge task load in the whole tree and create a graph of |
60 |
> that. |
61 |
I somewhat agree with that. However my observation is that these packages most |
62 |
often are libraries or other helpers that user is usualy not interested in |
63 |
directly. And the long operations are the ones where you have to do searches |
64 |
or operations involving world. So I have been thinking along the lines of |
65 |
making the longest operations fast and bounded, getting the O(1) |
66 |
responsivity. |
67 |
But in reality I do not think this shpould be "the ultimate solution" or even |
68 |
that there should be one. See the next one. |
69 |
|
70 |
> I would like portage to remain lean and mean. I do run gentoo on a 16MB |
71 |
> 60mhz pentium, and I like it. While the cache should also be a module that |
72 |
> replaces a direct-tree-read module (possibly wrapping it), I think that |
73 |
> caching should be possible on a configurable level. Not just dumbly load in |
74 |
> all ebuilds. |
75 |
Touche :). |
76 |
That's why I spent so many words discussing memory layout. |
77 |
However the real solution IMHO should allow multiple dependency trackers |
78 |
(cores) to be plugged as desired (choice of both at compilation and run-time |
79 |
(i.e. choosing at compilation to be able to choose at run time :))). And for |
80 |
that we would need a high level of efficient abstraction. And this is what |
81 |
got me started thinking about Ada :). |
82 |
|
83 |
|
84 |
And finally: |
85 |
> My biggest concern when reading your small paper is that you chose a |
86 |
> deterministic approach to this problem, while in fact the problem is |
87 |
> non-determinisitic. |
88 |
Could you please elaborate? I am afraid we are thinking about slightly |
89 |
different things here. |
90 |
|
91 |
I stay by my thought that any important to the system tool should be dumb. If |
92 |
there is any uncertainty it should stop and ask, unless it was designed for a |
93 |
very specific situation, where it can be trusted to make the choice. Package |
94 |
maintaince is not such area - IMHO every user that has identical |
95 |
configuration should get identical results (to the extent possible. So here |
96 |
we are talking requirements Daniel ;)). Otherwise we are facing a disasterous |
97 |
consequencies wil many people complaining and us being unable to reproduce |
98 |
anything reliably. |
99 |
|
100 |
George |
101 |
|
102 |
|
103 |
|
104 |
-- |
105 |
gentoo-portage-dev@g.o mailing list |