Dan Grossman, CSE 341, Sample Questions, Spring 2004

Here are some exam-like questions that are not on the final.  Some are
probably harder than the actual exam questions, but it's difficult to
judge.

1. Consider this Scheme code:

(define (add x y) (+ x y))
(define (double x) (* x 2))
(define-syntax quadruple
  (syntax-rules ()
    [(quadruple x)
     (add (double x) (double x))]))

(a) give a use of the quadruple macro that returns a number not
divisible by 4

(b) Assuming Scheme macros are _not_ hygienic (even though they are),
give a use of the quadruple macro that returns an odd answer.

2. A Scheme program with blanks is below.  Assume that f is a "pure"
   function (always returns the same outputs given the same inputs).
   Fill in the blanks such that:
    * x ends up holding true if there exists a number n >= 0 such that
   (f n) evaluates to true
    * the program goes into an infinite-loop otherwise.

(define (f x) ...) ; some pure body, not a blank to be filled

(define (g k n)
  (if (f n)
      (k #t)
      (h k (+ n 2))))

(define (h k n)
  (if (f n)
      (g k n)
      (g ___________)))

(define x (let/cc k __________))

3. Write a Smalltalk class-method instance:of: for class Foo such that
Foo instance: e1 of: e2 evaluates to true if and only if e1 is an
instance of the class-object e2 evaluates to.  (As in Java, this
includes being an instance of a subclass.)  Recall every Smalltalk
object accepts the class message and every class-object accepts the
superclass message.

4. Suppose you have to produce a Java program but you hate static
   typing.  You devise a plan: 
   * Every time you're supposed to write
     down a type (local variables, fields, method arguments, etc.),
     you'll write down the same type: Everything
   * You'll implement a translation from your program into one that
   typechecks but still uses Everything for every type.
   
   Give an overview of such a translation.  Hints:
   1. Have every class implement an interface Everything.
   2. You'll have to figure out what should be in Everything.
   3. You may have to give methods new names.
   4. You will have to add methods to classes.

   How could multiple subclassing (i.e., multiple inheritance) make
   your translation (particularly part 4) more convenient.

5. Which of the following programs runs faster.  Explain.
   (letrec ([even (lambda (x) (if (zero? x) #t (not (odd  (- x 1)))))]
            [odd  (lambda (x) (if (zero? x) #f (not (even (- x 1)))))])
      (let ([odd (lambda (x) (= 1 (remainder x 2)))])
        (even 10000000)))

  Methods for instances of A:
    even: n
      n = 0 ifTrue:  [^ true]
            ifFalse: [^ (self odd: n - 1) not]
    odd: n
      n = 0 ifTrue: [^ false]
            ifFalse:  [^ (self even: n - 1) not]

  Methods for instances of B, which subclasses A:
    odd: n
      ^ (n rem: 2) = 1

  (B new) even: 10000000

6. Consider these solutions to homework 5 that are "almost correct":
   a. The case for translating functions just translates the function
   body appropriately, but returns a function of two arguments rather
   than a pair of a function of two arguments and an environment

   b. The case for translating applications just translates the two
   parts (the function position and the single-argument position) and
   produces an application with the results.

   If the solution is completely correct except for (a), at what point
   would evaluation abort with an error? What would the error be?

   If the solution is completely correct except for (b), at what point
   would evaluation abort with an error? What would the error be?

7. Recall Java has static overloading, but does not allow two methods
   with the same argument types and different return types.  Here's a
   proposed relaxation of this restriction:
    * You can define two methods in a class with the same name and
   argument types, but different return types.
    * But you can only call such methods when "initializing a
   variable", for example: T x = m(e1,...,en);
    * The method called depends on the declared type of the variable
   (T in the previous step).

   Explain why this proposal does not always work out.  That is,
   explain what is ambiguous about it and why there's not a very good
   way to resolve the ambiguity.