--------------------------------------------------------------------------
Software Design and Development				Fall 1995
COM1205							Karl Lieberherr
---------------------------------------------------------------------------
Midterm

---------------------------------------------------------------------------
Open book and open notes. 

Question 1: 28 UNKNOWNS, 2 points each		56 points
Question 2: 7 UNKNOWNS, 6 points each:		42 points
Question 3: 18 UNKNOWNS, 4 points each.		72 points
Question 4: 2 UNKNOWNS, 30 points each		60 points

TOTAL:					       230


To make the grading easier, please put your values for the
unknowns on the enclosed answer sheet.

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

Most 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 by the theory of object-oriented design and 
programming. 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*

At the beginning of a question we give the number of points per unknown.



Question 1:
==================================================================
28 UNKNOWNS, 2 points each		56 points

Consider the following class dictionary:

// Hierarchical state machine for SAIC Authoring System prototype

// Author:  Paul A. Steckler
// Revised: 3/5/90


HierarchicalStateMachine =

	"Machine"     <machine>         MachineName
        "States"      <states>          List(State)

	// the start state is, by convention, the first state
	// in the machine's list of states

	// the current state is maintained at run-time, and is
	// initialized to the start state

       	["_CurrentState"     <currentstate>    State]

	// the state dictionary is used for fast access to states 
	// by name

	["_StateDictionary"  <statedict>       Dictionary(State)]

	// the machine's DemonDictionary is passed a string which 
	// indicates which object should be sent a "run" message

	["_DemonDictionary"  <demondict>       Dictionary(Demon)].

// applying the Terminal-Buffer rule; see page 393, section 12.4
// of the Demeter Book

MachineName = <n> DemIdent.
DemonName   = <n> DemIdent.
EventName   = <n> DemIdent.
StateName   = <n> DemIdent.
DictionaryName = <n> DemIdent.

State = 

	"State"            <statename>	 StateName

        "Transitions"      <transitions> TransitionTable

        "BeforeDemon"	   [<beforedemonnames> CommaList(DemonName)]
        "AfterDemon"	   [<afterdemonnames>  CommaList(DemonName)]

	// when the machine is built, the DemonNames are 
	// mapped to Demon objects

	["_BeforeDemon"    <beforedemons>     List(Demon)]        
	["_AfterDemon"     <afterdemons>      List(Demon)]        

	// the state's parent is filled in at run-time
        // so it doesn't appear in the input object

	// likewise for the default substate, which is the
	// first substate in the list of substates

	["_ParentState"     <parent>      State]
        ["_DefaultSubstate" <defaultsub>  State]

        ["SubStates"        <substates>   List(State) "Endsubstates"]
	"End".

TransitionTable = 

	<transitions> List(Transition).

Transition = 

	"OnEvent" 	<onEvent>	EventName
	"Goto"    	<nextStateName> StateName

	// actual state object filled in to allow fast transitions

	["_NextState"   <nextState> 	State].

// abstract class Demon has a pure virtual function "call"

Demon = "demon" .

Dictionary(X) = <entries> DictionaryEntry(X)
	        <size> DemNumber
	        <numentries> DemNumber
	        <sorted> DemNumber.

DictionaryEntry(X) = <name> DictionaryName <element> X.

CommaList(X) ~ X {"," X}.

List(X) ~ {X}.

The same cd in cross referenced form:


-------------------------------------------------------------
 Class Dictionary
