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
2.1 Modular Programming
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)
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:
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
-- type assertion is defined elsewhere;
-- type step_type is defined elsewhere;
type specification is
record pre-condition, post-condition: assertion;
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
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
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 loop DECOMPOSE;
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:
"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."
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?
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.
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:
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].
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>>
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:
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
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
"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]
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].
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 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."
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)
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
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]).
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:
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:
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.
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.
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.
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
Hartmannis and Stearns give calculations for validating and generating these decompositions automatically.
. . . . . . . . . ( end of section 2.5.3 A little theory) <<Contents | End>>
. . . . . . . . . ( 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
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
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.
Hardware and software constraints on early machines forced processes to be
programs and data to be files - batch processing
Each process had to be a separate program and each store and entity a file
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.
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.
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
ls -s|sort -n|tail
lists the ten largest files in a directory. The same components can be reorganized into:
ls -s|tail|sort -nthat 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/storeor
tee /tmp/store|SUM; MAX </tmp/store; rm /tmp/store
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
[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
There are less well known alternatives to SD for converting a DFD design into code. These are next.
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
[ NON-SEQUENTIAL in subjects ]
They were mentioned in the original work on SD
[StevensMyersetal74] and Structured
[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.
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:
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.
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
[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 ] ].
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:
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.
prove powerful results for Marked Directed Graphs that are
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,
The following would allow most useful DFDs:
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:
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
and pp126-128 of
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
[Olsen94]. Checking that a component completes a task in a satisfactory time is a necessary part of the
software process. For examples see
Physical Design Control step in SSADM (1982)
[Gelernter91]. There is a well-established literature on the scheduling of real-time systems
See [ See
in my bibliography].
Termination and speed can be treated separately from correctness, however
[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:
[Baetan90] in page 13 by J A Bergstra & J W Kop,
[AbadiLamport93], justice and fairness
[ShawB75], queuing theory
[SmithCUWilliamsLG93], and simulation
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)
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>>
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:
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:
. . . . . . . . . ( end of section 2.7 Objects) <<Contents | End>>
2.8 Agile and Extreme Processes
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>>
. . . . . . . . . ( end of section 2.9 Conclusions) <<Contents | End>>
[ 01_3.html ]
. . . . . . . . . ( end of section 2 Technical Methodologies) <<Contents | End>>