Algorithmic Language and Program Development

The title of this book contains the words ALGORITHMIC LANGUAGE, in the singular. This is meant to convey the idea that it deals not so much with the diversity of program­ ming languages, but rather with their commonalities. The task of formal program develop­ It allows classifying ment proved to be the ideal frame for demonstrating this unity. concepts and distinguishing fundamental notions from notational features; and it leads immediately to a systematic disposition. This approach is supported by didactic, practical, and theoretical considerations. The clarity of the structure of a programming language de­ signed according to the principles of program transformation is remarkable. Of course there are various notations for such a language. The notation used in this book is mainly oriented towards ALGOL 68, but is also strongly influenced by PASCAL - it could equally well have been the other way round. In the appendices there are occa­ sional references to the styles used in ALGOL, PASCAL, LISP, and elsewhere.

0.1 On the Etymology of the Word Algorithm.- 0.2 How Algorithms are Characterized.- 0.3 Programming as an Evolutionary Process.- 0.4 How to Solve it.- 1. Routines.- 1.1 The Parameter Concept.- 1.2 Declaration of a Routine.- 1.3 Hierarchical Construction of Routines.- 1.3.1 Primitive Routines and Computational Structures.- 1.3.2 The Principle of Substitution.- 1.3.3 Alternatives.- 1.3.4 Input/Output.- 1.4 Recursive Routines and Systems.- 1.4.1 Examples.- 1.4.2 Proof of Termination.- 1.4.3 Taxonomy of Recursion.- 1.4.4 The Level of Applicative Formulation.- 1.5 Mathematical Semantics: Fixpoint Theory.- 1.5.1 Recursive Routines and Functional Equations.- 1.5.2 Fixpoint Theory.- 1.6 Proofs by Induction of Properties of Routines.- 1.6.1 Computational Induction.- 1.6.2 Structural Induction.- 1.7 Operational Semantics: Machines.- 1.7.1 Unfolding and Folding.- 1.7.2 Partial Computation.- 1.7.3 Text Substitution Machines.- 1.7.4 The Stack Machine.- 1.8 Restriction of the Parameter Domain.- 1.9 Dijkstra’s Guards.- 1.10 Pre-Algorithmic Formulations by Means of Choice and Determination.- 1.10.1 The Choice Operator.- 1.10.2 The Determination Operator.- 1.11 Semantics of Non-Deterministic Constructions.- 1.11.1 Pre-Algorithms and Algorithms.- 1.11.2 Deriving Algorithms from Pre-Algorithms.- 1.11.3 Mathematical Semantics of Non-Determinate Routines.- 1.11.4 Operational Semantics of Non-Deterministic Algorithms.- 1.12 Routines with a Multiple Result.- 1.13 Structuring of Routines.- 1.13.1 Structuring by Means of Abstraction and Embedding.- 1.13.2 Segments and Suppressed Parameters.- 1.13.3 Object Declarations.- 1.13.4 Result Parameters and the Actualization Taboo.- 1.14 Routines as Parameters and Results.- 1.14.1 Routines as Results.- 1.14.2 Functional Programming.- 1.14.3 The Delay Rule.- Addendum: Notations.- 2. Objects and Object Structures.- 2.1 Denotations.- 2.2 Scope of a Freely Chosen Designation.- 2.3 Kinds of Objects.- 2.4 Sets of Objects, Modes.- 2.5 Composite Modes and Objects.- 2.6 Selectors, Structures with Direct (Selector) Access.- 2.6.1 Compounds.- 2.6.2 Arrays.- 2.6.3 The Selection Structure of Compound and Array.- 2.7 Mode Variants.- 2.8 Introduction of New Modes: Summary.- 2.9 Recursive Object Structures.- 2.9.1 Definition of Recursive Object Structures.- 2.9.2 Object Diagrams.- 2.9.3 Operational Detailing of Objects.- 2.10 Algorithms with Linear Object Structures.- 2.11 The Recursive Object Structure “File”.- 2.11.1 “Knitting” of Sequences.- 2.11.2 Files.- 2.12 Algorithms with Cascade-Type Object Structures.- 2.13 Traversal and Scanning of Recursive Object Structures.- 2.14 Infinite Objects.- 2.14.1 Nexuses of Objects.- 2.14.2 Lazy Evaluation.- 2.15 Some Peculiarities of Arrays.- 2.15.1 Arrays with Computed Index Bounds.- 2.15.2 Induced Operations for Arrays.- 2.16 Routines with Multiple Results Revisited.- Addendum: Notations.- 3. Computational Structures.- 3.1 Concrete Computational Structures.- 3.1.1 Encapsulation Effect.- 3.1.2 Properties of Operations.- 3.1.3 Definition of Concrete Computational Structures.- 3.1.4 Atomic Examples.- 3.2 Abstract Computational Structures and Abstract Types.- 3.2.1 Fundamental Concepts.- 3.2.2 Semantics of Abstract Computational Structures and Abstract Types.- 3.2.3 Completeness of Properties.- 3.2.4 Concretization of an Abstract Type.- 3.2.5 Notation and First Examples.- 3.2.6 Constructors and Selectors.- 3.3 Abstract Arrays.- 3.3.1 One-Side-Flexible Arrays.- 3.3.2 Two-Side-Flexible Arrays.- 3.3.3 Aggregates.- 3.4 Sequence-Type Computational Structures.- 3.4.1 Stack, Deck and Queue.- 3.4.2 Excursus: Divisibility Theory in Semi-Groups.- 3.4.3 Sequence and Word.- 3.4.4 Forgetful Functors.- 3.4.5 Sets.- 3.5 Number-Type Computational Structures.- 3.5.1 Peano Numbers.- 3.5.2 Cycle Numbers and Natural Numbers.- 3.5.3 Excursus: Extension by Means of Formal Quotients.- 3.5.4 Integers.- 3.5.5 Rational Numbers.- 3.5.6 Positional Systems and B-al-Fractions.- 3.6 Changing Abstract Types and Object Structures.- 3.6.1 Type Change and Related Types.- 3.6.2 Concretization.- 3.6.3 Implementation of Concrete Computational Structures.- 3.6.4 Example: Binarization.- 3.6.5 Example: Packing of Objects.- Addendum: Notations.- 4. Transformation into Repetitive Form.- 4.1 Schemes and Transformations.- 4.2 Treatment of Linear Recursion.- 4.2.1 The Technique of Re-Bracketing.- 4.2.2 The Technique of Operand Commutation.- 4.2.3 Function Inversion.- 4.2.4 Function Inversion According to Paterson and Hewitt.- 4.2.5 Function Inversion by Introducing Stacks.- 4.3 Treatment of Non-Linear Recursions.- 4.3.1 Method of Functional Embedding.- 4.3.2 Arithmetization of the Flow of Control.- 4.3.3 Special Cases of Nested Recursion.- 4.3.4 The Technique of Range-of-Values Tabulation.- 4.4 Disentanglement of the Control.- 4.4.1 Disentangled Routines.- 4.4.2 Disentangling Recursive Routines by Means of Function Inversion.- 4.4.3 Reshaping the Type of Control Flow.- 5. Program Variables.- 5.1 The Origin of Program Variables.- 5.1.1 Specialization of the Stack Machine.- 5.1.2 Specialization of the Range-of-Values Machine.- 5.2 Formal Introduction of Program Variables.- 5.2.1 Sequentialization of Object Declarations.- 5.2.2 Program Variables as a Means for Saving Identifiers.- 5.2.3 Expressions with Side-Effects.- 5.2.4 Complete Sequentialization of Collective Assignments.- 5.3 Procedures.- 5.3.1 Program Variables as Parameters.- 5.3.2 Actualization Taboo, Alias Ban and Suppressed Variable Parameters.- 5.3.3 Sharing of Variables.- 5.3.4 Initialization.- 5.3.5 Properties of Program Variables.- 5.4 Axiomatic Description of Programming Languages.- 5.4.1 Predicate Transformers.- 5.4.2 Program Verification.- 5.5 Variables for Structured Objects.- 5.5.1 Selective Alteration.- 5.5.2 Remarks on Input/Output.- Addendum: Notations.- 6. Control Elements.- 6.1 Deparameterization and Formal Treatment of Repetition.- 6.1.1 Deparameterization.- 6.1.2 Semantics of Repetition.- 6.1.3 Analytical Treatment of the Protocol Stack.- 6.2 Jumps.- 6.2.1 Simple Call as a Basic Control Element.- 6.2.2 Introduction of Jumps.- 6.3 The General do-od Construction.- 6.4 Loops.- 6.4.1 Rejecting and Non-Rejecting Repetition.- 6.4.2 Counted Repetition.- 6.5 Loops and Repetitive Systems.- 6.6 Sequential Circuits.- 6.7 Flow Diagrams.- 6.7.1 Classical Flow Diagrams.- 6.7.2 Splitting and Collection.- 6.7.3 Coordinated Flow Diagrams.- 6.8 Petri Nets.- 6.8.1 Theory of Petri Nets.- 6.8.2 Construction of Petri Nets, Connection to Coordinated Flow Diagrams.- 6.9 bool Petri Nets, Signals.- 6.10 nat Petri Nets, Semaphores.- Addendum: Notations.- 7. Organized Storages and Linked Lists.- 7.1 Organized Storages.- 7.1.1 Selective Updating.- 7.1.2 Collecting and Composing Variables.- 7.1.3 Computed Variables.- 7.1.4 Constructing Organized Storages and Generating Variables.- 7.1.5 Advantages and Disadvantages of Organized Storages.- 7.2 Identity of Variables and Alias Ban Revisited.- 7.2.1 Revision of the Assignment Axiom.- 7.2.2 Checking the Actualization Taboo.- 7.3 Implementing Object Structures by Organized Storages.- 7.4 Linked-List Implementation of Organized Storages.- 7.4.1 References to Variables: Pointers.- 7.4.2 Wirth’s Connection.- 7.4.3 Link Variables.- 7.4.4 Implementing Computational Structures Using Linked Lists.- 7.4.5 Properties of Pointers.- 7.5 Improvement of Algorithms Working on Linked Lists by Selective Updating.- 7.5.1 Algorithms for One-Way Linked Lists.- 7.5.2 Algorithms for Two-Way Linked Lists.- 7.6 Addressing.- 7.6.1 Addresses for Variables.- 7.6.2 Jump Addresses.- 7.6.3 Genuine Addresses.- 7.6.4 Outlook to Systems Programming.- Addendum: Notations.- Conclusion. Programming as an Evolutionary Process.- Program Specification and Development in a Uniform Language.- Conceptual Organization of the Algorithmic Language.- Tools to Be Used.- Methodology of Programming.