\documentclass{beamer}
\usetheme{Rochester}
\usepackage{fancyvrb}
\usepackage{listings}
\usepackage{tikz}
\usetikzlibrary{graphs}
\begin{document}
\title{Semantically Meaningful S-expression Diff}
\author{Arun Isaac}
\institute{Declarative and Minimalistic Computing Devroom, FOSDEM 2021}
\date{February 6 \& 7, 2021}
\frame{\titlepage}
\begin{frame}[fragile]
  \frametitle{Lisp code is data}
  \framesubtitle{Trivial to parse and manipulate}
  \onslide<2->
  \begin{lstlisting}[language=Lisp,morekeywords={define}]
    (define (factorial n)
      (if (zero? n)
          1
          (* n (factorial (- n 1)))))    
  \end{lstlisting}
  \begin{itemize}[<+(2)->]
  \item The source is almost literally the abstract syntax tree (AST)
  \item Automated source manipulation tools can be written easily
  \item sdiff---a diff program for S-expressions.
  \end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{The Unix world of lines}
  \framesubtitle{Files are a flat list of lines}
  \begin{itemize}[<+(1)->]
  \item Thanks to Unix legacy, most shell utilities (sed, grep, awk,
    cut, etc.) operate on lines.
  \item For example, GNU Diff outputs the difference as a list of
    lines to be inserted and deleted.
  \end{itemize}
  \onslide<4->
  \begin{Verbatim}[commandchars=\\\{\}]
    @@ -7,5 +7,5 @@
    ((? string?)
     (updated-url source-uri))
    ((source-uri ...)
    \textcolor{red}{-(find updated-url source-uri))))))}
    \textcolor{blue}{+(any updated-url source-uri))))))}
    (_ #f))
  \end{Verbatim}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Lisp projects use diff too}
  \framesubtitle{Impedance mismatch between S-expressions and
    line-oriented diff}
  \pause
  Can you spot the actual change in the following diff?
  \begin{Verbatim}[commandchars=\\\{\}]
    \textcolor{red}{< (/ (+ (- b)}
    \textcolor{red}{<       (sqrt (- (* expt b 2)}
    \textcolor{red}{<                (* 4 a c))))}
    \textcolor{red}{<    (* 2 a))}
    ---
    \textcolor{blue}{> (let ((b 1))}
    \textcolor{blue}{>   (/ (+ (- b)}
    \textcolor{blue}{>         (sqrt (- (* expt b 2)}
    \textcolor{blue}{>                  (* 4 a c))))}
    \textcolor{blue}{>      (* 2 a)))}
  \end{Verbatim}
\end{frame}

\begin{frame}[fragile]
  \frametitle{We need a tree diff for S-expressions}
  \framesubtitle{Not a line diff}
  We need a tree diff.
  \begin{Verbatim}[commandchars=\\\{\}]
    (\textcolor{blue}{let ((b 1))}
      (/ (+ (- b)
            (sqrt (- (* expt b 2)
                     (* 4 a c))))
         (* 2 a)))  
   \end{Verbatim}
\end{frame}

\begin{frame}
  \frametitle{Tree diff}
  \framesubtitle{A surprisingly difficult problem}
  \begin{itemize}[<+(1)->]
  \item Extracting the author's intent from the old and new files is
    hard, and probably requires general AI.
  \item Approximate by posing it as an optimization problem.
  \item For unordered trees, the problem is $\mathcal{NP}$-hard.
  \item We only deal with ordered trees.
  \item sdiff implements the \textsc{MH-DIFF} (Meaningful Hierarchical
    Diff) algorithm.
  \end{itemize}
  \onslide<6->
  \emph{Meaningful change detection in structured data}. Sudarshan
  Chawathe, Hector Garcia-Molina, 1997. ACM SIGMOD Record, 26(2),
  pp.26-37.
\end{frame}

\begin{frame}
  \frametitle{MH-DIFF}
  \framesubtitle{A very superficial overview}
  \begin{itemize}[<+->]
  \item MH-DIFF supports 6 operations---insert, delete, update, move,
    copy and glue
  \item With associated costs $c_i$, $c_d$, $c_u(old, new)$, $c_m$,
    $c_c$, $c_g$ respectively
  \item Posed as an optimization problem: to find an edit script such
    that the total cost is minimized.
  \end{itemize}
  \onslide<4->
  MH-DIFF operates in two phases.
  \begin{enumerate}[<+(1)->]
  \item Match old and new trees.
  \item Extract an edit script from the matching.
  \end{enumerate}
\end{frame}

\begin{frame}
  \frametitle{MH-DIFF}
  \framesubtitle{Matching old and new trees}
  Match changed/unchanged parts of old and new trees.
  \begin{columns}
    \column{0.5\textwidth}
    \begin{figure}
      \centering
      \begin{tikzpicture}
        \node {foo}
        child {node {3}}
        child {node {*}
          child {node {2}}
          child {node {a}}};
      \end{tikzpicture}
      \caption{Old tree}
    \end{figure}
    \column{0.5\textwidth}
    \begin{figure}
      \centering
      \begin{tikzpicture}
        \node {foo}
        child {node {3}}
        child {node {bar}
          child {node {2}}
          child {node {a}}};
      \end{tikzpicture}
      \caption{New tree}
    \end{figure}
  \end{columns}
\end{frame}

\begin{frame}
  \frametitle{MH-DIFF}
  \framesubtitle{Minimum cost edge cover}
  \begin{columns}
    \column{0.2\textwidth}
    \begin{overprint}
      \onslide<1-2>
          \begin{tikzpicture}
      \graph [left anchor=east, right anchor=west] {
        {a,b,c} -- [complete bipartite] {e,f,g}
      };
    \end{tikzpicture}
    \onslide<3->
    \begin{tikzpicture}
      \graph [simple,left anchor=east, right anchor=west] {
        {a,b,c} -- [complete bipartite] {e,f,g};
        a -!- e;
        a -!- g;
        b -!- e;
        b -!- f;
        c -!- f;
        c -!- g;
      };
    \end{tikzpicture}
    \end{overprint}
    \column{0.7\textwidth}
    \begin{itemize}[<+->]
    \item Begin with a complete bipartite graph with old tree nodes on
      one side and new tree nodes on the other
    \item An edge is a potential matching of old and new trees, and
      comes with a cost
    \item Goal: Prune edges to minimize total cost
    \item The minimum cost edge cover problem can be solved using the
      Hungarian algorithm
    \end{itemize}
  \end{columns}
\end{frame}

\begin{frame}
  \frametitle{Demos}
  \framesubtitle{The fun part}
  \begin{center}
    {\Huge Demos!}
  \end{center}
\end{frame}

\begin{frame}
  \frametitle{Going forward}
  \framesubtitle{Plenty still needs doing!}
  \begin{itemize}[<+->]
  \item sdiff isn't ready for everyday use yet
  \item plenty of bugs to fix and a lot more testing necessary
  \item maybe improve the cost model and support move, copy and glue
    operations
  \item fully support irregular lisp syntax such as quoting,
    line-based comments, etc.
  \item cleaner and more concise diff output
  \item a more optimized implementation that scales better
  \item integrate and replace tooling such as git diff
  \item use as diff for other S-expression data (such as LibrePCB)
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Thank You!}
  Code is available under GPLv3 at
  {\small \url{https://systemreboot.net/files/sdiff-fosdem2021.tar.gz}}

  \begin{itemize}
  \item Would you use sdiff?
  \item How can sdiff be more useful?
  \item Feedback and criticism welcome!
  \end{itemize}

  arunisaac@systemreboot.net
\end{frame}
\end{document}
