Programming Languages: Principles and Paradigms

Description

1848829132 Undergraduate Topics in Computer Science Programming Languages: Principles and Paradigms Foreword Introduction Use of the text Acknowledgements Contents Chapter 1 Abstract Machines The Concepts of Abstract Machine and of Interpreter The Interpreter An Example of an Abstract Machine: The Hardware Machine Memory The language of the physical machine Interpreter Implementation of a Language Implementation of an Abstract Machine Implementation in Hardware Simulation Using Software Emulation Using Firmware Implementation: The Ideal Case Notation Purely interpreted implementation Purely compiled implementation Comparing the Two Techniques Implementation: The Real Case and The Intermediate Machine Hierarchies of Abstract Machines Chapter Summary Bibliographic Notes Exercises References Chapter 2 How to Describe a Programming Language Levels of Description Grammar and Syntax Context-Free Grammars BNF Derivations and languages Derivation Trees Ambiguity Contextual Syntactic Constraints Compilers Lexical analysis Syntactic analysis Semantic analysis Generation of intermediate forms Code optimisation Code generation Semantics State Transitions Expression semantics Command semantics Computations Pragmatics Implementation Chapter Summary Bibliographical Notes Exercises References Chapter 3 Foundations The Halting Problem Expressiveness of Programming Languages Formalisms for Computability There are More Functions than Algorithms Chapter Summary Bibliographical Notes Exercises References Chapter 4 Names and The Environment Names and Denotable Objects Denotable Objects Environments and Blocks Blocks Types of Environment Operations on Environments Scope Rules Static Scope Dynamic Scope Some Scope Problems Chapter Summary Bibliographical Notes Exercises References Chapter 5 Memory Management Techniques for Memory Management Static Memory Management Dynamic Memory Management Using Stacks Activation Records for In-line Blocks Activation Records for Procedures Stack Management Dynamic Management Using a Heap Fixed-Length Blocks Variable-Length Blocks Single free list Multiple free lists Implementation of Scope Rules Static Scope: The Static Chain Static Scope: The Display Dynamic Scope: Association Lists and CRT Central Referencing environment Table (CRT) Chapter Summary Bibliographic Notes Exercises References Chapter 6 Control Structure Expressions Expression Syntax Infix Notation Prefix Notation Postfix Notation Semantics of Expressions Infix Notation: Precedence and Associativity Prefix Notation Postfix Notation Evaluation of Expressions Subexpression Evaluation Order The Concept of Command The Variable Assignment Sequence Control Commands Commands for Explicit Sequence Control Sequential Command Composite Command Goto Other sequence control commands Conditional Commands If Case Iterative Commands Unbounded iteration Bounded iteration Expressiveness of bounded iteration The for in C For-each Structured Programming Recursion Tail Recursion Recursion or Iteration? Chapter Summary Bibliographical Notes Exercises References Chapter 7 Control Abstraction Subprograms Parameters Return value Nonlocal environment Functional Abstraction Parameter Passing Call by value Call by reference Call by constant Call by result Call by value-result Call by name Higher-Order Functions Functions as Parameters Implementation of deep binding Binding policy and static scope What defines the environment Functions as Results Exceptions Pragmatics Implementing Exceptions Chapter Summary Bibliographical Notes Exercises References Chapter 8 Structuring Data Data Types Types as Support for Conceptual Organisation Types for Correctness Types and Implementation Type Systems Static and Dynamic Checking Scalar Types Booleans Characters Integers Reals Fixed Point Complex Void Enumerations Intervals Ordered Types Composite Types Records Variant Records and Unions Unions in C Variants and Security Arrays Operations on Arrays Checking Storage and Calculation of Indices Form of an Array: Where an Array is Allocated Dope Vectors Sets Pointers Pointer Arithmetic Deallocation Recursive Types Functions Equivalence Equivalence by Name Structural Equivalence Compatibility and Conversion Coercions Explicit Conversions Polymorphism Overloading Universal Parametric Polymorphism Explicit polymorphism Implicit Polymorphism Subtype Universal Polymorphism Remarks on the Implementation Type Checking and Inference Safety: An Evaluation Avoiding Dangling References Tombstone Locks and Keys Garbage Collection Reference Counting Mark and Sweep Interlude: Pointer Reversal Mark and Compact Copy Chapter Summary Bibliographic Notes Exercises References Chapter 9 Data Abstraction Abstract Data Types Information Hiding Representation Independence Modules Chapter Summary Bibliographical Notes Exercises References Chapter 10 The Object-Oriented Paradigm The Limits of Abstract Data Types A First Review Fundamental Concepts Objects Classes Objects in the heap and on the stack Encapsulation Subtypes Redefinition of a method Shadowing Abstract classes The subtype relation Constructors Inheritance Inheritance and visibility Single and multiple inheritance Dynamic Method Lookup Implementation Aspects Objects Classes and inheritance Late binding of self Single Inheritance Downcasting The Problem of Fragile Base Class Dynamic Method Dispatch in the JVM Multiple Inheritance Vtable Structure Replicated multiple inheritance Shared multiple inheritance Polymorphism and Generics Subtype Polymorphism Generics in Java Implementation of Generics in Java Generics, Arrays and Subtype Hierarchy Covariant and Contravariant Overriding Supertypes and Views Chapter Summary Bibliographical Notes Exercises References Chapter 11 The Functional Paradigm Computations without State Expressions and Functions Computation as Reduction The Fundamental Ingredients Evaluation Values Capture-Free Substitution Evaluation Strategies Evaluation by value Evaluation by name Lazy evaluation Comparison of the Strategies Programming in a Functional Language Local Environment Interactiveness Types Pattern Matching Infinite Objects Imperative Aspects Implementation: The SECD Machine The Functional Paradigm: An Assessment Program Correctness Program schemata Assessment Fundamentals: The lambda-calculus Syntactic conventions, free and bound variables Substitution Alpha equivalence Computation: beta reduction Normal forms Confluence Fixpoint operators Expressiveness of the lambda-calculus Chapter Summary Bibliographical Note Exercises References Chapter 12 The Logic Programming Paradigm Deduction as Computation Terminological Note An Example Syntax The Language of First-Order Logic Alphabet Terms Formulæ Logic Programs Theory of Unification The Logic Variable Substitution Most General Unifier A Unification Algorithm Martelli and Montanari's unification algorithm The Computational Model The Herbrand Universe Declarative and Procedural Interpretation Procedure Calls Evaluation of a non-atomic goal Heads with arbitrary terms Control: Non-determinism Backtracking in Prolog Some Examples Extensions Prolog Arithmetic Cut Disjunction If-then-else Negation Logic Programming and Databases Logic Programming with Constraints Advantages and Disadvantages of the Logic Paradigm Chapter Summary Bibliographical Notes Exercises References Chapter 13 A Short Historical Perspective Beginnings Factors in the Development of Languages 1950s and 60s FORTRAN Algol LISP COBOL Simula The 1970s C Pascal Smalltalk Declarative languages ML PROLOG The 1980s C++ Ada CLP 1990s Java Chapter Summary Bibliographical Notes References Index