Effectively computing the difference between two version of a source file has become an indespensable part of software development. The de facto standard tool used by most version control systems is the
UNIX diff utility, that compares two files on a line-by-line basis without any regard for the structure of the data stored in these files. This paper presents an alternative datatype generic algorithm for computing the difference between two values of any algebraic datatype. This algorithm maximizes sharing between the source and target trees, while still running in linear time. Finally, this paper demonstrates that by instantiating this algorithm to the Lua abstract syntax tree and mining the commit history of repositories found on GitHub, the resulting patches can often be merged automatically, even when existing technology has failed.
Wed 21 AugDisplayed time zone: Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna change
15:20 - 16:30
|Mixed Linear and Non-linear Recursive Types|
|A Mechanical Formalization of Higher-Ranked Polymorphic Type InferenceDistinguished Paper|
|An Efficient Algorithm for Type-Safe Structural Diffing|