[Skip Navigation] [CSUSB] / [CNS] / [Comp Sci & Eng Dept] / [R J Botting] >> [papers] >> rjb9Xx.TEMPO
[Index] [Contents] [Source] [Notation] [Copyright] [Comment] [Search ]
Tue May 12 11:06:30 PDT 2009

This part of my site contains partly baked ideas (PBI). It has drafts for publications, essays, plus illustrations and visual aids for presentations and seminars.

Disclaimer. CSUSB and the CS Dept have no responsibility for the content of this page.

Copyright. Richard J. Botting ( Tue May 12 11:06:30 PDT 2009 ). Permission is granted to quote and use this document as long as the source is acknowledged.


Contents


    Temporal Maps

      Author

      Dr. Richard J. Botting, Computer Science and Engineering Dept., California State University, San Bernardino 5500, State University Parkway, San Bernardino, CCA 92407.

      EMail: rbotting@csusb.edu

      URL: http://cse.csusb.edu/dick/papers/rjb9Xx.TEMPO.html

      Note the figures were orignially in PostScript generated on a Macintosh from MacDraw: http://cse.csusb.edu/dick/papers/rjb9Xx.TEMPO.figs.ps (Best viewed on Linux using Evince or Ghostscript). I have taken screen shots and placed them as GIFs in this (May 2009) update to the original paper.

      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.

      Introduction

        Background

        I have been looking into the relations between formal, executable, natural , and graphical documentation[Botting85, Botting87, & Botting89]. 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 [Graf89]. It is now possible to execute graphical representations of processes[ Herbertetal90, Upson90, Hareletal90]. Structured graphics of software have been shown to be worthwhile [ Pagan83, AmblerBurnett89, LiuHorowitz89, Scanlan89, Aoyamaetal89, Chang89, Wassermanetal90].

        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[Zelkowitz90], And/Or tables[Levesonetal95] 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[ShahookarMazumber91]. 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[Moen90]. Directed Acyclic Graphs(DAGs) - typically ERDs - are harder to produce automatically [DingMateti90, p281 in Berztiss89] but Martin and McClure have published a simple levelling heuristic[ MartinMcClure85]. Yet some ERDs will defeat all attempts at tidying. They can form non-planar forms like a Kurotaski 3><3 graph - see Figure 1.1 below.

        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[Lano77] - See Figure 1. 1. This N^2 layout wastes space but exposes structure (cf SADT layout and the LDST technique in SSADM[Cutts88]). See Figure 1.1.

        [Digraph and N-square notation]

        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.

        [Three Dimensions -- time >< possibility >< space]

        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[Cameron89] and SSADM[Cutts88]. They are more structured than diagrams proposed for objects[Olenfeldt85, Hareletal90, ShlaerMellor92]. 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>>

      Description of TEMPO

        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[Witty76, Witty77 ]. The TEMPO version requires the components to be boxes that fit together. Figure2.1 shows the evolution of the TEMPO rules.

        [Evolution of temporal mapping of sequential structures]

        Sets

        TEMPO shows sets like {a, b c, ...} as an ellipse or blob. A blob is a box with rounded corners[Harel86, Harel88, HarelKahanna92, Hareletal90, ColemanHayesBear92, Rumbaughetal90] . 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 describing erroneous cases. See Figure 2.2.

        [Set operations shown as blobs]

        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 Zelkowitz90]. See Figure 2.3.

        [Proofs using Tableaux]

        [Proofs using Algebra of temporal maps and dynamic relations]

        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's 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.
      1. f : A -> B. 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.4a.

        [Functions and Cartesian products]

        It is also possible to (1) show that many objects have similar behavior -- belong in the same class, (2) show correspondences between parts of parallel processes that should be synchonized, and (3) show many-to-many relationships. See Figure 2.5b.

        [Objects + Correspondences + Relations]

        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

        [Functions and Cartesian products]

        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 Milietal91]. 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 temporal 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.

        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

        [Sequential Semantics from Regular Expressions]

        The standard semantics of 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 message passing semantics which works well for everyday problems but avoids tackling problems of hazards, dead lock, and live lock[Jackson76, Jackson78, & Jackson80]. Lamport's approach to concurrency, Hoare's CSP or Robin Milner's work are candidates for a semantics that handles scheduling problems[Lamport86a, Lamport86b, Hoare85, Milner80].

        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.

        [Planar Programming and Zahn Loops]

      . . . . . . . . . ( 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>>

      Bibliography


        (AmblerBurnett89): A L Ambler & M M Burnett, Influence of Visual Technology on the Evolution of Language Environments, IEEE Computer v22 n10 (Oct 89)pp9-22


        (Aoyamaetal89): M Aoyama & K Miyamoto & N Murakama & H Nagano & Y Oki, Design Specification in Japan: Tree Structured Charts, IEEE Software v6n2(Mar 89)pp31-37


        (Berztiss89): Alfs Berztiss, Formal Specification Methods and Visualizations, in Chang 89 pp231-290


        (Botting85): R J Botting,An Eclectic Approach to Software Engineering, pp25-29 Proc Third Int'l Workshop on Software Specification & Design Aug 1985


        (Botting87): R J Botting, A Critique of Pure Functionalism, pp148-153 Proc. Fourth Int'l Workshop on Software Specification & Design April 1987


        (Botting89): R J Botting, Abstract of Research, Proc ACM CSC Conf 1989


        (Cameron89): John R Cameron, JSP and JSD: The Jackson Approach to Software development(2nd Edn), IEEE Comp Society Press CA 1989


        (Chang89): Shi-Kuo Chang(ed), Principles of Visual Programming Languages, Prentice Hall Int. Englewood Cliffs NY 1989


        (ColemanHayesBear92): 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


        (Cutts88): Geof Cutts, Structured Systems Analysis and Design Methodology, Van Nostrand Reinhold NY NY 1988


        (DingMateti90): Chen Ding & Prabhaker Mateti, A Framework for the Automated Drawing of Data Structure Diagrams, IEEE Trans SE16 n5 pp543-557(May 90)): CR9207-0512


        (Graf89): Mike Graf, Building a Visual Designers Environment, pp291-325 of Chang 89


        (Harel86): David Harel, Statecharts: A Visual Approach to Complex Systems(revised), Report CS86-02 Dept App Maths Weizman Inst Science Rehovot Israel March 1986


        (HarelKahanna92): David Harel & Chaim-Arie Kahanna, On Statecharts and Overlapping, ACM TOSEM V1n4(Oct 92) pp399-422


        (Hareletal90): 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


        (Herbertetal90): Andrew Herbert & William Lively & Sallie Sheppard, A Graphical Specification System for User-Interface Design, IEEE Software V7n4 (Jul 90) p12-20


        (Hoare85): C.A.R. Hoare, Communicating Sequential Processes, Prentice Hall 1985


        (Jackson76): M A Jackson, Constructive Methods of Program Design, Lect Notes in C Sci vol 44 pp236-262 Springer Verlag Berlin 1976


        (Jackson78): M A Jackson, Information Systems: Modelling Sequencing and Transformation, pp72-81 in Proc. 3rd Interntl Conf on Software Engineering IEEE 1978


        (Jackson80): M A Jackson, Conventional Programming Language, pp321-342 Human Interaction with Computers Acad Press London UK


        (Lamport86b): Leslie Lamport, A Simple Approach To Specifying Concurrent Systems, Report 15 Systems Research Center Digital Equipment Corpn Dec 25th 1986


        (Lamport86a): 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


        (Lano77): 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


        (LiuHorowitz89): l.-C Liu & E. Horowitz, A Formal Model for Software Project Management, IEEE Trans Soft Eng vSE-15 n10(Oct 89)pp1280-1293


        (MartinMcClure85): James Martin & carma McClure, Diagrammatic Techniques for Analysts & Programmers, Prentice Hall Intl NJ 1985


        (Milietal89): A Mili & N Boudriga & F Mili, Towards Structured Specifying: Theory Practice Application, Ellis Horwood Chichester UK 1989(USA Distribution John Wiley & Sons NY NY)


        (Milner80): Robin Milner, A Calculus of Communicating Systems, Springer Verlag 1980


        (Moen90): Sven Moen, Drawing Dynamic Trees, IEEE Software V7n4 (Jul 90) p21-28


        (Olenfeldt85): Lars Olenfeldt, Object/Event Analysis, ACM SIGSOFT Software Engineering Notes v10n1 (Jan 85) p52-57


        (Pagan83): Frank G Pagan, A Diagrammatic Notation for Abstract Syntax and Abstract Structured Objects, IEEE Trans SE-9n3pp280-289


        (Rumbaughetal90): James E. Rumbaugh & Michael R. Blaha & William J Premeriani & Frederick Eddy & William Lorenson, Object-Oriented Modelling and Design,Prentice Hall Englewood Cliffs NJ 1990


        (Scanlan89): 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


        (ShahookarMazumber91): K Shahookar & P Mazumber, VLSI Call Placement Techniques, ACM Comp Surveys, V2n2(Jun91)pp143-220


        (ShlaerMellor92): Sally Shlaer & Stephen J Mellor, Object Lifecycles: Modeling the World in States, Yourdon Press series Prentice Hall NJ 1992


        (Upson90): Graig Upson, Tools for Creating Visions, UNIX Review V8n8(Aug 90)pp39-47


        (Wassermanetal90): AI Wasserman & PA Pircher & R J Muller, The Object-Oriented Structured Design Notation for Software Design Representation, IEEE Computer v23n3(Mar 90)p50-62.


        (Wassermanetal90): AI Wasserman & PA Pircher & R J Muller, The Object-Oriented Structured Design Notation for Software Design Representation, IEEE Computer v23n3(Mar 90)p50-62.


        (Witty77): Rob Witty, Dimensional Flowcharting, Software-Practice & Experience v7 pp553-584


        (Witty76): Rob Witty, Dimensional Flowcharting, Report RL-76-132/A Rutherford Lab. Chilton England 1976


        (Zelkowitz90): 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

        For a PostScript verion of the figures for this paper ( side ways on) see [ rjb9Xx.TEMPO.figs.ps ]

      . . . . . . . . . ( end of section Figures) <<Contents | End>>

End