Online / 6 & 7 February 2021


Semantically meaningful S-expression diff

Tree-diff for lisp source code

Lisp has a wonderful minimal syntax that almost directly expresses the abstract syntax tree. Yet, diff and other tooling operate on the unix newline ending model. When lisp prides itself for its minimal syntax---code is data---that is easy to parse, why can't we do better?

Traditional diff implementations, such as GNU Diff, treat files as a flat list of lines. A tree-diff algorithm that can produce minimal and semantically meaningful output is a surprisingly more difficult and complex problem. In fact, for unordered trees, the problem is NP-hard.

In this talk, I will demonstrate a very early working prototype of an S-expression diff program. The program can operate on two versions of some lisp source code and extract a meaningful tree-diff. The program aims to replace 'git diff' and related tools for lisp projects.


Photo of Arun Isaac Arun Isaac