\documentclass{beamer}

\input{header.tex}

\begin{document}

%% Notes from meeting:

%% Expand traversal discussion and show an accumulator example for A.

%% Rearrange the slides so the punch line is clearer.

%% Watch 'formal' stuff so that it isn't too messy and is precise

%% Type discussion should be expanded




\frame{
  \begin{center}
  {\LARGE\color{blue}Removing Accidental Traversal Complexity\\\smallskip
    from Programs }
  
  ~\\~\\~\\~\\~\\~\\
  Bryan Chadwick

  ~\\PL Seminar\\April $23^{\text{rd}}$
  \end{center}
}

\begin{frame}
  \frametitle{AP-F}
  \begin{itemize}
  \item[*] Flexibility
    \begin{itemize}
    \item[-] Implicit traversal
    \item[-] Closer to hand written
    \item[] 
    \end{itemize}
    
  \item[*] Modularity
    \begin{itemize}
    \item[-] Abstraction/decomposition
    \item[-] Building up function sets
    \item[]
    \end{itemize}
  \item[*] A Solution to the ``{\it Expression Problem}''
    \begin{itemize}
    \item[-] ``Extension'' of functionality and data structures
    \end{itemize}
  \end{itemize}
\end{frame}


\begin{frame}
  \frametitle{Where We Fit}
  \ \qquad\includegraphics[scale=0.75]{dia.pdf}
\end{frame}


\begin{frame}
  \frametitle{Where We Fit}
  \ \qquad\includegraphics[scale=0.75]{dia-apf.pdf}  
\end{frame}


\begin{frame}[Outline]
  \frametitle{Outline}
  \tableofcontents
\end{frame}


