MIDTERM CSU 670 Software Development
Tuesday, November 4, 2008				Karl Lieberherr
=======================================================================

Open book and open notes

Question 1: 30 points (Software development technology: DemeterF)
Question 2: 32 points (Requirements analysis)
Question 3: 30 points (Object-oriented/language design)
Total:      92 points

Read questions 2 and 3 before you start. You might find them easier.

Question 1: Families of programs with DemeterF  (30 points)
======================================================================
======================================================================

Consider the following tested program and its output:

class dictionary program.cd
=========================================

package gen;
import edu.neu.ccs.demeterf.demfgen.lib.*;
import edu.neu.ccs.demeterf.*;

nogen Option(X): Some(X) | None(X).
nogen Some(X) = <just> X.
nogen None(X) = .

nogen List(X) : Cons(X) | Empty(X).
nogen Cons(X) = <first> X <rest> List(X).
nogen Empty(X) = .


AbstractClass : Concrete2 | UNKNOWN0 | Concrete1.
Concrete2 = "(" 
  <UNKNOWN1> Integer <UNKNOWN2> Y1 <UNKNOWN3> Z1 
  ")".
Y1 = <y2> Y2.
Y2 = <ya> AbstractClass.
Z1 = <z2> Z2.
Z2 = <za> AbstractClass.
Concrete1 = "link" <a_link> AbstractClass.
UNKNOWN0 = "()".

Pack = <good> boolean <min> int <max> int.

program.beh:
=======================================================================

Pack {{
  Pack(boolean g){ this(g,
              Integer.MAX_VALUE,
              Integer.MIN_VALUE); }
}}

Main.java:
==========================================================================
import gen.*;
import edu.neu.ccs.demeterf.*;
import edu.neu.ccs.demeterf.demfgen.lib.*;

public class Main {
  static void p(String s){ System.out.println(s); }
  static void p(){ System.out.println(); }
  public static void main(String args[]) throws Exception {
    AbstractClass something = AbstractClass.parse(System.in);
   p("The input in three different forms ==============================");
   p(something.display() + "\n");
   p(something.print() + "\n");
   p(something.toStr() + "\n");
   p("The result ==========================");
   p(" Check result " + Check.check(something));
  } 
}


Check.java:
=========================================================

import edu.neu.ccs.demeterf.*;
import gen.*;

class Check extends ID{
    Pack combine(AbstractClass l){ return new Pack(true); }
    Pack combine(Concrete2 t, int d, Pack lt, Pack rt){
      System.out.println("lt " + d +" " + lt.good + " "+ 
         lt.min + " " + lt.max + "\n");
      System.out.println("rt " + d +" " + rt.good + " "+ 
      rt.min + " " + rt.max + "\n");
      return new Pack((lt.good && rt.good && 
                  (lt.max < d) && (d < rt.min)),
                   Math.min(lt.min,d),
                   Math.max(rt.max,d)); }
    Pack combine(Object l, Pack p) { return p;}
    static boolean check(AbstractClass something){
      return new Traversal(new Check())
          .<Pack>traverse(something).good; }}


Consider the following input and output:

program.input:
======================================================================

(2
  (3 () ())
  link (1 () ()))


OUTPUT:
======================================================================

The input in three different forms ==============================
: Concrete2 (
   <UNKNOWN1> : int "2"
   <UNKNOWN2> : Y1 (
      <y2> : Y2 (
         <ya> : Concrete2 (
            <UNKNOWN1> : int "3"
            <UNKNOWN2> : Y1 (
               <y2> : Y2 (
                  <ya> : UNKNOWN0 ( ) ) )
            <UNKNOWN3> : Z1 (
               <z2> : Z2 (
                  <za> : UNKNOWN0 ( ) ) ) ) ) )
   <UNKNOWN3> : Z1 (
      <z2> : Z2 (
         <za> : Concrete1 (
            <a_link> : Concrete2 (
               <UNKNOWN1> : int "1"
               <UNKNOWN2> : Y1 (
                  <y2> : Y2 (
                     <ya> : UNKNOWN0 ( ) ) )
               <UNKNOWN3> : Z1 (
                  <z2> : Z2 (
                     <za> : UNKNOWN0 ( ) ) ) ) ) ) ) )

(2(3()())link(1()()))

Concrete2(2,Y1(Y2(Concrete2(3,Y1(Y2(UNKNOWN0())),Z1(Z2(UNKNOWN0()))))),Z1(Z2(Concrete1(Concrete2(1,Y1(Y2(UNKNOWN0())),Z1(Z2(UNKNOWN0())))))))

