This book provides a new, systematic and unified approach to the essential ideas of computer programming. While the traditional method is to describe various features of individual programming languages, this book emphasizes instead fundamental concepts common to all of them and the interrelations between these notions, thus enhancing the reader's insight into algorithms and their description.
The systematic development of the basic concepts leads moreover to methods for developing programs- from the specification of a problem to its implementation on a machine, and, in particular, from functional to procedural programs.
The book includes recent theoretical results from areas such as mathematical and operational semantics, fixed point theory, nondeterminism, and abstract data types, together with their application to program transformation and program correctness. In this way, it provides an introduction to the current topics of research, and prepares the student and the professional for the technical literature.


CONTENTS
========

Introduction
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
Chapter 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 Computationallnduction
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
Chapter 2. Objects and Object Structures
2.1 Denotations
2.2 Scope of a Freely Chosen Designation
2.3 Kinds ofObjectso
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" ofSequenceso
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; 177
2.15.2 Induced Operations for Arrays
2.16 Routines with Multiple Results Revisited
Addendum: Notations
Chapter 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
Chapter 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
Chapter 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 SharingofVariables
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
Chapter 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 boo! Petri Nets, Signals
6.10 nat Petri Nets, Semaphores
Addendum: Notations
Chapter 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 ofthe 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
Bibliography
Index
Glossary