Final examination
COM 3360						Karl Lieberherr
Fall 1994
============================================================================
Open book, open notes

Question 1:
===========
31 UNKNOWNS, 4 points each		124	
Question 2:
===========
2 UNKNOWNs, 15 points each		 30
Question 3:
===========
39 UNKNOWNS, 3 points each		117
Question 4:
===========
9 UNKNOWNs, 6 points each		 54
Question 5:
===========
36 UNKNOWNs, 4 points each		144
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Question 1:
===========
31 UNKNOWNS, 4 points each
f-travel

Consider the following class dictionary:
(See also the enclosed graphical forms. Two copies are enclosed
so that you can show various graphs, if you want.)

SmallTravelSystem = "small travel system"
  "passengers" <passengers> List(Passenger)
  "taxiCompanies" <taxiCompanies> List(TaxiCompany)
  "airlines" <airlines> List(Airline).
Passenger = "passenger"
  "events" <eventHistory> List(Event).
List(S) ~ "(" {S} ")".

TaxiCompany = "taxi company" <name> TaxiCompanyName
  Dispatcher <taxis> List(Taxi).
Taxi = "taxi" <id> DemString.
Airline = "airline" <name> AirlineName
  TicketAgent <airplanes> List(Airplane).
Airplane = "airplane" <id> DemString [<belongs_to> AirlineName]. 
TicketAgent = .
Dispatcher = .
TaxiCompanyName = <name> DemString.
AirlineName = <name> DemString.

Event:
  Depart |
  OrderTaxi |
  OrderPlaneTicket |
  UseTaxi |
  UseAirplane |
  Arrive.
Depart = "depart".
Arrive = "arrive".
OrderTaxi = "order taxi" TaxiCompanyName.
OrderPlaneTicket = "order plane ticket" AirlineName.
UseTaxi = Taxi.
UseAirplane = Airplane.


                         CD-NUMBERED-XREF
   Create a numbered cross reference list for a class dictionary.

-------------------------------------------------------------
 Class Dictionary
-------------------------------------------------------------
     1	SmallTravelSystem = "small travel system"
     2	  "passengers" <passengers> List(Passenger)
     3	  "taxiCompanies" <taxiCompanies> List(TaxiCompany)
     4	  "airlines" <airlines> List(Airline).
     5	Passenger = "passenger"
     6	  "events" <eventHistory> List(Event).
     7	
     8	List(S) ~ "(" {S} ")".
     9	
    10	TaxiCompany = "taxi company" <name> TaxiCompanyName
    11	  Dispatcher <taxis> List(Taxi).
    12	Taxi = "taxi" <id> DemString.
    13	Airline = "airline" <name> AirlineName
    14	  TicketAgent <airplanes> List(Airplane).
    15	Airplane = "airplane" <id> DemString [<belongs_to> AirlineName]. 
    16	TicketAgent = .
    17	Dispatcher = .
    18	TaxiCompanyName = <name> DemString.
    19	AirlineName = <name> DemString.
    20	
    21	Event:
    22	  Depart |
    23	  OrderTaxi |
    24	  OrderPlaneTicket |
    25	  UseTaxi |
    26	  UseAirplane |
    27	  Arrive.
    28	Depart = "depart".
    29	Arrive = "arrive".
    30	OrderTaxi = "order taxi" TaxiCompanyName.
    31	OrderPlaneTicket = "order plane ticket" AirlineName.
    32	UseTaxi = Taxi.
    33	UseAirplane = Airplane.

-------------------------------------------------------------
 Cross Reference List
-------------------------------------------------------------
SmallTravelSystem 	:1	
Passenger 	:5	2	
List 	:8	2	3	4	6	11	14	
TaxiCompany 	:10	3	
Taxi 	:12	11	32	
Airline 	:13	4	
Airplane 	:15	14	33	
TicketAgent 	:16	14	
Dispatcher 	:17	11	
TaxiCompanyName 	:18	10	30	
AirlineName 	:19	13	15	31	
Event 	:21	6	
Depart 	:28	22	
Arrive 	:29	27	
OrderTaxi 	:30	23	
OrderPlaneTicket 	:31	24	
UseTaxi 	:32	25	
UseAirplane 	:33	26	

-------------------------------------------------------------
 Alphabetically Sorted Cross Reference List
