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

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 > : MachineName ( 
      < n > : DemIdent "browser" ) 
   < states > : State_List { 
      : State ( 
         < statename > : StateName ( 
            < n > : DemIdent "browser_menu" ) 
         < transitions > : TransitionTable ( 
            < transitions > : Transition_List { 
               : 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" ) ) } ) 
         < beforedemonnames > : DemonName_CommaList { 
            : DemonName ( 
               < n > : DemIdent "init_X" ) , 
            : DemonName ( 
               < n > : DemIdent "draw_menu" ) } 
         < afterdemonnames > : DemonName_CommaList { 
            : DemonName ( 
               < n > : DemIdent "desensitize_menu" ) } 
         < substates > : State_List { 
            : State ( 
               < statename > : StateName ( 
                  < n > : DemIdent "get_name_substate" ) 
               < transitions > : TransitionTable ( 
                  < transitions > : Transition_List { 
                     : Transition ( 
                        < onEvent > : EventName ( 
                           < n > : DemIdent "OK" ) 
                        < nextStateName > : StateName ( 
                           < n > : DemIdent "show_tree_st" ) ) , 
                     : Transition ( 
                        < onEvent > : EventName ( 
                           < n > : DemIdent "cancel" ) 
                        < nextStateName > : StateName ( 
                           < n > : DemIdent "browser_menu" ) ) } ) 
ETC.
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 ===================================== 
browser_menu 
get_name_substate 
show_tree_st 
presenter_substate 
fudge_state 
editstate 
quitstate 
calls to y ===================================== 
ETC.
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 = 
               < statename > StateName 
               < transitions > TransitionTable 
               [ < parent > State ] 
               [ < defaultsub > State ] 
               [ < substates > State_List ] . 
      TransitionTable = 
               < transitions > Transition_List . 
      Transition = [ < nextState > State ] . 
      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 ] . 
      State = . 
      State_List ~ { State } . 
      State_Dictionary = < entries > State_DictionaryEntry . 
      State_DictionaryEntry = < element > State . 


Traversal directive:

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

Propagation graph for traversal:

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

Question 4:
==============================================================

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

UNKNOWN

diff ../demeter-input ./demeter-input
29,30d28
<                           BeforeDemon
<                           AfterDemon
48d45
<       AfterDemon

Describe how the propagation patterns from question 2
need to be changed.

Put your explanation into

UNKNOWN


Explain your answers.