Programming Language Design and Implementation

Description

Preface Do We Need New Programming Languages? Weak Languages General Design Principles To the Reader Contents List of Figures 1 A Brief History of Programming Languages 1.1 Before Computers: Turing Machines and Lambda Calculus 1.2 Programmable Electronic Computers 1.3 Early and Influential Programming Languages 1.3.1 Plankalkül 1.3.2 FORTRAN 1.3.3 LISP 1.3.4 COBOL 1.3.5 ALGOL 60 1.3.6 APL 1.3.7 PL/I 1.3.8 BASIC 1.3.9 Simula 1.3.10 Pascal 1.3.11 C 1.3.12 Prolog 1.3.13 ISWIM and ML 1.4 Further Reading 1.5 Exercises 2 Implementation Strategies 2.1 Compilation and Interpretation 2.2 REPLs and IDEs 2.3 Intermediate Code and Virtual Machines 2.4 Hybrid Methods 2.5 Cross Compilers, Reverse Compilers, and Obfuscation 2.6 Bootstrapping 2.6.1 Notation 2.6.2 Compiling Compilers 2.6.3 Full Bootstrap 2.6.4 Choosing the Language in Which to Write a Compiler 2.7 How Implementation Techniques can Influence Language Design 2.8 Further Reading 2.9 Exercises 3 Syntax 3.1 Lexical Elements 3.1.1 Character Sets 3.1.2 Case Sensitivity 3.1.3 Identifiers 3.1.4 Whitespace 3.1.5 Comments 3.1.6 Reserved Symbols 3.1.7 Separation of Tokens 3.1.8 Summary 3.2 Grammatical Elements 3.2.1 Line-Based Syntax 3.2.2 Multi-line Syntax 3.2.3 Syntax that Looks Like a Natural Language 3.2.4 Bracketed Syntax 3.2.5 Prefix, Post Fix and Operator-Precedence Syntax 3.2.6 Context-Free Syntax 3.2.7 Stronger Grammar Formalisms 3.2.8 Other Syntactic Considerations 3.2.9 Bracketing Symbols 3.3 Concerns that Span Both Lexing and Grammar 3.3.1 Macros 3.3.2 Visual Languages 3.4 Considerations When Designing Syntax 3.5 Further Reading 3.6 Exercises 4 Memory Management 4.1 Introduction 4.2 Static Allocation 4.2.1 Limitations 4.3 Stack Allocation 4.4 Heap Allocation 4.5 Manual Memory Management 4.5.1 A Simple Implementation of malloc() and free() 4.5.2 Joining Freed Blocks 4.5.3 Sorting by Block Size 4.5.4 Large Objects 4.5.5 Summary of Manual Memory Management 4.6 Automatic Memory Management 4.7 Reference Counting 4.8 Tracing Garbage Collectors 4.8.1 Mark-Sweep Collection 4.8.2 Two-Space Collection 4.8.3 Generational and Concurrent Collectors 4.9 Summary of Automatic Memory Management 4.10 Memory Management and Language Design 4.11 Further Reading 4.12 Exercises 5 Scopes, Functions, and Parameter Passing 5.1 Scope Rules 5.1.1 Global Scoping 5.1.2 Local Variables Only 5.1.3 Block Structure 5.1.4 Nested Function Declarations 5.1.5 Recursion 5.1.6 Macros 5.1.7 Parameter-Passing Methods 5.2 Implementing Functions and Function Calls 5.2.1 Summary of Implementing Function Calls 5.2.2 C-Style Functions 5.2.3 Nested Function Declarations 5.3 Functions as Parameters 5.4 First-Class Functions 5.5 Functional Programming Languages 5.5.1 Impure Functional Languages 5.5.2 Defunctionalisation 5.5.3 Pure Functional Languages 5.5.4 Lazy Functional Languages 5.5.5 Strictness Analysis 5.6 Exceptions 5.6.1 Tagged Return 5.6.2 Stack Unwinding 5.6.3 Using a Handler Stack 5.7 Further Reading 5.8 Exercises 6 Control Structures 6.1 Jumps 6.2 Structured Control 6.2.1 Conditionals 6.2.2 Loops 6.2.3 Whole-Collection Operations 6.2.4 Break and Continue 6.2.5 Structured Versus Unstructured Control 6.3 Exceptions and Continuations 6.3.1 Continuations 6.4 Function Calls as Control 6.5 Multithreading 6.5.1 Coroutines 6.5.2 Threads 6.5.3 Message Passing 6.6 Exercises 7 Types 7.1 Checking Types 7.2 Type Conversion 7.3 Atomic and Composite Types 7.3.1 Numbers 7.3.2 Characters 7.3.3 Boolean Values 7.3.4 Enumerated Types and Symbols 7.3.5 Product Types 7.3.6 Records and Structs 7.3.7 Collection Types 7.3.8 Union and Sum Types 7.3.9 Function Types 7.3.10 Recursive Types 7.3.11 Named Types and Type Equivalence 7.4 Polymorphism 7.4.1 Ad hoc Polymorphism 7.4.2 Interface Polymorphism 7.4.3 Subtype Polymorphism 7.4.4 Parametric Polymorphism 7.4.5 Polymorphic Type Inference 7.4.6 Polymorphism in Various Languages 7.5 Further Reading 7.6 Exercises 8 Modularisation 8.1 Simple Modules 8.1.1 Shared Modules 8.2 Modules with Abstraction 8.3 Name Spaces 8.3.1 Nested Modules 8.4 Modules and Classes 8.5 Modules as Parameters/Values 8.6 Further Reading 8.7 Exercises 9 Language Paradigms 9.1 What Is a Language Paradigm? 9.1.1 Data Flow 9.1.2 Execution Order 9.1.3 Structuring 9.1.4 Nomenclature 9.2 A Closer Look at Some Paradigms 9.3 Object-Oriented Languages 9.3.1 Classes and Objects 9.3.2 Single Inheritance 9.3.3 Multiple Inheritance 9.3.4 Prototype-Based Languages 9.4 Logic Languages 9.4.1 Pure Prolog 9.4.2 List Notation 9.4.3 Resolution 9.4.4 Full Prolog 9.4.5 Other Logic Languages 9.5 Further Reading 9.6 Exercises 10 Domain-Specific Programming Languages 10.1 GPLs Versus DSLs 10.2 When Should You (Not) Design a New DSL? 10.3 How do You Design a DSL? 10.4 How do You Implement a DSL? 10.4.1 Implementation as Embedded Language 10.4.2 Implementation by Preprocessor 10.4.3 Implementation as Compiler/Interpreter Modification 10.4.4 Implementation as Stand-alone Language 10.5 Examples of DSLs 10.5.1 Scratch 10.5.2 TeX and LaTeX 10.5.3 Graphviz 10.5.4 OpenSCAD 10.5.5 Troll 10.5.6 CRL 10.5.7 Futhark 10.6 Further Reading 10.7 Exercises 11 Specifying the Semantics of a Programming Language 11.1 Informal Specification 11.2 Specification by Reference Implementation 11.3 Formal Specification 11.3.1 Notation for Logic Rules 11.3.2 Environments 11.3.3 Judgements 11.3.4 Semantic Rules 11.4 Type Systems 11.5 Operational Semantics 11.5.1 Operational Semantics for a Functional Language 11.5.2 Relating Type Systems and Operational Semantics 11.5.3 Operational Semantics for an Imperative Language 11.5.4 Unstructured Control 11.5.5 Nontermination and Nondeterminism 11.6 Static Semantics 11.7 Languages That Have Formal Semantics 11.8 Further Reading 11.9 Exercises 12 Exploring the Limits 12.1 Limits of Computation 12.2 Limits on Program Features 12.3 Languages at the Limit 12.3.1 Reversible Programming Languages 12.3.2 Quantum Programming Languages 12.4 Further Reading 12.5 Exercises A Index Index