-------------------------------------------------------------
Airline 	:13	4	
AirlineName 	:19	13	15	31	
Airplane 	:15	14	33	
Arrive 	:29	27	
Depart 	:28	22	
Dispatcher 	:17	11	
Event 	:21	6	
List 	:8	2	3	4	6	11	14	
OrderPlaneTicket 	:31	24	
OrderTaxi 	:30	23	
Passenger 	:5	2	
SmallTravelSystem 	:1	
Taxi 	:12	11	32	
TaxiCompany 	:10	3	
TaxiCompanyName 	:18	10	30	
TicketAgent 	:16	14	
UseAirplane 	:33	26	
UseTaxi 	:32	25	

Find the unknowns in the following propagation patterns
and propagation graphs:

// print for a passenger the ids of the airplanes used.

// The event history says with which planes the passenger has flown.
*operation* void airplanes_used()
  *traverse*
    *from* UNKNOWN1 
      UNKNOWN2 -> *,UNKNOWN3,UNKNOWN4
    *to* UNKNOWN5
    *wrapper* UNKNOWN6
      *prefix*
	(@ cout << "**********airplane id =" << this -> get_id() << endl; @)

// print for a given passenger object
// the names of the airlines s/he uses and the total number
// of planes owned by the airline.
// An airline may sell tickets of other airlines,
// so the search has to be done through the UseAirplane class.
*operation* void number_of_planes_of_passengers_airlines(SmallTravelSystem* s)
  *traverse*
    *from* UNKNOWN7
      UNKNOWN8 -> *,UNKNOWN9,UNKNOWN10
      UNKNOWN11
    *to* UNKNOWN12 
    *wrapper* UNKNOWN13
      *prefix*
	(@ cout << "**************airline" << this << endl ; 
	   s->number_of_planes_of_airline(this); @)

*operation* void number_of_planes_of_airline(AirlineName* an)
  *traverse*
    *from* UNKNOWN14 
      UNKNOWN15 -> *,UNKNOWN16,* 
    *UNKNOWN17* UNKNOWN18
    *wrapper* UNKNOWN19
      *prefix*
	(@ if (this->get_name()->g_equal(an))
	     cout << "********** number of air planes =" <<  
	     this -> get_airplanes() -> list_length() << endl; @)

=========================================
=========================================
Propagation graphs for each of the propagation patterns

*operation* void airplanes_used()

Propagation graph for traversal:

*source* { Passenger } 
*target* { Airplane } 
   *paths* 
      Passenger = UNKNOWN20.
      UNKNOWN21
      Event : UNKNOWN22 . 
      UNKNOWN23 = < airplane > Airplane . 
      UNKNOWN24 = . 

*operation* void number_of_planes_of_passengers_airlines(SmallTravelSystem* s)

Propagation graph for traversal:

*source* { Passenger } 
*target* { AirlineName } 
   *paths* 
      Passenger = UNKNOWN25.
      UNKNOWN26
      Event : UNKNOWN27 . 
      UseAirplane = UNKNOWN28.
      UNKNOWN29 = [ < UNKNOWN30 > AirlineName ] . 
      UNKNOWN31 = . 

*operation* void number_of_planes_of_airline(AirlineName* an)

Propagation graph for traversal:

*source* { SmallTravelSystem } 
*target* { Airline } 
   *paths* 
      SmallTravelSystem = < airlines > Airline_List . 
      Airline_List ~ { Airline } . 
      Airline = . 


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Question 2:
===========
2 UNKNOWNs, 15 points each
f-inconsistency-kind4

Consider the following propagation pattern:

*operation* void f()
  *traverse*
    *join* (*from* A *to* B,
	    *from* B *to* C)
// The same as: *from* A *via* B *to* C
  *wrapper* C
    *prefix*
      (@ cout << this << endl; @)

When we customize a join propagation directive, such as the
one above, we have to watch out for short cuts.
For the directive *join*(D1,D2) and a customizer G the short-cut
property holds if in G there is a path from the source of D1
to the target of D2 not going through the target of D1.
Such a path is a short-cut path.

Consider the customizers below and
answer the following question: 
Does the short-cut property hold (i.e., are there
short cuts) for all customizers
with the propagation directive in the above propagation pattern?
UNKNOWN1 

Give a brief explanation: UNKNOWN2 

Case 1:
A =  B C.
B =  [A] C.
C = .

Case 2:
A =  B C.
B =  C.
C =  [A].

Case 3:
A =  B C.
B =  [A].
C = .

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Question 3:
===========
39 UNKNOWNS, 3 points each

Find the UNKNOWNs in the object, sentence and 
class dictionary cd-print below. 
The object is legal with respect to the class dictionary
and the sentence is the output of g_print() when the
object is printed.

