Beschreibung
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.
Autorenporträt
Inhaltsangabe0.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
Herstellerkennzeichnung:
Springer Verlag GmbH
Tiergartenstr. 17
69121 Heidelberg
DE
E-Mail: juergen.hartmann@springer.com