\section{Traversals}
\subsection{Motivation}
\begin{frame}[fragile]
  \frametitle{Traversals: Scheme Lists}
  \begin{itemize}
    \item[*] Structural Recursion
  \begin{BVerbatim}


    ;; fold-r : (X Y -> Y) Y [listof X] -> Y
    (define (fold-r xy->y y lox)
      (cond [(null? lox) y]
            [else (xy->y (car lox)
                         (fold-r xy->y y (cdr lox)))]))


  \end{BVerbatim}
  %% Discussion of generalized folds too: replacing constructors with
  %%   user defined functions (Meijer and Jeuring)

  \pause
  \item[*] Why use {\tt fold}, {\tt map}, and others?

    \pause
    \begin{itemize}
    \item[+] Easier... but why?
      
    \pause
    \item[+] Eliminate list ``field" accesses ({\tt car}/{\tt cdr})

    \pause
    \item[+] Eliminate explicit recursion
    \end{itemize}
    
    \pause
  \item[*] Abstract... hide structure!
    %% We don't hide it completely, but we have a more conceptual view
    %%   of the structure rather than a concrete view.
  \end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Motivation}
  \begin{itemize}
  \item[*] Want a ``{\it Write-Once}" Traversal
    %% General enough that it (or at least its semantics) doesn't have
    %%   to change if the data structures do.
    
  \item[*] Flexible (solve many problems, like {\tt fold})
    %% Abstract enough to handle multiple similar problems effectively

  \item[*] Handle multi-dimensional structures consistently
    %% Predictible in the face of new structures

  \item[*] Make things easier (shorthand)
    %% Like map/filter/etc... not just `fold'
  \end{itemize}
\end{frame}


\begin{frame}[fragile]
  \frametitle{Quick Example: Lambda Terms}
  %% Straight out of EOPL. The terms contain structural recursion in
  %%   different fields.
  \begin{BVerbatim}
   ;; An exp is either:
   ;;   -- (make-var-e symbol)
   ;;   -- (make-lambda-e symbol exp)
   ;;   -- (make-app-e exp exp)
   (define-struct var-e (id))
   (define-struct lambda-e (id body))
   (define-struct app-e (rator rand))
 
  \end{BVerbatim}

  \pause
  Calculate the free variables of a term:

  \begin{BVerbatim}
 

   ;; free-vars : exp -> [setof symbol]
   ;; Collect the free variables in an expression
   (define (free-vars e)
     (cond [(var-e? e)    (set-single (var-e-id e))]
           [(lambda-e? e) (set-rm (free-vars (lambda-e-body e))
                                  (lambda-e-id e))]
           [(app-e? e)    (set-union (free-vars (app-e-rator e))
                                     (free-vars (app-e-rand e)))]))
  
  \end{BVerbatim}
  %% At this point it's nothing new (obviously). But, we notice there
  %%   are a lot of recursive calls on the structure, and tedious
  %%   accesses in order to make it happen.

  \pause
  \begin{BVerbatim}

   ;; AP-F traversal free variable calculation
   (define (free-vars-apf e)
     (let ((B (func-set 
                [(var-e symbol)        (v id)      (set-single id)]
                [(lambda-e symbol set) (l id fv)   (set-rm fv id)]
                [(app-e set set)       (c fvl fvr) (set-union fvl fvr)])))
       (traverse-b e B)))
  \end{BVerbatim}

  %% A few new things:
  %%   - func-set... a set of functions where:
  %%              func := ((<type>*) (<id>*) Expr)
  %%          func-set := [listof func]

  %%   - The first type/id represents the original portion of the data
  %%       structure that was traversed (the constructor that we will
  %%       be replacing), the others represent results of the
  %%       recursive traversal.

  %%   - traverse-b... the generic traversal; we hand it the structure
  %%       to be traversed and a 'builder' that is used to replace
  %%       constructors.  The functions in the set are only called if
  %%       the declared types 'match' the actual traversal results.
  
  %% There are a few more specialized functions that we will see
  %%   later, but these all use a more general traversal function.
\end{frame}

\AtBeginSection[] % Do nothing for \section*
{
  \frame<beamer>{
    \frametitle{Outline}
    \tableofcontents[current]
  }
}


\section{Traversal Abstraction}
\begin{frame}[fragile]
  \frametitle{Traversal Abstraction}
  \begin{itemize}
  \item[*] Generic traversal function
  \item[*] 3 function sets: {\tt F}, {\tt B}, and {\tt A}
    %% We've seen a little of B, but more to come.
  \item[*] Control function: {\tt C}
  \item[*] Custom type-based dispatch
  \end{itemize}
\end{frame}


\begin{frame}[fragile]
  \frametitle{General Traversal}
  \begin{itemize}
  \item[] Primitives: {\tt number}, {\tt string}, etc...
    \begin{itemize}
    \item[-] Just apply {\tt F}
    \end{itemize}
  \item[]
  \item[] Structures:
    \begin{itemize}
    \item[-] Update the traversal argument
    \item[-] For each Field:
      \begin{itemize}
        \item[] If \ {\tt C} returns {\tt \#t}, recursively traverse
        \item[] Otherwise apply {\tt F}
      \end{itemize}
    \item[-] Use {\tt B} to rebuild the structure
    \item[-] Give {\tt F} a final chance
    \end{itemize}
  \end{itemize}
\end{frame}


\begin{frame}[fragile]
  \frametitle{Traversal Example: {\tt map}}
  \begin{BVerbatim}
    ;; map-t : (X -> Y) [listof X] -> [listof Y]
    ;; Map for any dimensional lists of primitives
    (define (map-t x->y lst)
      (traverse lst
                ;; F
                (func-set [(object) (x) (x->y x)]
                          [(list) (l) l])
                ;; B
                (func-set [(empty) (e) e]
                          [(cons object list) (c f r) (cons f r)])
                ;; A
                (func-set [(object object) (o arg) arg])
                ;; C
                (lambda (obj i) #t)
                ;; traversal argument (ignored)
                0))

    (map-t add1 '(1 2 3))  ;; ==> '(2 3 4)
    (map-t sub1 '(1 2 3))  ;; ==> '(0 1 2)

    (map-t add1 '(((1)) ((2 (3)))));; ==> '(((2)) ((3 (4))))
  \end{BVerbatim}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Traversal Example: {\tt map}}
  \begin{BVerbatim}
    ;; map-t : (number -> Y) [listof number] -> [listof Y]
    ;; Map for lists of numbers.
    ;;  * Really, it works for any structure containing numbers
    (define (map-t n->y lon)
      (traverse-f lon (union-idF [(number) (n) (n->y n)])))

    (map-t add1 '(1 2 3))  ;; ==> '(2 3 4)
    (map-t sub1 '(1 2 3))  ;; ==> '(0 1 2)

    (map-t add1 '(((1)) ((2 (3)))));; ==> '(((2)) ((3 (4))))
  \end{BVerbatim}
\end{frame}

\subsection{Types \& Function Selection}
\begin{frame}[fragile]
  \frametitle{Function Dispatch: {\tt delta}}
  \begin{itemize}
  \item[*] Sets of {\it typed} functions
  \item[*] Compares formal/actual types
  \item[*] {\it Best} one wins
  \item[*] Applies to a prefix of arguments
    
    %% User specifies the types a function can be applied to and the
    %%   dispatch function finds the 'best' (closest) match
  \end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Definition: {\tt better?}}

  \begin{BVerbatim}


    ;; better? : Function Function -> boolean
    ;; Is the first function 'better' than the second
    (define (better? f1 f2)
        (let ((n1 (func-arity f1))
              (n2 (func-arity f2)))
          (or (> n1 n2)
              (and (= n1 n2)
                   (more-specific? (func-types f1) (func-types f2) n1))))))

  \end{BVerbatim}
\end{frame}

%% We abstract the dispatch into a function called 'delta' that
%%   selects and calles the best function based on formal and actual
%%   argument types.

\newcommand\helper[1]{{\color{Number}\#$\mathtt{\backslash}$#1}\,}
\begin{frame}[fragile]
  \frametitle{Examples: {\tt delta}}

  \begin{BVerbatim}

    (define a-func
      (func-set [(number)      (n)   (- n 1)]
                [(object char) (o c) (char->integer c)]
                [(object)      (o)   5]))
  

    (delta a-func (list 7 \helper{A}))   ;; ==>  65

    (delta a-func (list 7 'test)) ;; ==>  6

    (delta a-func (list 'test 7)) ;; ==>  5

  \end{BVerbatim}
\end{frame}

%% The chosen function is applied to a prefix of the arguments.  This
%%   means that it is possible to ignore later arguments, leading
%%   to optional field traversals and optional traversal arguments.

%% This brings up an obvious optimization... skipping fields that we
%%   know are not used; but that's for another time.

%% Above, the first test chooses (object char) and uses both
%%   arguments. The second chooses the first function (number) and
%%   calls it on only the first actual argument.  The final test is
%%   only applicable to the last function, and calls it with a single
%%   argument.


\subsection{Control}
\begin{frame}[fragile]
  \frametitle{Traversal Control}
  \begin{itemize}
  \item[*] control {: (\tt struct number $\rightarrow$ boolean)}
  \item[*] Bypass structure fields
  \item[*] Dynamic... but not necessarily
  \item[*] {\tt\color{KeyWords}everywhere}
  \item[*] {\tt({\color{KeyWords}make-bypass} (type fieldname) ...)}
  \end{itemize}

  \begin{BVerbatim}



                ;; Define a simple 'pair'
                (def-prod a-pair [(n number)
                                  (c char)])
      
                ;; Define a control/bypass function
                (define skip (make-bypass (a-pair n)))
      
                (skip (a-pair 5 \helper{B}) 0) ;;  ==> #f
                (skip (a-pair 5 \helper{B}) 1) ;;  ==> #t

  \end{BVerbatim}
\end{frame}

%% everywhere is the control function that always returns #t... it is
%%   usefull for most situations.  For more control, we will use a
%%   static version that bypasses fields; build with 'make-bypass'.

%% We use our custom data definitions here.  def-prod is similar to
%%   define struct except we add types to fields to enable parsing.

%% 'skip' is defined as the control function that bypasses the 'n'
%%   field of 'a-pair' struct.  'n' happens to be the first (index
%%   zero) field within the struct, so our function returns false
%%   (meaning don't traverse) for that selected field.

%% Control is usefull for optimizations (from before... ignoring
%%   unneeded traversals), but also for correctness for limiting the
%%   extent of a transformation and/or non-type-preserving
%%   situations. We will see more examples later.


\subsection{Function Sets}
\begin{frame}[fragile]
  \frametitle{Function Sets}
  \begin{itemize}
  \item[*] {\tt\color{KeyWords}func-set}  builds them
  \item[*] {\tt\color{KeyWords}union-func}  ``extends'' them
  \item[*] Others for unions with defaults
  \end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Default Behavior}
  \begin{itemize}
    \lstset{basicstyle=\ttfamily\scriptsize}
    \item[*] Free to build fresh, or...
    \item[*] {\tt\color{KeyWords}union-\_} for each default\\~
    
    \begin{itemize}
      \item[]\begin{itemize}

  \item[idF] : {\tt id} transform
    \begin{BVerbatim}

  (lambda (obj) obj)

    \end{BVerbatim}

  \item[idA] : {\tt id} for arguments
    \begin{BVerbatim}

  (lambda (obj targ) targ)

    \end{BVerbatim}

  \item[Bc] : Calls original constructors
    \begin{BVerbatim}

  (func-set
    [(cons object list) (f r) (cons f r)]
    [(empty) (e) e]
     ...)
    \end{BVerbatim}
  \end{itemize}
  \end{itemize}
  \end{itemize}
\end{frame}


\begin{frame}[fragile]
  \frametitle{Finally... traversing}
  General:
  \begin{itemize}
  \item[]\scriptsize
    \begin{tabular}{l}
      {\tt (traversal obj F B A C . targ)}\\\\
    \end{tabular}
  \end{itemize}
  Defaults with control:
  \begin{itemize}
    \item[]\scriptsize
    \begin{tabular}{l@{}l}
      {\tt (traversal-fc obj F C)} &\;:\; Bc \& idA\\
      {\tt (traversal-bc obj B C)} &\;:\; idF \& idA\\
      {\tt (traversal-fac obj F A C targ)} &\;:\; Bc\\
      {\tt (traversal-bac obj B A C targ)} &\;:\; idF\\\\
    \end{tabular}
  \end{itemize}

  Aliases with {\tt \color{KeyWords}everywhere}:
  \begin{itemize}
    \item[]\scriptsize
    \begin{tabular}{l}
      {\tt (traversal-f obj F)}\\
      {\tt (traversal-b obj B)}\\
      \ \quad ...
    \end{tabular}
  \end{itemize}
  
\end{frame}


\section{Example: BSTs}
\begin{frame}[fragile]
  \frametitle{Example: BSTs}
  \begin{itemize}
  \item[*] Data-Definitions 
    \begin{itemize}
      \item[-] New 'language' for structure definitions
      \item[]
    \end{itemize}
        
  \item[*] Simple Transforms
    \begin{itemize}
      \item[-] Increment
      \item[-] Strings
      \item[-] Reverse
      \item[-] Height
    \end{itemize}
  \end{itemize}
\end{frame}

\subsection{Data Definitions}
\begin{frame}[fragile]
  \frametitle{Example: BST Data-Definitions}
  
  \begin{BVerbatim}

    ;; Mixed concrete/abstract syntax
    (def-sum  tree [leaf node])
    (def-prod leaf ["*"])
    (def-prod node ["(" (data number)
                        (left tree)
                        (right tree) ")"])


  \end{BVerbatim}

  \begin{minipage}[c][3cm]{8cm}
    \begin{itemize}
    \item[*] Sum types (abstract `interfaces')
    \item[*] Product types (constructors)
    \item[*] Uses {\tt\color{KeyWords} define-struct}
      \begin{itemize}
      \item[]
      \end{itemize}
    \end{itemize}
  \end{minipage}
