¿Tratamiento teórico por categorías de diferencias, parches y fusión?

¿Existe una categoría de parches que se ve más o menos así?

• Los objetos son cadenas en algún alfabeto base
• Los morfismos son guiones de edición ("diffs" o "parches") entre las cadenas

Estoy interesado en estas preguntas:

• ¿Existe una noción categórica de guión de edición mínima ? ¿Quizás la categoría de parches está enriquecida en PO-Sets?
• ¿Es la fusión de parches el impulso categórico?
• ¿Cómo generalizar esto de cadenas a árboles (un sistema de archivos o un tipo de datos algebraico)?

Como señaló Martin , hay algunos trabajos sobre la representación categórica de parches. "Una teoría categórica de parches" de Mimram y Di Giusto es el enfoque categórico más extenso para editar guiones, tal como lo utiliza el UNIX diff.

En su sentido, tienes lo que quieres. Los objetos son secuencias finitas de palabras sobre un alfabeto $L$ , visto como un mapeo $A : [n] \rightarrow L$ , donde $[n]$ denota el conjunto con $n$ elementos. Una flecha entre $A : [n] \rightarrow L$ y $B : [m] \rightarrow L$ es un mapeo de aumento parcial inyectivo $f : [n] \rightarrow [m]$. La inyectividad y el aumento están ahí para indicar que las copias nunca se cruzan entre sí. Puede encontrar todos los detalles en el papel .

Sí, la fusión se ve como el impulso a la finalización gratuita de la categoría anterior. Necesitamos la finalización para asegurarnos de agregar conflictos de fusión a nuestra construcción. No es el caso de que siempre exista una fusión.

En su segunda pregunta, no hay una noción categórica de script de edición mínima por dos razones principales.

1. Los guiones de edición vienen en todas las formas y formas. Algunos autores consideran inserciones, eliminaciones y copias, a algunos autores también les gusta agregar sustituciones como una operación. Cuando generalizas de cadenas a árboles, entonces, una gran cantidad de otras operaciones se vuelven factibles.

2. $ab$$ba$

Se ha trabajado mucho en generalizar guiones de edición a árboles. Esto se ha dividido en dos cuerpos principales de trabajo:

• Árboles sin tipo : piense solo en expresiones s. La distancia de edición de árbol entre dos árboles es la distancia de edición de cadena entre el recorrido previo al pedido de dichos árboles. Puede consultar alguna bibliografía de Demaine et al. o Pawlik y Augsten , por ejemplo.

• Árboles tipificados : parches sobre árboles de sintaxis abstracta que garantizan la buena tipificación del objeto, es decir, la aplicación de un parche siempre generará un AST válido. Bajo el paraguas escrito, hay menos operaciones de edición que uno puede considerar. La sustitución, por ejemplo, no tiene sentido. Sin embargo, existe una diferencia sobre el recorrido previo de los árboles por Lempsink et al. , que luego fue extendido por Vassena . Actualmente me estoy enfocando en enfoques que se distancian de los scripts de edición por los problemas que señalé anteriormente, como nuestro último trabajo o algún trabajo anterior que intenta aprovechar la estructura del tipo de valores que se están "parcheando".

En ninguno de esos casos no he visto una cuidadosa interpretación categórica de parches estructurados en árbol.

Hay bastante trabajo en esta dirección. Puede comenzar mirando [1, 2], pero no agotan el tema.

1. S. Mimram, C. Di Giusto, Una teoría categórica de los parches .

2. C. Angiuli, E. Morehouse, DR Licata, R. Harper, Teoría del parche homotópico .