% -*- Mode: Tex -*-

%\input /home/welg/6001mac.tex
%\input /homes/welg/6001/6001mac.tex
%\input /zu/scheme/6001ARCHIVE/fall89/6001mac.tex
\input 6001mac.tex

\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}}

\setlength{\textheight}{9in}

\begin{document}

\psetheader{Spring Semester, 1998}{Recitation -- Friday, February 18}

{\Large\bf 1. Student Presentation}

Explain to the class how Scheme prints compound data structures. Use
as examples the way the following three things print:

\begin{tabular}{p{2.5in}p{2.5in}}
\hbox{
\beginlisp
(define s1 (cons 7 14))
(define s2 (list 7 14))
(define s3 (cons 7 nil))
\endlisp
}
&
\hbox{
\beginlisp
s1 -> ???
s2 -> ???
s3 -> ???
\endlisp
}
\end{tabular}

\vskip .05in

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{\Large\bf 2. Cons Pairs and Lists}

Recall the contract for {\tt cons}, {\tt car}, {\tt cdr}, and {\tt
null}.

\beginlisp
(car (cons a b)) == a 
(cdr (cons a b)) == b
(pair? (cons a b)) == \#t
\endlisp

\vskip 0.05in

There are three main methods of representing cons and list
structures.  You should be able to convert between them.

\begin{tabular}{p{2in}p{3in}}
Scheme Expression:  & {\tt (list 1 (cons 2 3) (list 4 5))} \\
Box and Pointer Diagram: & \\
& \psfig{figure=r06-1.ps,height=0.5in} \\
Scheme Printout: & (1 (2 . 3) (4 5)) 
\end{tabular}

\vskip 0.15in

{\Large\bf 3. Practice}

Draw box and pointer diagrams and write what will Scheme print for
the following expressions.

\beginlisp
(1)$==>$ (define x (cons 5 2))
\null
(2)$==>$ (car x)
\null
(3)$==>$ (cdr x)
\null
(4)$==>$ (car (cdr x))
\null
(5)$==>$ (define y (cons sqrt x))
\null
(6)$==>$ (car (cdr y))
\null
(7)$==>$ (car y)
\null
(8)$==>$ (define z (cons ((car y) 49) x))
\endlisp

\vskip 0.10in

\newpage
Write a Scheme expression that will print each of the following.
Also draw box and pointer diagrams.

\beginlisp
(1)$==>$ (1 2 3)
(2)$==>$ (1 2 . 3)
(3)$==>$ ((1 (2)) . 3)
\endlisp

\vskip 0.10in

Write Scheme expressions that correspond to the following.

\begin{tabular}{p{2.5in}p{2.5in}}
\psfig{figure=r06-2.ps,height=1in} &
\psfig{figure=r06-3.ps,height=0.75in} 
\end{tabular}

\vspace{-0.15in}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{\Large\bf 4. Functions on Lists}

We saw that we have the primitive function {\tt pair?} to see if an
object is a pair.  What if we wanted to write the function {\tt list?}
to see if an object is a list?  

What is the contract for {\tt list?}
$\forall x_1, x_2, \ldots, x_n \;\;\;$
  {\tt (list? (list $x_1$ $x_2$ $\ldots$ $x_n$)) == \#t}

What's another way to write it?  
\beginlisp
(list? nil) == \#t
(list? (cons $x$ $l$)) == \#t   <==>   (list? $l$)
\endlisp

Now, how can we write {\tt list?} in scheme?

\beginlisp
(define (list? x)
  (or (null? x)
      (and (pair? x)
           (list? (cdr x)))))
\endlisp

What is the Order of Growth of {\tt pair?} and {\tt list?} ?

\vskip 0.15in

{\Large\bf 5. More Functions on Lists}

We know we have {\tt car}, {\tt cdr}, {\tt cadr}, etc, as accessors
for list structures.  But what if we wanted to reference the $n^{th}$
element of a list?  Write the function {\tt list-ref} that takes a
list {\tt x} and an integer {\tt n} and returns the $n^{th}$ element
of the list {\tt x}.

\beginlisp
(define (list-ref x n)
  (if (= n 0)
      (car x)
      (list-ref (cdr x) (- n 1))))
\endlisp

Write the function {\tt length} that takes a list {\tt x} and returns
the length of the list.

\beginlisp
(define (length x)
  (if (null? x)
      0
      (+ 1 (length (cdr x)))))
\endlisp

{\Large\bf 6. Kons/Kar/Kdr as Higher-Order Procedures}

In lecture we saw an example of writing {\tt cons}, {\tt car}, and
{\tt cdr} as procedures.  Here's an even more elegant (albeit more
obscure) way of doing it.  Can you figure out how this is working?

\beginlisp
(define kons (lambda (x y) (lambda (f) (f x y))))
(define kar (lambda (p) (p (lambda (a b) a))))
(define kdr (lambda (p) (p (lambda (a b) b))))
\endlisp

What would this do?

\beginlisp
(define x (kons 1 2))
(x +)
\endlisp

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}
