Re: Algebraic manipulation of patches vs. dependencies

Mark Seaborn wrote:
> I've been trying out Darcs recently, finding it useful, and trying to
> understand how it works.
>
> What puzzles me is that Darcs does not store a dependency graph of all
> the patches in a repository.  Instead it keeps patches in a list, and
> manipulates the list algebraically, reordering patches that commute.
> When two patches modifying the same file are reordered, the line
> numbers they refer to must be rewritten.  In some cases, Darcs groups
> together patches that can be applied in parallel.
>
> Is there any reason why Darcs doesn't go a step further by storing a
> full dependency tree?  This would have the advantage of being a
> canonical representation.  Patches' line numbers would not need to be
> rewritten according to where the patch appears in the sequence.  The
> line numbers of a patch could be given relative to the file contents
> defined by all the patches it depends on.

Mark Seaborn:

I think this is an excellent question.  The major jumping off point that 
separates darcs from my own personal vaporous idle thought experiment of 
a tool (which is named "zxc") is that in my tool dependencies are 
explicitly calculated (greedily) and explicitly stored (persistently).

I do not know for sure, but I harbor the suspicion that the reason darcs 
does otherwise is that Haskell programmers (like many smart programmers) 
are enamoured of timeless, lazy, declarative, mathematical algorithms. 
Therefore, they naturally think of writing a purely functional algorithm 
which evaluates to the right result, and that they naturally don't think 
of algorithms which are imperative and which explicitly and greedily 
store intermediate results to disk.

Regards,

Zooko