Algorithmic Language and Program Development

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.