\end{frame}

%% In Haskell, data definitions are mixed sum/product syntax that
%%   defines constructors and 'sub-types' all in one shot. We separate
%%   the two because it's usefull to create multiple interfaces
%%   (super-types) for a given type.

%% Here we only define (subtype node tree) and (subtype node tree)

\begin{frame}[fragile]
  \frametitle{Example: BST Data-Definitions}
  \begin{BVerbatim}

    ;; Mixed concrete/abstract syntax
    (def-sum  tree [leaf node])
    (def-prod leaf ["*"])
    (def-prod node ["(" (data number)
                        (left tree)
                        (right tree) ")"])


  \end{BVerbatim}

  \begin{minipage}[c][3cm]{10cm}
  \begin{itemize}
  \item[*] Supports parsing
    \begin{itemize}
    \item[]{\scriptsize\tt {\color{String}"(3 (1 (0 **) (2 **)) (5 (4 **) *))"}}
    \item[]
    \end{itemize}
  \item[*] Introduces constructors
    \begin{itemize}
    \item[]{\tt node : number tree tree $\rightarrow$ tree}
    \item[]{\tt leaf : $\rightarrow$ tree}
    \end{itemize}
  \end{itemize}
  \end{minipage}
\end{frame}



\subsection{Transform Examples}
\begin{frame}[fragile]
  \frametitle{Example: Increment}

  ~\quad\qquad\hbox{
    \begin{tabular}{rcl}
    \tiny
    \setlength{\unitlength}{0.05in}
    %\linethickness{2pt}
    \begin{picture}(20,10)
      \put(9.0, 10.0){\framebox(2,2){3}}
      \drawline(10.0,10.0)(5.0,8.3)
      \drawline(10.0,10.0)(15.0,8.3)
      \put(4.0, 6.3){\framebox(2,2){1}}
      \drawline(5.0,6.3)(2.5,4.6)
      \drawline(5.0,6.3)(7.5,4.6)
      \put(1.5, 2.6){\framebox(2,2){0}}
      \put(6.5, 2.6){\framebox(2,2){2}}
      \put(14.0, 6.3){\framebox(2,2){5}}
      \drawline(15.0,6.3)(12.5,4.6)
      \put(11.5, 2.6){\framebox(2,2){4}}
    \end{picture}&
    \begin{picture}(12,10)
      \put(-1.0, 20.0){{\Large $\rightarrow$}}
    \end{picture}&
    \tiny
    \setlength{\unitlength}{0.05in}
    \begin{picture}(20,10)
      \put(9.0, 10.0){\framebox(2,2){4}}
      \drawline(10.0,10.0)(5.0,8.3)
      \drawline(10.0,10.0)(15.0,8.3)
      \put(4.0, 6.3){\framebox(2,2){2}}
      \drawline(5.0,6.3)(2.5,4.6)
      \drawline(5.0,6.3)(7.5,4.6)
      \put(1.5, 2.6){\framebox(2,2){1}}
      \put(6.5, 2.6){\framebox(2,2){3}}
      \put(14.0, 6.3){\framebox(2,2){6}}
      \drawline(15.0,6.3)(12.5,4.6)
      \put(11.5, 2.6){\framebox(2,2){5}}
    \end{picture}
    \end{tabular}
  }

  \begin{BVerbatim}


    ;; tree-incr : tree -> tree
    ;; Increment each data element in the given tree
    (define (tree-incr t)
      (cond [(leaf? t) t]
            [else (node (add1 (node-data t))
                        (tree-incr (node-left t))
                        (tree-incr (node-right t)))]))


    ;; AP-F function
    (define (incr t)
      (traverse-f t (union-idF ((number) (n) (add1 n)))))




  \end{BVerbatim}
