[Skip Navigation] [CSUSB] / [CNS] / [CSE] / [R J Botting] / [Monograph] / 01_2
[Index] || [Contents] || [Source] || [ Search monograph] || [Notation] || [Copyright] Thu Sep 16 13:59:55 PDT 2010

Contents


    2 Technical Methodologies

      Previous Section

      [ 01_1.html ] and contents list [ http://cse.csusb.edu/dick/monograph/ ]

      2.0 Definition

      A technical methodology is a methodology that focusses on the structure of the product (code) and the techniques and technology used to write the code. In this page I describe methods concerned with the techniques of coding: Stepwise Refinement and its variations: Structured Programming, Functional Programming, and Functional Decomposition (section 2.2); Information Hiding(section 2.3); Structured Design(section 2.4); and Object Oriented Programming(Section 2.7).

      Each have powerful lobbies but there is little empirical data in their favor [VesseyWeber84] [Cardetal87]. However, there is evidence that each of these methods has worked under some conditions [Cockburn00]. One difficulty is to find out when each is best applied. It is also important to extract from methods the ideas that make them work. We can then put these clues to work.

      Sections 2.5 and 2.6 introduce a useful diagram for disentangling complex processes. The diagram was used in Structured Analysis and Structured Design. I propose a simple and theoretically sound version and use them in the next section(section 3). In that section I consider methods that give more precise modularization rules than the technical methods of this section.

      The most fundamental of these technical concerns is how to divide a program into separately developed pieces or modules. The next section introduces this.

      2.1 Modular Programming

        Modular programming divides a complex program into a set of simpler modules. Once only the best programmers used modular programming. Now only amateurs fail to use it. The debate in the literature is about what the word module means. In practice, the problem is that it is easy to select modules give problems later [Lindstrom93] p 57. Hence a methodology must provide guidance that helps to select a good modules. In the 1990's the term Software Architecture has become associated with the study of modular structures [GarlanParry95].

        You can get a list of relevant publications tagged MODUL in my bibliography.

      . . . . . . . . . ( end of section 2.1 Modular Programming) <<Contents | End>>

      2.2 Stepwise Refinement(SWR)

        2.2.1 SWR in Theory

          Stepwise refinement -- -- --(SWR )
          [Wirth71] is the main method taught in programming classes from the 1970's to the mid 1990's. Each module - starting at the top - is a procedure or function written in a programming language or pseudocode (a.k.a. Program design language, or PDL). Each step is either refined as another module or coded as a few instructions. Supposedly each module is provided with a specification and proved to satisfy it. The following picture shows the process:

          Figure 1. Stepwise Refinement

          Thus the program exands into a tree. Each node in the tree is simple piece of code. Each branch is a reference to a lower level module.

          Restricting each level to be either an iteration, a sequence, or a selection makes design easier because choosing a structure plus its one part determines the specification of the rest of the module [Mills72]. I will refer to this set of structures as the D-Structures [LedgardandMarcotti75]. Some have shown that much of SWR can be automated - but this does not show how, why, or when it works [Nishidaetal91] [Terwiliger93].

          Functional Decomposition -- -- --(FD)
          and Functional Programming -- -- --(FP)
          are closely related to SWR [MartinMcClure] [DunlopBasili82] [Henderson86] [Fairbarn87] [Huet90]. Functional methodologists appeal to the old architectural dogma that "form ever follows function". This is not the last time programmers were inspired by architectural theories to construct their programs a particular way. FD assumes that the best architecture of a piece of software is developed by breaking down its unique purpose into sub-goals. FP and FD assume that there is only one function for a piece of software. FP further assumes that a "function" ( purpose ) must be a mathematical function (a mapping). LISP is an early FP environment [McCarthyetal62]. Pure FP bans assignment statements on the basis that they are not easily axiomatized [Strachey66]. Backus's 1977 Turing lecture described modern FP that stresses abstraction and higher order functions [ACM86]. FP is still a popular methodology in some Computer Science degrees.

          HOS (Higher Order Software) was intended to be practical functional method based on rigorous theory ( see Appendix I & II of [Martin85]). It was applied in commercial data processing systems and other areas. HOS used a special tool (USE.IT) that verified that the interfaces and structures of all the functions fit together and then produces code automatically. James Martin claims a startlingly high productivity for this approach and argues it makes normal programmers redundant, see p 124 & pp284-289, [Martin85]. He compared the result to a clock that has to work because the cogs fit together [Martin85]. However such a "clock" will not keep time if it has an inaccurate top or bottom level functions. HOS has disappeared from sight since then.

          Functional methods tend to confuse several different meanings of the word functions. This confusion was part of the milieau at the time: [Nagel65]. The functional methods assume that the relation between structure and function is one-to-one. However this is false:


            [Parnas72b].
          1. Strachey and others point out that a choice of a data structure determines the program structure [Strachey66] [Jackson76] [RomanGambleBall93] p280.
          2. There are many algorithms that satisfy the functional specification for sorting [Knuth69] Vol 3.
          3. The structure of a "good" sort is not determined by the function but by (1) the paradigm in use [Ambleretal92], (2) the resources available(space,speed,deadlines), (3) the performance goals, (4) the properties of the data being sorted [Knuth71], and (5) how reusable it should be [Weideetal94b] .

          Functional methods also assume that a function( what the customer wants) can be broken down into a tree structure of functions (program specifications and/or program pieces). The Quality Function Deployment(QFD) method challenges this by showing that in real projects a particular customer need is correlated with several technical requirements and vice versa. Further QFD makes it clear that non-functional requirements like "easy to learn" are an important part of real software development.

          For more reading on functions see items FUNCTION in my bibliography.

        . . . . . . . . . ( end of section 2.2.1 SWR in Theory) <<Contents | End>>

        2.2.2 SWR in Practice

          If SWR was a universal method then it can be applied to SWR giving a process program - a program describing how to carry out part of the software process [Osterweil87]. I will apply SWR with Ada as a Program Design Language. Suppose we have the following data structures:
           	-- type  assertion  is  defined elsewhere;
           	-- type  step_type  is  defined elsewhere;
           	type  specification is
           			record  pre-condition, post-condition: assertion;
           			end record;
           	type  program (n:integer:=0) is
           			record  step: array integer range 1..n of step_type;
           				 spec: array integer range 1..n of specification;
           				-- some details omitted
           			end record;
          I get the following top level:
           	function  write_program_for (the_specification: specification) return  program is
           		prog:program:=top_level_code(the_specification);
           	begin
           		SPECIFY: for i  in prog.step'range loop
           			prog.spec(i):=specify( prog.step(i) );
           		    end loop   SPECIFY;
          
          
           		PROVE: for  i in prog.step'range loop
           			      for j  in prog.step'range loop
           					if can_follow(prog.step[j],  prog.step(i)) then
           						prove_implication(prog.spec(i).post_condition,  prog.spec(j).pre_condition);
           					end if;
           			     end loop;
           		    end loop   PROVE;
          
          
           		DECOMPOSE: for  i in prog.step'range loop
           			if   complex ( prog.spec(i) )  then prog.step(i):=write_program_for ( prog.spec(i) );
           			else    prog.step(i):=write_code_for( prog.spec(i) );
           			end if;
           		    end loop   DECOMPOSE;
          
          
           		return prog;
           	end;
          In the above, as in most process programs, the users of the process need intelligence to supply the undefined steps and conditions. Notice that others suggest different top levels for SWR - for example see Freij's top-down design program [Freijs93]. Further, since the "PROVE" step is sophisticated and time consuming, and so many programmers, computer science texts, and programming texts omit it. Others place it after the "DECOMPOSE" loop, make it a separate parallel task [CreveuilRoman94], or delay it until either testing or when a regulatory body insists on it [Parnasetal94]. Another variation occurs in some texts and papers that replace the "DECOMPOSE" process by a "REDESIGN" step where several nearby steps are gathered together and replaced by an expanded and improved set - Stan Kelly-Bootle makes fun of this as applied "kludge theory" in his "Devil's DP Dictionary". Terwilliger developed a prototype tool (ISLET), in Prolog, that supports the Dijkstra/Gries version of SWR [Terwilliger93a]. His conclusions include the following:
            "The programmer makes all the design decisions and must generate intermediate assertions for the proofs. While this method [SWR] has a certain elegance it is difficult to extend to larger and more complex designs [...]generating the intermediate assertions for the proofs becomes more and more of a burden. Unfortunately the point of infeasibility is reached quite quickly; therefore ISLET also supports the applications of preverified cliches to create programs more easily."

            "Cliche construction and verification are quite difficult but are only done once for each cliche and performed by a master designer."

            "Our experience leads us to believe that the cliches underlying the process are more important than is sometimes stated; furthermore, we believe that they can be formalized and automatically applied."

            [Terwilliger93a]


          He has published an example of using cliches to prove a simulation [Terwilliger93b]. Clearly we will need many cliches for this method to work.

          A number projects have used SWR not just to design programs, but also to specify requirements. Private and published experiences seem to indicate that this (1) tends to add unnecessary design details (like flags), (2) hide the reasons for various steps in the program, and (3) complicates the maintenance of the specifications [Levesonetal94] page 705.

        . . . . . . . . . ( end of section 2.2.2 SWR in Practice) <<Contents | End>>

        2.2.3 SWR Considered Harmful?

          I will now show that SWR has fundamental flaws as a general purpose software process. Then we will see what we can harvest from it.

          The rules for writing the top level of the program (top_level_code(the_specification) above) are mainly syntactic("No GOTOs") and hortatory. SWR programmers have to choose steps which, when specified, can then be proved to achieve the desired specification. This requires (1) unusual foresight , (2) a large collection of Terwilliger's cliches, and (3) additional work to ensure adequate performance.


          1. IBM's Cleanroom method - a new version of Mill's work - states that refinement is a creative step that has to be verified afterwards [Hevneretal92] [Hevneretal93].
          2. Roman & Wilcox write: " Like most contemporary authors, we view program derivation as a creative process [...] Each specification refinement requires some inspiration,..." [RomanWilcox94].
          3. Creveuil & Roman state "Looking ahead and back-tracking are a part of the method" [CreveuilRoman94].
          4. In one sample, 7% of the "refinements" applied by programmers were backtracking steps [Reynoldsetal92].
          5. For Niclaus Wirth, a "refinement" has become any evolutionary and iterative improvement in either the specification or the implementation of a module [Wirth95].
          6. Bergland called this "magic" and showed that other methods focused their "magic" more than SWR [Bergland81] figure 44.
          7. Reynolds et al show that SWR is a part of general problem solving [Reynoldsetal92].

          Therefore, the structure is an invention of the programmer. Inventors are proud of their own designs and don't want it disproved. So most practicing programmers ignore the "PROVE" step. Further, SWR does not encourage the designer to consider alternatives and choose the one that fits the current situation, see "trade-off analysis" in [DavisA94a] [DavisA94b]. Each refinement is an invitation to indulge in more or less pathological heroism!

          There has been a long debate on which control structures should be permitted [see HARMFUL in my bibliography]. The disputed structures are ways of coding non-sequential behavior so perhaps it is the idea of using sequential languages that is the problem:


            "Maybe Your Next Programming Language Shouldn't Be a Programming Language" [ShawM90].

          Programmers find it difficult to break out of sequential structures [Alexander92]. Many authors argue that by limiting designs to sequential solutions the simplest software can not be found [see NONSEQUENTIAL , CONCURRENCY , and NON-DETERMINISM in my bibliography]. For example, some sort programs are parallel and so are not discoverable by SWR [Hoare83] [GulAghar90] [Ambleretal92] [Weideetal94b]. Dijkstra has produced software with a non-sequential structure [Dijkstra68c]. Floyd describes a common kind of problem that has an elegant non-sequential solution in his 1978 Turing lecture:
            " [. . .] because input and output are naturally expressed using multiple levels of iteration, and because the input iterations do not nest with the output iterations, the problem is surprisingly hard to program in most programming languages [. . .] The problem is naturally formulated by decomposition into three communicating co-routines [. . .]. Yet, except for simulation languages, few of our programming languages have a coroutine control structure adequate to allow programming the problem in a natural way." ("The Paradigms of Programming" [ACM86])

          In 1975 Michael Jackson called this kind of problem a " structure clash" and showed how semi-co- routines gave elegant designs that are easy to code correctly [Jackson75] p66 of [OlsenD93]. In theory a concurrent set of finite state systems can be much smaller than the single finite state system that they emulate. In theory all finite state systems are reducible to couple "simple" machines and delays - however "simple" in this case is a piece of mathematical jargon - some simple machines will have millions of states [HartmannisStearns]. In practice, concurrency simplifies specifications [Levessonetal95] page 704. Decomposing specifications into views that are combined by logical (not sequential) operations can also be beneficial [JacksonD95b]. So SWR constrains thinking to stepwise solutions. When an engineer selects one solution( s ) from a set of solutions ( S ) then at best he or she has proved that s is no worse than other solutions in S [Krick69] p137. Now if a problem is computable then there is a D-structured solution [BohmJaccopini] [LedgardMarcotti75]. So programmers can always find a sequential structure. It may or may not be best in the long run. Diaz-Herrera put it like this " [...] the concern is with the call-return semantics, so subroutines become the main structural element. The methods assume that subroutines are also the best way to organize the program text and incrementally build the system. Nothing could be further from the truth." [Diaz-Herrera93] The meaning of the word "best" varies from project to project but at least implies that the program achieves its function. Satisfactory performance (speed and space) is essential [Cardenas-Garciaetal91]. Qualities like elegance, clarity, readability, maintainability, . . . are at least as as important because they effect long term cost [See citations under QUALITY in my bibliography]. Time-to-market may be critical for short-term survival. Sequential solutions may or may not optimize any of the above qualities:
            "The order in time in which processing is expected to take place should not be used in making the decomposition into modules. [...] We have tried to demonstrate by these examples that it is almost always incorrect to begin the decomposition of a system into modules on the basis of a flowchart." [Parnas72b].

          Hoare argued that SWR maximizes the interfaces between modules:
            "Note that the interfaces between modules of a program are [a] flow of control. It is information which passes, as it where, along these lines that must be specified more rigorously in order to ensure that the final assembly of separately implemented parts is to be successful.

            Unfortunately, the information which passes between the subtasks is not just a collection of 50 or 100 signals: it is the entire state of the computer store and external files at the time that control passes from one part of the program to another." [Hoare73].


          So SWR can not maximize maintainability. This is a long lost secret: Recasting an algorithm as a network of objects and operations leads to more maintainable code [Weideetal94b].

          Finally all top-down methods like SWR have an ironic flaw - they can not fail. Top-down methods have no rule that says: stop trying to solve this problem (or subproblem). As long as the programmer's imagination can supply refinements they will continue. But there are problems can not be solved by any program - the Halting Problem for example. Thus, SWR(and other top-down methods) can not produce a working program when applied to these problems. So a top-down + creativity - knowledge process will not stop and the program will always be "90% complete."

        . . . . . . . . . ( end of section 2.2.3 SWR Considered Harmful?) <<Contents | End>>

        2.2.4 Conclusions

        I conclude that, first stepwise refinement may ultimately produce a provably correct program but does not necessarily select the best design. Second, SWR, FD, and FP do not contain sufficient guidance in decomposing a complex process into pieces. Third: From SWR, FD, and FP we can extract the idea of applying a known algorithm or cliche to structure functions and procedures that have a fixed specification - say a square root library function or sort. Fourth: Hence someone who uses these methods must have easy access to as many cliches (patterns) as possible. Fifth: For complex problems, those with no published algorithm, those that require two or more cliches to run in parallel, or unstable problems that may change; other techniques may be better. Sixth: We may need a simple notation for refinement, sequence, selection and iteration:

        Figure 2. Sequential Structures=sequence+selection+iteration

        Finally: from the endless debate on structured programming, and the known complexities of parallel programs I conclude we will need a way to define simple to understand non-sequential structures. The next sections digs out some ways for determining the non-sequential or static structure of a piece of software from existing practice and earlier theory.

      . . . . . . . . . ( end of section 2.2 Stepwise Refinement(SWR)) <<Contents | End>>

      2.3 Information Hiding and ADTs

        2.3.1 Information Hiding in Theory

          Parnas published an alternative to sequential decomposition in 1972. His Information Hiding heuristic works by wrapping up each design decisions in a module with a defined interface [Parnas72a] [ [Parnas72b ] [Hoffman90]. The assumptions that can be made about the interface are designed to be independent of how the module is programmed. By the same rule, the module must not be designed to make use of any information about the design of the rest of the software. Thus different implementations can be used without changing the rest of the program. Ideally modules will be "plug compatible" and implementation decisions become irrelevant to the correctness of the whole. When something ( a decision, some data, a structure, an operation, or another module) appears in a module but no other module relies on it being there then it is said to be hidden or encapsulated. Steve McConnell's handbook pictures a good module as an iceberg with only the top 10% being visible [McConnel93].

          For a 15 years (roughly 1970-1985) SWR, FD and FP where the main methodologies studied in research papers. But, in the middle 1980's, Information hiding and encapsulated structures became a more popular method to write about.

          An early application of information hiding (Circa 1975?) was the idea of "separating the physical from the logical" - The reasoning being that since input/output hardware is designed by hardware designers there should be software modules that hide or encapsulate how the data is transmitted, stored, encoded, blocked, etc. The application programmer can then focus on the logical structure determined by the problem. This became an important paradigm for several operating systems where all devices appear as a stream of bytes, or a stream of blocks, etc. Later similar ideas have emerged for separately programming (1) data bases, (2) graphic displays, & (3) user interfaces. This principle lead some programmers to design separate programs for handling (1)printed output, (2) the logic of the application, and (3)formatted input. It re-emerges as the separation between lexers and parsers in compilers (see later). The "separate physical from logical" principle has been since reformulated or rediscovered many times See RESOLVE [Chauvet95] [Gammaetal95].

          Parnas's idea lead to the use of new program structures: "Abstract Data Types"(ADTs) in the 70's, C ".h" vs ".c" files in the 80's, Import/Export in Modula, Package Specifications and Bodies in Ada 83, and IBM Box-structures and C++/Java classes in the 90's [Hevneretal92] [HevnerMills93]. Another helpful idea: "Levels of Abstraction" [Dijkstra68c], "Virtual Machines", or "Layered Architecture" has been discovered many times [Shumate89] [Faulketal92] [Grimshaw93] [Blum94] [Weideetal94b]. Some modern formal methods use data refinement to complement SWR which has a similar effect [McDermid89] [Nicholls90] [MahoneyHayes92]. Objects can fit Parnas's criteria [Hoffman90a] [KorsunMcGregor90p59]. Meyer's "Design by Contract" concept is directly derived from the "information hiding" school of thought [Meyer92]. An Abstract Data Type(ADT) is a collection of functions or operations that(1) manipulate a set of data objects(the data type) and (2) satisfy a specified abstract algebra [LiskovZitler75] [Winograd79] [Isner82] [Meyer82] [Pagan83] [LiskovGuttag86] [Berztiss88] [Bishop90] [Yadav90]. ADTs hide the information about how the data type is coded and manipulated inside a "chip." As in hardware the chip has a specification of how and when it can be used. However, Ada, and most computer science and programming texts use ADTs but omit the algebraic part of the specification. However this information can be useful for (1) checking for coding and specification errors, see LARCH and LCLint [EvansGuttagHorningTan94], (2) debugging [Rosenblum95], (3)monitoring for faults [??] and (4) selecting faster implementations

          [VandevoordeGuttag94] see also RESOLVE in my bibliography.

          In a typical ADT, the operations are functions that operate on elements of the type and produce elements of the type. When the operations are actually procedures (so called void function in C/C++/Java) that operate on and change a particular element of the type, and the structure is hidden by these procedures then we get an abstract data object, or virtual machine. Further developments in the direction of "object-orientation" will be covered in the last section on technical methods below.

          Experiences of Ada, C++, and other partial implementations of the ideal ADT, seem to be leading to a redefinition of what a module is. The idea of a "module" seems to be mutating from being "a data type with hidden structure plus an abstract specification" into new forms. For example in Larch/Smalltalk types are specified separately in Larch and implemented by sets of Smalltalk classes. In Resolve, a module can be (1)a specification of a concept, (2)a description of how the concept can be used in a particular implementation(interfaces), and (3)the actual (hidden) implementation of a concept [See RESOLVE in my bibliography]. Here a concept (a module) can have many implementations - each with different ways for it to be used(interfaces). Each of set of interfaces can have several different implementations with different performance properties. The implementation modules, in turn, do not refer to other implementations, but to concepts. This is called the layered architecture [Zwebenetal95]. So the programmer uses the concept and its usage rules to write code. The compiler would check, optimize and assemble the result. This more complex conceptual structure may or may not be accepted by the software engineering community. It took 20 years for encapsulation and abstraction to become the dominant paradigm. Parnas's original idea of separating design choices is still not properly understood [Parnas 1996 Private communication]. Whether a three layer elaboration or some other set of shells encapsulating a kernel of implemented intelligence will be popular in the 21st century is another matter.

          The idea that data can be described by the operations that manipulate it, leads to the idea of generic modules. Generic modules can work on many kinds of data as long as it fits the module's abstract specification. Thus in most languages "+" operator has (approximately) the properties expected of addition in high school algebra whether it is applied to integers, floating point numbers, or (in C) chars. Similarly the idea of finding the next value in a data type ("++" in C, "succ" in Ada and Pascal) is generic across all finite enumerated types, characters, integers, etc. Again sorting is a well defined process for any linearly ordered set of items - independent of their type, storage, etc.. COBOL, PL/I, and C all provide macros that can give this effect when used absolutely as the designer expects - the compiler does not check the substitution. Ada 83 made it possible for a programmer to create new generic operations, procedures, functions, and ADTs safely [Ada83]. Templates in C++ do something similar, as do functors in Standard ML. Similarly frameworks "wrap" around specific modules to provide particular services: A generic sorting framework is given and organizes: the type of item, the ordering, and a description of the aggregate data (array, list, file, ...) into a new module that can be used for sorting the specified data as is desired. Notice that templates and Ada style generics are not a runtime mechanism.

          You can fake generic code if you can write code that can ignore their actual types for general operations, and use parameters that are subprograms for specific operations. For example in C the library qsort function sorts "void*" data with a specially coded function to do the comparison. "void*" fakes generic code buy sacrificing strong data typing. Modern functional languages(FP, SATHER, ML,...) introduced the idea of polymorphism. A polymorphic function can use generic properties of data that has a partially defined type: for example a sort can be written for list of any items at all as long as they all can be compared by the same boolean operation.

          The object-oriented languages (Smalltalk, C++, Java, ...) have a similar kind of polymorphism. In the object-oriented sense, data types are organized into an Aristotelian hierarchy of generic and specific classes. Polymorphic methods (virtual functions) are bound dynamically to a specific piece of code in this hierarchy and is chosen by the specific class of the object. Those who have worked with Ada generics or C++ templates find the polymorphism of Java or C++ a clumsy and less powerful technique. However, polymorphism still better than being unable to write any kind of generic code.

          Generic code can be used in many different programs and projects. A practitioner learns that it is easier to write generic modules because all the assumptions have to be stated up front and then abided by. Further Yaknis et al observe that the expense of proving a generic module is shared among all the instances, and so conclude that (1) only generic algorithms a worth proving, and (2) they must be designed so that correct instances are automatically generated [YaknisFarrellSchultz94]. In other words, these generic algorithms are formally specified cliches that can be automatically reused. Functors ML and GenVoca components [Batoryetal94] specify the transformations that can be made to generate specific versions from generic forms. There is research on special languages (Module Interconnection Languages) that do generate and connect modules written in normal programming languages. In other words tools are developing that amplify the work done by the programmer. They are like levers in that a small powerful action can be spread out over a wide range of uses.

          A complete set of generic "chips" would codify most of computer science. Perhaps computer science can be treated as a supplier of "generic abstract chips" that in clearly documented circumstances can be used by software engineers to solve real problems. However recent publications are heading in the direction of families of related "chips" - patterns. There is much research on packages of generic objects and operations that model a set of solutions to a set of problems found within a particular domain.

          Parnas's information hiding is orthogonal to stepwise refinement


            "design decisions transcend time of execution, modules will not correspond to steps in the processing" [Parnas72b].

            "Historically, the services have employed a functional decomposition method for specification writing. This is a very convenient way to represent end-user requirements for systems and also a way to test systems. It does not lend itself to good software-engineering practices such as object-oriented design or information hiding." [RAdm Sears speaking at the 12th Annual National Conference on Ada Technology, as reported on page 16 of the AdaIC Newsletter June 1994]


          In 1972 Parnas suggested what Jackson later(1975) calls "dismemberment": This is an efficient way for code that is always crossing module boundaries [Parnas72b] At the time operating systems and programming languages did not make it easy to treat programs as modules in another program. Now days we have more processing power and in many cases are trying to solve bigger problems with worse deadlines. So we have scripting language that connect module inputs to module outputs without recoding. Now a program is separately compiled code with perfect encapsulation. In practice it is easier to rapidly produce applications in such a system than traditional programming. Examples include: UNIX, HyperCard, Microsoft VBXs, NextStep/OpenStep...and other APIs(Application Program Interfaces) [Udell93] [Staringer94].

          Parnas's modules typically preserve hidden, internal data. The Information Hiding heuristic leads to encapsulated data, but not necessarily vice versa. It is claimed that hiding information reduces the dependency between modules - the frequency with which a change in one place has an effect on other parts [WildeHuitt92]. This should also make it easier to verify safety and manage the code [Diaz-Herrera93] p78. There is some experimental evidence that layered designs (using only specified information and operations) are completed quicker with no apparent loss of quality [Zweben95].

        2.3.2 Information Hiding in Practice

          Modern Information Hiding follows the following guidelines:
          1. Nail down requirements before doing the design.
          2. Divide the solution into modules using information hiding/abstraction.
          3. Specify modules precisely, as a black-box before writing the program.
          4. Use formal methods to give precise documentation.
          5. Write the code last to fill in the "hidden" information.

          [Chmuraetal.90] [Parnas85]

          Even so there is room for argument about the correct interfaces for modules for example [Constantine90] versus [Hoffman90]

          Chmura reports that these methods discovered 300 errors in the design(not the code) of a large project [Chmuraetal90]. This compares well with the 800 errors found in running the software of another project using literate programming [Knuth89]. But Parnas explains:


            "We have not yet proved that these methods lead to reliable code that meets time and space constraints. We found that every one of these precepts is easier to pronounce than to carry out. Those who think that software designs will become easy, and that errors will disappear, have not attacked substantial problems. [ . . . ]

            "We can write software requirements documents that are complete and precise. We can understand the mathematical model behind such documents and can follow a systematic procedure to document all necessary requirements decisions. Unfortunately it is hard to make the decisions that must be made to write such a document. We often don't know how to make those decisions until we can play with the system. Only when we have built a similar system before is it easy to determine the requirements in advance. It is worth doing but it is not easy.

            "We know how to decompose complex systems into modules when we know the set of design decisions that must be made in the implementation. Each of these must be assigned to a single module. We can do that when we are building a system that resembles a system we built before. When we are solving a totally new problem, we will overlook difficult design decisions. The result will be a structure that does not fully separate concerns and minimize complexity.

            "We know how to specify abstract interfaces for modules. We have a set of standard notations for use in that task. Unfortunately, it is very hard to find the right interface. The interface should be an abstraction of the set of alternative designs. We can find that abstraction only when we understand the alternative designs."


          [Parnas85]
            "It is also safe to say that the long-accepted rule of specification before implementation must be relaxed. Specifications can turn out to be as unsuitable as implementations can turn out to be wrong."

          [Wirth95]

          Clearly Information Hiding relies on experience and intuition. There is no accepted notation as yet [Diaz-Herrera93].

          From Information Hiding and the related methods we can extract the idea that: Module boundaries should separate different concerns and hide "know-how".. This means that module can not be just a function or a procedure. So, a module must be a system of functions, procedures, data types, constants, and variable data etc with a specification encapsulating them.

        . . . . . . . . . ( end of section 2.3.2 Information Hiding in Practice) <<Contents | End>>

      . . . . . . . . . ( end of section 2.3 Information Hiding and ADTs) <<Contents | End>>

      2.4 Structured Design(SD)

        "Structured Design"(SD) was an extremely popular set of methods for planning modules [Yourdon75] [DeMarco79] [DeMarko80] [WardMellor85] [Boddie87] [Coad90]. Those organizations that adopted structured design, structured programming, walkthroughs, time shared program development, and other parts of IBM's "Improved Programming Techniques"-- -- --(IPT)
        in the 1970s seemed pleased with the results [McNurlin77]. A recent comparison of two similar teams working on similar (large) projects in the same language with and without Structured Analysis(SA) and Structured Design(SD) showed that the number of interface errors was reduced significantly in the SA+SD team [NakajoKume91]. Formal versions have been created [Lustman94]. There are some combined SA+SD methods - Structured Analysis and Design(SAD). The evolution of Constantine's ideas into a popular method has been documented [Keufel90]. Yourdon's "Structured Design" method to evolved through at least four forms [Bowles90]. First it was functional(YSM 1.0), and then became process oriented, and then included a model of data, and then added dynamics(YSM 2.0) [WardMellor85] [Yourdon93], and then objects(YSM 3.0) [Coad90] [ShlaerMellor92]. Expert Systems Technology has been fitted to it [KellerR87]. The original SD method used coupling and cohesion to evaluate a structure [StevensMyersConstantine74]. The internal cohesion of a module, and its coupling to other modules were subjective post hoc pseudo-metrics. Recent work has started to develop objective and valid measures [BiemanOtt94]. More modern versions are (1) Wilde's dependency analysis [WildeHuitt92] and (2) the idea of the constraints imposed, at design time, by commitments [Marketal93].

        It is not necessary to apply SD to itself since Tom De Marco's text's on these methods used their own methods to describe SD [DeMarco80] [DeMarco88].

        From SA(Structure Analysis) we can take the idea that there is more to software engineering than writing a single program - part of software engineering involves looking at existing solutions. Further software engineering is about designing a system of cooperating parts. From SA we can extract a powerful tool for understanding existing systems: Data Flow Diagrams.

      . . . . . . . . . ( end of section 2.4 Structured Design(SD)) <<Contents | End>>

      2.5 Data Flow Diagrams

        2.5.1 Description & History

          Data Flow Diagrams -- -- --(DFDs)
          developed from cybernetics and general systems theory in the 1950's. From 1970's through to the 1990s all commercial SA & SD methodologies used Data Flow Diagrams(DFDs). They let you abstract the structure of a system and ignore details. They show parts of a system plus the flow of information between the parts. " [...]dataflow [...]seems to be a natural way for people to think about [processes]. After surveying several process-definition efforts, we found that almost all of them used some sort of dataflow notation as a first approximation -- and sometimes as final documentation"p61 of [Dutton93]. DFDs make interfaces obvious and de-emphasize sequences. Many use them for describing and defining systems, programs, and processes [See Sources under DFD in my bibliography]. Jankowski has listed 28 rules for drawing DFDs so that they fit SA [Jankowski94]pp78-80.

          DFD's evolved from "Diagrams of Immediate Effects" used in Cybernetics and General System Theory in the 1940's and 50's. These diagrams ("Boxes and Arrows") are collections of symbols connected by arrows. In other words they are directed graph with nodes and arcs or a digraph with vertices and edges. The nodes represent parts of something. Arcs show couplings between the parts. An arrow connects A to B if and only if part A can directly effect part B and not vice versa (Section 4/12 through 4/15 of [RossAshby56]).

          Figure 3. DFD of thermostat person chiller heater switch house

          Equivalent Text. A person can change the thermostat or the switch (or both). The thermostat effects the switch, and the switch can effect the heater and/or chiller. These in turn eventually change the house temperature. If well designed, the change in temperature effects the thermostat so that it turns off the heater/chiller. The temperature change may make the person happier. If not the person instigates another set of changes. The diagram implies (inaccurately) that the house temperature is not effected by the outside weather or anything but the heater and chiller.

          In these old DFDs the parts are not subroutines but objects: the nodes are physically separated components that (1) work in parallel, (2) tend to exist for a long time, (3) tend toward states where the whole is stable, and (4) encapsulate some degree of "intelligence". Compare the above with the attempt to evolve some software:

          Figure 4. Life-cycle vs System

          In Ross Ashby's diagrams the coupling between parts was instantaneous, but in information processing there is often an unknown and/or variable delay. So the arrows in DFDs merely mean that a sequence of events at one end must match the sequence at the other end after some delay. Usually, and without loss of generality, the arrows on DFDs behave as first-in-first-out queues [KramerLuqiBerzins93] [BradacPerryVotta94]. Intuitively, you can imagine a person at each node mailing packages along the arrows - like in an office or a Mail-enabled Application [Chisholm94bc]. The "Job-shop" model is an obvious way to simulate the behavior of such systems [LeonardDavis95]. Implicitly if there is no connection between to parts in a DFD then there is no direct influence (hidden) either: The user (above) is stopped from influencing the hardware except by using the software, or the programmer for example. The UK Structured Systems Analysis and Design Methodology (SSADM 1981...) uses similar semantics. These DFDs capture Diaz-Herrera's static structure [Diaz-Herrera93]. Each DFD is an architecture for a kind of Ensemble [Gelernter91]. On the theoretical side Harmannis and Stearns have developed a deep theory of when and how finite state systems can be decomposed into DFD-like systems.

          Larry Constantine writes:


            "Data flow Diagrams were intended as a nonprocedural model of computation, separating the essence of what the computer was to do from how it was to be implemented. [...] In practice, designers often turned DFDs into flowcharts with funny figures, a corruption encouraged by enhancements that implicitly invited procedural thinking" [Constantine94]

          These "corrupt" DFDs use arrows as control flow and so draw DFDs that are Von Neuman flowcharts and/or State Transition Diagrams(STDs) [WardMellor85] [Ward8689] [HatleyPirbhai87](DFD/CFD) [MurphyBalke89] [Babinetal91] [Lustman94] [Zhuetal95]. In these an arrow A->B can mean that part A hands control to part B. Larry Constantine argues that this is unwise [Constantine94].

        2.5.2 DFD Definition

          This book uses concurrent DFDs to model non-sequential systems like the development of software. In a Concurrent DFD a connection A->B means that (1) parts A and B co-operate, collaborate, or communicate in some way ( the form they communicate can be noted on the arrow), (2) A can effect B but not vice versa , and (3) eventually B accepts all of A's communications. (1) implies that A and B must both exist at the same time. I assume that B may wait for communications from A but A can always proceed even if B has not yet accepted previous data.

          No "control" is transferred. At most a message can either create and/or delete its target. When control is transferred: A stops and B starts and so I use a different notation.

          Again, the DFD states explicitly what connection are permitted and implicitly forbids other influences. Each DFD states a precise architecture [MoriconiQian94].

          Concurrent DFDs allow us to see software as a machine as well as a text or formula - as Gelernter recommends [Gelernter91p41]. They also allow us to model systems that have hundreds of more or less cooperating pieces - hardware, software, and human. A DFD helps us imagine systems as cellular organisms or ecologies. They can be used to recast an algorithms as machines [WeideOgdenSitaraman94].

          Now if A effects B but they do not both exist at the same time then any influence A has on B must be through another part that stores the effect. So some DFD parts will have memories - they will not be functions. Later we look at some extra constraints that specify behaviors more exactly.

          Figure 5. General Structures= sequence, selection,all,data flow

          The future IEEE Standard Reference Model for Computer System Tool Integration will incorporate DFDs with Processes, Stores, and Entities. [Poston89]. Stores hold things for future processing but do not change them. Their intelligence is limited to rote learning. Processes move and change things. They have enough intelligence to recall their state and use it and rules to determine how they react. Entities are not part of the system. They are intelligent enough to be unpredictable, creative, and error prone. In this book processes are bubbles or boxes with rounded corners. Stores have corners. Entities and external data flows are not in boxes. Entities and stores can be duplicated, but each processes can only occur once. An arc can have a label that determines the types and/or names of the effects and/or data transferred.

          Figure  6. Sample DFD of a Coding

          The nodes and arcs in a DFD can have names that identify them. A node can identify another DFD. The identified DFD can replace the node in the whole DFD. The above compiler for example can be substituted in the Typical DFD above. Further the lexer in the compiler can in turn be made of many processes [Dyadkin94] [Dyadkin95]. Notice that no new connections appear when such a substitution takes place.

          Figure 7. Refinement of Compile in Figure 6

          For complex systems, I will use the n2 Chart layout with nodes on a diagonal and the arcs in an n><n matrix. Data flow is always clockwise in an N2 chart and so arrows are omitted [Lano77] [Garfield78] [ SADT in subject ] [Zhuetal95].

          A process waits when it has no incoming data but an entity can initiate change in a process or be a sink into which change is absorbed [Beer74]. The stores respond solely to input from processes like data bases or Linda tuple spaces [Gelernter91]. Processes add data, search for and read data, or extract data. Each process and store has an internal control mechanism but entities are out of control. In a stable system a finite quantity of input from an entity leads to a finite transient response before all processes end up waiting for more data [Ross Ashby above, cf a Trellis in [Gelernter91]. With a little care and attention to timing you can avoid deadlocks [Ryant95]. A deadlock happens when a process waits for data that will never be produced because it depends on data that the process itself has not yet produced. Another, danger that can be avoided in practice, is livelock, when more and more data is produced in a self-stoking cycle, but no useful results are produced. There will be more about timing when we consider DFDs as a design tool below.

        . . . . . . . . . ( end of section 2.5.2 DFD Definition) <<Contents | End>>

        2.5.3 A little theory

          The Hartmanis and Stearns theory of coupling sequential systems has a little known theorem that can be interpreted as linking DFDs to the practice of separating of concerns. The practice is to separate different views of the problem - physical vs logical, rules vs databases, user view vs internal structure,... - and design different modules for each partial view. If these views generate a systematic model of the system (a state determined system or a program) then there exists a decomposition of the system into a DFD with the model as a part of it. If the two or more views are orthogonal then the DFD has separated parts as well:

          Hartmannis and Stearns give calculations for validating and generating these decompositions automatically.

        . . . . . . . . . ( end of section 2.5.3 A little theory) <<Contents | End>>

        2.5.4 Summary

          With roots in Cybernetics and General System Theory, concurrent DFDs are like a circuit diagram - they show the allowable parts and connections. They show how separate parts are interfaced. They hide timing, implementation, and internal structures. DFDs are useful for documenting an existing system, process, design, or program. Song and Osterweil use DFDs to document their method for comparing methodologies [SongOsterweil94]. I will use them to describe a system of processes that help create and modify software, compare [Dutton93]. Ways of expressing DFDs mathematically will develop in chapters 4, 5 and 7.

        . . . . . . . . . ( end of section 2.5.4 Summary) <<Contents | End>>

      . . . . . . . . . ( end of section 2.5 Data Flow Diagrams) <<Contents | End>>

      2.6 From DFDs to Code

        DFDs are clearly a useful tool for understanding what already exists but are they a good design notation? DFDs could be the software equivalent of "circuit diagrams" or "block diagrams" like the DFGs of [AthanasSilverman93].

        First observe that DFDs handle clashing structures elegantly and separate the design decisions into independent design problems - if only we had the technology to reconnect them! Second, using non- sequential structures can make it easier to reuse cliches. For example, suppose we have a function SUM to scan a stream of data and return the sum of the items(or zero if it is empty), and another function MAX that scans a stream of code for the largest of the items ( or zero it is empty) then we can not combine these into a single program without either

        • storing the data and scanning it twice,

          or

        • modifying the code of the two functions.
        There is no structured program that splits the data as it arrives into two parallel streams and feeds it to an unaltered MAX and SUM in parallel to produce the result: Figure 8: Parallel Composition of MAX and SUM

        High-level non-sequential should technology should make the above construction simple. Here is a historical tour through the ways a DFD can be turned into code.

        Batch Processing

        Hardware and software constraints on early machines forced processes to be programs and data to be files - batch processing [Hares90] p44. Each process had to be a separate program and each store and entity a file [Martin85]. Comparatively simple programs collate several input files and generate other files from them. Many of these programs are needed in turn to fulfill a particular business function.

        Figure 9: Batch implementation

        This approach has advantages: The coupling between separate programs was low and implementation decisions were well hidden by the files. Testing was simple because no stubs or scaffolding were needed. The disadvantage is that a whole batch must be processed at a time. So an efficient design would pack many functions into one program - lowering its cohesion.

        Pipes

        Dividing a design into programs and files gives us independent modules with well defined interfaces. UNIX pipes can replace some files when ever the DFD is a "pipeline"(Figure 10). These lead to standardized general purpose components that fit together in different ways to solve many different problems [Udell94].

        For example:

         	ls -s|sort -n|tail
        Figure 10: UNIX Pipeline

        lists the ten largest files in a directory. The same components can be reorganized into:

         	ls -s|tail|sort -n
        that lists the ten files that are last alphabetically in order of increasing size [May94].

        When a complete suite of compatible programs becomes a separately maintained subsystem then we get a megamodule [WiederholdWegnerCeri93]. Recasting algorithms as objects and processes can also make the result more efficient and also more reusable [Weideetal94b].

        However the UNIX Pipe has limitations. The parallel combination of DUP, MAX and SUM of figure 8 above has to be written either

         		tee /tmp/store|MAX; SUM </tmp/store; rm /tmp/store
        or
         		tee /tmp/store|SUM; MAX </tmp/store; rm /tmp/store

        Structured Design

        An alternate way to convert a DFD into a running program was to convert it into a hierarchy of functions. This idea became the Structured Design method (SD). SD transforms a design drawn as a DFD into a tree of subroutines [Diaz-Herrera93]. SD used heuristics to select a process to be root. Data flows defined the branches, but some flows are some ignored or rerouted by the designer. Each process becomes a subprogram and the data flows define parameters. The designer uses intuition to place selections and iterations on the resulting "structure diagram" [Bergland81]. This approach has been criticized [Diaz-Herrera93]. James Martin, states that although the DFDs as used in SA can disentangle a complex system, they lead to ambiguous and erroneous designs if not backed up by "rigorous functional decomposition"(section 2.2.1 above) and "data analysis"(section 3.5 below) [Martin85]. The Cleanroom method is a rigorous form of decomposition, inspired by cybernetics (black box, white box, state box), and easily displayed using DFDs. Song and Osterweil use rigorous functional decomposition to compare methodologies [SongOsterweil94].

        There are less well known alternatives to SD for converting a DFD design into code. These are next.

        Co-Routines

        If there is a tool that transforms a batch version into a real time version then a batch version is a worthwhile prototype. It is easy to speed up simple batch systems directly when you use co-routines as in Conway's 1963 "Separable Diagram Compiler" or the COBOL SORT verb. Knuth traces co-routines back to 1958 [Knuth69]. Knuth, Floyd, Dahl, and others have shown that co-routines can give simpler solutions than subroutines [Knuth69] [Dahletal72] [FloydinACM86] [ NON-SEQUENTIAL in subjects ] They were mentioned in the original work on SD [StevensMyersetal74] and Structured Programming [Dahletal72] but then vanished from sight. Perhaps because co-routines come in pairs and so it is not easy to use them with hierarchical code.

        Restartable Subroutines

        Michael A. Jackson therefore developed restartable subroutines as part of his JSP method (section 3.3 of this chapter). These are invoked like other sub-programs but hide a simple mechanism to restart them after their last exit [Appendix 2]. They are also called semi-co-routines [Robinson79] or co-functions [ ICON in subjects ]

        Each return saves the state of the routine and each call recovers this sate and restarts the routine after the return. Each return is actually a suspension point. In JSP a module is designed as a free standing process with a number of input and output channels. When coded, one channel is selected and its input or output commands are replace by suspension points where the routine waits for the data, or waits for the data to be processed. Jackson's semi-co-routines have exactly one process operational at a time, because whenever data is transferred, one process suspends and another starts up [Jackson78]. Such a schedule is safe and easy to compile [BrinchHansen81] [BrinchHansen83]. As a test consider the problem of reusing SUM and MAX in a program that calculates both without altering their design. Suppose that SUM and MAX were coded as semi-co-routines that suspend whenever they need data then we just code DUP to take each item in turn and pass it in a normal function call to SUM and MAX. Because they are restartable they remember where they are and their internal state. They can even output the results for us. The catch is that there are few languages that support this elementary type of module.

        The above technique can be used whenever the processes in the DFD form a tree [JSP Course materials]. Many problems need only tree structured DFDs. Further, DFDs that are not trees can be split into separate "passes" or phases each of which is tree-structured. For example the DFD of a compiler(above) was not a tree. A compiler is typically split into two passes or phases, as shown next:

        Figure 11: Classic Compiler Scheduling

        In the above the lexer is typically written as a finite state machin but is coded as a subroutine. The parser is often written as a grammmar and coded with calls to the lexer subroutine. The parser produces a complete program structure and a dictionary of names. The generator then uses these data structures to produce the object code.

        Threads

        Recently a new form of simulated concurrency has become popular - threads. In the original form the word thread appears as an operating system concept which allows the system program focus on the sequential logic of a process even if it is continually suspending itself and then later be being restarted. By separating the program into pure (read only) code and data a single logical process can be used by many unrelated "threads of control." This concept fits well with Jackson's semi-coroutines and he shows that multithreaded code can simplify the logic of a program that has to handled a stream of interleaved data [Jackson75]. Apparently complex concurrent designs like Hoare's Sieve are easy to design and code using this idea.

        The idea of a piece of code that can suspend itself appears in Java as a "Thread". It is easy to make Java threads behave like Jackson semi-co-routines. Java also provides a mechanism for connecting a pair of threads by a pipe [Flanagan96] pp135-139. However, it is common for a programmer with no training in concurrent programming to have problems in Java because of uncooperative threads that fail to suspend themselves [ [Usenet news:comp.lang.java 1995-96, abstracted and archived at ] [ java.mbox ] ].

        Summary

        So using pipes, sorts, semi-co-routines and judicious scheduling an engineer can implement a DFD of logically parallel processes directly. He or she will discover the following advantages:
        • First, interactions between processes use a documented protocol.
        • Second, each part can be torture tested by connecting a standardized random test generators [MillerFredricksenSo90].
        • Third, the designs are closer to the user's world [Jackson75] [Bergland81] [Floyd86] [Fosteretal91] [Gelernter91].
        • Fourth, changes in one part of the user's problem will be changes in a single part of the solution [Jackson75].
        • Fifth, it is easy to parameterize small problems and write general re-usable processes with the parameters supplied at run time [UNIX and C command line arguments] or at compile time [Ada generics, ML functors, GenVoca Components], So, the parts in a DFD are often available as "off the shelf" programs.
        • Sixth, prototypes can be thrown together using shell scripts [Gancarz95].
        • Seventh, the design can be distributed over a network of processors [Jackson75].
        • Eighth, the result can be easier to understand and reuse and (potentially) more efficient than a pure sequentially structured program [Weideetal94bp88].

        Fear of Parallelism

        Computer scientists are encouraged to avoid parallel processes because of the difficulties in reasoning about them in general [Apt88]. It is clear that in some systems ignoring the timing of events can lead to errors [Ryant95] for example. For example:

        Figure  6. Sample DFD of a Coding

        The above DFD permits the compiler to process a source file that the coder is editing. The results could be problematic. This kind of problem that has spawned many doctoral dissertations. But humans automatically schedule editing and compiling so that they do not access the same source code at the same time. Humans did this easily when compilations took minutes rather than seconds. The source code was split over several modules and the compiler compiled one module in the background while the coder worked on another module in the foreground.

        So, simple DFDs can be programmed and/or scheduled to avoid the complexities [KahnMacQueen77] [Grune77] [Jackson80] [ChandyMisra88] [Fosteretal91] [Shopiro??]. A correctly structured network of correct processes can be shown to implement a given specification [see CSP , CCS , and chapters 4 and 5 for samples]. It is possible to reason about a DFD's termination and correctness without knowing very much about the nodes in the DFD [GoudaHerman91] [Lamport90a] [AbadiLamport9093] [Shankar93] See [ TIMING in my bibliography]. In this case we can say that the DFD is modular. Here reasoning is much simpler - almost trivial and intuitive for most practical situations.

        Further, certain data flow systems always have behavior that is timing independent. For example, [KarpMiller66] show that if functions are connected by FIFO queues and always read and write the same amount of data(or are blocked if not available) then the interleaving of processes cannot effect the final outcome. Since a state can be stored in a queue that loops from a function to itself, the result still holds if we have processes with internal states.

        Similarly [HoltCommonerEvenPhueli71] prove powerful results for Marked Directed Graphs that are special Petri nets very similar to Karp amd Miller's Computation Graphs. Both have the restriction that a node can not choose where it gets its input from. On each initiation, data (tokens) are taken from every input and produced on every output for that node(transition). As a result there is some elegant mathematical result that can be shown about what configuations are possible. However, this outlaws a common and useful form of DFD process that collates one or more streams of data. For example suppose we have two sources for integers (or other key data) that are sorted. We want a process that outputs the items in order from both streams. A simple algorithm (balanced line merge) reads one item from each stream and then repeatedly outputs the minimum item and replaces it by a new item from the same stream. For example,
        Table
        Input1Input2Output
        343
        5-4
        -75
        6-6
        12-7
        -88
        -99
        -1010
        Etc.

        (Close Table)
        The dashes in the above table show the process ignoring and input. This can not be done by a node in a "Computation Graph" or a transition in a "Marked Directed Graph". A Petri net with places and transitions doesn't have this constraint. For more on Petri nets and other models see [ math_76_Concurency.html ] my notes on the subject.

        The following would allow most useful DFDs:


        1. (A1): No Shared storage: All communication between processes is via buffered data flows(eg pipes).
        2. (A2): Blocking input: A process is suspended if no data is waiting. It cannot find out if there is data waiting.
        3. (A3): Non-blocking output: A process always succeeds in sending data. It cannot find out what happens to it.
        4. (A4): No Races: Each stream of input into a process comes from only one other process at a time.
        5. (A5): Terminated input: There is a recognizable signal placed after the end of each data flow.

        There has been much work on the avoidance of critical races( property (A4) above) [KaramStanczykBond89] [McNameeOlsson90] [WardMellor92] [NetzerMiller92]. New theories without buffering [ChandyMisra88] [Staskauskas93] [KayReed93] [Kurki-Suonio94] [LamShankar94a] [Jonsson94]. These suggest the following rules will make a DFD modular:


        1. (S1): Simple Processes: Each process can select one of a set of input or output actions that are valid at that time.
        2. (S2): Parallel Actions: Only one action is selected but it can change several state variables simultaneously. Each action is output by one part. But each can trigger input to many parts.
        3. (S3): Non-blocking output: A part has sole control of its outputs. Output always succeeds.
        4. (S4): Blocking input: A process can not control (reject or select) its input.
        5. (S5): Fairness/Justness: The scheduling guarantees that all inputs are eventually consumed.

        If a data store - or for that matter - if any resource (a printer, a disk,...) is shared between two processes then the access to it has to be controlled. Shlaer & Mellor suggest practical ways to do this (see pages70-82 of [ShlaerMellor92] ). Owicki & Gries developed conditions for data sharing to work [OwickiGries76]. The Linda tuple space is cleverly designed to let a great many processes communicate and share data in many ways [CarrieroGelernter89]. However shared data contributed to a deadly bug [LevesonTurner93] and the developers of the Space Shuttle Software regretted their uses of shared data [SpectorGifford84] pages 898-900. Hoare stated
          " [...] pure storage should not be shared in the design of a system using concurrency"

        [Hoare83] p 205, section 6.3. Further see the "Law of Demeter":
          "One should not retrieve a part of an object and then perform an operation on that part, but should instead perform the operation on the original object, which can implement the operation by delegating it to the part" [Wirfs-BrockJohnson90].

        Thus a node in a DFD should be designed to
        • (1) do what is needed (eg: to count events, or to keep track of some entities and/or relationships) and
        • (2) control access to its data [Magnusson90].
        Jackson System Development -- -- --(JSD)
        uses this approach ( For more see JSD ). So does Ada 83 (with tasks) and Ada 95 (with tasks and protected data types). Data base management system must also resolve this problem [see below for more on DBMSs]. Simple ways of controlling and synchronizing data are critical to distributed systems, data bases, client/server technology, groupware, and even small mobile computers [West95].

        Similar problems occur when developing software! Consider the example of DFD(above) where a coder edits source code that is compiled into object code. A single coder can control the urge to compile a module that is being edited! But suppose that there are several coders. Then the source code files must be put under the control of a Source Code Control System(SCCS), Revision Control System(RCS), or some other from of configuration management to make sure that no module is compiled in an out-of-date form or is simultaneously modified by two people at one time.

        Performance Problems in Concurrent DFD designs

        To describe the structure of a solution as a DFD does not guarantee that is fast enough. The data flows may have to be annotated to indicate how closely coupled two processes have to be. Most systems are only predictable when they handle events/transactions much faster than they happen631 [KayReed93] and pp126-128 of [Gelernter91]. When the queues grow too long then the system will cease to perform satisfactorily [SmithCU93]. So a key requirement is that the average rate of objects entering a flow is less than the rate at which they are consumed [Olsen93] [Olsen94]. Checking that a component completes a task in a satisfactory time is a necessary part of the software process. For examples see [Luqi92], the Physical Design Control step in SSADM (1982) [SmithCU93] [Gelernter91]. There is a well-established literature on the scheduling of real-time systems See [ See TIMING in my bibliography]. Termination and speed can be treated separately from correctness, however [Kurki-Suonio94] [AbadiLamport90] [AbadiLamport94]. Time can be factored out, compare [Dijkstra68]. Jackson has rules in his methods (JSP & JSD) to minimize "deadlock" and "live-lock." Gelernter's Trellis architecture combines a classical cybernetic "Design for a Brain" [Ross Ashby, Beer] with a performance specification [Gelernter91]. Theoretical treatments include: "liveness" [Lamport86b] [Baetan90] in page 13 by J A Bergstra & J W Kop, [AbadiLamport93], justice and fairness [Frances86] [Shankar93] [Jonsson94]] progress, [ChandyMisra88] [Staskauskas93], performance, [ShawB75], queuing theory [Olsen93] [Olsen94] [SmithCU90] [SmithCUWilliamsLG93], and simulation [LeonardDavis95].

        Some are working on proving correctness and speed at the same time [KayReed93]. Sometimes it may be necessary to specify one of these cases: (1) communication is synchronous, (2) a one process waits for the other process complete a process(Ada rendezvous), (3) only one process can run at a time and control is passed along with data(JSP, Edison, Icon), or (4)one process waits until a response is sent back on a different flow ["conversational constraint" JSD] cf [Shankar93] pp252-253.

        In practice performance is dominated by the interaction of (1) the hardware, (2) the physical placement of data, (3) the sequence of data access, and (4) caching [SSADM82] [Botting88] [Bentley93] [RuemmlerWilkes94] and [ PERFORMANCE in my bibliography]. But, as in the design of data types(Abstract vs Implemented) looking for a satisfactory physical design is often best separated from determining the conceptually correct structure(section 3.4 below).

        A prototype can have a simple but inefficient schedule, and let the implementor develop faster versions [as in [Kowalski79]. If the hardware is available then the processes can be distributed over several processors and run in parallel. The architectures vary from client/server through to massively parallel. Complex networks and tighter schedules need extra design work to ensure safety, liveness, and no race conditions [ArnoldTFuson94]. But several calculi and some tools help analyze and verify networks of communicating processes (see CSP , CCS , and Lamport (in my bibliography)). There are many examples of complex systems being implemented successfully [ArjomandiFischerLynch83] [Upson90] [Herbertetal.90]. Appendix 2 has some examples of simple non-sequential code. Many people have published examples of non-sequential designs [McKeagMilligan80] [HehnerSilverberg83] plus other citations under [NON-SEQUENTIAL]. In chapters 3 and 4 I will give theoretical reasons for using parallelism as a design structure.

        Implementations of Non-sequential DFDs(Alphabetical order)


        Net
        1. Ada Tasks [ ADA in subjects ]
        2. Adaptive Parallelism & Piranha [Carrieroetal95]
        3. Distributed code connected by Sockets [ UNIX ]
        4. Distributed code connected by RPCs [ArnoldTFuson94]
        5. EDISON modules [BrinchHansen81,BrinchHansen83]
        6. Generators [LiskovGuttag86]
        7. Icon co-functions [GriswoldGriswold83]
        8. Iterators [Lamb90]
        9. Jackson semi-co-routines (COBOL,PL/I,FORTRAN) [Jackson75]
        10. Java Threads+Pipes [??]
        11. Linda Tuple-spaces [CarrieroGelernter89]
        12. Mail Enabled Applications [Chisholm94bc]
        13. McIlroy's pipes + Named pipes and FIFOs [Ritchie80] [ATTBellLabs] UNIX
        14. MENDEL Objects [Honidenetal94]
        15. Mentat persistent classes [Grimshaw93]
        16. Mirror Worlds [Gelernter91]
        17. Modula II Co-routines
        18. Multi-processor solutions [Abbotetal93] OCCAM
        19. Simula processes [Palme82]
        20. Streams [Nakataetal91]
        21. The C++ Task Library [StroustrupShopiro]

        (End of Net)

        Like a circuit diagram Concurrent DFDs are for documenting a design. They are not a design method and they don't record why the design is the way it is. They do not determine (1) how data is structured, (2) how it changes, and (3) how it is implemented. They can implemented directly by modern programming tools. Later ideas help with these three kinds of decision.

      . . . . . . . . . ( end of section 2.6 From DFDs to Code) <<Contents | End>>

      2.7 Objects

        Parnas's idea of hiding design decisions is often misunderstood. For many it means "encapsulation": that a module should control access to a private data structure. During the late 70's and early 80's the focus of methodologists shifted from the level of steps, operations, algorithms, to data, then to packages, and then to objects [Winograd79]. Robin Milner: "Object oriented programming is a wonderful example of how fruitful things don't happen very precisely. That is, the programming community has come up with this tantalizing, powerful and productive way of thinking that is obviously with us to stay because it gives people just what they want. But at the same time its very difficult to understand mathematically and semantically [...]." p95-96 [Frenkel93] We now have many languages which work at the level of packages and objects including: Smalltalk [Kay1977], Eiffel [Meyer90] [Meyer91] [Meyer92] [Meyer93], C++ [ManesMurphy93], Hypertalk [CoulourisThimbleby93], Ada 95 [Ada95], Object-Oriented Pascal [ISO1995?], Java [??], etc. Objects are said to be a new paradigm: An object is a self contained (encapsulated ) piece of a program with variables, code, input/output, and objects of its own. Objects are said to provide services to other objects and/or entities called its clients [CORBA]. In this book objects get requests for services by being passed messages - others talk of calling an object's member functions(C++), or executing a module's procedures [Wirth95]. The set of messages defines the object's interface with other objects in the system. Objects are grouped into classes by the rule: objects of a given class provide equivalent services. Each class of objects has a set of methods that define how objects of that class react to messages. Classes can inherit the methods of other classes - their parents or base classes. An object can also inherit variables from its parents. A programmer can rapidly make new classes from old ones by using inheritance. Others call this extension [Wirth95] compare Ada 95, Java ??. Some languages distinguish two forms of inheritance: extension and implementation. In Implementation a parent class presents the same interface to the outside world while its children have different implementations(polymorphism). There are many ways this is achieved: run-time searches(Smalltalk), virtual functions & RTTI(C++), etc. A parent class can also be abstract (Smalltalk, ISO Object Pascal, Ada 95, Java). Abstract classes have at least abstract method. An abstract [C++, Java ??] or deferred(Eiffel [Meyer93]) method has an interface defined in a base class but its body is defined only by the child classes. Different children can define the abstract method to different things. Powerful tools are available for constructing and analyzing classes [Cox90a] [Cox90b].

        ==============================

        ______________________________

        ==============================

        There are partial but popular implementations of this technology: Object based systems use only encapsulation and abstraction - without inheritance and polymorphism. Microsoft's popular OLE/COM is an example as are VBXs in Visual Basic.

        Notice that the idea of generic module (see above) also applies to classes - for example a single C++ template can describe an infinite collection of classes with similar services and inheritance. A formal model of objects is developed in chapter 6. An object is persistent if it appears to survive the termination of its clients. Collections of interrelated persistent objects are a kind of data base [GrayPetal92]. An object, class, or system is distributed if the physical processor handling it can be changed transparently [Meyer93]. Distributed object-oriented systems are still at the laboratory stage [Mulhauseretal93]. Given enough "intelligence" distributed persistent objects can be thought of as software agents. Objects are conceptually parallel: Robin Milner: "[Object oriented programming ] naturally talks about objects that coexist and must therefore be allowed to behave simultaneously. That's parallelism or concurrency." [Frenkel93] Concurrency raises new problems when two tasks both attempt to operate on a resource at one time. A standard solution is a monitor. A monitor is an object with mutual exclusion. This means that only one request will be serviced at one time and other requests are processed later [BuhrFortierCoffin95]. Java allows a programmer to indicate that a statement, a method, or a class is synchronized - executed by only one thread at a time. There has been much work on concurrent object oriented programming: Special Issue of the Communications of the ACM Vol 36 n9(Sep 93)pp34-139 [Agharetal89] [BahsounMerzServieres93] [Caromel93] [DavisMorgan93] [GulAgha90] [LamShankar93](Conclusions) [Lohr93] [Meyer93] [Mulhauseretal93] [Wegner92] [WyatKaviHufnagel92]. In this book only simple concurrency is needed: I distinguish dynamic objects from non-dynamic objects. Non-dynamic objects react to a message by entering a piece of code(a method) at the beginning. A dynamic object uses hidden state variables to restart a process as if the process had been interrupted just as it finishes handling the last message [Agha90]. In a sense these objects politely interrupt and suspend themselves when part of there task is done. Dynamic objects combine the advantages of object- orientation with the simple parallelism of semi-co-routines. In theoretical terms a dynamic object is an automata. Jackson recommend there use for handling interleaved streams of data [Jackson75] and hence streams of events in time [Jackson83]. Berzins and Luqi use the terms mutable types and machines for dynamic objects [BerzinsandLuqi91]. Others call them active objects [Magnusson90], persistent objects [Grimshaw93], or processes. C++ constructors and destructors are step in the direction of dynamic objects.

        A structured dynamic object has one or more threads of control each expressed as a structured program that "describes the life-time behavior of an active object" [Magnusson90]page 88. An unstructured dynamic object uses an explicit state variable to get a similar effect - perhaps documented by a State Transition Diagram. A dismemebered dynamic object tries get a similar effect by providing a multitude of methods each representing (as a structured program) the behavior in the different states. The State pattern of Gamma et al [pages 305-313] dismemebers the dynamics of a class across a tree of subclasses allowing "an object to alter its behavior when its internal state changes." Dismemberment makes it difficult to reverse engineer the logical dynamics from apparent structure of the code. A dynamic monitor is a monitor that is also a dynamic object and so has a single-thread of control in it at one time.

        Ada 83 provided Task Types as an implementation mechanism for fully concurrent structured dynamic objects. Ada 95 added protected data types as a light weight variation. Java provides the Thread class that can be used to express structured dynamics. Michael Jackson's JSP has shown how structured dynamic objects can be coded in sequential languages by inverting them [Appendix 2]. JSD and SSADM design systems as networks of persistent structured dynamic objects - dynamic objects with the process expressed as a regular expression that save their states in secondary storage [ See JSD and SSADM in my bibliography].

        Proponents of objects claim that object technology will reduce problems of maintenance and user interfaces [Lawson90]. A recent paper describes benefits from object-oriented technology in three projects [Capperetal94]. However objects bring new problems:


        1. "Some of C++ most important features - classes, inheritance, and dynamic binding - can interfere with the ability of software developers and maintainers to understand the code they work with."..."Conventional tools...woefully inadequate when applied to C++ with its penchant for overloaded names, independent scopes that are not lexically nested, both static and dynamic object types"... [tools have to understand] "the semantics of class hierarchies and dynamically bound functions"... [and can]..."provide a qualitative improvement in the environment available to C++ programmers" [LejterMeyersReiss92].
        2. "Polymorphism and hierarchies lead to an explosion in the kinds of dependencies." [WildeHuitt92].

        3. "Polymorphism is a powerful and flexible programming mechanism, but like many others it presents opportunities for abuses [that] ruin program understandability. [...] the dispersal of operations across tiny procedures [...]exacerbates the difficulty inherent in understanding a large software system" [PonderBush94].

        4. " [...]OOT [Object Oriented Technology] has a nasty 'fragile base class problem,' which means that once a problem is designed and implemented as a class hierarchy, it is maximally coupled. [...] We are warned against this in 1975(minimize coupling, maximize cohesion). Coupling is a maintenance nightmare that bit Mentor Graphics(Falcon Framework) in the bottom line." [WillsT94].

        Research shows that if analysis and design documentation is missing then (1) experienced software engineers can not reconstruct a hierarchy of classes consistently [Dvorak94] and (2) maintenance is harder in an object-oriented system [WildeHuitt92] [Wildeetal93]. New kinds of errors are possible:
        1. "Despite a close correspondence between design and implementation, an Object-oriented program is complex. Inheritance introduces a new class of potential errors" [Jordan90].
        2. " [...] inheritance in object-oriented programs [...]might well come to be known as the GOTO of the 90's"p309 of [GoldsteinAlger92]
        3. " [...]the concepts in the real world, which programs attempt to model, do not come in neatly packaged hierarchies." [BaclawskiIndurkhya94]

        Many authors have pointed out the dangers of imposing a structure on a problem that is derived from the features of a particular language or implementation [ArnoldK94] [BaclawskiIndurkhya94] [GoldsteinAlger92] [Winkler92]. However this is the general problem of putting technique above reality: Humans tend to construct a reality that fits their language and expectations, including complex forms of inheritance (as in C++) or a large ready made hierarchy of classes (as in SmallTalk or the Java AWT).

        Some object-oriented proponents have seemed to ignore problems of correctness, reliability, and efficiency. Others are apparently ignorant of the literature as Constantine points out [Constantine95b]. For example: "Errors are all too frequent in coding, yet little attention has been paid to them in the programming literature" [Keffer93] p50

        Object technology does not choose the objects to be implemented:


        1. "Good objects are more difficult to write well for several reasons [...]" [ArnoldTFuson94]
        2. "Early object class library users have found they must exert extreme discipline to avoid unwanted effects [...] system crashes [...]inheritance problems [...]bulky recompilation." [Leinfuss93].
        3. "The bad news is that whenever inappropriate types of objects are selected, [...] the final architecture reflects these poor decisions." [Nerson93]page 36
        4. "The most difficult design task is to find the most appropriate decomposition of the whole into a module hierarchy, minimizing function and code duplication." [Wirth95]page 68
        5. "Specifications can turn out to be as unsuitable as implementations can turn out to be wrong." [Wirth95] page 68
        6. "High level class abstractions usually do not come first to mind" [Nerson93]Page 72
        7. "Unless developers agree on the definition of concepts, common identification of important entities will be infrequent [...]developers will classify concepts according to their own viewpoint." [Dvorak94]Page 60
        8. "We should expect it to be the norm, rather than the exception, when a category is applicable only to the problem in hand." [GoldsteinAlger92]page 101
        9. "Reusability is a result of effort(thinking) that occurs during the design activity of a software project and is largely uninfluenced by programmers' activities in the coding phase -- except for the possibility that incompetent programmers can foul up any design" [Racko94].

        Methodologists have tried fill the gap between the client and the design - see section 3.7 below.

      . . . . . . . . . ( end of section 2.7 Objects) <<Contents | End>>

      2.8 Agile and Extreme Processes

        Towards the end of the 20th century a movement started that took all the technical developments and took them to extremes:
        1. The design is the code.
        2. Don't let the sun set on bad code.
        3. Never program alone.
        4. Abandon all work that is not executable.
        5. Specify code by writing test code.
        6. And so on

        This movement has followed the bandwaggon growth of all previous movements and has had notable successes, just like previous religions. However, it is more about Process than Method. Starting with eXtreme Programming a number of other methodologists developed there own processes: all aiming to reduce the weight on the programmer. From this emerged the Agile Manifesto: [FowlerHighsmith01] and a the usual tidal wave of publications[ AGIL ]

        A key observation was made by Alistair Cockburn [Cockburn00] : any method/methodology/process can work, and any any can fail, depending on the motivation and skill of the people involved. This kind of terminates a lot of discussion of big methodologies.

        The other key change was that Gilb's idea of evolutionary delivery [Gilb88] works more often than not has entered the mainstream. In fact, history has been rewritten back to successful projects in the 1960's that (it now appears) used iteration and evolution to achieve success. [LarmanBasili03] for example. I have been advocating an iterative systems-approach since the earliest versions of the monograph. See [ 01_4.html ] below.

      . . . . . . . . . ( end of section 2.8 Agile Processes) <<Contents | End>>

      2.9 Conclusions

        First, modules are vital but flowcharts, PDLs/algorithms, and structured programming languages are a sequential models that encourage bad coupling and weak information hiding. Second, stepwise refinement, functional decomposition, functional programming, structured design, and information hiding have steps where the designer uses experience and intuition because the purpose of a module or program does not determine a unique structure [McDermid89] p4, pp122-133, p189, ... Third, objects changed the way software is constructed, but do not of themselves solve the problem of software design. Fourth: Technical methods work well when the problem is well understood and matches the techniques known to the programmer. They are the natural methods for most people - but notice that "natural" implies "untrained" and so "naive". Fifth: Technique is not enough when the problem is not understood or fails to fit a known technique. Sixth: In these methods the key parts of software development go on in the developers' brains [Posting by Rick Rowe 92, May 94] and tend to never get recorded. So: we need better rules for selecting structures/classes/types. It might also be wise to invest time and money in training good people in many small methods so that they can apply them, as needed, as the project proceeds.

      . . . . . . . . . ( end of section 2.9 Conclusions) <<Contents | End>>

      Next Section

      See [ 01_3.html ]

    . . . . . . . . . ( end of section 2 Technical Methodologies) <<Contents | End>>

End