--------------------------------------------------------------------------
Object-oriented Systems                         Fall 1995
COM 3360/NTU SE737
---------------------------------------------------------------------------
Assignment 4                                    Due date: Monday, Oct. 30
						NTU: one week later
---------------------------------------------------------------------------

This assignment is stored in file $OO/hw/4
in file assign.txt

=========
On CCS Northeastern machines,
OO=/course/com3360

On the WWW, OO = http://www.ccs.neu.edu/research/demeter/course
=========

Use the following header for your written homework submissions
and put it at the top of the first page:

Course number: COM 3360/NTU SE737 (whichever applies)
Name:
Account name:
Assignment number:
Date:

Send your solution by email to the teaching assistant (kate) with subject line:

Subject: COM 3360/NTU SE737 HW number

where number is the homework number.
==========

Put the solutions to this homework into directory
/proj/adaptive3/projects/com3360-f95/YOUR_LOGIN/hw4
==========

Midterm time is approaching. For COM3360 students,
it will be held on Oct. 30. Sample midterm exams are in

$OO/exams/m-3360*

In
$OO/exams/practice-exam-handout
you find instructions on how to prepare your own practice exams.
---------

When you have questions about concepts and tools, please check first URL:

ftp://ftp.ccs.neu.edu/pub/people/lieber/faq/Demeter-FAQ

for an answer.
Whenever you have questions about course material,
please send e-mail to:

mail lieberherr@ccs.neu.edu ccs.courses.com3360@ccs.neu.edu


===============================================================
Theme:

This homework invites you to abstract object-oriented designs
from C++ programs and to write simple propagation patterns.
You also look at a larger example of a programming tool,
the Isthmus tool, and collect a few statistics on it.
Finally, the homework invites you to explore Tcl/Tk a little and to call 
propagation patterns from Tcl.

Background tasks:
1. Work through chapters 3 and 4 of the User's Guide using the computer.

   Chapter 3 helps you to make your cds LL(1) (you have read
   this already in assignment 3) and chapter 4 helps
   you with the technical details of propagation patterns.

2. Do the background tasks for assignment 4, page 554.
============== 


PART A:
=======

Abstracting object-oriented design patterns from C++ programs.

Below are two sets of C++ member functions
and corresponding class dictionaries, called test and test2.
I claim they both come from the same propagation pattern
subject to a renaming of function names.
What is the propagation pattern? Describe it in English.

Both sets of functions are only called through the first function in the set,
i.e., all function names, except the first one, are not
used elsewhere and their names are irrelevant to the abstraction.

Hint:
It should be something like:

For a given A-object, find all ?-objects contained in the
A-object, except objects reachable through a data member called
?. For each ?-object we found ...

/========================================= test

Class dictionary:

A = 
  <b1> B
  <b2> B
  <b3> B
  <b4> B
  <b5> B.
B =
  <c1> C
  <c2> C
  <c3> C
  <c4> C
  <c5> C.
C = .

// member functions

#include "UNKNOWN.h"

//  A  = <b1 > B 
//    <b2 > B 
//    <b3 > B 
//    <b4 > B 
//    <b5 > B .
void A::f(  )
{
  DEM_TRACE("A","void A::f()");
  // outgoing calls
  // construction edge prefix wrappers
 cout << "coming from vertex " << this->get_type() << endl ; 
  this->get_b2()->f1(  );
  // construction edge prefix wrappers
 cout << "coming from vertex " << this->get_type() << endl ; 
  this->get_b3()->f1(  );
  // construction edge prefix wrappers
 cout << "coming from vertex " << this->get_type() << endl ; 
  this->get_b4()->f1(  );
  // construction edge prefix wrappers
 cout << "coming from vertex " << this->get_type() << endl ; 
  this->get_b5()->f1(  );
}

//  B  = <c1 > C 
//    <c2 > C 
//    <c3 > C 
//    <c4 > C 
//    <c5 > C .
void B::f1(  )
{
  DEM_TRACE("B","void B::f1()");
  // outgoing calls
  // construction edge prefix wrappers
 cout << "coming from vertex " << this->get_type() << endl ; 
  this->get_c1()->f2(  );
}