The result ==========================
lt 3 true 2147483647 -2147483648

rt 3 true 2147483647 -2147483648

lt 1 true 2147483647 -2147483648

rt 1 true 2147483647 -2147483648

lt 2 true 3 3

rt 2 true 2147483647 -2147483648

 Check result false


Question 1.A: Avoid mentioning all classes in Check.check(...)
***************************************************
5 points

Focus on the Check class in Check.java.
Notice that the program does not mention
many of the classes that are involved 
in the computation (e.g., Y1, Y2, Concrete1, etc.).

Explain how this is possible. Which method processes
the Y1-objects?

The class dictionary program.cd contains funny
field names that are not mentioned directly in class Check.
Why can we avoid the use of field names like: UNKNOWN1, UNKNOWN2, UNKNOWN3?


Question 1.B: Noise elimination 
******************************************************
10 points

The class dictionary program.cd contains noise.

Find the simplest class dictionary with meaningful
class and part names that activates
all parts of the Check.check(...) method, except the

Pack combine(Object l, ...)

method.

Question 1.C: Write the program from scratch
*******************************************************
15 points

Rewrite the program Check.check(AbstractClass something) by doing the traversal
manually. You may use the "simplest" structure
that you found above or the full cd at the beginning of this question.
Explicitly mention the cd you use.

Find the UNKNOWNs in the following program:

AbstractClass {{
public Pack check2() { return new Pack(UNKNOWN-1C-1);}  
}}

Concrete2 {{
public Pack check2(){
  Pack lp = UNKNOWN-1C-2;
  Pack rp = UNKNOWN-1C-3;
  return new Pack((lp.UNKNOWN-1C-4 && rp.UNKNOWN-1C-5 &&
    (lp.UNKNOWN-1C-6 < UNKNOWN-1C-7) && (UNKNOWN-1C-8 < rp.UNKNOWN-1C-9)),
    Math.min(lp.UNKNOWN-1C-10, UNKNOWN-1C-11),
    Math.max(rp.UNKNOWN-1C-12, UNKNOWN-1C-13));
}  
}}

UNKNOWN-1C-14


Question 2: Requirements Analysis for Classic Derivatives
======================================================================
======================================================================
8 points per price -> 32 points


Consider the relation R exactly 2 in 3 (arity 3).
(remember relation 22: that was exactly 1 in 3.)
Consider the following derivative:

d1 = classic SDG MAX-CSP((R),p,s)

Compute the maximum price p below which this derivative should not be sold,
because in any raw material for this derivative the fraction
p of the constraints can be satisfied.

Use a randomized approach as discussed in class: Compute the expected number
of satisfied constraints and compute the maximum bias.

Show all intermediate results:
The polynomial in b giving the expected value of satisfied constraints.
The derivative.
The computation of the maximum bias.
The computation of the price.


Consider the derivatives:

d3 = classic SDG MAX-CSP ((2), p3, seller).
d4 = classic SDG MAX-CSP ((4), p4, seller).
d5 = classic SDG MAX-CSP ((6), p5, seller).

Find the best price as above.


Question 3: Object-Oriented Design and Data Binding
======================================================================
======================================================================
30 points


Consider the following class dictionary NewLook defining cds.

// class dictionary NewLook
Cd_graph = <first> Adj <rest> Adj_list EOF.
Adj = "type" <vertex> Vertex <ns> Neighbors "end".
Neighbors: Product | Sum.
Product = "product" <c_ns> Any_vertex_list.
Sum = "sum" <first> Vertex "|" <second> Vertex.
Any_vertex : Labeled_vertex | Syntax_vertex.
Syntax_vertex = <string> String.
Labeled_vertex = "<" <label_name> ident ">" 
                     <class_name> Vertex.
Adj_list: Cd_graph | Empty_cd_graph .
Any_vertex_list: Nany_vertex_list | Empty_vl.
Nany_vertex_list = 
<first> Any_vertex <rest> Any_vertex_list.
Empty_vl = .
Empty_cd_graph = .
Vertex = <name> ident.

Learn the language NewLook defined by the cd NewLook.

Write an object-oriented design (class dictionary) in the notation NewLook.

1. For the CSP raw materials that your robots use. (15 points)

2. For the class dictionary for class dictionaries defining NewLook.
   (translating the first seven class definitions only.) (15 points)

   For example, your cd should contain a line like this:
   type Sum product "sum" <first> Vertex "|" <second> Vertex end