CS 61A		Spring 1992		Final exam solutions

1.  Prime factorization.

(a) (factors n) --> list of prime factors

(define (factors n)
  (define (helper n s)
    (cond ((= n 1) '())
	  ((= (remainder n (head s)) 0)
	   (cons (head s) (helper (/ n (head s)) s)) )
	  (else (helper n (tail s))) ))
  (helper n primes))

A lot of people ignored the hint about using the PRIMES stream and
checked every possible integer for primality.  This is pretty
inefficient but not actually wrong.

One common mistake was to include factors other than prime factors.
Another was to include each prime only once, so (factors 12) would
return (2 3) instead of (2 2 3).  A third possible mistake is to get
confused about streams versus lists; PRIMES is a stream, so you use
head/tail to read it, but the value returned by FACTORS is a list,
so you construct it with cons, not cons-stream.


(b) factor-stream with factors of all the positive integers

(define factor-stream (map factors integers))


Scoring: 3 points for (a), 2 for (b).  You don't get full credit for
(b) unless you use MAP; one of the main things you were supposed to
learn in the stream section was to think in terms of these signal
processing tools.


2.  Abstract data type.

I was astonished by the number of questions people asked about this
problem during the exam.  Many people seem not to know what it means
to implement an abstract data type -- it means to write the constructor
and selector functions (and mutators if appropriate, but we didn't ask
for that in this problem).  Many people don't understand how to change
the internal representation -- the below-the-line view -- without also
changing the way the functions are called (their domains and ranges).

So, first of all, here are the domains and ranges of the functions:

TIME: domain is two integers; range is a time (the ADT).
HOUR: domain is a time; range is an integer.
MINUTE: domain is a time; range is an integer.
HOUR?:  domain is a time; range is true or false.


(a) Internal representation of time ADT is a list of two numbers:

(define time list)
(define hour car)
(define minute cadr)
(define (hour? t) (= (minute t) 0))


(b) Internal representation of time ADT is an integer number of minutes:

(define (time h m) (+ (* h 60) m))
(define (hour t) (div t 60))
(define (minute t) (remainder t 60))

HOUR? is the same as in part a.


Scoring: The standard 5-point scale:
  5    if correct
  3-4  if you have the idea
  1-2  if you have an idea
  0    otherwise

"Having the idea" means having the correct domain and range.  Not having
the idea means having TIME take a list as an argument, for example, instead
of two numbers.

We didn't take off points if you weren't sure how to get the integer
quotient for HOUR in (b), as long as it was clear that you were trying
to do that.


3.  King Arthur's problem.

(define-class (knight num)
  (instance-vars (left '()) (right '()))
  (method (set-left-neighbor! obj) (set! left obj))
  (method (set-right-neighbor! obj) (set! right obj))
  (method (skip)
    (if (eq? self left)
	num                   ; this is where we return the winning number
	(ask left 'die) ))
  (method (die)
    (print (se 'knight num 'dies))
    (ask left (set-right-neighbor! right))
    (ask right (set-left-neighbor! left))
    (ask left 'skip) ))

One common confusion was between SELF, which is a knight object, and
NUM, which is a number that identifies the knight.  You can't print
SELF; you can't send NUM messages.

Really bad mistakes included not having instance variables for the
neighbors and not passing on the skip/die messages.

A common, subtle mistake was to do the (ask left 'skip) BEFORE printing
the message about dying.  If you do this, the dying messages come out
backwards, and the return value of the winning knight number doesn't
get returned as the top-level solution.

Scoring: standard 5-point scale.


4. cxr-function.

There are several ways to do this.  The main point is to make sure
that your function returns a function, and that when you invoke your
function recursively you don't expect it to give you a list.

(define (cxr-function name)
  (define (helper name)
    (cond ((empty? name) (lambda (x) x))
	  ((eq? (last name) 'a)
	   (lambda (x) ((helper (bl name)) (car x))) )
	  ((eq? (last name) 'd)
	   (lambda (x) ((helper (bl name)) (cdr x))) )
	  (else (error "not legal cxr name")) ))
  (helper (bf (bl name))) )

Notice that there are two left parentheses before the recursive
call to helper.  That's because (helper (bl name)) returns a
function, and we want to apply that function to some list.

That version gets rid of the C and the R at top-level, calling a
helper function with just As and Ds.  It's also possible to avoid
the helper function:

(define (cxr-function name)
  (cond ((eq? (last name) 'r) (cxr-function (bl name)))
	((eq? (last name) 'c) (lambda (x) x))
	((eq? (last name) 'a)
	 (lambda (x) ((cxr-function (bl name)) (car x))) )
	((eq? (last name) 'd)
	 (lambda (x) ((cxr-function (bl name)) (cdr x))) )
	(else (error "not legal cxr name")) ))

It's also possible to process the name left to right instead of right
to left, if you make sure to compose the car/cdr functions accordingly:

(define (cxr-function name)
  (cond ((eq? (first name) 'c) (cxr-function (bf name)))
	((eq? (first name) 'r) (lambda (x) x))
	((eq? (first name) 'a)
	 (lambda (x) (car ((cxr-function (bf name)) x))) )
	((eq? (first name) 'd)
	 (lambda (x) (cdr ((cxr-function (bf name)) x))) )
	(else (error "not legal cxr name")) ))

Another approach surrounds the COND with (lambda (x) ...) instead of
having individual lambdas inside each cond clause.  If you do that, you
can also use a helper function that just does plain ordinary list
manipulation:

(define (cxr-function name)
  (lambda (x)
    (define (helper name x)
      (cond ((empty? name) x)
	    ((eq? (last name) 'a) (helper (car x) (bl name)))
	    ((eq? (last name) 'd) (helper (cdr x) (bl name)))
	    (else (error "not legal cxr name")) ))
    (helper (bf (bl name)) x)))

Scoring: standard scale.  "Having the idea" requires both that the
return value be a function and that there be recursion.

The most common problem was not knowing how to connect up the function
returned by the recursive call with an argument, the ((helper ...) x)
business.

Other problems included trying to take car/cdr of the function name, which
is a word, not a list; forgetting to quote the letters C, A, D, or R in
the EQ? tests; building a list of the words car and cdr instead of building
a function; and getting the order of composition backwards.


5.  Substring in logic programming.

(a) Write the rules.

We had two solutions in mind:

    (rule (substring ?x (?a . ?b))
	  (or (leading-substring ?x (?a . ?b))
	      (substring ?x ?b)))

    (rule (leading-substring (?a . ?b) (?a . ?x))
	  (leading-substring ?b ?x))

    (rule (leading-substring () ?x))

Or the one using append (or append-to-form, as the book calls it):

    (rule (substring ?small ?big)
	  (and (append ?x ?y ?big)
	       (append ?a ?small ?x)))

Other solutions are possible.  Some people made a special case for a
rightmost substring as well as for a leftmost one, but that's not
necessary.  It's rarely a good idea to try to solve a programming
problem by thinking of a zillion special cases.  The leftmost-substring
rule above is useful not as a SPECIAL case but as a BASE case for the
rule before it.


(b) What will (substring ?x (a b c)) do?

It will report more than one match.  There are, in fact, seven substrings
of (a b c):  (), (a), (b), (c), (a b), (b c), and (a b c).  But as it turns
out, some of these are reported more than once:

query==> (substring ?x (a b c))

(substring (a b c) (a b c))
(substring (b c) (a b c))
(substring (a c) (a b c))
(substring () (a b c))
(substring (a b) (a b c))
(substring (c) (a b c))
(substring (a) (a b c))
(substring (b) (a b c))
(substring (a b) (a b c))
(substring () (a b c))
(substring (a) (a b c))
(substring (b) (a b c))
(substring (a) (a b c))
(substring () (a b c))
(substring () (a b c))
done

But this is not the sort of thing we'd expect you to predict in detail.


(c) What will (substring (a b c) ?x) do?

It goes into an infinite loop without reporting anything.  We have the rule

(rule (substring ?x (?a  . ?b))
      (substring ?x ?b))

If you unify this rule with the query, you get the bindings
   ?x1 = (a b c)
   ?x = (?a1 . ?b1)
And you get a new query (substring ?x1 ?b1) which is, in effect, the same as
(substring (a b c) ?b1) -- but this is the same as the original query with a
different variable name, so it matches the same rule and generates a new,
identical query.

Scoring: 3 points for (a), 1 each for (b) and (c).


6.  Metacircular evaluator.

(a) It's a change to apply, because you make new frames when you invoke
a function, and that's apply's job.

(b) It could be done in apply itself, at the call to extend-environment,
but it's probably cleaner to do it in extend-environment itself.  (We
accepted either, though.)

(c)

(define (extend-environment variables value base-env)
  (IF (NULL? VALUES)
      BASE-ENV
      (adjoin-frame (make-frame variables values) base-env) ))

Strictly speaking this solution prevents a check for an error that
might happen in make-frame, so it's fine if you want to say
  (IF (AND (NULL? VARIABLES) (NULL? VALUES)) ...)
and let make-frame give the error message if the sizes don't agree.

A few people wanted to return the current environment, rather than the
procedure's base environment.  If you do that you are changing the rules
of Scheme, so that it uses dynamic scope instead of lexical scope.  This
changes the meaning of Scheme programs.  You were asked to make a change
that just changes the inner mechanism without changing the meaning of the
Scheme language.


(d) When won't this work?

The only time this won't work is if we are going to want to ADD A NEW BINDING
to a frame that won't have been created.  What adds bindings to frames?  Not
lambda; that creates procedures.  Not calling a procedure; that makes a new
frame, rather than adding bindings to an old one.  Only DEFINE adds a binding
to a frame.  The problematic case is invoking a procedure with internal
DEFINEs.

Lots of people said "object oriented programming."  Nope, sorry, there are
no internal defines within functions of no arguments in the OOP system.


Scoring: 1, 1, 2, 1 for the four parts.