Michael Weber: “A #lisp conversation sparked the cunning idea to write a diff-like algorithm for s-expressions.”

The algorithms is based on Levenshtein-like edit distance calculations. It tries to minimize the number of atoms in the result tree (also counting the edit conditionals |#-new|, |#+new|). This can be observed in the example below: instead of blindly adding more edit conditionals, the algorithm backs up and replaces the whole subexpression.

DIFF-SEXP> (diff-sexp  
                '(DEFUN F (X) (+ (* X 2) 4 1)) 
                '(DEFUN F (X) (- (* X 2) 5 3 1)))
((DEFUN F (X) (|#-new| + |#+new| - (* X 2) |#-new| 4 |#+new| 5 |#+new| 3 1)))

DIFF-SEXP> (diff-sexp  
                '(DEFUN F (X) (+ (* X 2) 4 4 1)) 
                '(DEFUN F (X) (- (* X 2) 5 5 3 1)))
((DEFUN F (X) |#-new| (+ (* X 2) 4 4 1) |#+new| (- (* X 2) 5 5 3 1)))