Sample Final Questions
CS 1410-20
Fall 2011


A radar center must track flying objects. Every flying object has a
position, which is expressed as three numbers for latitude, longitude,
and altitude. Known objects also have an identifying string, while
unknown objects have no identifier.

Provide a data definition (suitable for use with Racket) for
radar-tracked flying objects.

----------------------------------------

Provide a Java version of your data definition for radar-tracked
flying objects.

----------------------------------------

A data definition:

   ; A blue is either
   ;  - (make-small num num)
   ;  - (make-medium num blue)
   (define-struct small (x y))
   (define-struct medium (w z))

Provide enough examples to cover each case of data definition.

----------------------------------------

Provide a Racket template for the above data definition

----------------------------------------

Translate the preceding data definition to Java, and include template
methods. You can omit class constructors.

----------------------------------------

Translate your Racket examples to Java examples.

----------------------------------------

Suppose we add a new variant to blue:

   ; A blue is either
   ;  ...
   ;  - (make-large blue blue num)
   ...
   (define-struct large (p q r))

Explain breifly but completely how the Racket template changes.

----------------------------------------

Here's a new data definition:

 ; A purple is either
 ;  - num
 ;  - (make-light purple)
 ;  - (make-heavy purple purple)
 (define light (next))
 (define heavy (left right))

Here's a broken function:

 ; purple-nums : purple -> list-of-num
 ;  Returns a list of all numbers in p
 (define (purple-nums p)
  (cond
   [(light? p) (purple-nums (light-next p))]
   [else (cond
           [(number? (heavy-left p))
            (cons (heavy-left p) (purple-nums (heavy-right p)))]
           [else (cons
                  (purple-nums p)
                  (purple-nums (heavy-right p)))])]))

Because the implementation fails to follow the data definition in two
essential ways, "purple-nums" doesn't work.

 - What are the two ways in which the function is broken?
   
 - Provide two example purples, one to expose each problem:
 
----------------------------------------

The following Java code implements the same data structure and
function:

   // Assume a NList class for lists of numbers:
   interface NList {
     ...
     NList scaleNums(int factor);
   }
   class NEmpty implements NList { NEmpty() {} ... }
   class NCons implements NList { 
      NCons(int first, NList rest) { ...} 
      ...
   }
  

   interface Purple {
     // Sums all of the numbers in this purple
     NList nums();
   }
  
   class NumPurple implements Purple {
     int n;
     NumPurple(int n) {
       this.n = n;
     }
     NList nums() {
       return this.n;
     }
   }
  
   class LightPurple implements Purple {
     private Purple next;
     LightPurple(Purple next) {
       this.next = next;
     }
     NList nums() {
       return this.next.nums();
     }
   }
  
   class HeavyPurple implements Purple {
     Purple left;
     Purple right;
     HeavyPurple(Purple left, Purple right) {
       this.left = left;
       this.right = right;
     }
     NList nums() {
       return new NCons(this.left.nums(), this.right.nums());
    }
  }
  

 - The code has two type errors (i.e., contract violations that are
   detected before running). What are the two problems?
   
 - Suggest a way to fix the type errors and also make the
   method meet its purpose.
   
----------------------------------------

Extend the LightPurple class to implement ScaleLightPurple:

 - A ScaleLightPurple has a Purple (like all LightPurples) but also
   an integer that scales all of the ints in the next purple.

 - Clearly, the ScaleLightPurple class must override the nums()
   method. Note that the next field in LightPurple is private,
   which means that it cannot be accessed outside the enclosing 
   `class' form.

 - Include also a setScale() method in ScaleLightPurple for setting
   the scale of the purple. The setScale() method changes the
   purple, rather than producing a new purple (so it returns void).

----------------------------------------

  Purple p1 = new ScaleLightPurple(new NumPurple(12), 2);
  ScaleLightPurple p2 = p1;
  p1.setScale(1);
  p2.setScale(3);
  p2.nums()

The types don't match in this code. In what two places must a
cast be inserted to make the contracts match?

What is the result of the last expression?

----------------------------------------

Suppose that we drop ScaleLightPurple, but we add a Combiner interface
declaration to the above program and a combine method as follows:

   interface Combiner<T> {
     T combine(int n, T o);
   }

   interface Purple {
     ...
     <T> T combineNums(Combiner<T> c, T base);
   }
  
   class NumPurple implements Purple {
     ...
     <T> T combine(Combiner<T> c, T base) {
       return c.combine(this.n, base);
     }
   }
  
   class LightPurple implements Purple {
     ...
     <T> T combine(Combiner<T> c, T base) {
       return this.next.combine(c, base);
     }
   }
  
   class HeavyPurple implements Purple {
     ...
     <T> T combine(Combiner<T> c, T base) {
       this.left.combine(c, this.right.combine(c, base));
    }
  }
  
Note that, given

   class Conser implements Combiner<NList> {
     NList combine(int n, NList l) {
       return new NCons(n, l);
     }
   }
  
then for any Purple p,

  p.combine(new Conser(), new NEmpty())

is the same as

  p.nums()


Define a class MaxFinder that implements Combiner for finding the
maximum positive integer in a Purple (or 0 if the Purple contains no
positive integers). Use

  class Integer {
    int i;
    Integer(int i) { this.i = i; }
    int intValue() { return this.i; }
  }

and the result of

  p.combine(new MaxFinder(), new Integer(0))

should be an instance of Integer.