LAB3a:

2.25.  Extract 7

(cadr (caddr '(1 3 (5 7) 9)))

I did that one by knowing that "cadr" means "the second element" and
"caddr" means "the third element," and the seven is the second element
of the third element of the overall list.

(car (car '((7)))

(cadr (cadr (cadr (cadr (cadr (cadr '(1 (2 (3 (4 (5 (6 7))))))))))))



2.53.  Finger exercises.   
Note that it matters how many parentheses are printed!

> (list 'a 'b 'c)
(a b c)

> (list (list 'george))
((george))

> (cdr '((x1 x2) (y1 y2)))
((y1 y2))

> (cadr '((x1 x2) (y1 y2)))
(y1 y2)

> (pair? (car '(a short list)))
#f

> (memq 'red '((red shoes) (blue socks)))
#f

> (memq 'red '(red shoes blue socks))
(red shoes blue socks)



2.55 (car ''abracadabra)

When you write

    'foo

it's just an abbreviation for

    (quote foo)

no matter what foo is, and no matter what the context is.  So

    ''foo

is an abbreviation for

    (quote (quote foo))

If you enter the expression

    (car ''abracadabra)

you are really saying

    (car (quote (quote abracadabra)))

Using the usual evaluation rules, we start by evaluating the subexpressions.
The symbol car evaluates to a function.  The expression

    (quote (quote abracadabra))

evaluates to the unevaluated argument to (the outer) quote, namely

    (quote abracadabra)

That latter list is the actual argument to car, and so car returns the first
element of that list, i.e., the word quote.


Another example:

    (cdddr '(this list contains '(a quote)))

is the same as

    (cdddr '(this list contains (quote (a quote))))

which comes out to

    ((quote (a quote)))


P.S.:  Don't think that (car ''foo) is a quotation mark!  First of all,
the quotation mark has already been turned into the list for which it
is an abbreviation before we evaluate the CAR; secondly, even if the
quotation mark weren't an abbreviation, CAR isn't FIRST, so it doesn't
take the first character of a quoted word!



2.27.  Deep-reverse.

This is a tough problem to think about, although you can write a really
simple program once you understand how.  One trick is to deep-reverse a
list yourself, by hand, without thinking about it too hard, and THEN ask
yourself how you did it.  It's pretty easy for you to take a list like

((1 2 3) (4 5 6) (7 8 9))

and instantly write down

((9 8 7) (6 5 4) (3 2 1))

How'd you do it?  The answer probably is, "I reversed the list and then I
deep-reversed each of the sublists."  So:

(define (deep-reverse lst)                  ;; Almost working version
  (map deep-reverse (reverse lst)))

But this doesn't QUITE work, because eventually you get down to the level
of atoms (symbols or numbers) and you can't map over an atom.  So:

(define (deep-reverse lst)
  (if (pair? lst)
      (map deep-reverse (reverse lst))
      lst))

If you tried to define deep-reverse without using map, you'll appreciate
the intellectual power it gives you.  You probably got completely lost in
cars and cdrs, none of which are used in this program.

Now that you understand the algorithm, it's possible to do what the problem
asked us to do, namely "modify your reverse procedure":

(define (deep-reverse lst)
  (define (iter old new)
    (cond ((null? old) new)
	  ((not (pair? old)) old)
	  (else (iter (cdr old) (cons (deep-reverse (car old)) new)))))
  (iter lst '()))

This program will repay careful study, especially if you've fallen into the
trap of thinking that there is an iterative form and a recursive form in which
any problem can be expressed.  Deep-reverse combines two subproblems.  The
top-level reversal is one that can naturally be expressed iteratively, and
in this procedure the invocation of iter within itself does express an
iteration.  But the deep-reversal of the sublists is an inherently recursive
problem; there is no way to do it without saving a lot of state information
at each level of the tree.  So the call to deep-reverse within iter is truly
recursive, and necessarily so.  Can you express the time and space requirements
of this procedure in Theta(...) notation?

5. Tree Warm-up

To get "Caroline" we use

(datum (cadr (children (car (children kennedy)))))

6. Almost-equal

(define (almost-equal tree1 tree2)
  (forest-ae (children tree1) (children tree2)))

(define (forest-ae ls1 ls2)
  (cond ((and (null? ls1) (null? ls2)) #t)
        ((or (null? ls1) (null? ls2)) #f)
        (else 
              (and (almost-equal (car ls1) (car ls2))
                   (forest-ae (cdr ls1) (cdr ls2))))))

Lab 3B:

1.  Add REPEAT to person class.

(define-class (person name)
  (INSTANCE-VARS (OLD-TEXT '()))
  (method (say stuff)
    (SET! OLD-TEXT STUFF)
    stuff)
  (method (ask stuff) (ask self 'say (se '(would you please) stuff)))
  (method (greet) (ask self 'say (se '(hello my name is) name)))
  (METHOD (REPEAT) OLD-TEXT))

Notice that the ASK and GREET methods don't have to set old-text,
because they use the SAY method.


2. Which double-talkers work?

(define-class (double-talker name)
  (parent (person name))
  (method (say stuff) (se (usual 'say stuff) (ask self 'repeat))) )

There are two things wrong with this approach.  One is that it assumes
that the two arguments to SE are evaluated left-to-right, since the
use of REPEAT assumes that we've just said the new stuff.  That might
work in some versions of Scheme but not in others.

The second problem is that the value remembered in old-text will be
a single copy of the argument, rather than two copies; therefore, if
we ask this double-talker to repeat, it'll only say the thing once.


(define-class (double-talker name)
  (parent (person name))
  (method (say stuff) (se stuff stuff)) )

This would work except for the REPEAT feature.  We can ask a double-talker
to ASK or to GREET and it will correctly say the right thing twice.  But
if we ask this double-talker to REPEAT, it won't say anything at all,
because it never remembered the stuff in old-text.


(define-class (double-talker name)
  (parent (person name))
  (method (say stuff) (usual 'say (se stuff stuff))) )

This one works as desired.