//  C  = .
void C::f2(  )
{
  DEM_TRACE("C","void C::f2()");
  // prefix class wrappers
 cout << this << endl; 
}

/========================================= test2

Class dictionary:

A = 
  <b1> B
  <b2> B
  <b3> B
  <b4> B
  <b5> B 
  <c2> B1 
  <c3> X 
  <c1> C.
B1 = <b1> B.
X = <c1> C.
B =
  <c1> C2
  <c2> C
  <c3> C
  <c4> C
  <c5> C <b2> C1.
C1 = <c1> C.
C2 = <b1> C.
C = .

// member functions

#include "UNKNOWN.h"

//  A  = <b1 > B 
//    <b2 > B 
//    <b3 > B 
//    <b4 > B 
//    <b5 > B 
//    <c2 > B1 
//    <c3 > X 
//    <c1 > C .

void A::f(  )
{
  DEM_TRACE("A","void A::f()");
  // outgoing calls
  // construction edge prefix wrappers
 cout << "coming from vertex " << this->get_type() << endl ; 
  this->get_b2()->f(  );
  // construction edge prefix wrappers
 cout << "coming from vertex " << this->get_type() << endl ; 
  this->get_b3()->f(  );
  // construction edge prefix wrappers
 cout << "coming from vertex " << this->get_type() << endl ; 
  this->get_b4()->f(  );
  // construction edge prefix wrappers
 cout << "coming from vertex " << this->get_type() << endl ; 
  this->get_b5()->f(  );
}

//  B  = <c1 > C2 
//    <c2 > C 
//    <c3 > C 
//    <c4 > C 
//    <c5 > C 
//    <b2 > C1 .
void B::f(  )
{
  DEM_TRACE("B","void B::f()");
  // outgoing calls
  // construction edge prefix wrappers
 cout << "coming from vertex " << this->get_type() << endl ; 
  this->get_c1()->f(  );
  // construction edge prefix wrappers
 cout << "coming from vertex " << this->get_type() << endl ; 
  this->get_b2()->f(  );
}

//  C1  = <c1 > C .
void C1::f(  )
{
  DEM_TRACE("C1","void C1::f()");
  // outgoing calls
  // construction edge prefix wrappers
 cout << "coming from vertex " << this->get_type() << endl ; 
  this->get_c1()->f(  );
}

//  C2  = <b1 > C .
void C2::f(  )
{
  DEM_TRACE("C2","void C2::f()");
  // outgoing calls
  // construction edge prefix wrappers
 cout << "coming from vertex " << this->get_type() << endl ; 
  this->get_b1()->f(  );
}

//  C  = .
void C::f(  )
{
  DEM_TRACE("C","void C::f()");
  // prefix class wrappers
 cout << this << endl; 
}

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
PART B:
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Abstracting object-oriented design patterns from C++ programs.

Below are three sets of C++ member functions called simple1,
simple2 and simple3.
I claim they all come from the same object-oriented design pattern.
What is it? Describe it in English.

=================================================================== simple1

Class dictionary:

A = <b1> X
    <c1> C.
X = .
C = .

// member functions
#include "UNKNOWN.h"

//  A  = <b1 > X 
//    <c1 > C .
void A::f(  )
{
  DEM_TRACE("A","void A::f()");
  // outgoing calls
  this->get_c1()->f(  );
  // suffix class wrappers
 cout << "after visiting an object of class " << 
	 this -> get_type() << endl; 
}

//  C  = .
void C::f(  )
{
  DEM_TRACE("C","void C::f()");
  // suffix class wrappers
 cout << "after visiting an object of class " << 
	 this -> get_type() << endl; 
}

================================================================== simple2
Class dictionary:

A = <c1> B <c2> B <c3> B.
B = <b1> C <b2> C <b3> C.
C = .

// member functions
#include "UNKNOWN.h"

//  A  = <c1 > B 
//    <c2 > B 
//    <c3 > B .
void A::f(  )
{
  DEM_TRACE("A","void A::f()");
  // outgoing calls
  this->get_c1()->f(  );

  // suffix class wrappers
 cout << "after visiting an object of class " << 
	 this -> get_type() << endl; 
}