-------------------------------------------------------------
     1	// Hierarchical state machine for SAIC Authoring System prototype
     2	
     3	// Author:  Paul A. Steckler
     4	// Revised: 3/5/90
     5	
     6	
     7	HierarchicalStateMachine =
     8	
     9		"Machine"     <machine>         MachineName
    10	        "States"      <states>          List(State)
    11	
    12		// the start state is, by convention, the first state
    13		// in the machine's list of states
    14	
    15		// the current state is maintained at run-time, and is
    16		// initialized to the start state
    17	
    18	       	["_CurrentState"     <currentstate>    State]
    19	
    20		// the state dictionary is used for fast access to states 
    21		// by name
    22	
    23		["_StateDictionary"  <statedict>       Dictionary(State)]
    24	
    25		// the machine's DemonDictionary is passed a string which 
    26		// indicates which object should be sent a "run" message
    27	
    28		["_DemonDictionary"  <demondict>       Dictionary(Demon)].
    29	
    30	// applying the Terminal-Buffer rule; see page 393, section 12.4
    31	// of the Demeter Book
    32	
    33	MachineName = <n> DemIdent.
    34	DemonName   = <n> DemIdent.
    35	EventName   = <n> DemIdent.
    36	StateName   = <n> DemIdent.
    37	DictionaryName = <n> DemIdent.
    38	
    39	State = 
    40	
    41		"State"            <statename>	 StateName
    42	
    43	        "Transitions"      <transitions> TransitionTable
    44	
    45	        "BeforeDemon"	   [<beforedemonnames> CommaList(DemonName)]
    46	        "AfterDemon"	   [<afterdemonnames>  CommaList(DemonName)]
    47	
    48		// when the machine is built, the DemonNames are 
    49		// mapped to Demon objects
    50	
    51		["_BeforeDemon"    <beforedemons>     List(Demon)]        
    52		["_AfterDemon"     <afterdemons>      List(Demon)]        
    53	
    54		// the state's parent is filled in at run-time
    55	        // so it doesn't appear in the input object
    56	
    57		// likewise for the default substate, which is the
    58		// first substate in the list of substates
    59	
    60		["_ParentState"     <parent>      State]
    61	        ["_DefaultSubstate" <defaultsub>  State]
    62	
    63	        ["SubStates"        <substates>   List(State) "Endsubstates"]
    64		"End".
    65	
    66	TransitionTable = 
    67	
    68		<transitions> List(Transition).
    69	
    70	Transition = 
    71	
    72		"OnEvent" 	<onEvent>	EventName
    73		"Goto"    	<nextStateName> StateName
    74	
    75		// actual state object filled in to allow fast transitions
    76	
    77		["_NextState"   <nextState> 	State].
    78	
    79	// abstract class Demon has a pure virtual function "call"
    80	
    81	Demon = "demon" .
    82	
    83	Dictionary(X) = <entries> DictionaryEntry(X)
    84		        <size> DemNumber
    85		        <numentries> DemNumber
    86		        <sorted> DemNumber.
    87	
    88	DictionaryEntry(X) = <name> DictionaryName <element> X.
    89	
    90	CommaList(X) ~ X {"," X}.
    91	
    92	List(X) ~ {X}.

-------------------------------------------------------------
 Cross Reference List
-------------------------------------------------------------
HierarchicalStateMachine 	:7	
MachineName 	:33	9	
DemonName 	:34	45	46	
EventName 	:35	72	
StateName 	:36	41	73	
DictionaryName 	:37	88	
State 	:39	10	18	23	60	61	63	77	
TransitionTable 	:66	43	
Transition 	:70	68	
Demon 	:81	28	51	52	
Dictionary 	:83	23	28	
DictionaryEntry 	:88	83	
CommaList 	:90	45	46	
List 	:92	10	51	52	63	68	

-------------------------------------------------------------
 Alphabetically Sorted Cross Reference List
-------------------------------------------------------------
CommaList 	:90	45	46	
Demon 	:81	28	51	52	
DemonName 	:34	45	46	
Dictionary 	:83	23	28	
DictionaryEntry 	:88	83	
DictionaryName 	:37	88	
EventName 	:35	72	
HierarchicalStateMachine 	:7	
List 	:92	10	51	52	63	68	
MachineName 	:33	9	
State 	:39	10	18	23	60	61	63	77	
StateName 	:36	41	73	
Transition 	:70	68	
TransitionTable 	:66	43	


The same class dictionary in expanded form:

