% -*- Mode: Tex -*-

\def\AnswerSheet{1}

\input 6001mac.tex

\begin{document}

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

{\Large\bf 1. Some of the Important Things to Know}

\begin{itemize}
\vspace{-0.15in}
\item Rules for Evaluation (substitution model) -- when in doubt {\bf stop thinking!}
\vspace{-0.1in}
\item Rules for Special Forms 
\vspace{-0.1in} 
\item Iteration vs. Recursion 
\vspace{-0.1in} 
\item Pairs, Lists, and Trees (defining, manipulating, contracts, abstractions)
\vspace{-0.1in} 
\item Higher Order Procedures (procedures returning procedures)
\vspace{-0.1in} 
\item Abstraction of List Operations ({\tt map}, {\tt accumulate},
and {\tt filter}.
\end{itemize}


{\Large\bf 2. Tricky Stuff}

What are the values of the following expressions:

\begin{tabular}{p{3.2in}|p{3.2in}}
{
\beginlisp
(if 0 1 2) \RA \ANSWER{1}
\null
(define (my-if pred conseq alt)
  (if (zero? pred) alt conseq))
\null
(my-if 0 1 2) \RA \ANSWER{2}
\null
(define (factorial n)
  (my-if n
         (* n (factorial (- n 1)))
         1))
\null
(fact 5) \RA \ANSWER{[infinite loop!]}
\endlisp
} & {
\beginlisp
(define x 5)
(define y 6)
(let ((x 7) 
      (y x))
  (+ x y))  \RA \ANSWER{12}
\null
((lambda (x y) ((y 6) x)) 4 
  (lambda (w) (lambda (z) (* 2 z))))  \RA \ANSWER{8}
\null
(list 1 (list 2 list 3) 4)  
  \RA \ANSWER{(1 (2 \#[procedure] 3) 4)}
\null
((if + - *) 4 3)  \RA \ANSWER{1}
\endlisp
}
\end{tabular}

{\Large\bf 3. Writing Some Procedures}

Write the following procedures:

\begin{tabular}{p{3.2in}|p{3.2in}}
{
The procedure {\tt count-pairs} that counts the number 
of {\tt cons} pairs in a tree structure. 

{\lisp (count-pairs (list 2 (list 3 4) (list 5))) \RA 6}

\beginlisp
\null
(define (count-pairs tree)
\ANSWER{
  (if (pair? tree)
      (+ 1 (count-pairs (car tree))
           (count-pairs (cdr tree)))
      0)}
)
\endlisp
} & {
The procedure {\tt copy-some} that copies the first {\tt n} elements
of a list 

{\lisp (copy-some 3 (list 1 2 3 4 5)) \RA (1 2 3)}

\beginlisp
\null
(define (copy-some n lst)
\ANSWER{
   (if (= n 0)
       nil
       (cons (car lst) 
             (copy-some (- n 1) (cdr lst))))
})
\endlisp
}
\end{tabular}

{\Large\bf 4. Order of Growth}

What's the order of growth of the procedure {\tt copy-some} above?
$\Theta(\ANSWER{n})$.  Consider the following procedure to copy the
last n elements of a list.  What is the order of growth of {\tt
last-n}?  $\Theta(\ANSWER{n^2})$.

\beginlisp
(define (last-k k lst) 
  (if (= (length lst) k)
      lst
      (last-k k (cdr lst))))
\endlisp

\newpage

{\Large\bf 5. Defining a New List Abstraction}

Notice that it can take a long time to find the length of one of our
list structures.  Say we want to define a new sequence abstraction,
similar to lists, but that can return the length in constant time.
Here's the contract:

\beginlisp
(head (attach x seq)) == x
(tail (attach x seq)) == seq
(seq-empty? empty-seq) == \#t
(seq-empty? (attach x seq)) == \#f
(seq-length seq) == the length in $\Theta(1)$ time.
\endlisp

\begin{tabular}{p{3.2in}p{3.2in}}
{
How can we do this?  Let's define a sequence as show to the right.
The list (1 3 5) would be represented as a list of pairs.  The {\tt
car}s are the elements of the list, and the {\tt cdr}s are the lengths
of the lists.  Fill in the blanks below to complete the abstraction.
} & {
\vspace{-0.4in}
\centerline{\psfig{figure=r09-1.ps,height=1in}}
}
\end{tabular}

\begin{tabular}{p{3.2in}|p{3.2in}}
{
\beginlisp
(define empty-seq nil)
(define seq-empty? null?)
\null
(define (head seq) \ANSWER{(caar seq)           })
(define (tail seq) \ANSWER{(cdr seq)            })
\null
(define (seq-length seq)
  (if (seq-empty? seq)
      0
      \ANSWER{(cdar seq)               }))
\null
(define (attach x seq) 
\ANSWER{  (cons (cons x (+ 1 (seq-length seq))) seq)
})
\endlisp
} & {
\beginlisp
(define (list->seq lst)
\ANSWER{
  (define (helper lst n)
    (if (null? lst) 
        nil
        (cons (cons (car lst) n)
              (helper (cdr lst) (- n 1)))))
  (helper lst (length lst))
})
\null
(define (seq->list seq)
\ANSWER{
  (map car seq)
})
\endlisp
}
\end{tabular}

\begin{tabular}{p{3.2in}p{3.2in}}
{
How about another way?  Here a sequence is a pair of two things.  The
{\tt car} is the original list, and the {\tt cdr} stores the lengths
of the list.  Fill in the blanks below to complete the abstraction.
} & {
\vspace{-0.4in}
\centerline{\psfig{figure=r09-2.ps,height=1.1in}}
}
\end{tabular}

\vspace{-0.3in}

\begin{tabular}{p{3.5in}|p{3.2in}}
{
\beginlisp
(define empty-seq (cons nil nil))
(define (seq-empty? seq) (null? (car seq)))
\null
(define (head seq) \ANSWER{(caar seq)                  })
(define (tail seq) \ANSWER{(cons (cdar seq) (cddr seq))})
\null
(define (seq-length seq)
  (if (seq-empty? seq)
      0 
      \ANSWER{(cadr seq)                            }))
\null
(define (attach x seq)
\ANSWER{
  (cons (cons x (car seq)) 
        (cons (+ 1 (seq-length seq)) (cdr seq)))
})
\endlisp 
} & {
\beginlisp
\null
\null
(define (list->seq lst)
\ANSWER{
  (define (helper n)
    (if (= n 0)
        nil
        (cons n (helper (- n 1)))))
  (cons lst (helper (length lst)))
})
\null
(define (seq->list seq) 
\ANSWER{
  (car seq)
})
\endlisp      
} 
\end{tabular}

Notice that with either of these abstractions, lists behave in the
same way as they did before, except that the length of a list can be
computed in constant time.  We traded time for space.  

\end{document}
