Disclaimer. CSUSB and the CS Dept have no responsibility for the content of this page.
Copyright. Richard J. Botting ( Fri Jan 20 11:56:22 PST 2006 ). Permission is granted to quote and use this document as long as the source is acknowledged.
Author
Dr. Richard J. Botting
Richard J. Botting,
Computer Science Dept.,
California State University, San Bernardino
5500, State University Parkway,
San Bernardino, CCA 92407.
Phone: US. (909)-880-5327.
Fax: (909)-880-7004
EMail: rbotting@Wiley.csusb.edu, dick@silicon.csci.csusb.edu
URL: http://ftp.csci.csusb.edu/rjb9Xx.TEMPO.mth URL: http://www.csci.csusb.edu/rjb9Xx.TEMPO.html
Figures in PostScript: http://ftp.csci.csusb.edu/rjb9Xx.TEMPO.figs.ps
Themes
formal and conceptual modelling, temporal constraints, concurrency,
formal reasoning, design methods.
Abstract
I describe my experiences with graphics of models used in the
analysis, specification, and design of software. My goal was a
self-organizing diagram where the parts have a position determined
by the logic of the problem not the aesthetics of the drafter. I
propose a notation fits into the informal, formal and semi-formal
methods found in the software process. It is probably better to
use it as an interactive interface than as a graphical output.
Background
I have been looking into the relations between formal, executable,
natural , and graphical documentation[Botting 85, 87, & 89]. A
good diagram connects a powerful neural network (the eye-brain
system) to the problem. Mike Graf's observation of designers in
action shows they use visual symbols [Graf 89]. It is now possible
to execute graphical representations of processes[ Herbert et al
90, Upson 90, Harel et al 90]. Structured graphics of software
have been shown to be worthwhile [ Pagan 83, Ambler & Burnett 89,
Liu & Horowitz 89, Scanlan 89, Aoyama et al. 89, Chang 89,
Wasserman et al. 90].
Diagrams used in 20th century CASE systems are informal. They require the manual positioning of icons. Layout is a matter of taste not of semantics. So time is spent on meaningless aesthetics. A better representation would be formal and save time.
Sequential structures have a natural two dimensional layout. This was first proposed by Witty in the 1970s. Structured programs, regular expressions, and context free grammars, Jackson data structure diagrams and structure text, natural deduction proofs, Trace tables[Zelkowitz 90], And/Or tables[Leveson et al 95] and data dictionaries all fit this model. So a set of N concurrent structures require a 2N dimensional space to represent them. Concurrency is important for simplifying the representation of concurrent systems. If each of the N concurrent parts have only p possible states, an equivalent sequential picture can require p^N states.
Automatic circuit layout problems are NP-complete[Shahookar & Mazumber 91]. The problem of laying out diagrams of highly constrained and/or concurrent structures (such as Data Flow Diagrams(DFDs) and Entity_Relation_Diagrams(ERDs)) seems equally intractable. A tree structure is easy to draw once the root has been found and the levels identified[Moen 90]. Directed Acyclic Graphs(DAGs) - typically ERDs - are harder to produce automatically [Ding & Mateti 90, p281 in Berztiss 89] but Martin and McClure have published a simple levelling heuristic[Martin and McClure 85]. Yet some ERDs will defeat all attempts at tidying - see Figure 1.1.
An alternate heuristic is useful for diagrams which have large numbers of constraints between parts like a DFD. Here the parts are placed on a diagonal line. and interactions and couplings are put in off diagonal positions chosen to give a clock wise flow of influence[Lano 77] - See Figure 1. 1. This N^2 layout wastes space but exposes structure (cf SADT layout and the LDST technique in SSADM[Cutts 88]).
TEMPO
My notation is called TEMPO because it shows a "temporal map" of
sequential parts of a system. The idea is to place symbols above
each other if they are separated in time, and adjacent to when
they are alternatives. Concurrent (spatially separate structures)
would default to the N2 convention but their relative position is
not meaningful - See figure 1.2.
TEMPO diagrams fit into most methods. They include simplified DFDs and ERDs of structured analysis and design. They are more intuitive than Jackson's notations and could be used in JSP/JSD[Cameron 89] and SSADM[Cutts 88]. They are more structured than diagrams proposed for objects[Olenfeldt 85, Harel et al 90, Shlaer & Mellor 92]. They can be used at the highest and lowest views of a system.
These benefits do not come without costs. First, TEMPO is a formal notation with simple yet sophisticated semantics and so it takes time to learn. Second, it is not suitable for a manual updating. Third, its value increases with scale of the problem, and so it is hard to demonstrate its worth in a class or research paper. Fourth, it needs computerized tools. I am working on a formal specification of the system with a matching executable prototype.
. . . . . . . . . ( end of section Introduction) <<Contents | End>>
Sequential Structures
TEMPO has simple rules to automatically map any sequential
structure onto a rectangle or box. The box should be thought of
as a temporal framework describing possible sequence of events,
process, operations, etc. One dimension (normally the vertical
one) is associated with time. The other dimension with
alternatives and possibilities like Nassi-Schneiderman Charts
and Witty's Dimensional Flowcharting[Witty 76 & 77 ]. The TEMPO
version requires the components to be boxes that fit together.
Figure2.1 shows the evolution of the TEMPO rules.
Sets
TEMPO shows sets like {a, b c, ...} as an ellipse or blob. A
blob is a box with rounded corners[Harel 86, Harel 88, Harel &
Kahanna 92, Harel et al 90, Coleman Hayes & Bear 92, Rumbaugh et
al 90] . Elements can be anywhere inside. The blobs can overlap
to show intersections. A class of objects satisfying several
simultaneous structures (A&B& C...) is shown as a set with the
parts anywhere and with '&' in top left hand corner. Complements
(A ~ B) are shown similarly. Intersection is useful for expressing
context sensitive data and/or clashing structures. Complement
is good for errors. See Figure 2.2.
Logic
Proofs are shown by associating the vertical dimension with
deductions and the horizontal one with alternative cases.
Hypotheses open a new box. Deductions form a directed acyclic
graph connecting steps in the proofs. Program proving can be
done by reducing a sequential TEMPO diagram without loops toa
disjunctive normal form. Here the dimensions are associated with
conjunctions and disjunctions[ Cf Zelkowitz 90]. See Figure 2.3.
Entity Relationship Diagrams
In an ERD the sets of similar objects all exist at one time. In
TEMPO, ERDs must be simplified until only many-to-one
relationships connect the entities. Other types of relations are
transformed into entities(cf SSADM LDST). When relation f
relates each element in A to a unique element in a set B then A is
shown as a box below B and connected with a line labeled f.
Numbers can be placed at the lower end to show the numbers of
elements in A associated with each b in B. Labels can be omitted.
When the relation that is being drawn is "part of"(Cartesian
products/ record structures/...) then the components can be placed
inside the entity of which they are a part. See figure 2.4.
Data Flow Diagrams
A formal DFD is a special case of a semantic net. Arrows symbolize
couplings or constraints between sequences of data. Timing and
scheduling is handled by placing parts in a TEMPO framework. The
data flows are superimposed on this. Figure 2.5
Programs
A TEMPO framework is a not a program. It can be shown to
represent a specification of a program using non-deterministic
relational semantics[like in Mili et al 91]. It is easy to show
that TEMPO sequential frameworks are a generalization of the D-
structures. The conversion of the framework into source code
would be documented by overlaying the TEMPO chart with control
paths and other annotations.
Semantics
A TEMPO framework is defined as a picture of an expression in an
abstract algebra (either a semi-ring or a lattice) with 3
operators: - product, sum, and Kleene closure. The expression can
describe a language, a set of patterns, or a relation that forms a
simple but highly non-deterministic specification for a program.
The following procedure generates the expression for a simple
sequential framework:- A repeated structure is the Kleene
closure of its contents. A vertical sequence generates term which
is the product of the expressions of the boxes in the sequence.
All these path terms are summed. See Figure 2.7
Named structures can be recursive. So a named framework with named components gives a set of simultaneous equations. The standard fixed point approximation semantics or Arbib's Partially Additive semantics can be used to solve them. See Figure 2.7
The standard semantics of all constrained frameworks hasn't been fixed yet. When the parts are in a "blob" marked with an operator then that operator is applied(see section 2.2 above). Data flows have a simple asynchronous model which works well for everyday problems but avoids tackling problems of hazards, dead lock, and live lock[Jackson 76, 78, & 80]. Lamport's approach, Hoare's CSP or Robin Milner's work are candidates for a semantics that handles scheduling problems[Lamport 86a & 86b, Hoare 85, Milner 80].
Planar Programs
The algorithm for interpreting a sequential structure can be
generalized to: (1) A repeated structure is the Kleene closure of
its contents. (2) Each path from the top line of eeh box to the
bottom line, that proceeds only through horizontal lines and never
cuts through a horizontal line or a meeting of two lines generates
a product term of the parts the path goes through. (3)The path
terms are summed.
Given this algorithm then it becomes easier to show some structures that are unusually complex when written using the three structures.... and yet a general framework is clearly equivalent to a structured design. More importantly it is easy to see all the possible paths from top to bottom. This is a promising basis for a graphic CASE system. It appears that this may be a better way to interface with the engineer than using a textual code - because the diagrams are simpler. See Figure 2.8.
. . . . . . . . . ( end of section Description of TEMPO) <<Contents | End>>
Lessons Learned so far from TEMPO
Summary
TEMPO is a simple way to display sequential formal models as a two
dimensional framework. Concurrent systems of parts can be placed
freely. In a graphic environment the designer has a simple way
to express of complex logical and temporal patterns.
Conclusions
I wanted to save the time wasted making a diagram look good. The
logic of the problem can determine the appearance of the solution.
Regular, context free, or dynamic structures can be quickly and
easily converted into an elegant picture of the problem and/or
solution. The problem of having any set of formal definitions
converted into graphics does not seem tractable. Instead it is
probably better to provide a graphical interface that is
internally stored as a mathematical expression.
The Future
TEMPO defines a way to see and hence manipulate software
structure. It appears essential to proceed to an executable
prototype of the TEMPO notation to test its worth. If it proves
to provide an intuitive visual interface then it can be extended
to provide a three dimensional virtual world: Sequential plans,
pieces of logic, objects, data types, etc would appear as boxes
floating in space. Couplings, flows, and mappings would be seen
as pipes connecting the objects. An engineer would work by
exploring and modifying the structures and their connections.
Science fiction has named such a model "Cyberspace". Perhaps such
a world might become the most important way to build, monitor,
modify, and maintain complex software.
. . . . . . . . . ( end of section Lessons Learned so far from TEMPO) <<Contents | End>>
(Ambler & Burnett 89): A L Ambler & M M Burnett, Influence of Visual Technology on the Evolution of Language Environments, IEEE Computer v22 n10 (Oct 89)pp9-22
(Aoyama et al 89): M Aoyama & K Miyamoto & N Murakama & H Nagano & Y Oki, Design Specification in Japan: Tree Structured Charts, IEEE Software v6n2(Mar 89)pp31-37
(Berztiss 89): Alfs Berztiss, Formal Specification Methods and Visualizations, in Chang 89 pp231-290
(Botting 85): R J Botting,An Eclectic Approach to Software Engineering, pp25-29 Proc Third Int'l Workshop on Software Specification & Design Aug 1985
(Botting 87): R J Botting, A Critique of Pure Functionalism, pp148-153 Proc. Fourth Int'l Workshop on Software Specification & Design April 1987
(Botting 89): R J Botting, Abstract of Research, Proc ACM CSC Conf 1989
(Cameron 89): John R Cameron, JSP and JSD: The Jackson Approach to Software development(2nd Edn), IEEE Comp Society Press CA 1989
(Chang 89): Shi-Kuo Chang(ed), Principles of Visual Programming Languages, Prentice Hall Int. Englewood Cliffs NY 1989
(Coleman Hayes & Bear 92): Derek Coleman & Fiona Hayes & Stephen Bear, Introducing ObjectCharts or How to Use Statecharts in Object-Oriented Design, IEEE Trans SE-18n1(Jan 92)pp9-18, CR9301-0026
(Cutts 88): Geof Cutts, Structured Systems Analysis and Design Methodology, Van Nostrand Reinhold NY NY 1988
(Ding & Mateti 90): Chen Ding & Prabhaker Mateti, A Framework for the Automated Drawing of Data Structure Diagrams, IEEE Trans SE16 n5 pp543-557(May 90)): CR9207-0512
(Graf 89): Mike Graf, Building a Visual Designers Environment, pp291-325 of Chang 89
(Harel 86): David Harel, Statecharts: A Visual Approach to Complex Systems(revised), Report CS86-02 Dept App Maths Weizman Inst Science Rehovot Israel March 1986
(Harel & Kahanna 92): David Harel & Chaim-Arie Kahanna, On Statecharts and Overlapping, ACM TOSEM V1n4(Oct 92) pp399-422
(Harel et al 90): D Harel & H Lachover & A Naamad &A Pnueli & M Politi & R Sherman & A Ahtull-Trauring & M Trakhtenbrot, STATEMATE: A Working Environment for the Development of Complex Reactive Systems, IEEE SE-16n4pp403-414
(Harel 88): David Harel, On Visual Formalisms, Commun ACM v31n5(May 88)pp514-530
(Herbert et al 90): Andrew Herbert & William Lively & Sallie Sheppard, A Graphical Specification System for User-Interface Design, IEEE Software V7n4 (Jul 90) p12-20
(Hoare 85): C.A.R. Hoare, Communicating Sequential Processes, Prentice Hall 1985
(Jackson 76): M A Jackson, Constructive Methods of Program Design, Lect Notes in C Sci vol 44 pp236-262 Springer Verlag Berlin 1976
(Jackson 78): M A Jackson, Information Systems: Modelling Sequencing and Transformation, pp72-81 in Proc. 3rd Interntl Conf on Software Engineering IEEE 1978
(Jackson 80): M A Jackson, Conventional Programming Language, pp321-342 Human Interaction with Computers Acad Press London UK
(Lamport 86b): Leslie Lamport, A Simple Approach To Specifying Concurrent Systems, Report 15 Systems Research Center Digital Equipment Corpn Dec 25th 1986
(Lamport 86a): Leslie Lamport, Control Predicates are Better than Dummy Variables for Reasoning About Program Control, Report 11 Systems Research Center Digital Equipment Corpn May 5th 1986
(Lano 77): R J Lano, The N^2 Chart, TRW report(Software Series) TRW-SS-77-04(Nov 77) TRW Redondo Beach CA 90278 1977, Extract published as pp244-271 of Richard H Thayer & Merlin Dorfman(eds), System and Software Requirements Engineering, IEEE CS Press
Tutorial Cat No.EH0304-6
(Liu & Horowitz 89): l.-C Liu & E. Horowitz, A Formal Model for Software Project Management, IEEE Trans Soft Eng vSE-15 n10(Oct 89)pp1280-1293
(Martin & McClure 85): James Martin & carma McClure, Diagrammatic Techniques for Analysts & Programmers, Prentice Hall Intl NJ 1985
(Mili et al 89): A Mili & N Boudriga & F Mili, Towards Structured Specifying: Theory Practice Application, Ellis Horwood Chichester UK 1989(USA Distribution John Wiley & Sons NY NY)
(Milner 80): Robin Milner, A Calculus of Communicating Systems, Springer Verlag 1980
(Moen 90): Sven Moen, Drawing Dynamic Trees, IEEE Software V7n4 (Jul 90) p21-28
(Olenfeldt 85): Lars Olenfeldt, Object/Event Analysis, ACM SIGSOFT Software Engineering Notes v10n1 (Jan 85) p52-57
(Pagan 83): Frank G Pagan, A Diagrammatic Notation for Abstract Syntax and Abstract Structured Objects, IEEE Trans SE-9n3pp280-289
(Rumbaugh et al 90): James E. Rumbaugh & Michael R. Blaha & William J Premeriani & Frederick Eddy & William Lorenson, Object-Oriented Modelling and Design,Prentice Hall Englewood Cliffs NJ 1990
(Scanlan 89): David Scanlan, Structure Flowcharts Outperform Pseudocode: An Experimental Comparison, IEEE Software V6n4(Sep 89)pp28-29 also letters V7n1(Mar 90)pp4&6&10&117 V7n3(May 90)p99
(Shahookar & Mazumber 91): K Shahookar & P Mazumber, VLSI Call Placement Techniques, ACM Comp Surveys, V2n2(Jun91)pp143-220
(Shlaer & Mellor 92): Sally Shlaer & Stephen J Mellor, Object Lifecycles: Modeling the World in States, Yourdon Press series Prentice Hall NJ 1992
(Upson 90): Graig Upson, Tools for Creating Visions, UNIX Review V8n8(Aug 90)pp39-47
(Wasserman et al 90): AI Wasserman & PA Pircher & R J Muller, The Object-Oriented Structured Design Notation for Software Design Representation, IEEE Computer v23n3(Mar 90)p50-62.
(Wasserman et al 90): AI Wasserman & PA Pircher & R J Muller, The Object-Oriented Structured Design Notation for Software Design Representation, IEEE Computer v23n3(Mar 90)p50-62.
(Witty 77): Rob Witty, Dimensional Flowcharting, Software-Practice & Experience v7 pp553-584
(Witty 76): Rob Witty, Dimensional Flowcharting, Report RL-76-132/A Rutherford Lab. Chilton England 1976
(Zelkowitz 90): Marvin V Zelkowitz, A Functional Correctness Model of Program Verification, IEEE Computer magazine, V23n11(Nov 90)pp30-39
. . . . . . . . . ( end of section Bibliography) <<Contents | End>>
Figures
. . . . . . . . . ( end of section Figures) <<Contents | End>>