% -*- 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 27}

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

{\Large\bf 0. Announcements}

$\bullet$ Quiz 1 coming up!  Wednesday, March 11th, 1998.  5pm - 7pm
XOR 7pm - 9pm.

\vskip .1in

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

{\Large\bf 1. Student Presentation}

The two programs below were found in a trash can, perhaps because they
didn't work quite right. From their names, they appear to be attempts
to create a list whose elements are the same but in reverse order from
some starting list. With the help of box-and-pointer diagrams, explain
what each actually does.

\beginlisp
(define (reverse L1)
  (cond ((null? L1) nil)
        (else (reverse (cdr L1))
              (cons (car L1) (cdr L1)))))
\endlisp

\beginlisp
(define (reverse L1)
  (if (null? L1)
      nil
      (cons (reverse (cdr L1)) (car L1))))
\endlisp

\vskip .1in

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

{\Large\bf 2. Symbols, Quote, and Eq?}

Draw the box and pointer diagrams for each of the following
expressions, and write what is printed out by the interpreter: 

\beginlisp
(cons 'a '(b))     ==>
(cons '(a) '(b))   ==>
(list 'a 'b)       ==>
(list '(a) '(b))   ==>
(append '(a) '(b)) ==>
\endlisp

Given the following definitions, what are the values of the {\tt eq?}
expressions below?

\begin{tabular}{p{2in}p{2in}}
\hbox{
\beginlisp
(define a 2)
(define b 'two)
(define c b)
(define d 'b)
\endlisp
}
&
\hbox{
\beginlisp
(eq? a b)  ==>
(eq? d 'b) ==>
(eq? b d)  ==>
(eq? b c)  ==> 
\endlisp
}
\end{tabular}

Given the a-list data structure below, evaluate the following {\tt
assq} expressions:

\begin{tabular}{p{2.5in}p{4in}}
\hbox{
\beginlisp
(define desc
  '((where Room-34-304)
    (what (course 6.001)
          (section 4))
    (when (day Friday)
          (month February)
          (date 27)
          (year 1998)
          (hour 10)
          (minute 00))
    (why (scheme rules!))))
\endlisp
} 
&
\hbox{
\beginlisp
(define (assq name a-list)
  (cond ((null? a-list) \#f)
        ((eq? name (caar a-list))
         (car a-list))
        (else (assq name (cdr a-list)))))
\null
\null
(assq 'why desc)  ==> % (why (scheme rules!))

(assq 'what desc) ==> % (what (course 6.001) (section 4))

(assq 'date (assq 'when desc)) ==> % <ERROR>
\endlisp
}
\end{tabular}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
{\Large\bf 3. Comparing Trees}

We can use {\tt eq?} to compare symbols.  What about trees?
Write the function {\tt equal?} that takes two trees of symbols and
returns true if the same symbols are arranged in the same structure.

\beginlisp
(equal? '(this is a list) '(this is a list))
;Value: \#t
\null
(equal? '(this (is a) list) '(this (is a) list))
;Value: \#t
\null
(equal? '(this is a list) '(this (is a) list))
;Value: \#f
\endlisp

\beginlisp
(define (equal? a b)
%   (or (and (null? a) (null? b))
%       (and (symbol? a) (symbol? b) (eq? a b))
%       (and (pair? a) (pair? b) 
%            (equal? (car a) (car b))
%            (equal? (cdr a) (cdr b))))
\null
\null
\null
\null
\null
)
\endlisp

\vskip .1in

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

{\Large\bf 4. Occurrences}

Write the function {\tt occurrences} that takes a symbol and a tree
and counts the number of times that symbol appears in the tree.  For
example, 
\beginlisp
(occurrences 'a '((a b) ((a a) c b (((a))))))  ==>  4
\endlisp

\beginlisp
(define (occurrences symbol tree)
%   (cond ((null? tree) 0)
%         ((eq? symbol tree) 1)
%         ((not (pair? tree)) 0)
%         (else
%          (+ (occurrences symbol (car tree))
%             (occurrences symbol (cdr tree)))))
\null
\null
\null
\null
\null
)
\endlisp


\vskip .1in
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{\Large\bf 5. All Pairs}

Write the function {\tt all-pairs} that takes a list and returns a
list of all pairs of the elements in the list.  For example, 
\beginlisp
(all-pairs '(1 2 3 4)) ==>  ((1 2) (1 3) (1 4) (2 3) (2 4) (3 4))
\endlisp

\beginlisp
(define (all-pairs s)
%   (if (null? s)
%       nil
%       (append (map (lambda (x) (list (car s) x)) (cdr s))
%               (all-pairs (cdr s))))
\null
\null
\null
\null
\null
)
\endlisp

\vskip .1in

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

{\Large\bf 6. Fringe}

Write the function {\tt fringe} that takes a tree structure and returns a flat
list of the leaves of the tree.  For example 
\beginlisp
(fringe (list 1 (list 2) 3)) ==> (1 2 3)
\endlisp

\beginlisp
(define (fringe x)
%   (cond ((null? x) nil)
%         ((not (pair? x)) (list x))
%         (else 
%           (append (fringe (car x))
%                   (fringe (cdr x)))))
\null
\null
\null
\null
\null
)
\endlisp

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

\end{document}
