WIXLIB

Relations Relations can be represented as graphs A hierarchy is a DAG (directed acyclic graph)M1M1a graphM1,2M1,1M3M2a DAGM1,2,1M4MM1,3M1,2,1,15M1,2,2M2M3M4M6Ch. 4a)50b)

The USES relation A uses B– A requires the correct operation of B– A can access the services exported by B throughits interface– it is “statically” defined– A depends on B to provide its services example: A calls a routine exported by B A is a client of B; B is a server In a modular system:– r n2 where n S – High fan-in and low fan-outCh. 451

Component Diagram for ABM Meaningfulnaming forservicesInterface Correctdirection for thedependencyarrows.DependencyCh. 452

Desirable property USES should be a hierarchy: e.g., Layered Style Hierarchy makes software easier to understand– we can proceed from leaf nodes (who do not use others)upwards They make software easier to build They make software easier to testCh. 453

Hierarchy Organizes the modular structure throughlevels of abstraction Each level defines an abstract (virtual)machine for the next level (OS architecture)– level can be defined precisely Mi has level 0 if no Mj exists s.t. Mi r Mj let k be the maximum level of all nodes Mj s.t. Mi r Mj.Then Mi has level k 1Ch. 454

IS COMPONENT OF Used to describe a higher level module as constituted bya number of lower level modules A IS COMPONENT OF B– B consists of several modules, of which one is A B COMPRISES A MS,i {Mk Mk S Mk IS COMPONENT OF Mi}we say that MS,i IMPLEMENTS MiCh. 455

A graphical viewM M M8 97M5M2M3M6M1M4M1(IS COMPONENT OF)M2M3M M M8 97M5M4M6(COMPRISES)They are a hierarchyCh. 456

Product families Careful recording of (hierarchical) USESrelation and IS COMPONENT OFsupports design of program familiesCh. 457

Interface vs. implementation (1) USES and IS COMPONENT OF partially describe anarchitecture To understand the nature of USES, we need to knowwhat a used module exports through its interface The client imports the resources that are exported byits servers Modules implement the exported resources Implementation is hidden to clientsCh. 458

Interface vs. implementation (2) Clear distinction between interface andimplementation is a key design principle Supports separation of concerns– clients care about resources exported from servers– servers care about implementation Interface acts as a contract between a module andits clientsCh. 459

Interface vs. implementation (3)interface is like the tip of the icebergCh. 460

Information hiding Basis for design (i.e. module decomposition) Implementation secrets are hidden to clients They can be changed freely if the change does notaffect the interface Golden design principle– INFORMATION HIDING Try to encapsulate changeable design decisions asimplementation secrets within module implementationsCh. 461

How to design module interfaces? Example: design of an interpreter forlanguage MINI– We introduce a SYMBOL TABLE module provides operations to– CREATE an entry for a new variable– GET the value associated with a variable– PUT a new value for a given variable– the module hides the internal data structure of thesymbol table– the data structure may freely change withoutaffecting clientsCh. 462

Interface design Interface should not reveal what weexpect may change later It should not reveal unnecessary details Interface acts as a firewall preventingaccess to hidden partsCh. 463

Prototyping Once an interface is defined,implementation can be done– first quickly but inefficiently– then progressively turned into the finalversion Initial version acts as a prototype thatevolves into the final productCh. 464

More on likely changesan example Policies may be separated from mechanisms Mechanism (technique, method)– ability to suspend and resume tasks in a concurrentsystem Policy (strategy, scheduling, protocol)– how do we select the next task to resume?» different scheduling policies are available» they may be hidden to clients» they can be encapsulated as module secretsCh. 465

Design notations Notations allow designs to be described precisely They can be textual or graphic We illustrate two sample notations– TDN (Textual Design Notation)– GDN (Graphical Design Notation) We discuss the notations provided by UMLCh. 466