: SmallTravelSystem ( 
   < UNKNOWN1 > : UNKNOWN2 { 
      : UNKNOWN3 ( 
         < UNKNOWN4 > : UNKNOWN5 { 
            : UNKNOWN6 ( 
               < taxicompanyname > : TaxiCompanyName ( 
                  < name > : DemString "UNKNOWN7" ) ) , 
            : OrderPlaneTicket ( 
               < airlinename > : AirlineName ( 
                  < name > : DemString "UNKNOWN8" ) ) , 
            : Depart ( ) , 
            : UNKNOWN9 ( 
               < taxi > : Taxi ( 
                  < id > : DemString "UNKNOWN10" ) ) , 
            : UseAirplane ( 
               < airplane > : Airplane ( 
                  < id > : DemString "UNKNOWN11" 
                  < belongs_to > : UNKNOWN12 ( 
                     < name > : DemString "UNKNOWN13" ) ) ) } ) } 
   < UNKNOWN14 > : UNKNOWN15 { 
      : UNKNOWN16 ( 
         < name > : TaxiCompanyName ( 
            < name > : DemString "TownTaxi" ) 
         < UNKNOWN17 > : UNKNOWN18 ( ) 
         < taxis > : Taxi_List { 
            : Taxi ( 
               < id > : DemString "UNKNOWN19" ) } ) } 
   < airlines > : Airline_List { 
      : Airline ( 
         < name > : AirlineName ( 
            < name > : DemString "UNKNOWN20" ) 
         < ticketagent > : TicketAgent ( ) 
         < airplanes > : Airplane_List { 
            : Airplane ( 
               < id > : DemString "air1" 
               < belongs_to > : AirlineName ( 
                  < name > : DemString "Delta" ) ) } ) } ) 

sentence corresponding to above object graph:

kleines Reisesystem 
  Passagiere UNKNOWN21 
    Passagier 
      Ereignisse ( 
	bestelle Taxi "TownTaxi" 
	bestelle Flugschein "Delta" 
	Abfahrt 
	Taxi "taxi1" 
	Flugzeug "air1" "Delta" ) 
    UNKNOWN22 ) 
  Taxifirmen ( 
    Taxifirma "TownTaxi" ( Taxi "taxi1" ) ) 
    Fluggesellschaften ( 
      Fluggesellschaft "Delta" 
	( Flugzeug "air1" "Delta" ) ) 
ende 


// Class dictionary (cd-print) for printing

SmallTravelSystem  = "UNKNOWN23 UNKNOWN24" 
                    "UNKNOWN25" 
                    <passengers > Passenger_List 
                    "UNKNOWN26" 
                    <taxiCompanies > TaxiCompany_List 
                    "UNKNOWN27" 
                    <airlines > Airline_List "UNKNOWN28".
Passenger  = "UNKNOWN29" 
            "UNKNOWN30" 
            <eventHistory > Event_List 
            "ende".
TaxiCompany  = "UNKNOWN31" 
              <name > TaxiCompanyName 
              <dispatcher > Dispatcher 
              <taxis > Taxi_List .
Taxi  = "UNKNOWN32" 
       <id > DemString .
Airline  = "UNKNOWN33" 
          <name > AirlineName 
          <ticketagent > TicketAgent 
          <airplanes > Airplane_List .
Airplane  = "UNKNOWN34" 
           <id > DemString 
            [ <belongs_to > AirlineName  ] .
TicketAgent  = .
Dispatcher  = .
TaxiCompanyName  = <name > DemString .
AirlineName  = <name > DemString .
Event  : Depart   |
        OrderTaxi   |
        OrderPlaneTicket   |
        UseTaxi   |
        UseAirplane   |
        Arrive 
           *common* .
Depart  = "UNKNOWN35" .
Arrive  = "Ankunft" .
OrderTaxi  = "UNKNOWN36 UNKNOWN37" 
            <taxicompanyname > TaxiCompanyName .
OrderPlaneTicket  = "UNKNOWN38 UNKNOWN39" 
                   <airlinename > AirlineName .
UseTaxi  = <taxi > Taxi .
UseAirplane  = <airplane > Airplane .
Passenger_List  ~ "(" { Passenger } ")" .
TaxiCompany_List  ~ "(" { TaxiCompany } ")" .
Airline_List  ~ "(" { Airline } ")" .
Event_List  ~ "(" { Event } ")" .
Taxi_List  ~ "(" { Taxi } ")" .
Airplane_List  ~ "(" { Airplane } ")" .


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Question 4:
===========
9 UNKNOWNs, 6 points each

