\batchmode










\documentstyle[11pt,psfig,epsf,landscape,twoside,color]{article}
\makeatletter

\pagestyle{myheadings}

%
\evensidemargin 35pt

%
\setcounter{secnumdepth}{0}

%

\setlength{\oddsidemargin}{0in}
%
\setlength{\textwidth}{6.5in}

%


\setlength{\topmargin}{-0.5in}
%
\setlength{\headheight}{0.25in}
%
\setlength{\headsep}{0.25in}
%
\setlength{\textheight}{8.5in}

%

\setlength{\parindent}{0in}

%
\setlength{\parskip}{\medskipamount}

%



%



%


%






%

\newlength{\hlessmm}
\setlength{\hlessmm}{\textwidth}
\addtolength{\hlessmm}{-2em}

\newlength{\hlessmmmm}
\setlength{\hlessmmmm}{\textwidth}
\addtolength{\hlessmmmm}{-4em}

%



%



%





%









\outer

\outer

\outer

{\obeyspaces\gdef {\ }}

%



 

%
\newlength{\illuswidth}
\setlength{\illuswidth}{\textwidth}
\addtolength{\illuswidth}{-7pt}

%


%



%


%



%


%








%














\setlength{\textheight}{9in}
\setlength{\textwidth}{6.7in}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{-0.2in}

\definecolor{HiddenAnswer}{rgb}{1,1,1}
\definecolor{HighlitedAnswer}{rgb}{1,0,0}
\definecolor{EndOfAnswer}{rgb}{0,0,0}

\ifx\undefined\AnswerSheet

\else

\fi

%




\def\AnswerSheet{1}

\newcommand {\evalsto}{$\Longrightarrow$}