//  B  = <b1 > C 
//    <b2 > C 
//    <b3 > C .
void B::f(  )
{
  DEM_TRACE("B","void B::f()");
  // outgoing calls
  this->get_b2()->f(  );
  this->get_b3()->f(  );
  // suffix class wrappers
 cout << "after visiting an object of class " << 
	 this -> get_type() << endl; 
}

//  C  = .
void C::f(  )
{
  DEM_TRACE("C","void C::f()");
  // suffix class wrappers
 cout << "after visiting an object of class " << 
	 this -> get_type() << endl; 
}

================================================================== simple3
Class dictionary:

A = <b1> B <b2> B <b3> B <c> C <c1> D <y1> E.
B = <c1> C <c2> C.
C = .
D = <b1> C <x1> C.
E = <b1> C <b2> C <f2> F.
F = <c1> C.

// member functions
#include "UNKNOWN.h"

//  A  = <b1 > B 
//    <b2 > B 
//    <b3 > B 
//    <c > C 
//    <c1 > D 
//    <y1 > E .
void A::f(  )
{
  DEM_TRACE("A","void A::f()");
  // outgoing calls
  this->get_b2()->f(  );
  this->get_b3()->f(  );
  this->get_c1()->f(  );
  this->get_y1()->f(  );
  // suffix class wrappers
 cout << "after visiting an object of class " << 
	 this -> get_type() << endl; 
}

//  B  = <c1 > C 
//    <c2 > C .
void B::f(  )
{
  DEM_TRACE("B","void B::f()");
  // outgoing calls
  this->get_c1()->f(  );
  // suffix class wrappers
 cout << "after visiting an object of class " << 
	 this -> get_type() << endl; 
}

//  C  = .
void C::f(  )
{
  DEM_TRACE("C","void C::f()");
  // suffix class wrappers
 cout << "after visiting an object of class " << 
	 this -> get_type() << endl; 
}

//  D  = <b1 > C 
//    <x1 > C .
void D::f(  )
{
  DEM_TRACE("D","void D::f()");
  // outgoing calls
  this->get_x1()->f(  );
  // suffix class wrappers
 cout << "after visiting an object of class " << 
	 this -> get_type() << endl; 
}

//  E  = <b1 > C 
//    <b2 > C 
//    <f2 > F .
void E::f(  )
{
  DEM_TRACE("E","void E::f()");
  // outgoing calls
  this->get_f2()->f(  );
  // suffix class wrappers
 cout << "after visiting an object of class " << 
	 this -> get_type() << endl; 
}

//  F  = <c1 > C .
void F::f(  )
{
  DEM_TRACE("F","void F::f()");
  // outgoing calls
  this->get_c1()->f(  );

  // suffix class wrappers
 cout << "after visiting an object of class " << 
	 this -> get_type() << endl; 
}

PART C:
=======

Write your two object-oriented designs from part A and B
as propagation patterns and generate the corresponding 
C++ programs.
There should be one pp for part A and one pp for part B.
Was your answer correct? Do you get
the right C++ program back from your object-oriented design?

Hint: Use 

make clean 

after you remove a C++ file.

PART D:
=======
Theme:

Understanding and using Isthmus:

In directory

$OO/hw/4/workflow-isthmus/generated

there is a C++/Tcl program related to workflow management.
This program has been created from the files in

$OO/hw/4/workflow-isthmus

(excluding directory: generated)

by using the commands

demeter
isthmus-cd
isthmus-pp *.pp

and by copying the file Imakefile.sample to Imakefile and
main_tcl.C.sample to main.C and
main.tcl.sample to main.tcl.


Ordering:

demeter
isthmus-cd
cp Imakefile.sample Imakefile
gen-make
cp main_tcl.C.sample main.C
cp main.tcl.sample main.tcl
isthmus-pp *.pp


Part 1:
===============================================================

Study the Isthmus system (README file is at the end of this PART).

