% -*- Mode: Tex -*-

\def\AnswerSheet{1}

\input 6001mac.tex

\begin{document}

\psetheader{Spring Semester, 1999}{Recitation -- Friday, March 12}

{\Large\bf 1. Equality Predicates}

In the past, we have used the function {\tt eq?} to test equality
between two symbols and {\tt =} to test equality between two numbers.
The built-in function {\tt eqv?} is a tests the equality of any two
atoms.

\begin{tabular}{p{1.3in}p{1.8in}p{2.3in}}
{
\beginlisp
(= 2 2)
\RA \#t
(eq? 2 2)
\RA <undefined>
(eqv? 2 2)
\RA \#t
\endlisp
} & 
{
\beginlisp
(= 'robot 'robot)
\RA <error>
(eq? 'robot 'robot)
\RA \#t
(eqv? 'robot 'robot)
\RA \#t
\endlisp
} & 
{
\beginlisp
(= (cons 2 4) (cons 2 4))
\RA <error>
(eq? (cons 2 4) (cons 2 4))
\RA \#f
(eqv? (cons 2 4) (cons 2 4))
\RA \#f
\endlisp
} 
\end{tabular}

\vspace{-0.2in}

That's annoying.  What if we want to check to see if two lists or tree
structures are the same?  There's a function called {\tt equal?} that
does this.  Here are some examples.  How could we write {\tt equal?} ?  

\begin{tabular}{p{2in}p{4in}}
{
\beginlisp
(equal? 5 5)        \RA \#t
(equal? 5 6)        \RA \#f
(equal? 'tree 'cat) \RA \#f
(equal? 'cat 'cat)  \RA \#t
\endlisp
} & 
{
\beginlisp
(equal? '(this is list 1) '(this is list 1))   \RA \#t
(equal? '(this is list 1) '(this is (list 1))) \RA \#f
(equal? '(lambda (x) x) '(lambda (x) x))       \RA \#t
(equal? (lambda (x) x) (lambda (x) x))         \RA \#f
\endlisp
} 
\end{tabular}

\vspace{-0.2in}

