% -*- 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.  

\vskip 0.1in

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

{\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)))))
\null
\null
\null
\null
\null
)
\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)))))
\null
\null
\null
\null
)
\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) '*)
\null
            < INSERT CODE HERE >
\null
%         (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}