TDN & GDN Illustrate how a notation may help indocumenting design Illustrate what a generic notation may looklike Are representative of many proposednotations TDN inherits from modern languages, likeJava, Ada, Ch. 467

An example of TDNmodule Xuses Y, Zexports var A : integer;type B : array (1. .10) of real;procedure C ( D: in out B; E: in integer; F: in real);Here is an optional natural-language description of whatA, B, and C actually are, along with possible constraintsor properties that clients need to know; for example, wemight specify that objects of type B sent to procedure Cshould be initialized by the client and should nevercontain all zeroes.implementationIf needed, here are general comments about the rationaleof the modularization, hints on the implementation, etc.is composed of R, Tend XCh. 468

Comments in TDN May be used to specify the protocol to befollowed by the clients so that exportedservices are correctly provided. Examples of protocols:– A certain operation which does the initialization ofthe module should be called before any otheroperation– An insert operation cannot be called if the table isfullCh. 469

Example (cont.)module Ruses Yexports var K : record . . . end;type B : array (1. .10) of real;procedure C (D: in out B; E: in integer; F: in real);implementationend R.module Tuses Y, Z, Rexports var A : integer;implementationend T.Ch. 470

Benefits Notation helps describe a design precisely Design can be assessed for consistency– having defined module X, modules R and T mustbe defined eventually if not incompleteness– R, T replace X either one or both must use Y, ZCh. 471

GDN description of module XModule YModule XModuleRAModuleTBCModule Zmodule Xuses Y, Zexports var A : integer;type B : array (1. .10) of real;procedure C ( D: in out B; E: in integer; F: in real);Here is an optional natural -language description of whatA, B, and C actually are, along with possible constraintsor properties that clients need to know; for example, wemight specify that objects of type B sent to procedure Cshould be initialized by the client and should nev ercontain all zeroes.implementationIf needed, here are general comments about the rationaleof the modularization, hints on the implementation, etc.is composed of R, Tend XCh. 472

X's decompositionmodule Xuses Y, Zexports var A : integer;type B : array (1. .10) of real;procedure C ( D: in out B; E: in integer; F: in real);Here is an optional natural -language description of whatA, B, and C actually are, along with possible constraintsor properties that clients need to know; for example, wemight specify that objects of type B sent to procedure Cshould be initialized by the client and should nev ercontain all zeroes.implementationIf needed, here are general comments about the rationaleof the modularization, hints on the implementation, etc.is composed of R, Tend Xmodule Ruses Yexports var K : record . . . end;type B : array (1. .10) of real;procedure C (D: in out B; E: in integer; F: in real);implementationend R.module Tuses Y, Z, Rexports var A : integer;implementationend TCh. 4.73

Code Compilation and ExecutionSource from: http://www.technocage.com/ ray/notespage.jsp?pageName ikiq1 -- This doesn't write hello worldbegin -- My first programvar x ;var y;-- lousy indentation andSPACing while y - 5 loopvar y;read x ,y;x 2 * (3 y);end;write 5; -- Not sure why five, but okay.endegq2q3iq4nbq0qfeq5nq6dCh. 474

Code Compilation and Execution 1. Generate Tokens3. Generate SyntaxTree From Tokens2. Use grammar to parseTokens (don’t panic!)Ch. 475

Code Compilation and Execution .7. ExecuteMachine LanguageOn the computer3. Generate Syntax Tree From Tokens5. Traverse treeTo generateAssembly Program6. GenerateMachine LanguageCode for CPUAssemblerProgramLDMOVLDADDLDCh. 4A, 4EHB, AC, (addrs)A, B, C(addrs 4), A4. AttachAssemblyCode76

Example: a compilerCh. 477