Consider the class dictionary from question 1.
Consider the following transportation customizer restrictions 
discussed in class and in the book. I use here better names as follows:

--------------------------
Getting-in Restriction: 
  "can get in only through a transportation source"

If a vertex v in the transportation graph has an incoming 
non-transportation edge, then v must be a source vertex of
the transportation directive.
--------------------------

--------------------------
No-return Restriction: 
  "can not return to source"

A source vertex of a transportation (or traversal) directive
cannot have incoming edges in the transportation graph.
--------------------------

Find the UNKNOWNS below:

Propagation pattern

*operation* void transp2()
  *traverse*
    *from* SmallTravelSystem
  *carry* *in* int i
    *along*
      *from* Passenger 
      *to* Airplane

error message from propagation pattern compiler

// *operation* void transp2 ( ) 
// propagate: error:  
// the UNKNOWN1 Restriction is violated. 
// The UNKNOWN2 edge 'UNKNOWN3' 
// which is in the traversal graph but not in the 
// transportation graph is not allowed, 
// since 'UNKNOWN4' is  in the transporation graph 
// but not a transportation source.

Propagation pattern

*operation* void transp1()
  *traverse*
    *from* SmallTravelSystem
  *carry* *in* int i
    *along*
      *from* Passenger 
      *to* Taxi

error message from propagation pattern compiler

// *operation* void transp1 ( ) 

// propagate: error:  
// the UNKNOWN5 Restriction is violated. 
// The UNKNOWN6 edge '~> UNKNOWN7,UNKNOWN8' 
// which is in the traversal graph but not in the 
// transportation graph is not allowed, 
// since 'UNKNOWN9' is  in the transporation graph 
// but not a transportation source.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Question 5:
===========
36 UNKNOWNs, 4 points each

The class dictionary from question 1 is used.
Consider the propagation patterns, sentence and output trace below.
Find the UNKNOWNs.

The comments are important!

// For a SmallTravelSystem-object
// print the event history of all passengers who are taxi users

*operation* void query1()
  *traverse*
    *from* SmallTravelSystem
      *via* Passenger
    *to* Taxi
    // transportation pattern
    *carry* *UNKNOWN1* UNKNOWN2* UNKNOWN3= (@ UNKNOWN4 @)
      *along*
        *from* UNKNOWN5 
        *to* UNKNOWN6
    *wrapper* UNKNOWN7
      *prefix*
	(@ cout << "passenger event history " << etl << this << endl;  @)
    // end transportation pattern

// For a SmallTravelSystem-object
// print for each taxi used by a passenger the taxi company name of the
// company controlling the taxis.

*operation* void query2()
  *traverse*
    *from* SmallTravelSystem
      *via* Passenger
    *to* Taxi
    // transportation pattern	
    *carry* *UNKNOWN8* UNKNOWN9* UNKNOWN10
      *along*
        *from* UNKNOWN11
          *via* UNKNOWN12
        *to* UNKNOWN13
      *at* Taxi taxi_id = (@ id @)

    *wrapper* SmallTravelSystem
      *suffix*
	(@ this -> find(taxi_id);  @)
    // end transportation pattern	

*operation* void find(DemString* taxi_id)
  *traverse*
    *from* SmallTravelSystem
      *through* -> *, taxiCompanies, *
    *to* Taxi
    // transportation pattern
    *carry* *UNKNOWN14* UNKNOWN15* UNKNOWN16 = (@ name @)
      *along*
	*from* UNKNOWN17 *to* UNKNOWN18
    *wrapper* Taxi
      *prefix*
        (@ if (id -> g_equal(taxi_id))
	     cout << "taxi company name " << tcn << endl;
       @)
    // end transportation pattern

sentence:

small travel system
  passengers (
    passenger
      events (
        order taxi "TownTaxi"
        order plane ticket "Delta"
        depart
        taxi "taxi1"
        airplane "air1" "Delta"))
  taxiCompanies (
    taxi company "TownTaxi"
      (taxi "taxi1"))
  airlines (
    airline "Delta"
      (airplane "air1" "Delta"))

output trace: 