Answer the following questions:
a)
How many propagation patterns does the isthmus-cd tool contain?
b)
How many propagation patterns does the isthmus-pp tool contain?
c)
How many repetition classes does the class dictionary for isthmus-cd contain?
d)
How many repetition classes does the class dictionary for isthmus-pp contain?
e)
What is the ratio between generated and user-written lines in
propagate.benefit for isthmus-cd?
f)
What is the ratio between generated and user-written lines in
propagate.benefit for isthmus-pp?


Part 2:
===============================================================

Study the generated files and add the following behavior:
(You need to copy my directory or you need to regenerate it
in one of your directories)

a)
Add in main.tcl a call to the propagation pattern defined in 1.pp.

b)
Add to main.tcl code for creating a button with text "exit" so that each 
time the button is clicked by the mouse, the application exits.

Add to main.tcl code for creating a button object with text 
"compute required resources" so that each
time the button is clicked by the mouse, the propagation
pattern is executed on the object in variable: iWFM.
The output goes to the window where you run the application.

c)
Add to main.tcl code for creating a message widget into which the  
length of the list of the output of the propagation pattern will
be written.

Turn in your modified main.tcl. Note that you can develop the
modifications to main.tcl interactively by first typing them
directly into the window where you run "run".

Part 3:
===============================================================

Write propagation patterns (one or more) which print for a given 
WFM-object the names of all projects and their
due dates. The output should look like (in the window from where
you run the application):

project1	3/12/95
project2	6/11/95
...

Spaces are unimportant in the output. You may add more tokens to the
class dictionary but then you have to run isthmus-cd and
isthmus-pp *.pp again.

Turn in your propagation pattern.


README file for Isthmus:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Isthmus is distributed as a non-trivial application of 
Adaptive Programming and as a public domain tool to integrate
Tcl/Tk with Adaptive Programming. Isthmus is implemented as a Demeter
Tools/C++ application and serves as a good example how adaptive
object-oriented programs are superior to object-oriented programs.

This file is at URL:
http://www.ccs.neu.edu/research/demeter/course/isthmus/README-first

Brought to you by the collaborative effort of
Salil Pradhan and Karl Lieberherr and several members of the classes
COM1205 and COM3360 at Northeastern University. They are mentioned
at the place of their contribution. Significant contributions
are from undergraduate students.

Enhancements and applications to Isthmus make very good projects
for COM1205 and COM3360/NTU SE737 participants.

Isthmus is on the WWW at URL:

http://www.ccs.neu.edu/research/demeter/course/isthmus

and also in

/proj/adaptive/www/course/isthmus

It is also as a compressed tar file at URL:

ftp://ftp.ccs.neu.edu/pub/research/demeter/isthmus.tar.gz

