From lechner@cs.uml.edu  Thu Oct 13 03:43:35 2005
From: Bob Lechner <lechner@cs.uml.edu>
Message-Id: <200510130743.j9D7hYgF177345@saturn.cs.uml.edu>
Subject: GEN Meta-Schema and LCP/SM  extensions for Fwd/Rev Engineering
To: lechner@cs.uml.edu (Bob Lechner)
Date: Thu, 13 Oct 2005 03:43:34 -0400 (EDT)
Cc: sfrye@cs.uml.edu (Scot Frye), ralmonte@cs.uml.edu (Almonte), rayreeves@highstream.net (Ray Reeves)

To Recipients:

I would appreciate your comments on this.
It may be a break-through or a 
YALF (Yet-Another-Lechner-Folly.)

GEN Meta-Schema and LCP/SM  extensions for Fwd/Rev Engineering

1. Bibliography:

Pattern Languages of Program Design, A-W 1995 
This first PLoP Conf Proceedings
contains these two refs on STDs in LCP:

Jiri Soukup: Implementing Patterns [as interface classes) (395-412)  

Panu Viljamaa: Client-Specified Self(CSS),  (495-504)
(compares CSS to dynamic classes, instance-methods, delegation)

Other Books: 
-------------
James Rumgaugh: OMT Insights, SIGS Books 1996. 
This is a collection of short articles from JOOP.
Two chapters are of special interest to BDE and LCP:
Modeling Models and Viewing Views (MVC framework) May 1994 (pp 297-308)
Controlling Code (How to implement Dynamic Models) May 1993 (pp.309-313)

J Wierenga: Design Methods for Reactive Systems, M-K '2003
(Yourdon, Statemate and the UML)

Miro Samek: Practical Statecharts in C/C++, CMPBooks 2002.
(CD with lots of source code for Samek's Quantum Framework,
plus Eval. Version of a RTOS-32 for x86 CPUs
[RTKernel-32 from On-TIme SW (p. 266 fn1)] )

Samek Ch. 9, Implementations of QF, opens with this 
DLParnas quote:
"There is no trick  in building large systems quickly;
the quicker you build them, the larger they get!"

Raistrick et al (Kennedy-Carter): MDA with xUML.
CambridgeUPress, 2004 (with CD of iUMLite from K-C).

Binder: Testing O-O Systems, A-W 1999
A complete theoretical exposition of State Machines
is in one small (~100pp) part of this 1200 pp book.
Plus an extensive bibliography.


