Salil:

please print on both sides and 2 pages per side.

Please print the cd in question 1 also separately.

-- Karl


--------------------------------------------------------------------------
Software Design and Development				Winter 1996
COM1205							Karl Lieberherr
---------------------------------------------------------------------------
Midterm

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

Question 1:
18 UNKNOWNs, 2 points each					36
Question 2:
5 UNKNOWNs, 5 points each					25
Question 3:
25 UNKNOWNs, 5 points for 1 through 9, 3 points for rest.       45
								48
								===
								154


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:
===========
18 UNKNOWNs, 2 points each

Consider the following class dictionary, called ACME Kernel:


// Class dictionary for the ACME Kernel
Architecture = 
	"Architecture" "{"
	"Components" ":"  <components> LIST(Component) 
	"Connectors" ":"  <connectors> LIST(Connector)
        ["Instances" <instances> LIST(Instance)]. 
	      // of components 

Gemeinsam : Architecture | Component | Connector | Port | Role | Instance
  *common* 
	    [ "Representations" ":" 
	       <representations> SLIST(Representation) ]
	    ["Properties" ":"  <properties> SLIST(Property)  ]
	    <name> Name
	    "}" .
		
Component = "Component" "{"  
	    ["Ports" ":"  <ports> LIST(Port)] 
	    ["Instances" <instances> LIST(Instance)] 
	      // of components and connectors
	    ["Attachments" ":"  <attachments> SLIST(Attachment)].
	      // connect instantiated components and connectors

Instance = "Instance" "{" <connectorOrComponent> Name.

Connector = "Connector" "{" 
            "Roles" ":"  <roles> LIST(Role)  . 

Port = "Port" "{".

Role = "Role" "{".

Attachment = <cmp_inst_name> Name "." <port_name> Name 
	     "to" <con_inst_name> Name "." <role_name> Name .

Representation = "External" [ <t> Type ":" ] Att_value .

Property =  <t>  Type  "=" A_Att_value .

A_Att_value : Att_value | Att_value_s .
Att_value = <val> DemString .
Att_value_s = <val> DemIdent .
Name = <val> DemIdent .
Type = <val> DemIdent.

LIST(S) ~ "{" S{S} "}".
SLIST(S) ~ "{" S { ";" S} "}".

and the following sentence:


Architecture {
  Components : {
	Component {
	   Ports : { 
	     Port { Properties : { datatype = UNKNOWN1 }
	     stdin}
	     Port { Properties : { datatype = UNKNOWN2 }
	     stdout}
           }
	   Representations : { External file : "/lib/kalman.c" }
	   Properties : { Aesop-style = UNKNOWN3 ;
		          Aesop-datapath = "stdin to stdout" ;
			  UniCon-type = UNKNOWN4 }
        UNKNOWN5}
	Component {
	   Ports : { 
	     Port { Properties : { datatype = char-stream }
	     stdin}
	     Port { Properties : { datatype = char-stream }
	     stdout}
	   }
	   Representations : { External file : "/lib/find_error.c" }
	   Properties : { Aesop-style = pf ;
		          Aesop-datapath = "stdin to stdout" ;
			  UniCon-type = filter }
	detect_errors}
	Component {
	   Ports : { 
	     Port { Properties : { datatype = char-stream }
	     stdin}
	     Port { Properties : { datatype = char-stream }
             stdout}
	   }
	   Representations : { External file : "/lib/show_tracks.c" }
	   Properties : { Aesop-style = pf ;
		          Aesop-datapath = "stdin to stdout" ;
			  UniCon-type = filter }
	show_tracks}
	Component  {
	  Instances {
	    Instance { p1 p1_inst}
	    Instance { p2 p2_inst}
	    Instance { smooth_signal smooth_signal_inst}
	    Instance { error_detect error_detect_inst}}
  	  Attachments : {
	    smooth_signal_inst.stdout to p1_inst.source ;
	    error_detect_inst.stdin to p1_inst.sink ;
	    error_detect_inst.stdout to p2_inst.source ;
	    show_tracks_inst.stdin to p2_inst.sink}
	my_component}
  }
  Connectors : {
	Connector {
	   Roles : { 
	     Role { Properties : { datatype = char-stream }
	     source}
	     Role { Properties : { datatype = char-stream }
	     sink}
	   }
	   Properties : { Aesop-style = pf ;
		          Aesop-datapath = "source to sink" ;
			  UniCon-type = pipe }
	p1}
	Connector {
	   Roles : { 
	     Role { Properties : { datatype = char-stream }
	     source}
	     Role { Properties : { datatype = char-stream }
	     sink}
	   }
	   Properties : { Aesop-style = pf ;
		          Aesop-datapath = "source to sink" ;
			  UniCon-type = pipe }
	p2}
  }
kernel-radar-pipeline}

