Midterm Exam COM 3360
November 8, 2001
Prof. Karl Lieberherr
========================================
Open books and open notes


Question 1:
===========

Consider the following class dictionary, behavior file, 
and output. Find the UNKNOWNS.

unknowns 1 - 8: 5 points each :	40 points
other unknowns: 2 point each  : 64 points

//////////////////     class dictionary
import edu.neu.ccs.demeter.dj.*;
import java.util.*; 
import java.io.*; 

public UNKNOWN1 		= List(Collaboration) *EOF*.
public Collaboration		= "collaboration" 
				  <name> CollabName [IsACollab] ";"
				  Structure AdapterDef.
				   
public IsACollab		= "extends" CollabName.
public Structure 		= <imports> Imports 
				   <participants> List(ParticipantDef) *l . 
public IsA			= "extends" ParticipantName.
public Impls			= "implements" <internames> CommaList(ParticipantName).
public HasA			= JavaType VarName ";".

public Imports			= List(Import).
public Import 			= "import" LongImportName ";" *l.
public LongImportName		= LongName. 


public ParticipantDef  		= 
				  ParticipantOrInterface <name> ParticipantName 
				  [IsA]	[Impls] *l. 

public ParticipantOrInterface	: IsParticipant | IsInterface.
public IsParticipant		= "participant".
public IsInterface		= "interface".

public AdapterDef 		= <adapters> List(AdapterItem). 
public AdapterItem		= "attach" [ <collabs> CommaList(CollabRef)]
				  AttachmentSpecList.
public CollabRef 		: ResharedCollab | SharedCollab |  NormalCollab 
				  common CollabName.
 public ResharedCollab		= "reshared" .
 public SharedCollab 		= "shared"  .
 public NormalCollab 		= "normal".

public AttachmentSpecList	= "{" List(Attachment) "}". 

public Attachment 		=  "{" ShortName ":" + *l 
				   <defs> List(CompositeParticipantDef) - *l "}".



public CompositeParticipantDef	= <lhs> PartSpec "+="  
				  [<rhs> CommaList(PartSpec)] <with> With *l.
public With 			= "with" <maps> BracedList(Entry).

Entry 				: UNKNOWN2.
Around				= "UNKNOWN3" <nameSpace> ShortName ":"
				  <l> NameSpec "UNKNOWN4" <r> NameSpec .

        
public Export 			= "export" <lmem> NameSpec 
				  ["as" <rmem> NameSpec] .
List(S)                         ~ { S}.
CommaList(S)                    ~ S {"," *s S}.
BracedList(P)                   ~ "{" + *l {  P  } - *l "}".

public PartSpec                 = <var> LongName.
public ShortName                = <name> Ident.
public LongName                 ~ ShortName { "." ShortName}.
public VarName                  = ShortName.
public JavaType                 = <type> LongName <array> List(ArraySpec).
public ArraySpec                = "[" "]".
public NameSpec                 = ShortName.
public CollabName               = LongName.
public ParticipantName          = ShortName.

Main = .


///////////////////// behavior file

Main {
{{
  public static void main(String[] args)  throws Exception {
  AC ac = AC.parse(System.in);
  ac.print();
  System.out.println();
  System.out.println("done 1");
  ac.display();
  System.out.println();
  System.out.println("done 2");
  ac.display_all();
  System.out.println();
  System.out.println("done 3");

     // DJ
     ClassGraph cg = new ClassGraph(true, false);
     ClassGraph cgCommandsWithoutTail = new ClassGraph(cg,
       "from AC bypassing -> *,tail,* to *");

  ac.process(new TraversalGraph("from AC to UNKNOWN5", cg));

  System.out.println("done");

  }
}}
}

ParticipantName {
  UNKNOWN6
  }

AC {
  void display_all() bypassing -> *,tail,* to * (DisplayVisitor);
  }


AC {
  void display() bypassing -> *,tail,* to UNKNOWN7 (DisplayVisitor);
  }

AC {
  void print() to * (PrintVisitor);
  }

AC {
{{
  void process(TraversalGraph where) {
      Visitor cV = new Visitor() {
        void before(ParticipantDef host){
	  System.out.println("participant name ");
	  host.get_name().print();
	  System.out.println();
	};
	public void start() {System.out.println("UNKNOWN8");}

      };
      where.traverse(this, cV);
   }
}}
}



/////////////   output (I removed the indentation from the 
/////////////   DisplayVisitor output

collaboration counts;participant Counted extends X

collaboration gettersNsetters;participant Foo implements Y

collaboration result;participant Food

