Michi’s blog » Blog Archive » PROPs and patches

PROPs and patches

February 15th, 2008

Brent Yorgey wrote a post on using category theory to formalize patch theory. In the middle of it, he talks about the need to commute a patch to the end of a patch series, in order to apply a patch undoing it. He suggests a necessary condition to do this is that, given patches P and Q, we need to be able to find patches Q’ and P’ such that PQ=Q’P', and preferably such that Q’ and P’ capture some of the info in P and Q.

However, as such, this is not enough to solve the issue. For one thing, we can set Q’=P and P’=Q, and things are the way he asks for.

Now, I wonder whether we can solve this by using PROPs (or possibly di-operads or something like that). Let’s represent a document as a list of some sort of tokens. We’ll set D_n the set of all lists of length , and we’ll set P_n^m to denote operations that take a list of length n and returns a list of length m.

One operation here is obvious – the identity operation. So we’ll take that into the mix. And we’ll also want to have some manner of composing operations. So, set $\circ_i:P_n^m\times P_r^s\to P_n^{m+s-r}$ to be the operation that applies the second argument to the elements i,i+1,…,i+m of the list outputted by the first argument.

This way, we can make patch trees – using the identities to fill out when a patch doesn’t influence everything; and have composition of operations represent composition of patches.

Now, the commutativity that Brent asks for would manifest as an additional relation – on top of those inherent in the definition of a PROP – to rebuild trees. One obvious one pops out immediately – as long as the trees don’t overlap, in other words, as long as the subtree we want to reorganize is contractible (in the topological sense), we can commute patches freely.

When trees -do- overlap, however, the undo operation Brent asks for is much more tricky. Consider the following sequence of edits:

[] -> [a] -> [b] -> [cbd]

Now, undo the insertion of [a].

Sure, taken this way, we cheat a little. Maybe we want to restrict edit descriptions to explicit deletions and additions. So we would have

[] -> [a] -> [] -> [b] -> [cb] -> [cbd]

and here we could probably move things around a bit easier. I don’t quite see how to do it, right now, though.

2 People had this to say...

wren Said...

I think this highlights the point of the problem. What does it mean to undo []->[a] without also undoing [a]->[] ?

That is, perhaps the proper way to think about things is not in terms of insertions and deletions to a constant state, but rather to think in terms of reachability on a graph of edits. Thus, we have a graph from nil with a cycle to [a] and back before moving on to [b] and so forth. Now what does it mean to “remove [a]“? Rather than thinking of it as removing the arc from nil to [a], think of it as removing the [a] node itself.

Alternatively, consider the process of pushing A to the end of AA^-1BCD. Since AA^-1 = [], then AA^-1 = A^-1′A’ implies A^-1′A’ = []. There’s an abstruse study of strings with these sorts of “negative” letters in mathematics, though I forget the name it goes by.

February 16th, 2008 at 3:41

Michi Said...

wren: It sounds like you’re talking about combinatorial group theory – where you study groups as given by finite presentation, and where string rewriting systems and rules for precisely manipulation of strings of symbols representing group generators are the tools of the trade.

However, Brent does have a good point when he says that we’ll probably want to work in a groupoid and not a group with these operations; since a patch A describing the change from P to Q won’t be applicable unless the state we’re in IS P.

February 16th, 2008 at 10:30

Want your say?

post navigation

about: Michi is a recent PhD working in homological algebra and applied algebraic topology. This blog is his outlet for texts with some manner of thought put into them. Over at his LiveJournal intimate details and streams of consciousness might be found.
Not all here is mathematics. All here, though, are my personal thoughts and opinions. Please read the about page (linked above) for more details.
This blog uses statcounter.com for logging and traffic analysis. In order to identify return visitors, this site will issue a cookie on viewing the blog.

Travel plans

Recent Comments

Tags: MATH198

Categories

Blogroll

Family

Mathematician blogs

Archives