MASSACHVSETTS INSTITVTE OF TECHNOLOGY
Department of Electrical Engineering and Computer Science
6.001---Structure and Interpretation of Computer Programs
Spring Semester, 1999
Recitation -- Friday, March 12
In the past, we have used the function eq? to test equality between two symbols and = to test equality between two numbers. The built-in function eqv? is a tests the equality of any two atoms.
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 equal? that does this. Here are some examples. How could we write equal? ?
(define (equal? x y) HiddenAnswer (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)) EndOfAnswer)
Here are examples using Quote (') Quasiquote (`) and Unquote (,). Quasiquote is the same as quote, except it cancels out with unquote. Consider the following examples: (define y 5)
'y
y
'(x y z) 
(list 'x 'y 'z)
`y 
y
`,y 
5
`(x y z) 
(list `x `y `z)
`(x ,y z) 
(list `x `,y `z) 
(list `x 5 `z)
`(x (+ 2 5) z) 
(list `x `(+ 2 5) `z) 
(list `x (list `+ `2 `5) `z)
`(x ,(+ 2 5) z) 
(list `x `,(+ 2 5) `z) 
(list `x 7 `z)
A couple of weeks ago, we saw an example of why we couldn't write our own if statement, because if needs to be a special form. Recall the following:
(define (c-if pred conseq alt)
(if (zero? pred) alt conseq))
(c-if (= 1 1) 5 (/ 1 0))
<error> [even though you might think it should return 5]
But we could write a procedure like this. Look carefully at what this is doing.
(define (my-if pred conseq-proc alt-proc) (if (zero? pred) (alt-proc) (conseq-proc)))
How would you rewrite (c-if (= 1 1) 5 (/ 1 0)) using my-if so that it does the right thing (returns 5)?
HiddenAnswer (my-if (= 1 1) (lambda () 5) (lambda () (/ 1 0))) EndOfAnswer
We are going to build a function called replace which searches through a tree and replaces items according to certain matching rules. A call to replace looks like this: (replace match? pattern change tree), where match? is a predicate called on the elements of the tree, pattern is the pattern to be matched, change is a function that changes the part of the tree that matched, and tree is the tree to be operated upon. We can use this function to write procedures that replace one symbol ( 'hate) with another ( 'love) or to find the absolute value of the leaves of a tree:
Fill in the code for the function replace:
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 '? to match any one element of a list. To do this, we write a function called requal? that takes a list x and a pattern pat and returns #t if the pattern matches list. For example,
Now write the code for the function requal?:
Fill in the correct values of pred, pattern, and change to make these expressions work:
The function 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 replace function. (1) Whenever 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 replace on the result of replace until nothing changes.