Kategorietheoretische Behandlung von Diffs, Patches und Merge?

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)?

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.

$L$$A : [n] \rightarrow L$$[n]$$n$$A : [n] \rightarrow L$$B : [m] \rightarrow L$$f : [n] \rightarrow [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. $ab$$ba$

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.

In dieser Richtung gibt es einiges an Arbeit. Sie könnten mit [1, 2] beginnen, aber sie erschöpfen das Thema nicht.

1. S. Mimram, C. Di Giusto, Eine kategorische Theorie der Flecken .

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