\end{frame}


\begin{frame}[fragile]
  \frametitle{Example: Strings}

  ~\qquad\quad\hbox{
    \begin{tabular}{rcl}
    \tiny
    \setlength{\unitlength}{0.05in}
    %\linethickness{2pt}
    \begin{picture}(20,10)
      \put(9.0, 10.0){\framebox(2,2){3}}
      \drawline(10.0,10.0)(5.0,8.3)
      \drawline(10.0,10.0)(15.0,8.3)
      \put(4.0, 6.3){\framebox(2,2){1}}
      \drawline(5.0,6.3)(2.5,4.6)
      \drawline(5.0,6.3)(7.5,4.6)
      \put(1.5, 2.6){\framebox(2,2){0}}
      \put(6.5, 2.6){\framebox(2,2){2}}
      \put(14.0, 6.3){\framebox(2,2){5}}
      \drawline(15.0,6.3)(12.5,4.6)
      \put(11.5, 2.6){\framebox(2,2){4}}
    \end{picture}&
    \begin{picture}(12,10)
      \put(-1.0, 20.0){{\Large $\rightarrow$}}
    \end{picture}&
    \tiny
    \setlength{\unitlength}{0.05in}
    \begin{picture}(20,10)
      \put(7.5, 10.0){\framebox(5,2){three}}
      \drawline(10.0,10.0)(5.0,8.3)
      \drawline(10.0,10.0)(15.0,8.3)
      \put(3.5, 6.3){\framebox(3,2){one}}
      \drawline(5.0,6.3)(2.5,4.6)
      \drawline(5.0,6.3)(7.5,4.6)
      \put(0.5, 2.6){\framebox(4,2){zero}}
      \put(6.0, 2.6){\framebox(3,2){two}}
      \put(13.0, 6.3){\framebox(4,2){five}}
      \drawline(15.0,6.3)(12.5,4.6)
      \put(10.5, 2.6){\framebox(4,2){four}}
    \end{picture}
    \end{tabular}
  }

  \begin{BVerbatim}


    (define names '("zero" "one" "two"
                    "three" "four" "five"))

    ;; tree-strs : tree -> tree
    ;; Replace each data element by its English word
    (define (tree-strs t)
      (cond [(leaf? t) t]
            [else (node (list-ref names (node-data t))
                        (tree-strs (node-left t))
                        (tree-strs (node-right t)))]))


    ;; AP-F function
    (define (strs t) 
      (traverse-f t (union-idF ((number) (n) (list-ref names n)))))

  \end{BVerbatim}