attach normal gettersNsetters{{gns:	
	Food+=Foo, X, edu.neu.ccs.demeter.S with{	
		around gns:get_str do counted export main as y
	}
	
}}attach shared counts{{q:	
	Food+=Counted, R, S.T with{	
		export gns as counted export gnsset_i as reset
	}
	
}}
done 1
: AC  (
<collaboration_list> : Collaboration_List  {
<first> : Nonempty_Collaboration_List  (
<it> : Collaboration  (
<adapterdef> : AdapterDef  (
<adapters> : AdapterItem_List  { } ) )
<next> : Nonempty_Collaboration_List  (
<it> : Collaboration  (
<adapterdef> : AdapterDef  (
<adapters> : AdapterItem_List  { } ) )
<next> : Nonempty_Collaboration_List  (
<it> : Collaboration  (
<adapterdef> : AdapterDef  (
<adapters> : AdapterItem_List  {
<first> : Nonempty_AdapterItem_List  (
<it> : AdapterItem  (
<attachmentspeclist> : AttachmentSpecList  (
<attachment_list> : Attachment_List  {
<first> : Nonempty_Attachment_List  (
<it> : Attachment  ( ) ) } ) )
<next> : Nonempty_AdapterItem_List  (
<it> : AdapterItem  (
<attachmentspeclist> : AttachmentSpecList  (
<attachment_list> : Attachment_List  {
<first> : Nonempty_Attachment_List  (
<it> : Attachment  ( ) ) } ) ) ) ) } ) ) ) ) ) } )
done 2
: AC  (
<collaboration_list> : Collaboration_List  {
<first> : Nonempty_Collaboration_List  (
<it> : UNKNOWN9  (
<name> : UNKNOWN10  (
<longname> : UNKNOWN11  {
<first> : Nonempty_LongName  (
<it> : UNKNOWN12  (
<name>  : Ident "UNKNOWN13" ) ) } )
<structure> : Structure  (
<imports> : UNKNOWN14  (
<import_list> : UNKNOWN15  { } )
<participants> : UNKNOWN16  {
<first> : Nonempty_ParticipantDef_List  (
<it> : UNKNOWN17  (
<participantorinterface> : UNKNOWN18  ( )
<name> : UNKNOWN19  (
<shortname> : UNKNOWN20  (
<name>  : Ident "Counted" ) )
<isa> : IsA  (
<participantname> : ParticipantName  (
<shortname> : ShortName  (
<name>  : Ident "X" ) ) ) ) ) } )
<adapterdef> : AdapterDef  (
<adapters> : AdapterItem_List  { } ) )
<next> : Nonempty_Collaboration_List  (
<it> : Collaboration  (
<name> : CollabName  (
<longname> : LongName  {
<first> : Nonempty_LongName  (
<it> : ShortName  (
<name>  : Ident "gettersNsetters" ) ) } )
<structure> : Structure  (
<imports> : Imports  (
<import_list> : Import_List  { } )
<participants> : ParticipantDef_List  {
<first> : Nonempty_ParticipantDef_List  (
<it> : ParticipantDef  (
<participantorinterface> : IsParticipant  ( )
<name> : ParticipantName  (
<shortname> : ShortName  (
<name>  : Ident "Foo" ) )
<impls> : Impls  (
<internames> : ParticipantName_CommaList  {
<first> : Nonempty_ParticipantName_CommaList  (
<it> : ParticipantName  (
<shortname> : ShortName  (
<name>  : Ident "Y" ) ) ) } ) ) ) } )
<UNKNOWN21> : UNKNOWN22  (
<adapters> : AdapterItem_List  { } ) )
<next> : Nonempty_Collaboration_List  (
<it> : UNKNOWN23  (
<UNKNOWN24> : UNKNOWN25  (
<UNKNOWN26> : UNKNOWN27  {
<first> : Nonempty_LongName  (
<it> : UNKNOWN28  (
<name>  : Ident "UNKNOWN29" ) ) } )
<structure> : Structure  (
<imports> : Imports  (
<import_list> : Import_List  { } )
<participants> : ParticipantDef_List  {
<first> : Nonempty_ParticipantDef_List  (
<it> : ParticipantDef  (
<participantorinterface> : IsParticipant  ( )
<name> : ParticipantName  (
<shortname> : ShortName  (
<name>  : Ident "Food" ) ) ) ) } )
<adapterdef> : AdapterDef  (
<adapters> : AdapterItem_List  {
<first> : Nonempty_AdapterItem_List  (
<it> : AdapterItem  (
<collabs> : CollabRef_CommaList  {
<first> : Nonempty_CollabRef_CommaList  (
<it> : NormalCollab  (
<collabname> : CollabName  (
<longname> : LongName  {
<first> : Nonempty_LongName  (
<it> : ShortName  (
<name>  : Ident "gettersNsetters" ) ) } ) ) ) }
<attachmentspeclist> : AttachmentSpecList  (
<attachment_list> : Attachment_List  {
<first> : Nonempty_Attachment_List  (
<it> : Attachment  (
<shortname> : ShortName  (
<name>  : Ident "gns" )
<defs> : CompositeParticipantDef_List  {
<first> : Nonempty_CompositeParticipantDef_List  (
<it> : CompositeParticipantDef  (
<lhs> : PartSpec  (
<var> : LongName  {
<first> : Nonempty_LongName  (
<it> : ShortName  (
<name>  : Ident "Food" ) ) } )
<rhs> : PartSpec_CommaList  {
<first> : Nonempty_PartSpec_CommaList  (
<it> : PartSpec  (
<var> : LongName  {
<first> : Nonempty_LongName  (
<it> : ShortName  (
<name>  : Ident "Foo" ) ) } )
<next> : Nonempty_PartSpec_CommaList  (
<it> : PartSpec  (
<var> : LongName  {
<first> : Nonempty_LongName  (
<it> : ShortName  (
<name>  : Ident "X" ) ) } )
<next> : Nonempty_PartSpec_CommaList  (
<it> : PartSpec  (
<var> : LongName  {
<first> : Nonempty_LongName  (
<it> : ShortName  (
<name>  : Ident "edu" )
<next> : Nonempty_LongName  (
<it> : ShortName  (
<name>  : Ident "neu" )
<next> : Nonempty_LongName  (
<it> : ShortName  (
<name>  : Ident "ccs" )
<next> : Nonempty_LongName  (
<it> : ShortName  (
<name>  : Ident "demeter" )
<next> : Nonempty_LongName  (
<it> : ShortName  (
<name>  : Ident "S" ) ) ) ) ) ) } ) ) ) ) }
<with> : With  (
<maps> : Entry_BracedList  {
<first> : Nonempty_Entry_BracedList  (
<it> : Around  (
<nameSpace> : ShortName  (
<name>  : Ident "gns" )
<l> : NameSpec  (
<shortname> : ShortName  (
<name>  : Ident "get_str" ) )
<r> : NameSpec  (
<shortname> : ShortName  (
<name>  : Ident "counted" ) ) )
<next> : Nonempty_Entry_BracedList  (
<it> : Export  (
<lmem> : NameSpec  (
<shortname> : ShortName  (
<name>  : Ident "UNKNOWN30" ) )
<rmem> : NameSpec  (
<shortname> : ShortName  (
<name>  : Ident "UNKNOWN31" ) ) ) ) ) } ) ) ) } ) ) } ) )
<next> : Nonempty_AdapterItem_List  (
<it> : AdapterItem  (
<collabs> : CollabRef_CommaList  {
<first> : Nonempty_CollabRef_CommaList  (
<it> : SharedCollab  (
<collabname> : CollabName  (
<longname> : LongName  {
<first> : Nonempty_LongName  (
<it> : ShortName  (
<name>  : Ident "UNKNOWN32" ) ) } ) ) ) }
<attachmentspeclist> : AttachmentSpecList  (
<attachment_list> : Attachment_List  {
<first> : Nonempty_Attachment_List  (
<it> : Attachment  (
<shortname> : ShortName  (
<name>  : Ident "UNKNOWN33" )
<defs> : CompositeParticipantDef_List  {
<first> : Nonempty_CompositeParticipantDef_List  (
<it> : CompositeParticipantDef  (
<lhs> : PartSpec  (
<var> : LongName  {
<first> : Nonempty_LongName  (
<it> : ShortName  (
<name>  : Ident "UNKNOWN34" ) ) } )
<rhs> : PartSpec_CommaList  {
<first> : Nonempty_PartSpec_CommaList  (
<it> : PartSpec  (
<var> : LongName  {
<first> : Nonempty_LongName  (
<it> : ShortName  (
<name>  : Ident "UNKNOWN35" ) ) } )
<next> : Nonempty_PartSpec_CommaList  (
<it> : PartSpec  (
<var> : LongName  {
<first> : Nonempty_LongName  (
<it> : ShortName  (
<name>  : Ident "UNKNOWN36" ) ) } )
<next> : Nonempty_PartSpec_CommaList  (
<it> : PartSpec  (
<var> : LongName  {
<first> : Nonempty_LongName  (
<it> : ShortName  (
<name>  : Ident "UNKNOWN37" )
<next> : Nonempty_LongName  (
<it> : ShortName  (
<name>  : Ident "UNKNOWN38" ) ) ) } ) ) ) ) }
<with> : With  (
<maps> : Entry_BracedList  {
<first> : Nonempty_Entry_BracedList  (
<it> : Export  (
<lmem> : NameSpec  (
<shortname> : ShortName  (
<name>  : Ident "UNKNOWN39" ) )
<rmem> : NameSpec  (
<shortname> : ShortName  (
<name>  : Ident "UNKNOWN40" ) ) )
<next> : Nonempty_Entry_BracedList  (
<it> : Export  (
<lmem> : NameSpec  (
<shortname> : ShortName  (
<name>  : Ident "UNKNOWN41" ) )
<rmem> : NameSpec  (
<shortname> : ShortName  (
<name>  : Ident "reset" ) ) ) ) ) } ) ) ) } ) ) } ) ) ) ) } ) ) ) ) ) } )
done 3
start the traversal
participant name 
Counted
participant name 
Foo
participant name 
Food
done



Question 2:
===========

100 points.

Design a program that solves the following problem:

Given a class dictionary, find out whether it is connected
in the sense that from the first class all other classes are reachable.

Example:

A = B.
B = C D.
C : X | Y.
D = .
X = .
Y = Q.
Z : Q common B.

is connected.

A = B.
C = D.

is not connected because there is no connection from B to C.

By program design I mean:

1. Sketch a class dictionary.
2. What kind of growth plan would you use?
3. What kind of traversals would you use?
4. What kind of visitors?
5. What kind of connection definition do you use?