\beginlisp
(define (equal? x y)
\ANSWER{
  (cond ((and (atom? x) (atom? y)) (eqv? x y))
        ((and (pair? x) (pair? y)) 
          (and (equal? (car x) (car y))
               (equal? (cdr x) (cdr y))))
        (else \#f))})
\endlisp

{\Large\bf 2. Quote, Quasiquote, Unquote}

Here are examples using Quote (') Quasiquote (`) and Unquote (,).
Quasiquote is the same as quote, except it cancels out with unquote.
Consider the following examples:  {\lisp (define y 5)}

\beginlisp
'y              \RA y
'(x y z)        \RA (list 'x 'y 'z)
`y              \RA y
`,y             \RA 5
`(x y z)        \RA (list `x `y `z) 
`(x ,y z)       \RA (list `x `,y `z)       \RA (list `x 5 `z) 
`(x (+ 2 5) z)  \RA (list `x `(+ 2 5) `z)  \RA (list `x (list `+ `2 `5) `z)
`(x ,(+ 2 5) z) \RA (list `x `,(+ 2 5) `z) \RA (list `x 7 `z)
\endlisp

{\Large\bf 3. Continuations - Where do you want to go next?}

A couple of weeks ago, we saw an example of why we couldn't write our
own {\tt if} statement, because {\tt if} needs to be a special form.  
Recall the following:

\beginlisp
(define (c-if pred conseq alt) 
  (if (zero? pred) alt conseq))
(c-if (= 1 1) 5 (/ 1 0)) \RA <error>  [even though you might think it should return 5]
\endlisp

But we could write a procedure like this.  Look carefully at what this
is doing.

\vspace{-0.05in}

\beginlisp
(define (my-if pred conseq-proc alt-proc)
  (if (zero? pred) (alt-proc) (conseq-proc)))
\endlisp

How would you rewrite {\lisp (c-if (= 1 1) 5 (/ 1 0))} using {\lisp
my-if} so that it does the right thing (returns 5)?

\beginlisp
\ANSWER{(my-if (= 1 1) (lambda () 5) (lambda () (/ 1 0)))}
\endlisp

\newpage

{\Large\bf 4. Replace}

We are going to build a function called {\cf replace} which searches
through a tree and replaces items according to certain matching rules.
A call to replace looks like this: {\cf (replace match?~pattern change
tree)}, where {\cf match?}~is a predicate called on the elements of
the tree, {\cf pattern} is the pattern to be matched, {\cf change} is
a function that changes the part of the tree that matched, and {\cf
tree} is the tree to be operated upon.  We can use this function to
write procedures that replace one symbol ({\cf 'hate}) with another
({\cf 'love}) or to find the absolute value of the leaves of a tree:

\begin{tabular}{p{3.2in}p{3.8in}}
\beginlispA
(define (censor tree)
  (replace eq? 'hate (lambda (x) 'love) tree))
(censor '(I hate scheme))
\RA (I love scheme)
(censor '(I ((hate) scheme)))
\RA (I ((love) scheme))
\endlisp
&
\beginlispA
(define (abs-tree tree)
  (replace (lambda (x y) (and (number? x) (< x y)))
           0 - tree))
\null
(abs-tree '(-3 -2 (-1 0 1) 2 3))
\RA (3 2 (1 0 1) 2 3)
\endlisp
\end{tabular}

Fill in the code for the function {\cf replace}: 

\begin{tabular}{p{6in}}
\beginlisp
(define (replace match? pat change tree) 
\ANSWER{
  (cond ((null? tree) nil)
        ((match? tree pat) (change tree))
        ((not (pair? tree)) tree)
        (else (cons (replace match? pat change (car tree))
                    (replace match? pat change (cdr tree))))))
}
\endlisp
\end{tabular}

{\Large\bf 5. Requal?}

Now we want to allow patterns that have a little more flexibility by
introducing wildcards.  A wildcard is a special symbol which matches a
more general class of patterns.  We will start by using the symbol
{\cf '?} to match any one element of a list.  To do this, we write a
function called {\cf requal?} that takes a list {\cf x} and a pattern
{\cf pat} and returns {\cf \#t} if the pattern matches list. For
example,

\begin{tabular}{p{3.5in}p{3.5in}}
\beginlisp
(requal? '(1 2 3 4) '(1 2 3 ?))
\RA \#t
(requal? '(1 2 3 4) '(1 ? 3 ?))
\RA \#t
\endlisp
&
\beginlisp
(requal? '(1 (2 3) 4) '(1 ? 4))
\RA \#t
(requal? '(1 2 3 4) '(1 ? 4))
\RA \#f
\endlisp
\end{tabular}

Now write the code for the function {\cf requal?}:

\begin{tabular}{p{6.5in}}
\beginlisp
(define (requal? x pat)
\ANSWER{
  (cond ((eq? pat '?) \#t)
        ((and (atom? x) (atom? pat)) (eqv? x pat))
        ((and (pair? x) (pair? pat)) 
          (and (requal? (car x) (car pat))
               (requal? (cdr x) (cdr pat))))
        (else \#f))})
\endlisp
\end{tabular}

{\Large\bf 5. Pattern Matching}

Fill in the correct values of {\cf pred}, {\cf pattern}, and {\cf
change} to make these expressions work:

\begin{tabular}{p{2.8in}p{3.8in}}
\beginlispA
(replace pred pattern change 
         '(M (M V T) (M (X Y) T) B))
\RA (M (M I T) (M I T) B)
pred    = \ANSWER{requal?}
pattern = \ANSWER{'(M ? T)}
change  = \ANSWER{(lambda (x) '(M I T))}
\endlisp
&
\beginlispA
(replace pred pattern change 
         '(1 (2 3) (negate (4 5 6)) 7 (negate (8 9))))
\RA (1 (2 3) (-4 -5 -6) 7 (-8 -9))
pred    = \ANSWER{requal?}
pattern = \ANSWER{'(negate ?)}
change  = \ANSWER{(lambda (x) (map - (cadr x)))}
\endlisp
\end{tabular}

The function {\cf replace} performs one of the recursive paths that
were demonstrated in lecture yesterday.  You can think about the
pattern matcher from lecture as a higher-level function that performs
two more levels of recursion on our existing {\cf replace} function.
(1) Whenever {\cf replace} is called, it operates not just on one
replacement rule, but on a set of replacement rules.  (2) The
higher-level function recursively calls {\cf replace} on the result of
{\cf replace} until nothing changes.

\end{document}