\end{frame}


\begin{frame}[fragile]
  \frametitle{Example: Reverse}

  ~\quad\qquad\hbox{
    \begin{tabular}{rcl}
    \tiny
    \setlength{\unitlength}{0.05in}
    %\linethickness{2pt}
    \begin{picture}(20,10)
      \put(9.0, 10.0){\framebox(2,2){3}}
      \drawline(10.0,10.0)(5.0,8.3)
      \drawline(10.0,10.0)(15.0,8.3)
      \put(4.0, 6.3){\framebox(2,2){1}}
      \drawline(5.0,6.3)(2.5,4.6)
      \drawline(5.0,6.3)(7.5,4.6)
      \put(1.5, 2.6){\framebox(2,2){0}}
      \put(6.5, 2.6){\framebox(2,2){2}}
      \put(14.0, 6.3){\framebox(2,2){5}}
      \drawline(15.0,6.3)(12.5,4.6)
      \put(11.5, 2.6){\framebox(2,2){4}}
    \end{picture}&
    \begin{picture}(12,10)
      \put(-1.0, 20.0){{\Large $\rightarrow$}}
    \end{picture}&
    \tiny
    \setlength{\unitlength}{0.05in}
    \begin{picture}(20,10)
      \put(9.0, 10.0){\framebox(2,2){3}}
      \drawline(10.0,10.0)(5.0,8.3)
      \drawline(10.0,10.0)(15.0,8.3)
      \put(4.0, 6.3){\framebox(2,2){5}}
      \drawline(5.0,6.3)(7.5,4.6)
      \put(6.5, 2.6){\framebox(2,2){4}}
      \put(14.0, 6.3){\framebox(2,2){1}}
      \drawline(15.0,6.3)(12.5,4.6)
      \drawline(15.0,6.3)(17.5,4.6)
      \put(11.5, 2.6){\framebox(2,2){2}}
      \put(16.5, 2.6){\framebox(2,2){0}}
    \end{picture}
    \end{tabular}
  }

  \begin{BVerbatim}


    ;; tree-rev : tree -> tree
    ;; Reverse all the data elements in the tree
    (define (tree-rev t)
      (cond [(leaf? t) t]
            [else (node (node-data t)
                        (tree-rev (node-right t))
                        (tree-rev (node-left t)))]))


    ;; AP-F function
    (define (rev t) 
      (traverse-b t (union-Bc [(node object tree tree)
                               (n d lt rt) (node d rt lt)])))



  \end{BVerbatim}
\end{frame}


