COURSE COM3360 / NTU SE737 PROGRESS ==================================================== (all chapter and page numbers refer to the Demeter book: Karl Lieberherr, Adaptive Object-oriented Software: The Demeter Method with Propagation Patterns, PWS Publishing Company. See http://www.ccs.neu.edu/home/lieber/book.html) LECTURES ARE SUMMARIZED IN REVERSE ORDER (first lecture at end of file) Reachable from course home page URL: http://www.ccs.neu.edu/home/lieber/com3360.html Archived at URL: ftp://ftp.ccs.neu.edu/pub/people/lieber/com3360-f95-history.txt 10. lecture: Dec. 4, 1995 =========================================================================== Review of the OOPSLA'95 workshop on adaptable systems. The workshop report is accessible through: http://www.ccs.neu.edu/research/demeter/adaptable-systems An important unifying theme to understand adaptable software is Polya's Inventor's Paradox. This was an unexpected result of the workshop. Review of adaptive object-oriented software What is important is the high-level approach to software development which you learned in this course. You learned to think in terms of large and varied families of programs instead of single programs. From another point of view, you learned to recognize subtle but often occurring redundancies in object-oriented software and you learned a technique to eliminate the redundancies using adaptive programs and class dictionaries. To practice the concepts, we used the Demeter Tools/C++ but they are secondary to the course since they only offer _one_ of many possible implementations of the concepts of adaptive software. You learned how the Demeter Tools/C++ translate propagation patterns and class dictionaries into C++. What you learned in this course is readily transferable to other programming languages, like CLOS or Smalltalk or Java. Design Patterns We covered the descriptive components of design patterns and looked at a few more examples. Design patterns are also based on Polya's Inventor's paradox. Problems are solved at the abstract level in terms of patterns and then the solution is customized by applying the patterns to a specific context. Design patterns for adaptive software may be found at: http://www.ccs.neu.edu/research/demeter/adaptive-patterns Final exam is on Monday, Dec. 11 during class time (2 hours). For NTU students, the exam will be one week later. Practice exams are in the exams directory of $OO. I hope to see several of you in COM3362, the advanced version of this course. See the course home page which is accessible from my home page http://www.ccs.neu.edu/home/lieber In any case, I hope I have provided you with a valuable, and academically stimulating introduction to object-oriented systems which at the same time is also valued in the job market place. I hope you come back from time to time to the Demeter home page http://www.ccs.neu.edu/research/demeter to learn the latest about adaptive software and its implementation. Please help spread the word. =========================================================================== 9. lecture: Nov. 27, 1995 Style rules for class dictionaries (from chapter 12) Terminal buffer rule Normalization Other methods Jacobson's Method: OOSE Based on use cases: A use case is a subset of the behavior of the system, described as a sequence of interactions in response to an initial triggering event. Patterns (from the Design Patterns book by Gamma et al.) A design pattern consists of a pattern name, the problem and its context, the solution and the consequences (results and tradeoffs) of applying the pattern. Example: Memento Pattern: (page 285 Design Pattern book) Problem: Capture an objects's state without violating encapsulation. Solution: Use g_copy and a Memento class Consequences: Structure-shy approach Might be expensive The memento pattern can be viewed as an application of the Law of Demeter for propagation patterns. ====================== beginning of notes The Memento Pattern (Adaptive version) Is also about structure-shy programming. Commit to less structure when you write a class. Class dictionary ================ ConstraintSolver = State. // Originator ConstraintSolverMemento = State. // Memento MoveCommand = <_state> ConstraintSolverMemento <_delta> Point <_target> Graphic. // The Caretaker is the MoveCommand class *component* ADAPTIVE_MEMENTO < ... > *static* *operation* ConstraintSolver* Instance() *wrapper* ConstraintSolver (@ return_val = this; @) *operation* ConstraintSolverMemento* CreateMemento() *traverse* *from* ConstraintSolver *to* State *wrapper* State // do not need the friend mechanism here (@ return_val = new ConstraintSolverMemento(this -> g_copy()); @) *operation* void SetMemento(ConstraintSolverMemento* cm) *traverse* *from* ConstraintSolver *to* State *wrapper* State *replace-by* // improved iteration interface cm *go* *from* ConstraintSolverMemento *to* State // (@ cm -> get_state(); @) *operation* void Execute() *wrapper* MoveCommand (@ ConstraintSolver* solver = ConstraintSolver::Instance(); _state = solver->CreateMemento(); _target->Move(_delta); solver->Solve(); @) *operation* void UnExecute() *wrapper* MoveCommand (@ ConstraintSolver* solver = ConstraintSolver::Instance(); _target->Move(- _delta); solver->SetMemento(_state); // restore solver state solver->Solve(); @) // alternative solution which is not structure-shy *operation* void Execute() *wrapper* MoveCommand (@ ConstraintSolver* solver = ConstraintSolver::Instance(); _state = solver->get_state() -> g_copy(); //CreateMemento(); _target->Move(_delta); solver->Solve(); @) *operation* void UnExecute() *wrapper* MoveCommand (@ ConstraintSolver* solver = ConstraintSolver::Instance(); _target->Move(- _delta); solver->set_state(_state); // restore solver state // solver->SetMemento(_state); // restore solver state solver->Solve(); @) This alternative solution hardwires details of the ConstraintSolver object into the MoveCommand-object (the fact that the solver has a part called state). The MoveCommand-object commits to more structure. We can view the Memento pattern as coming from the desire to make the call _state = solver->get_state() -> g_copy(); adaptive. ====================== end of notes Memory management use rset_x(...) (see Demeter-FAQ) use g_delete(...) use man g_delete to learn more. Case study graph drawing graphical user interface Three use cases =========================================================== 8. lecture: Nov. 20, 1995 Style rules for class dictionaries First discuss flat class graphs only (page 489, exercise 15.7) Want to come up with a definition of "inductiveness" which excludes class graphs like: A = B. B : C. C = A. The idea is to "exclude cylces which have no way out" Class graph slice Class graph slice of a class graph 2 applications of class graph slices: growth plans and inductiveness A growth plan is a sequence of class graph slices increasing in size. Useful for testing adaptive programs in stages. A vertex v is inductive, if there is a cycle-free class graphs slice anchored at v. Examples of inductive and non-inductive class graphs. Generalization to non-flat class dictionaries and class dictionaries with optional parts. Law of Demeter for classes. Non-inductive class dictionaries and infinite loops and cyclic objects. Making a non-inductive class dictionary inductive. An inductive cd which is also LL(1) allows to create a tree-object from sentence. Tree-object might need object linking by propagation pattern to create cyclic objects from context. Example: Mothers = List(Mother). Mother = Child Name. Child = [ Mother] Name. After mother list has been created, we can process the list and link each child to his or her mother. Minimizing class dictionaries Object-equivalence Size of a class dictionary minimization in two steps: first minimize construction edges, followed by minimizing alternation edges For construction edge minimization there is an efficient algorithm. For alternation edge minimization there is no efficient algorithm known: the problem is NP-hard. Special case of alternation edge minimization: tree property. Efficient algorithm. Also allows us to test whether cd is object-equivalent to a single inheritance cd. Eliminating multiple inheritance Design language for adaptive programs Uses ABC: Adaptive Behavioral Component Idea: use one master traversal to control several other subordinate traversals. ABC is represented by ABC-object at run-time. An example of ABCs, simulated by transportation patterns illustrates the idea. We can simulate ABCs with transportation patterns (by copying and editing). For now we view ABCs as a design language which you may want to use in your project for documenting your adaptive programs which you write in your projects. *ABC* <*traverse* t> Integer count() { *var* Integer numItems ; *prelude* {numItems = 0;} *traverse* t *wrapper* (Target(t)) *after* {numItems++;} *return* {numItems;}} *end* *ABC* <*traverse* t; *vertex* rType; *label* item > rType sum() { *var* rType total; *prelude* {total = 0 ;} *traverse* {t;} *wrapper* Target(t) *after* {total += item;} // violation of LoD for AP *return* {total;}} *end* *ABC* <*traverse* t; *vertex* rType, *label* item> rType average() { *var* count() c; // c has type count() sum() s; // s has type sum() *traverse* {t;} *return* {if c<>0 then rtype(s/c) else undef; }} *end* *ABC* void employeeStats() { *directives* CoToDept = *from* Company *to* Department; DeptToEmp = *from* Department *to* Emp; CoDeptEmp = *join* (CoToDept,DeptToEmp) *var* count() empsPerDept; average() avgSalPerEmp; average() avgEmpsPerDept; *traverse* {CoDeptEmp;} *wrapper* Company *after* {cout << avgEmpsPerDept;} *wrapper* Department *after* {cout << avgSalPerEmp;}} ======================================== Simulation with transportation patterns test environment for running: /proj/lieber/envs/sim-abc *operation* void employeeStats() *traverse* *from* Company *via* Department *to* Employee *wrapper* Department *suffix* (@ cout << "Average salary per employee " << avgSalPerEmp << endl; @) *wrapper* Company *suffix* (@ cout << "Average # of employees per department " << avgEmpsPerDept << endl; @) // simulated ABC empsPerDept *carry* *out* int empsPerDept *along* *from* Department *to* Employee *wrapper* Department *prefix* (@ cout << "create ABC empsPerDept.count" << endl; empsPerDept = 0; @) *suffix* (@ cout << "complete ABC empsPerDept.count" << endl; @) *wrapper* Employee (@ cout << "increment empsPerDept.count" << endl; empsPerDept++; @) // simulated ABC avgSalPerEmp *carry* *out* float avgSalPerEmp, *out* int count1, *out* int sum1 *along* *from* Department *to* Employee *wrapper* Department *prefix* (@ cout << "create ABC avgSalPerEmp.average" << endl; cout << "create ABC avgSalPerEmp.average.count" << endl; cout << "create ABC avgSalPerEmp.average.sum" << endl; count1 = 0; sum1 = 0 ; @) *suffix* (@ cout << "complete ABC avgSalPerEmp.average" << endl; cout << "complete ABC avgSalPerEmp.average.count" << endl; cout << "complete ABC avgSalPerEmp.average.sum" << endl; avgSalPerEmp = sum1/count1; @) *wrapper* Employee *suffix* (@ cout << "increment avgSalPerEmp.average.count" << endl; count1++; cout << "add avgSalPerEmp.average.sum" << endl; sum1 = sum1 + *salary; @) // simulated ABC avgEmpsPerDept *carry* *out* float avgEmpsPerDept, *out* int count2, *out* int sum2 *along* *from* Company *to* Department *wrapper* Company *prefix* (@ cout << "create ABC avgEmpsPerDept.average" << endl; cout << "create ABC avgEmpsPerDept.average.count" << endl; cout << "create ABC avgEmpsPerDept.average.sum" << endl; count2 = 0; sum2 = 0 ; @) *suffix* (@ cout << "complete ABC avgEmpsPerDept.average" << endl; cout << "complete ABC avgEmpsPerDept.average.count" << endl; cout << "complete ABC avgEmpsPerDept.average.sum" << endl; avgEmpsPerDept = sum2/count2; @) *wrapper* Department *suffix* (@ cout << "increment avgEmpsPerDept.average.count" << endl; count2++; cout << "add avgEmpsPerDept.average.sum" << endl; sum2 = sum2 + empsPerDept; @) The example shows the advantages of ABCs over transportation patterns. ========================================================================== 7. lecture: Nov. 13, 1995 Law of Demeter (Object form) Using material in the IEEE Software paper (Sept. 1989). The Law of Demeter (class form): efficiently checkable but too coarse. The Law of Demeter (object form): not efficiently checkable but catches the intent. Example: A = B C D. B = C. C = D. D = . A::f() {this->get_b()->get_c()->get_d()->f2();} satisfies the class form but violates the object form. Law of Demeter for propagation patterns (Brad Appleton's proposal) We can simplify the LoD for adaptive programming: ==================================== When we write a wrapper for a class C for a propagation pattern with traversal and operation name f, then we can only use the functions of the following classes: the argument classes of f, including C. the classes which are instantiated in the wrapper. ==================================== For the Demeter Tools/C++ we need the following addendum: Operations of terminal classes (DemIdent, DemNumber, etc.) may also be called. ================================================================== Transforming programs which violate this rule. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ From now on we apply the LoD for propagation patterns. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Improved wrappers (checking well-formedness of a join) Discussion of *initially* *finally-break* *break* etc. (Not yet implemented in tools.) State Machines Many OO design methods, e.g. the Unified Method by Booch-Rumbaugh-Jacobson support a dynamic modelling language using state machines. The state machines are used to describe state transitions of objects with states. Most objects have just one state. But usually some of them have several states and then a state machine is used to model those objects. A class dictionary for state machines with substates is given and its implementation is discussed. Style rules for class dictionary graphs (chapter 12) Inductiveness of class dictionary graphs is described informally. The concept of class graph slices is introduced. It is good to discuss this first for flat class graphs (this was not done in the lecture). See page 489 of the Demeter Book. Class graph slices are not only useful to define inductiveness but also to define the concept of a growth plan (see page 489). For non-flat class dictionary graphs, the concept of a semi-class dictionary graph is needed. See page 500 of Demeter Book. =============================================================== 6. lecture: Nov. 6, 1995 First part: discussion of midterm Solutions will be put on WWW next week. Instructional objectives which are covered by exam. Philosophy behind exam: as a side effect learn something useful about improving directives. Brief discussion of Prototype design pattern: put prototypyical objects in files and read them in when application starts. g_parse can be called for any file. We briefly discussed the need for a better iteration interface for adaptive software. We discussed the implementation of condensers. *carry* *out* A* a = ... is implemented as an argument of type A*&. (a reference to a pointer or variable parameter of a pointer type in Pascal terminology.) Transportation patterns use the three modes *in*, *out*, *inout* to indicate whether an argument goes in, out or both. *inout* has the same implementation as *out* and is used for readability reasons. The same primitives are used in Ada. Second part: Composition of propagation patterns and transportation patterns We discussed the motivation behind the two restrictions summarized on page 319 of the Demeter book. We noted that the tools call the Transportation Entry Restriction the Transportation Source Restriction. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 5. lecture: Oct. 30, 1995 First part: midterm for non NTU SE737 students Extended propagation directives delete edges and/or vertices before traversal Transportation patterns (Chapter 10 of Demeter Book) Simulating them with propagation patterns Advantages of transportation patterns: easier signature changes, more structure-shy (or more efficient) Broadcaster and condensers Transportation patterns as reusable units Simulating transportation patterns with variable declarations at beginning of *.pp files: (@ ... @) Projects Discussion of list of suggested projects 4. lecture: Oct. 23, 1995 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Propagation directives: Primitive: [A,B] = *from* A *to* B PathSet_G([A,B]) = set of all paths from A to B in graph G. Operations: join: D1.D2 well-formedness condition: Target(D1) = Source(D2) (tools are more general) PathSet_G(D1.D2) = PathSet_G(D1) . PathSet_G(D2) (. on the right-hand-side is concatenation of paths) syntax: *join* (*from* A *to* B, *from* B *to* C) (this is equivalent to: *from* A *via* B *to* C) merge: D1+D2 well-formedness condition: Source(D1) = Source(D2) and Target(D1) = Target(D2) (tools are more general) PathSet_G(D1+D2) = PathSet_G(D1) \union PathSet_G(D2) syntax: *merge* (*from* A *via* B *to* C, *from* A * *via* X to* C) What is a path? First assume that the class dictionaries are flat, i.e., no alternation class has outgoing construction edges. In this context, a path is any sequence of construction and subclass edges. (not covered: intersection of directives. Also very useful. Not provided by tools.) Incompleteness: [A,B], join and merge can not express the path set: A,b1,B for the class graph: A = B B. B = . Therefore, we generalize the primitive [A,B] to [A,c,B] where c is a constraint on the paths from A to B. Constraint table: vertices edges positive *via* *through* negative (*bypassing*) *bypassing* (*bypassing*) means not implemented in the tools. With *through* and *bypassing* we can use construction, alternation edges (tools are more general). Bypassing a set edges means bypassing all of them. *through* a set of edges means to go through at least one. Reason: The negation of *through* is *bypassing*. The wild card symbol is allowed in edge specifications. >>>>>> answers question left open in the lecture. Using *via* {a set of vertices} means to go through at least one of the vertices in the set. >>>>>> answers question left open in the lecture. See the syntax summary for propagation directives on page 180. PathSet versus Graph: The path sets may be infinite sets (in the case of cycles in the class dictionary) while the graph corresponding to a path set (the union of all edges and vertices in the path set) is always finite and it provides a ``summary'' of the path set. Price for graph abstraction: consistency. short-cut (page 464) zig-zag (page 464) Repairing short-cut: split pp into two. See chapter 15 for a detailed discussion of consistency and propagation directives involving [A,B], join and merge. (Flat class dictionary graphs only.) How work propagation directives for non-flat class dictionaries? We need to use a refined path concept: Introduce for each alternation edge in the cdg an inheritance edge in the opposite direction. The set of inheritance edges is called: EI. (EA: alternation, EC: construction). A path must satisfy the regular expression: ((EI* EC)|EA)* Propagation patterns with void return type with non-void return type: return_val and *init* Wrapper may be defined for sets of vertices and sets of edges. Tcl/Tk and Isthmus: See http://www.ccs.neu.edu/research/demeter/course/isthmus for the source and documentation about Isthmus. For any given cd and a set of pps, Isthmus extends Tcl with the behavior provided by the cd and pps. In other words, Isthmus is a Tcl/Tk extension generator which brings adaptivity to the Tcl/Tk community. Remarks about hw4: reminder: main.tcl cleans up. A quick intro to Tcl/Tk. See /course/com3360/tcl-tk for further resources. Specifically, the tutorial: tutorial/wtour Midterm is next week: open book and open notes. Covers material from homeworks (including hw 4) and lectures. 3. lecture: broadcast Oct. 16, taped Oct. 10 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Object Construction and Presentation (from chapter 11 of Demeter book): representing objects in a structure-shy way propagation pattern / object-oriented program = object description (sentence) / object graph Turning a class dictionary graph into a class dictionary Printing objects Language defined by class dictionary Ambiguity of class dictionaries first sets: LL(1) conditions Rule 1 follow sets: LL(1) conditions Rule 2 LL(1) conditions: throw out some of the non-ambiguous class dictionaries Parsing: inverse of printing: both are a bijection if LL(1) conditions hold class dictionary for class dictionaries class dictionary for propagation patterns Design Patterns (from the design pattern book) Decorator pattern Command pattern Lecture was pretaped and will be broadcast at the regular time. Salil Pradhan will be there to answer questions. I will be back on Friday. My office hours are canceled for next week. When I am back I will report on our full day workshop on Adaptable and Adaptive Software at OOPSLA '95. We also demo Demeter and we have two posters at OOPSLA '95. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2. lecture: Oct. 2, 1995 some viewgraphs selected from ECOOP '94 and Object World Germany presentations at URL: http://www.ccs.neu.edu/research/demeter/course/viewgraphs/tutorial.ps other viewgraphs selected from URL: http://www.ccs.neu.edu/research/demeter/course/viewgraphs/course-viewgraphs.ps several of the pictures are also in the Demeter book Inventor's Paradox (Chapter 4) Polya's advice: Instead of solving a concrete problem, solve a more general one. Applications to computer science (data structure generalization) and mathematics (octahedron). Developing the concept of propagation patterns with OMT class model. class wrappers edge wrappers (from Chapter 8) History: Law of Demeter and the evolution of adaptive software History of software development (Chapter 4) Computer memory example: evolution of adaptive program through three class dictionary graphs Graphical User Interface example: Drawing graphs Evolution through two class dictionary graphs ========================================== To run the program we discussed: Go to /course/com1205/hw/sample-application/oopsla1/generated and run the program by typing run /course/com1205/hw/sample-application/oopsla1/generated is an improved form of /proj/adaptive2/projects/com3399-w95/bofam/hw4 In /course/com1205/hw/sample-application/oopsla1/ you see all important files. ========================================== The Isthmus tool: An glue generator for Tcl/Tk and adaptive programs ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ The current Isthmus manual is at URL: ftp://ftp.ccs.neu.edu/pub/people/lieber/isthmus-u-guide.ps It needs improvement! ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Code generation: (Chapter 8.2) From path sets to propagation graph to C++ code +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1. lecture: Sep. 25, 1995 Brief introduction to adaptive object-oriented software Class dictionary graphs (Chapter 6) Development by example: (see Chapter 5) 1. level: An object O 2. level: A class dictionary for describing objects similar to O. 3. level: A mathematical structure for describing class dictionary graphs. Graphical representation of class dictionary graphs first focus on core model: construction and alternation classes and edges extensions for convenience: repetition classes optional parts Textual representation of class dictionary graphs Objectives covered: (see Chapter 14) 5,6,7,9 Object graphs (Chapter 6) Textual and graphical representation Conformance to class graph Objectives covered: 24,25,26,27,29 A tour through adaptive programming (see Chapter 4 and Chapter 15) Course organization see class packet 1 Hw: see ccs.courses.com3360 and /course/com3360/hw/1/assign.txt A tour through the use of the Demeter system (see the Quick Reference Guide in 18.2, page 578) sem-check demeter run Objectives covered: 80 =================================================================== Reachable from URL: http://www.ccs.neu.edu/home/lieber/com3360.html