>> void SmallTravelSystem::query1()
 >> void UNKNOWN19::query1()
  >> void UNKNOWN20::query1()
   >> void Event_List::query1(Event_List*  etl)
    >> void UNKNOWN21::query1(Event_List*  etl)
     >>  at UNKNOWN22 , ***  PREMATURELY TERMINATED *** 
     <<  at UNKNOWN23 , ***  PREMATURELY TERMINATED *** 
    << void Event::query1(Event_List*  etl)
    >> void Event::query1(Event_List*  etl)
     >>  at UNKNOWN24 , ***  PREMATURELY TERMINATED *** 
     <<  at UNKNOWN25 , ***  PREMATURELY TERMINATED *** 
    << void Event::query1(Event_List*  etl)
    >> void Event::query1(Event_List*  etl)
     >>  at UNKNOWN26 , ***  PREMATURELY TERMINATED *** 
     <<  at UNKNOWN27 , ***  PREMATURELY TERMINATED *** 
    << void Event::query1(Event_List*  etl)
    >> void UseTaxi::query1(Event_List*  etl)
     >> void Taxi::query1(Event_List*  etl)
passenger event history 
      events (
        order taxi "TownTaxi"
        order plane ticket "Delta"
        depart
        taxi "taxi1"
        airplane "air1" "Delta")
    taxi "taxi1"
     << void Taxi::query1(Event_List*  etl)
    << void UseTaxi::query1(Event_List*  etl)
    >> void Event::query1(Event_List*  etl)
     >>  at UseAirplane , ***  PREMATURELY TERMINATED *** 
     <<  at UseAirplane , ***  PREMATURELY TERMINATED *** 
    << void Event::query1(Event_List*  etl)
   << void UNKNOWN28::query1(Event_List*  etl)
  << void UNKNOWN29::query1()
 << void UNKNOWN30::query1()
<< void SmallTravelSystem::query1()
>> void SmallTravelSystem::query2()
 >> void Passenger_List::query2(DemString* &  taxi_id)
  >> void Passenger::query2(DemString* &  taxi_id)
   >> void Event_List::query2(DemString* &  taxi_id)
    >> void Event::query2(DemString* &  taxi_id)
     >>  at OrderTaxi , ***  PREMATURELY TERMINATED *** 
     <<  at OrderTaxi , ***  PREMATURELY TERMINATED *** 
    << void Event::query2(DemString* &  taxi_id)
    >> void Event::query2(DemString* &  taxi_id)
     >>  at OrderPlaneTicket , ***  PREMATURELY TERMINATED *** 
     <<  at OrderPlaneTicket , ***  PREMATURELY TERMINATED *** 
    << void Event::query2(DemString* &  taxi_id)
    >> void Event::query2(DemString* &  taxi_id)
     >>  at Depart , ***  PREMATURELY TERMINATED *** 
     <<  at Depart , ***  PREMATURELY TERMINATED *** 
    << void Event::query2(DemString* &  taxi_id)
    >> void UseTaxi::query2(DemString* &  taxi_id)
     >> void Taxi::query2(DemString* &  taxi_id)
     << void Taxi::query2(DemString* &  taxi_id)
    << void UseTaxi::query2(DemString* &  taxi_id)
    >> void Event::query2(DemString* &  taxi_id)
     >>  at UseAirplane , ***  PREMATURELY TERMINATED *** 
     <<  at UseAirplane , ***  PREMATURELY TERMINATED *** 
    << void Event::query2(DemString* &  taxi_id)
   << void Event_List::query2(DemString* &  taxi_id)
  << void Passenger::query2(DemString* &  taxi_id)
 << void Passenger_List::query2(DemString* &  taxi_id)
 >> void SmallTravelSystem::find(DemString*  taxi_id)
  >> void Passenger_List::find(DemString*  taxi_id)
   >> void Passenger::find(DemString*  taxi_id)
   << void Passenger::find(DemString*  taxi_id)
  << void Passenger_List::find(DemString*  taxi_id)
  >> void TaxiCompany_List::find(DemString*  taxi_id)
   >> void TaxiCompany::find(UNKNOWN31)
    >> void Taxi_List::find(UNKNOWN32)
     >> void Taxi::find(UNKNOWN33)
taxi company name "TownTaxi" 
     << void Taxi::find(UNKNOWN34)
    << void Taxi_List::find(UNKNOWN35)
   << void TaxiCompany::find(UNKNOWN36)
  << void TaxiCompany_List::find(DemString*  taxi_id)
 << void SmallTravelSystem::find(DemString*  taxi_id)
<< void SmallTravelSystem::query2()

HAPPY HOLIDAYS AND A HAPPY NEW YEAR