14
$\begingroup$

Is there a category of patches that looks roughly like this:

  • The objects are strings in some base alphabet
  • The morphisms are edit scripts ("diffs" or "patches") between the strings

I'm interested in these questions:

  • Is there a categorical notion of minimal edit script? Maybe the category of patches is enriched in PO-Sets?
  • Is merging of patches the categorical pushout?
  • How to generalise this from strings to trees (a file system, or an algebraic datatype)?
$\endgroup$
2
  • 1
    $\begingroup$ You will want to have a look at the theory behind the Darcs VCS $\endgroup$
    – Bergi
    Jul 6, 2019 at 20:02
  • 1
    $\begingroup$ ...or Pijul, a relatively recent attempt to create a "newer Darcs". (And as far as I remember from that talk, merging is the pushout in a "free completion" of the diff category...). $\endgroup$ Jul 7, 2019 at 7:05

2 Answers 2

13
$\begingroup$

As pointed by Martin, there is some work on the categorical representation of patches. Mimram and Di Giusto's "A Categorical Theory of Patches" being the most extensive categorical approach to edit-scripts as used by the UNIX diff.

In their sense, you have what you want. The objects are finite sequences of words over an alphabet $L$, seen as a mapping $A : [n] \rightarrow L$, where $[n]$ denotes the set with $n$ elements. An arrow between $A : [n] \rightarrow L$ and $B : [m] \rightarrow L$ is an injective partial increasing mapping $f : [n] \rightarrow [m]$. Injectivity and increasing are there to indicate that copies never cross over each other. You can find all the details on the paper.

Yes, merging is seen as the pushout on the free cocompletion of the above category. We need the cocompletion to make sure we add merge conflicts to our construction. It is not the case that a merge always exists.

Onto your second question, there is no categorical notion of minimal edit script for two main reasons.

  1. Edit-scripts come in all shapes and forms. Some authors consider insertions, deletions and copies, some authors like to add substitutions as an operation too. When you generalize from strings to trees, then, a plethora of other operations become feasible.

  2. More importantly, though, minimal-cost edit-scripts are not unique. Take the file $ab$, and write a patch that transforms it into $ba$. What is the minimal edit script that does this? There are two! Once again, when generalizing into trees one can find even more situations where a notion of "minimality" is doubtful.

There has been a lot of work on generalizing edit scripts to trees. This has been split in two main bodies of work:

  • Untyped Trees: Think of s-expressions only. The tree-edit-distance between two trees is the string-edit-distance between the preorder traversal of said trees. You can check some bibliography by Demaine et al. or Pawlik and Augsten, for example.

  • Typed Trees: Patches over Abstract Syntax Trees that are guaranteed to preserve the well-typedness of the object, ie, applying a patch will always yield a valid AST. Under the typed umbrella, there are less edit operations one can consider. Substitution, for example, doesn't make sense. Nevertheless, there exists a diff over the preorder traversal of the trees by Lempsink et al., which was later extended by Vassena. I am currently focusing on approaches that distance themselves from edit scripts for the very problems I pointed earlier, such as our latest work or some earlier work which tries to take advantage of the structure of the type of the values being "patched".

In either of those cases I have not seen a careful categorical interpretation of tree-structured patches.

$\endgroup$
3
  • $\begingroup$ Awesome answer! But why should there be no categorical notion of minimal edit scripts just because they're not unique? (Co)limits aren't unique either, only up to isomorphism. $\endgroup$
    – Turion
    Jul 5, 2019 at 12:44
  • $\begingroup$ I guess we could take the cocompletion and include conflicts, or just say that pushouts don't always exist, and when they don't exist there is no merge? $\endgroup$
    – Turion
    Jul 5, 2019 at 12:45
  • 1
    $\begingroup$ @Turion, uniqueness up to isomorphism is pretty strong. We don't have that with edit scripts. This makes it pretty difficult to define the arrow between $A$ and $B$ as the minimal edit script. Instead, on says that diff finds the minimal, but the model will consider any edit script as an arrow between $A$ and $B$. Composition is another problem, for example. Composition of minimal edit scripts is not guaranteed to be minimal. On the other comment, yes, we could say some merges don't exist. But diff3 does compute them. This would remove conflict handling from the model altogether. $\endgroup$ Jul 5, 2019 at 13:56
8
$\begingroup$

There is quite a bit of work in this direction. You could start by looking at [1, 2], but they don't exhaust the topic.


  1. S. Mimram, C. Di Giusto, A Categorical Theory of Patches.

  2. C. Angiuli, E. Morehouse, D. R. Licata, R. Harper, Homotopical Patch Theory.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.