Other modulesmodule MAINuses ANALYZER, CODE GENERATORexports procedure MINI (PROG: in file of char;CODE: out file of char); end MAIN -- This doesn't write hello worldbegin -- My first programvar x ;var y;-- lousy indentation andSPACing while y - 5 loopvar y;read x ,y;x 2 * (3 y);end;write 5; -- Not sure why five,but okay.end module ANALYZERuses SYMBOL TABLE, ABSTRACT TREE HANDLERexports procedure ANALYZE (SOURCE: in file of char);SOURCE is analyzed; an abstract tree is producedby using the services provided by the tree handler,and recognized entities, with their attributes, arestored in the symbol table.end ANALYZERCh. 478

Other modulesmodule CODE GENERATORuses SYMBOL TABLE, ABSTRACT TREE HANDLERexports procedure CODE (OBJECT: out file of char);The abstract tree is traversed by using theoperations exported by theABSTRACT TREE HANDLER and accessingthe information stored in the symbol tablein order to generate code in the output file. end CODE GENERATORDraw the GDN of the Compiler Program. GDN isdiscussed in the next slideCh. 479

Component Diagram: CompilerCh. 480

Example of Software Architecturehttp://www.turing.toronto.edu/ brewste/bkshelf/NOT IN EXAMCh. 481

Usage of relations in Software Engineering:Architecture of ApacheS4ModularityPrinciple:Decomposing asystem based onLow-coupling &High-cohesionRest-of-sysS1S3NOTIN EXAMS2Ch. 4Color-codedLinks represent thelevel of dependencyof a file to another fileS582

Representing thearchitecture usinggraph visualizerS1-S4S5S3(Rigi) Association-links with differentstrengths to simplify the view Viewing the locus of interactionamong entities to evaluate therecovery process rest-of-sysDifferent types of links betweenboxes:– Association-links– Entity-usage links S2NOT IN EXAMFile-level analysisFunction-levelanalysisInsight into the system beforestarting the recoveryManual recoveryCh. 483

Categories of modules Functional modules– traditional form of modularization– provide a procedural abstraction– encapsulate an algorithm e.g. sorting module, fast Fourier transformmodule, Ch. 484

Categories of modules (cont.) Libraries– a group of related procedural abstractions e.g., mathematical libraries– implemented by routines of programming languages Common pools of data– data shared by different modules e.g., configuration constants– the COMMON FORTRAN constructCh. 485

Categories of modules (cont.) Abstract objects– Objects manipulated via interface functions– Data structure hidden to clients– Example: Symbol Table Abstract data types– Many instances of abstract objects may begenerated– Example: StackCh. 486

Abstract objects: an example A calculator of expressions expressed inPolish postfix forma*(b c) abc * a module implements a stack where thevalues of operands are shifted until anoperator is encountered in the expression(assume only binary operators)Ch. 487

Example (cont.)Interface of the abstract object STACK"exports:procedure PUSH (VAL: in integer);procedure POP 2 (VAL1, VAL2: out integer);Ch. 488

Design assessment How does the design anticipate changein type of expressions to be evaluated?– e.g., it does not adapt to unary operatorsCh. 489

Abstract data types (ADTs) A stack ADT allows to have more thanone instance of a stack moduleindicates that details of thedata structure are hiddenfrom the clientsmodule STACK HANDLERexportstype STACK ?;This is an abstract data -type module; the data structureis a secret hidden in the implementation part.procedure PUSH (S: in out STACK ; VAL: in integer);procedure POP (S: in out STACK ; VAL: out integer);function EMPTY (S: in STACK) : BOOLEAN;.end STACK HANDLERCh. 490

ADTs An ADT module is a module that exports a type, along with theoperations needed to access and manipulate objects of thattype. An ADT hides the representation of the type and the algorithmsused in the operations. The details of the type is dealt with inthe implementation of the ADT. Correspond to Java and C classes Concept may also be implemented by Ada private types andModula-2 opaque types May add notational details to specify if certain built-in operationsare available by default on instance objects of the ADT– e.g., type A TYPE: ? (: , ) indicates that assignment and equality checkare available

