CS 61A		Spring 1994	Midterm #1 solutions

1.  What will Scheme print?

> (+ (* 3 4 0 7) 8)
8


> (lambda (x) (/ x 0))
PROCEDURE

	[Some people said "error."  An error will result if this
	procedure is *invoked*, but there's nothing erroneous about
	defining it.]


> (butfirst '(help!))
()

	[The butfirst of a *sentence* containing one word is all but
	that word, i.e., the empty sentence.  (BUTFIRST 'HELP!) without
	the inner parentheses would be butfirst of a word, and would
	return ELP!, the most common wrong answer.  The second most
	common wrong answer, although we didn't take off for it, was
	'() -- that is, the correct answer with a quote in front.
	If you are reading '() in programs as if it were the name of
	the empty sentence, then you don't understand quoting.]


> ((if 3 * +) 4 5)
20

	[Since 3 is true, the value of the inner parenthesized
	expression is the multiplication function.]


> (let ((+ -))
    (+ 8 2))
6

	[Names of primitives are just ordinary variables that happen
	to have a predefined value, but that can be overridden by a
	local binding.  Notice that that isn't true about names of
	special forms; you can't say (LET ((DEFINE +)) ...) etc.]


> (+ 9 3)
12

	[The effect of a LET binding is local to the body of the LET.
	It doesn't change the meaning of + globally.]


Scoring: 1/2 point each, rounded down.


2.  Which are iterative?

(define (butfirst-n num stuff)
  (if (= num 0)
      stuff
      (butfirst-n (- num 1) (bf stuff))))

YES.  The result of the recursive invocation is the result
of the whole thing.

(define (member? thing stuff)
  (cond ((empty? stuff) #f)
	((equal? thing (first stuff)) #t)
	(else (member? thing (bf stuff)))))

YES.  Same reasoning.

(define (addup nums)
  (if (empty? nums)
      0
      (+ (first nums)
	 (addup (bf nums)))))

NO.  In this case, the result of the recursive invocation
is one argument to a + invocation that has to be done to
produce the overall result.

(Why don't we say, in the first example, "the result of the
recursive invocation is one argument to an IF invocation"?
Because IF and COND are special forms, and their special
evaluation rules mean that by the time the recursive call
happens, they've already decided that that will be the
overall answer.  But + is an ordinary procedure, and its
actual argument expressions are evaulated *before* it does
its work.)

Scoring: One point, all or nothing.


3.  Increasing?

(define (increasing? nums)
  (cond ((empty? (bf nums)) #t)
	((>= (first nums) (first (bf nums))) #f)
	(else (increasing? (bf nums)))))

There are other possible solutions, but all essentially like this.

Scoring:  Problems 3-5 are scored on this scale:
	5    correct except maybe some right parentheses missing.
	3-4  has the idea
	1-2  has an idea
	0    other

In this case, "has the idea" means that it's recursive, and that the
first two numbers are compared to determine the partial result, and
that there wasn't some awful idiosyncratic problem.  A typical 4 would
have an error in the base case, or getting the test wrong (allowing
equality, for example).  A typical 3 would be no base case at all,
thinking that BUTFIRST means SECOND, etc.


4.  Strategies for the 21 project.

I was upset by the number of questions asked about this question during
the exam.  You should all have understood the domain and range of a
strategy procedure from doing the project, and if you didn't understand,
the information was right there in the exam:

  A strategy procedure in the 21 project takes two arguments, the player's
  hand so far and the dealer's visible card, as in this example:

	(my-strategy '(3h 4d 10c) '5s)

  It returns true to indicate that the player wants another card, false
  otherwise.

So everybody who asked "what procedure do I have to call to take
another card?" *both* didn't do the project and can't read!

(a) A strategy that takes another card if and only if we have fewer than 4.

(define (four-cards player-hand dealer-card)
  (< (count player-hand) 4))

That's it!  Many people said

(define (four-cards player-hand dealer-card)
  (if (< (count player-hand) 4)
      #t
      #f))

and that's okay, but if you think about it, the extra IF doesn't really
make any difference.  It says: If < returns true, return true; if < returns
false, return false.

(b) A procedure that returns a strategy like part (a) but for any number:

(define (n-cards num)
  (lambda (player-hand dealer-card)
    (< (count player-hand) num)))

The crucial point is that n-cards itself is *not* a strategy, but it
should *return* a strategy as its value.  So it uses lambda to create
a procedure that follows the strategy rules: takes two arguments,
returns true or false.

Scoring: 2 points for (a), 3 for (b), except that if your answer to (b)
duplicates a mistake in (a) you don't lose points twice.  In (b), a
3-point answer is correct; a 2-point answer has the correct domains
and ranges, i.e., it's a function that takes one number as argument
and returns a function of two arguments, etc.


5.  Brooklyn accent.

(define (brooklyn wd)
  (cond ((<= (count wd) 1) wd)
	((equal? (first-two wd) 'oi)
	 (word 'er (brooklyn (bf (bf wd)))))
	((equal? (first-two wd) 'er)
	 (word 'oi (brooklyn (bf (bf wd)))))
	(else (word (first wd) (brooklyn (bf wd))))))

(define (first-two wd)
  (word (first wd) (first (bf wd))))

Of course you don't have to define first-two as a separate procedure,
but you must make some equivalent test.

You can't say
	(equal? (first-two wd) (or 'oi 'er))   ;; wrong!!!!!
Scheme isn't English.  Ask me or your TA for help if you don't
understand this.

It turns out that, even though we said "assume the argument word
will always contain at least one letter," you have to handle the
case of an empty word, because if the last two letters are OI or
ER, the recursive call (BROOKLYN (BF (BF WD))) will use an empty
word as argument.  But we didn't take off for missing that subtle
point, because I didn't realize it myself at first!

A typical 3-point answer would forget the need to butfirst the
word twice in the recursive call for OI and ER cases, or would
stop looking after finding one OI or ER.

A surprising number of people wanted to use SENTENCE rather than WORD
as the combiner; I don't understand why.