[darcs-devel] Re: patch domains idea

[David Roundy]

On Sat, Jan 29, 2005 at 08:03:54AM +0000, Aaron Denney wrote:
> On 2005-01-27, David Roundy <droundy at abridgegame.org> wrote:
> > The idea is called "patch domains".  A patch domain is a description of
> > "what a patch acts on".  Like the concept of "patches" and "trees" in
> > the existing patch theory, a "domain" is an abstract concept, but with
> > reasonably strict laws governing the behavior of any implementation.
> 
> Neat, and quite possibly workable.  I'm somewhat dubious about how much
> they'll actually help though -- they'll grow and interact through use and
> have the same high time behaviour.  As I see it, it's just a means of
> "chunking" so that there are fewer things in that behaviour.

The advantage comes that you can use this (with sufficiently clever
algorithms) to get O(nlogn) commutation.  Nothing I presented included such
clever algorithms, but they could certainly be developed.  Without the
domain concept, it's not possible to avoid O(n^2) commutation (of two
patches of n primitive patches each).

> > 3. extendDomain :: Patch -> Domain -> Domain
> >
> > This extends a Domain by "applying" a patch, so
> >
> > domainOf (ComP (p:ps)) = dof (reverse ps) (domainOf p)
> >   where dof [] d = d
> >         dof (x:xs) d = dof xs (x `extendDomain` d)
> 
> Wouldn't Domain -> Patch -> Domain be easier for folding?
> Well, foldr, I guess.  I find using a strict foldl more natural
> though.

Either way.  I'm not a particularly proficient folder.  I store my clean
clothes in a hamper rather than fold them.

> > I think one could work out a set of efficient commutation algorithms
> > which would actually be independent of the actual choice of domains.
> 
> Choice of domains or representation (type) of domains?  I'm not
> sure I'd fully believe either, having run across so many situations
> where the choice of basis made a great difference.

The choice of domains (that is, of the definition of domains) will make a
difference in the efficiency gained, but can't make a difference in the
final answer--unless of course you have a buggy domain implementation.

> > Obviously there is the trivial "domain space" in which all domains
> > intersect, which obeys all these laws.  For debugging purposes, an
> > implemntation with "pluggable domains" might be a good idea.  Then one
> > could experiment with different domain realizations with the same set of
> > unit tests.  e.g. perhaps for seriously large trees one might want to
> > truncate the filepaths after two or three nested directories.
> 
> Hence reducing the number of domains.  Hmm.

Interestingly, I just thought of the other limiting choice for a space of
domains, and that is the spaces of patches themselves. :) (extendDomain is
just patch composition, and domainOf is identity, etc...) That's obviously
the finest granularity that a domain can have... and would be a good
easy-to-implement test case for testing the unit tests themselves.
-- 
David Roundy
http://www.darcs.net