Home

Software Component Engineering

1. CHAPTER 3 ABSTRACT AND CONCRETE TEMPLATES DECOUPLING 61 In this case the latter looks simpler But be careful C requires that seemingly innocuous space between the two gt characters The error message from failing to type it is likely to be very cryptic Luckily someone who has done this before has put the code of Figure 3 11 into the Resolve C Component Catalog Notice how this code formats the actual parameters one per line so the little gotcha mentioned above will not arise O Fame ES ES RR ES OS SS DS SS SE SS DER see RR eee Concrete Template Sequence Kernel la C SS ifndef CT SEQUENCE KERNEL 1A C define CT_SEQUENCE KERNEL 1A C 1 LI 2 ES fi Global Context 259222 E22 50H 3235 IS Er Zee ES De Ze ee ee ee Se SEES include CT Sequence Kernel la h include CT Sequence Kernel C h endif CT SEQUENCE KERNEL 1A C Figure 3 11 CT Sequence Kernel_la_C h After bringing this component into scope you can instantiate it as follows concrete instance class Sequence Of Integer instantiates Sequence Kernel la C lt Integer gt Notice also a new component relation in the code of Figure 3 11 specializes In the analogous code of Figure 3 9 the program creates a new concrete instance by instantiating a concrete template The relation connecting a template and an instance created from it
2. current BINARY_TREE CLIENT VIEW BINARY_TREE 13 t2 Compose current BINARY_TREE 14 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Height Formal Contract Specification Ee math operation HEIGHT t binary tree of Item integer satisfies if t empty tree then HEIGHT t 0 else there exists x Item left right binary tree of Item t compose x left right and HEIGHT t 1 max HEIGHT left HEIGHT right TEL function Integer Height is abstract Fl ensures Height HEIGHT self TAS Informal Description A call to the Height operation has the form of an expression tl Hetght zas This operation returns an Integer value which is the height of t1 i e the number of items on the longest path from the root of t to any leaf of rl BINARY_TREE CLIENT VIEW BINARY_TREE 15 Sample Traces Statement Statement Object Values Object values tl Height tl Height BINARY_TREE 16 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Size Formal Contract Specification function Integer Size is abstract ensures Size self 1 Informal Description A call to the Size operation has the form of an expression EL SIZE ar This operation returns an Integer value which is the number of items in the binary tree t1 i e IZI Sample Traces Statement Object Values Id Name Table Motivation Applicability and Indications for Use The pro
3. An kas CHAPTER 2 ABSTRACT AND CONCRETE TEMPLATES GENERALIZATION if k 1 output lt lt lt lt all lt lt x An output lt lt lt lt a 0 lt lt An global function body Real Original Evaluation preserves Polynomial Coefficients amp a preserves Real x object Real result object Integer k while k lt a Length 1 rl preserves a x alters result k maintains there exists s string of real Is k and s is prefix ofa and result EVAL s x decreases jal k 1x object Real term alk object Integer i Compute the k th term a k x k while i lt k preserves x K alters term i maintains i lt k and term fterm x i decreases k i 1 term x 1 Add this term to total so far result term k 28 return result SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 global function body Real Horner Iterative Evaluation preserves Polynomial Coefficients amp a preserves Real x object Real result object Integer k while k gt 0 fat preserves a X alters result k maintains there exists s Isi lal s is suffix of a EVAL s result decreases k 1 1 result k return result a Length 1 string of real k 1 and and x result x alk global function body Real Horner Recursive Evaluation pr
4. a type that is similar to Sorting Machine except that when you remove an item it is not the next one in sorted order but the last one that was put in i e it observes a different temporal not a value based ordering SORTING_MACHINE 2 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Component Family Members Abstract Components Sorting_Machine_Kernel the programming type of interest with the operations below Insert e Remove First e Remove Any e Size Change To Extraction Phase e Is In Extraction_Phase Concrete Components Sorting Machine Kernel I C This is a checking implementation of Sorting Machine Kernel in which the execution time for each of the operations constructor Insert Remove Any Size Change To Extraction Phase and Is In Extraction Phase is constant while the execution time for Remove First and for the destructor are proportional to the number of items in the object All objects of this type have the interface of Sorting Machine Kernel with the concrete template name Sorting Machine Kernel I C substituted for the abstract template name Sorting Machine Kernel To bring this component into the context you write include CT Sorting Machine Kernel 1 C h You also need to have in scope a utility class that implements the abstract template utility class General Are In Order for the type of Item you want to use which determines the sorting order For example to sort 7ext values
5. Along with Get_From comes the shorthand operator gt gt The following two statements are equivalent nl Get From input input gt gt nl NATURAL CLIENT VIEW Sample Traces Statement nl Get From input input gt gt nl input gt gt nl NATURAL 21 Object Values nl 45142398 input is_open input ext_name input content nl 13 input is open input ext_ name input content nl input is open input ext_ name input content nl input is open input ext_ name input content true 13 n 7 n n5 true 7 n n5 true n5 true wow NATURAL 22 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Put_To lt lt Formal Contract Specification math operation DIGIT CHARACTER i integer character satisfies if 0 lt i lt 10 then DIGIT CHARACTER i TO CHARACTER TO_INTEGER TOE a else DIGIT_CHARACTER iy 7 07 math operation POSITIVE OUTPUT_REP n NATURAL MODEL string of character satisfies if n 0 then POSITIVE OUTPUT REP n empty string else there exists k d integer n 10 k d and 0 lt d lt 10 and POSITIVE OUTPUT REP n POSITIVE OUTPUT REP k lt DIGIT CHARACTER d gt math operation OUTPUT REP gee NATURAL MODEL string of character satisfies if n 0 then OUTPUT REP n 0 else OUTPUT REP n POSITIVE OUTPUT REP n Lay procedure Put To alters Character OStream str is_ab
6. Informal Description Note This and the other operation descriptions that follow refer to these objects in examples object Natural Number 1 C nl n2 n3 object Integer i object Character IStream input object Character OStream output A call to the Multiply_By_Radix operation has the form nl Multiply By Radix i This operation multiplies n by RADIX and then adds i to it You may make this call only if i could be a digit in base RADIX i e 0 lt i lt RADIX This operation and three others Divide_By_Radix Discrete_Log and Radix allow you as a client to think about and manipulate a Natural_Kernel object s value through a view of its radix representation in the base RADIX The key to understanding Natural_Kernel is to realize that there is a difference among the following concepts a number an abstract idea the way we normally think about that number to perform mathematical calculations which involves the radix representation discussed below and the way we write that number so we can communicate with each other also discussed below For instance here are some ways to think about and write the single abstract natural number we usually call 42 4 10 2 10 in decimal base 10 ordinarily written 42 because 10 is the default base in normal mathematical usage 5 8 2 80 in octal base 8 often written 52g 1 334 1 3242e3140030 in ternary base 3 often written 11203 1 25 0 2
7. Statement Object Values sl lt 92 6 18 gt i 37 sl lt 37 6 18 gt i 92 sl lt 92 6 18 gt i 92 lt A 255 6 gt lt 167 9217 34 2995 0 gt lt 92 16 921 34 STACK 8 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Length Formal Contract Specification function Integer Length is_abstract rl ensures Length self 1 Informal Description A call to the Length operation has the form of an expression sl Length This operation returns an Integer value which is the length of the string q1 i e Ig I Sample Traces Statement Object Values sl lt 6 92 13 18 gt i 68 Fa Be Ze sl lt 6 92 13 18 gt i 4 Static_Array Motivation Applicability and Indications for Use The programming type Static_Array allows you to repeatedly access and update a fixed size table of items of an arbitrary type You index into the table using an Integer value that lies within an interval determined when you instantiate a concrete template that implements Static_Array_Kernel For example suppose you want to record the high temperature for each month of the year To do this you can declare an Static_Array object whose items are of type Real and set 1t up to be indexed by the values 1 through 12 for the months of the year Each entry in the table initially has an initial value for type Real 1 e 0 0 You may access and update the value as
8. a type that allows you to add items in sequence one at a time but when you remove an item it is the first one that was put in e Stack a type that allows you to add items in sequence one at a time but when you remove an item it is the last most recent one that was put in e Sequence a type that allows you to add or remove items in sequence one at a time accessing an item at any time by random access based on its current position Component Family Members Abstract Components List Kernel the programming type of interest with the operations below Move To Start Move To Finish e Advance e Add Right Remove Right e Accessor Left Length Right Length Concrete Components List Kernel la C This is a checking implementation of List Kernel in which the execution time for each of the operations constructor Move To Start Move To Finish Advance Add Right Remove Right the accessor Left Length and Right Length is constant while the execution time for the destructor is proportional to the sum of the lengths LIST 2 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 of the two strings in the tuple All objects of this type have the interface of List_Kernel with the concrete template name List_Kernel_la_C substituted for the abstract template name List_Kernel To bring this component into the context you write include CT List Kernel la _C h Component Coupling Diagram List_ Kernel
9. an integer do not meet this condition and cannot be interpreted as an Integer value The second error message is a lot less end user friendly than the first one But at least you know something went haywire at the point you typed a response to the prompt Agreed it would be nicer for the program to inform you Sorry you have not typed an integer Please try again It is possible to change the program to do this rather than reading into an Integer object you could read the user s response into a Text object which is always legal then check whether it can be converted to an Integer But there are plenty of even less friendly things the program could do For instance it could forge blithely ahead and keep on computing apparently happy as a clam only to surprise you later with a bizarre result or a terrible death by segmentation fault or death by bus error for which the root cause would be much harder to find 3 2 1 The Defensiveness Dilemma You might be tempted to conclude that because programs should be bulletproof for end users the same maxim applies to a software component s operations whose users are client programs that invoke the services of that component That is you might expect that every operation with a non trivial precondition like Get_From for Integer should always check that precondition to make sure the client program does not crash In fact if you jumped to this conclusion then you would be in good co
10. lt 9 6 13 90 gt lt 9613 900 gt SEQUENCE 6 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Remove Formal Contract Specification procedure Remove preserves Integer pos produces Item x is abstract requires 0 lt pos lt self ensures there exists a b string of Item lal pos and self a lt x gt b and self a b 1x Informal Description A call to the Remove operation has the form sl Remove i n This operation removes the item in position i of string s and returns it in n You may make this call only if 0 lt i lt ls l The numbering of positions in the string s starts at 0 For example to remove the leftmost item of s and return it in n you might write sl Remove 0 n Sample Traces Statement Object Values lt 9 6 90 13 gt 279 sl Remove i n sl Remove 2 n SEQUENCE CLIENT VIEW SEQUENCE 7 Accessor Formal Contract Specification function Items operator preserves Integer pos is abstract requires 0 lt pos lt self ensures there exists a b string of Item lal pos and self a lt self pos gt b 1 Informal Description A call to the accessor operator has the form of an expression Sil asy This expression acts as the name of an object of type tem whose value is the item in position i of string s You may make this call only if 0 lt i lt lsZl The numbering of positions in
11. t3 Decompose i tl t2 t1l Decompose i t2 t3 BINARY_TREE CLIENT VIEW BINARY_TREE 11 Accessor Formal Contract Specification function Items operator preserves Accessor Position amp current is abstract requires self empty tree ensures there exists left right binary tree of Item self compose self current left right 1 Informal Description A call to the accessor operator has the form of an expression tl current Ao og This expression acts as the name of an object of type tem whose value is the item at the root of tl You may make this call only if is not empty The special word current is the only thing that can appear between in the accessor It always refers to the single item at the root of the tree which is the one that would be separated from the two subtrees if you called the Decompose operation at the point where you are using the accessor operator You may use t current wherever any other object of type Item may appear The accessor operator like all functions preserves its arguments But it is important to realize that the accessor expression t1 current does not simply denote the value of the root item in it acts as the name of an object of type Item which you may consider to lie at the root of rl This means that not only may you use the expression t current as a value of type Item you may even change the value of the object called 1 cur
12. Sorry both integers must be non negative and one must be positive And this brings us to the second problem with the party line approach Suppose Greatest_Common_Divisor were an operation provided by an off the shelf software component If the precondition were checked in the body of the operation the error message could not be expected to make nearly as much sense to the end user as the one above Perhaps this is not 2 This example illustrates albeit unwittingly as it is tangential to the real point here something about recursion The programmer who implements an operation by writing a recursive body for it is simultaneously the operation s implementer and a client programmer calling that operation This suggests that you should think of client programmer and operation implementer not as two different individuals but as two different roles Sometimes one person plays both roles at the same time sometimes different individuals are involved 50 SOFTWARE COMPONENT ENGINEERING VOLUME 2 obvious from the present application example because the arguments to Greatest_Common_ Divisor are just numbers and have no other application specific meaning But in another situation you might like the end user to see a message like this Sorry the number of apples must be non negative and the number of oranges must be positive Obviously the off the shelf component has no notion of apples or oranges only of numbers and cannot be
13. la_C of Sequence Kernel remember there might be others and they have different names e h means the C code is not compiled in advance but rather will be compiled with the application program that is including it As with a concrete instance bringing a concrete template into scope automatically brings into scope the abstract template in this case Sequence_Kernel that specifies the interface contract it implements 2 2 2 Instantiating the Concrete Template to Create a Concrete Instance After a concrete template component is in scope you need to instantiate it in order to use it This step is the only extra one required when using templates as opposed to instances and fortunately it is pretty easy The simple declaration that instantiates Sequence Kernel la Cin Poly_Eval cpp comes immediately after all the components to be used are brought into scope It uses the keywords concrete_instance class and instantiates as follows concrete instance class Polynomial Coefficients instantiates Sequence Kernel la C lt Real gt In Poly_Eval cpp the application programmer has decided that mathematically speaking the coefficients of a polynomial can be treated as a string of real numbers He she has consulted the interface contract specification Sequence_Kernel and has noted that the mathematical model of a Sequence_Kernel_la_C object is a string the type of entries in the string being determined by a single template par
14. rn Value into this range by treating it as the numerator of a fraction whose denominator is LIMIT i e rn Limit Suppose LIMIT 10000 for some particular implementation of Random_Kernel as it turns out it is for the implementation Random_Kernel_1 Then if the value of rn is 2500 the expression To_Real rn Value To_Real rn Limit evaluates to 0 25 if rn 6978 then the expression evaluates to 0 6978 etc More generally to get a random real number from a uniform distribution over a b the appropriate translation and scaling transformation is a b a To Real rn Value To Real rn Limit It is easy to put such code into a component for a shared catalog and make it generally useful beyond the current application Just as a checking component can make calls to the underlying component it checks a concrete extension can make calls to the underlying component it extends Normally as in this case the component being extended is a kernel implementation This technique for adding functionality to a component family is called layering Calls to operations of the component being extended simply pass through the concrete extension layer unscathed to be handled by the component being extended while calls to the additional operations in the concrete extension do their work by calling the operations of the underlying component 64 SOFTWARE COMPONENT ENGINEERING VOLUME 2 Y client call to tT kernel op
15. t abracadabra false cse t ece sl false ece cse t abracadabra 7 a FF bt a e SORTING_MACHINE CLIENT VIEW SORTING_MACHINE 9 Size Formal Contract Specification function Integer Size is abstract ee ensures Size self contents 1 Informal Description A call to the Size operation has the form of an expression STS GC ii This operation returns an Integer value which is the number of elements of the multiset s1 contents including copies of a single value as many times as it occurs i e ls contentsl Sample Traces Statement Object Values sl true ece cse i 68 i sl size 0 aa sl true ece cse i 2 SORTING_MACHINE 10 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Change_To_Extraction_Phase Formal Contract Specification procedure Change To Extraction Phase is abstract Ze requires self inserting true ensures self false self contents LAL Informal Description A call to the Change_To_Extraction_Phase operation has the form s1 Change To Extraction Phase This operation changes s from insertion phase to extraction phase You may make this call only if s is in insertion phase Sample Traces Statement Object Values SORTING_MACHINE CLIENT VIEW SORTING_MACHINE 11 Is_In_Extraction_Phase Formal Contract Specification function Boolean Is In Extraction Phase
16. 1 TER Informal Description A call to the Decrement operation has the form nl Decrement This operation subtracts one from n You may make this call only if nl is strictly positive since Natural_Type objects always have non negative values Sample Traces EN IE NATURAL CLIENT VIEW NATURAL 13 Compare Formal Contract Specification function Integer Compare preserves Natural Numbers n is abstract ensures if self lt n then Compare 1 else if self n then Compare 0 else Compare 1 PAL Informal Description A call to the Compare operation has the form of an expression nl Compare n2 This operation returns an Integer value of 1 if nl lt n2 0 if n1 n2 and 1 if n1 gt n2 Sample Traces Statement Object Values 45142398 1996 13 i nl Compare n2 45142398 1996 i n2 Compare n1 45142398 1996 1 i nl Compare n2 NATURAL 14 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Add Formal Contract Specification procedure Add preserves Natural Numbers n is abstract A ensures self self n ER Informal Description A call to the Add operation has the form nl Add n2 This operation adds n2 to n1 Sample Traces Statement Object Values nl 26 n2 952 nl 978 n2 952 NATURAL CLIENT VIEW NATURAL 15 Subtract Formal Contract Specification procedure Subtract preserves Natural Numbers n
17. Abstract to Abstract In addition to a new kernel type and its standard and kernel operations some clients might want additional operations that are not essential but rather are merely useful Figure 1 5 shows an example The declaration of Random_Uniform begins abstract instance class Random Uniform extends abstract instance Random Kernel 14 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 which states the dependence relationship between the new class Random_Uniform and the existing class Random_Kernel namely Random_Uniform extends Random_Kernel i SS aana EX Abstract Instance Random Uniform Se SE SS SEES SSE Re Se Sense ay ifndef AI RANDOM UNIFORM define AI RANDOM UNIFORM 1 public VASK ensures Uniform Real a b a TO REAL self TO REAL LIMIT 1 Fr ensures Uniform Integer j TO INTEGER TO REAL k j 1 TO REAL self TO _REAL LIMIT ne he endif AI RANDOM UNIFORM Figure 1 5 AI Random Uniform h CHAPTER 1 ABSTRACT AND CONCRETE INSTANCES 15 The meaning of the keyword extends here where it relates two abstract components is that any concrete component that claims to implement Random_Uniform must implement the interface contract specified in Random_Kernel and in addition it must implement the extra interface contracts for the new operations specified in Random_Uniform Phrased another way the behavior of any concrete component that can
18. Upper_Bound Formal Contract Specification function Integer Upper Bound is abstract ensures Upper Bound upper EL Informal Description A call to the Upper_Bound operation has the form of an expression al Upper Bound This operation returns an Integer value which is the upper bound on the interval of legal indices into al i e upper Sample Traces Statement Statements A RR Values 1 7 abcd Po a a abed 8 go go 9 bucks 7 abcd 8 go 9 bucks Text Text 1s a built in type concrete instance in Resolve C which is included when you bring RESOLVE_Foundation h into the global context The name Text is therefore unusual it is the name of a concrete template even though it does not end in _2 or 1a or the like Motivation Applicability and Indications for Use Resolve C also includes Boolean Character Integer and Real as built in types An object of any of these types has a very simple mathematical model i e a simple mathematical type boolean character integer and real respectively While Boolean Integer and Real objects clearly are useful in a variety of situations Character objects usually seem less valuable The reason is that normally you want to combine individual Character objects into sequences or strings of characters If you need to deal with a sequence of characters as a unit then you should use a Text object whose mathem
19. contain information that is required to understand the new component An important implication of these fundamental design rules is e Concrete Component Dependence Rule Avoid introducing a dependence on a concrete component If the dependence of a concrete component on another component is required create that dependence to an abstract component There is a nice way to satisfy the requirements of the concrete component dependence rule as illustrated in this chapter by two important examples of its application checking components and concrete extensions Simply put in every new component create a formal template parameter a concrete instance for each abstract component whose interface contracts it depends on restricting that parameter to be an implementation of the associated interface contract Checking components arise from an analysis of the defensiveness dilemma the policy decision faced by every software engineer regarding which party to an interface contract is responsible for checking the preconditions of operations A careful analysis clearly supports the policy known as design by contract summarized as follows e Design by Contract Rule Do not call an operation when its precondition is not satisfied unless you are willing to accept any behavior whatsoever from that point onward during execution of the program This policy is logically sound as the one in force for a final delivered software product During the software deve
20. is abstract J requires self gt n ensures self fself n EEJ Informal Description A call to the Subtract operation has the form nl Subtract n2 This operation subtracts n2 from n1 You may make this call only if n is at least as large as n2 Sample Traces Statement Object Values nl 101 n2 37 n1 Subtract n2 ee aa nl 64 n2 37 NATURAL 16 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Multiply Formal Contract Specification procedure Multiply preserves Natural Numbers n is abstract ensures self self n 1 Informal Description A call to the Multiply operation has the form nl Multiply n2 This operation multiplies n by n2 Sample Traces Statement Object Values nl 123 n2 94 n1 Multiply n2 AAA nl 11562 n2 94 NATURAL CLIENT VIEW NATURAL 17 Divide Formal Contract Specification procedure Divide preserves Natural Number n produces Natural Number amp rem is abstract ES requires n gt 0 ensures self self n rem and 0 lt rem lt n 1 Informal Description A call to the Divide operation has the form nl Divide n2 n3 This operation divides n by n2 and returns with the remainder in n3 Sample Traces Statement A E ll Values xl ES A 103 3243455 2 r NATURAL 18 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Copy_To Fo
21. is abstract ee ensures Is In Extraction Phase not self inserting 1 Informal Description A call to the s_In_Extraction_Phase operation has the form of an expression s1 Is In Extraction Phase This operation returns a Boolean value which is true iff s is in extraction phase Sample Traces Statement Object Values sl true ece cse true s1 Is In Extraction Phase sl true ec b false SORTING_MACHINE 12 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Stack Motivation Applicability and Indications for Use The programming type Stack allows you to collect and later process items in last in first out LIFO order For example suppose you need to keep track of the locations where a mouse has been while exploring a maze sort of like bread crumbs that it leaves on the ground so it can retrace its path to look for unexplored corridors To do this you can create a Stack object whose elements are of a type that records the location of a single bread crumb Then you can push its location whenever the mouse drops a bread crumb and pop a location to determine where the mouse should go whenever it wants to back up Other operations allow you to access the top item in a Stack object and to determine its length Related Components e Queue a type that is similar to Stack except that when you remove an item it is not the last one that was put in but rather the fir
22. is initial x and self compose x empty string LIZ Informal Description The model for Tree_Kernel is a tree of items which initially has size 1 The root is an initial value for type Item and the root has no children A Tree_Kernel object may be arbitrarily large Like all RESOLVE C types Tree_Kernel comes with operator amp and Clear Note The sample traces for this and the other operation descriptions refer to the type Tree_Of_Integer which is the result of the following instantiation concrete_instance class Tree_Of_Integer instantiates Tree Kernel la _ C lt Integer gt O Sample Traces Statement Object Values tl TREE CLIENT VIEW TREE 5 Add Formal Contract Specification procedure Add preserves Integer pos consumes Subtree Types t is abstract requires 0 lt pos and pos lt children self ensures there exists a b string of tree of Item lal pos and children self a b and self compose root self a lt t gt b 1 Informal Description Note This and the other operation descriptions refer to these objects in examples object Tree Of Integer tl t2 t3 t4 object Integer i n A call to the Add operation has the form tl Add i t2 This operation adds tree 12 in position i of the string of children of the root of i e ina position such that the number of children of the root of t before the newly added one is equal to i Notic
23. only for work actually needed The component family Sorting_Machine allows you to collect and later process items in sorted order It addresses both problems noted above A Sorting_Machine object is a collection just like a Queue or a Stack The main difference is that with a Queue you put items in and get them back in first in first out order with a Stack you put items in and get them back in last in first out order with a Sorting_Machine you put items in and get them back in sorted order So no surprise there are operations to insert items and remove items as well as to report the number of items in the object An important difference is that Sorting_Machine has two phase behavior Initially a Sorting_Machine object is in the insertion phase which means it is ready for you to insert some Items Once you have inserted all the items of interest you explicitly tell the object to change to extraction phase At this point you can remove items as many items as you want one at a time according to the ordering of interest For completeness there is also an operation to remove any arbitrary item which you can invoke in either phase This operation ignores the ordering among entries Related Components e Queue a type that is similar to Sorting Machine except that when you remove an item it is not the next one in sorted order but the first one that was put in i e it observes a temporal not a value based ordering e Stack
24. output content x1301nn1 0 NATURAL 24 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Partial_Map Motivation Applicability and Indications for Use The programming type Partial_Map allows you to build query and dismantle a set of ordered pairs 2 tuples whose two components are of two arbitrary types Generally the first component of each pair which is considered to be a unique key allows you to lookup the second component of that pair which is considered to be information associated with the key value There can be at most one pair in the set with any given key value For example suppose you need to keep a simple database of employees and their salaries To do this you can create a Partial_Map object whose key type is Text to store an employee name this is also called the domain type hence its name D Item and whose associated information type is Integer to store an employee salary this is also called the range type hence its name R_Item To enter the salary of an employee you simply define into the Partial_Map object the pair consisting of the employee s name and the employee s salary Later you can lookup the employee s salary by using the employee s name as the key Other operations allow you to manipulate and observe properties of a Partial_Map object such as its size 1 e the number of pairs it holds Related Components None Component Family Members Abstract Components e Parti
25. then there is no parameter box for that formal parameter in the component s CCD because an unrestricted template parameter induces no dependencies on any other specific software component For example the CCDs for the Sequence components in Chapter 2 do not have a parameter box for tem because it is an unrestricted template parameter Remember the purpose of the CCD is to show design time dependencies and a parameter box for an unrestricted template parameter would have no arrows out of it and therefore would introduce and make apparent no dependencies whatsoever there is no sense even drawing it 3 2 5 Instantiating a Checking Component Now suppose you are a client programmer who wants to use a checked implementation of Natural_Kernel say Natural_Kernel_1 during the software development process You must 7 In C C programs you would use the keywords virtual public in place of the Resolve C keyword checks 58 SOFTWARE COMPONENT ENGINEERING VOLUME 2 as usual first bring into scope using include statements the checking component as well as the implementation to be checked Then you simply instantiate the checking component like any other template concrete instance class Natural Kernel 1 C instantiates Natural Kernel C lt Natural Kernel 1 gt O Now you can declare objects of type Natural_Kernel_1_C object Natural Kernel 1 Cn m Client calls to Multiply_By_Radix on the objects n and m are now checked for pre
26. 3 7 _ Concrete Template Natural Kernel C 0 Bannan nnn nn nn nn nn nnn nce ifndef CT NATURAL KERNEL C define CT NATURAL KERNEL C 1 56 SOFTWARE COMPONENT ENGINEERING VOLUME 2 public procedure body Multiply By Radix preserves Integer k assert 0 lt k o lt k assert k lt self Radix k lt RADIX y endif CT NATURAL KERNEL C Figure 3 7 CT Natural Kernel_C h The suffix _C in the name of the component is a Resolve C convention indicating that the component checks the preconditions of calls to all operations that have non trivial preconditions Notice that the include statement in Figure 3 7 appears in a formal comment This strange construction is used when the C compiler doesn t need to include the file in order to compile this code but the human reader does need to understand the component whose code is in the included file In other words from the standpoint of the logical dependencies between components that are recorded in a CCD Natural_Kernel_C depends on Natural_Kernel Because of the way Resolve style components are encoded in C you do not directly express this dependence in the code needed by the compiler The logical dependence on Natural_Kernel appears in the template s parameter list The declaration of the formal parameter Natural_Base
27. C header files are required for templates because C templates are not separately compiled For uniformity and simplicity every component discussed in this book is defined in a h file whether it is a template or an instance When you bring a concrete instance into scope the abstract instance that contains the interface contract specification comes along for the ride by transitivity because the concrete component includes the abstract component it implements In fact by virtue of the Resolve C discipline s rules for component design and coding explicitly including a component with include automatically brings into scope all the other components abstract and concrete on which it depends either directly or indirectly 1 2 2 Using the Concrete Instance How do you use an off the shelf component in a client program There is a simple rule once you have brought an off the shelf concrete component into scope as described above you may use the type and operations exactly as though they were built in You may declare objects of the type provided by the component and call the operations provided by the component exactly as you do with the built in types and their operations To illustrate Monte Carlo declares an object rn of type Random Uniform Generator 1 and calls its operations Generate_Next which generates a new random number held in rn and Uniform_Real which transforms the random number held in rn into a correspondi
28. Columbus namel San Francisco ID_NAME_TABLE 12 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Look_Up_Id_Via_Name Formal Contract Specification procedure Look Up Id Via Name produces Integer amp id preserves Text name is abstract rl preserves self requires NAME IS DEFINED IN self name ensures id name is in self 1 Informal Description A call to the Look Up Id Via Name operation has the form t1 Look Up Id Via Name idl namel This operation finds the pair in t with name name and returns a copy of the id associated with namel as the value of id You may make this call only if there is a pair in t whose name component equals namel ID_NAME_TABLE CLIENT VIEW ID_NAME_TABLE 13 Sample Traces Statement Object Values 3 Santa Fe 8 San Francisco 2 Columbus idl 27702 namel Santa Fe tl Look Up Id Via Name idl namel FR Santa Fe 3 8 San Francisco 2 3 Columbus idl namel Santa Fe 3 Santa Fe 8 San Francisco 2 Columbus 49 t1 Look Up Id Via Name idl Columbus 3 Santa Fe 8 San Francisco 2 2 Columbus ID_NAME_TABLE 14 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Id Is In Table Formal Contract Specification function Boolean Id Is In Table preserves Integer id is abstract ensures Id Is In Table ID IS DEFINED IN self id
29. ID IS DEFINED IN m ID NAME TABLE MODEL id integer boolean is there exists name string of character id name is in m math definition NAME IS DEFINED IN m ID NAME TABLE MODEL name string of character boolea is there exists id integer id name is in m Las standard abstract operations Id Name Table Kernel PEL ld Name Table Kernel is modeled by ID NAME TABLE MODEL initialization ensures self empty set LAS Informal Description The model for ald Name Table Kernel object is a finite set of ordered pairs each of which is an integer and a string of characters Each integer and each string of characters is unique among all the pairs in the set An Id_Name_Table_Kernel object is initially empty An d_Name_Table_Kernel object may be an arbitrarily large set Like all Resolve C types Id Name Table Kernel comes with operator amp and Clear ID_NAME_TABLE 4 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Sample Traces Statement Object Values AAA ID_NAME_TABLE CLIENT VIEW ID_NAME_TABLE 5 Add Id Name Pair Formal Contract Specification procedure Add Id Name Pair preserves Integer id consumes Text amp name is abstract requires not ID IS DEFINED IN self id and not NAME IS DEFINED IN self name ensures self self union id name 1x Informal Description Note This and the other operation descriptions
30. Text Text Text Integer gt field name Employee 0 Text first name field name Employee 1 Text middle name field name Employee 2 Text last_name field name Employee 3 Text address field name Employee 4 Integer salary Second approach structured record alternatively not in addition concrete instance class Full Name instantiates Record lt Text Text Text field name Full Name 0 Text first name field name Full Name 1 Text middle name field name Full Name 2 Text last name concrete instance class Employee instantiates Record lt Full Name Text Integer FF field_name Employee 0 Full_Name name field_name Employee 1 Text address field_name Employee 2 Integer salary A closely related component is Array The most important difference is that the individual objects in a Record may be of different types while all the individual objects in an Array and in most other collections of objects must be of the same type However a Record can contain at most ten fields and the number of fields is fixed at instantiation time while an Array may contain arbitrarily many objects and its size is determined at run time by calling the Set_Bounds operation One other component is closely related to Record It is essentially identical to Record except that its name is Representat
31. _ then multiply that by x and add a _ and so on With a little thought you can deduce that the original approach to the computation uses about n 2 multiplications and n additions where Horner s rule uses only n multiplications and n additions The problem we wish to explore is how much execution speed difference there is between these two methods and also between a recursive and an iterative implementation of Horner s rule The user s manual for an application program to answer these questions might be Run the program by typing the command Poly_Eval It reads from stdin a non negative integer which is the degree of the polynomial to be evaluated i e n followed by the n 1 real valued coefficients in the order a through a followed by the real valued point at which the polynomial is to be evaluated i e x Each number is on its own line of input The program then prints out the polynomial followed by the evaluation of the polynomial at the point x and the execution time for the obvious method and for Horner s rule both iterative and recursive and then quits The program that follows illustrates a solution along with many other things LIE Of FR Basra e SS SS SSS Se Bra nnSrEanS2 sn EN fr Main Program Polynomial evaluation timing comparison I Besseres o a g SSR Seesen Date 9 August 1999 revised 24 November 2006 l Author Bruce W Weide Z7 Brief User s Manual 24 SOFTWARE
32. an Integer value which is the length of the string of children of the root of tl TREE 12 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Sample Traces Statement A E Values t1 Number Of Children i t2 Number Of Children TREE CLIENT VIEW TREE 13 Size Formal Contract Specification function Integer Size is abstract ensures Size self 1 Informal Description A call to the Size operation has the form of an expression EL SIZE IO its This operation returns an Integer value which is the size of the tree i e It I TREE 14 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Sample Traces Statement Object Values
33. and decoupling You just need to combine into a single formla parameter list the template parameters that are used for both purposes The code for Sequence_Kernel_C illustrates this in Figure 3 10 RE 25222222252 55522222555 820222452272 eee fl Concrete Template Sequence Kernel C R NESS SEES SH ifndef CT SEQUENCE KERNEL C define CT SEQUENCE KERNEL C 1 Ni N f f Global Context 2772227272222 200 2 A e a en a ee ee RA include AT Sequence Kernel h 7 I f Posse Sess SSS SASS SS ESS 70H SSH HH IE BROS Hg ME Interface HH HH HH Ho R 2 HE ae Sa aa class Sequence Kernel C checks concrete instance Sequence Base public procedure body Add preserves Integer pos consumes Item amp x assert 0 lt pos 0 lt pos assert pos lt self Length pos lt self self Sequence Base Add pos x procedure body Remove preserves Integer pos produces Item x 60 SOFTWARE COMPONENT ENGINEERING VOLUME 2 assert 0 lt pos 0 lt pos assert pos lt self Length pos lt self self Sequence Base Remove pos x function body Item amp operator preserves Integer pos assert 0 lt pos 0 lt pos assert pos lt self Length pos lt self F7 endif CT_SEQUENCE KERNEL C Figure 3 10 CT Sequence Kernel_C h There are two new features in thi
34. are children of the root of T e g in Figure 2 children T lt T1 T2 Tk gt Related Components Binary Tree a type that is similar to a Tree where each item has at most two children Component Family Members Abstract Components Tree Kernel the programming type of interest including the operations below e Add e Remove e Accessor Number Of Children e Size Concrete Components Tree Kernel la C This is a checking implementation of Tree Kernel in which the execution time for each of the operations constructor Number Of Children Size and the accessor is constant while the execution time for Add and Remove is proportional to the number of children of the root of the tree and the execution time for the destructor is proportional to the size of the tree All objects of this type have the interface of Tree Kernel with the concrete template name Tree Kernel la C substituted for the abstract template name Tree Kernel To bring this component into the context you write include CT Tree Kernel la_C h TREE CLIENT VIEW Component Coupling Diagram Tree_ Kernel implements Tree_ Kernel_1a_C TREE 3 TREE 4 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Descriptions Tree_Kernel Type and Standard Operations Formal Contract Specification standard abstract operations Tree Kernel fet Tree Kernel is modeled by tree of Item initialization ensures there exists x Item
35. be explained using Random_Uniform can be partially explained using Random_Kernel Random_Uniform itself contains only the explanations of two extra operations called Uniform_Real and Uniform_Integer This style of organizing interface contract specifications is known as specification by difference or incremental specification Rather than putting all operation specifications in one place you separate them into logically cohesive pieces and assemble them in mix and match fashion Figure 1 6 shows how to depict in a component coupling diagram or CCD the fact that the extends relation holds between these two abstract instances Recall that the only relations captured in CCDs in Volume 1 were uses and implements This is a new relation Random_ Kernel extends Random_ Uniform Figure 1 6 The extends relation may hold between two abstract instances The same approach can be used to extend any abstract description with any other so long as the functionalities being added together do not conflict This is always the case if you follow the Resolve C discipline although it is not the case if you aren t careful For example C will let you extend abstract instance Random_Kernel by adding an operation called Set Value with a single Integer parameter and almost the same specification as above except that the ensures clause is different Using the rules of C the new definition would override or replace the original one rather than ad
36. boolean initialization ensures self empty string BAR procedure Remove preserves Integer pos produces Boolean amp x is abstract ql requires 0 lt pos lt self ensures 20 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 there exists a b string of boolean lal pos and self a lt x gt b and self a b KEA br You could specify the other operations in a similar way by copying the interface contract specifications almost directly from the operations of Text Then you could do the same thing for a new abstract instance defining a type called say Sequence_Of_Integer whose model would be a string of integers Sequence_Of_Integer would have the same kernel operations as Sequence_Of_Boolean except that the entries in an object s string model would be of type Integer Now if you re paying attention you ll see it would be silly to key in Sequence Of Integer from scratch Instead you d just copy the file for Sequence Of Boolean and replace all occurrences of Boolean by Integer using a text editor The places to change are double underlined below shown after the substitutions have been made abstract instance class Sequence Of Integer public standard abstract operations Sequence Of Integer Ze Sequence Of Integer is modeled by string of integer initialization ensures self empty string LEJ procedure Remove preserves Integer pos produces Integer amp x i
37. created by C generally would result in incorrect behavior so it is helpful that the C compiler can be made to detect these violations of the Resolve C discipline 5 In C C programs you would use the keywords virtual void to introduce a method returning no value in place of the Resolve C keyword procedure 6 In C C programs you would use 0 in place of the Resolve C keyword is abstract CHAPTER 1 ABSTRACT AND CONCRETE INSTANCES 13 Another interesting thing here is self in the ensures clause Recall that the way you invoke an operation that is associated with a type also known in object oriented programming parlance as a method is by saying something like this rand Set Value k Here k must be an object of type Integer and rand must be an object of a type that implements Random_Kernel in order for the compiler to consider the call to be valid By way of contrast if Set_Value were a global operation then you would invoke it like this Set_Value rand k In this situation two formal parameters would be declared in the header of Set_Value so there would be two names to use in the ensures clause But with Ser_Value being a method for type Random_Kernel rather than a global operation there is only one formal parameter and therefore only one name to use in the ensures clause In either case the formal parameter to which k is bound at the time of the call has a name n But what is rand bound to in the interf
38. in non decreasing lexicographic order there is a catalog component already available Text Are In Order 1 Before instantiating Sorting Machine Kernel I C as in the Sorting Machine Kernel description below you must bring this component into scope as follows include CI Text Are In Order 1 h There are a few other available components of this kind for the built in types but often you ll have to build your own utility class for a new type and or a new ordering by following these as examples SORTING_MACHINE CLIENT VIEW SORTING_MACHINE 3 Component Coupling Diagram Sorting_ General_ Machine _ Are_In_ Kernel Order implements implements Sorting_ Machine_ Kernel_1_C SORTING_MACHINE 4 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Descriptions Sorting_Machine_Kernel Type and Standard Operations Formal Contract Specification Pl math subtype SORTING MACHINE MODEL is inserting boolean contents finite multiset of Item TEL standard abstract operations Sorting Machine Kernel pel Sorting Machine Kernel is modeled by SORTING_MACHINE MODEL initialization ensures self true empty multiset 1 Informal Description The model for Sorting_Machine_Kernel is an ordered pair a boolean that records the phase of the object true if the machine is in insertion phase false if it is in extraction phase and a finite multiset of Items Initially the machine is in insertion phase and the
39. is complete The first tree of Figure 2 would be complete if the subtrees whose roots are s and t were exchanged and the second tree of Figure 2 would be complete if g were the left subtree and not the right subtree of h We are now ready to define the mathematical idea of binary trees over a set of items That is binary tree of A is the name of a mathematical type and we need to define the set of values associated with the type assuming we know the set of values associated with mathematical type A In tree theory there is a special mathematical operation function the compose function that takes as arguments a root item from A say x a binary tree of A say T and another binary tree of A say T2 and produces a binary tree of A say 73 with x as the root of 73 with TI as the left subtree of 73 and with 72 as the right subtree of 73 This is pictured in Figure 5 x EN Figure 5 The tree 73 compose x TI T2 We now define inductively the set of binary trees over set A or binary tree of A which is the type name you use when writing the mathematics of trees This set consists of exactly those binary trees that can be built up from the empty tree by zero or more applications of the compose function according to the following cases e Base case The empty tree denoted empty tree is an element of binary trees over set A e Inductive case If 7 and T2 are elements of binary trees over set A and if x is an element o
40. is followed by a restriction clause a formal comment that says Natural Base implements Natural_Kernel In the Sequence example in Chapter 2 the formal parameter tem was unrestricted the client programmer may bind any Resolve C type to Item Not so here When instantiating Natural_Kernel_C the client programmer must bind to the formal parameter Natural_Base a concrete instance that implements Natural_Kernel it may be Natural_Kernel_1 or Natural_Kernel_2 or any other implementation of Natural_Kernel that exists now or might be developed in the future but it may not be say Text Thus Natural_Kernel_C depends on Natural_Kernel because the client programmer must know about Natural_Kernel at least enough to decide whether the concrete component to be used as the actual parameter claims to implement it The other new feature in this code is the declaration of Natural_Kernel_C itself which says class Natural Kernel C checks concrete instance Natural Base This code which the C compiler does care about means that every concrete instance created from concrete template Natural_Kernel_C by fixing the parameter Natural_Base depends on Natural_Base in the stated way 1 e it checks it Moreover it means that operations CHAPTER 3 ABSTRACT AND CONCRETE TEMPLATES DECOUPLING 57 of the checked implementation that have no preconditions are executed directly from that component with no screening by the checking component 7 Notice
41. layered on top of an implementation of the kernel The new operation works by calling the kernel operations to do its job In both these situations there is an underlying concrete component that does the bulk of the work Wrapped around it is a thin layer of new code that invokes the operations of the underlying component Both the underlying component and the layer around it are concrete components and clearly the latter depends on the former The use of templates to decouple this concrete to concrete dependence is a crucial idea in software component engineering 70 SOFTWARE COMPONENT ENGINEERING VOLUME 2 Client View Appendices Array Binary_Tree Id Name Table List Natural Partial Map Queue Record Sequence Set Sorting Machine Stack Static Array Text Tree CLIENT VIEW APPENDICES SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Array Motivation Applicability and Indications for Use The programming type Array allows you to set up and then repeatedly access and update a fixed size table of items of an arbitrary type You index into the table using an Integer value that lies within an interval determined when you set the bounds of the Array object This set up occurs after you declare the object and typically is done just once for each object but you may reuse the same Array object by resetting its bounds For example suppose you want to record the high temperature for each day of the mont
42. like 0 main 1 operator gt gt Character IStream amp Integer amp 2 Integer Get From Character IStream amp 3 To_Integer Text Violated assertion at File class sce rcpp RESOLVE Foundation Conversion Operations Conversion Operations cpp Line 552 Operation To Integer Violated assertion is lt OK_Text gt lt White Space gt lt Digits gt lt White Space gt lt White Space gt At An gt lt Digits gt Pe OUT NE O EFT SEO TESTER t is in language of OK Text and CHAPTER 3 ABSTRACT AND CONCRETE TEMPLATES DECOUPLING 47 2147483648 lt TO INTEGER t lt 2147483647 Abort The relatively cryptic violated assertion message comes from the operation To_Integer which is invoked by the operation Get From for the built in type Integer which is invoked by the gt gt operator in the main program of Euclid The Get_From operation for Integer 1t turns out has a non trivial precondition the next line of characters to be read from the source of characters that is attached to the Character IStream object input at this point normally the keyboard must be interpretable as an Integer value Specifically the next line must begin with zero or more whitespace characters followed by at least one decimal digit character followed by zero or more whitespace characters The characters you typed in response to the prompt i e
43. more common requirements of a software system is to process or list some data in sorted order The data may be of any type e g Text and the ordering may be anything e g reverse alphabetical order A typical approach to meeting this requirement is to put the data in some collection object perhaps an Array or Queue or Sequence or Static Array and then to pass that object to a procedure operation that rearranges the entries into the desired order This conventional way of doing things has at least two serious disadvantages e You have to write a different implementation of sorting for each collection type even if you can parameterize it by the type of data in the collection and the ordering This leads to a proliferation of implementations of the same sorting algorithm which differ only in how they access and manipulate the data in the collection It would be much better if sorting could be done without regard for the type of collection that holds the data to be sorted e The design is inefficient if you don t really need all the data in sorted order For instance if you need to find the top ten reasons out of 1000 that software component engineering is important then you can do it by sorting all 1000 reasons in decreasing order of importance and looking at just the first ten But there is no need to have sorted the last 990 into order and all the time spent doing that is simply wasted It would be much better to be able to pay
44. multiset is empty A Sorting_Machine_Kernel object may be arbitrarily large Like all Resolve C types Sorting_Machine_Kernel comes with operator amp and Clear Note The sample traces for this and the other operation descriptions refer to the type Sorting_Machine_Of_Text which is the result of the following instantiation concrete_instance class Sorting Machine Of Text instantiates Sorting Machine Kernel 1 C lt Text Text Are In Order 1 gt The component 7ext Are In Order I is a concrete instance utility class that implements General_Are_In_Order lt Text gt This means that it exports a Boolean valued function operation Are_In_Order which takes two Text objects as arguments and returns true iff the first and second arguments are in lexicographic order according to ASCII character ordering Text Are In Order 1 also gives a realization supplied mathematical definition for ARE_IN_ORDER which formally describes this ordering For example aardvark and zebra are in order 1 e ARE_IN_ORDER aardvark zebra is true This means the call Text_Are_In_Order_1 Are_In_Order aardvark zebra returns true Similarly ARE IN ORDER zebra zebras is true but not ARE IN ORDER bird ape Note that Text_Are_In_Order_1 ARE_IN_ORDER has the following properties lA multiset is just like a set except that it can have many copies of any value SORTING_MACHINE CLIENT VIEW SORTING_MACHIN
45. object because ordinarily sequential processing of the items proceeds from left to right using the Advance operation see below The Move_To_Finish operation takes you directly to the finish by skipping over all items in s right Sample Traces Statement Object Values LIST 6 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Advance Formal Contract Specification procedure Advance is abstract LRA requires self right empty string ensures self left self right self left fself right and self left self left 1 LA Informal Description A call to the Advance operation has the form sl Advance This operation moves the fence forward toward the right by one position in s but does not otherwise affect the items of s You may make this call only if s right is not empty Sample Traces Statement Object Values LIST CLIENT VIEW LIST 7 Add_Right Formal Contract Specification procedure Add Right consumes Item x is_abstract A ensures self self left lt x gt self right pas Informal Description A call to the Add_Right operation has the form s1 Add Right i This operation adds the item whose value is i just to the right of the fence in s 1 e it adds it at the left end of s right Sample Traces Statement Object Values sl lt 58 12 gt lt 9 90 gt i 13 sl lt 58 12 gt lt 13 9 90 gt i 0 LIST 8 SOF
46. of string s i e Is I Sample Traces Statement Object Values sl lt 12 21 58 gt i 1 Fa EA O sl lt 12 21 58 gt i 3 SEQUENCE 10 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Set Motivation Applicability and Indications for Use A programming type Set is the direct counterpart of a mathematical set which is its mathematical model You can create a Set object whose elements are of some particular type add and remove elements check membership of an element and determine the cardinality size or number of elements the Set contains Related Components e Partial_Map a type that is similar to Set except that it is modeled by a set of ordered pairs that must satisfy the function property i e there must be at most one pair in the set with any given value of the first component of the pair Component Family Members Abstract Components e Set Kernel the programming type of interest with the operations below e Add e Remove e Remove_Any e Is Member e Size Concrete Components e Set Kernel I C This is a checking implementation of Set_Kernel in which the execution time for each of the operations constructor Remove Any and Size is constant while the execution time for each of the operations destructor Add Remove and Is Member is proportional to the size of the set All objects of this type have the interface of Set_Kernel with the concrete template name Set_Kernel_1_C s
47. refer to these objects in examples object Id Name Table 1 C tl t2 object Text namel name2 object Integer idl id2 1 object Boolean b A call to the Add Id Name Pair operation has the form t1 Add Id Name Pair idl namel This operation adds the pair whose value is id name to the set t You may make this call only if t does not contain already a pair whose id component is id and if t does not contain already a pair whose name component is namel Sample Traces Statement Object Values 3 Santa Fe 8 San Francisco idl 2 namel Columbus t1 Add_ Id Name Pair idl namel Santa Fe 3 8 San Francisco 2 Columbus idl namel ID_NAME_TABLE 6 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Remove_Id_Name_Pair Formal Contract Specification procedure Remove Id Name Pair preserves Integer id preserves Text name produces Integer amp id copy produces Texts name copy is abstract requires id name is in self ensures id copy id and name copy name and self self id name 1 Informal Description A call to the Remove Id Name Pair operation has the form t1 Remove Id Name Pair idl namel id2 name2 This operation removes from t the pair whose id component is id and whose name component is namel and returns its value in id2 name2 You may make this call only if there is a pair in tl whose id component is id and
48. starting the loop How does the specification of the operation help you decide the answer to this question In the body of Write_Polynomial is there really a need for if k 1 before the output of the a x term How does the specification of the operation help you decide the answer to this question 34 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Why does the program evaluate the polynomial 1000 times using each method Is each reported execution time given in usec which is supposed to be usec i e microseconds the time for one execution of the evaluation operation or for all 1000 evaluations The times reported include some time for incrementing k and for loop overhead How would you determine whether this error is significant and how would you adjust the times reported if necessary Why does the program output the polynomial before using each evaluation method Rather why does the requirement for the application state that it should do this On how many different polynomials would you test the program before you could state confidently under what conditions Horner s rule is faster than the obvious method of evaluation and by how much Similarly what test runs would enable you to assert confidently whether there is a performance penalty for using the recursive implementation of Horner s rule and if so how much of a penalty 2 3 Anatomy of a Component Family Sequence There is one
49. the string s starts at 0 For example to set the leftmost item of s to 17 you might write assuming s gt 1 s1 0 17 Notice that you can do the above assignment only because the assignment operator is defined for the type Item in this case Integer You may do to s i only what you may do to any other object of type Item The accessor operator like all functions preserves its arguments s and i in the example But it is important to realize that the accessor expression s i does not simply denote the value of the item in position i of string s it acts as the name of an object of type Item which you may consider to lie in that position of the string s This means that not only may you use the expression s i as a value of type Item you may even change the value of the object called s i but remember that this also changes the value of s1 The sample traces help illustrate some important points regarding the convenience and danger of accessor expressions The first and second sample statements how an accessor expression such as sI i acts like an object of type Item whose value may be changed depending on the statement in which the expression occurs The third sample statement shows that s i may appear as an argument in a call where an Item value object or constant is required This call involves other arguments e g 52 but none of the other arguments may be s or may involve an accessor expression for s beca
50. too Some of the required functionality seems so general and valuable that it probably has been written before Hoping to do as little work as possible you imagine you might be able to acquire significant pieces of the program from a repository of common off the shelf or COTS components Volume 2 of Software Component Engineering deals with this situation from the perspective of a client programmer What s different from the scenarios in Volume 1 Now you have at your disposal a significant set of general purpose software components that far surpass in functionality the Resolve C built in types Each component comes with an interface contract specification to describe its behavior and multiple implementations of that behavior with different performance profiles This chapter shows you how to use them 1 1 Resolve C Software Components The Resolve C taxonomy of software components is this e An abstract instance is an interface contract specification a description of behavior in abstract terms that do not reveal the details of how that behavior is achieved e lt A concrete instance is an implementation of an interface contract a description of how to achieve the specified behavior e An abstract template is a parameterized interface contract specification a generator for a group of similar abstract instances e lt A concrete template is a parameterized implementation of an interface contract a generator for a group of si
51. which is the one that would be removed if you called the Remove_Right operation at the point where you are using the accessor operator You may use s current wherever any other object of type Item may appear The accessor operator like all functions preserves its arguments But it is important to realize that the accessor expression s current does not simply denote the value of the current item in s it acts as the name of an object of type Item which you may consider to lie at the left end of the string s right This means that not only may you use the expression s current as a value of type Item you may even change the value of the object called s current but remember that this also changes the value of s1 The sample traces help illustrate some important points regarding the convenience and danger of accessor expressions The first and second sample statements show how an accessor expression such as s current acts like an object of type Item whose value may be changed depending on the statement in which the expression occurs The third sample statement shows that s current may appear as an argument in a call where an tem is required This call involves other arguments e g 52 but none of the other arguments may be s or may involve an accessor expression for s because this would violate the repeated argument rule So while you might be tempted to write something like s1 Add Right sl current this statemen
52. whose name component is namel ID_NAME_TABLE CLIENT VIEW Sample Traces Statement t1 Remove Id Name Pair idl namel tl Remove Id Name Pair 2 Columbus ID_NAME_TABLE 7 Object Values Santa Fe San Francisco Columbus 3 8 2 8 idl namel id2 name2 San Francisco 10047 anything id2 name2 3 Santa Fe 2 Columbus San Francisco San Francisco 3 Santa Fe 2 Columbus 133 doesn t matter id2 name2 id2 3 2 name2 ET id2 name2 Santa Fe Columbus ID_NAME_TABLE 8 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Remove_Any_Pair Formal Contract Specification procedure Remove Any Pair produces Integer amp id produces Text amp name is_abstract V GGE requires self empty set ensures id name is in self and self self id name 1x Informal Description A call to the Remove_Any_Pair operation has the form tl Remove Any Pair idl namel This operation removes some pair from t any pair and returns its value in id namel You may make this call only if is not empty Notice that this operation may remove a different pair from r if called twice in identical situations as illustrated in the sample tracing table ID_NAME_TABLE CLIENT VIEW ID_NAME_TABLE 9 Sample Traces Statement Object Values 3 Santa Fe 8 San Francisco 2 Columbu
53. 00000 000000 000000 000000 000000 AAA F COX HH F e amp O10 H CHAPTER 2 ABSTRACT AND CONCRETE TEMPLATES GENERALIZATION 3 000000 2 000000 1 000000 p 10 000000 154320987654321 000000 execution time 350 usec IE x x Horner s rule iterative p x 14 000000 13 000000 12 000000 11 000000 10 000000 9 000000 000000 000000 000000 000000 000000 000000 000000 1 000000 p 10 000000 154320987654321 000000 execution time 220 usec gt gt gt gt A F O gt x x x xX XX gt O 0 69 1 gt gt gt gt gt gt N RO RR ORR ISO BE Loy der de S NU BOD IO NK A RAR N WGA Oo H 00 A A A F HF E XXX MM KM Xx XM Horner s rule recursive p x 14 000000 13 000000 12 000000 11 000000 10 000000 9 000000 000000 000000 000000 000000 000000 000000 000000 1 000000 p 10 000000 154320987654321 000000 execution time 230 usec gt gt gt gt A O Hr gt IS iO EN 60 N gt gt gt gt YY rY rorRPRHE BE N N 1 N 1 N WB 0101 N 0 AR AR ARR gt N WB oa H 00 A A A A HF Sp XXX XXX Xx ox gt ta aaa Here are a few simple exercises to test your understanding of the code the problem it addresses and this sample test run In the body of Read_Polynomial_And_X is there really a need to clear object a before
54. 1 Figure 1 2 Estimating x How many points are expected to lie within Q The area of Q is 77 4 so 71 4 is the expected fraction of points in the unit square that are also in Q This leads to the conclusion that if you observe that a fraction f of random points lying in the unit square also lie in Q then 4fis a reasonable guess for the value of x This is known as a Monte Carlo estimate because it is a lot like gambling only here you rely on randomness to work for you The user s manual for an application program that uses this method might be Run the program by typing the command Monte_Carlo The program asks for a positive integer which is the number of points to use for a Monte Carlo estimate of x then reports the resulting estimate of 7 and then quits There are many ways to estimate x nearly any of which is a lot more efficient and effective than this one if not as much fun If the end user really just wants you to report an approximate value for zt then there is no reason to prescribe that it should be done this way Nonetheless the Monte Carlo approach is worth knowing for other applications and the need for and use of random numbers are the key features this example is intended to illustrate Estimating 7 is just a particularly simple use of Monte Carlo techniques Faced with designing this program you would no doubt quickly come to wonder whether there is already a way to generate random numbers Certainly someone m
55. 1 2 0 2 1e21 0 2 in binary base 2 often written 101010 The important point is that the same abstract number i e the one we usually call 42 might be represented internally in the computer and displayed externally in many different ways The abstract number is characterized by its mathematical properties for computational purposes we NATURAL 6 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 might choose to think of it in binary as 1 2 0 2 1 23 0 2 1 2 0 2 for communication purposes we might choose to write it in decimal as 42 These examples suggest that the base must be a small integer Actually it can be any value greater than or equal to 2 an efficient implementation of Natural_Kernel might use a number in the thousands or more as its value of its base RADIX For instance here is another way to think of and write the number we call 42 notice the base is greater than 10 2 16 10 16 in hexadecimal base 16 often written 2A 6 The digits of a number viewed in this way always lie between 0 and RADIX 1 inclusive For RADIX gt 10 there are not enough numerals to use for some of the digits so the letters A B etc are customarily introduced to stand for 10 11 etc when writing a number in a base other than decimal Different implementations of Multiply_By_Radix might therefore use different values for RADIX The concrete instances Natural 1 C Natural_1 Natural_Number_1_C a
56. 2 Columbus ID_NAME_TABLE 16 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Size Formal Contract Specification function Integer Size is abstract ensures Size self 1 Informal Description A call to the Size operation has the form of an expression Elsie E Yan This operation returns an Integer value which is the size of the set tZ i e It I Sample Traces Statement Object Values Santa Fe 3 8 San Francisco 2 2 Columbus 68 3 Santa Fe 8 San Francisco 2 Columbus List Motivation Applicability and Indications for Use The programming type List allows you to collect and then process items in sequential order But unlike its close cousins Queue and Stack 1t allows you to add and remove items not just from the ends of a string of items but from anywhere in the middle as well So wherever you might use a Queue or Stack object but want a bit more flexibility in terms of which items you may access then consider a List object On the other hand a List object does not provide as much flexibility as a Sequence object because you cannot directly access an item based on its position in a List object The relative advantage of using a List object is that there is a very efficient implementation of the List kernel operations all can run in constant time which cannot be matched by any implementation of Sequence Related Components e Queue
57. 398 i 1 Bl Divide_By Radix i a nl 4514239 i 8 NATURAL 8 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Discrete_Log Formal Contract Specification function Integer Discrete Log is abstract FEI ensures if self 0 then Discrete Log 0 else RADIX Discrete Log 1 lt self lt RADIX Discrete Log 1 Informal Description A call to the Discrete_Log operation has the form of an expression nl Discrete Log This operation returns an Integer value equal to the discrete logarithm of n in base RADIX What is the discrete logarithm Stated in terms of the radix representation of n see Multiply_By_Radix above another way to explain the call nl Discrete Log is to say that it returns the number of digits needed to write n in base RADIX except that it always returns O not 1 in case n 0 Sample Traces Statement Object Values nl 45142398 i 1 i nl Diserete Log E e nl 45142398 i 8 Eg E ER NATURAL CLIENT VIEW NATURAL 9 Radix Formal Contract Specification function Integer Radix is abstract ensures radix RADIX PAS Informal Description A call to the Radix operation has the form of an expression nl Radix This operation returns an Integer value which is n s RADIX In order for this operation to be useful n s RADIX must have the same value here as it does for the other operations t
58. 5 600 per year Employee field name field value middle mare pe TO CN The mathematical model of this value is a five tuple John Q Doe 123 Easy St 85600 e You might instantiate the concrete_template class Record with three fields of types Text Text and Text calling the resulting concrete instance Full_Name The you might declare RECORD 2 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Full_Name s field names to be first_name middle_name and last_name Then you might instantiate the concrete_template class Record again creating the concrete instance Employee with three fields of types Full_Name Text and Integer and field names name address and salary Schematically you could view the situation like this EXT ces gt SN The mathematical model of this value is a three tuple whose first component is another three tuple John Q Doe 123 Easy St 85600 The first approach gives a flat Record with five fields and no further organization The second approach probably the better one from the standpoint of human understanding gives a more structured Record one of whose fields is itself a Record that is meaningful even outside the context of employee information In fact in practice you probably would need more detailed address information So you d also want to subdivide the address into street address city etc by making a concrete instance Addres
59. 9215 34 QUEUE 8 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Length Formal Contract Specification function Integer Length is_abstract rl ensures Length self 1 Informal Description A call to the Length operation has the form of an expression gl Length This operation returns an Integer value which is the length of the string q1 i e lg1 Sample Traces Statement Object Values ql lt 6 92 13 18 gt i 68 i al tength 0 22 2 gl lt 6 92 13 18 gt i 4 Record Record is a built in type in Resolve C which is included when you bring RESOLVE_Foundation h into the global context The name Record is therefore unusual it is the name of a concrete template even though it does not end in _2 or 1a or the like Motivation Applicability and Indications for Use The programming type Record allows you to set up and access the individual objects in a small fixed size no larger than ten collection of objects of various and arbitrary types You should consider Record whenever you want to treat such a collection of diverse objects as a single object for some purposes and as individual constituent sub objects for other purposes The way you achieve the former behavior is straightforward since this is what an object ordinarily is The way you achieve the latter behavior at the same time is to give symbolic names called field names to the sub object
60. COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Reads from stdin a non negative integer which is the degree of the polynomial to be evaluated i e n followed by the n 1 real valued coefficients in the order a0 through an followed by the real valued point LL at which the polynomial is to be evaluated i e X Each number is expected to be on its own line of input The program then prints out the polynomial followed by the evaluation of the polynomial at the point x and the execution time for the obvious method and for Horner s El rule both iterative and recursive and then quits PA NASA Se SSeS e a ee eee ae kf A e a ee eee ae een ee iif Global Context 727 2227 a a DE a EZ include RESOLVE Foundation h include CI Timer 1 h CHAPTER 2 ABSTRACT AND CONCRETE TEMPLATES GENERALIZATION global procedure Read Polynomial And X alters Character IStream amp input produces Polynomial Coefficients amp a produces Real amp x requires input is open TRUE and there exists s string of real z real TO TEXT s in INPUT ENCODING s TO TEXT z In is prefix of input content ensures input is open TRUE and input ext name finput ext name and input content TO TEXT la in INPUT_ENCODING a TO TEXT x In input content LE global_pro
61. E 5 e Any string of characters is in order with itself e In ASCII all the upper case characters come before any of the lower case characters This means for example that ARE IN ORDER ZZZ an The description of Remove_First explains how the second template parameter of Sorting_Machine_Kernel_1_C is used Sample Traces Statement Object Values SORTING_MACHINE 6 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Insert Formal Contract Specification procedure Insert consumes Item amp x is abstract ae requires self inserting true ensures self true self contents union x LAJ Informal Description Note This and the other operation descriptions refer to these objects in examples object Sorting_Machine_Of_Text s1 object Text t object Integer i object Boolean b A call to the Insert operation has the form sl Insert t This operation adds the item whose value is to the contents of s You may make this call only if s is in insertion phase Sample Traces Statement Object Values po er a ET TE 5 i a i l t mm SORTING_MACHINE CLIENT VIEW SORTING_MACHINE 7 Remove_First Formal Contract Specification P N math operation IS FIRST s multiset of Item x Item boolean is x is ins and for all y Item where y is in s ARE_IN ORDER x y 1 procedure Remove First produces Item x is abstract xl requires self in
62. Ex f Informal Description A call to the d_Is_In_Table operation has the form of an expression t1 Id Is In Table idl This operation returns true if there is a pair in with an id component of id and returns false otherwise Sample Traces Statement Object Values tl 3 Santa Fe 8 San Francisco 2 Columbus true b tl Id_Is In Table idl 3 Santa Fe 8 San Francisco 2 Columbus b false idl 99 Santa Fe 37 8 San Francisco 2 Columbus false b 01 Td Ts In Table 2 3 3 Santa Fe 8 San Francisco 2 Columbus ID_NAME_TABLE CLIENT VIEW ID_NAME_TABLE 15 Name Is In Table Formal Contract Specification function Boolean Name Is In Table preserves Text name is abstract ensures Name Is In Table NAME IS DEFINED IN self name fey Informal Description A call to the Name Is In Table operation has the form of an expression tl Name Is In Table namel This operation returns true if there is a pair in with a name component of namel and returns false otherwise Sample Traces Statement Object Values tl 3 Santa Fe 8 San Francisco 2 Columbus b true namel Cincinnati b tl Name Is In Table namel 3 Santa Fe 8 San Francisco 2 Columbus b false namel Cincinnati Santa Fe 37 8 San Francisco 27 Columbus 8 San Francisco
63. FTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Concrete Components e Text This is the standard implementation of the abstract instance Text_Kernel that comes built in to Resolve C It is a concrete instance i e you may declare objects of type Text Text is a checking component which means that it checks the preconditions of its operations So if you call any of the Text operations with a violated precondition then your program will immediately stop and report the violation To bring this component into the context you write include RESOLVE Foundation h Component Coupling Diagram Text_ Kernel implements TEXT CLIENT VIEW TEXT 3 Descriptions Text_Kernel Type and Standard Operations Formal Contract Specification standard abstract operations Text Kernel xl Text Kernel is modeled by string of character initialization ensures self empty string TEL Informal Description The model for a Text_Kernel object is a string of characters which is initially empty A Text_Kernel object may be an arbitrarily long string Like all Resolve C types Text_Kernel comes with operator amp and Clear Sample Traces Statement Object Values pe O TEXT 4 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Add Formal Contract Specification procedure Add preserves Integer pos preserves Character c is abstract rl requires 0 lt pos lt self ensures there e
64. G 3 1 The Problem of Component Dependence 3 1 1 Avoidable Dependence Is Bad 3 1 2 Avoidable Concrete to Concrete Dependence Is Worse 3 2 Decoupling the Checks Relation 3 2 1 The Defensiveness Dilemma 3 2 2 Example The Natural Family 3 2 3 Checking Components and the Checks Relation 3 2 4 Implementing a Checking Component UNO 0H ROW UW OD em poa GN N a Yu NNN Fe NN FR VO wm O Ww 31 31 34 34 36 38 38 41 41 41 42 44 47 51 53 55 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 3 2 5 Instantiating a Checking Component 57 3 2 6 Combining Generalization and Decoupling The Specializes Relation 58 3 3 Decoupling the Extends Relation Concrete to Concrete 62 3 3 1 The Extends Relation Concrete to Concrete The Layering Approach 63 3 3 2 Instantiating a Concrete Extension 66 3 4 Summary 68 CLIENT VIEW APPENDICES Array Binary_Tree Id Name Table List Natural Partial Map Queue Record Sequence Set Sorting Machine Stack Static Array Text Tree 1 Abstract and Concrete Instances Suppose your job is to write a Resolve C application program At first blush it seems no more complex than the examples in Volume 1 Yet after thinking about it you conclude that the program calls for functionality beyond what is provided directly by the built in Resolve C types not just narrow application specific capabilities but ones that would be useful in many other situations
65. I NATURAL KERNEL define AI NATURAL KERNEL 1 abstract_instance class Natural Kernel public math subtype NATURAL MODEL is integer exemplar n constraint n gt 0 52 SOFTWARE COMPONENT ENGINEERING VOLUME 2 math definition RADIX integer satisfies restriction RADIX gt 2 LE standard abstract operations Natural Kernel pen Natural Kernel is modeled by NATURAL MODEL initialization ensures self 0 PERF procedure Multiply By Radix preserves Integer k is abstract Frl requires 0 lt k lt RADIX ensures self self RADIX k CA procedure Divide_By Radix produces Integer amp k is_abstract Frl ensures self self RADIX k and 0 lt k lt RADIX 1 function Integer Discrete_Log is_abstract V SKE ensures if self 0 then Discrete Log 0 else RADIX Discrete Log 1 lt self lt RADIX Discrete Log 1 function Integer Radix is_abstract ensures Radix RADIX 1 ke endif AI NATURAL KERNEL Figure 3 5 AI Natural Kernel h Note that Multiply_By_Radix has a non trivial precondition Intuitively the following call n Multiply By Radix k alters n by tacking the digit k onto the right end of the digits of the old n The precondition is that k must actually be a digit in the radix used for n i e it must be between 0 and RADIX 1 CHAPTER 3 ABSTRACT AND CONCRETE TEMPLATES DECOUPLING 53 inclus
66. Kernel object may be arbitrarily large Like all Resolve C types Stack_Kernel comes with operator amp and Clear Note The sample traces for this and the other operation descriptions refer to the type Stack_Of_Integer which is the result of the following instantiation concrete instance class Stack Of Integer instantiates Stack Kernel la C lt Integer gt O Sample Traces Statement Object Values AENA TC STACK 4 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Push Formal Contract Specification procedure Push consumes Item amp x is_abstract Ze ensures self lt x gt self BAR Informal Description Note This and the other operation descriptions refer to these objects in examples object Stack Of Integer sl s2 object Integer i A call to the Push operation has the form sl Push i This operation adds the item whose value is i to the top left end of sl Sample Traces Statement Object Values sl lt 58 12 21 gt i 13 sl lt 13 58 12 21 gt i 0 STACK CLIENT VIEW STACK 5 Pop Formal Contract Specification procedure Pop produces Item amp x is_abstract ZRH requires self empty_string ensures self lt x gt self ER Informal Description A call to the Pop operation has the form sl Pop i This operation removes the item from the top left end of s and returns its value ini You may make this cal
67. List_ Kernel_1a_C LIST CLIENT VIEW LIsT 3 Descriptions List_Kernel Type and Standard Operations Formal Contract Specification fmt math subtype LIST MODEL is left string of Item right string of Item TEJ standard abstract operations List Kernel EAI List Kernel is modeled by LIST MODEL initialization ensures self empty string empty string If Informal Description The model for List_Kernel is a pair of strings of items each of which is initially empty The concatenation of the two strings contains all the items in a List_Kernel object These strings are called left and right to suggest that you should imagine a separator called the fence to lie between the two strings the first string is to the left of the fence and the other string is to the right of the fence A List_Kernel object may be arbitrarily large 1 e both strings may be arbitrarily long Like all Resolve C types List_Kernel comes with operator amp and Clear Note The sample traces for this and the other operation descriptions refer to the type List_Of_Integer which is the result of the following instantiation concrete instance class List Of Integer instantiates List Kernel la C lt Integer gt Prototyopical objects of this type in the examples that follow have names beginning with s not T because it is difficult to visually distinguish the letter 1 from the numeral 1 Sample Trace
68. OLVE C VOLUME 2 Right_Length Formal Contract Specification function Integer Right Length is abstract Jl ensures Right Length self right 1 Informal Description A call to the Right_Length operation has the form of an expression s1 Right_Length This operation returns an Integer value which is the length of the string s right i e Isl rightl Sample Traces Statement Object Values lt 58 gt 13 9 90 gt 37 sl lt 58 12 gt lt 13 9 90 gt i 3 Natural Motivation Applicability and Indications for Use RESOLVE C includes the built in programming type Integer whose mathematical model is a mathematical integer lying between two bounds On most modern computer systems these are 23 and 23 1 2 147 483 648 and 2 147 483 647 These bounds make the potential nteger values big enough for most routine purposes However there are many situations where non negative integer valued objects are appropriate but where two billion or so is not the largest value ever encountered For example the amount of a bank transaction in U S currency might be recorded in an Integer object the number of cents being transferred But then a figure like the U S national debt or even a plausible inter bank electronic fund transfer is too large to handle If you need to accommodate a larger arbitrarily large non negative number then you should use a Natural object whose mathematic
69. Real 0 0 To Real k 1 j endif CT RANDOM UNIFORM 1 Figure 3 15 CT Random Uniform_1 h In the code in Figure 3 15 the concrete template depicted as the outer shell or layer in Figure 3 14 is called Random Uniform 1 because it is an implementation of the abstract instance Random_Uniform There are a couple new features in this code First Random Uniform I takes part in two specific dependence relations with other components it implements Random_Uniform and it extends Random_Base a restricted formal template parameter that must implement Random_Kernel Notice that Random_Uniform extends Random_Kernel so any implementation of Random_Uniform must implement Random_Kernel as well as the two new operations whose interface contracts are specified in Random_Uniform The concrete to concrete extends relation makes this happen automatically the kernel operations come from Random_Base the component being extended and the code for the two additional operations Uniform_Real and Uniform_Integer is provided here in Random_Uniform_1 The second new feature is in the code for the new operations Just as a checking component calls operations from the component it checks a layered extension calls the operations from the component it extends It does this by using self as the name of the receiver object exactly as with a checking component Notice that the body of an operation in an extension may call not only the operations from the c
70. Software Component Engineering With Resolve C Volume 2 The Client s View Draft of June 5 2007 Bruce W Weide Department of Computer Science and Engineering The Ohio State University Columbus Copyright O 2007 by the author All rights reserved Contents 1 ABSTRACT AND CONCRETE INSTANCES 1 1 Resolve C Software Components 1 1 1 Subroutine Libraries 1 1 2 User Defined Types 1 1 3 Classes 1 1 4 Components and Catalogs 1 1 5 Component File Naming Conventions 1 2 Example Monte Carlo Estimation of rn 1 2 1 Bringing a Concrete Instance Into Scope 1 2 2 Using the Concrete Instance 1 3 Anatomy of a Component Family Random 1 3 1 The Kernel Type Standard Operations and Kernel Operations 1 3 2 The Extends Relation Abstract to Abstract 1 3 3 Using a Concrete Component 1 4 Summary ABSTRACT AND CONCRETE TEMPLATES GENERALIZATION 2 1 Parameterized Software Components 2 1 1 Resolve C Language Support for Templates 2 1 2 Collection Components 2 1 3 Template Instantiation 2 2 Example Polynomial Evaluation 2 2 1 Bringing a Concrete Template Into Scope 2 252 Instantiating the Concrete Template to Create a Concrete Instance 2 2 3 Using the Resulting Concrete Instance 23 Anatomy of aComponent Family Sequence 2 3 1 The Kernel Type Standard Operations and Kernel Operations 2 3 2 The Extends Relation Abstract to Abstract 2 3 3 Using a Concrete Component 2 4 Summary ABSTRACT AND CONCRETE TEMPLATES DECOUPLIN
71. Something like Figure 3 2 appears as a single highlighted dependence chain in Figure 3 3 but as you can see it s only the tip of the iceberg CHAPTER 3 ABSTRACT AND CONCRETE TEMPLATES DECOUPLING 43 Figure 3 3 Dependence chains are part of dependence graphs How can you avoid this kind of situation A design by contract discipline such as Resolve C makes it possible for a component designer to have each concrete component depend only on the interface contracts needed to build it and not on particular concrete components that implement those contracts Where there is a dependence on an abstract component in general this dependence is to a kernel abstract component or to an extension of it This dependence chain from the concrete component can therefore go through perhaps two other components there it usually stops This means you can think of a dependence on an abstract component as killing a dependence chain or at least as declaring it terminally ill This observation leads to another specific consequence of the limited dependence rule Concrete Component Dependence Rule Avoid introducing a dependence on a concrete component If the dependence of a concrete component on another component is required create that dependence to an abstract component It is easy to avoid dependencies from abstract components to concrete components because it is never necessary to make what something does depend on how something els
72. Specification function Items operator preserves Accessor Position amp current is abstract requires self empty string ensures there exists a string of Item self lt self current gt a 1x Informal Description A call to the accessor operator has the form of an expression ql current This expression acts as the name of an object of type tem whose value is the item at the front of ql You may make this call only if g is not empty The special word current is the only thing that can appear between in the accessor for type Queue It always refers to the single item that you can access directly without dequeuing any others the front leftmost item which is the one that would be removed if you called the Dequeue operation at the point where you are using the accessor operator You may use ql current wherever any other object of type Item may appear The accessor operator like all functions preserves its arguments But it is important to realize that the accessor expression g current does not simply denote the value of the front item in q1 it acts as the name of an object of type Item which you may consider to lie at the left end of the string g This means that not only may you use the expression q current as a value of type Item you may even change the value of the object called g current but remember that this also changes the value of q The sample traces help illust
73. TWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Remove_Right Formal Contract Specification procedure Remove Right produces Item amp x is_abstract Jl requires self right empty string ensures self self left lt x gt self right LAZ Informal Description A call to the Remove_Right operation has the form sl Remove_Right i This operation removes and returns in i the item just to the right of the fence in s i e the item at the left end of s right You may make this call only if s right is not empty Sample Traces Statement Object Values lt 58 gt 13 9 90 gt 67 sl lt 58 12 gt lt 9 90 gt i 13 LIST CLIENT VIEW LIST 9 Accessor Formal Contract Specification function Items operator preserves Accessor Position amp current is abstract PAGE requires self right empty string ensures there exists a string of Item self right lt self current gt a 1 Informal Description A call to the accessor operator has the form of an expression sl currentl 1 This expression acts as the name of an object of type tem whose value is the item at the left end of s right You may make this call only if s right is not empty The special word current is the only thing that can appear between in the accessor for type List It always refers to the single item that you can access directly the one just to the right of the fence
74. Templates which are effectively generators for entire families of instances are explained in Chapters 2 and 3 A kernel abstract instance acts as a centerpiece for a family of related components It defines the mathematical model of a new user defined kernel type which automatically has the standard operations constructor destructor swap operator amp and Clear along with the interface contracts of its kernel operations or methods The latter are operations that together are deemed by the designer to be both necessary and sufficient to perform all useful manipulations of objects of the new type Other abstract instances can then be added incrementally to specify interface contracts for more operations methods These abstract instances are said to extend the kernel abstract instance Generally a kernel abstract instance is self sufficient in the sense that it has no dependencies on other components An abstract instance that specifies an extension of course depends at least on the abstract instance it extends This dependency is recorded in the code in two places in a include statement that brings the other component into scope so it is visible to the compiler and in an abstract_instance class declaration using the keyword extends to indicate the explicit dependence relation between the new component and the kernel abstract instance A component coupling diagram CCD depicts this relationship schematically to ease human underst
75. a new type it might be called Complex in the scenario above is called a user defined type to contrast it with a built in type A client programmer developing a new application might not need to create any new types Often he or she can just retrieve types that are generally useful from a catalog of off the shelf software components developed by others Recall from Volume 1 that the type of an object determines both the mathematical model of the object s value state and the operations that a client programmer may call in order to observe CHAPTER 1 ABSTRACT AND CONCRETE INSTANCES and to control the value of that object Given the central role of types then it seems natural to consider a type s mathematical model and its associated operations to be the basis for a software component This is the view taken in object oriented programming in general and in the Resolve C discipline in particular 1 1 3 Classes C offers a program unit called a class in which you can describe either a type s mathematical model and its associated operations via an interface contract specification or a method of achieving that behavior via implementation code This unit is introduced with the keyword class prefixed in the Resolve C discipline by a qualifying keyword to indicate which category it belongs to in the Resolve C taxonomy of components abstract_instance concrete_instance abstract_template or concrete_template The chapter dis
76. a non trivial precondition the checking component need do nothing special to protect against violations of their requires clauses because there can t be any such violations every call to one of these operations is a good call that goes through the protective wall without difficulty D client call to operation lt 4 with trivial precondition Natural_ Kernel_1 client call to good call to Multiply_By_Radix Multiply_By_Radix rejected call to violated precondition Figure 3 6 Intuitive operation of a checking component A checking component is a concrete component it contains code that is executed not an interface contract Specifically the code for Multiply_By_Radix in the checking component depicted above might look like this 4 You will not go wrong by assuming RADIX 10 in which case you re dealing with numbers as represented using the normal decimal digits With this assumption if n 123 and k 4 at the time of the call then n 1234 and k 4 after the call 54 SOFTWARE COMPONENT ENGINEERING VOLUME 2 procedure body Multiply By Radix preserves Integer k assert 0 lt k Q lt k assert k lt self Radix k lt RADIX self Natural Kernel 1 Multiply By Radix k A new Resolve C keyword in this code is assert gt which you can think of as the name of a built in global procedure with two arguments The first argument is a condition that you expect to be true If the first argumen
77. ace contract specification For this the implicit name of the formal parameter to which the receiver object is bound we use self What is the mode of self By default for any procedure operation self is an alters mode parameter for any function operation self is a preserves mode parameter LIMIT is the number of different values that an object of type of Random_Kernel might have see the math subtype RANDOM_MODEL Suppose LIMIT 19 which is a horribly small value for a useful random number generator but it is technically possible to have a concrete component that implements Random_Kernel and stipulates that LIMIT 19 Then a tracing table for the statement above might look like this Statement Object Values rand 13 k 27 rand Set_Value k EEE AM rand 8 k 27 The interface contract specification says that upon return from Set Value we know that self n mod LIMIT It also says that n is preserved The parameter binding for this call matches rand with self and k with n Therefore we must see the result shown above rand 27 mod 19 8 So suppose you use a concrete component that provides a type whose behavior can be explained using the abstract instance Random_Kernel Then any object of that type is considered a unit whose state space is modeled as a RANDOM_MODEL and whose associated operations include the standard operations as well as the kernel operations specified in Random_Kernel 1 3 2 The Extends Relation
78. agram Natural_ Kernel Natural_ Arithmetic Natural_ extends Number extends implements implements implements implements Natural_1 _C Natural_1 Natural_ Natural_ Number 1 C Number 1 2 This CCD is not the actual CCD for the Natural family which includes a number of templates for technical reasons But it is equivalent to the true CCD from the standpoint of a client using any of the concrete components NATURAL 4 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Descriptions Natural_Kernel Type and Standard Operations Formal Contract Specification math subtype NATURAL MODEL is integer exemplar n constraint n gt 0 math definition RADIX integer satisfies restriction RADIX gt 2 LA standard abstract operations Natural Kernel LE Natural Kernel is modeled by NATURAL MODEL initialization ensures self 0 NR Informal Description The model for Natural_Kernel is a mathematical integer which is initially zero A Natural_Kernel object may have an arbitrarily large but always non negative value Like all Resolve C types Natural_Kernel comes with operator amp and Clear Sample Traces Statement Object Values ee E NATURAL CLIENT VIEW NATURAL 5 Multiply_By_Radix Formal Contract Specification procedure Multiply By Radix preserves Integer k is abstract requires 0 lt k lt RADIX ensures self self RADIX k LAY
79. al model is an integer which is bounded below by zero but which is for practical purposes not bounded above Related Components e Integer the type to use if the numbers in your calculations are always small Component Family Members Abstract Components Natural Kernel the programming type of interest with the operations below e Multiply_By_Radix e Divide By Radix e Discrete_Log Radix Natural Arithmetic a bundle combining Natural Kernel and the operations below Convert From Integer Increment e Decrement e Compare e Add Subtract This list of abstract components is not entirely accurate for the Natural family which includes a number of templates for technical reasons But it is equivalent from the standpoint of a client using any of the concrete components listed next NATURAL 2 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Multiply Divide Natural_Number a bundle combining Natural_Arithmetic and the operations below e Copy To e Get_From gt gt e Put_To lt lt Concrete Components Natural_1_C This is a checking implementation of the abstract instance Natural_Kernel so it is not very powerful you probably want Natural_Number_1_C instead It is a concrete instance 1 e you may declare objects of type Natural_1_C Natural_1_C is a checking component which means that it checks the preconditions of its operations So if you call any of the Natural_1_C operati
80. al_Map_Kernel the programming type of interest with the operations below Define Undefine Undefine_Any e Accessor e Is_Defined e Size Concrete Components e Partial Map Kernel I C This is a checking implementation of Partial_Map_Kernel in which the execution time for each of the operations constructor Define Undefine Any and Size is constant while the execution time for each of the operations destructor Undefine the accessor and Is Defined is proportional to the size of the set All objects of this type have the interface of Partial Map Kernel with the concrete template name Partial Map Kernel I C substituted for the abstract template name Partial Map Kernel To bring this component into the context you write include CT Partial Map Kernel 1 C h PARTIAL_MAP 2 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Component Coupling Diagram Partial_Map_ Kernel implements Partial_Map_ Kernel_1_C PARTIAL_MAP CLIENT VIEW PARTIAL_MAP 3 Descriptions Partial_Map_Kernel Type and Standard Operations Formal Contract Specification math subtype PARTIAL FUNCTION is finite set of d D Item r R_Item exemplar m constraint for all dl d2 D Item rl r2 R Item where d1 r1 is in m and d2 r2 is in m if dl d2 then rl r2 math operation IS DEFINED IN m PARTIAL FUNCTION d D Item boolean is there exists r R_Item d r is in m Lay standard abstract o
81. ameter Therefore it is appropriate to bind the formal parameter tem of Sequence_Kernel_la_C to the type Real The resulting concrete instance is named something that suggests its intended use in this application program Polynomial_Coefficients You don t have to name an instance of Sequence_Kernel_la_C something general like Sequence_Of_Real 2 2 3 Using the Resulting Concrete Instance Once an application program instantiates the concrete templates it needs it uses the resulting concrete instances just as though they were concrete instances from a component catalog i e just as though they were built in types Poly_Eval cpp involves no other new features of Resolve C Nonetheless it is worth studying to see how it uses previously discussed features 2 In C C programs you would use the keywords class and virtual public in place of the Resolve C keywords concrete_instance class and instantiates respectively 32 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 For example the interface section begins with a mathematical definition that is used in the specification of Read_Polynomial_And_X to describe precisely the input format for the program The other mathematical definition is used in the specifications of the three polynomial evaluation operations to describe precisely what polynomial evaluation means Both these definitions are inductive In contrast to the formal specifications for the input and computat
82. anding A client program that needs to use some implementation of an abstract instance must bring into scope the particular concrete instance it wishes to use not just the abstract instance that explains 1ts behavior for humans This allows the compiler to generate executable code for the client program However all the client programmer needs to know in order to do this is the location in the file system of the appropriate concrete instance there is no reason to look at the Resolve C code of that instance The component s location is determined by a set of Resolve C conventions it is in a component catalog directory then down in a component kind directory in this case CI since the component is a concrete instance then down in a component family directory determined by the kernel abstract instance that the concrete instance implements and finally in the file in that directory that contains the concrete instance code itself General purpose Resolve C components are located in the Resolve C Catalog a default starting point as the compiler searches for components so include statements in application programs CHAPTER 1 ABSTRACT AND CONCRETE INSTANCES 17 do not include long absolute paths but rather relative paths from this fixed location Again a CCD concisely depicts the fact that a concrete instance implements a particular abstract instance and if that abstract instance specifies an extension the kernel abstract i
83. ant to make template instantiation easier for a client programmer 3 3 Decoupling the Extends Relation Concrete to Concrete Now let s return to Monte Carlo It uses concrete instance Random Uniform Generator I which implements abstract instance Random_Uniform Recall that Monte_Carlo uses the operation Uniform_Real from Random_Uniform_Generator_1 This function takes two Real numbers a and b and returns a random Real value drawn from a uniform probability distribution over the interval a b 8 In C C programs you would use the keywords virtual public in place of the Resolve C keyword specializes CHAPTER 3 ABSTRACT AND CONCRETE TEMPLATES DECOUPLING 63 Random_ Uniform Random_ Kernel extends implements Random_ Uniform_ Generator_1 Figure 3 13 The CCD for an extension implementation Figure 3 13 shows the CCD for Random Uniform Generator 1 used in Chapter 1 The technique discussed here is how as the client programmer of Monte_Carlo needing the functionality of Random Uniform you could have created Random Uniform Generator I yourself given only an implementation of Random_Kernel from the Resolve C Catalog 3 3 1 The Extends Relation Concrete to Concrete The Layering Approach The computation you need to perform is rather simple To get a random real number from a uniform distribution over 0 0 1 0 you can scale the value of a random integer between 0 and LIMIT 1 inclusive i e
84. ass Natural Kernel 1 you may leave whitespace around or omit it You must use the qualified name here because the C compiler would interpret a call to an unqualified Multiply_By_Radix as a recursive call to the checking component s code Finally notice that the receiver object in this call is self As you know C uses traditional object oriented programming syntax in method calls not global operation calls Specifically you put the name of the receiver object or distinguished argument before a and the name of the method after it Recall from Chapter 1 that this syntax causes a problem when writing specifications there is no formal parameter associated with the receiver object hence no 5 C compilers support a version of assert with slightly different syntax with the exact format of the arguments and the effect when the condition evaluates to false also being somewhat different 6 In C C programs you might use this in place of the Resolve C key word self Alternatively in C C you would be allowed to write this gt in place of self or simply leave out the receiver object altogether In Resolve C the convention is never to call a method without an explicit receiver object CHAPTER 3 ABSTRACT AND CONCRETE TEMPLATES DECOUPLING 55 programmer declared name you can use to refer to it in the operation s specification For specifications we therefore reserve the special name sel
85. atalog components In order to avoid the hassle of having to learn and write a complete file name which might involve a long path the details of which might vary from system to system in Resolve C you give the name of a component file relative to the directory where Resolve C Catalog components reside For special 1 In C C programs you would use just the keyword class whether the component being defined is an interface contract specification or an implementation an instance or a template 4 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 catalogs you might have to provide the catalog s directory name too or follow other catalog specific instructions for how to include its components On the other hand as you develop new components that are not yet ready to be placed in a catalog and to be used by other people in their programs you should include them by a path to one of your own private directories 1 1 5 Component File Naming Conventions As a client programmer using a catalog of off the shelf components then you need to know the names of the files in which the required components are described The file names within a catalog directory arise from the following Resolve C conventions which are based on the taxonomy of component varieties and on the class names used for particular components e Within a catalog directory a component file resides in one of four subdirectories based on whether it is an abst
86. atical model is a string of characters RESOLVE C has literals constants of the built in types Boolean Character Integer and Real e g true a 13 and 3 14159 respectively There also are literals of type Text e g hello there A Text literal comprises zero or more Character literals enclosed in double quotes without single quotes around the individual Character literals that make it up You may use a Text literal any place a Text object is required as an argument to an operation if the associated formal parameter has preserves mode This makes Text a very useful type when you need to prompt a user for input label an output construct a menu of choices etc Such prompts and labels may be Text literals in your source code Related Components e Character the type of each of the individual items in a Text object e Sequence a generalization of Text in which the individual items may be of any type Component Family Members Abstract Components e Text Kernel the programming type of interest with the operations below Add e Remove e Accessor Length For flexibility you might store such Text literals in resource files This allows a knowledgeable user to customize certain aspects of an application program e g to adapt it to a foreign language without having access to the source code Resource files are not further discussed here but they are conventional features of many programs TEXT 2 SO
87. ations for code that can be executed Parameterized concrete components concrete templates are entirely parallel to abstract templates in structure and purpose The difference is that they are concrete i e they consist of code that describes not what behavior is available but how that behavior is achieved Once instantiated this code can be compiled and executed As with concrete instances for kernel components a client programmer need not see any of the code in the concrete templates for kernel components being used but rather only the abstract templates that specify their interface contracts The next section illustrates how to develop an application program that uses a concrete template 2 2 Example Polynomial Evaluation A problem that arises in numerical software is evaluation of a polynomial For instance suppose you have a polynomial 1 P X a x 4 jX a7Xx ag that you need to evaluate at a point x How can you do this The obvious method is to repeatedly multiply x by itself to compute x and multiply that by a to give the first term then to compute x and multiply it by a _ to give the second term and add it to the first term and so on Horner s rule is a more efficient way to compute the same thing If you rewrite the polynomial as follows this alternative computation almost pops out at you P X a x Ay_p X 4 2 X 47 X AQ That is start with a multiply it by x and add a
88. ause they have something in common with each other and the various f s allow you distinguish among the objects in that Record RECORD 8 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Sample Traces Statement Object Values nl John NOs Doe t Adams nl last_ name amp t John O Adams t Doe John woran Adams nl first_name Remove 2 On Adams Jon NO Adams Gt WE Kennedy Jon Eo Adams I WO Kennedy ME Jon Adams I OIL Kennedy Sequence Motivation Applicability and Indications for Use Occasionally you need something like Text but with the individual items in the string as something other than Characters The interesting functionality of Text is that you can create and manipulate arbitrarily long strings by adding and or removing items and that you can directly index into a string by position If you need the generalized template version of Text in which you as a client programmer can decide what type the items of the string can be then you should use Sequence Related Components Text the built in RESOLVE C type whose generalization is Sequence e Array a type that is similar to Sequence in that you can directly index into an Array object by position but different in that an Array object always has the same number of items in it and this number cannot be changed dynamically Component Family Members Abst
89. ble I C This is a checking implementation of the abstract instance Id Name Table Kernel It is a concrete instance i e you may declare objects of type Id Name Table I C Id Name Table I Cis a checking component which means that it checks the preconditions of its operations So if you call any of the Id Name Table I C operations with a violated precondition then your program will immediately stop and report the violation To bring this component into the context you write ID_NAME_TABLE 2 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 include CI Id Name Table 1 C h e Id Name Table 1 This is a non checking implementation of the abstract instance Id Name Table Kernel It is a concrete instance i e you may declare objects of type Id_Name_Table_1 To bring this component into the context you write include CI Id Name Table 1 h Component Coupling Diagram Id_Name_ Table_ Kernel implements implements Id Name Id Name Table 1 C Table 1 ID_NAME_TABLE CLIENT VIEW ID_NAME_TABLE 3 Descriptions Id_Name_Table_Kernel Type and Standard Operations Formal Contract Specification xl math subtype ID NAME TABLE MODEL is finite set of id integer name string of character exemplar m constraint for all idl id2 integer namel name2 string of character where idl namel is in m and id2 name2 is in m idl id2 iff namel name math definition
90. cedure Write Polynomial alters Character OStream output preserves Polynomial Coefficients amp a Var requires output is open TRUE ensures 1 global function Real Original Evaluation preserves Polynomial Coefficients amp a preserves Real x PEN ensures Original Evaluation EVAL a x TEL laa gt global function Real Horner Iterative Evaluation preserves Polynomial Coefficients amp a preserves Real x 25 26 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 PEN ensures Horner Iterative Evaluation EVAL a x 1x wan 22 o global function Real Horner Recursive Evaluation preserves Polynomial Coefficients amp a preserves Real x ensures Horner Recursive Evaluation EVAL a x 1x Ra Fe Ra re global procedure body Read Polynomial And X alters Character IStream s input produces Polynomial Coefficients amp a produces Real amp x object Integer n k input gt gt n a Clear object Real coeff input gt gt coeff a Add k coeff k input gt gt x global procedure body Write Polynomial alters Character OStream output preserves Polynomial Coefficients amp a object Integer k output lt lt p x n k a Length 1 output lt lt lt lt a k lt lt x lt lt k lt lt
91. condition violations where they would not have been checked if their type had been Natural_Kernel_1 Moreover you can easily make Natural_Kernel_1_C a reusable component and put it into a shared component catalog where you and others can use it in a variety of application programs simply by bringing it into scope using include This code is illustrated in Figure 3 9 it contains no new features bie SS A e ES KN Ay Concrete Instance Natural Kernel 1 C BE NSS HE EI TI FT BERGE 3y ifndef CI NATURAL KERNEL 1 C define CI NATURAL KERNEL 1 C 1 A AE O AR A OR O eee eo KL Global Context in 7 HH EHE MAA SAR PAS AS SS EEE ET RSS Regener include CI Natural Kernel 1 h include CT Natural Kernel C h concrete instance class Natural Kernel 1 C instantiates Natural Kernel C lt Natural Kernel 1 gt O endif CI NATURAL KERNEL 1 C Figure 3 9 CI Natural Kernel_1_C h 3 2 6 Combining Generalization and Decoupling The Specializes Relation Usually the kernel component being checked is not a concrete instance but rather a concrete template Consider a checking component Sequence_Kernel_C for implementations of CHAPTER 3 ABSTRACT AND CONCRETE TEMPLATES DECOUPLING 59 Sequence_Kernel The difference from Natural_Kernel is that Sequence_Kernel already has a template parameter for generalization Fortunately it is easy to combine the uses of templates for generalization
92. ction is important because LIMIT is a mathematical integer not a programming Integer and hence could otherwise be arbitrarily large because mathematical integers know no bounds e Math subtype RANDOM MODEL is a mathematical integer between 0 and LIMIT e Math definition NEXT is a mathematical function from the domain RANDOM MODEL to the range RANDOM_MODEL that captures how a particular implementation of Random_Kernel generates pseudo random numbers Pseudo random numbers are series of numbers that seem to be random in the sense that they pass certain statistical tests of randomness even though they are generated by a deterministic and hence reproduceable algorithmic process It is beyond the scope of this book to describe in a formal way an interface contract for this component The key point is that a client of Random_Kernel needs to know only that NEXT describes this process and the properties those numbers will have not the details of exactly what the series of numbers will be Next is a declaration that the new kernel type like all Resolve C types has the standard operations 3 In C C programs you would use no keyword at all in place of the Resolve C keyword abstract_instance 12 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 e lt A constructor which is an operation that is called automatically for each object of this type without the client having to write an explicit call when execution reaches the poi
93. cusses only instances templates are introduced in Chapter 2 1 1 4 Components and Catalogs We can now say what a software component actually is A Resolve C software component is a C class of any of the four kinds listed above A component catalog is a collection of abstract and concrete instances and templates In practice each component is stored in a file and the files defining the components in a catalog are organized within a directory for that catalog The Resolve C Catalog is the primary collection of general purpose Resolve C components These are not quite as widely useful as the built in types and operations but they are still valuable in a variety of client programs There can be other catalogs of special purpose components In fact you also may set up your own catalogs but this is not discussed here main program file off the shelf software components makes visible Global Context section makes visible Interface section Figure 1 1 A main program file that brings into scope two components In order to use an off the shelf component from one of these catalogs you first need to bring the component into scope or make it visible in your program so the C compiler knows about the component To do this you simply write a include statement by convention in the section of your program labelled Global Context giving the name of the file containing the component This is particularly easy for Resolve C C
94. d the left and right subtrees L and R pictured in Figure 3 Notice that each of the left and right subtrees of T has exactly the same type of structure as T itself For example the right subtree of 7 in Figure 3 called R consists of a root item k and the left and right subtrees L and R and so on for L and R BINARY_TREE 2 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 d root of T k lt _ root of R L left subtree ofR R right subtree of R L left subtree of T R right subtree of T Figure 3 The abbreviated structure of T and R The left subtree L of R is interesting It appears to consist of only a root item s and nothing more This is not quite right Actually it consists of a root item s and left and right subtrees each of which is an empty tree Empty trees are trees containing no items Empty trees in tree theory play the same role as do empty strings in string theory and empty sets in set theory So in fact every leaf item in tree T is the root of a subtree where both the left and right subtrees are empty trees With this in mind a more accurate depiction of the tree T is given in Figure 4 Generally trees are drawn as in Figure 1 omitting the empty trees seen in Figure 4 Even though they may not be shown don t forget that the empty trees are there Also note that this short cut in drawing trees results in some ambiguity Specifically when we write s by itself it is ambiguous as to w
95. descriptions refer to these objects in examples object Static Array Of Text al a2 object Text t object Integer il i2 A call to the accessor operator has the form of an expression Arar Ans This expression acts as the name of an object of type Item i e Text in this case whose value is that paired with i in al You may make this call only if there is a pair in al whose first component is il i e only if iZ lies between lower and upper inclusive You may use a il wherever any other object of type Item 1 e Text in this case may appear The accessor operator like all functions preserves its arguments But it is important to realize that the accessor expression al il does not simply denote the value associated with il in al it acts as the name of an object of type Item which you may consider to be in that particular pair in al This means that not only may you use the expression al il as a value of type Item you may even change the value of the object called a il but remember that this also changes the value of al The sample traces help illustrate some important points regarding the convenience and danger of accessor expressions The first and second sample statements show how an accessor expression such as al il acts like an object of type Item whose value may be changed depending on the statement in which the expression occurs The third sample statement s call to the swap operator involves other argume
96. ding a new operation There is no reason to do this when extending a component using the Resolve C discipline and you must avoid it 1 3 3 Using a Concrete Component As a client of the off the shelf concrete component used in the Monte_Carlo program all you need to know about it is summarized in the CCD in Figure 1 7 The name of the concrete instance is Random_Uniform_Generator_1 and it implements Random Uniform and hence also Random_Kernel The interface contract specifications in the latter two components explain how Random Uniform Generator 1 objects will behave in the client program the possible values those objects can have and the operations that you can call on them That s it As a client you do not need to see the code for Random_Uniform_Generator_1 7 In C C programs you would use the keywords virtual public in place of the Resolve C keyword extends 16 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Random_ Uniform Random_ Kernel extends implements Random_ Uniform_ Generator_1 Figure 1 7 The implements relation may hold between a concrete and abstract instance 1 4 Summary There are four kinds of Resolve C software components each of which is a class in C abstract and concrete instances and abstract and concrete templates An abstract instance defines an interface contract specification while a concrete instance comprises code that implements such a contract
97. e achieves its behavior The problem is in how to avoid dependence of a concrete component on other concrete components Specifically the checks and concrete to concrete extends relations are defined later in this chapter as concrete to concrete dependencies The remaining sections of this chapter explain these dependence relationships and then describe how to use templates to decouple or break the dependencies in what otherwise could become very long dependence chains among concrete components The result of carefully applying these rules is that there are only two categories of dependencies in well engineered software component catalogs abstract to abstract dependencies and concrete to abstract dependencies There are no long dependence chains or large dependence graphs 44 SOFTWARE COMPONENT ENGINEERING VOLUME 2 The design rules above inform the recommended solutions to several problems that arise in software component engineering even ones that on the surface do not seem directly related to dependencies Let s look at two of them now along with their template based solutions 3 2 Decoupling the Checks Relation Traditionally most people have agreed that one of the key features of good software is that it is bulletproof A proper interpretation of this advice is that the end user of an application program should not be able to do anything that causes it to crash If you ve studied them carefully as you should then you mig
98. e constructors for the fields only upon the first use of some Record accessor The destructor s execution time is essentially the sum of the execution times of the destructors for the fields 1f the constructors have actually have been invoked All the Record accessors take constant time once field construction takes place To bring this component into the context you write include RESOLVE Foundation h Component Coupling Diagram Record_ Kernel implements Record RECORD CLIENT VIEW RECORD 5 Descriptions Record_Kernel Type and Standard Operations Formal Contract Specification standard abstract operations Record Kernel JA Record Kernel is modeled by field0 Item0 fieldi Iteml field9 Item9 initialization ensures is initial self field0 and is initial self fieldl and and is initial self field9 and PAY Informal Description Record_Kernel is a special component that can be instantiated with any number of fields up to ten The above formal description then is not legitimate C code because in C a template has a fixed and definite number of parameters The above schema describes with the nature of Record_Kernel as a client should view it but not the exact code used for it The intended meaning is that when you instantiate this template with a particular number of fields say 3 then the Item types are Item0 through tem2 and the component names in the tuple m
99. e in tZ i You may make this call only if m is not empty Notice that this operation may remove a different pair from mI if called twice in identical states as illustrated in the sample tracing table Sample Traces Statement Object Values you 94 me 15 her 33 who 47 ml Undefine Any tl i you 94 her 33 me LN VON IA me 139 y her 33 who ml Undefine Any tl i her 33 PARTIAL_MAP 8 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Accessor Formal Contract Specification function R Item amp operator preserves D Items d is abstract Jx requires IS_DEFINED IN self d ensures d self d is in self LAJ Informal Description A call to the accessor operator has the form of an expression sa Ped eian This expression acts as the name of an object of type R Item i e Integer in this example whose value is that paired with in m You may make this call only if there is a pair in m whose first component is You may use m t wherever any other object of type R Item i e Integer in this case may appear The accessor operator like all functions preserves its arguments But it is important to realize that the accessor expression m t does not simply denote the value associated with r in ml it acts as the name of an object of type R Item which you may consider to be in that particular pair in m Thi
100. e is passed as a template parameter and there is nothing wrong with it e The first and third arguments to field name are for human consumption only Among other things this means that the C compiler will let you but you should not use field names from one Record instance to access the fields of a different Record instance Sample Traces Statement Object Values RECORD CLIENT VIEW RECORD 7 Accessor Note There is one accessor operation per field The description here uses the accessor operation for the first field i e fieldO as a prototype for the others which work similarly Formal Contract Specification function Item0 amp operator preserves Accessor0g fn0 is abstract ensures self self fn0 self fieldl self field9 1 Informal Description A call to the accessor operator has the form of an expression n1 first name This expression acts as the name of an object of type tem0 i e Text in this case which is the sub object in the first field of n i e the one whose field name is first name in this case You may use n first_name wherever any other object of type Text may appear The accessor operator like all functions preserves its arguments But it is important to realize that the accessor expression n first_name does not simply denote the value of the object in field first name of nl it acts as the name of an object of type Text which is the sub ob
101. e that the value of t2 is consumed and that you may make this call only if O lt i lt Ichildren tI l i e i is a valid position in the string of children of the root of TREE 6 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Sample Traces Statement Object Values i TREE CLIENT VIEW TREE 7 Remove Formal Contract Specification procedure Remove preserves Integer pos produces Subtree Types t is abstract JER requires 0 lt pos and pos lt children self ensures there exists a b string of tree of Item lal pos and children self a lt t gt b and self compose root self a b LAS Informal Description A call to the Remove operation has the form tl Remove i t2 This operation removes the tree in position i of the string of children of the root of t and returns it in 2 You may make this call only if O lt i lt Ichildren tl i e i is a valid position in the string of children of the root of t1 TREE 8 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Sample Traces Statement Statement A O O OOOO O El Values GGA tl Remove 1 t3 TREE CLIENT VIEW TREE 9 Accessor Formal Contract Specification function Items operator preserves Accessor Position amp current is abstract JAR ensures self compose self current children self pas Informal Description A call to the accessor operator has the form of an
102. eans that not only may you use the expression s current as a value of type Item you may even change the value of the object called s current but remember that this also changes the value of sl The sample traces help illustrate some important points regarding the convenience and danger of accessor expressions The first and second sample statements show how an accessor expression such as s current acts like an object of type Item whose value may be changed depending on the statement in which the expression occurs The third sample statement shows that s current may appear as an argument in a call where an tem is required This call involves other arguments e g 52 but none of the other arguments may be s or may involve an accessor expression for s because this would violate the repeated argument rule So while you might be tempted to write something like sl Push sl current this statement violates the repeated argument rule Be aware that the C compiler will not report this as an error You need to avoid the pitfall by personal discipline The last statement in the tracing table also illustrates that an accessor expression acts exactly like an object of type Item Notice that s current which is being pushed onto s2 in this statement is consumed its new value is O since Item is Integer here because Push consumes its argument So this statement changes both s and 32 STACK CLIENT VIEW STACK 7 Sample Traces
103. ected against multiple inclusion by the above C idiom But including it is not necessary because a h file is not intended to be compiled separately You really only need to include RESOLVE_Foundation h in a program that can be compiled e g in Monte_Carlo cpp from Figure 1 3 The simple rule is to include RESOLVE_Foundation h in all cpp files but nowhere else Next comes the interface section which contains the declaration of abstract_instance class Random_Kernel By convention for an abstract component that introduces a kernel type and its kernel operations the class name ends in _Kernel Inside the block that follows is the keyword public which indicates that the declarations that follow are part of the publicly accessible interface of the class In other words any client of this class is permitted to use the mathematical and programming entities declared after public The first of these entities are the mathematical definitions used to specify the interface contract of the programming type and operations Here the mathematics part makes three declarations e Math definition LIMIT is a mathematical integer constant whose value is supplied by the particular concrete instance chosen to implement this abstract instance As a client of Random_Kernel all you know about LIMIT is that it satisfies the restriction that LIMIT is positive and no larger than the maximum integer representable on this computer Note that the latter restri
104. el is modeled by string of Item initialization ensures self empty string 22 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 1 procedure Remove preserves Integer pos produces Item x is abstract VAGE requires 0 lt pos lt self ensures there exists a b string of Item lal pos and self a lt x gt b and self a b 1x F The list of formal template parameters appears within angle bracket delimiters lt gt wedged between the keywords abstract_template and class In this case there is only one formal parameter declared here as concrete_instance class tem which denotes the type of the entries in the objects being specified Other template components might have multiple template parameters 2 1 2 Collection Components In the Sequence family of components we parameterize each component by the type of entries in the string to generalize code that otherwise would be far more special purpose This use of templates is therefore called generalization By far the most common scenario of this kind arises when designing components whose mathematical models involve parameterized mathematical theories such as those mentioned at the beginning of this chapter strings sets functions and tuples Such components usually are called collection components because objects of their types are collections of objects of some other type s which is are the template parameter s The appendices document se
105. en trouble is inevitable Answer 1 is therefore not a good policy So consider answer 2 both parties are responsible for writing code that checks the precondition of the call Now there is no problem in principle but there is a problem in practice because this approach is needlessly inefficient Why do the same computation twice when once is always enough if only there were some policy to determine who is responsible for performing it This leaves two apparently reasonable choices To embrace answer 3 is to adopt the party line and make the operation implementer responsible There are two problems with this approach The first problem is that a check inside the operation body is often redundant even when the client programmer does not consciously check the precondition before making the call Consider for example the operation Greatest_Common_Divisor in the Euclid example global function Integer Greatest Common Divisor preserves Integer j preserves Integer k fom requires 0 lt j lt k and CHAPTER 3 ABSTRACT AND CONCRETE TEMPLATES DECOUPLING 49 0 lt k ensures IS GCD Greatest Common Divisor j k LL global function body Integer Greatest Common Divisor preserves Integer j preserves Integer k if j 0 return k else return Greatest Common Divisor k mod j j The recursive call in the body is never made if j 0 since it occurs in the else block of an if statement whose cond
106. eration an implemen tation of i client call to Random i Kernel d cod operation from a concrete extension calling kernel Figure 3 14 Intuitive operation of a concrete extension The first step in the process of implementing Random_Uniform is to create a concrete template that extends some implementation of Random_Kernel This concrete to concrete extends relation is entirely parallel in meaning to the abstract to abstract extends relation of Chapter 2 And the way to achieve it is entirely parallel to that used for a checking component the code for the new operation Uniform_Real depends only on the interface contract Random_Kernel not on any particular implementation of it The implementation being extended therefore can be made a template parameter to decouple what would otherwise be a concrete to concrete dependence C SS a DD a EGEN EN Concrete Template Random Uniform 1 NS a a O a ae ee KR ifndef CT RANDOM UNIFORM 1 define CT RANDOM UNIFORM 1 1 include AI Random Uniform h include AI Random Kernel h 1x concrete template lt concrete instance class Random Base pee implements abstract_instance Random Kernel 1 CHAPTER 3 ABSTRACT AND CONCRETE TEMPLATES DECOUPLING 65 public function body Real Uniform Real preserves Real a preserves Real b function body Integer Uniform Integer preserves Integer j preserves Integer k return j To Integer self Uniform
107. eration call and denotes a textual substitution that converts the template to an instance An instance is something that the compiler already knows how to process 39 40 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 3 Abstract and Concrete Templates Decoupling In addition to their most obvious use for generalization templates can help you design more elegant and reusable software components in another way This chapter starts by considering the problems caused by component to component dependence and considers why concrete to concrete component dependence in particular is a problem both for human understandability and for maintainability of software It then explains how to use templates to avoid concrete to concrete component dependence 3 1 The Problem of Component Dependence Component X depends on component Y if you need to know something about Y in order to understand X When the code for component X mentions component Y by name then X directly depends on Y Notice that dependence is fransitive i e if X depends on Y and Y depends on Z then X depends on Z Every specific dependence relation between components discussed so far 1 e extends implements and uses is transitive but even if a specific dependence relation were not transitive the general dependence it introduces would be transitive Looking the other direction if you change Y even slightly then you certainly have to understand the impact of t
108. es Consider for example the built in type Text A Text object is modeled by a mathematical string of characters With the kernel operations you can add remove or access a character by its position in the string and you can get the length of the string But what s so special about characters Why can t you have objects modeled by strings of say booleans or integers or reals or anything else and do Text like operations on those objects You can and luckily it s easy This chapter shows you how to do it 2 1 Parameterized Software Components Mathematical string theory is a generic or parameterized theory stringness is independent of what kind of entries are in a string Some other mathematical theories are similar You can have a mathematical set of any type of entry a mathematical function from any type to any type tuples of any types and so on Objects whose values are modeled as say mathematical strings of booleans are perfectly reasonable How would you define a new programming object type with this model Following the approach in Chapter 1 you would define a new abstract instance providing a type called say Sequence_Of_Boolean whose model would be a string of booleans with essentially the same kernel operations as Text Here s how you might specify it abstract_instance class Sequence Of Boolean public standard abstract operations Sequence Of Boolean PER Sequence Of Boolean is modeled by string of
109. eserves Polynomial Coefficients a preserves Real x object Real result if a Length 0 return 0 0 else object Real y a Remove 0 y result a Add 0 y return result x Horner Recursive Evaluation a x Ye CHAPTER 2 ABSTRACT AND CONCRETE TEMPLATES GENERALIZATION program body main object Character IStream input object Character OStream output object Polynomial Coefficients a object Real x evaluation object Integer k elapsed time object Timer 1 t Open input and output streams input Open External output Open External Read number of coefficients coefficients a and point x Read Polynomial And X input a x Print polynomial evaluate it and report timing for each evaluation method Original method output lt lt Original method n Write Polynomial output a k 0 t Restart while k lt 1000 evaluation Original Evaluation a x k lapsed_time t Reading output lt lt p lt lt x lt lt lt lt evaluation lt lt An lt lt execution time lt lt elapsed time lt lt usec n n Horner s rule done iteratively output lt lt Horner s rule iterative n Write Polynomial output a k 0 t Restart while k lt 1000 evaluation Horner Iterative Evaluation a x k u 7
110. essential difference between the code for an abstract instance and that for an abstract template the latter is parameterized so there is a list of formal template parameters Other than this the basic structure of a component family is just as explained in Section 1 3 2 3 1 The Kernel Type Standard Operations and Kernel Operations Figure 2 3 shows the entire file contents for the abstract component called Sequence_Kernel Some of this file is so cut and dried that all abstract template files that introduce new kernel types are identical in structure to this one ifndef AT define AT_ public standard abstract operations Sequence Kernel Sequence Kernel is modeled by string of Item initialization ensures self empty string 1 procedure Add CHAPTER 2 ABSTRACT AND CONCRETE TEMPLATES GENERALIZATION preserves Integer pos consumes Item amp x is_abstract requires 0 lt pos lt self ensures there exists a b string of Item lal pos and self a b and self a lt x gt b 137 procedure Remove preserves Integer pos produces Item amp x is_abstract requires 0 lt pos lt self ensures there exists a b string of Item lal pos and self a lt x gt b and self a b 1 function Items operator preserves Integer pos is abstract requires 0 lt pos lt self ensures there exists a b strin
111. expected to emit such a message if its precondition is violated You can see the effect of this problem in the second error message from Euclid which comes from the Get_From operation for Integer and which is therefore a lot less end user friendly than the first error message This leaves us to examine case 4 which is to make the client programmer responsible for establishing that the precondition holds before making any call to any operation The very presence of a non trivial precondition in the specification is a direct statement of this responsibility It means that the operation is allowed to do anything if that condition is not satisfied caveat emptor Sometimes the client programmer is able to show by careful reasoning that the precondition for a call holds and therefore does not need to write code to test 1t Other times the client programmer is unable to prove that the precondition holds and must write code to test it unless he she is willing to settle for a program that is not really bulletproof But in any event it 1s the client programmer who is responsible for establishing preconditions Bertrand Meyer calls this decision design by contract we also use the minor variant programming by contract because there is an official agreement between the client and the implementer of a component that lays down precisely which party is responsible for what The client is responsible for making sure that the precondition of an operation holds a
112. expression t1 current This expression acts as the name of an object of type tem whose value is the item at the root of tl The special word current is the only thing that can appear between in the accessor for type Tree It always refers to the single item at the root You may use t current wherever any other object of type Item may appear The accessor operator like all functions preserves its arguments But it is important to realize that the accessor expression t1 current does not simply denote the value of the root item in tIl it acts as the name of an object of type Item which you may consider to lie at the root of the tree This means that not only may you use the expression t current as a value of type Item you may even change the value of the object called t current but remember that this also changes the value of t Note that using the accessor function is the only way to change the root in a tree TREE 10 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Sample Traces Statement Object Values tl ceurrent amp i tl eurrent i TREE CLIENT VIEW TREE 11 Number Of Children Formal Contract Specification function Integer Number Of Children is abstract ensures Number Of Children children self 1 Informal Description A call to the Number_Of_Children operation has the form of an expression t1 Number_Of Children This operation returns
113. f A then compose x TI T2 is an element of binary trees over set A As an example here is a complete justification that the leftmost tree pictured in Figure 2 is a binary tree according to the definition just given e compose s empty tree empty tree is a binary tree say TI e compose x empty tree empty tree is a binary tree say T2 e compose y empty tree empty tree is a binary tree say T3 e compose t T2 T3 is a binary tree say T4 e compose k TI T4 is a binary tree the one we re looking for Notice that we say the path because there is exactly one path from the root to each item in a tree This property is the basis for another way to characterize trees BINARY_TREE 4 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Related Components e None Component Family Members Abstract Components e Binary Tree Kernel the programming type of interest with the operations below Compose Decompose Accessor Height Size Concrete Components Binary Tree Kernel la C This is a checking implementation of Binary_Tree_Kernel in which the execution time for each of the operations constructor Compose Decompose accessor and Size is constant while the execution time for the destructor is proportional to the size of the tree All objects of this type have the interface of Binary_Tree_Kernel with the concrete template name Binary_Tree_Kernel_la_C substituted for the abstract template
114. f for this purpose Similarly there is no programmer declared name to refer to the receiver object in an operation s body So in Resolve C self is the name reserved for the implicit formal parameter that is bound to the receiver object If n is an object of type Natural_Kernel_1 then the statement n Multiply By Radix k results in self being bound to n in the operation body Any changes to self as a result of executing the body of Multiply_By_Radix are reflected in object n back in the calling program after the call returns In other words self in the checking code above is the direct counterpart of self in the specification of Multiply_By_Radix There is a problem with the above code though the checking component in which it appears introduces a dependence on Natural Kernel 1 another concrete component This violates the concrete component dependence rule To complete the discussion of checking components let s see how to decouple this dependence using templates 3 2 4 Implementing a Checking Component The checking component code actually does not depend in any logical way on Natural_Kernel_1 the same code would work with any implementation of Natural_Kernel if that concrete component s name could be substituted for Natural Kernel I in the fully qualified name used in the code No problem You can parameterize the checking component by the implementation of Natural_Kernel that it checks The code for this is shown in Figure
115. f legal indices into a to be i and 12 respectively It also makes the value in each position of al table an initial value for type Item Because the initial value of a newly declared Array_Type object makes it essentially useless until the bounds are changed Set_Bounds is generally the first operation called for a new object of the type Sample Traces Statement Object Values 7 abcd 8 XYZ 9 bucks al Set_ Bounds il 12 BD 4 ARRAY 6 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Accessor Formal Contract Specification function Items operator preserves Integer i is abstract requires self lb lt i lt self ub ensures i self i is in self table 1 Informal Description A call to the accessor operator has the form of an expression AU ess This expression acts as the name of an object of type Item i e Text in this case whose value is that paired with i in al You may make this call only if there is a pair in al table whose first component is il i e only if iZ lies between al lb and al ub inclusive You may use al il wherever any other object of type Item 1 e Text in this case may appear The accessor operator like all functions preserves its arguments But it is important to realize that the accessor expression al il does not simply denote the value associated with il in al it acts as the name of an object of type Item which y
116. g of Item lal pos and self a lt self pos gt b NRZ function Integer Length is_abstract Ze ensures Length self ER he endif AT SEQUENCE KERNEL Figure 2 3 AT Sequence Kernel h The fact that Sequence Kernel is a template rather than an instance is evident first in the stylized comment at the beginning of this file The keyword abstract template tells the 3 In C C programs you would use the keyword template in place of the Resolve C keyword abstract_template 36 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 compiler to expect next the angle brackets lt gt that surround the list of the formal template parameters recall Section 2 1 1 Here there is one template parameter a concrete instance class called Item A formal parameter name is used only within the template where it is declared It has no special status and may be given any name not already in scope As you can readily see this interface contract specification includes the standard operations and the other kernel operations just like the abstract instance Random_Kernel in Chapter 1 2 3 2 The Extends Relation Abstract to Abstract Chapter 1 discusses a second component in the Random family an abstract instance that adds interface contract specifications for additional operations to extend Random_Kernel An analogous approach applies to templates Suppose you want to add to Sequence_Kernel an
117. gal but it is not recommended because it is very hard to understand PARTIAL_MAP CLIENT VIEW PARTIAL_MAP 9 Sample Traces Statement Object Values you 94 me 15 her 33 tl her 47 you 94 me 15 her 47 tl her 33 you 94 me 15 her 33 tl her 33 you 94 me 15 her 47 him 65 you 4 her m2 Define tl m1 t2 0 mer 15 her 47 him 05 you 4 her 94 PARTIAL_MAP 10 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Is_Defined Formal Contract Specification function Boolean Is Defined preserves D Items d is abstract ensures Is Defined IS DEFINED IN self d 1 Informal Description A call to the s_Defined operation has the form of an expression ml Is Defined tl This operation returns true iff there is a pair in m whose first component is rl Sample Traces Statement Object Values you 0 me 15 her 47 tl him b true b ml Is Defined t1 you 0 me 15 her 47 tl him false you 0 me 15 her 47 tl her false b ml Is Defined t1 you 0 me 15 her 47 tl her true PARTIAL_MAP CLIENT VIEW PARTIAL_MAP 11 Size Formal Contract Specification function Integer Size is abstract ensures Size self 1 Informal Description A cal
118. ger n pts_ in U pts in Q object Real pi estimate Open input and output streams input Open External output Open External Ask user for number of points output lt lt Number of points input gt gt n Create counts for estimate while pts in U lt n AB preserves n alters rn pts in U pts in Q maintains 0 lt pts in Q lt pts in U lt n and pts in Q number of points that have been in the quarter circle and pts in U number of points that have been in the unit square decreases CHAPTER 1 ABSTRACT AND CONCRETE INSTANCES 7 pts in U 1 object Real x y Generate a random point in the unit square U pts in Utt Check if point is also in the quarter circle Q if x x y y lt 1 0 pts in Ott Estimate pi pi estimate 4 0 To Real pts in 0 To Real n output lt lt pi is about equal to lt lt pi estimate lt lt An Close input and output streams input Close External output Close External Figure 1 3 Monte_Carlo cpp This program introduces no substantial new features of the Resolve C discipline except how to make visible and then how to use types and operations that are not built in but rather are defined by off the shelf software components 1 2 1 Bringing a Concrete Instance Into Scope The following line include CI Random Uniform Generator 1 h brings into sco
119. gramming type Id Name Table allows you to build query and dismantle a set of ordered pairs 2 tuples whose two components are an integer called an id and a string of characters called a name Each id and each name can appear at most once in any given Id Name Table object For example suppose you need to keep a simple database of employee ids and their names assuming all employees have unique names To do this you can create an Id Name Table object To enter the name of an employee you simply add to the Id Name Table object the pair consisting of the employee s id and the employee s name Later you can look up the employee s name given the employee s id and vice versa Other operations allow you to manipulate and observe properties of an d Name Table object such as its size i e the number of pairs it holds Related Components e Partial_Map a type that is similar to d Name Table except that a it is a template so the client can select the types of both components of the ordered pairs and b you can look up a pair based on the value of only the first of its two components not both Component Family Members Abstract Components Id Name Table Kernel the programming type of interest with the operations below Add Id Name Pair e Remove Id Name Pair e Remove Any Pair e Look Up Name Via Id e Look Up Id Via Name e Id Is In Table e Name Is In Table e Size Concrete Components e Id Name Ta
120. h To do this you can declare an Array object whose items are of type Real and set it up to be indexed by the values 1 through 31 e g for January When you set these bounds each entry in the table has an initial value for type Real 1 e 0 0 You may access and update the value associated with each day Once you are done processing data for January you may use the same Array object to record the high temperature for each day of February say Simply reset the Array s bounds to be 1 through 28 or 29 and repeat the process The most closely related component is Static_Array which is nearly identical except in regard to when the index bounds are fixed Another closely related component is Sequence A Sequence object starts out as an empty string of Item values so if you want to use it as a table in the fashion mentioned above you have to add entries to it one by one until the table is populated with values A Array object becomes populated with initial values of type tem as soon as you set its interval bounds With a Sequence object you can interleave operations that change the size of the Sequence with operations that access and update existing entries possibly deferring the decision to add more entries or to remove some however adding and removing changes the indices of some of the existing entries With the Array object you can t change the bounds of the table without completely wiping out the previous table and starting over with new bound
121. hat involve RADIX i e Multiply_By_Radix Divide_By_Radix and Discrete_Log This property holds for the concrete instance Natural_Number_1_C used in the tracing table examples because it implements all of these operations with RADIX 10 Sample Traces Statement Object Values nl 45142398 i 46 i nl Radix 0 EAS nl 45142398 i 10 NATURAL 10 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Convert From Integer Formal Contract Specification procedure Convert From Integer preserves Integer k is abstract Zr produces self requires k gt 0 ensures self k 1 Informal Description A call to the Convert_From_Integer operation has the form nl Convert From Integer i This operation sets n equal to i You may make this call only if i is non negative Sample Traces Statement Object Values nl 13 i 497 nl 497 i 497 nl 78 i 497 NATURAL CLIENT VIEW Increment Formal Contract Specification procedure Increment is abstract JEI ensures self self 1 1 Informal Description A call to the Increment operation has the form nl Increment This operation adds one to n Sample Traces Statement Object Values NATURAL 11 NATURAL 12 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Decrement Formal Contract Specification procedure Decrement is abstract requires self gt 0 ensures self self
122. hether we mean the tree with root s and left and right subtrees that are empty or just the item s In most cases the type and therefore the intention should be clear from context When it is not we ll try to be careful to say exactly what we mean ZN NN NEIN Nur Figure 4 The full structure of T The size of T denoted ITI is the number of items in T e g in Figure 1 as in Figure 4 ITI 9 The height of T is the number of items on the longest path from the root to some leaf The height of an empty tree is defined to be 0 Again referring to Figure 1 or Figure 4 you can see the height of T is 4 since the path string of items lt d k t x gt has length 4 so do two other paths but no path is longer than 4 The notion of a path also gives rise to that of a level An item BINARY_TREE CLIENT VIEW BINARY_TREE 3 occurs on level k in a tree if the length of the path from the root to that item has length k In T of Figure 1 and Figure 4 d is on level 1 a and k are on level 2 h s and t are on level 3 etc Notice that the empty trees shown in the full structure of Figure 4 do not contribute either to the size or the height of T A binary tree is complete if all the leaves occur on at most two different levels and if all the leaves at the bottom highest numbered level are as far to the left as possible This means that T 1s not a complete binary tree nor are the first two trees shown in Figure 2 But the third tree in Figure 2
123. his change on X and you might have to change X too and then anything that depends on X So more dependencies reduce not only the understandability but the maintainability ease of change of software components 3 1 1 Avoidable Dependence Is Bad Some dependencies are simply unavoidable For example consider the example from Chapter 1 whose CCD is reproduced in Figure 3 1 There is just no way to explain the operation Uniform_Real which is in the component Random_Uniform without talking about the mathematical model of self which is in the component Random_Kernel Of course you could try to eliminate the dependence between the two abstract components by combining the dependent specifications within a single abstract component But this wouldn t solve the problem of limiting what you need to know and understand It would merely make internal and therefore not apparent from a CCD the inherent dependence of the specification of each operation on the kernel type s mathematical model Since CCDs are intended to show dependencies this attempt to mask the problem would be self defeating Random_ Uniform extends Figure 3 1 Unavoidable dependence between abstract instances Figure 3 2 illustrates the kind of situation you really want to avoid a long dependence chain or a long path of arrows in a CCD Remember in order to understand a component you need to understand all the components it depends on either directly or by transiti
124. ht notice that some of the application program examples in this book seem to be bulletproof For example consider the Euclid program discussed in Volume 1 and reproduced here for convenience PILE ii ii e arten ana Fr re ff Main Program Euclid s algorithm for GCD a ai ae Date 13 August 1996 revised 24 November 2006 Author Bruce W Weide Brief User s Manual Asks for two integers and if both are non negative and one is positive reports the GCD of the two and then quits LE NE BESSA SSR sae eae ERDE SEHE SSeS oe See SES See A ler ser daa fi Global Context 2727722772077 a ii ii Ba math definition DIVIDES d integer n integer boolean is there exists k integer n k d math definition IS GCD gcd integer m integer n integer boolean is m 0 or n 0 and DIVIDES gcd m and DIVIDES gcd n and for all k integer where DIVIDES k m and DIVIDES k n k lt gcd 1 CHAPTER 3 ABSTRACT AND CONCRETE TEMPLATES DECOUPLING lobal function Integer Greatest Common Divisor g u g de ry preserves Integer j preserves Integer k requires 0 lt j lt k and O lt k ensures IS GCD Greatest Common Divisor j k pay 2244444422 global function body Integer Greatest Common Divisor preserves Integer j preserves Integer k return k else return Greatest Common D
125. ike all Resolve C types Array_Kernel comes with operator amp and Clear Notice that the bounds on the interval of legal indices is part of the model of an individual Array_Kernel object so it is perfectly OK to swap two Array_Kernel objects that have different bounds Of course these two Array_Kernel objects still must have the same tem type or they are not of the same type and therefore cannot be swapped with each other ARRAY 4 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Note The sample traces for this and the other operation descriptions refer to the type Array_Of_Text which is the result of the following instantiation concrete instance class Array Of Text instantiates Array Kernel 1 C lt Text gt O Sample Traces Statement Object Values ARRAY CLIENT VIEW ARRAY 5 Set_Bounds Formal Contract Specification procedure Set Bounds preserves Integer lower preserves Integer upper is abstract JER ensures self lb lower and self ub upper and for all i integer there exists x Item i x is in self table and is initial x iff self lb lt i lt self ub LAS Informal Description Note This and the other operation descriptions refer to these objects in examples object Array Of Text al a2 object Text t object Integer il i2 A call to the Set_Bounds operation has the form al Set Bounds il i2 This operation sets the lower and upper bounds on the interval o
126. ike one e g field name Full Name 1 Text middle name The first argument is the name of the Record instance to which the new field name applies in this case Full_Name The second argument is the field number to which the new field name refers in this case the second field i e field number 1 The third argument is the type of the field being named in this case Text The fourth argument is the field name being declared in this case middle_name Notice that a field name must have the syntax of an identifier in C i e it must look like the name of an object Moreover for all other intents and purposes middle_name is treated exactly like the name of an object its scope is identical to that of any other object declared at this point and there must be no other object in the current scope with this name Two other possibly surprising facts about field names are e You may have two names for the same field of the same Record instance e g field name Full Name 1 Text middle name field name Full Name 1 Text m name Ordinarily you would not make these two declarations in the same scope because it is sure to be confusing to a reader But a field name has the same scope as an object declaration made at the same point So sometimes you will have different names for the same field because one field name is declared in one scope and another is declared in a different scope This happens for example when a Record instanc
127. in a pair whose first component is t1 Sample Traces Statement Object Values ml you 94 me 15 tl her 33 ml Define tl 1 you 94 me 15 her 33 PARTIAL_MAP 6 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Undefine Formal Contract Specification procedure Undefine preserves D Item d produces D Items d copy produces R Items r is abstract ZEI requires IS DEFINED IN self d ensures d copy d and d copy r is in self and self self d_copy r LAY Informal Description A call to the Undefine operation has the form ml Undefine tl t2 i This operation removes from m the pair whose first component is and returns its value in 12 i You may make this call only if there is a pair in m whose first component is Sample Traces Statement Object Values you 94 me 15 her 33 me anything 47 ml Undefine tl t2 i you 94 her 33 me me 15 PARTIAL_MAP CLIENT VIEW PARTIAL_MAP 7 Undefine_Any Formal Contract Specification procedure Undefine Any produces D Item d produces R Items r is_abstract JER requires self empty set ensures d r is in self and self self d r 1x Informal Description A call to the Undefine_Any operation has the form ml Undefine Any tl i This operation removes some pair from mI any pair and returns its valu
128. in the component file CI Complex Kernel_1 h 1 2 Example Monte Carlo Estimation of x Let s look at an example of how you can use an off the shelf component to solve an application problem Among the many interesting ways to estimate things is to take a random sample For instance suppose you want predict what fraction of votes will be cast for candidate X in an election You don t want to ask everyone how he she will vote because that would be much too expensive An appropriate approach is to conduct an opinion poll i e to select a small but not too small random sample of potential voters and to use the fraction of the sample respondents who plan to vote for candidate X as an estimate of the fraction of all voters who plan to vote for candidate X The same idea can be used to estimate other things e g the value of x Figure 1 2 illustrates this Suppose you generate random points within a unit square Then the fraction of those points that fall within the quarter circle Q can be used to compute an estimate fort How The expected number of points that fall within the unit square that also fall within some region inside CHAPTER 1 ABSTRACT AND CONCRETE INSTANCES 5 it is equal to the area of that inner region divided by the area of the unit square which is 1 For example half the points are expected to lie in the top half of the unit square half are expected to lie in the left half of the unit square and so on 0 0
129. interface contract for an operation to reverse a sequence Figure 2 4 shows how to do this NN a a Sa a la a ar a aa a oe a aa if Abstract Template Sequence Revers Ik USERS SE SS ESS SSS SS SS SES SS SSS I Se u ifndef AT SEQUENCE REVERSE define AT SEQUENCE REVERSE 1 ff sees SEES SSD SSS Shea 25H aoe SS ooo oie SE fi Global Context 222 a mee a aetna aw ee SNE DE public procedure Reverse is_abstract ensures 1 E7 endif AT SEQUENCE REVERSE Figure 2 4 AT Sequence Reverse h The formal template parameter of Sequence_Reverse happens to be called Item as in Sequence_Kernel However these two templates are not connected by this name The formal CHAPTER 2 ABSTRACT AND CONCRETE TEMPLATES GENERALIZATION 37 parameter names in these two templates could be different from each other The connection is made not by the parameter names but rather by this code abstract template lt concrete instance class Item gt class Sequence Revers extends abstract_instance Sequence Kernel lt Item gt This declaration of Sequence Reverse means that every instance of the Sequence Reverse template extends some corresponding instance of the Sequence_Kernel template In particular the abstract instance Sequence_Reverse lt Item gt extends the abstract instance Sequence_Kernel lt Item gt for any type that a client might choose to p
130. ion and it is used for one and only one thing in Resolve C programs If you are implementing a kernel component then you always collect together the individual objects that you are using to represent an object of the new type and make them fields RECORD 4 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 of an instance of Representation Client programmers need to know nothing about Representa tion except that a it is essentially Record with a different name and b it shouldn t be used in ordinary client programs Related Components e Array and Static Array types that are similar to Record except that they may contain objects of only one type but they may contain far more objects than a Record e Representation a type that is virtually identical to Record except that it is used in only one place to hold the individual objects that comprise the representation of a kernel abstraction and hence of no use to client programmers Component Family Members Abstract Components e Record Kernel the programming type of interest with the operations below e Accessor one accessor for each field Concrete Components e Record This is the standard implementation of the abstract template Record Kernel that comes built in to Resolve C It uses a technique called lazy initialization so the constructor is very fast and takes time independent of the number and types of the fields You pay the cost of th
131. ion operations the specification of the operation Write_Polynomial is partly informal see the part of the postcondition inside square bracket delimiters It is unambiguous that the output stream must be open at the time of the call and that it remains open and attached to the same sink as when the call was made But the exact format of the output produced is not completely specified here In principle it could be formally specified just as the input format is formally specified Poly_Eval cpp is the first sample program we ve seen that illustrates how it is possible to specify the format of inputs and or outputs It also is the first to illustrate that the exhortation to use formal specifications is not meant to be taken as dogma but as a practical technique for making your programs more understandable and more maintainable by others and by you in the future after you ve forgotten the details Indeed there are two other places where the commitment to formality hasn t been observed here the loops in the input and output operations don t have loop invariants At least the input loop probably should have this because the behavior of Read_Polynomial_And_X is formally specified By the way we ran this code on one computer with the following input OHM O BW NY oo OOO O O O O m w GOTOGO The program produced the following output Original method p x 14 000000 13 000000 12 000000 11 000000 10 000000 9 000000 0
132. is appropriately called instantiates The code of Figure 3 11 creates a new concrete template by partially instantiating another concrete template That is the number of template parameters for the client programmer to provide goes from two in Sequence_Kernel_C to one in Sequence_Kernel_la_C but the client still has to instantiate the template to use it The 62 SOFTWARE COMPONENT ENGINEERING VOLUME 2 relation connecting these two templates is called specializes because the all purpose concrete template Sequence_Kernel_C has been made less universal but therefore easier to instantiate by fixing one of its template parameters Figure 3 12 shows this relationship in the CCD for Sequence_Kernel_la_C Sequence_ Kernel Sequence_ implements Sequence_ Kernel_1a checks Kernel_C Sequence specializes Kernel_1a_C Figure 3 12 CCD for Sequence_Kernel_1a_C and the specializes relation To summarize then there is a long and somewhat tortured story here The defensiveness dilemma has to be addressed somehow a case analysis of possible solutions leads to the selection of design by contract as the proper policy that policy leads to the need for checking components checking components introduce concrete to concrete dependencies that violate the concrete component dependence rule How can you avoid these concrete to concrete dependencies Use templates to decouple them Then specialize the all purpose checking component if you w
133. is familiar with because all Resolve C components look like this It facilitates building tools that process files containing Resolve C components Of course the C compiler doesn t care about these comments we re talking about other toolos that might process component files for purposes such as convenient browsing through a component catalog The two lines that follow the opening comment block starting with ifndef and define and the very last line starting with endif are part of a standard idiom of C One problem with C is that 1f you include the same file more than once in a single compilation then you get errors because the compiler doesn t like to see the same declarations and definitions more than once A single off the shelf component might well be included in two or more different and independent subcomponents of a main program To prevent a component from being introduced into your program more than once you place the main contents of each file that might ever be included anywhere inside a special kind of if statement that is a directive to the compiler itself It introduces a condition to be checked Only if that condition holds does the compiler actually include the code between the if directive and the corresponding endif The if directive here ifndef asks the compiler to check whether the global compile time constant AL RANDOM_KERNEL is not defined hence ndef The name of this con
134. ition is j 0 So the calling program does check this part of the precondition not because it s afraid to call Greatest_Common_Divisor in that case but because it doesn t have to this is the base case in the recursion The subtle difference in intent for the above case might seem pedantic So consider the other part of the requires clause which says in part that the first argument to the operation is no larger than the second There is no explicit check for this before the recursive call because the client programmer can argue that the first actual parameter k mod j is no larger than j even without checking This conclusion is based purely on reasoning about the program behavior about what mod can return In other words if you can establish by a valid argument that a precondition holds at the time of a call then there is no reason to have any code to check that the precondition holds From this example you can see how adding a test at the beginning of the operation body would only make this program less efficient than it is now and no safer in terms of precondition violations Well this is not entirely true because there is one call from main in this case that is not recursive This is precisely the reason the main program does check the precondition of Greatest_Common_Divisor before calling it The manifestation of this is that the end user who enters two integers that do not satisfy the precondition is informed
135. ive Design by contract says it is ultimately the client s responsibility to make sure k has a legal value and that an implementation of Natural_Kernel say Natural_Kernel_1 should not check this condition in the body of Multiply_By_Radix Natural_Kernel can therefore help to illustrate how to write precondition checking code for a component operation just once and package it into a component so it works for all of the operation s call sites in all client programs 3 2 3 Checking Components and the Checks Relation The recommended approach to catching erroneous calls to component operations during client program development is to create and use a checking component A checking component for Natural_Kernel is a concrete component that wraps an implementation of Natural_Kernel e g Natural_Kernel_1 inside a protective wall and thereby defends that implementation against a client programmer s failure to observe the design by contract rule As illustrated in Figure 3 6 the checking component checks the wrapped implementation by using the following strategy in the body of Multiply_By_Radix e Check the precondition of Multiply_By_Radix e Report a violated assertion to the client and halt execution immediately if the precondition is not satisfied e Continue the computation normally by calling Multiply_By_Radix from the wrapped implementation if the precondition is satisfied Since none of the other Natural_Kernel operations has
136. ivisor k mod j j program body main object Character IStream input object Character OStream output object Integer small large Open input and output streams input Open External output Open External Get two integers from user put them in proper order output lt lt Please input an integer input gt gt small output lt lt Please input another integer input gt gt large if small gt large small amp large Compute GCD of small and large 46 SOFTWARE COMPONENT ENGINEERING VOLUME 2 if small lt 0 or large lt 0 Can t find GCD output lt lt nSorry both integers must be non negative lt lt and one must be positive iss Compute and report GCD i object Integer gcd gcd Greatest_Common Divisor small large output lt lt nGCD lt lt gcd lt lt An Close input and output streams input Close External output Close External Figure 3 4 Euclid cpp This program asks the end user to input two integers It expects both numbers to be non negative and one to be positive and if this isn t the case then the program gently reports the error Sorry both integers must be non negative and one must be positive On the other hand watch what happens if you respond to the program s first prompt for an integer by typing an integer The program squawks something
137. ject in that particular field of n This means that not only may you use the expression nI first name as a value of type Text you may even change the value of the object called n first_name but remember that this also changes the value of n The sample traces help illustrate some important points regarding the accessor expressions The first and second sample statements show how an accessor expression such as nI first name acts like an object of type Text whose value may be changed depending on the statement in which the expression occurs The accessors for Record are different than other accessors in an important way however Itis not a violation of the repeated argument rule to use two or more different fields of the same Record object in a single call You may use the same field of two different Record objects in a single call e g as illustrated in the tracing table where the first name fields of n and n2 are swapped This would not be a repeated argument violation under any circumstances because n and n2 are different objects What s different with Record objects is that it is also acceptable to use two different fields of the same Record as illustrated in the last tracing table example where the first_name and middle name fields of n1 are swapped Here s how to think of it Record is merely a way to declare a group of objects with names of the form r f where r is the name of the common Record they re part of presumably bec
138. l only if s is not empty Sample Traces Statement Object Values sl lt 13 58 12 21 gt i 92 sh amp 58 12 2 gt i 13 STACK 6 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Accessor Formal Contract Specification function Items operator preserves Accessor Position amp current is abstract PAGE requires self empty string ensures there exists a string of Item self lt self current gt a 1 Informal Description A call to the accessor operator has the form of an expression sl currentl 2 47 This expression acts as the name of an object of type tem whose value is the item at the top of sl You may make this call only if s is not empty The special word current is the only thing that can appear between in the accessor for type Stack It always refers to the single item that you can access directly without popping any others the top leftmost item which is the one that would be removed if you called the Pop operation at the point where you are using the accessor operator You may use s current wherever any other object of type Item may appear The accessor operator like all functions preserves its arguments But it is important to realize that the accessor expression s current does not simply denote the value of the top item in s1 it acts as the name of an object of type Item which you may consider to lie at the left end of the string s This m
139. l to the Size operation has the form of an expression ml size Y ure This operation returns an Integer value which is the size of the set ml i e ImIl Sample Traces Statement Object Values you 0 me 15 her 47 68 PARTIAL_MAP 12 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Queue Motivation Applicability and Indications for Use The programming type Queue allows you to collect and later process items in first in first out FIFO order For example suppose you need to keep track of requests for service and to service them in the order in which they were received To do this you can create a Queue object whose elements are of a type that records the information for a single request enqueue each request as it arrives and dequeue a request whenever you are ready to service the next one Other operations allow you to access the front item in a Queue object and to determine its length Related Components e Stack a type that is similar to Queue except that when you remove an item it is not the first one that was put in but rather the last one e Sorting Machine a type that is similar to Queue except that when you remove an item it is not the first one that was put in but the next one in sorted order according to some ordering based on the values of the items Component Family Members Abstract Components Queue Kernel the programming type of interest with the operati
140. lapsed_time t Reading output lt lt p lt lt x lt lt lt lt evaluation lt lt An lt lt execution time lt lt elapsed time lt lt usec n n 30 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Horner s rule done recursively output lt lt Horner s rule recursive n Write Polynomial output a k 0 t Restart while k lt 1000 evaluation Horner Recursive Evaluation a x k u gt lapsed_time t Reading output lt lt p lt lt x lt lt lt lt evaluation lt lt An lt lt execution time lt lt elapsed time lt lt usec n n Close input and output streams input Close External output Close External Figure 2 2 Poly_Eval cpp This program introduces only one substantially new feature of Resolve C the use of a concrete template Sequence Kernel la C Like the abstract template it implements a concrete template has formal parameters that must be bound to actual parameters in a client program uses 1t There can be many alternative concrete templates that might implement a given abstract template After deciding which of these concrete templates to use in a given situation a choice that depends on matching the performance time and space characteristics of the candidate implementations with the application s performance requirements the client programmer needs to d
141. lopment process however a client programmer being human can make a mistake and inadvertently call an operation whose precondition is not satisfied Debugging code with such an error is facilitated when it is detected and reported immediately at the point of occurrence which does not happen under a strict interpretation of design by contract Enter checking components which are wrappers for components that have been developed using design by contract The client programmer during the software development process wraps a checking component around the normal unchecked component that will be used in the final delivered product substituting for it the original component only after he or she is convinced that 1t is being used fully in accordance with the design by contract rule Concrete extensions arise from the need to add functionality after a kernel component has been designed and implemented There is no way a designer can hope to think of every useful CHAPTER 3 ABSTRACT AND CONCRETE TEMPLATES DECOUPLING 69 operation for a component up front before it is released in a shared catalog to be used by others The kernel operations must be reasonably powerful but cannot be all encompassing When a component family needs to be supplemented with a new operation its interface contract specification can be added by using an abstract extension The implementation of this new operation calls for a concrete extension a component whose code is
142. ly if 0 lt i lt lIt I The numbering of positions in the string starts at O For example to remove the left most character of and return it in c you might write t1l Remove 0 c Sample Traces Statement Object Values tl Help tl Remove i c tl Remove 2 c TEXT CLIENT VIEW TEXT 7 Accessor Formal Contract Specification function Characters operator preserves Integer pos is abstract pol requires 0 lt pos lt self ensures there exists a b string of character lal pos and self a lt self pos gt b 1 Informal Description A call to the accessor operator has the form of an expression erai esr This expression acts as the name of an object of type Character whose value is the character in position i of string t You may make this call only if 0 lt i lt It I The numbering of positions in the string starts at O For example to set the left most character of t to X you might write assuming It 1 t1 0 X The accessor operator like all functions preserves its arguments and i in the example But it is important to realize that the accessor expression t i does not simply denote the value of the character in position i of string t1 it acts as the name of a Character object which you may consider to lie in that position of the string This means that not only may you use the expression tl i as a value of type Character you
143. matically catching violated preconditions makes it easier to debug programs Professional programmers also can benefit from using this approach during early software development stages at least CHAPTER 3 ABSTRACT AND CONCRETE TEMPLATES DECOUPLING 51 There remains one plausible objection to the design by contract rule It would be nice to be able to catch a client programmer s mistakes early in the development process not after delivery of the program but rather during its development when some errors are almost inevitable Can this be done without proliferating throughout the client program precondition checking code that later according to design by contract should be removed before delivery Yes by using templates 3 2 2 Example The Vatural Family The abstract instance Random_Kernel used in the Monte_Carlo example in Chapter 1 is somewhat unusual in that a client program may invoke any of its operations at any time In other words none of the operations has a requires clause there is no way for the client of an implementation of Random_Kernel to violate the interface contract by failing to respect a precondition So let s look at a different abstract instance to illustrate how to address the problem of an explosion of precondition checking code in client programs This component allows you to manipulate arbitrarily large natural numbers and as is more typical of interface contracts one of its operations has a non trivial prec
144. may even change the value of the object called t i but remember that this also changes the value of The sample traces help illustrate some important points regarding the convenience and danger of accessor expressions The first and second sample statements how an accessor expression such as t1 i acts like an object of type Character whose value may be changed depending on the statement in which the expression occurs The third sample statement shows that t i may appear as an argument in a call where a Character value object or constant is required This call involves other arguments e g 12 but none of the other arguments may be or may involve an accessor expression for t because this would violate the repeated argument restriction So while you might be tempted to write something like t1 1 amp t1 24 this statement violates the repeated argument rule for the swap operator This conclusion is especially clear if i 24 at the time the statement is executed but it is true even if i has some other value since both swap operator arguments are accessor expressions for the same object namely t Be aware that the C compiler will not report this as an error You need to avoid the pitfall by personal discipline TEXT 8 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Sample Traces Statement Object Values tl HpLw TEXT CLIENT VIEW TEXT 9 Length Formal Contract Specification func
145. milar concrete instances Every Resolve C software component then is an abstract or concrete instance or template This chapter introduces abstract and concrete instances Chapters 2 and 3 describe how components that are abstract and concrete templates add substantial generality and power The appendices summarize the interface contract specifications for a number of general purpose Resolve C components 1 1 1 Subroutine Libraries What specifically is the nature of a software component in Resolve C Based on Volume 1 there is one obvious choice for what an off the shelf software component should be a global operation Throughout the early history of computing this is precisely what off the shelf software components were A collection of operations that can be used by other client programmers is known as a subroutine library interface contract specifications are provided to client programmers but implementations generally are kept secret because a client programmer has no reason to see them 2 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 One of the problems with limiting component collections to being subroutine libraries is that the types of the parameters are limited to a fixed set of built in types In Resolve C for example every global operation in a subroutine library would have only parameters of type Boolean Character Integer Real Text Character_IStream or Character_OStream This might not seem too re
146. mpany Many programming texts advocate this But the Euclid program violates this advice For example its Greatest_Common_Divisor operation has a non trivial precondition yet the implementation of the operation does not check that this condition holds What are the differences among the various situations in Euclid Why does one kind of error lead to an easy to understand application specific error message while the other leads to a cryptic general purpose but still arguably helpful to the programmer error message Why do some operation implementations check their preconditions while others do not The defensiveness dilemma is an important issue faced by an operation s implementer including a client programmer who needs to implement a new operation To check or not to check preconditions that is the question 1 These are two of the tragedies that can befall a defective program on one system The catastrophes on your system may vary 48 SOFTWARE COMPONENT ENGINEERING VOLUME 2 The term defensiveness comes from the traditional party line advice always defend against client errors in calling your operation by checking its precondition in the operation s implementation A closer analysis of the situation reveals why there seems to be a dilemma and why the party line is not the right approach For any particular call of any particular operation there are four possible answers to the question of which person client
147. n have the same flexibility as mathematical theories in the sense of being parameterized A parameterized software component is called a template By using a template instead of an editor to generalize from Text to Sequence you avoid the three problems noted above 2 1 1 Resolve C Language Support for Templates In Resolve C you declare one formal template parameter for each different type name that needs to be replaced hence the term parameterized component This formal parameter is analogous to a formal parameter to an operation That is a formal parameter is an arbitrary name that serves as a placeholder for information to be filled in later The main differences between operation parameters and template parameters are summarized in Figure 2 1 Parameter toan Parameter to a operation template What the formal parameter stands for A value of the A type fixed type of the parameter When the actual parameter value is supplied Execution time Compile time Figure 2 1 Operation parameters vs template parameters In Resolve C syntax here s how you might use a template parameter to write an abstract template that serves as an interface contract specification for the generalized Sequence_Kernel Section 2 3 gives the details abstract template lt concrete instance class Item gt class Sequence Kernel public standard abstract operations Sequence Kernel Sequence Kern
148. name Binary_Tree_Kernel To bring this component into the context you write include CT Binary Tree Kernel la C h Component Coupling Diagram Binary _ Tree_ Kernel implements Binary _ Tree _ Kernel_1a_C BINARY_TREE CLIENT VIEW BINARY_TREE 5 Descriptions Binary_Tree_Kernel Type and Standard Operations Formal Contract Specification standard abstract operations Binary Tree Kernel jet Binary Tree Kernel is modeled by binary tree of Item initialization ensures self empty_tree Lay Informal Description The model for Binary_Tree_Kernel is a binary tree of items which is initially empty A Binary_Tree_Kernel object may be arbitrarily large Like all Resolve C types Binary_Tree_Kernel comes with operator amp and Clear Note The sample traces for this and the other operation descriptions refer to the type Binary_Tree_Of_Integer which is the result of the following instantiation concrete instance class Binary Tree Of Integer instantiates Binary Tree Kernel la C lt Integer gt O Sample Traces Statement Object Values 0 EX DE BINARY_TREE 6 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Compose Formal Contract Specification procedure Compose consumes Item amp x consumes Binary Tree Kernel amp left subtree consumes Binary Tree Kernel amp right_subtree is_abstract LEE produces self ensures self compose x left subtree right subt
149. nd Natural Number I all use RADIX 10 which conveniently matches the way we ordinarily write numbers This helps in understanding the sample trace tables that follow Stated in these terms another way to explain the call nl Multiply By Radix i is to say that it appends i as the new low order rightmost digit of n1 Sample Traces Statement Object Values nl 45142398 i 1 nl 451423981 i 1 nl 4514239810 i 1 3 Technically the word digit applies only when RADIX 10 For RADIX 2 a digit usually is called a bit a contraction of binary digit However it is customary to use digit regardless of the value of RADIX especially when RADIX is a fixed but unknown constant as it is here NATURAL CLIENT VIEW NATURAL 7 Divide_By_Radix Formal Contract Specification procedure Divide By Radix produces Integer amp k is abstract JET ensures self self RADIX k and 0 lt k lt RADIX LEJ Informal Description A call to the Divide_By_Radix operation has the form nl Divide By Radix i This operation divides n by RADIX and returns with the remainder in i Stated in terms of the radix representation of n1 see Multiply_By_Radix above another way to explain the call nl Divide By Radix i is to say that it removes the low order rightmost digit of n and returns with that digit as the value of i Sample Traces Statement Object Values nl 45142
150. nents or concrete components But the effects of dependence chains are more serious when they involve concrete components because 1n the absence of abstract components and the knowledge of how to take advantage of them most programmers routinely introduce concrete to concrete dependencies Without disciplined design a concrete component depends on another concrete component and that depends on yet another concrete component that on yet another and so on you have a long dependence chain In fact it gets worse If you don t consciously limit dependencies between concrete components then a typical concrete component depends on more than one other component so the dependencies branch out Every time there is a dependence from a concrete component to two others there is a doubling of the number of dependence chains The resulting chains together form a dependence graph A component at the root of this graph depends on all the components in all the dependence chains in the entire graph and the number of chains in the graph typically grows very quickly with the lengths of the chains because of the typical branching factor for a concrete component Figure 3 3 illustrates how a single concrete component like the one on the right can depend directly and indirectly on a very large number of other components Imagine that the same kinds of dependencies continue for another few levels of arrows and you can see that trouble is brewing
151. ng real number that lies between this functions two arguments If you didn t know that this type and these operations were not built in to Resolve C you could not tell by looking at the code that uses them You reason about the behavior of the client program in precisely the same way too Objects of user defined types are in every important sense first class citizens with the same status as objects of the built in types This property means there is uniformity and consistency of client code even in very large applications with many user defined types 1 3 Anatomy of a Component Family Random From a client programmer s perspective you are most interested in the abstract instance es that explain each concrete instance used in your program the interface contract that you need in order to use a component This section focuses on the off the shelf component Random Uniform Generator I used in Monte Carlo as an example to illustrate the structure and meanings of the abstract component s that specify the functionality of this concrete component Other than its name there is no need for you as a client programmer to know anything more than this about the concrete instance that is included The Resolve C discipline advises that you explain the behavior of a possibly complex concrete instance by dividing the overall abstract description into bite sized abstract instances The main abstract instance specifies a new user defined kernel
152. non empty Notice that this operation does not have functional deterministic behavior i e even if it is called twice with exactly the same value of s it might return with different results since it is permitted to remove any element from s This is illustrated in the tracing table below Sample Traces Statement Object Values sl 6 92 13 18 i 379 ee ee a a 379 en sl 6 13 18 i 92 SET CLIENT VIEW SET 7 Is Member Formal Contract Specification function Boolean Is Member preserves Item amp x is abstract ZEI ensures Is Member x is in self TEX Informal Description A call to the Is Member operation has the form of an expression s1 Is Member 1 This operation returns a Boolean value which is true iff an element with value i is in set sl Sample Traces Statement Object Values b sl Is Member i b sl Is Member 92 SET 8 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Size Formal Contract Specification function Integer Size is abstract ensures Size self 1 Informal Description A call to the Size operation has the form of an expression STLSTES 0 ii This operation returns an Integer value which is the size of cardinality of or number of elements in set s i e IsJI Sample Traces Statement Object Values 3 18 Sorting_Machine Motivation Applicability and Indications for Use One of the
153. nstance that it extends All other components that a concrete instance depends on are automatically brought into scope by transitivity making component inclusion in a client program easy to manage In a client program that uses a typical concrete instance the name of that concrete instance a class in C is also the name of a type As a client programmer you may declare objects of that type and may invoke on them any operations in the abstract instance s that are implemented subject of course to the interface contracts specified for those operations Once a concrete instance is brought into scope with its include statement the new type is available to be used just like any built in type of Resolve C 18 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 2 Abstract and Concrete Templates Generalization Most existing software has been designed with software components that are in the Resolve C taxonomy abstract or concrete instances Yet there are significant advantages to designing software components that are abstract and concrete templates Templates serve two distinct purposes e to generalize components that otherwise would be too special purpose for widespread use in different application programs and e to decouple dependencies between components This chapter and the next build upon Chapter 1 by showing you how to use these two slightly more advanced but very powerful software component engineering techniqu
154. nstraint for all i integer there exists x Item i x is in a iff lower lt i lt upper Lay standard abstract operations Static Array Kernel PE Static Array Kernel is modeled by STATIC ARRAY MODEL initialization ensures self i integer x Item where lower lt i lt upper and is initial x 1 x IR Informal Description The model for Static_Array_Kernel is a finite set of ordered pairs of type integer tem that contains exactly one pair for each integer within the interval from lower to upper inclusive These bounds are template parameters that are just ordinary integer constants once Static_Array_Kernel is instantiated Like all Resolve C types Static_Array_Kernel comes with operator amp and Clear Note The sample traces for this and the other operation descriptions refer to the type Static_Array_Of_Text which is the result of the following instantiation concrete instance class Static Array Of Text instantiates Static Array Kernel 1 C lt Text 7 9 gt ih STATIC_ARRAY 4 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Sample Traces Statement Object Values A STATIC_ARRAY CLIENT VIEW STATIC_ARRAY 5 Accessor Formal Contract Specification function Items operator preserves Integer i is abstract requires lower lt i lt upper ensures i self i is in self 1 Informal Description Note This and the other operation
155. nt where that object is declared The purpose of the constructor is to create the representation of the object and to give it an initial value in this example 0 As a client you don t need to know anything about the constructor except the initial value 1t gives each newly declared object of the type which is specified in the formal comment that follows standard_ abstract_operations e A destructor which is an operation that is called automatically for each object of this type without the client writing an explicit call when execution leaves the block in which that object is declared The purpose of the destructor operation is to destroy a better description would be reclaim the representation of the object What does this mean Asa client programmer you have no need to know this You do not explicitly call the destructor anyway and in general the details of what it does and how are of interest only to implementers e A swap operation which exchanges the values of any two objects of this type using the operator amp e A Clear operation that resets the receiver object s value to an initial value for this type The formal comment that follows says that this new kernel type is modeled by the mathematical subtype RANDOM_MODEL as defined above and that every new object of this type has the initial value O when the object is declared Notice a very important point the name of the type described here is the name of
156. nts e g a2 but none of the other arguments may be a or may involve an accessor expression for al because this would violate the repeated argument rule So while you might be tempted to write something like allil amp alli2 this statement violates the repeated argument rule Be aware that the C compiler will not report this as an error You need to avoid the pitfall by personal discipline STATIC_ARRAY 6 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Sample Traces Statement Object Values 7 abcd 8 XYZ 9 bucks 7 abcd 8 go 9 bucks il bryg Habea E 9 bucks il t XYZ 7 abcd 8 g0 9 bucks 7 8 cd 9 rom 7 abcd 8 rom 9 bucks 7 8 cd 9 go STATIC_ARRAY CLIENT VIEW STATIC_ARRAY 7 Lower_Bound Formal Contract Specification function Integer Lower Bound is abstract ee ensures Lower Bound lower ER Informal Description A call to the Lower_Bound operation has the form of an expression al Lower Bound This operation returns an Integer value which is the lower bound on the interval of legal indices into al i e lower Sample Traces Statement Statement A o o o l Values 1 7 abcd Po ed a abed 8 g0 go 9 bucks 7 abcd 8 go 9 bucks STATIC_ARRAY 8 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2
157. o two things in order to use the selected concrete template e Bring the desired concrete template into scope in the application program e Instantiate it to create a concrete instance 2 2 1 Bringing a Concrete Template Into Scope Let s continue with the Poly Eval example to see exactly how this works The appendix for the Sequence family lists just one implementation of Sequence Kernel which is called Sequence_Kernel_la_C so there isn t much choice here The appendix explains To bring this component into scope you write include CT Sequence Kernel la C h Hence you see this exact statement in the global context section near the beginning of Figure 2 2 In fact there are other implementations of Sequence Kernel in the Resolve C Catalog but we ignore them here and in the appendix in order to concentrate on how to use a chosen concrete template CHAPTER 2 ABSTRACT AND CONCRETE TEMPLATES GENERALIZATION 31 The other component brought into scope at this point in the code is a Timer component a concrete instance that lets you time the execution of any code fragment Its use is illustrated by this program but is not further discussed here The name CT Sequence Kernel_la_C h derives from the following features as introduced in Chapter 1 e CT means this component is a concrete template e Sequence means it is in the Sequence component family e Kernel_la_C means it is implementation
158. odel are fieldO through field2 Upon declaration an object of this type has a value in which all its fields have initial values for their respective types Like all Resolve C types Record_Kernel comes with operator amp and Clear The discussion and sample traces for this and the other operation descriptions refer to the type Full_Name which is the result of the following instantiation and field name declarations repeated from the example above concrete instance class Full Name instantiates Record lt Text Text Text ERZ field name Full_Name 0 Text first_name field name Full_Name 1 Text middle name field name Full Name 2 Text last name RECORD 6 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 object Full Name nl n2 object Character c object Text t The names of the fields are declared separately from the instantiation of the template Typically these declarations appear immediately following the instantiation but are needed only if the fields are to be accessed there This might not be so in all cases for example a Record instantiation might be needed to create a concrete instance to pass as a template parameter in another instantiation Perhaps the fields of objects of this type will be accessed only in the second template in which case the field names should only be declared there The declaration of a field name is not a call to an operation though it looks l
159. oint is that merely saying that a complex number is represented by using two Real objects does not pin things down enough A client programmer must know which representational scheme is being used by which operations and if different representations are used for different operations in the subroutine library then the client programmer must convert manually between them In short this is a mess If you could view an object whose value is a complex number as a unit as a single object with an abstract state described in terms of the mathematical theory of complex numbers then you wouldn t need to be concerned with such issues 1 1 2 User Defined Types The problem outlined above suggests that a subroutine library might not be the best way of organizing off the shelf software components Even if it works well enough in limited application domains focusing on individual operations generally is not the right way to think about software components Experienced software engineers have recognized for decades the need for a richer set of types than what is built in to most programming languages No fixed set of types however large or sophisticated can possibly be just what it takes to develop application programs that no one has ever thought of before The requisite level of generality can only be obtained if a software engineer can design and implement new types and associated operations that fit the situation at hand when that is appropriate Such
160. omponent it extends but other operations from the extension as seen here in the body of Uniform_Integer Figure 3 16 shows the CCD for Random_Uniform_1 This pattern of organizing component dependencies is the primary technique for adding functionality to a component family It works equally well when the components involved also use templates for generalization 66 SOFTWARE COMPONENT ENGINEERING VOLUME 2 Random_ Uniform Random_ Kernel extends implements implements Random_ extends Uniform_1 Figure 3 16 CCD for a typical layered extension 3 3 2 Instantiating a Concrete Extension As a client programmer instantiating a concrete extension is nothing new you simply bring into scope the component s you need and then instantiate them In this case you need only Random_Uniform_1 and some implementation of Random_Kernel It happens that Random Kernel I is available it is a template itself but happens to have no template parameters Here is how you might instantiate Random Kernel 1 and Random Uniform I to create a concrete instance class in your client code concrete instance class Random Uniform Generator instantiates Random Uniform 1 lt Random Kernel 1 lt gt gt O Note the formatting of the nested template instantiation with the space between the gt characters It also is possible to make this concrete instance a component in a catalog as shown in Figure 3 17 You simply incl
161. ondition i e its interface contract specification has a requires clause that is not necessarily true at the time of a call Objects of the built in type Integer are limited to a fairly large but practically speaking far from unlimited range of values about 2 billion to 2 billion There are many situations where you need only non negative integer valued objects but where two billion or so is not the largest value ever encountered For example the amount of an electronic bank transaction in U S currency might be recorded in an Integer object the number of cents being transferred But then a figure like the U S national debt or even a plausible inter bank electronic fund transfer is too large to handle with an Integer object A family of components in the Resolve C Catalog is available to help you in this situation The central abstract component for this family is Natural_Kernel There are four kernel operations to manipulate a Natural_Kernel object through the digits of its radix representation as explained in the client view appendix for the Natural family Several additional operations are offered through extensions to provide more directly useful operations to do addition subtraction multiplication etc Figure 3 5 shows the interface contract specification of Natural_Kernel Ih fre So SES oo SS DRS Se SSeS sonne HE omas nenne EN fy Abstract Instance Natural Kernel PD MERE HSS ae Sees Se ee ee A EEE eee en Ke ifndef A
162. ons below e Enqueue e Dequeue e Accessor e Length Concrete Components e Queue Kernel la C This is a checking implementation of Queue Kernel in which the execution time for each of the operations constructor Enqueue Dequeue the accessor and Length is constant while the execution time for the destructor is proportional to the length of the string All objects of this type have the interface of Queue_Kernel with the concrete template name Queue_Kernel_la_C substituted for the abstract template name Queue_Kernel To bring this component into the context you write include CT Queue Kernel la C h QUEUE 2 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Component Coupling Diagram implements Queue_ Kernel_1a_C QUEUE CLIENT VIEW QUEUE 3 Descriptions Queue_Kernel Type and Standard Operations Formal Contract Specification standard abstract operations Queue Kernel Queue Kernel is modeled by string of Item initialization ensures self empty string Tay Informal Description The model for Queue_Kernel is a string of items which is initially empty A Queue_Kernel object may be arbitrarily large Like all Resolve C types Queue_Kernel comes with operator amp and Clear Note The sample traces for this and the other operation descriptions refer to the type Queue_Of_Integer which is the result of the following instantiation concrete_instance class Queue_Of Integer instantiates Q
163. ons with a violated precondition then your program will immediately stop and report the violation To bring this component into the context you write include CI Natural 1_C h Natural_1 This is a non checking implementation of the abstract instance Natural_Kernel so it is not very powerful you probably want Natural Number I instead It is a concrete instance i e you may declare objects of type Natural_1 To bring this component into the context you write include CI Natural 1 h Natural_Number_1_C This is a checking implementation of the abstract instance Natural_Number It is a concrete instance i e you may declare objects of type Natural_Number_1_C Natural_Number_1_C is a checking component which means that it checks the preconditions of its operations So if you call any of the Natural_Number_1_C operations with a violated precondition then your program will immediately stop and report the violation To bring this component into the context you write include CI Natural Number 1 C h Natural_Number_1 This is a non checking implementation of the abstract instance Natural Number It is a concrete instance i e you may declare objects of type Natural_Number_1 To bring this component into the context you write include CI Natural Number 1 h Note In all of the above concrete components the implementation supplied value of the constant RADIX is 10 NATURAL CLIENT VIEW NATURAL 3 Component Coupling Di
164. orm The more complex CCD shows additional structure that explains how it implements Random Uniform it is an instance of a template Random Uniform I that implements Random Uniform and it happens to use Random_Kernel_1 for the Random_Kernel operations Random_ Uniform Random_ Kernel extends implements implements implements Random_ Random_ Kernel_1 extends Uniform_1 Random_ Uniform_ Generator_1 Figure 3 18 CCD for Random_Uniform_Generator_1 68 SOFTWARE COMPONENT ENGINEERING VOLUME 2 To summarize using the same technique that decouples a checking component from the component it checks you can decouple a concrete extension from the component it extends 3 4 Summary Generalizing collection components to work with arbitrary entry types is the most obvious use for abstract and concrete templates Yet it is arguably not the most important one That honor goes to decoupling concrete to concrete dependencies Introducing concrete to concrete dependencies in code is as easy as falling off a log but it leads to software that is needlessly difficult to understand and to change A disciplined software component designer can avoid concrete to concrete dependencies by observing the following principles e Limited Dependence Rule Design each component so it depends on as few other components as possible e Least Information Rule Design each component so it depends only on components that
165. ou may consider to be in that particular pair in al table This means that not only may you use the expression a il as a value of type Item you may even change the value of the object called a 11 but remember that this also changes the value of al The sample traces help illustrate some important points regarding the convenience and danger of accessor expressions The first and second sample statements show how an accessor expression such as al il acts like an object of type Item whose value may be changed depending on the statement in which the expression occurs The third sample statement s call to the swap operator involves other arguments e g a2 but none of the other arguments may be a or may involve an accessor expression for al because this would violate the repeated argument rule So while you might be tempted to write something like al i1 amp alli2 this statement violates the repeated argument rule Be aware that the C compiler will not report this as an error You need to avoid the pitfall by personal discipline ARRAY CLIENT VIEW Sample Traces ARRAY 7 Statement Object Values 7 abcd 8 XYZ 9 bucks 7 abcd 8 go 9 bucks il 8 t XYZ 7 abcd 8 XYZ 9 bucks il 8 t XYZ 7 10 7 10 9 Tabea ad 9 bucks 11 LO hy red 9 7 abcd 8 cd 9 bucks il Ogee ger
166. pe parameter the type of entries for a string or set the domain and range types for a function the types of the fields of a tuple Templates in this case address the following problem Suppose you have a component that dictates a specific type for a collection s entries and you want to make it more general so it allows the collection s entries to be any type If all you have are abstract and concrete instances then there is an obvious way to do this copy and paste code from the instance you have and make routine replacements in it with a text editor Unfortunately copying and pasting code has severe disadvantages The most important is the loss of single point of control over change If CHAPTER 2 ABSTRACT AND CONCRETE TEMPLATES GENERALIZATION you ever need to change a piece of code that has been copied and pasted you have to find all the places where it has been propagated and change it there too The advantage of using templates rather than copy paste is that the template becomes that single point of control over change Instances generated by instantiating the template i e by fixing the template s parameters are not created manually by a software engineer wielding a text editor but rather by the C compiler Instantiation of a template by a client programmer involves a simple statement that looks similar to an operation call However fixing a template s parameters happens at compile time not execution time as with an op
167. pe the code that implements the operations defined by the concrete instance called Random Uniform Generator 1 As a class name Random Uniform Generator I is also the name of the type defined by this concrete component so this type name is now in scope Furthermore the names of all the operations provided by this concrete component are in scope This means that you may now declare objects of type Random Uniform Generator I and may call the operations provided by concrete instance Random Uniform Generator I Why do you bring into scope the concrete component as opposed to the abstract component that it implements For human consumption you could include just the abstract component that provides the cover story 1 e the interface contract specification But you always need to include the concrete component if you plan to declare objects of the provided type and call provided operations because the compiler needs this information in order to generate executable program code 8 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 In principle a concrete instance could be stored in a cpp C separately compiled file which could be compiled once into an object code library that is to be linked with your separately compiled application program This would save a little compilation time in client programs that use the component In practice however almost all Resolve C components are templates rather than instances and h
168. perations Partial Map Kernel Partial Map Kernel is modeled by PARTIAL FUNCTION initialization ensures self empty set Lag Informal Description The model for Partial_Map_Kernel is a finite set of ordered pairs of type D_Item R_Item which is initially empty A Partial_Map_Kernel object may be arbitrarily large Like all Resolve C types Partial_Map_Kernel comes with operator amp and Clear Note The sample traces for this and the other operation descriptions refer to the type Partial_Map_Instance which is the result of the following instantiation concrete instance class Partial Map Instance instantiates Partial Map Kernel 1 C lt Text Integer gt O PARTIAL_MAP 4 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Sample Traces Statement Object Values AAA PARTIAL_MAP CLIENT VIEW PARTIAL_MAP 5 Define Formal Contract Specification procedure Define consumes D Items d consumes R Item amp r is abstract rl requires not IS DEFINED IN self d ensures self self union d r LEY Informal Description Note This and the other operation descriptions refer to these objects in examples object Partial Map Instance ml m2 object Text tl t2 object Integer 1 object Boolean b A call to the Define operation has the form ml Define tl 1 This operation adds the pair whose value is tZ i to the set ml You may make this call only if ml does not already conta
169. programmer or operation implementer is responsible for establishing that the precondition of the operation holds at the time of the call 1 Neither is responsible 2 Both are responsible 3 Operation implementer is responsible 4 Client programmer is responsible It is easy to dispense with answers 1 and 2 If an operation has a non trivial precondition that is not satisfied at the time of the call then by definition of the interface contract the operation is permitted to do anything If no one is responsible for seeing to it that this condition holds then the operation can among other things legitimately e Do nothing more but quietly return to the calling program without doing anything else e Continue computing with garbage data and produce any answers it likes e Halt the program without further report or further incident Emit an error message Fire a missile toward Michigan As the caller of the operation you cannot predict which if any of these or many other possibilities will ensue So the only reason a rational client programmer would not worry about whether the precondition holds is that he she thinks the operation implementer has written code to check it and to do something tame in response to a violation And the only reason a rational operation implementer would not check the precondition is that he she thinks the client programmer will check it If there is no policy that establishes who is responsible th
170. quence_Reverse you need to understand Sequence_Kernel Why The specification of the mathematical model for sequence objects is there The interface contract for the Reverse operation in Figure 2 4 makes no sense unless you know that self is a string of Items 2 3 3 Using a Concrete Component As a client of the off the shelf concrete component used in the Poly_Eval program all you need to know about it is summarized in the CCD in Figure 2 6 The name of the concrete instance is Sequence_Kernel_la_C and it implements Sequence_Kernel The interface contract specification in the latter component explains how Sequence_Kernel_la_C objects will behave in the client program the possible values those objects can have and the operations that you can call on them That s it As a client you do not need to see the code for Sequence_Kernel_la_C Sequence_ Kernel implements Sequence_ Kernel_ 1a_C Figure 2 6 The implements relation may hold between a concrete and abstract template 2 4 Summary Abstract and concrete templates are parameterized software components that you can instantiate to create abstract and concrete instances respectively One important use of templates is to generalize component designs This is typically done with a collection component i e one that introduces a user defined type whose mathematical model involves strings sets functions and or tuples In each of these mathematical theories there is at least one ty
171. r Partial_Map and in many other situations where the problem at hand has the distinctive recursive structure of divide and conquer algorithms The mathematics used to model trees requires some explanation Figure 1 shows a tree called T The root of T is d the item also called a node at the top of the tree d has two children where a is the left child and k is the right child Similarly a has only a left child h and h has only a right child g while k has two children with s being the left child and r the right Since g s x and y have no children they are called the leaves of T All other items in T are interior items FANS SSN a Figure 1 A binary tree T Continuing the family tree metaphor that gives rise to some but as you can see not all of the terms here k is the parent of both s and t and s and t are siblings Tis a binary tree since every item in T has at most two children that is every item has 0 1 or 2 children The string of items lt g 5 x y gt is the frontier or yield of T the string of leaves of T from left to right There are several subtrees of T Some of these are pictured in Figure 2 iy Wr S lt Figure 2 Some subtrees of T Binary trees have a particular structure or composition Specifically every binary tree except for the empty binary tree see below consists of a root item together with two subtrees called the left subtree and right subtree The tree T consists of the root item d an
172. ract Components e Sequence Kernel the programming type of interest with the operations below e Add e Remove e Accessor Length Concrete Components e Sequence Kernel la C This is a checking implementation of Sequence Kernel in which the execution time for each of the operations constructor and Length is constant the execution time each of the operations Add Remove and the accessor is proportional to the position being indexed and the execution time for the destructor is proportional to the length of the string All objects of this type have the interface of Sequence_Kernel with the concrete template name Sequence_Kernel_la_C substituted for the abstract template name Sequence_Kernel To bring this component into the context you write include CT Sequence Kernel la C h SEQUENCE 2 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Component Coupling Diagram Sequence_ Kernel implements Sequence_ Kernel_1a_C SEQUENCE CLIENT VIEW SEQUENCE 3 Descriptions Sequence_Kernel Type and Standard Operations Formal Contract Specification standard abstract operations Sequence Kernel Sequence Kernel is modeled by string of Item initialization ensures self empty string AL Informal Description The model for Sequence_Kernel is a string of items which is initially empty A Sequence_Kernel object may be arbitrarily long Like all Resolve C types Sequence Kernel comes with ope
173. ract or concrete instance or template e The subdirectory called AI contains components that are abstract instances e The subdirectory called CI contains components that are concrete instances e The subdirectory called AT contains components that are abstract templatees e The subdirectory called CT contains components that are concrete templatees e Within the component kind directory a component file resides in a subdirectory whose name is that of a component family i e a set of logically related components For example for a component defining a new programming type for complex number objects this subdirectory name probably would be Complex All the components in the directory would deal with such objects and their class names would begin with the prefix Complex_ e Within the component family directory an individual component file has a name that is the remainder of the class name 1 e whatever comes after the component family name and the underscore separator and a h extension For example the abstract instance that defines a programming type for complex number objects along with the most important operations for such objects probably would be called Complex_Kernel As an abstract instance it would be in the component file Al Complex Kernel h One possible concrete instance that implements Complex_Kernel might be called Complex_Kernel_1 for implementation 1 of Complex_Kernel If so it would be
174. rate some important points regarding the convenience and danger of accessor expressions The first and second sample statements show how an accessor expression such as q1 current acts like an object of type Item whose value may be changed depending on the statement in which the expression occurs The third sample statement shows that q 1 current may appear as an argument in a call where an tem is required This call involves other arguments e g q2 but none of the other arguments may be q or may involve an accessor expression for q because this would violate the repeated argument rule So while you might be tempted to write something like ql Enqueue ql current this statement violates the repeated argument rule Be aware that the C compiler will not report this as an error You need to avoid the pitfall by personal discipline The last statement in the tracing table also illustrates that an accessor expression acts exactly like an object of type Item Notice that q1 current which is being enqueued onto q2 in this statement is consumed its new value is O since tem is Integer here because Enqueue consumes its argument So this statement changes both q1 and q2 QUEUE CLIENT VIEW QUEUE 7 Sample Traces Statement Object Values ql lt 92 6 18 gt i 37 ql lt 37 6 18 gt i 92 al current i AAA ql lt 92 6 18 gt i 92 lt A A 295 76 57 lt M6 DLL 345 255 6 gt lt 16
175. rator amp and Clear Note The sample traces for this and the other operation descriptions refer to the type Sequence_Of_Integer which is the result of the following instantiation concrete instance class Sequence Of Integer instantiates Sequence Kernel 1 C lt Integer gt th Sample Traces Statement Object Values A TAR SEQUENCE 4 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Add Formal Contract Specification procedure Add preserves Integer pos consumes Item amp x is_abstract requires 0 lt pos lt self ensures there exists a b string of Item lal pos and self a b and self a lt x gt b 1x Informal Description Note This and the other operation descriptions refer to these objects in examples object Sequence Of Integer sl s2 object Integer i n A call to the Add operation has the form sl Add i n This operation adds n in position i of string s i e in a position such that the number of items before the newly added one is equal to i Notice that the value of n is consumed so afterward n 0 You may make this call only if 0 lt i lt IsIl You can see from this example that the numbering of positions in the string s effectively starts at O For instance to add n at the beginning of s i e as the leftmost item of s you might write sl Add 0 n SEQUENCE CLIENT VIEW SEQUENCE 5 Sample Traces Statement Object Values
176. ree Ise Informal Description Note This and the other operation descriptions refer to these objects in examples object Binary Tree Of Integer tl t2 t3 t4 object Integer i A call to the Compose operation has the form t1 Compose i t2 t3 This operation produces as the value of a binary tree whose root value is i and whose left and right subtree values are 12 and 13 BINARY_TREE CLIENT VIEW BINARY_TREE 7 Sample Traces Statement Object Values t1 Compose i t2 t3 t1 Compose i t2 t3 BINARY_TREE 8 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 NN t1 Compose i t2 t3 BINARY_TREE CLIENT VIEW BINARY_TREE 9 Decompose Formal Contract Specification procedure Decompose produces Item amp x produces Binary Tree Kernel amp left_subtree produces Binary Tree Kernel amp right subtree is abstract consumes self requires self empty tree ensures self compose x left subtree right subtree Las Informal Description A call to the Decompose operation has the form t1 Decompose i t2 t3 This operation breaks into three pieces the root whose value it returns in i and the left and right subtrees whose values it returns in f2 and 13 respectively You may make this call only if tl is not empty BINARY_TREE 10 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Sample Traces Statement Object Values t1 Decompose i t2 t3
177. rent but remember that this also changes the value of rl The sample traces help illustrate some important points regarding the convenience and danger of accessor expressions The first and second sample statements show how an accessor expression such as t current acts like an object of type Item whose value may be changed depending on the statement in which the expression occurs The third sample statement shows that tI current may appear as an argument in a call where an tem is required This call involves other arguments e g t2 but none of the other arguments may be or may involve an accessor expression for t because this would violate the repeated argument rule So while you might be tempted to write something like t1 Compose t2 current t2 t3 this statement violates the repeated argument rule Be aware that the C compiler will not report this as an error You need to avoid the pitfall by personal discipline The last statement in the tracing table also illustrates that an accessor expression acts exactly like an object of type Item Notice that t current which is being composed as the new root of t2 in this statement is consumed its new value is O since tem is Integer here because Compose consumes its arguments So this statement changes both r and 12 BINARY_TREE 12 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Sample Traces Statement Statement bject Vales object Values current
178. rmal Contract Specification procedure Copy To produces Natural Numbers n is abstract Zr preserves self ensures n self 1 Informal Description A call to the Copy_To operation has the form nl Copy_ To n2 This operation copies n to n2 Note There is no assignment operator for Natural_Number objects but the same effect can be accomplished using Copy_To Sample Traces Statement Object Values nl 45142398 n2 1996 n1 Copy_To m2 AAA nl 45142398 n2 45142398 NATURAL CLIENT VIEW NATURAL 19 Get_From gt gt Formal Contract Specification math operation IS DIGIT c character boolean is c is in AS CAE gS Pi BAT SEHE EST SITE ESTER math subtype DIGIT is character exemplar d constraint IS DIGIT d math operation IS DIGITS s string of character boolean satisfies if s empty string then IS DIGITS s true else there exists a string of character c character s a lt c gt and IS DIGITS s IS DIGITS a and IS _ DIGIT c math operation INTEGER VAL s string of DIGIT NATURAL MODEL satisfies if s empty string then INTEGER VAL s 0 else there exists a string of DIGIT d DIGIT s a lt d gt and INTEGER VAL s 10 INTEGER VAL a TO INTEGER d TO INTEGER 0 math operation IS SPACES AND TABS s string of character boolean is elements s is subset of t math operation IS AN INPUT REP
179. rovide for Item For example Sequence_Reverse lt Integer gt extends Sequence_Kernel lt Integer gt Sequence_Reverse lt Random_Uniform_1 gt extends Sequence_Kernel lt Random_Uniform_1 gt and so on In the postcondition for program operation Reverse the built in mathematical function reverse denotes the string obtained by considering the entries in the string to be in the opposite order For example with strings of integers the following is true reverse lt 1 2 3 gt lt 3 2 1 gt Figure 2 5 shows how to depict in a CCD the fact that the extends relation holds between these two abstract templates The difference between this CCD and its counterpart in Chapter 1 is that the rounded corner rectangles standing for the two abstract templates have heavy borders This is a visual cue used in CCD s to indicate that components are templates rather than instances Sequence_ Kernel Sequence_ Reverse extends Figure 2 5 The extends relation may hold between two abstract templates This CCD raises a second subtle issue Both Sequence Kernel and Sequence Reverse have template parameters If a component uses another component that is not built in then this relationship should be shown in the CCD Why then is there nothing in the CCD to indicate that each of these components uses this other type called Item Shouldn t there be another box in the diagram to stand for Item because the type a client binds to tem might not be b
180. s 1 idl 17 namel don t care tl Remove Any Pair idl namel tl 8 San Francisco 2 Columbus idl 3 namel Santa Fe 3 Santa Fe 8 San Francisco 2 Columbus idl 17 namel don t care tl Remove Any Pair idl namel 3 Santa Fe 8 San Francisco idl 2 namel Columbus ID_NAME_TABLE 10 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Look Up Name Via Id Formal Contract Specification procedure Look Up Name Via Id preserves Integer id produces Text amp name is abstract Frl preserves self requires ID IS DEFINED IN self id ensures id name is in self 1 Informal Description A call to the Look_Up_Name_Via_ld operation has the form t1 Look Up Name Via Id idl namel This operation finds the pair in with id component id and returns a copy of the name associated with id as the value of namel You may make this call only if there is a pair in whose id component equals id ID_NAME_TABLE CLIENT VIEW ID_NAME_TABLE 11 Sample Traces Statement Object Values 3 Santa Fe 8 San Francisco 2 Columbus idl 2 namel don t care t1 Look Up Name Via Id idl namel 3 Santa Fe 8 San Francisco 2 Columbus idl 2 namel Columbus 3 Santa Fe 8 San Francisco 2 Columbus namel who cares 8 San Francisco 2
181. s Statement Object Values ATAR LisT 4 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Move_To_Start Formal Contract Specification procedure Move To Start is abstract fed ensures self empty string self left self right Lae Informal Description Note This and the other operation descriptions refer to these objects in examples object List Of Integer sl s2 object Integer i A call to the Move_To_Start operation has the form sl Move To Start This operation moves the fence to the start left end of s but does not otherwise affect the items of sl The left end is called the start of a List object because ordinarily sequential processing of the items proceeds from left to right using the Advance operation see below The Move_To_Start operation takes you directly to the start by skipping backward over all items in s left thereby preparing for a typical sequential processing activity Sample Traces Statement Object Values LIST CLIENT VIEW LisT 5 Move_To_Finish Formal Contract Specification procedure Move To Finish is abstract ZN ensures self self left self right empty_string 1 Informal Description A call to the Move_To_Finish operation has the form s1 Move To Finish This operation moves the fence to the finish right end of s but does not otherwise affect the items of sl The right end is called the finish of a List
182. s also called fields of a Record object By using these field names with accessor operations you can directly manipulate the fields of a Record object In fact this is the only way to manipulate the sub objects The mathematical model of a Record then 1s just a tuple whose members are the Record fields Let s consider an example Suppose you want to keep track of the following information for each employee of a company first name middle name last name address and salary For some purposes you want all the information about a particular employee to stay together e g perhaps you want a Sequence whose Items are this Record type or you want this Record type to be the R Item in a Partial_Map with the employee s ID number as the D Item For other purposes you want to be able to get to the individual pieces of information about a particular employee e g perhaps you want to give the employee a raise There are several different ways to use Record to do this Here are two approaches e You might instantiate the concrete_template class Record with five fields of the types Text Text Text Text and Integer calling the resulting concrete instance Employee Then you might declare Employee s field names to be first_name middle_name last_name address and salary respectively Schematically you could view as follows an object of this type that contains information about John Q Doe an employee who lives at 123 Easy Street and makes 8
183. s string of character n NATURAL NUMBER boolean is there exists sl s2 s3 string of character c character s sl s2 s3 in and IS SPACES AND TABS s1 and IS DIGITS s2 and n INTEGER VAL s2 and IS SPACES AND TABS s3 LAS procedure Get From NATURAL 20 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 alters Character IStream str is abstract Jal produces self requires str is open true and there exists x NATURAL MODEL s string of character s is prefix of str content and IS AN INPUT REP s x ensures str is open true and str ext_name str ext_name and there exists s string of character str content s str content and IS AN INPUT REP s self Ley Informal Description A call to the Get_From operation has the form nl Get_ From input This operation reads n from the input stream input It alters input by reading and passing all characters up to and including the next newline n character Before this newline must be only blanks or tabs t followed by at decimal digits 0 1 9 followed by only blanks or tabs The digits denote the value of n in the usual manner of writing decimal numbers regardless of the value of RADIX see Multiply_By_Radix above with the additional provision that an empty string of digits is read as 0 You may make this call only if input is open and if its content has a prefix that satisfies this requirement
184. s you decide up front on the required size and bounds and then you access and update table entries whose indices remained fixed throughout The Sequence is always indexed starting with 0 The Array object may be set up to be indexed starting with any Integer value Related Components e Sequence atype that is similar to Array except that it is incrementally resizable and that it is always indexed from 0 e Static Array a type that is essentially identical to Array except that the index bounds are fixed not at run time but at template instantiation time Component Family Members Abstract Components e Array_Kernel the programming type of interest with the operations below e Set Bounds e Accessor e Lower Bound ARRAY 2 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 e Upper Bound Concrete Components e Array Kernel I C This is a checking implementation of Array_Kernel in which the execution time for each of the operations constructor the accessor Lower Bound and Upper Bound is constant the execution time for the destructor is proportional to the length of the interval between the upper and lower bounds and the execution time for Set Bounds is proportional to the sum of the length of the interval between the current upper and lower bounds and the length of the interval between the new lower and upper bounds All objects of this type have the interface of Array_Kernel with the concrete template name Arra
185. s as an instance of concrete_template class Record in much the same fashion as Full_Name above On the other hand suppose you also wanted to keep track of each employee s birthdate This suggests another concrete instance Date which also would be generally useful outside this application The mathematical model of Date probably should be a three tuple of integers with some constraints on the values of the fields However Date should not simply be a Record instance because there also are mutual constraints on the values of the fields That is the day must be between 1 and 31 inclusive if the month is 1 but between 1 and 28 inclusive if the month is 2 except if the year is a leap year in which case 1 through 29 is allowed and so on The complication introduced by such a constraint is a clue that it is inappropriate to treat a date as merely three independent numbers which are placed together for convenience which is how you d be treating it if you made Date an instance of Record You can guess from the above description that Record is an unusual template component in the sense that different instantiations of it involve different numbers of template parameters Indeed this is so here are the Resolve C statements that declare the concrete instances and their field names for two approaches above First approach flat record concrete instance class Employee instantiates RECORD CLIENT VIEW RECORD 3 Record lt Text
186. s code Starting at the end the fully qualified name for the accessor is a bit strange Technically operator is the name of the accessor operation but C offers special concise syntax for normal use i e s pos rather than s operator pos The special syntax is not available with the fully qualified name Second the restriction in the formal parameter list on Sequence_Base the implementation of Sequence_Kernel to be checked indicates that the type Item must be the same when Sequence_Kernel_C is instantiated as it is when the implementation to be checked is instantiated Suppose you need sequences of integers and you want the operations on them to be checked Following an analogous approach as with Natural_Kernel_1_C in Section 3 2 5 you can create two instances in the client program concrete instance class Sequence Of Integer Base instantiates Sequence Kernel la lt Integer gt 137 concrete instance class Sequence Of Integer instantiates Sequence Kernel C lt Integer Sequence Of Integer Base gt he The name of the first concrete intance is immaterial because it is used only as an actual parameter when creating the second instance In fact you could combine these two instantiations into one and not even bother to give a name to the concrete instance to be checked concrete instance class Sequence Of Integer instantiates Sequence Kernel C lt Integer Sequence Kernel la lt Integer gt gt
187. s means that not only may you use the expression m t as a value of type R Item you may even change the value of the object called m t but remember that this also changes the value of m The sample traces help illustrate some important points regarding the convenience and danger of accessor expressions The first and second sample statements show how an accessor expression such as m t acts like an object of type R Item whose value may be changed depending on the statement in which the expression occurs The third sample statement shows that m t1 may appear as an argument in a call where an R_ tem is required This call involves other arguments e g m2 but none of the other arguments may be m or may involve an accessor expression for ml because this would violate the repeated argument rule So while you might be tempted to write something like ml Define tl m1 t2 this statement violates the repeated argument rule Be aware that the C compiler will not report this as an error You need to avoid the pitfall by personal discipline The last statement in the tracing table also illustrates that an accessor expression acts exactly like an object of type R Item Notice that both t and m1 12 which are being Defined into m2 in this statement are consumed their new values are and 0 respectively because Define consumes its arguments So this statement changes both m and m2 This kind of complicated call is officially le
188. s_abstract requires 0 lt pos lt self ensures there exists a b string of integer lal pos and self a lt x gt b and self a b EEA y Copying and pasting code like this is generally bad for three reasons e It is tedious CHAPTER 2 ABSTRACT AND CONCRETE TEMPLATES GENERALIZATION 21 e It is easy to make a mistake with the editor and accidentally mess up parts of the code that you didn t intend to change even parts that you didn t think you touched Taking a text editor to code is a lot like taking a blowtorch to a steel I beam once you ve modified it all the good properties you ve established about it e g the correctness of the code or the strength of the I beam are suddenly in doubt and have to be established again Even if you do the modifications correctly the result is that you have multiple copies of essentially the same code If you need to change the common code later for any reason you have to make these changes in multiple places Software engineers know from experience that it is far better to have a single point of control over change a single place where each non trivial piece of code resides This way if you have to change it you know the change needs to occur only there In fact if there is only one fundamental principle of software engineering that you must know this is the one Fortunately you don t have to do all this manual copying and pasting Software components ca
189. serting false and self contents empty multiset ensures IS FIRST self contents x and self false self contents x TAL Informal Description A call to the Remove First operation has the form sl Remove First t This operation removes from s a first item in general this is not unique though it is in the example according to the ARE IN ORDER definition supplied by the utility class Item Are In Order and returns its value in t You may make this call only if sZ is not in insertion phase and is not empty Sample Traces Statement Object Values false ece cse abracadabra nn en SORTING_MACHINE 8 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Remove_Any Formal Contract Specification procedure Remove Any produces Item amp x is_abstract rl requires self contents empty multiset ensures x is in self contents and self self inserting self contents x EL Informal Description A call to the Remove_Any operation has the form s1 Remove Any t This operation removes from s some i e any arbitrary item and returns its value in 1 You may make this call only if s is not empty it doesn t matter whether s is in insertion phase or extraction phase Notice that this operation may remove a different item from s if called twice in identical states as illustrated in the sample tracing table Sample Traces Statement Object Values false ece cse
190. set of items This inductive definition is similar to the definition of binary trees The set of trees over set A or tree of A which is the type name you use when writing the mathematics of trees consists exactly of those trees that can be built up from the items in A by one or more applications of the compose function The compose function for trees takes as arguments a root item from A say x and a string of k trees of A say lt TI T2 Tk gt and produces a tree of A say T with x as the root of T and TI T2 Tk as the subtrees This is pictured in Figure 2 Figure 2 The tree T compose x lt T1 T2 Tk gt And here is the inductive definition of the set tree over set A TREE 2 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Base case If x in an element of A then compose x empty string is an element of trees over set A e Inductive case If x is an element of A and for all i 1 lt i lt k Ti is an element of trees over set A then compose x lt T1 T2 Tk gt is an element of trees over set A In addition to the type tree and the operation compose there are three other basic math operations you need to be familiar with They are size root and children Consider a tree T Then size T also denoted 171 is the number of items in 7 e g in Figure 1 size T 11 root T is the root item of T e g in Figure 2 root T x and children T is the string of trees that
191. sociated with each month by using that month s index an integer between 1 and 12 The most closely related component is Array which is nearly identical except in regard to when the index bounds are fixed Another closely related component is Sequence A Sequence object starts out as an empty string of Item values so if you want to use it as a table in the fashion mentioned above you have to add entries to it one by one until the table is populated with values A Static_Array object becomes populated with initial values of type Item as soon as you declare 1t With a Sequence object you can interleave operations that change the size of the Sequence with operations that access and update existing entries possibly deferring the decision to add more entries or to remove some however adding and removing changes the indices of some of the existing entries With the Static_Array object you can t change the bounds of the table you decide up front on the required size and bounds and then you access and update table entries whose indices remained fixed throughout The Sequence is always indexed starting with 0 The Static_Array object may be set up to be indexed starting with any Integer value Related Components e Array a type that is essentially identical to Static Array except that the index bounds are fixed not at template instantiation time but at run time e Sequence a type that is similar to Static_Array except that it is incrementall
192. st one e Sorting Machine a type that is similar to Stack except that when you remove an item it is not the last one that was put in but the next one in sorted order according to some ordering based on the values of the items Component Family Members Abstract Components e Stack Kernel the programming type of interest with the operations below e Push e Pop e Accessor Length Concrete Components e Stack Kernel la C This is a checking implementation of Stack_Kernel in which the execution time for each of the operations constructor Push Pop the accessor and Length is constant while the execution time for the destructor is proportional to the length of the string All objects of this type have the interface of Stack_Kernel with the concrete template name Stack_Kernel_la_C substituted for the abstract template name Stack_Kernel To bring this component into the context you write include CT Stack Kernel la C h STACK 2 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Component Coupling Diagram implements Stack_ Kernel_1a_C STACK CLIENT VIEW STACK 3 Descriptions Stack_Kernel Type and Standard Operations Formal Contract Specification standard abstract operations Stack Kernel LEN Stack Kernel is modeled by string of Item initialization ensures self empty string Lay Informal Description The model for Stack_Kernel is a string of items which is initially empty A Stack_
193. stant is by convention in Resolve C the kind of component AI CI AT or CT followed by the class name in all upper case characters this makes it unique The first time the file is included somewhere this constant is not yet defined so the compiler includes the rest of the file through the matching endif The directive just after the ifndef i e define defines the constant to have the value 1 but this value is immaterial So each subsequent time the file is included during this compilation the constant AL RANDOM_KERNEL already has a defined value and the compiler ignores everything from ifndef through the matching endif This trick CHAPTER 1 ABSTRACT AND CONCRETE INSTANCES 11 makes sure that each included component is really included and compiled exactly once even if 1t is apparently included in many different places The next section of a typical Resolve C file is the global context section which brings into scope any other components that this one directly depends on Here this section is absent as it 1s for a typical abstract component that describes a kernel type The abstract instances discussed later in this section describe additional operations and these always include other components the ones they directly depend on in their global context sections By the way you might be wondering why RESOLVE_Foundation h is not included here You could include it without causing any trouble because it is prot
194. stract PET preserves self requires str is open true ensures str is open true and str ext_name str ext_name and str content str content OUTPUT REP self IZ Informal Description A call to the Put_To operation has the form nl Put_To output This operation writes the decimal representation of n1 to the file or text output stream output decimal regardless of the value of RADIX see Multiply_By_Radix above It alters output only by appending to it all the characters decimal digits of the decimal representation of n You may make this call only 1f output is open NATURAL CLIENT VIEW NATURAL 23 Along with Put_To comes the shorthand operator lt lt The following two statements are equivalent nl Put_To output output lt lt nl Values output using operator lt lt may be combined into single values or may be strung together using operator lt lt repeatedly as illustrated in the last sample trace statement Sample Traces Statement Object Values mi 1 3 output is_open true output ext_name output content x nl Put_To output nl 13 output is open true output ext_name output content x13 nl output is_open true output ext_ name output content x13 output lt lt nl nl output is_open true output ext_ name output content x130 output lt lt nnl lt lt nl nl output is open true output ext_ name
195. strictive at first but it leads to surprisingly difficult design and maintenance problems For example suppose you are dealing with an application program that involves complex numbers These are numbers of the form a bei where a and b are real numbers and i 1 notice that i is not a real number There is a rich mathematical theory of complex numbers and special notation for dealing with them How do you make the connection between your application program s complex numbers and the operations available in the subroutine library If there are operations in the subroutine library whose abstract descriptions mention complex numbers each parameter to these operations must be of one of the built in types e g Real Therefore you as a client programmer may not think of a complex number as a single entity Every time you want to pass a complex number as an argument you must pass two real numbers Just to make matters a bit worse in this case there are at least two completely different but plausible ways that two Real objects can be used to represent a complex number One is the way suggested above the two real numbers are a and b the real and imaginary parts of the complex number Another method is to consider the two real numbers as the polar coordinates of the complex number The details of how these representations work and their relative merits are beyond the scope of this discussion but they are not the issue The p
196. t is true then the assert statement does nothing and program execution continues with the next statement If the first argument is false then the second argument a Text value is used in an error message that is output to the screen where the form of the report is similar to that shown for the violated precondition of To_Integer in Euclid in Section 3 2 1 after which assert aborts program execution Since the second argument is reported as the assertion that has been violated it is phrased as something that should have been true but surprisingly was not In the example code note the subtle difference between the two arguments the first is a computation of the value of a mathematical assertion and the second is the mathematical assertion itself as a Text value You should use assert only where you expect the tested condition to be true under normal circumstances It should be used only to signal truly abnormal situations from which the program cannot recover and for which immediately stopping execution with an error message is an appropriate response It normally should be used only to give information to a client programmer who is still developing and or testing a program not to give an error message to the end user The call to the underlying Multiply_By_Radix in the component being checked uses the following long name Natural Kernel 1 Multiply By Radix This is the fully qualified name for the Multiply_By_Radix operation in the cl
197. t the time it is called and the implementer is responsible for making sure that the postcondition holds at the time it returns We state the client programmer s obligation under this agreement as follows Design by Contract Rule Do not call an operation when its precondition is not satisfied unless you are willing to accept any behavior whatsoever from that point onward during execution of the program The client programmer of Euclid has used this rule in two ways He apparently has decided that it is unacceptable to call Greatest_Common_Divisor with bogus arguments but that it is acceptable to call Get_From with an input stream that might not contain characters that can be interpreted as an Integer value The program s reaction to a violation of this second precondition is whatever the built in Getz From happens to do which is to emit the less friendly error message To summarize Euclid is not bulletproof because there is no guarantee that it won t simply crash or do anything else if the end user types in the wrong thing in response to a prompt for an integer value gt 3 All operations for Resolve C bulit in types check their preconditions in the instructional version since efficiency is not nearly as important for student programs as the ability to isolate bugs The Resolve C design by contract rule is that client programmers are responsible for establishing preconditions but students occasionally forget to do so and auto
198. t violates the repeated argument rule Be aware that the C compiler will not report this as an error You need to avoid the pitfall by personal discipline The last statement in the tracing table also illustrates that an accessor expression acts exactly like an object of type Item Notice that s current which is being added to s2 in this statement is consumed its new value is O since Item is Integer here because Add Right consumes its argument So this statement changes both s and s2 LisT 10 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Sample Traces Statement Object Values sl lt 92 6 gt lt 18 53 gt i 37 sl lt 92 6 gt lt 37 53 gt i 18 sl lt 9 6 gt lt 18 53 gt i 18 lt non 6 Sy lt 18 23 gt lt 47 gt lt 3 gt lt 92 6 gt lt 0 53 gt lt 47 gt lt 18 3 gt LIST CLIENT VIEW LisT 11 Left_Length Formal Contract Specification function Integer Left Length is abstract ee ensures Left Length self left ER Informal Description A call to the Left_Length operation has the form of an expression sl Left Length This operation returns an Integer value which is the length of the string s left i e Is1 leftl Sample Traces Statement Object Values lt 58 gt 13 9 90 gt 37 sl lt 58 12 gt lt 13 9 90 gt i 2 LisT 12 SOFTWARE COMPONENT ENGINEERING WITH RES
199. that this design succeeds in decoupling Natural_Kernel_C from any particular concrete component replacing the concrete to concrete dependence in the original code Natural Kernel I Con Natural_Kernel_1 with a concrete to abstract dependence Vatural_Kernel_C on Natural_Kernel The checks relation is a concrete to concrete dependence but the concrete component at the target of the checks arrow in the CCD for Natural_Kernel_C in Figure 3 8 is a little black rectangular parameter box This box stands for a restricted formal template parameter of the component Natural_Kernel_C which is depicted with thick sides because it is a template Natural_ Kernel implements Natural chooks Kernel_C Figure 3 8 CCD for Natural_Kernel_C This CCD shows that there is still a concrete to concrete dependence Natural_Kernel_C checks some concrete component note that the parameter box is shaped like a concrete component to emphasize that the actual parameter is a concrete instance But which concrete component is being checked You don t know from the CCD because this decision is not known at design time Instead the choice has been deferred to instantiation time by making the checked component a template parameter What you can tell from the CCD from the arrow out of the parameter box is that the component being checked must be some concrete instance that implements Natural_Kernel If a component has a template parameter with no restriction on it
200. the class This is potentially confusing but alas it is something you have to learn to live with when using C and other object oriented languages Next is the header declaration for a procedure operation Set_Value introduced with the keyword procedure At the end of the procedure declaration and before the formal comment containing its specification is the keyword is_abstract 6 This appears in the declaration of every operation in an abstract instance or an abstract template It tells the compiler that there is no body for the procedure in this abstract component the body will appear in some concrete component that implements this abstract component 4 The standard abstract operations declaration replaces what you would otherwise write in C C at this point individual declarations of the constructor destructor and if you designed the class to have them swap operator and Clear operation It also inhibits the creation of two operations that C would otherwise give you by default assignment operator and copy constructor You could do the same thing in C C by declaring the assignment operator and copy constructor to be private This means that if you try to assign something to an object of the new type or try to pass an object of the new type as the actual parameter where the associated formal parameter is declared without an amp the compiler will report an error The default versions of assignment and copy constructor as
201. tion Integer Length is abstract LA ensures Length self EL Informal Description A call to the Length operation has the form of an expression tl Length This operation returns an Integer value which is the length of string 17 i e It I Sample Traces Statement Object Values tl Help i 1 oes AA ti HeLp i 4 TEXT 10 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Tree Motivation Applicability and Indications for Use The programming type Tree is very common in language processing applications e g parsers interpreters compilers etc The mathematics used to model general trees is similar to that used to model binary trees see Binary_Tree Here we describe only those aspects that differ from the explanation of binary trees The tree in Figure 1 has a root e interior items or nodes h k and f and leaves c g b a j 1 and d just like a binary tree But note that item e has three children and item k has four This is what makes this a tree and nor a binary tree In a tree there is no limitation on the number of children any given item can have An item can have 0 1 2 3 or any finite number of children e fi D k g a f d Figure 1 A tree T Another important difference is that there is no empty tree The smallest tree is a tree of size 1 1 e a tree with exactly one item the root and no children Mathematically we define trees over a
202. type by stating its mathematical model along with the standard operations and kernel operations that can be applied to objects of that type Other operations called extensions can be added in other abstract instances the total behavior being the sum or union of the behaviors described in these smaller pieces CHAPTER 1 ABSTRACT AND CONCRETE INSTANCES 1 3 1 The Kernel Type Standard Operations and Kernel Operations Figure 1 4 shows the entire file contents for the abstract component called Random_Kernel All abstract instance files that introduce new kernel types are identical in structure to this one function Integer Value is abstract ensures Value self 10 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 1 procedure Generate Next is abstract ensures self NEXT self 1 function Integer Limit is_abstract Ll ensures Limit LIMIT 1 1 Figure 1 4 AI Random Kernel h The stylized comment block at the beginning says this file defines an abstract instance whose name is Random Kernel This kind of comment is always the first thing in a Resolve C component The middle line of the block contains the kind of component followed by a colon followed by the abstract instance name Having a strict convention about even this aspect of what the file contains is helpful in two ways It gives a reader of the file some useful overview information in a form that he or she
203. ubstituted for the abstract template name Set_Kernel To bring this component into the context you write include CT Set Kernel 1 C h SET 2 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Component Coupling Diagram Set_ Kernel implements Set_ Kernel_1_C SET CLIENT VIEW SET 3 Descriptions Set_Kernel Type and Standard Operations Formal Contract Specification standard abstract operations Set Kernel Lm Set_Kernel is modeled by finite set of Item initialization ensures self empty set 1 Informal Description The model for Set_Kernel is a finite set of items which is initially empty A Set_Kernel object may be arbitrarily large but still finite Like all Resolve C types Set_Kernel comes with operator amp and Clear Notice that the properties of mathematical sets include that the elements in a set are unordered and that there are no duplicate elements in a set Note The sample traces for this and the other operation descriptions refer to the type Set_Of_Integer which is the result of the following instantiation concrete_instance class Set Of Integer instantiates Set Kernel 1 C lt Integer gt O Sample Traces Statement Object Values AAA SET 4 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Add Formal Contract Specification procedure Add consumes Item amp x is abstract requires x is not in self ensures self self union x 1
204. ude the components used in the instantiation and instantiate them as above giving the new component an appropriate name In fact this is the component used in Monte_Carlo as presented in Chapter 1 Me dessen SEES REESE SEEDEDE es e ge ESKS EDP SES nee ges R Li d Concrete Instance Random Uniform Generator 1 O ir land ES a ia m he R A dee ee SS ia eine El ifndef CI RANDOM UNIFORM GENERATOR 1 define CI_RANDOM UNIFORM GENERATOR 1 1 9 How can a template have no parameters This sometimes arises when implementing kernel components and is discussed only in Volume 3 because a client programmer simply has to know that such things exist and how to instantiate them What is the difference between a template with no parameters and an instance The latter has to be instantiated before it can be used CHAPTER 3 ABSTRACT AND CONCRETE TEMPLATES DECOUPLING 67 include CT Random Kernel_1 h include CT Random Uniform 1 h concrete instance class Random Uniform Generator 1 instantiates Random Uniform 1 lt Random Kernel 1 lt gt endif CI RANDOM UNIFORM GENERATOR 1 Figure 3 17 CI Random Uniform_Generator_1 h Finally Figure 3 18 shows the CCD for Random Uniform Generator 1 A comparison with the CCD in Figure 3 13 is instructive The simpler CCD shown earlier is all a client of Random Uniform Generator I need to know about it it s a concrete instance and it implements Random_Unif
205. ueue Kernel la C lt Integer gt O Sample Traces Statement Object Values IS CE UOO QUEUE 4 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Enqueue Formal Contract Specification procedure Enqueue consumes Item amp x is abstract fet ensures self self lt x gt pay Informal Description Note This and the other operation descriptions refer to these objects in examples object Queue Of Integer ql q2 object Integer i A call to the Enqueue operation has the form ql Enqueue i This operation adds the item whose value is i to the rear right end of q1 Sample Traces Statement Object Values ql lt 58 12 21 gt i 13 al Enqueve i AAA ql lt 58 12 21 13 gt i 0 QUEUE CLIENT VIEW QUEUE 5 Dequeue Formal Contract Specification procedure Dequeue produces Item amp x is abstract V SEL requires self empty string ensures self lt x gt self 1x Informal Description A call to the Dequeue operation has the form ql Dequeue i This operation removes the item from the front left end of g and returns its value in i You may make this call only if q is not empty Sample Traces Statement Object Values ql lt 58 12 21 13 gt i 92 al Dequese i AAA ql lt 12 21 13 gt i 58 QUEUE 6 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Accessor Formal Contract
206. uilt in along with a uses arrow to it from each of the templates shown above No and here s why It is certainly true that the uses relation holds between any template and the components bound by the client to its template parameter s However the purpose of a CCD is to show dependencies between components at component design time i e as those components exist in a component catalog out of the context of any particular client program in which they might be used The bindings of particular values to template parameters arise at instantiation time 1 e as components are integrated into a specific client program by template instantiation At design time we know literally nothing about which component tem in this example might be bound to later it might be any type whatsoever The template parameter Item therefore introduces no dependency between Sequence_Kernel or Sequence_Reverse and any other 38 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 component that is known at component design time So no box for fem or arrow for uses is depicted in the above CCD This conclusion is consistent with the intended interpretation of a CCD in order to understand a component you need to understand all and only the other components that can be reached from that component by following arrows out of it in the CCD To understand Sequence Kernel for example you don t need to understand any other component To understand Se
207. use this would violate the repeated argument restriction So while you might be tempted to write something like sl i amp s1 24 this statement violates the repeated argument restriction for the swap operator This conclusion is especially clear if i 24 at the time the statement is executed but it is true even if i has some other value since both swap operator arguments are accessor expressions for the same object SEQUENCE 8 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 namely s Be aware that the C compiler will not report this as an error You need to avoid the pitfall by personal discipline The last statement in the tracing table again illustrates that an accessor expression acts exactly like an object of type Item Notice that s i which is being added to s2 in this statement is consumed its new value is O since Item is Integer here because Add consumes its second argument So this statement changes both s and s2 Sample Traces Statement Object Values lt 92 6 18 gt 255 lt 92 255 6 gt lt 76 921 34 7 gt s2 Add 3 sl i KO 2550 S lt 76 921 34 6 7 gt SEQUENCE CLIENT VIEW SEQUENCE 9 Length Formal Contract Specification function Integer Length is_abstract rl ensures Length self 1 Informal Description A call to the Length operation has the form of an expression sl Length This operation returns an Integer value which is the length
208. ust have encountered this problem before and perhaps you can make use of their solution What you are looking for is a previous solution that has been captured as a unit with two separate descriptions e an abstract description of behavior that you can consult as a client programmer and p y prog e a concrete description that you can include in your Resolve C program so the computer can execute the operations you invoke Fortunately there are indeed off the shelf software components to make this application program fairly straightforward The program that follows illustrates this Highlighted code is discussed in the text 2 How reasonable the estimate is depends on how many points you use Careful treatment of this question is beyond the scope of the current discussion SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 If a SRG Main Program Monte Carlo estimate of pi Peer A Se es sa oe SKS Se eS IH Date 14 August 1996 revised 24 November 2006 IL Author Bruce W Weide Brief User s Manual Asks for a positive integer which is the number of points to use for a Monte Carlo estimate of pi then reports the resulting estimate of pi and then quits bi e ee ae kf I a Re a ea a ee ee ene oe iif Global Context s mter Dene tS e a a me ESS a IE a EZ program body main object Character IStream input object Character OStream output object Inte
209. veral families of collection components Among these are the List Queue Sequence and Stack families whose models involve mathematical strings the Array Partial_Map Set and Static_Array families whose models involve mathematical sets and the Binary_Tree family whose model involves mathematical trees 2 1 3 Template Instantiation Suppose you are a client programmer writing an application program and you want the formal parameter tem in Sequence_Kernel to be replaced by say Boolean creating an instance Sequence_Of_Boolean that is logically identical to the first piece of code in Section 2 1 When you ask the compiler to instantiate the template by providing this actual template parameter to bind to the formal template parameter the C compiler automatically replaces all occurrences of Item by Boolean and treats the resulting code as an abstract instance Instantiation is tantamount to filling in the blanks in a form The compiler already knows how to compile the resulting abstract instance and the net effect is exactly the same as if the original abstract instance Sequence_Of_Boolean had been used CHAPTER 2 ABSTRACT AND CONCRETE TEMPLATES GENERALIZATION 23 As a client programmer however you never explicitly instantiate an abstract template The reason is that an application program needs to use concrete instances which contain code that can be executed not abstract instances which contain interface contract specific
210. vity indirectly These are all the components that are reachable from a component by following arrows out of it in the CCD Similarly if you change a component you might have to change any or all of the components from which the changed component is reachable along a dependence chain 42 SOFTWARE COMPONENT ENGINEERING VOLUME 2 Figure 3 2 A dependence chain The intuitive objective that you should minimize such dependence chains suggests a general rule of thumb for component design Limited Dependence Rule Design each component so it depends on as few other components as possible Here is an important general consequence of the limited dependence rule that says something about how to achieve it 1 e about how to partition information among components Least Information Rule Design each component so it depends only on components that contain information that is required to understand the new component This design rule is the basis for distinguishing abstract and concrete components a client program needs to know only the interface contracts for the components it uses not the details of their implementations In fact as we will see next the division of component information into what vs how is arguably the most important idea in component based software 3 1 2 Avoidable Concrete to Concrete Dependence Is Worse The ill effects of long dependence chains arise whether the components involved are abstract compo
211. x Informal Description Note This and the other operation descriptions refer to these objects in examples object Set Of Integer sl object Boolean b object Integer i n A call to the Add operation has the form sl Add i This operation adds the element whose value is 7 to set s You may make this call only if i is not already in s Sample Traces Statement Object Values SET CLIENT VIEW SET 5 Remove Formal Contract Specification procedure Remove preserves Item amp x produces Item amp x copy is_abstract requires x is in self ensures self self x and x copy x LES Informal Description A call to the Remove operation has the form sl Remove i n This operation removes from set s the element whose value is i and returns with n having that value as well You may make this call only if 7 is in sl Sample Traces Statement Object Values sl Remove i n sl Remove i n SET 6 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Remove_Any Formal Contract Specification procedure Remove Any produces Item amp x is_abstract rl requires self empty_set ensures x is in self and self self x IAZ Informal Description A call to the Remove_Any operation has the form sl Remove Any i This operation removes from set s some any element and returns with i having that item s value You may make this call only if s is
212. xists a b string of character lal pos and self a b and self a lt c gt b PEL Informal Description Note This and the other operation descriptions refer to these objects in examples object Text tl t2 object Boolean b object Character c object Integer i object Character IStream input object Character OStream output A call to the Add operation has the form t1 Add i c This operation adds c in position i of string t1 i e in a position such that the number of characters before the newly added character is equal to i You may make this call only if 0 lt i lt Irll You can see from this example that the numbering of positions in the string effectively starts at O For instance to add X at the beginning of f i e as the left most character of t you might write tl Add 0 X TEXT CLIENT VIEW TEXT 5 Sample Traces Statement Object Values TEXT 6 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Remove Formal Contract Specification procedure Remove preserves Integer pos produces Characters c is abstract rl requires 0 lt pos lt self ensures there exists a b string of character lal pos and self a lt c gt b and self a b 1 Informal Description A call to the Remove operation has the form tl Remove i c This operation removes the character in position i of string t and returns it in c You may make this call on
213. y ARRAY 8 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Lower_Bound Formal Contract Specification function Integer Lower Bound is abstract ensures Lower Bound self lb 1 Informal Description A call to the Lower_Bound operation has the form of an expression al Lower Bound This operation returns an Integer value which is the lower bound on the interval of legal indices into al i e al lb Sample Traces 7 abcd 8 go 9 bucks 32 il al Lower Bound 7 abcd 8 go 9 bucks ARRAY CLIENT VIEW ARRAY 9 Upper_Bound Formal Contract Specification function Integer Upper Bound is abstract ensures Upper Bound self ub EL Informal Description A call to the Upper_Bound operation has the form of an expression al Upper Bound This operation returns an Integer value which is the upper bound on the interval of legal indices into al i e al ub Sample Traces 7 abcd 8 go 9 bucks 32 i al Upper Bound 7 abcd 8 go 9 bucks ARRAY 10 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Binary_Tree Motivation Applicability and Indications for Use The programming type Binary Tree is ubiquitous in computing It is commonly used in formal language processing applications as the basis for fast searching algorithms as might be used in an implementation of Set o
214. y resizable and that it is always indexed from 0 Component Family Members Abstract Components e Static Array Kernel the programming type of interest with the operations below e Accessor e Lower Bound e Upper Bound Concrete Components e Static Array Kernel I C This is a checking implementation of Static_Array_Kernel in which the execution time for each of the operations accessor Lower Bound and STATIC_ARRAY 2 SOFTWARE COMPONENT ENGINEERING WITH RESOLVE C VOLUME 2 Upper_Bound is constant the execution times for the constructor and destructor are proportional to the length of the interval between the upper and lower bounds All objects of this type have the interface of Static_Array_Kernel with the concrete template name Static_Array_Kernel_1_C substituted for the abstract template name Static_Array_Kernel To bring this component into the context you write include CT Static Array Kernel 1 C h Component Coupling Diagram Static_ Array_ Kernel implements Static_ Array_ Kernel_1_C STATIC_ARRAY CLIENT VIEW STATIC_ARRAY 3 Descriptions Static_Array_Kernel Type and Standard Operations Formal Contract Specification math subtype INDEXED TABLE is finite set of i integer x Item exemplar t constraint for all il i2 integer xl x2 Item where i1 x1 is int and 12 x2 is in t if il 12 then x1 x2 math subtype STATIC ARRAY MODEL is INDEXED TABLE exemplar a co
215. y_Kernel_1_C substituted for the abstract template name Array_Kernel To bring this component into the context you write include CT Array Kernel 1 C h Component Coupling Diagram Array_ Kernel implements Array _ Kernel_1_C ARRAY CLIENT VIEW ARRAY 3 Descriptions Array_Kernel Type and Standard Operations Formal Contract Specification math subtype INDEXED TABLE is finite set of i integer x Item exemplar t constraint for all il i2 integer xl x2 Item where i1 x1 is int and 12 x2 is in t if il 12 then x1 x2 math subtype ARRAY MODEL is lb integer ub integer table INDEXED TABLE exemplar a constraint for all i integer there exists x Item i x is in a table iff a lb lt i lt a ub LL standard abstract operations Array Kernel LEN Array Kernel is modeled by ARRAY MODEL initialization ensures self 1 0 empty set Pay Informal Description The model for Array_Kernel is a three tuple an integer which is the lower bound of the interval of legal indices into a table an integer which is the upper bound of that interval and the table itself a finite set of ordered pairs of type integer Item that contains exactly one pair for each integer within the interval from the lower bound to the upper bound inclusive Initially the lower bound is 1 and upper bound is 0 The constraint of the model implies that the set of pairs is therefore initially empty L

Software Component Engineering

Contents

Download Pdf Manuals

Related Search

Related Contents