and the following object graph:

: Architecture ( 
   < components > : Component_LIST { 
      : Component ( 
         < ports > : Port_LIST { 
            : Port ( 
               < properties > : Property_SLIST { 
                  : Property ( 
                     < t > : Type ( 
                        < val > : DemIdent "datatype" ) 
                     < a_att_value > : Att_value_s ( 
                        < val > : DemIdent "char-stream" ) ) } 
               < name > : Name ( 
                  < val > : DemIdent "stdin" ) ) , 
            : Port ( 
               < properties > : Property_SLIST { 
                  : Property ( 
                     < t > : Type ( 
                        < val > : DemIdent "datatype" ) 
                     < a_att_value > : Att_value_s ( 
                        < val > : DemIdent "char-stream" ) ) } 
               < name > : Name ( 
                  < val > : DemIdent "stdout" ) ) } 
         < representations > : Representation_SLIST { 
            : Representation ( 
               < t > : Type ( 
                  < val > : DemIdent "file" ) 
               < att_value > : Att_value ( 
                  < val > : DemString "/lib/kalman.c" ) ) } 
         < properties > : Property_SLIST { 
            : Property ( 
               < t > : Type ( 
                  < val > : DemIdent "Aesop-style" ) 
               < a_att_value > : Att_value_s ( 
                  < val > : DemIdent "pf" ) ) , 
            : Property ( 
               < t > : Type ( 
                  < val > : DemIdent "Aesop-datapath" ) 
               < a_att_value > : Att_value ( 
                  < val > : DemString "stdin to stdout" ) ) , 
            : Property ( 
               < t > : Type ( 
                  < val > : DemIdent "UniCon-type" ) 
               < a_att_value > : Att_value_s ( 
                  < val > : DemIdent "filter" ) ) } 
         < name > : Name ( 
            < val > : DemIdent "smooth_signal" ) ) , 
/// omitted
         < attachments > : UNKNOWN6 { 
            : Attachment ( 
               < cmp_inst_name > : Name ( 
                  < val > : DemIdent "UNKNOWN7" ) 
               < UNKNOWN8 > : Name ( 
                  < val > : DemIdent "UNKNOWN9" ) 
               < con_inst_name > : Name ( 
                  < val > : DemIdent "p1_inst" ) 
               < UNKNOWN10 > : Name ( 
                  < val > : DemIdent "source" ) ) , 
            : Attachment ( 
               < cmp_inst_name > : Name ( 
                  < val > : DemIdent "UNKNOWN11" ) 
               < UNKNOWN12 > : Name ( 
                  < val > : DemIdent "UNKNOWN13" ) 
               < UNKNOWN14 > : Name ( 
                  < val > : DemIdent "p1_inst" ) 
               < role_name > : Name ( 
                  < val > : DemIdent "sink" ) ) , 
/// omitted
   < connectors > : Connector_LIST { 
      : Connector ( 
         < roles > : Role_LIST { 
            : UNKNOWN15 ( 
               < properties > : Property_SLIST { 
                  : Property ( 
                     < t > : Type ( 
                        < val > : DemIdent "datatype" ) 
                     < a_att_value > : Att_value_s ( 
                        < val > : DemIdent "char-stream" ) ) } 
               < name > : Name ( 
                  < val > : DemIdent "UNKNOWN16" ) ) , 
/// omitted
            : Property ( 
               < t > : Type ( 
                  < UNKNOWN17 > : DemIdent "UniCon-type" ) 
               < a_att_value > : Att_value_s ( 
                  < val > : DemIdent "pipe" ) ) } 
         < name > : Name ( 
            < val > : DemIdent "p2" ) ) } 
   < name > : Name ( 
      < val > : DemIdent "UNKNOWN18" ) ) 
// end of object

Find the UNKNOWNs.

Question 2:
===========
5 UNKNOWNs, 5 points each

Consider the class dictionary of question 1 and modify it so that
it accepts the sentence below.

The difference is that components and connectors can be given 
in any order and that inheritance between components
and connectors is now available.

Find the UNKNOWNs.

Architecture {
  Types {
	Component {
	   Ports : { 
	     Port { Properties : { datatype = char-stream }
	     stdin}
	     Port { Properties : { datatype = char-stream }
	     stdout}}
	   Properties : { Aesop-style = pf ;
		          Aesop-datapath = "stdin to stdout" ;
			  UniCon-type = filter }
           ports}
	Component {
	   Inherits {ports} 
	   Representations : { External file : "/lib/kalman.c" }
        smooth_signal}
	Component {
	   Inherits {ports} 
	   Representations : { External file : "/lib/find_error.c" }
	detect_errors}
	Component {
	   Inherits {ports} 
	   Representations : { External file : "/lib/show_tracks.c" }
	show_tracks}

	Connector {
	   Roles : { 
	     Role { Properties : { datatype = char-stream }
	     source}
	     Role { Properties : { datatype = char-stream }
	     sink}
	   }
	   Properties : { Aesop-style = pf ;
		          Aesop-datapath = "source to sink" ;
			  UniCon-type = pipe }
	p_type}
	Component  {
	  Instances {
	    Instance { p_type p1_inst}
	    Instance { p_type p2_inst}
	    Instance { smooth_signal smooth_signal_inst}
	    Instance { error_detect error_detect_inst}}
  	  Attachments : {
	    smooth_signal_inst.stdout to p1_inst.source ;
	    error_detect_inst.stdin to p1_inst.sink ;
	    error_detect_inst.stdout to p2_inst.source ;
	    show_tracks_inst.stdin to p2_inst.sink}
	my_component}

  } // Types
	  Instances {
	    Instance { my_component my_inst}}
kernel-radar-pipeline}

Your new class dictionary should have the following form:

// Grammar for ACME Kernel
// EBNF-like syntax
// input to adaptive meta-programming tool
// to create C++ class library (with parser and printer)
// and Tcl/Tk interface

Architecture = 
	"Architecture" "{"
	"UNKNOWN1" <typeDefs> LIST(UNKNOWN2)
        ["Instances" <instances> LIST(Instance)]. 
	      // of components 
UNKNOWN3 : UNKNOWN4 | Connector
  *common*
            ["UNKNOWN5" <from> LIST(Name)].
	    // to inherit for example properties and roles
	    // support multiple inheritance


Gemeinsam : Architecture | TypeDef | Port | Role | Instance
  *common* 
	    [ "Representations" ":" 
	       <representations> SLIST(Representation) ]
	    ["Properties" ":"  <properties> SLIST(Property)  ]
	    <name> Name
	    "}" .
		
Component = "Component" 
	    "{"  
	    ["Ports" ":"  <ports> LIST(Port)] 
	    ["Instances" <instances> LIST(Instance)] 
	      // of components and connectors
	    ["Attachments" ":"  <attachments> SLIST(Attachment)].
	      // connect instantiated components and connectors

Instance = "Instance" "{" <connectorOrComponent> Name.

Connector = "Connector" "{" 
            "Roles" ":"  <roles> LIST(Role)  . 

Port = "Port" "{".

Role = "Role" "{".

Attachment = <cmp_inst_name> Name "." <port_name> Name 
	     "to" <con_inst_name> Name "." <role_name> Name .

Representation = "External" [ <t> Type ":" ] Att_value .

Property =  <t>  Type  "=" A_Att_value .

A_Att_value : Att_value | Att_value_s .
Att_value = <val> DemString .
Att_value_s = <val> DemIdent .
Name = <val> DemIdent .
Type = <val> DemIdent.

LIST(S) ~ "{" S{S} "}".
SLIST(S) ~ "{" S { ";" S} "}".

Find the UNKNOWNs.


Question 3:
===========
25 UNKNOWNs, 5 points for 1 through 9, 3 points for rest.

Consider the class dictionary from question 1
and the following propagation patterns.

Find the UNKNOWNs.


// test_find is used to test propagation pattern find below.
// Would be easier to test with Tcl, using Isthmus.

*operation* void test_find()
  // no traversal
  *wrapper* Architecture
    (@ Component* c = this -> 
       find(new Name(new DemIdent("smooth_signal")));
       if (c) cout << c << endl; else cout << " not found" << endl; @)


// find searches an Architecture-object for a Component-object
// with name n

*operation* Component* find(Name* n)
  *init* (@ 0 @)
  *traverse*
    UNKNOWN1
      (@ if (n -> UNKNOWN2(this -> UNKNOWN3()))
	   return_val = this;
      @)


// find_repr_att_value searches an Architecture-object
// for all Att_value-objects which are contained in
// Representation-objects.
// It does not find any Att_value-objects outside
// Representation-objects.

*operation* void find_repr_att_value()
  *traverse*
    UNKNOWN4
    *wrapper* UNKNOWN5
      (@ cout << this << endl ; @)


// instance_component_pairs searches an Architecture-object
// for Component-objects and those Component-objects
// for Instance-objects and prints for each Instance-object
// name the name of the enclosing Component-object

*operation* void instance_component_pairs()
  *traverse*
    UNKNOWN6
    *carry* *in* Name* n = (@ get_name(); @)
      *along* *from* UNKNOWN7 *to* UNKNOWN8
    *wrapper* Instance
      (@ cout << " instance name " << this->get_name()
	      << " component name "<< n << endl; @)


Here is a trace of the above propagation
patterns for the input object of question 1.
Find the UNKNOWNs.

>> void Architecture::test_find()
 >> Component*  Architecture::find(Name*  n)
  >> void Architecture::find_(Component* & return_val,Name*  n)
   >> void Component_LIST::find_(Component* & return_val,Name*  n)
    >> void Component::find_(Component* & return_val,Name*  n)
    << void Component::find_(Component* & return_val,Name*  n)
    >> void Component::find_(Component* & return_val,Name*  n)
    << void Component::find_(Component* & return_val,Name*  n)
    >> void Component::find_(Component* & return_val,Name*  n)
    << void Component::find_(Component* & return_val,Name*  n)
    >> void Component::find_(Component* & return_val,Name*  n)
    << void Component::find_(Component* & return_val,Name*  n)
   << void Component_LIST::find_(Component* & return_val,Name*  n)
  << void Architecture::find_(Component* & return_val,Name*  n)
 << Component*  Architecture::find(Name*  n)
Component { Ports : { Port { Properties : 
{ datatype = char-stream } stdin } Port { Properties : { datatype = 
char-stream } stdout } } Representations : 
{ External file : "/lib/kalman.c" } 
Properties : { Aesop-style = pf ; 
Aesop-datapath = "stdin to stdout" ; UniCon-type = filter } smooth_signal } 
<< void Architecture::test_find()
>> void Architecture::find_repr_att_value()
 >> void UNKNOWN9::find_repr_att_value()
  >> void Component::find_repr_att_value()
   >> void UNKNOWN10::find_repr_att_value()
    >> void UNKNOWN11::find_repr_att_value()
    << void UNKNOWN12::find_repr_att_value()
    >> void UNKNOWN13::find_repr_att_value()
    << void UNKNOWN14::find_repr_att_value()
   << void UNKNOWN15::find_repr_att_value()
   >> void Representation_SLIST::find_repr_att_value()
    >> void Representation::find_repr_att_value()
     >> void Att_value::find_repr_att_value()
"/lib/kalman.c" 
     << void Att_value::find_repr_att_value()
    << void Representation::find_repr_att_value()
   << void Representation_SLIST::find_repr_att_value()
  << void Component::find_repr_att_value()
  >> void Component::find_repr_att_value()
   >> void Port_LIST::find_repr_att_value()
    >> void Port::find_repr_att_value()
    << void Port::find_repr_att_value()
    >> void Port::find_repr_att_value()
    << void Port::find_repr_att_value()
   << void Port_LIST::find_repr_att_value()
   >> void Representation_SLIST::find_repr_att_value()
    >> void Representation::find_repr_att_value()
     >> void Att_value::find_repr_att_value()
"/lib/find_error.c" 
     << void Att_value::find_repr_att_value()
    << void Representation::find_repr_att_value()
   << void Representation_SLIST::find_repr_att_value()
  << void Component::find_repr_att_value()
  >> void Component::find_repr_att_value()
   >> void Port_LIST::find_repr_att_value()
    >> void Port::find_repr_att_value()
    << void Port::find_repr_att_value()
    >> void Port::find_repr_att_value()
    << void Port::find_repr_att_value()
   << void Port_LIST::find_repr_att_value()
   >> void Representation_SLIST::find_repr_att_value()
    >> void Representation::find_repr_att_value()
     >> void Att_value::find_repr_att_value()
"/lib/show_tracks.c" 
     << void Att_value::find_repr_att_value()
    << void Representation::find_repr_att_value()
   << void Representation_SLIST::find_repr_att_value()
  << void Component::find_repr_att_value()
  >> void Component::find_repr_att_value()
   >> void Instance_LIST::find_repr_att_value()
    >> void Instance::find_repr_att_value()
    << void Instance::find_repr_att_value()
    >> void Instance::find_repr_att_value()
    << void Instance::find_repr_att_value()
    >> void Instance::find_repr_att_value()
    << void Instance::find_repr_att_value()
    >> void Instance::find_repr_att_value()
    << void Instance::find_repr_att_value()
   << void Instance_LIST::find_repr_att_value()
  << void Component::find_repr_att_value()
 << void Component_LIST::find_repr_att_value()
 >> void Connector_LIST::find_repr_att_value()
  >> void Connector::find_repr_att_value()
   >> void UNKNOWN16::find_repr_att_value()
    >> void UNKNOWN17::find_repr_att_value()
    << void UNKNOWN18::find_repr_att_value()
    >> void UNKNOWN19::find_repr_att_value()
    << void UNKNOWN20::find_repr_att_value()
   << void UNKNOWN21::find_repr_att_value()
  << void Connector::find_repr_att_value()
  >> void Connector::find_repr_att_value()
   >> void Role_LIST::find_repr_att_value()
    >> void Role::find_repr_att_value()
    << void Role::find_repr_att_value()
    >> void Role::find_repr_att_value()
    << void Role::find_repr_att_value()
   << void Role_LIST::find_repr_att_value()
  << void Connector::find_repr_att_value()
 << void Connector_LIST::find_repr_att_value()
<< void Architecture::find_repr_att_value()
>> void Architecture::instance_component_pairs()
 >> void Component_LIST::instance_component_pairs()
  >> void Component::instance_component_pairs()
  << void Component::instance_component_pairs()
  >> void Component::instance_component_pairs()
  << void Component::instance_component_pairs()
  >> void Component::instance_component_pairs()
  << void Component::instance_component_pairs()
  >> void Component::instance_component_pairs()
   >> void Instance_LIST::instance_component_pairs(Name*  n)
    >> void Instance::instance_component_pairs(Name*  n)
 instance name p1_inst  component name UNKNOWN22 
    << void Instance::instance_component_pairs(Name*  n)
    >> void Instance::instance_component_pairs(Name*  n)
 instance name p2_inst  component name UNKNOWN23 
    << void Instance::instance_component_pairs(Name*  n)
    >> void Instance::instance_component_pairs(Name*  n)
 instance name smooth_signal_inst  component name UNKNOWN24 
    << void Instance::instance_component_pairs(Name*  n)
    >> void Instance::instance_component_pairs(Name*  n)
 instance name error_detect_inst  component name UNKNOWN25 
    << void Instance::instance_component_pairs(Name*  n)
   << void Instance_LIST::instance_component_pairs(Name*  n)
  << void Component::instance_component_pairs()
 << void Component_LIST::instance_component_pairs()
<< void Architecture::instance_component_pairs()