--------------------------------------------------------------------------
Software Design and Development                      Winter 2001
COM 1205                                             Prof. Karl Lieberherr
---------------------------------------------------------------------------
Final

THE GAME OF REDUNDANCY AND UNKNOWNS
-----------------------------------

Some of the questions in this exam ask you to determine unknowns
of the form UNKNOWN1, UNKNOWN2, ... This makes it easier for you
to answer the questions, since you get extra context information.
Yet you need to master the behavioral objectives of the course to answer
the questions. Guessing an answer is not a successful strategy and
therefore a "game of redundancy" test is more interesting than
a multiple choice test.

The questions have the following pattern: I show you several artifacts
which are related to software design and
development. Because of the dependencies between the artifacts,
some of the information is redundant and can be recovered from the
context by applying the objectives covered in the course.
The information which you should discover is marked UNKNOWNx.

If an unknown is not uniquely determined, mark the answer with *CHOICE*.
An unknown may be anything, e.g., a number, an identifier, a character,
two identifiers with a blank between them,
a string etc. If an unknown is the empty string, give NOTHING as answer,
e.g., UNKNOWN = NOTHING.

Example:

5 + UNKNOWN1 = 8

UNKNOWN1 = 3

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

UNKNOWN2 * UNKNOWN3 = 20

UNKNOWN2 = 4 *CHOICE*
UNKNOWN3 = 5 *CHOICE*



Question 1:
==============================================================
10 UNKNOWNs, 2 points each, 20 points

Consider the following object graph as printed
by the Display visitor generated from some class graph.

: A  (
  <w_list> : W_List  {
    <first> : Nonempty_W_List  (
      <it> : W  (
        <b> : B  (
          <l> : N  (
            <first> : Y  ( )
            <rest> : N  (
              <first> : Z  ( )
              <rest> : N  (
                <first> : Y  ( )
                <rest> : E  ( ) ) ) ) )
        <e> : E  ( )
        <x> : Z  ( ) )
      <next> : Nonempty_W_List  (
        <it> : W  (
          <b> : B  (
            <l> : E  ( ) )
          <e> : E  ( )
          <x> : Y  ( ) )
        <next> : Nonempty_W_List  (
          <it> : W  (
            <b> : B  (
              <l> : E  ( ) )
            <e> : E  ( )
            <x> : W  (
              <b> : B  (
                <l> : N  (
                  <first> : Y  ( )
                  <rest> : N  (
                    <first> : Z  ( )
                    <rest> : N  (
                      <first> : Y  ( )
                      <rest> : E  ( ) ) ) ) )
              <e> : E  ( )
              <x> : Z  ( ) ) ) ) ) ) } )

Find the corresponding class dictionary: Find the UNKNOWNs below:

A = UNKNOWN1.                     
W = UNKNOWN2.                   
B = UNKNOWN3.                   
L : UNKNOWN4.                  
E = UNKNOWN5.                 
N = UNKNOWN6.                
X : UNKNOWN7.               
Y = UNKNOWN8.              
Z = UNKNOWN9.           

W_List = <first> Nonempty_W_List.
Nonempty_W_List = UNKNOWN10. 


Question 2:
==============================================================
39 UNKNOWNs, 3 points each, 117 points

Consider the following class dictionary COLL:

program.cd:

import java.util.*;
import edu.neu.ccs.demeter.dj.*;      

Examples = List(Collaboration) EOF.
Collaboration = "collaboration" 
  <name> CollName "{"
  <cd> DemeterJ_ClassDictionary
  ["interfaces" <interfaces> List(Java_Interface)]
  ["classes" <classes> List(Java_Class)]
  ["subCollaborations" <subCollaborations> List(Collaboration)]
  ["adapters" <adapters> NList(AdapterItem)]
  "}".
CollName = Ident. // no duplications
ClassName = Ident. 
MethodName = Ident. 

Java_Interface = Text.
Java_Class = Text.
Java_MethodSignature = "signature" Text.
Java_MethodBody = "body" Text.

DemeterJ_ClassDictionary = "cd" Text.

AdapterItem = "class_map"
  QualifiedClassName "played_by" CList(ClassName) 
  ["with" List(MethodDetail)] .
MethodDetail : MapMethodToMethods | ImplementMethod.
MapMethodToMethods = "method_map"
  Java_MethodSignature "played_by" CList(MethodName).
ImplementMethod = "implement" Java_MethodSignature
  Java_MethodBody.
QualifiedClassName = CollName "." ClassName.

List(S) ~ {S}.
NList(S) ~ S {";" S}.
CList(S) ~ "{" S {"," S} "}".

Main = .

Remember that class Text uses {{ and }} to delimit the text.

A collaboration is defined when its name appears after the keyword
"collaboration" in class Collaboration.
A collaboration is used, if the collaboration name (an object 
of class CollName) appears inside a QualifiedClassName-object.
For an example, consider the following input:


The input in program.input is:

collaboration GrammarUsedButNotDefined {
  cd {{ Grammar = List(Production).
	Production = <lhs> NonTerminal <rhs> Body.
	Body = ...
	NonTerminal = Ident.
	Main = .
     }}
  classes
    {{ class Main {
         public static void main(String args[]) throws Exception {
         Grammar c = Grammar.parse(System.in);
	 ClassGraph cg = new ClassGraph(true, false);
         c.usedButNotDefined(ClassGraph);
         System.out.println("done");
         }  
       }
    }}
  subCollaborations
    collaboration UsedButNotDefined {
      cd {{ Sys = List(Definition).
    	    Definition = Item Body.
	    Item = Ident.
	    Body = List(Item).
         }}
      interfaces 
        {{interface SysI {
    	     public void usedButNotDefined(ClassGraph cg);
	     abstract String get_defs();
	     abstract String get_uses();}
        }}
      classes
        {{ class Sys implements SysI {
             public void usedButNotDefined(ClassGraph cg){}
             HashSet definitions(ClassGraph cg){
 	       cg.traverse(this,get_defs(), new Visitor() {});
	     }
           }
        }}
     }  
  adapters
    class_map 
      UsedButNotDefined2.Sys played_by {Grammar}
	with 
          implement 
             signature {{ abstract String get_defs() }}
             body {{ return new String
		 ("from Grammar bypassing Body to NonTerminal");
             }}
	;
    class_map
      UsedButNotDefined.Item played_by {NonTerminal}
}

The following collaborations are defined:
 GrammarUsedButNotDefined
 UsedButNotDefined

The following collaboration is undefined:
 UsedButNotDefined2

Your task is to write a program that finds all defined and undefined
collaborations in a given Examples-object.

Fill in the following UNKNOWNs:


Main {
  public static void main(String args[]) throws Exception {{
    Examples c = Examples.parse(System.in);
    UNKNOWN1 UNKNOWN2 = new UNKNOWN3(UNKNOWN4,UNKNOWN5);
    UNKNOWN6 = new UNKNOWN7(UNKNOWN8, "from Examples bypassing -> *,tail,* to *");

    Set dns = c.getDefinedNames(cg);
    UNKNOWN9 it;
    System.out.println(" defined");
    it = dns.UNKNOWN10();
    while (it.UNKNOWN11()) {
      String el = (String) it.UNKNOWN12();
      System.out.println(" defined id " + el);
    }

    System.out.println(" undefined");
    Set udns = c.getUndefinedNames(cg);
    it = udns.UNKNOWN13();
    while (it.UNKNOWN14()) {
      String el = (String) it.UNKNOWN15();
      System.out.println(" undefined id " + el);
    }
  }}
}


Examples {
{{
  public Set UNKNOWN16(ClassGraph cg) {
    final Set def = new HashSet();
    List defs =
      cg.UNKNOWN17(this, "UNKNOWN18");
    UNKNOWN19 it = defs.UNKNOWN20();
    UNKNOWN21 (it.UNKNOWN22()) {
      UNKNOWN23 el = (UNKNOWN24) it.UNKNOWN25();
      String cname = el.get_name().get_ident().toString();
      def.UNKNOWN26(cname);
    }
    return def;
  }
  public Set UNKNOWN27(ClassGraph cg) {
    final Set def = UNKNOWN28(cg);
    final Set undef = new HashSet();
    List used = 
      cg.UNKNOWN29(this, "UNKNOWN30");
    UNKNOWN31 it = used.UNKNOWN32();
    UNKNOWN33 (it.UNKNOWN34()) {
      UNKNOWN35 el = (UNKNOWN36) it.next();
      String cname = el.get_collname().get_ident().toString();
      if (!def.UNKNOWN37(cname))
        undef.UNKNOWN38(cname);
    }
    return undef;
  }
}}
}

The program violates the Law of Demeter. Point out all violations.
Put your answers into UNKNOWN39.


Question 3:
==============================================================
11 UNKNOWNs, 3 points each, 33 points

Consider the traversal specification for the class graph COLL:

from Collaboration to Java_MethodBody

Give in alphabetical order the names of the Java
classes whose objects will be traversed:
Those are the classes for which you would have to write
code if you did the traversal explicitly in Java.

UNKNOWN1
UNKNOWN2
UNKNOWN3
UNKNOWN4
UNKNOWN5
UNKNOWN6
UNKNOWN7
UNKNOWN8
UNKNOWN9
UNKNOWN10
UNKNOWN11

(Remember: there are so many classes, because with X_List you also have
Nonempty_X_List.)


Question 4:
==============================================================
6 UNKNOWNs, 6 points each, 36 points

Consider the following method xyz in the context
of the class graph COLL of question 2.
The programmer has given a bad name to the method.