The propagation patterns of Isthmus are in:
isthmus/i*/*.pp along with the class dictionaries.

The documentation is in directory doc.

At URL:
http://www.ccs.neu.edu/research/demeter/course/isthmus/doc/Users-Guide/HTML-guide/_i-manual.html

is the hypertext version of the documentation.
doc/Users-Guide contains the Latex source of the documentation
and
doc/mann contains the man pages.

doc/Users-Guide/_i-manual.ps
contains the Postscript form of the documentation.

The directory 

testing

contains regression test directories which are important for
testing enhancements to Isthmus.


PART E:
=======

Do Assignment 4, on page 554 of the Demeter book.

========
For your convenience, parts of assignment 4 are enclosed.

Write propagation patterns for a compiler for a stack machine for the
following programming language.

Example = <exps> Postfix_list.
Postfix : Numerical | Compound.
Numerical = <val> DemNumber.
Compound = "{" <arguments> Arguments <op> Op "}".
Arguments = <arg1> Postfix <arg2> Postfix .
Op : Mulsym | Addsym | Subsym.
Mulsym = "*".
Addsym = "+".
Subsym = "-".
Postfix_list ~ Postfix {Postfix }.

Use the following code for generating the stack machine code.
The stack machine has only 4 instructions:

ADI for addition
MLI for multiplication
SBI for subtraction

The above three operations take the two topmost 
elements of the stack as arguments.

The fourth operation, LOC, allows to load a constant onto the stack.
LOC

You only implement the code generator and not an interpreter 
for the stack machine.
// ===================================================================
// Implementation of member functions for the compiler.
// ===================================================================

void Addsym::code_gen() { 
   cout << " ADI \n";} // adds two top-most elements and leaves result on stack

void Mulsym::code_gen() {
   cout << " MLI \n";}

void Subsym::code_gen() {
   cout << " SBI \n";}

void DemNumber::code_gen() {
   cout << " LOC %d\n",val ;} // loads constant on stack

Your compiler should produce the following output for the input
1
{2 3 *}
{3 4 +}
{{3 4 *} {2 3*} +}

generated stack machine code:

1
 LOC 1

{2 3 *}
 LOC 2
 LOC 3
 MLI 

{3 4 +}
 LOC 3
 LOC 4
 ADI 

{{3 4 *} {2 3 *} +}
 LOC 3
 LOC 4
 MLI
 LOC 2
 LOC 3
 MLI
 ADI


Turn in your compiler with the output produced for

2 {1 3 *} {1000 {{3 4 +} 6 *} -}


Subpart 2:
COMPUTING THE SIZE OF AN EXPRESSION
===================================

Write a propagation pattern to compute the size of an expression.
Use the class dictionary from part 1.
An operator has size 1, in general, however, the - operator
has size 10. A number has size 5.

Your program should produce the following output for the input

1
{2 3 *}
{34 6 -}

Output:

1
size: 5

{2 3 *}
size: 11

{34 6 -}
size: 20

Subpart 3:
Compute the size of a class dictionary 
======================================

For class dictionaries defined by the class dictionary in

$OO/sample-class-libraries/c-nice-small/cd.cd

compute their size, according to the following definition:

Definition: Size of a class dictionary
======================================

We define the size of a class dictionary to be:
 
 number of construction edges +
 number of alternation edges * 1/4 +
 number of characters in all the strings (tokens).
  
Examples:
   
A = . has size zero

A = <x> DemNumber "end".  has size 1 + 3 = 4 ( 3 is the size of the token)

                                  size
A = <x> B.			//1
Y : U | V.			//2 * (1/4)
U = <x> X "alternat".           //1 + 8
V = <x> X "alternat".           //1 + 8
 
 has size 3 + (1/4)* 2 + 2*8

Your program should print the total size only.

Hint:
For class Syntax_vertex use something like:

*wrapper* Syntax_vertex // interface: (float& size)
  *prefix*
    (@ size = size + strlen(*string); @)

to compute the size of a token.
Note that it is not possible to attach code to terminal
classes such as DemString.

Turn in your propagation pattern and the output it produced for

$OO/sample-class-libraries/c-nice-small/cd.cd


What is the size of the following class dictionary? Also turn it in.

Example = <exps> Prefix_list.
Prefix : Numerical | Compound.
Numerical = <val> DemNumber.
Compound = "{" <arguments> Arguments <op> Op "}".
Arguments = <arg1> Prefix <arg2> Prefix .
Op : Mulsym | Addsym .
Mulsym = "*".
Addsym = "+".
Prefix_list : Empty | NonEmpty.
Empty = .
NonEmpty = <car> Prefix <cdr> Prefix_list.

=================================================================
What to turn in:
=================================================================
Turn in electronically one file containing:

For PARTS A and B, the English descriptions of your object-oriented
designs.

For PART C: The two propagation patterns developed in PARTS A and B
and the output produced by your propagation patterns.
For PART A, run your program in a copy of directory 
  $OO/hw/4/test2/generated and
for PART B, run your program in a copy of directory
  $OO/hw/4/simple2/generated 

In PART C, you don't have to worry about building a test object. All class
dictionaries used, define just one object and that object I have
already built for you. A description of the object is in file
demeter-input. The file is empty, so we build the object from
thin air. 

For PART D: see there.

For PART E: see Assignment 5 and it is repeated here:

For each subpart, turn in the following:

Your class dictionary,
the files *.pp, i.e., your propagation patterns,
the part of main.C where you call your propagation patterns,
the propagation graph files inter-pps/*.trv,
generate.benefit, propagate.benefit,
inputs, and outputs.

For your own enjoyment (put do NOT turn them in), look at the
generated class library.