% -*- Mode: Tex -*-

\def\AnswerSheet{1}

\input 6001mac.tex

\begin{document}

\psetheader{Spring Semester, 1999}{Recitation -- Wednesday, March 10}

{\Large\bf 1. Generic Operations}

\begin{tabular}{p{3.2in}|p{3.2in}}
\hline
\centerline{\bf Type Abstraction}
\vspace{-0.15in}
& 
\centerline{\bf Rationals and Integers}
\vspace{-0.15in}
\\
\hline
{ 
\beginlisp
(define (attach-type type contents)
  (cons type contents))
\null
(define (type datum)
  (if (pair? datum)
      (car datum) 
      (error "Bad Datum")))
\null
(define (contents datum)
  (if (pair? datum) 
      (cdr datum)
      (error "Bad Datum'')))
\endlisp
} & {
\beginlisp
(define (make-rat n d) 
  (attach-type 'rat (cons n d)))
(define (numer x) (car x))
(define (denom x) (cdr x))
\null
(define (mul-rat x y)
  (make-rat (MUL (numer x) (numer y))
            (MUL (denom x) (denom y))))
\null
(define (make-int n) (attach-type 'int n))
(define (mul-int n1 n2) 
  (make-int (* n1 n2)))
\endlisp
}
\\
\end{tabular}

\begin{tabular}{p{3.2in}|p{3.2in}}
\hline
\centerline{\bf Dispatch Method}
\vspace{-0.15in}
& 
\centerline{\bf Table Method}
\vspace{-0.15in}
\\
\hline
{
\beginlisp
(define (MUL x y)
  (cond ((and (rat? x) (rat? y))
         (mul-rat (contents x) (contents y)))
        ((and (int? x) (int? y))
         (mul-int (contents x) (contents y)))
        (else (error "No method avail."))))
\endlisp
} & {
\beginlisp
(define (apply-generic op . args)
  (let ((type-tags (map type args)))
    (let ((proc (get op type-tags)))
      (if proc
          (apply proc (map contents args))
          (error "No method available")))))
\null
(define (MUL x y) (apply-generic 'mul x y))
(put 'mul '(rat rat) mul-rat)
(put 'mul '(int int) mul-int)
\endlisp
}
\end{tabular}

{\Large\bf 2. An Example}

Let's walk through the evaluation of {\lisp (mul x y)} with the tree
structures below.  Notice the pattern:

\begin{enumerate}
\vspace{-0.1in}
\item Find the correct procedure based on type.
\vspace{-0.1in}
\item Strip off the tag to get to the data.
\vspace{-0.1in}
\item Call the procedure with the data arguments (maybe recursively calling ``smart procedures'').
\vspace{-0.1in}
\item Attach the tag to the result.
\end{enumerate}

\centerline{\psfig{figure=r11-1.ps,height=1.5in}}

{\Large\bf 3. Comments on Generic Operations}

{\bf 1. Adding New Types and Operators} 

\begin{itemize} 
\vspace{-0.2in}
\item How would we add a new type (say polynomials)? \\
\ANSWER{For the dispatch method, each operator must be changed to
account for the new type.} \\
\ANSWER{For the table method, we need another put for each operator.}
\vspace{-0.1in}
\item How would we add a new operator (say divide)? \\
\ANSWER{For the dispatch method, write a new operator that has the
proper dispatch table} \\
\ANSWER{For the table method, we need another put for each type.}
\end{itemize}


\begin{tabular}{p{3.5in}p{3in}} 
\vspace{-0.6in}
{\bf 2. There are three main ways of dealing with \verb+  + operations on these
different types:}
{\small 
\begin{itemize}
\vspace{-0.07in}
\item {\bf Dumb:} Implement each box separately, and be sure to use
the right procedure.
\vspace{-0.1in}
\item {\bf Type Dispatch:} Make ``Smart Procedures'' from the Columns.
\vspace{-0.1in}
\item {\bf Object Oriented:} Make ``Smart Data'' from the Rows.
\end{itemize}
}
& {
{\footnotesize 
\begin{tabular}{|c||c|c|c|}
\hline
& MUL & ADD & SUB \\
\hline
\hline
rat & {\lisp mul-rat} & {\lisp add-rat} & {\lisp sub-rat} \\
\hline
int & {\lisp mul-int} & {\lisp add-int} & {\lisp sub-int} \\
\hline
complex & {\lisp mul-complex} & {\lisp add-complex} & {\lisp sub-complex} \\
\hline
poly & {\lisp mul-poly} & {\lisp add-poly} & {\lisp sub-poly} \\
\hline
sets & {\lisp set-xsect} & {\lisp set-union} & {\lisp set-sub} \\
\hline
... & {\lisp ...} & {\lisp ...} & {\lisp ...} \\
\hline
\end{tabular}
}
}
\end{tabular}

{\Large\bf 4. Representing Sets}

A set is a mathematical object defined as a collection of unique
objects (i.e.\ an element appears at most once in a set).  To model
sets, we need to build an implementation that supports several
operations.  Build an implementation for sets of symbols, using
unordered lists as the basic representation.  Try to use map, filter,
and accumulate where appropriate.

\begin{tabular}{p{3.2in}|p{3.2in}}
\hline 
{
$\bullet$ {\tt element?} takes as input an element and a set and returns
true if the element is in the set.

\beginlisp
(define (element? x s)
\ANSWER{
  (not (null? 
    (filter (lambda (elt) (eq? elt x)) s)))
})
\endlisp

\vspace{0.05in}

$\bullet$ {\tt adjoin} takes as input an element and a set and returns a
new set with that element added.  

\beginlisp
(define (adjoin x s)
\ANSWER{
  (if (element? x s) 
      s 
      (cons x s))
})
\endlisp

\vspace{0.05in}

$\bullet$ {\tt union} takes as input two sets and returns a new set
will all elements from both sets.

\beginlisp
(define (union s t)
\ANSWER{
  (accumulate adjoin t s)
})
\endlisp
} & {

$\bullet$ {\tt intersection} takes as input two sets and returns a new
set containing any element contained in both of the input sets. 

\beginlisp
(define (intersection s t)
\ANSWER{
  (filter 
     (lambda (x) (element? x t) 
     s))
})
\endlisp

\vspace{0.15in}

$\bullet$ {\tt set-} takes as input two sets and returns a new set
containing all elements of the first set that are not in the second set

\beginlisp
(define (set- s t)
\ANSWER{
  (filter 
    (lambda (x) (not (element? x t) 
    s)))
})
\endlisp

}
\\
\hline
\end{tabular}


\begin{tabular}{p{3.5in}p{3in}}
\vspace{-0.5in}
What are the orders of growth of these functions in time and space?

\vspace{0.05in}

Some of these operations are very expensive?  Is there any way that we
can do better than this? 

\ANSWER{Sorted sets using {\tt symbol<}}

&
\begin{tabular}{|l|c|c|}
\hline
& Time & Space \\
\hline
{\tt element?} & $\Theta(\ANSWER{n})$ & $\Theta(\ANSWER{n})$ \\ 
{\tt adjoin} & $\Theta(\ANSWER{n})$ & $\Theta(\ANSWER{n})$ \\ 
{\tt union} & $\Theta(\ANSWER{n^2})$ & $\Theta(\ANSWER{n})$ \\ 
{\tt intersection} & $\Theta(\ANSWER{n^2})$ & $\Theta(\ANSWER{n})$ \\ 
{\tt set-} & $\Theta(\ANSWER{n^2})$ & $\Theta(\ANSWER{n})$ \\
\hline
\end{tabular}
\end{tabular}

\end{document}