\newcommand {\hstrut}[1]{\hspace*{#1}}

\newcommand {\vstrut}[2]{\rule[#1]{0in}{#2}}

\newcommand {\hm}{\hspace*{1em}}

\newcommand {\hmm}{\hspace*{2em}}

\newcommand {\hmmm}{\hspace*{3em}}

\newcommand {\hmmmm}{\hspace*{4em}}

\newenvironment {tightlist}%
{\begin{list}{$\bullet$}{%
    \setlength{\topsep}{0in}
    \setlength{\partopsep}{0in}
    \setlength{\itemsep}{0in}
    \setlength{\parsep}{0in}
    \setlength{\leftmargin}{1.5em}
    \setlength{\rightmargin}{0in}
    \setlength{\itemindent}{0in}
}
}%
{\end{list}
}

\newcommand {\cf}{\footnotesize\tt}

\newcommand {\IP}{$\bullet$}

\newcommand {\RA}{{\Large \bf $\Rightarrow$}}

\newcommand {\goesto}{$\longrightarrow$}

\def\lisp#1{\footnotesize\tt #1}

\def\beginlispA{%
  \begin{minipage}[t]{\linewidth}
  \begin{list}{$\bullet$}{%
    \setlength{\topsep}{0in}
    \setlength{\partopsep}{0in}
    \setlength{\itemsep}{0in}
    \setlength{\parsep}{0in}
    \setlength{\leftmargin}{0in}
    \setlength{\rightmargin}{0in}
    \setlength{\itemindent}{0in}
  }\item[]
  \obeyspaces
  \obeylines \footnotesize\tt}

\def\beginlisp{%
  \begin{minipage}[t]{\linewidth}
  \begin{list}{$\bullet$}{%
    \setlength{\topsep}{0in}
    \setlength{\partopsep}{0in}
    \setlength{\itemsep}{0in}
    \setlength{\parsep}{0in}
    \setlength{\leftmargin}{1.5em}
    \setlength{\rightmargin}{0in}
    \setlength{\itemindent}{0in}
  }\item[]
  \obeyspaces
  \obeylines \footnotesize\tt}

\def\endlisp{%
  \end{list}
  \end{minipage}
  }

\def\psfileprefix{/usr/nikhil/parle/}

\def\illustration#1#2{
\vbox to #2{\vfill\special{psfile=\psfileprefix#1.ps hoffset=-72 voffset=-45}}}

\newcommand {\closure}[2]{%
\begin{tabular}[t]{l}
\raisebox{-1.5ex}{%
  \setlength{\unitlength}{0.2ex}
  \begin{picture}(25,15)(0,-7)
   \put( 5,5){\circle{10}}
   \put( 5,5){\circle*{1}}
   \put( 5,5){\vector(0,-1){10}}
   \put(15,5){\circle{10}}
   \put(15,5){\circle*{1}}
   \put(15,5){\vector(1,0){12}}
  \end{picture}}
  \fbox{\footnotesize #2} \\ 
%
\hspace*{0.8ex} \fbox{\footnotesize #1}
\end{tabular}
}

\newcommand {\proc}[2]{%
\begin{tabular}{l}
params: #1 \\ 
body: #2 \\ 
\end{tabular}
}

\newcommand {\psetheader}[2]{%
\markboth{6.001, #1---#2}{6.001, #1---#2}
\begin{center}
MASSACHVSETTS INSTITVTE OF TECHNOLOGY \\ 
Department of Electrical Engineering and Computer Science \\ 
6.001---Structure and Interpretation of Computer Programs \\ 
#1 \\ 
\medskip
{\bf #2}
\end{center}
}

\newcommand {\problem}[1]{{\bf #1}}

\newcommand {\key}[1]{\fbox{{\sc #1}}}

\newcommand {\ctrl}{\key{ctrl}--}

\newcommand {\shift}{\key{shift}--}

\newcommand {\run}{\key{run} \ }

\newcommand {\runkey}[1]{\run \key{#1}}

\newcommand {\extend}{\key{extend} \ }

\newcommand {\kkey}[1]{\key{k$_{#1}$}}

\def\fbox#1{%
  \vtop{\vbox{\hrule%
              \hbox{\vrule\kern3pt%
                    \vtop{\vbox{\kern3pt#1}\kern3pt}%
                    \kern3pt\vrule}}%
        \hrule}}

\def\emptybox#1#2{\fbox{\vbox to #2{\hbox to #1 {\null}}}}

\def\pscenter#1{\hbox to\hsize{\hss\psadobenomag{#1}\hss}}

\def\itemx{\vspace{-0.1in}\item}

\def\ANSWER#1{{\color{HiddenAnswer} #1 \color{EndOfAnswer}}}

\def\ANSWER#1{{\color{HighlitedAnswer} #1 \color{EndOfAnswer}}}

\makeatother
\newenvironment{tex2html_wrap}{}{}
\newwrite\lthtmlwrite
\def\lthtmltypeout#1{{\let\protect\string\immediate\write\lthtmlwrite{#1}}}%
\newbox\sizebox
\begin{document}
\pagestyle{empty}
\setcounter{secnumdepth}{0}
{\newpage
\clearpage
\samepage \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
{ 

\begin{minipage}[t]{\linewidth}
\begin{list}{$\bullet$}{%
\setlength{\topsep}{0in}
\setlength{\partopsep}{0in}
\setlength{\itemsep}{0in}
\setlength{\parsep}{0in}
\setlength{\leftmargin}{1.5em}
\setlength{\rightmargin}{0in}
\setlength{\itemindent}{0in}
}\item[]
\obeyspaces
\obeylines \footnotesize\tt 
(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'')))

\end{list}
\end{minipage} 
} & {

\begin{minipage}[t]{\linewidth}
\begin{list}{$\bullet$}{%
\setlength{\topsep}{0in}
\setlength{\partopsep}{0in}
\setlength{\itemsep}{0in}
\setlength{\parsep}{0in}
\setlength{\leftmargin}{1.5em}
\setlength{\rightmargin}{0in}
\setlength{\itemindent}{0in}
}\item[]
\obeyspaces
\obeylines \footnotesize\tt 
(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)))

\end{list}
\end{minipage} 
}
\\ 
\end{tabular}
}

{\newpage
\clearpage
\samepage \begin{tabular}{p{3.2in}|p{3.2in}}
\hline
\centerline{\bf Dispatch Method}
\vspace{-0.15in}
& 
\centerline{\bf Table Method}
\vspace{-0.15in}
\\ 
\hline
{

\begin{minipage}[t]{\linewidth}
\begin{list}{$\bullet$}{%
\setlength{\topsep}{0in}
\setlength{\partopsep}{0in}
\setlength{\itemsep}{0in}
\setlength{\parsep}{0in}
\setlength{\leftmargin}{1.5em}
\setlength{\rightmargin}{0in}
\setlength{\itemindent}{0in}
}\item[]
\obeyspaces
\obeylines \footnotesize\tt 
(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."))))

\end{list}
\end{minipage} 
} & {

\begin{minipage}[t]{\linewidth}
\begin{list}{$\bullet$}{%
\setlength{\topsep}{0in}
\setlength{\partopsep}{0in}
\setlength{\itemsep}{0in}
\setlength{\parsep}{0in}
\setlength{\leftmargin}{1.5em}
\setlength{\rightmargin}{0in}
\setlength{\itemindent}{0in}
}\item[]
\obeyspaces
\obeylines \footnotesize\tt 
(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)

\end{list}
\end{minipage} 
}
\end{tabular}
}

{\newpage
\clearpage
\samepage \psfig{figure=r11-1.ps,height=1.5in}
}

{\newpage
\clearpage
\samepage \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 & {\footnotesize\tt mul-rat} & {\footnotesize\tt add-rat} & {\footnotesize\tt sub-rat} \\ 
\hline
int & {\footnotesize\tt mul-int} & {\footnotesize\tt add-int} & {\footnotesize\tt sub-int} \\ 
\hline
complex & {\footnotesize\tt mul-complex} & {\footnotesize\tt add-complex} & {\footnotesize\tt sub-complex} \\ 
\hline
poly & {\footnotesize\tt mul-poly} & {\footnotesize\tt add-poly} & {\footnotesize\tt sub-poly} \\ 
\hline
sets & {\footnotesize\tt set-xsect} & {\footnotesize\tt set-union} & {\footnotesize\tt set-sub} \\ 
\hline
... & {\footnotesize\tt ...} & {\footnotesize\tt ...} & {\footnotesize\tt ...} \\ 
\hline
\end{tabular}
}
}
\end{tabular}
}

{\newpage
\clearpage
\samepage \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.


\begin{minipage}[t]{\linewidth}
\begin{list}{$\bullet$}{%
\setlength{\topsep}{0in}
\setlength{\partopsep}{0in}
\setlength{\itemsep}{0in}
\setlength{\parsep}{0in}
\setlength{\leftmargin}{1.5em}
\setlength{\rightmargin}{0in}
\setlength{\itemindent}{0in}
}\item[]
\obeyspaces
\obeylines \footnotesize\tt 
(define (element? x s)
{\color{HighlitedAnswer} 
  (not (null? 
    (filter (lambda (elt) (eq? elt x)) s)))
 \color{EndOfAnswer}})

\end{list}
\end{minipage} 

\vspace{0.05in}

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


\begin{minipage}[t]{\linewidth}
\begin{list}{$\bullet$}{%
\setlength{\topsep}{0in}
\setlength{\partopsep}{0in}
\setlength{\itemsep}{0in}
\setlength{\parsep}{0in}
\setlength{\leftmargin}{1.5em}
\setlength{\rightmargin}{0in}
\setlength{\itemindent}{0in}
}\item[]
\obeyspaces
\obeylines \footnotesize\tt 
(define (adjoin x s)
{\color{HighlitedAnswer} 
  (if (element? x s) 
      s 
      (cons x s))
 \color{EndOfAnswer}})

\end{list}
\end{minipage} 

\vspace{0.05in}

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


\begin{minipage}[t]{\linewidth}
\begin{list}{$\bullet$}{%
\setlength{\topsep}{0in}
\setlength{\partopsep}{0in}
\setlength{\itemsep}{0in}
\setlength{\parsep}{0in}
\setlength{\leftmargin}{1.5em}
\setlength{\rightmargin}{0in}
\setlength{\itemindent}{0in}
}\item[]
\obeyspaces
\obeylines \footnotesize\tt 
(define (union s t)
{\color{HighlitedAnswer} 
  (accumulate adjoin t s)
 \color{EndOfAnswer}})

\end{list}
\end{minipage} 
} & {

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


\begin{minipage}[t]{\linewidth}
\begin{list}{$\bullet$}{%
\setlength{\topsep}{0in}
\setlength{\partopsep}{0in}
\setlength{\itemsep}{0in}
\setlength{\parsep}{0in}
\setlength{\leftmargin}{1.5em}
\setlength{\rightmargin}{0in}
\setlength{\itemindent}{0in}
}\item[]
\obeyspaces
\obeylines \footnotesize\tt 
(define (intersection s t)
{\color{HighlitedAnswer} 
  (filter 
     (lambda (x) (element? x t) 
     s))
 \color{EndOfAnswer}})

\end{list}
\end{minipage} 

\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


\begin{minipage}[t]{\linewidth}
\begin{list}{$\bullet$}{%
\setlength{\topsep}{0in}
\setlength{\partopsep}{0in}
\setlength{\itemsep}{0in}
\setlength{\parsep}{0in}
\setlength{\leftmargin}{1.5em}
\setlength{\rightmargin}{0in}
\setlength{\itemindent}{0in}
}\item[]
\obeyspaces
\obeylines \footnotesize\tt 
(define (set- s t)
{\color{HighlitedAnswer} 
  (filter 
    (lambda (x) (not (element? x t) 
    s)))
 \color{EndOfAnswer}})

\end{list}
\end{minipage} 

}
\\ 
\hline
\end{tabular}
}

{\newpage
\clearpage
\samepage \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? 

{\color{HighlitedAnswer} Sorted sets using {\tt symbol<} \color{EndOfAnswer}}

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

\stepcounter{section}

\end{document}