\begin{frame}[fragile]
  \frametitle{Example: Height}

  ~\quad\qquad\hbox{
    \begin{tabular}{rcl}
    \tiny
    \setlength{\unitlength}{0.05in}
    %\linethickness{2pt}
    \begin{picture}(20,10)
      \put(9.0, 10.0){\framebox(2,2){3}}
      \drawline(10.0,10.0)(5.0,8.3)
      \drawline(10.0,10.0)(15.0,8.3)
      \put(4.0, 6.3){\framebox(2,2){1}}
      \drawline(5.0,6.3)(2.5,4.6)
      \drawline(5.0,6.3)(7.5,4.6)
      \put(1.5, 2.6){\framebox(2,2){0}}
      \put(6.5, 2.6){\framebox(2,2){2}}
      \put(14.0, 6.3){\framebox(2,2){5}}
      \drawline(15.0,6.3)(12.5,4.6)
      \put(11.5, 2.6){\framebox(2,2){4}}
    \end{picture}&
    \begin{picture}(12,10)
      \put(-1.0, 20.0){{\Large $\rightarrow$}}
    \end{picture}&
    \tiny
    \setlength{\unitlength}{0.05in}
    \begin{picture}(20,10)
      \put(4.0, 6.0){{3}}
    \end{picture}
    \end{tabular}
  }

  \begin{BVerbatim}



    ;; height : tree -> number
    ;; Calculate the height of the given tree
    (define (height t)
      (let ((B (func-set 
                 [(leaf) (l) 0]
                 [(node object number number)
                  (n d lt rt) (add1 (max lt rt))])))
        (traverse-b t B)))







  \end{BVerbatim}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Example: Height - Top Down}

  ~\quad\qquad\hbox{
    \begin{tabular}{rcl}
    \tiny
    \setlength{\unitlength}{0.05in}
    %\linethickness{2pt}
    \begin{picture}(20,10)
      \put(9.0, 10.0){\framebox(2,2){3}}
      \drawline(10.0,10.0)(5.0,8.3)
      \drawline(10.0,10.0)(15.0,8.3)
      \put(4.0, 6.3){\framebox(2,2){1}}
      \drawline(5.0,6.3)(2.5,4.6)
      \drawline(5.0,6.3)(7.5,4.6)
      \put(1.5, 2.6){\framebox(2,2){0}}
      \put(6.5, 2.6){\framebox(2,2){2}}
      \put(14.0, 6.3){\framebox(2,2){5}}
      \drawline(15.0,6.3)(12.5,4.6)
      \put(11.5, 2.6){\framebox(2,2){4}}
    \end{picture}&
    \begin{picture}(12,10)
      \put(-1.0, 20.0){{\Large $\rightarrow$}}
    \end{picture}&
    \tiny
    \setlength{\unitlength}{0.05in}
    \begin{picture}(20,10)
      \put(4.0, 6.0){{3}}
    \end{picture}
    \end{tabular}
  }

  \begin{BVerbatim}



    ;; height : tree -> number
    ;; Calculate the height of the given tree using an argument
    (define (height t)
      (let ((A (union-idA 
                 [(node number) (n h) (add1 h)])))
            (B (func-set 
                 [(leaf number) (l h) h]
                 [(node object number number) (n d lt rt) (max lt rt)]))
        (traverse-ba t B A 0)))






  \end{BVerbatim}
\end{frame}

\section{More Lambda Examples}
\begin{frame}[fragile]
  \frametitle{More Lambda Examples}
  \begin{itemize}
  \item[*] Addition of {\it let}
    \begin{itemize}
      \item[-] Missing case is caught
      \item[] 
    \end{itemize}
  \item[*] de Bruijn Indices (different ways)
    \begin{itemize}
      \item[-] idF (transform {\it var-e})
      \item[-] Bc (rebuild {\it var-e})
      \item[-] But scope rules not captured!
    \end{itemize}
\end{itemize}
\end{frame}

%\subsection{Adding Let: Issues}
\begin{frame}[fragile]
  \frametitle{Lambda: adding {\it let}}
\begin{minipage}[t][6cm]{14cm}
  \begin{BVerbatim}
   ;; Lambda expressions
   (def-sum  exp [var-e lambda-e app-e let-e])

   (def-prod var-e [(id symbol)])
   (def-prod lambda-e ["(" "lambda" "(" (id symbol) ")"
                                        (body exp) ")"])
   (def-prod app-e ["(" (rator exp) (rand exp) ")"])
   (def-prod let-e ["(" "let" (id symbol) "=" (rand exp) 
                         "in" (body exp) ")"])
 

   ;; free-vars: exp -> [setof symbol]
   (define (free-vars-apf e)
     (let ((B (func-set 
                [(var-e symbol)         (v id)      (set-single id)]
                [(lambda-e symbol set)  (l id fv)   (set-rm fv id)]
                [(app-e set set)        (c fvl fvr) (set-union fvl fvr)])))
       (traverse-b e B)))
  \end{BVerbatim}
  \\

  \qquad\qquad\begin{minipage}[c][1.5cm]{6cm}
    \begin{tabular}{|l|}\hline\color{Output}
    \begin{BVerbatim}[frame=single]


      No applicable function found for:
         (let-e symbol set set)

    \end{BVerbatim}
    \\\hline
    \end{tabular}
  \end{minipage}
\end{minipage}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Lambda: adding {\it let}}
\begin{minipage}[t][6cm]{14cm}
  \begin{BVerbatim}
   ;; Lambda expressions
   (def-sum  exp [var-e lambda-e app-e let-e])

   (def-prod var-e [(id symbol)])
   (def-prod lambda-e ["(" "lambda" "(" (id symbol) ")"
                                        (body exp) ")"])
   (def-prod app-e ["(" (rator exp) (rand exp) ")"])
   (def-prod let-e ["(" "let" (id symbol) "=" (rand exp) 
                         "in" (body exp) ")"])
 

   ;; free-vars: exp -> [setof symbol]
   (define (free-vars-apf e)
     (let ((B (func-set 
                [(var-e symbol)         (v id)      (set-single id)]
                [(lambda-e symbol set)  (l id fv)   (set-rm fv id)]
                [(app-e set set)        (c fvl fvr) (set-union fvl fvr)])
                [(let-e symbol set set) (l id fvl fvr)
                                        (set-union fvl (set-rm fvr id))]))
       (traverse-b e B)))
  \end{BVerbatim}
  \\~
  %\begin{itemize}
  %  \item[*] Safe Structure Additions
  %  \item[*] With test coverage (of course)   
  %\end{itemize}
  \end{minipage}