Articles:
---------
M. Ward: "Derivation of Data Intensive Algorithms by Formal
Transformation --The Schorr-Waite Graph Marking Algorithm",
IEEE Transactions on Software Engineering, 22(9), Sept 1996, pp 665-686"
(This paper inspired my Ghost Variables slides at $PH/ghostvarsRev3
and Prachee Sharma's MS thesis at UML/CS.)

Others TBD

-------------------------------------

2. LCP's relation to Soukup:

PLoP/Soukup implements class Composite as an interface
with methods that link other classes containing data,
without making the data-containing classss inter-dependent.

Does this resemble how LCP's application subclasses 
inherit from generic Active Classes, using delegation 
of BOTH method execution AND state model flow control 
from application objects to their counterpart Active 
Instances?

The app-objects are persistent table-row instances 
containing data (and embedded pointers) with no other
inerdependence besides fkeys from which pr_util
auto-generates embedded list-traversal pointers.

The methods which inter-relate the objects 
(the functional interfaces between classes)
are all contained in Soukup's Composite class.

In LCP, they are the responsibility of 
Active Classes with their method-specific State Models 
and Action Routines.


3. Possible extension of LCP:

LCP has AC as parent/container/aggregate of 
both ST and FT types of objects (table rows). 
All these are static properies of the AC.

[FT_rows are 1:1 related to FuncPtrArray 
pointers declared by StateModelCreateCompletely
and initialized by the linker.]

The Composite pattern has two types of components:
the leaf/atomic sub-type and the Composite sub-type.
The later is an aggregate of lower-level components.

A node HN of a diagram HG can have a second
HGid2 fkey that refers to is expansion.
In bde2SM, a diagram HG maps to a State Model SM,
and its nodes HN map 1:1 to states ST.
The second HNid2 to a nodes' expansion 
naturally maps to an SMid2 which is the SM
expansion of a STate. 

[This expansion is unique if it exists; furthermore,
it may be declared as the expansion of 
more than one STate in one or more SMs.
Sharing a sub-model among multiple STate components
and diagrams may be risky and may violate encapsulation.
However, it is done all the time in non-OO code 
by means of shared procedures and calls to 
library routines, These routines must be  
re-entrant if they can  be executed concurrently.

Execution of AI methods under LCP control
goes on concurrently, by inter-leaving their atomic
STate action routine calls, whose order is 
determined by the event dispatching discipline.

[This order may be FIFO or otherwise, including future
of Timer Service events in prioriy-queued
order of their timeout deadlines.]


4. New insights: 

4.1. Suppose SM inherits from an FT superclass. 
SM is composite because it is an aggregate
of states with their action routines.

4.2. Suppose FT has a second subclass of type EP for 
'EntryPoint' (a function pointer to executable code).
Note that an EP object might as well be used 
as the target Action Routine for an Atomic or 
indecomposable STate. 

Now each STate in a StateModel can have an FTid fkey
that refers to (by down-casting if necessary) 
to EITHER of its two subclasses: 
(1) an atomic EP (a compiled function), 
OR 
(2) an SM Composite (an aggregate of substates).

Now the LCP dispatcher would have an additional
responsibility: Decide whether to call an EP routine
which is compiled directly into executable code, 
or to descend into the Composite SM recursively,
and follow its event-driven control flow model,
traversing its STates until a PASS/FAIL return
action is reached. This 'recursive descent'
requires a pushdown stack that identifies the 
client StateModel SMid and its current state STid.

The Client AIid and its SM instance is suspended 
until the lower-level [AIid and its] SM instance 
completes its operation and exits.

To fully  emulate low-level program semantics,
the Server Active Instance must return a status code.
I would interpret this as a PASS (TRUE) exit,
or as a FAIL (FALSE) exit along with an error code.

Upon exit from the lowest-level SM, 
LCP pops the stack and re-enters its 'caller'.
I.e., it returns to the current STate of the 
client SM which invoked it.


After return from a 'Server' SM to a 'Client' ST, 
a PASS or FAIL verdict must be anticipated. 
[FAIL implies an associated error code value.] 

I conjecture that this provides semantics for  
descending into a sub-StateModel (subclass of FT) 
that is equivalent to evaluating a 'Guard 
Condition' (GC) predicate in the Client's STate,
since the GC also returns an error status code.

As a matter of fact, this GC could be implemented 
by invoking an instance of the EP subclass of FT.
Now the LCP interpreter becomes equivalent to
TRAIL's interpreter: each ST becomes a model
for an 'if P then A' statement: 

State Action A is unchanged from the current 
LCP implementation:
It is (always) an Atomic or compiled action,
with no return value.  However, it has side effects 
on local (and friend) class and instance) variables, 
and it can generate event messages to other AI's.

P is a (new) GC that can be implemented 
in one of two ways:
(P1) Call a predicate-evaluation function 
via its EntryPoint EP (Atomic, compiled subclass of FT) 
OR 
(P2) Suspend, descending into a nested State Model
(Composite, interpreted subclass of FT).

This implies that a ST object must now have TWO FTids
(but only one SMid, since FTid1 replaces SMid2):
(1) FTid1 to an expansion SM OR Atomic EP subtype 
of FT, to implement its Guard Condition (GC)
(this GC may be atomic or composite), and 
(2) FTid2 to its Atomic subtype of FT, 
which can only be an Atomic State Action. 

The most interesting thing about this approach
is that code migration between the atomic and 
composite types of If-conditioni predicates is 
relatively easy; in fact it should permit both:  

(1) Reverse engineeering: from code to State Model,
for any procedure-level code fragment. 

(2) Forward engineering: from State Model to
its (refactored) compiled code replacement.

One way this refactoring can be done is to translate
the interpreter's SM database into a two-level 
switch(state) and switch(event) case hierarchy,
with direct calls to predicate evaluation and
action routines. Other ways may be more O-O:
(Viljamaa's PLoP-95  article has 4 alternatives).


5. Reverse Engineering: 

Conjecture (to be verified or constrained):
Reverse engineering can move any procedure hierarchy 
into the LCP framework by simply defining the 
top-level entry point as an EP, and moving its argv[] 
parameter list into an Event Type with the same 
signature as the EP. The dispatcher then calls main()
with this argv[].
 
Then the sub-programs of main are decomposed one by one 
into State Models. Each call to a decomposed procedure
is implemented as a GC predicate of some STate of the 
client program.

The STate invokes the GC Predicate via its FTid1
fkey (or FTid_pp parent-poiner) data member.
LCP must build an Event Instance (EI)
which contains the actual argument list of the call.

The ET of this EI must have the same data member type sequence
(same signature) as the called procedure declaration did.
(The EIcurr pointer replaces the stack-based  pointer 
to these actual argument values.) 

[TBD: 
(1) extend chgen's meta-model to include 
a larger extensible set of AttributeTypes (AT).
This can be done by providing an ATid fkey in each TA. 
(ATid either augments or replaces the format field  
=I/F/Cnn/Tnn and is_key field =0/1/s in table TA.)
Associative entity TA now relates TT to AT.

(2) extend LCP's schema to include an M to N
association EA between ET and AT, analogous to
the M to N association TA between TT and AT in (1). 
Table AT will then support both the TA-list 
of TableAttribute types and the EA-list of 
EventType fields types for actual argument expressions.

[Conjecture: ET and TT can be merged, as can TA and EA.
Then each ET becomes just another TT object, albeit
at a different level of granularity in space/time.]


6. Forward Engineering:

Forward Engineering can now proceed by refactoring,
with prototype transformation and testing at 
the State Model level, by decomposing the one-state 
procedure EP into substates connected by state transitions:
i.e., by migrating the EP (atomic procedure) subclass of FT 
towards the other (Composite or State Model) subclass SM. 

After testing the LCP prototype if it turns out to 
to improve performance, iwe could generate a new 
compiled version of the code, 
by translating the nested State Model prototype
back into compilable and directly executable code.

Question: Can Reverse and/or Forward Engineering be automated? 
Probably. For insight into this, see Martin Ward's UK website: 
http://www.dur.ac.uk/martin.ward/

Martin's group developed "The FermaT Transformation Engine,
an industrial-strength program transformation system"
(free software under the GNU General Public License GPL).
(Scheme and Perl lovers will love this too. :-)

Conjecture: FermaT may be a good way to do forward and 
reverse engineering of code to/from state models.