% -*- 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}{9.2in}

\begin{document}

\psetheader{Spring Semester, 1998}{Recitation -- Wednesday, March 11}

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

{\Large\bf 1. Student Presentation}

Describe the main differences between a patent, a copyright and a
trade secret, as it applies to protecting software.

\vskip .1in

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

{\Large\bf 2. Replacement in Trees}

In the microquiz on Friday, we saw the function deep-censor that
replaces a certain symbol with 'XX in a tree.

\beginlisp
(deep-censor 'MIT '((MIT) (dear MIT) my (heart) (belongs (to MIT))))
;Value 17: ((XX) (dear XX) my (heart) (belongs (to XX)))
\endlisp

\beginlisp
(define (deep-censor sym tree)
  (cond ((null? tree) nil)
        ((eq? sym tree) 'XX)
        ((not (pair? tree)) tree)
        (else
         (cons (deep-censor sym (car tree))
               (deep-censor sym (cdr tree))))))
\endlisp

Notice that to replace something in a tree, we need to build a whole
new tree.  

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

{\Large\bf 3. More General Replacement in Trees}

Let's try to write a more general replacer.  
A call to replace looks like this: \\
{\tt (replace match? pattern change tree)}, where \\
\hbox{\hspace{0.1in}}{\tt match?} is a predicate called on the elements of the tree \\
\hbox{\hspace{0.1in}}{\tt pattern} is the pattern to be matched \\
\hbox{\hspace{0.1in}}{\tt change} is a function that changes the part of the tree that matched, and \\
\hbox{\hspace{0.1in}}{\tt tree} is the tree.

For example, we could write {\tt deep-censor} using replace like this:

\beginlisp
(define (deep-censor sym tree)
  (replace eq? sym (lambda (x) 'XX) tree))
\endlisp

Here's another example using replace:

\beginlisp
(define (abs-tree tree)
  (replace (both numbers? <) 0
           (lambda (x) (- x))
           tree))

(define (numbers? x y)
  (and (number? x) (number? y)))

(define (both f g)
  (lambda (x y) 
    (and (f x y) (g x y))))

(abs-tree '(-3 -2 -1 0 1 2 3)) ==> (3 2 1 0 1 2 3)
\endlisp

\newpage  
Write replace:

\beginlisp
(define (replace match? pat change tree) 
  (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

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

{\Large\bf 4. Censoring lists}

Given the way we've define deep-censor, the following will not work (Why?):

\beginlisp
(deep-censor '(M I T) '(((M I T)) (dear (M I T)) my (heart) (belongs (to (M I T)))))
\endlisp

How can we fix it?

\beginlisp
(define (deep-censor sym tree)
  (replace equal? sym (lambda (x) 'XX) tree))
\endlisp

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

{\Large\bf 5. Some Pattern Matching}

What would we have to do if we wanted to replace patterns?  For
example, consider the following, given that the special symbol {\tt '?}
matches any {\bf one} element of a list.

\beginlisp
(deep-censor '(? I T) '(((M I T)) (dear (R I T)) my (heart) (belongs (to (R I T)))))
\endlisp

Try writing the function {\tt requal?} that takes a list, {\tt} x, and
a pattern, {\tt pat}, and returns {\tt \#t} if the pattern matches x.
For example,

\beginlisp
(requal? '(1 2 3 4) '(1 ? 3 ?))
;Value: \#t

(requal? '(1 (2 3) 4) '(1 ? 3))
;Value: \#t

(requal? '(1 2 3 4) '(1 ? 4))
;Value: ()
\endlisp

\beginlisp
(define (requal? x pat)
  (cond ((equal? x pat) \#t)
        ((eq? pat '?) \#t)
        ((or (atom? pat) (atom? x)) \#f)
        (else 
         (and (requal? (car x) (car pat))
              (requal? (cdr x) (cdr pat))))))
\endlisp

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

{\Large\bf 6. More Pattern Matching}

Our {\tt requal?} function can handle patterns with the symbol '? in
it.  How about patterns with the symbol '* in it (that match any
number of elements in a list)?

\beginlisp
(requal? '(1 2 3 4 5 6 7 8) '(1 * 2 * 6 ? 8))  ==> \#t
\endlisp

\beginlisp
(define (requal? x pat)
  (cond ((equal? x pat) \#t)
        ((eq? pat '?) \#t)
        ((eq? pat '*) \#t)
        ((atom? pat) \#f)
        ((and (eq? (car pat) '*) (null? x)) 
         (null? (cdr pat)))
        ((atom? x) \#f)
        ((eq? (car pat) '*)
         (or (requal? (cdr x) pat)
             (requal? x (cdr pat))))
        (else 
         (and (requal? (car x) (car pat))
              (requal? (cdr x) (cdr pat))))))
\endlisp

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

{\Large\bf 7. More Pattern Matching}

Fill in the correct {\tt pred}, {\tt pattern}, and {\tt change} below,
to make this expression work:

\beginlisp
(replace pred pattern change '(1 (2 3) (negate 4 5 6) 7 8 (negate 9)))
\null
;Value: (1 (2 3) (-4 -5 -6) 7 8 (-9))
\endlisp

\beginlisp
(replace requal? '(negate *) 
         (lambda (x) (map - (cdr x)))
         '((1) (2 3) (negate 4 5 6) (7 8) (negate 9)))
\endlisp

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

\end{document}