\end{frame}
%\subsection{de Bruijn Indices}


\begin{frame}[fragile]
  \frametitle{Lambda: de Bruijn Indices (hand-written)}
\begin{minipage}[t][6cm]{14cm}
  \begin{BVerbatim}
 ;; Lambda expressions
 (def-sum  exp [ ... addr-e])

 ;;  ...
 (def-prod addr-e ["idx" (n number)])


 ;; deBruijn: exp -> exp
 ;; Replace variable exps with their de Bruijn indices (addr)
 (define (deBruijn e)
   (letrec ((db* (lambda (e env)
                   (cond [(var-e? e)    (addr-e (lookup env (var-e-id e)))]
                         [(app-e? e)    (app-e (db* (app-e-rator e) env)
                                               (db* (app-e-rand e) env))]
                         [(let-e? e)    
                          (let-e (let-e-id e)
                                 (db* (let-e-rand e) env)
                                 (db* (let-e-body e) (cons (let-e-id e) env)))]
                         [(lambda-e? e)
                          (lambda-e (lambda-e-id e)
                                    (db* (lambda-e-body e) 
                                         (cons (lambda-e-id e) env)))]))))
     (db* e '())))

  \end{BVerbatim}
  \end{minipage}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Lambda: de Bruijn Indices}
\begin{minipage}[t][6cm]{14cm}
  \begin{BVerbatim}
 ;; Lambda expressions
 (def-sum  exp [ ... addr-e])

 ;;  ...
 (def-prod addr-e ["idx" (n number)])


 ;; deBruijn: exp -> exp
 ;; Replace variable exps with their de Bruijn indices (addr)
 (define (deBruijn e)
   (let ((F (union-idF  
              [(var-e list) (v env) (addr-e (lookup env (var-e-id v)))]))
         (A (union-idA 
              [(lambda-e list) (l env) (cons (lambda-e-id l) env)])))
     (traverse-fa (let->lambda e) F A '())))


 ;; let->lambda: exp -> exp
 ;; Transform 'let' into 'lambda'
 (define (let->lambda e)
   (let ((B (union-Bc 
              [(let-e symbol exp exp)
               (l id rand body) (app-e (lambda-e id body) rand)])))
     (traverse-b e B)))

  \end{BVerbatim}
  \end{minipage}
\end{frame}


\begin{frame}[fragile]
  \frametitle{Lambda: de Bruijn Indices}
\begin{minipage}[t][6cm]{14cm}
  \begin{BVerbatim}
 ;; Lambda expressions
 (def-sum  exp [ ... addr-e])

 ;;  ...
 (def-prod addr-e ["idx" (n number)])


 ;; deBruijn: exp -> exp
 ;; Replace variable exps with their de Bruijn indices (addr)
 (define (deBruijn e)
   (let ((B (union-Bc  
              [(var-e symbol list) (v s env) (addr-e (lookup env s))]))
         (A (union-idA 
              [(lambda-e list) (l env) (cons (lambda-e-id l) env)])))
     (traverse-ba (let->lambda e) B A '())))


 ;; let->lambda: exp -> exp
 ;; Transform 'let' into 'lambda'
 (define (let->lambda e)
   (let ((B (union-Bc 
              [(let-e symbol exp exp)
               (l id rand body) (app-e (lambda-e id body) rand)])))
     (traverse-b e B)))

  \end{BVerbatim}
  \end{minipage}
\end{frame}

\section{Traversal Checks}
\begin{frame}[fragile]
  \frametitle{Traversal Checks}
  \begin{itemize}
  \item[*] What are ``errors"?
    \begin{itemize}
    \item[-] No applicable function
    \end{itemize}
  \item[]
  \item[*] Traversal Results
    \begin{itemize}
    \item[-] Must match function types
    \item[-] Check using structures \& control
    \item[-] Can provide everything statically
    \end{itemize}
\end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Example: Errors}
\begin{minipage}[t][6cm]{8cm}
  \begin{BVerbatim}
    ;; Some Data Structures
    (def-sum  W [X Y])
    (def-prod X [(n number)])
    (def-prod Y [(s symbol)])
    (def-prod Z ["z" (w W)])

    (define z1 (parse-string Z "z 5"))
    (define z2 (parse-string Z "z hello"))

    ;; number -> string ... not safe for X
    (define F (union-idF [(number) (n) (number->string n)]))


    (traverse-f z1 F) ;; ==> (Z (X "5"))    -- BAD!

    (traverse-f z2 F) ;; ==> (Z (Y 'hello)) -- OK

  \end{BVerbatim}
  \end{minipage}
\end{frame}


\begin{frame}[fragile]
  \frametitle{Example: Errors}
\begin{minipage}[t][6cm]{8cm}
  \begin{BVerbatim}
    ;; Some Data Structures
    (def-sum  W [X Y])
    (def-prod X [(n number)])
    (def-prod Y [(s symbol)])
    (def-prod Z ["z" (w W)])

    (define z1 (parse-string Z "z 5"))
    (define z2 (parse-string Z "z hello"))

    (define B (func-set
                [(X number) (x n) (number->string n)]
                [(Y symbol) (y s) (symbol->string s)]

                ;; Z W -> W
                [(Z W) (z w) w]))


    (traverse-b z1 B) ;; ==> error: No (Z string) function
    
    (traverse-b z2 B) ;; ==> error:          ""
  \end{BVerbatim}
  \end{minipage}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Example: Errors}
\begin{minipage}[t][6cm]{8cm}
  \begin{BVerbatim}
    ;; Some Data Structures
    (def-sum  W [X Y])
    (def-prod X [(n number)])
    (def-prod Y [(s symbol)])
    (def-prod Z ["z" (w W)])

    (define z1 (parse-string Z "z 5"))
    (define z2 (parse-string Z "z hello"))

    (define B (func-set
                [(X number) (x n) (number->string n)]
                [(Y symbol) (y s) (symbol->string s)]
                
                ;; fix: Z string -> string
                [(Z string) (z w) (string-append "(z " w ")")]))


    (traverse-b z1 B) ;; ==> "(z 5)"
    
    (traverse-b z2 B) ;; ==> "(z hello)"
  \end{BVerbatim}
  \end{minipage}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Example: Errors}
\begin{minipage}[t][6cm]{8cm}
  \begin{BVerbatim}
    ;; Some Data Structures
    (def-sum  W [X Y V])
    (def-prod X [(n number)])
    (def-prod Y [(s symbol)])
    (def-prod Z ["z" (w W)])

    ;; New variant of W
    (def-prod V [(c char)])


    (define z1 (parse-string Z "z '5'"))

    (define B (func-set
                [(X number) (x n) (number->string n)]
                [(Y symbol) (y s) (symbol->string s)]
                [(Z string) (z w) (string-append "(z " w ")")]))


    (traverse-b z1 B) ;; ==> error: No (V char) function
  \end{BVerbatim}
  \end{minipage}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Example: Errors}
\begin{minipage}[t][6cm]{8cm}
  \begin{BVerbatim}
    ;; Some Data Structures
    (def-sum  W [X Y V])
    (def-prod X [(n number)])
    (def-prod Y [(s symbol)])
    (def-prod Z ["z" (w W)])

    ;; New variant of W
    (def-prod V [(c char)])


    (define z1 (parse-string Z "z '5'"))

    (define B (func-set
                [(X number) (x n) (number->string n)]
                [(Y symbol) (y s) (symbol->string s)]
                [(Z string) (z w) (string-append "(z " w ")")]
                
                ;; fix: V char -> string
                [(V char) (v c) (list->string (list c))]))


    (traverse-b z1 B) ;; ==> (z 5)
  \end{BVerbatim}
  \end{minipage}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Check Algorithm}
  \begin{itemize}
  \item[*] Primitives: transformations
  \item[*] Products: constructor replacements
  \item[*] Sums: do subtype traversals unify?
  \item[*] Recursively simulate structure traversal
    \begin{itemize}
    \item[-] Traversal is what AP-F is good at!
    \end{itemize}
  \end{itemize}
\end{frame}

%\subsection{Errors?}
%\subsection{Cases}
%\subsection{Checker Algorithm}

\begin{frame}
  \frametitle{AP-F}
  \begin{itemize}
  \item[*] Flexibility
    \begin{itemize}
    \item[-] Implicit traversal
    \item[-] Closer to hand written
    \item[] 
    \end{itemize}
    
  \item[*] Modularity
    \begin{itemize}
    \item[-] Abstraction/decomposition
    \item[-] Building up function sets
    \item[]
    \end{itemize}
  \item[*] A Solution to the ``{\it Expression Problem}''
    \begin{itemize}
    \item[-] ``Extension'' of functionality and data structures
    \end{itemize}
  \end{itemize}
\end{frame}


\section{Present \& Future}
\begin{frame}[fragile]
  \frametitle{Present/Future Work}
  \begin{itemize}
  %\item[*] All this works in {\it Java} too!
  \item[*] Formal types / safety
  \item[*] Relation to other AP concepts
  \item[*] What else can be done statically
  \item[*] Performance \& optimizations
\end{itemize}
\end{frame}


\begin{frame}[fragile]
  %\frametitle{The End}
  \begin{center}\huge\color{KeyWords}
    Thanks!\\~\\
    \ \ Any Questions?
  \end{center}
\end{frame}





\end{document}



%% Anticipated Questions:

%% Q: What about non-DF ordering?

%% A: Non DF orders make sense for transformations... Why?  because
%%   transformations are type preserving, the type is there to
%%   continue traversing after a transformation, and a constructor is
%%   applied after traversing. 

%% We could see a more abstract version that applys a function to the
%%   structure before traversing... this would help with the Let
%%   issues where the structural hierarchy is different from the needs
%%   of the algorithm.  Some of these needs can be addressed with
%%   traversla composition, but some require top-down transformations
%%   to eliminate seperate traversals.