HierarchicalStateMachine  = 
  "Machine" 
   <machine > MachineName 
    "States" 
     <states > State_List 
      [ "_CurrentState" <currentstate > State  ] 
       [ "_StateDictionary" <statedict > State_Dictionary  ] 
	[ "_DemonDictionary" <demondict > Demon_Dictionary  ] .
MachineName  = <n > DemIdent .
DemonName  = <n > DemIdent .
EventName  = <n > DemIdent .
StateName  = <n > DemIdent .
DictionaryName  = <n > DemIdent .
State  = "State" 
        <statename > StateName 
        "Transitions" 
        <transitions > TransitionTable 
        "BeforeDemon" 
         [ <beforedemonnames > DemonName_CommaList  ] 
        "AfterDemon" 
         [ <afterdemonnames > DemonName_CommaList  ] 
         [ "_BeforeDemon" <beforedemons > Demon_List  ] 
         [ "_AfterDemon" <afterdemons > Demon_List  ] 
         [ "_ParentState" <parent > State  ] 
         [ "_DefaultSubstate" <defaultsub > State  ] 
         [ "SubStates" <substates > State_List "Endsubstates"  ] 
        "End" .
TransitionTable  = <transitions > Transition_List .
Transition  = "OnEvent" 
             <onEvent > EventName 
             "Goto" 
             <nextStateName > StateName 
              [ "_NextState" <nextState > State  ] .
Demon  = "demon" .
State_List  ~ { State } .
State_Dictionary  = <entries > State_DictionaryEntry 
                   <size > DemNumber 
                   <numentries > DemNumber 
                   <sorted > DemNumber .
Demon_Dictionary  = <entries > Demon_DictionaryEntry 
                   <size > DemNumber 
                   <numentries > DemNumber 
                   <sorted > DemNumber .
DemonName_CommaList  ~ DemonName { "," DemonName } .
Demon_List  ~ { Demon } .
Transition_List  ~ { Transition } .
State_DictionaryEntry  = <name > DictionaryName 
                        <element > State .
Demon_DictionaryEntry  = <name > DictionaryName 
                        <element > Demon .
   *terminal_sets* DemText , DemReal , DemString , DemIdent , DemNumber .

Consider the following input sentence:

Machine browser
States
State browser_menu
      Transitions    OnEvent object Goto get_name_substate
                     OnEvent edit   Goto editstate
                     OnEvent quit   Goto quitstate
      BeforeDemon   init_X, draw_menu
      AfterDemon    desensitize_menu
      SubStates
            State         get_name_substate
              Transitions   OnEvent OK Goto show_tree_st
                            OnEvent cancel  Goto browser_menu
              BeforeDemon pop_dialog
              AfterDemon pop_down_dialog
              SubStates
                  State         show_tree_st
                    Transitions   OnEvent Mouse1 Goto show_tree_st
                                  OnEvent Mouse2 Goto presenter_substate
                    BeforeDemon   display_tree 
                    AfterDemon    clear_tree
                    SubStates
                        State   presenter_substate
                          Transitions   OnEvent quit Goto fudge_state 
                          BeforeDemon   set_up_presenter_on_node
                          AfterDemon   clear_presenter
                        End
                        State   fudge_state 
                          Transitions
                          BeforeDemon
                          AfterDemon
                        End 
                   Endsubstates
	         End
               Endsubstates
	    End
      Endsubstates
End

State editstate
      Transitions OnEvent quit Goto browser_menu
      BeforeDemon   init_editor
      AfterDemon    quit_editor
End

State quitstate
      Transitions
      BeforeDemon exitDemon
      AfterDemon
End

Find the UNKNOWNS in the corresponding object graph below:

: HierarchicalStateMachine ( 
   < machine > : UNKNOWN1 ( 
      < n > : DemIdent "browser" ) 
   < states > : State_List { 
      : State ( 
         < UNKNOWN2 > : UNKNOWN3 ( 
            < UNKNOWN4 > : UNKNOWN5 "UNKNOWN6" ) 
         < UNKNOWN7 > : UNKNOWN8 ( 
            < UNKNOWN9 > : UNKNOWN10 { 
               : Transition ( 
                  < onEvent > : EventName ( 
                     < n > : DemIdent "object" ) 
                  < nextStateName > : StateName ( 
                     < n > : DemIdent "get_name_substate" ) ) , 
               : Transition ( 
                  < onEvent > : EventName ( 
                     < n > : DemIdent "edit" ) 
                  < nextStateName > : StateName ( 
                     < n > : DemIdent "editstate" ) ) , 
               : Transition ( 
                  < onEvent > : EventName ( 
                     < n > : DemIdent "quit" ) 
                  < nextStateName > : StateName ( 
                     < n > : DemIdent "quitstate" ) ) } ) 
         < UNKNOWN11 > : UNKNOWN12 { 
            : UNKNOWN13 ( 
               < UNKNOWN14 > : UNKNOWN15 "UNKNOWN16" ) , 
            : UNKNOWN17 ( 
               < UNKNOWN18 > : UNKNOWN19 "UNKNOWN20" ) } 
         < UNKNOWN21 > : UNKNOWN22 { 
            : UNKNOWN23 ( 
               < UNKNOWN24 > : UNKNOWN25 "UNKNOWN26" ) } 
         < UNKNOWN27 > : UNKNOWN28 { 
ETC.


Question 2:
==================================================================
7 UNKNOWNS, 6 points each:		42 points

Consider again the cd from question 1 and the following pp:

*operation* void x()
  *traverse*
    *from* HierarchicalStateMachine
      *through* -> *,statename,*
    *to* StateName
  *wrapper* StateName
    (@ cout << this << endl; @)

*operation* void y()
  *traverse*
    *from* HierarchicalStateMachine
    *to-stop* State
    // to-stop means that we don't take
    // any paths going out from State
  *wrapper* State
    (@ cout << this << endl; @)

*operation* StateName* simulate(EventName* e)
  *traverse*
    *from* HierarchicalStateMachine
      *through* -> *,currentstate,* 
    *to-stop* State
  *wrapper* State
    *prefix* 
      (@ return_val = this->next_state_name(e) ; @)

*operation* StateName* next_state_name(EventName* e)
  *traverse*
    *from* State
      *bypassing* 
		  -> *,defaultsub,*,
		  -> *,substates,*
    *to* Transition
  *wrapper* Transition
   (@ if (e -> g_equal(onEvent))
	 return_val = nextStateName; @)

For the sentence used in question 1, 
the above pps produce the following output:
(the pps are called with:

cout << "calls to x ===================================== " << endl;
iHierarchicalStateMachine -> x();
cout << "calls to y ===================================== " << endl;
iHierarchicalStateMachine -> y();
cout << "calls to simulate ===================================== " << endl;
iHierarchicalStateMachine -> simulate(new EventName(new DemIdent("abc")));
)

Find the UNKNOWNS:

calls to x ===================================== 
UNKNOWN1 
UNKNOWN2 
UNKNOWN3
UNKNOWN4
UNKNOWN5
UNKNOWN6
UNKNOWN7
calls to y ===================================== 
ETC.


Question 3:
============================================================
18 UNKNOWNS, 4 points each.		72 points

Consider the cd from question 1: Find the UNKNOWNS below:

Traversal directive:

*from* { HierarchicalStateMachine } 
  *through* -> State , statename , StateName 
*to* { StateName } 

Propagation graph for traversal:

      HierarchicalStateMachine = 
               < states > State_List 
               [ < currentstate > State ] 
               [ < statedict > State_Dictionary ] . 
      StateName = . 
      State = 
               < UNKNOWN1 > UNKNOWN2 
               < UNKNOWN3 > UNKNOWN4 
               [ < UNKNOWN5 > UNKNOWN6 ] 
               [ < UNKNOWN7 > UNKNOWN8 ] 
               [ < UNKNOWN9 > UNKNOWN10 ] . 
      TransitionTable = 
               < transitions > Transition_List . 
      Transition = UNKNOWN11 
      State_List ~ { State } . 
      State_Dictionary = < entries > State_DictionaryEntry . 
      Transition_List ~ { Transition } . 
      State_DictionaryEntry = < element > State . 


Traversal directive:

*from* { HierarchicalStateMachine } *to-stop* { State } 

Propagation graph for traversal:

      HierarchicalStateMachine = 
               < states > State_List 
               [ < currentstate > State ] 
               [ < statedict > State_Dictionary ] . 
      UNKNOWN12 = . 
      UNKNOWN13 ~ { State } . 
      UNKNOWN14 = < entries > State_DictionaryEntry . 
      UNKNOWN15 = < UNKNOWN16 > UNKNOWN17 . 


Traversal directive:

*from* { State } 
  *bypassing* -> State , defaultsub , State , 
	      -> State , substates , State_List 
*to* { Transition } 

Propagation graph for traversal:

      State =  UNKNOWN18
      TransitionTable = < transitions > Transition_List . 
      Transition = [ < nextState > State ] . 
      Transition_List ~ { Transition } . 

Question 4:
==============================================================
2 UNKNOWNS, 30 points each		60 points

In this question the cd G from question 1
is changed to a new cd G' resulting in a simple
mapping from sentences of the old cd to sentences of the
new cd and a corresponding mapping T of objects of the old cd
to objects of the new cd.

You are asked to update the propagation patterns P to P' so that
for all tree objects O of G:

T(P_G(O)) = P'_G'(T(O)).

Here P_G(O) is the result of customizing P with G and then calling
the resulting object-oriented program on O.

You are also asked to update a given sentence as we evolve from the
old cd to the new cd.


The cd from question 1 is changed as follows (the output of diff is given):

1. Substitute TransitionTable by List(Transition)

<         "Transitions"      <transitions> TransitionTable
---
>         "Transitions"      <transitions> List(Transition)

2. Put two keywords inside optional part

<         "BeforeDemon"	   [<beforedemonnames> CommaList(DemonName)]
<         "AfterDemon"	   [<afterdemonnames>  CommaList(DemonName)]
---
>         ["BeforeDemon"	   <beforedemonnames> CommaList(DemonName)]
>         ["AfterDemon"	   <afterdemonnames>  CommaList(DemonName)]

3. Delete class TransitionTable

< 
< TransitionTable = 
< 
< 	<transitions> List(Transition).


Describe how the sentence from question 1 needs to be changed.
The sentence is repeated here:


Machine browser
States
State browser_menu
      Transitions    OnEvent object Goto get_name_substate
                     OnEvent edit   Goto editstate
                     OnEvent quit   Goto quitstate
      BeforeDemon   init_X, draw_menu
      AfterDemon    desensitize_menu
      SubStates
            State         get_name_substate
              Transitions   OnEvent OK Goto show_tree_st
                            OnEvent cancel  Goto browser_menu
              BeforeDemon pop_dialog
              AfterDemon pop_down_dialog
              SubStates
                  State         show_tree_st
                    Transitions   OnEvent Mouse1 Goto show_tree_st
                                  OnEvent Mouse2 Goto presenter_substate
                    BeforeDemon   display_tree 
                    AfterDemon    clear_tree
                    SubStates
                        State   presenter_substate
                          Transitions   OnEvent quit Goto fudge_state 
                          BeforeDemon   set_up_presenter_on_node
                          AfterDemon   clear_presenter
                        End
                        State   fudge_state 
                          Transitions
                          BeforeDemon
                          AfterDemon
                        End 
                   Endsubstates
	         End
               Endsubstates
	    End
      Endsubstates
End

State editstate
      Transitions OnEvent quit Goto browser_menu
      BeforeDemon   init_editor
      AfterDemon    quit_editor
End

State quitstate
      Transitions
      BeforeDemon exitDemon
      AfterDemon
End

------------------
Put your explanation into

UNKNOWN1


Describe how the propagation patterns from question 2
need to be changed because of the cd change.

Put your explanation into

UNKNOWN2


Explain your answers.