Examples {
{{
  public void xyz(ClassGraph cg){
    cg.traverse(this,"from Examples to Collaboration", new Visitor(){
      int x;
      public void start(){x=0;}
      void before(Collaboration c){
	x++; 
	System.out.println("Collaboration " + 
	  c.get_name().get_ident() + " xyz " + x);
      } 
      void after(Collaboration c){
        x--;
      }
    });
  }
}}
}

What is a better name?
Put your answer into UNKNOWN1.

Explain in a few words what the method xyz does.
Put your answer into UNKNOWN2.

What is the output produced by the above method xyz if
used on the input in program.input from question 2:
Find the UNKNOWNs:

Collaboration UNKNOWN3 xyz UNKNOWN4
Collaboration UNKNOWN5 xyz UNKNOWN6




Question 5:
==============================================================
12 UNKNOWNs, 3 points each, 36 points

Write a traversal strategy that finds for a given Collaboration-object
all ClassName-objects that are not contained in a QualifiedClassName-object.

Put your answer into UNKNOWN1.


Give in alphabetical order the edges
that will be traversed. Give the UNKNOWNs below.

Edges:

 -> AdapterItem,UNKNOWN2,UNKNOWN3
 -> AdapterItem_NList,first,Nonempty_AdapterItem_NList
 -> ClassName_CList,first,Nonempty_ClassName_CList
 -> UNKNOWN4,UNKNOWN5,UNKNOWN6
 -> UNKNOWN7,UNKNOWN8,UNKNOWN9
 -> UNKNOWN10,UNKNOWN11,UNKNOWN12
 -> Nonempty_AdapterItem_NList,it,AdapterItem
 -> Nonempty_AdapterItem_NList,next,Nonempty_AdapterItem_NList
 -> Nonempty_ClassName_CList,it,ClassName
 -> Nonempty_ClassName_CList,next,Nonempty_ClassName_CList
 -> Nonempty_Collaboration_List,it,Collaboration
 -> Nonempty_Collaboration_List,next,Nonempty_Collaboration_List


Question 6:
==============================================================
2 UNKNOWNs, 10 points each, 20 points

Consider the following input to the parser generated from class dictionary
COLL (question 2):

collaboration UsePublisherSubscriber {
  cd {{ Point = .
	InterestedInPointChange = .
	Main = .
     }}
  classes
    {{ class Main {
         public static void main(String args[]) throws Exception {
         Point c = Point.parse(System.in);
         c.usedButNotDefined(ClassGraph);
         System.out.println("done");
         }  
       }
    }}
    {{ class Point {
	 void set(...) {}
       }
    }}
    {{ class InterestedInPointChange {
	 void public notifyChange() {}
       }
    }}
  subCollaborations
    collaboration PublisherSubscriber {
      cd {{ Publisher = Vector(Subscriber).
	    Subscriber = .
         }}
      interfaces 
        {{interface PublisherI {
    	     public void attach(Subscriber subsc);
    	     public void detach(Subscriber subsc);
    	     abstract void changeOp(...);
	     public void replaced_changeOp(... 
	       Method expected_changeOp, ...) {
		 expected_changeOp.invoke(thisObject, args);
		 for (int i=0; i<subscribers.size(); i++) {
		   ... newUpdate(thisObject); }
               }
        }}
      classes
        {{ class Publisher implements PublisherI {
	     }
           }
        }}
     }  
  adapters
    class_map n1
// the following is line 48 !!!!!!!!!!!!!!!!!!!!
      PublisherSubscriber.Publisher played_by {Point}
	with method_map signature {{void changeOp();}} played_by {set};
    class_map n2
      PublisherSubscriber.Subscriber played_by {InterestedInPointChange}
	with 
      implement 
        signature {{ void subUpdate(Publisher publ) }}
        body {{ notifyChange(); ...
             }}
}

The parser created the following error message:

DemeterJ version 0.8.3
Copyright (c) 2000 Northeastern University
Reading project file program.prj...
Running the test...
Exception in thread "main" ParseException: Encountered "PublisherSubscriber" at line 48, column 7.
Was expecting:
    "." ...
    
	at Parser.generateParseException(Parser.java:916)
	at Parser.jj_consume_token(Parser.java:852)
	at Parser._QualifiedClassName(Parser.java:286)
	at Parser._AdapterItem(Parser.java:207)
	at Parser._Nonempty_AdapterItem_NList(Parser.java:468)
	at Parser._AdapterItem_NList(Parser.java:355)
	at Parser._Collaboration(Parser.java:105)
	at Parser._Nonempty_Collaboration_List(Parser.java:408)
	at Parser._Collaboration_List(Parser.java:306)
	at Parser._Examples(Parser.java:50)
	at Examples.parse(Examples.java:14)
	at Main.main(Main.java:17)

Note that I have marked line 48 in the input.
Describe in UNKNOWN1 what is wrong with the input.
Describe in UNKNOWN2 how to make a simple deletion from the input
to make it syntactically correct.