CS 61A		Week 1		Homework Solutions


2.  The Scheme interpreter applies an ordinary procedure by first evaluating
all the argument expressions and then invoking the procedure.  Consider first
one of the examples that worked:

> (new-if (= 2 3) 0 5)

Scheme evaluates this expression as follows:

(a) Evaluate the symbol new-if.  Its value turns out to be an ordinary
procedure.  Therefore the rest of the combination is evaluated normally.

(b) Evaluate the three argument expressions.  Their values are #f [i.e.,
false], 0, and 5 respectively.

(c) Apply the procedure new-if to the argument values #f, 0, and 5.  By the
substitution model, this means we must substitute "#f" for "predicate",
"0" for "then-clause", and "5" for "else-clause":
	(cond (#f 0) (else 5))

(d) Evaluate this new expression, getting the value 5.

By contrast, if we'd entered the expression

> (if (= 2 3) 0 5)

Scheme would evaluate it as follows:

(a) Notice that the symbol IF is a keyword, the name of a special form.
Therefore the rest of the combination is evaluated specially.

(b) Invoke the special form with the UNEVALUATED argument expressions
"(= 2 3)", "0", and "5".

(c) The "if" evaluation rule then causes its first argument to be
evaluated.  Since the value is #f, i.e. false, it then evaluates
the expression "5", whose value is the number 5.  The expression "0"
is never evaluated.

In the example above, it doesn't make any PRACTICAL difference that the
expression "5" was evaluated to produce the number 5.  [By the way,
Scheme uses quotation marks for a special purpose, which isn't what I
mean here.  I'm just using them to delimit something you're to imagine as
having typed into the computer.]

Now, on to the square root program.  In the body of sqrt-iter, the third and
final argument to new-if is the expression
	(sqrt-iter (improve guess x) x)
Suppose we invoke sqrt-iter with an expression like
	(sqrt-iter 1 4)
Since sqrt-iter and new-if are both ordinary procedures, they are applied
just like the new-if example I described earlier:

(a) Evaluate the symbol sqrt-iter.  Its value turns out to be an ordinary
procedure.  Therefore the rest of the combination is evaluated normally.

(b) Evaluate the two argument expressions.  Their values are 1 and 4,
respectively.

(c) Apply the procedure sqrt-iter to the argument values 1 and 4.  By the
substitution model, this means we must substitute "1" for "guess" and
"4" for "x":
	(new-if (good-enough? 1 4)
		1
		(sqrt-iter (improve 1 4)
			   4))

(d) Evaluate this new expression.  Here is where the problem comes in.
Since new-if is an ordinary procedure, we follow steps (a)-(d) for this
sub-evaluation also:

(a) Evaluate the symbol new-if.  Its value turns out to be an ordinary
procedure.  Therefore the rest of the combination is evaluated normally.

(b) Evaluate the three argument expressions.  The first one turns out
(after a sequence of (a)-(d) steps) to have the value #f, i.e., false.
The second has the value 1.  The third invokes sqrt-iter, so we start
another (a)-(d) sequence of steps just like the first one.  But the first
one is still pending, waiting for us to finish down here.  That is, the
evaluation of the original (sqrt-iter 1 4) is waiting for the evaluation
of the new-if expression, and that's waiting for the evaluation of the new
sqrt-iter expression.  But THAT will involve evaluating another new-if
expression, which will...  This is an infinite regress.  You'll never get
any answer at all.

This business of nested evaluations isn't all wrong.  In the real
sqrt-iter the same thing happens, with sqrt-iter invoking if, and if
invoking sqrt-iter, and so on.  The difference is that with the real
if, a special form, Scheme gets to test whether the good-enough? expression
is true or false BEFORE it evaluates the inner sqrt-iter expression.  At
first the good-enough? expression is false, so if invokes sqrt-iter repeatedly
just as in the new-if version.  But eventually good-enough? returns a true
[that is, #t] value, and then the inner sqrt-iter expression need not be
evaluated.  With new-if, we needed to evaluate the inner sqrt-iter before
we had a chance to see if good-enough? came out true or false.  Therefore
Scheme never finds out that it's time to stop iterating.


3.

(define (squares nums)
  (if (empty? nums)
      '()
      (se (square (first nums))
	  (squares (bf nums)) )))

4.

(define (increment sent)
   (if (empty? sent)
       '()
       (se (addone (first sent))
           (increment (bf sent)))))

(define (addone wd)
   (if (number? wd)
       (+ wd 1)
       wd))

5.

(define (ordered? sent)
  (cond ((empty? (bf sent)) #t)
	((> (first sent) (first (bf sent))) #f)
	(else (ordered? (bf sent))) ))

This procedure is written assuming that the argument is a sentence that
contains at least one word, and that all of the words are numbers.


6a.

(define (first-streak sent)
   (cond ((empty? sent) 0)
         ((empty? (bf sent) 1)
         ((equal? (first sent) (first (bf sent)))
          (+ 1 (first-streak (bf sent))))
         (else 1)))

6b.

(define (best-streak sent)
   (if (empty? sent)
       0
       (max (first-streak sent)
            (best-streak (bf sent)))))


7.  Are "and" and "or" ordinary functions or special forms?  The general idea
of the solution is to type in an expression that will produce an error if all
its subexpressions are evaluated, and see if they all are.  For example,
supposing there is no definition for the symbol "x" you could say

> (or 1 2 x)

According to the ordinary evaluation rule, the expressions "1" "2" and "x"
should all be evaluated before "or" is invoked, so you should get an error
message complaining about the unbound symbol.  On the other hand, if "or"
is a special form, you'd expect it to stop as soon as it evaluates the "1"
and give 1 as its result.

If you try this in Scheme, you don't get an error message.
This means, most likely, that "or" is a special form whose arguments
are evaluated one by one.  If there were an error message could you 
conclude that "or" is ordinary?  No!  "Or" could be a special form
that evaluates its arguments right-to-left.  For that matter there is
no reason that "or" couldn't evaluate the middle argument first.  How
would you test for that?

(Of course, in reality you know that they're special forms because
the textbook told you so.)

Why might a special form be a good idea?  Here are a few reasons:

(a) Efficiency.  Suppose instead of numbers or symbols I used combinations
as the arguments to "or", and each combination takes several minutes to
compute.  If the first one happens to be true, it'd be a shame to waste all
that time computing the others.

(b) Conditions that depend on each other.  Consider the expression

> (or (= x 0) (> 5 (/ y x)))

This will work fine if "or" is special and evaluates left-to-right,
otherwise we may be dividing by zero.

Reasons why an ordinary function might be preferred:

(c) Fewer kludges.  It's very easy to read and understand a Lisp program
if you can be sure that everything that looks like (blah glorp zilch)
is evaluated by evaluating the subexpressions and then applying the
procedure "blah" to the arguments "glorp" and "zilch".  Everything that
looks like a procedure application but is really a special case just makes
things that much harder to understand.

(d) Creeping featurism.  Where do we stop?  Maybe we should make
multiplication a special form; after all, in the expression

> (* 0 x)

there's no real reason to evaluate x because we know zero times anything
is zero.  Pretty soon there are no real functions left in the language.

(e) Functional objects.  You're not expected to know this yet, but
next week you'll learn that procedures can be manipulated as data,
just as numbers can.  But special forms aren't procedures and there are
some things we can't do to them.


8.

(define (hof-increment sent)
   (every sent addone))

(define (addone wd)
   (if (number? wd)
       (+ wd 1)
       wd))

9.

(define (hof-ordered? sent)
   (if (collapse (lambda (num ordered-so-far) 
                   (if (number? ordered-so-far) 
                      (if (< num ordered-so-far) num #f)
                      ordered-so-far))    
                 (+ 1 (last sent))
                 sent)            
       #t
       #f))

The tricky part here is that the second argument to our lambda function
will sometimes be numbers and sometimes be booleans. Remember that collapse
scans the sentence from right to left; we have the lambda function return #f
if we find out of order elements in the elements we have scanned so far. Otherwise
we return the most recently scanned element.

10a)

(define (insert num sent)
   (cond ((empty? sent) (se num))
         ((< num (first sent)) (se num sent))
         (else (se (first sent) (insert num (bf sent))))))

10b)

(define (insertion-sort sent)
   (if (empty? sent)
       '()
       (insert (first sent) (insertion-sort (bf sent)))))

10c)

(define (general-insertion-sort sent comparator)
   (if (empty? sent)
       '()
       (general-insert (first sent)
                       (general-insertion-sort (bf sent) comparator)
                       comparator)))

(define (general-insert num sent comparator)
   (cond ((empty? sent) (se num))
         ((comparator num (first sent)) (se (first sent)
                                            (general-insert num (bf sent)
                                                                comparator)))
         (se num sent)))

Notice the only difference between 10c and 10b/10a is that we replaced the < 
operator with the generalized comparator argument.