Kategorietheoretische Behandlung von Diffs, Patches und Merge?

14

Gibt es eine Kategorie von Patches, die ungefähr so ​​aussieht:

  • Die Objekte sind Zeichenfolgen in einem Basisalphabet
  • Die Morphismen sind Bearbeitungsskripte ("diffs" oder "patches") zwischen den Strings

Ich interessiere mich für folgende Fragen:

  • Gibt es eine kategorische Vorstellung von minimalem Bearbeitungsskript? Vielleicht ist die Kategorie der Patches in PO-Sets angereichert?
  • Ist das Zusammenführen von Patches das kategorische Pushout?
  • Wie verallgemeinere ich das von Strings zu Bäumen (ein Dateisystem oder ein algebraischer Datentyp)?
Turion
quelle
1
Sie werden einen Blick auf die Theorie hinter dem Darcs VCS
Bergi
1
... oder Pijul , ein relativ neuer Versuch, einen "neueren Darcs" zu erschaffen. (Und soweit ich mich erinnere, ist das Zusammenführen der Push-out in einer "freien Vervollständigung" der Diff-Kategorie ...).
phipsgabler

Antworten:

15

Wie von Martin angedeutet , gibt es einige Arbeiten zur kategorialen Darstellung von Patches. Mimram und Di Giustos "A Categorical Theory of Patches" (Eine kategoriale Theorie der Patches) sind der umfassendste kategoriale Ansatz für die Bearbeitung von Skripten, wie sie von der UNIX diff.

LEIN:[n]L[n]nEIN:[n]LB:[m]Lf:[n][m]. Injektivität und Erhöhung weisen darauf hin, dass sich Kopien niemals überkreuzen . Sie finden alle Details auf dem Papier .

Ja, das Zusammenführen wird als Pushout für die freie Vervollständigung der obigen Kategorie angesehen. Wir brauchen die Kokompletion, um sicherzustellen, dass wir unserer Konstruktion Zusammenführungskonflikte hinzufügen. Es gibt nicht immer eine Zusammenführung.

Bei Ihrer zweiten Frage gibt es aus zwei Hauptgründen keine kategorische Vorstellung von minimalem Bearbeitungsskript.

  1. Bearbeitungsskripte gibt es in allen Formen und Formen. Einige Autoren betrachten Einfügungen, Löschungen und Kopien, einige Autoren möchten auch Ersetzungen als Operation hinzufügen. Wenn Sie von Schnüren auf Bäume verallgemeinern, wird eine Fülle anderer Operationen möglich.

  2. einbbein

Es wurde viel Arbeit an der Verallgemeinerung von Bearbeitungsskripten auf Bäume geleistet. Dies wurde in zwei Hauptbereiche unterteilt:

  • Untypisierte Bäume : Denken Sie nur an S-Ausdrücke. Die Baumeditierentfernung zwischen zwei Bäumen ist die Zeichenketteneditierentfernung zwischen der Vorbestellungsdurchquerung der Bäume. Sie können einige Bibliographien von Demaine et al. oder Pawlik und Augsten zum Beispiel.

  • Typisierte Bäume : Patches über abstrakten Syntaxbäumen , bei denen garantiert wird, dass die Typisierung des Objekts erhalten bleibt, dh das Anwenden eines Patches führt immer zu einem gültigen AST. Unter dem typisierten Dach gibt es weniger Bearbeitungsvorgänge, die berücksichtigt werden können. Substitution zum Beispiel macht keinen Sinn. Trotzdem gibt es einen Unterschied zur Vorbestellung der Bäume von Lempsink et al. , die später von Vassena erweitert wurde . Ich konzentriere mich derzeit auf Ansätze, die sich von Bearbeitungsskripten für genau die Probleme distanzieren, auf die ich zuvor hingewiesen habe, wie unsere neueste Arbeit oder einige frühere Arbeiten, die versuchen, die Struktur des Typs der Werte, die "gepatcht" werden, auszunutzen.

In beiden Fällen habe ich keine sorgfältige kategoriale Interpretation von Patches mit Baumstruktur gesehen.

Victor Miraldo
quelle
Geniale Antwort! Aber warum sollte es keine kategorische Vorstellung von minimalen Bearbeitungsskripten geben, nur weil sie nicht eindeutig sind? (Co) Grenzen sind auch nicht eindeutig, nur bis zum Isomorphismus.
Turion
Ich denke, wir könnten die Kokompletion nehmen und Konflikte einbeziehen oder einfach sagen, dass Pushouts nicht immer existieren und wenn sie nicht existieren, gibt es keine Verschmelzung?
Turion
1
EINBdiffEINBdiff3