An example:simulation of a gas stationmodule FIFO CARSuses CARSexportstype QUEUE : ? ;procedure ENQUEUE (Q: in out QUEUE ; C: in CARS);procedure DEQUEUE (Q: in out QUEUE ; C: out CARS);function IS EMPTY (Q: in QUEUE) : BOOLEAN;function LENGTH (Q: in QUEUE) : NATURAL;procedure MERGE (Q1, Q2 : in QUEUE ; Q : out QUEUE);This is an abstract data-type module representingqueues of cars, handled in a strict FIFO way;queues are not assignable or checkable for equality,since “: ” and “ ” are not exported. Module GAS-STATIONend FIFO CARSuses FIFO CARSgasoline 1, gasoline 2, gasoline 3: QUEUEcar wash: QUEUE;that car: CARS;ENQUEUE (car wash, that car);MERGE (gasoline 1,Ch. 4 gasoline 2, gasoline 3);end GAS STATION92

Example ofModular Programming Using CModular Programming in CBy John R. Hayes, Courtesy of Embedded Systems ProgrammingNov 30 2001 (8:24 AM)URL: D 9900399DEFINITION MODULE fooEXPORT list of functions andNOTdataINdeclarations of exported functionsand dataEND fooEXAMIMPLEMENTATION MODULE fooIMPORT list of modules used. code .END fooCh. 493

Listing 1: foo.c(implementation)/* foo.c *//* Import needed interfaces: */#include "x.h"#include "y.h"/* Implements this interface;NOTused forINcompilerEXAMchecks: */#include "foo.h"int var1;static int var2;void Fun1(int *p) { . }static void Fun2(void) { . }Ch. 494

Listing 2: foo.h (interface)/* foo.h */#define var1 Foo var1/* prefixing function name with module name */NOT IN EXAM#define Fun1 FooFun1extern int var1;extern void Fun1(int *);Ch. 495

Missing Proper Header File#include stdio.h main() { printf("e %f\n", exp(1)); }NOT IN EXAMMay produce e 0.0000 instead of e 2.718282Program has a simple mistake. It is missing#include math.h . The use of function prototypesprevents such a problem. C compiler assumes thatexp(1) expected and integer argument andreturned an integer result.Ch. 496

Listing 3: client.c(implementation)/* client.c *//* Import needed interfaces: */#include "z.h"/* Implements this interface: */#include "client.h"NOTstatic void ClientFun(void){int z;.Fun1(z);.}IN EXAMAn integer passed to Fun1 instead of pointer to integer.#include “foo.h” is missing. Client.c will compile but linkerCh. 4 an error message97Can not find Fun1 and will send

Listing 4: priqueue.h(interface)/* priqueue.h */#define Enqueue PriEnqueue#define Dequeue PriDequeue#define CreateQueue PriCreateQueueNOT IN EXAMtypedef struct priority queue struct * Priority queue;extern void Enqueue(Priority queue, int priority, void *data);extern void *Dequeue(Priority queue);extern Priority queue CreateQueue(void);int x;float f;void *p &x; // p points to x*(int*)p 2;p &r;// p points to r*(float*)p 1.1;Ch. 498

Modular programming consists of separating implementation frominterface and hiding information in the implementation. In C this is achieved by placing the interface definition in a header fileand the implementation in a source file. Disciplined use of static is used to hide implementation details. Theinterface definition forms the link between a module and its clients.NOT IN EXAM The module includes its own interface definition to confirm that itimplements the advertised interface; a client module imports/includesthe interface definition to verify that it is using the interface correctly. Put the constant definitions and data structure declarations in theheader for inclusion by its corresponding C source file. Now, if aconstant or data structure is only used by one source file, place themin that source file. If a constant or data type is used throughout anapplication, they belong in a traditional header file.Ch. 499

However, software architecture is more than “components and connectors”, or “major elements of a system”. It is a collection of views, patterns, stakeholders, and roles [SEI]. Therefore, Software architecture provides the necessary mea