CS 61A			Spring 1992		Midterm 1 solutions


1. What will Scheme print?

> (* (+ 2 3) (- 7 (* 5 0)))
35

	This is (* 5 (- 7 0)) or (* 5 7).  (+ 2 3) --> 5, etc.


> (if (+ 2 3) (+ 4 5) (+ 6 7))
9

	(+ 2 3) is 5, which isn't #f, so it's true, so the second
	argument expression (+ 4 5) is evaluated to give the answer.


> (define six 6)
six

> (let ((- +)
	(ringo six))
    (- six ringo))
12

	Lots of people got this wrong.  The LET means, "substitute the
	actual arguments (+ and 6) for the formal parameters (- and ringo)
	in the body"; that gives us (+ 6 6) which is neither an error
	nor zero!


> (- 6 4)
2

	The substitution of + for - is only inside the LET; globally,
	- still means subtraction.


> (first (butlast (last (butlast '(the long and winding road)))))
w

	(bl '(the long and winding road)) --> (the long and winding)
	(last '(the long and winding))    --> winding
	(butlast 'winding)                --> windin
	(first 'windin)                   --> w


> (+ (bl 472) (first 38))
50

	This is (+ 47 3).


> (lambda (a b) (word b (first a)))
#

	This was another popular one to get wrong.  The LAMBDA creates
	a procedure, but does not invoke the procedure on any particular
	arguments.  It returns the procedure itself.


> ((lambda (d c) (word (last c) d)) 'here 'not)
there

	D is HERE, and C is NOT.


Scoring: 1/2 point each, except for (define six 6).  If you made the same
mistake on all of them (e.g., put all the results in parentheses), we
gave part credit.



2.  Add-numbers.

(define (add-numbers sent)
  (cond ((empty? sent) 0)
	((number? (first sent))
	 (+ (first sent) (add-numbers (bf sent))) )
	(else (add-numbers (bf sent))) ))

Alternate solution:

(define (add-numbers sent)
  (add (filter number? sent)) )

(define (add sent)
  (if (empty? sent)
      0
      (+ (first sent) (add (bf sent))) ))

[Note for hotshots:  It's tempting to try
   (define (add-numbers sent)
     (sum first (filter number? sent) bf '()) )
using the SUM procedure from the book, but it doesn't quite work because
the base case requires that A and B be numbers, not sentences.]


Typical errors included no base case, returning the empty sentence instead
of zero in the base case [think about the TYPE of the return value; if
it's generally a number, it has to be a number in the base case too],
leaving out one of the two recursive calls, or using 1+ instead of +
so that you counted the number of numbers instead of adding them.

Scoring:  Questions 2-4 follow "CS 61A Standard Scoring":

	5   Correct and elegant.
	3-4 Has the general idea.
	1-2 Has some idea or other.
	0   Has no idea.

In this case "the general idea" means doing a filter-type recursion.


3.  Inductive definition of f.

(define (f a b)
  (if (= b 0)
      1
      (* a (f a (- b 1))) ))

The function F is the exponentiation function, A to the Bth power;
we also accepted "multiply A by itself B times."  We did not accept
a sentence that just translated the inductive definition into words;
that's not "the mathematical meaning" as we specified.


The worst common mistake in the code was to leave out the recursive call,
although several people had serious syntax errors such as
	(define f(a,b) ...)     WRONG!


Scoring:  For a correct program and an incorrect sentence we generally
took off one point, unless your sentence was SO off-base as to call in
question your understanding of your own program.



4.  higher order function

(define (choose-function pred f1 f2)
  (lambda (x)
    (if (pred x)
	(f1 x)
	(f2 x) )))

There really is no other correct way to do this one.  The crucial thing
is to keep track of the domain [the allowable argument values] and the
range [the allowable result values] of the functions involved:

domain of choose-function:  Three functions.
range of choose-function:   Another function.

domain of choose-function's result function:  One number.
range of choose-function's result function:   One number.
 [Actually they don't have to be numbers, but they are in the
  examples listed.]

So, choose-function has to be
	(define (choose-function FUNCTION FUNCTION FUNCTION)
	  (lambda (NUMBER) NUMBER))

A lot of people wanted to say
	(define (choose-function pred f1 f2)
	  (if pred f1 f2))    WRONG!
which is well-motivated because it returns a function, either f1 or f2,
as desired.  But you can't just say (if pred ...) because that asks
whether the function PRED itself is true or false [it's true, of course,
because everything that isn't #f is true] instead of asking whether the
result of applying pred to some argument is true or false.