Programming Languages: Design and Implementation (4th Edition)

Titles in this series now included in the Thomson Reuters Book Citation Index! 'Texts in Computer Science' (TCS) delivers high-quality instructional content for undergraduates and graduates in all areas of computing and information science, with a strong emphasis on core foundational and theoretical material but inclusive of some prominent applications-related content. TCS books should be reasonably self-contained and aim to provide students with modern and clear accounts of topics ranging across the computing curriculum. As a result, the books are ideal for semester courses or for individual self-study in cases where people need to expand their knowledge. All texts are authored by established experts in their fields, reviewed internally and by the series editors, and provide numerous examples, problems, and other pedagogical tools; many contain fully worked solutions.The TCS series is comprised of high-quality, self-contained books that have broad and comprehensive coverage and are generally in hardback format and sometimes contain color. For undergraduate textbooks that are likely to be more brief and modular in their approach, require only black and white, and are under 275 pages, Springer offers the flexibly designed Undergraduate Topics in Computer Science series, to which we refer potential authors. Preface 6 Do We Need New Programming Languages? 7 Weak Languages 8 General Design Principles 9 To the Reader 10 Contents 11 List of Figures 17 1 A Brief History of Programming Languages 19 1.1 Before Computers: Turing Machines and Lambda Calculus 20 1.2 Programmable Electronic Computers 22 1.3 Early and Influential Programming Languages 24 1.3.1 Plankalkül 24 1.3.2 FORTRAN 25 1.3.3 LISP 26 1.3.4 COBOL 28 1.3.5 ALGOL 60 29 1.3.6 APL 31 1.3.7 PL/I 32 1.3.8 BASIC 33 1.3.9 Simula 34 1.3.10 Pascal 34 1.3.11 C 34 1.3.12 Prolog 35 1.3.13 ISWIM and ML 36 1.4 Further Reading 37 1.5 Exercises 37 2 Implementation Strategies 40 2.1 Compilation and Interpretation 41 2.2 REPLs and IDEs 42 2.3 Intermediate Code and Virtual Machines 42 2.4 Hybrid Methods 44 2.5 Cross Compilers, Reverse Compilers, and Obfuscation 44 2.6 Bootstrapping 46 2.6.1 Notation 47 2.6.2 Compiling Compilers 48 2.6.3 Full Bootstrap 50 2.6.4 Choosing the Language in Which to Write a Compiler 53 2.7 How Implementation Techniques can Influence Language Design 53 2.8 Further Reading 54 2.9 Exercises 55 3 Syntax 57 3.1 Lexical Elements 57 3.1.1 Character Sets 58 3.1.2 Case Sensitivity 60 3.1.3 Identifiers 60 3.1.4 Whitespace 61 3.1.5 Comments 63 3.1.6 Reserved Symbols 65 3.1.7 Separation of Tokens 66 3.1.8 Summary 68 3.2 Grammatical Elements 68 3.2.1 Line-Based Syntax 68 3.2.2 Multi-line Syntax 70 3.2.3 Syntax that Looks Like a Natural Language 70 3.2.4 Bracketed Syntax 71 3.2.5 Prefix, Post Fix and Operator-Precedence Syntax 72 3.2.6 Context-Free Syntax 73 3.2.7 Stronger Grammar Formalisms 75 3.2.8 Other Syntactic Considerations 75 3.2.9 Bracketing Symbols 78 3.3 Concerns that Span Both Lexing and Grammar 79 3.3.1 Macros 79 3.3.2 Visual Languages 80 3.4 Considerations When Designing Syntax 81 3.5 Further Reading 83 3.6 Exercises 83 4 Memory Management 86 4.1 Introduction 86 4.2 Static Allocation 87 4.2.1 Limitations 87 4.3 Stack Allocation 88 4.4 Heap Allocation 90 4.5 Manual Memory Management 90 4.5.1 A Simple Implementation of malloc() and free() 91 4.5.2 Joining Freed Blocks 94 4.5.3 Sorting by Block Size 95 4.5.4 Large Objects 97 4.5.5 Summary of Manual Memory Management 98 4.6 Automatic Memory Management 99 4.7 Reference Counting 100 4.8 Tracing Garbage Collectors 102 4.8.1 Mark-Sweep Collection 103 4.8.2 Two-Space Collection 105 4.8.3 Generational and Concurrent Collectors 109 4.9 Summary of Automatic Memory Management 112 4.10 Memory Management and Language Design 113 4.11 Further Reading 114 4.12 Exercises 115 5 Scopes, Functions, and Parameter Passing 119 5.1 Scope Rules 120 5.1.1 Global Scoping 120 5.1.2 Local Variables Only 121 5.1.3 Block Structure 121 5.1.4 Nested Function Declarations 124 5.1.5 Recursion 126 5.1.6 Macros 126 5.1.7 Parameter-Passing Methods 127 5.2 Implementing Functions and Function Calls 129 5.2.1 Summary of Implementing Function Calls 130 5.2.2 C-Style Functions 130 5.2.3 Nested Function Declarations 131 5.3 Functions as Parameters 133 5.4 First-Class Functions 134 5.5 Functional Programming Languages 136 5.5.1 Impure Functional Languages 136 5.5.2 Defunctionalisation 137 5.5.3 Pure Functional Languages 138 5.5.4 Lazy Functional Languages 140 5.5.5 Strictness Analysis 141 5.6 Exceptions 142 5.6.1 Tagged Return 142 5.6.2 Stack Unwinding 143 5.6.3 Using a Handler Stack 144 5.7 Further Reading 144 5.8 Exercises 144 6 Control Structures 150 6.1 Jumps 150 6.2 Structured Control 152 6.2.1 Conditionals 153 6.2.2 Loops 156 6.2.3 Whole-Collection Operations 160 6.2.4 Break and Continue 162 6.2.5 Structured Versus Unstructured Control 163 6.3 Exceptions and Continuations 165 6.3.1 Continuations 166 6.4 Function Calls as Control 167 6.5 Multithreading 169 6.5.1 Coroutines 169 6.5.2 Threads 171 6.5.3 Message Passing 173 6.6 Exercises 174 7 Types 180 7.1 Checking Types 182 7.2 Type Conversion 184 7.3 Atomic and Composite Types 185 7.3.1 Numbers 185 7.3.2 Characters 187 7.3.3 Boolean Values 187 7.3.4 Enumerated Types and Symbols 188 7.3.5 Product Types 188 7.3.6 Records and Structs 190 7.3.7 Collection Types 192 7.3.8 Union and Sum Types 197 7.3.9 Function Types 199 7.3.10 Recursive Types 200 7.3.11 Named Types and Type Equivalence 202 7.4 Polymorphism 205 7.4.1 Ad hoc Polymorphism 206 7.4.2 Interface Polymorphism 208 7.4.3 Subtype Polymorphism 209 7.4.4 Parametric Polymorphism 213 7.4.5 Polymorphic Type Inference 216 7.4.6 Polymorphism in Various Languages 226 7.5 Further Reading 230 7.6 Exercises 231 8 Modularisation 236 8.1 Simple Modules 236 8.1.1 Shared Modules 237 8.2 Modules with Abstraction 238 8.3 Name Spaces 239 8.3.1 Nested Modules 239 8.4 Modules and Classes 240 8.5 Modules as Parameters/Values 240 8.6 Further Reading 241 8.7 Exercises 241 9 Language Paradigms 242 9.1 What Is a Language Paradigm? 242 9.1.1 Data Flow 242 9.1.2 Execution Order 243 9.1.3 Structuring 244 9.1.4 Nomenclature 245 9.2 A Closer Look at Some Paradigms 246 9.3 Object-Oriented Languages 246 9.3.1 Classes and Objects 246 9.3.2 Single Inheritance 247 9.3.3 Multiple Inheritance 250 9.3.4 Prototype-Based Languages 251 9.4 Logic Languages 252 9.4.1 Pure Prolog 252 9.4.2 List Notation 256 9.4.3 Resolution 257 9.4.4 Full Prolog 261 9.4.5 Other Logic Languages 264 9.5 Further Reading 265 9.6 Exercises 265 10 Domain-Specific Programming Languages 269 10.1 GPLs Versus DSLs 269 10.2 When Should You (Not) Design a New DSL? 271 10.3 How do You Design a DSL? 272 10.4 How do You Implement a DSL? 273 10.4.1 Implementation as Embedded Language 274 10.4.2 Implementation by Preprocessor 277 10.4.3 Implementation as Compiler/Interpreter Modification 278 10.4.4 Implementation as Stand-alone Language 278 10.5 Examples of DSLs 279 10.5.1 Scratch 279 10.5.2 TeX and LaTeX 280 10.5.3 Graphviz 280 10.5.4 OpenSCAD 282 10.5.5 Troll 282 10.5.6 CRL 285 10.5.7 Futhark 286 10.6 Further Reading 286 10.7 Exercises 287 11 Specifying the Semantics of a Programming Language 289 11.1 Informal Specification 289 11.2 Specification by Reference Implementation 290 11.3 Formal Specification 291 11.3.1 Notation for Logic Rules 292 11.3.2 Environments 293 11.3.3 Judgements 293 11.3.4 Semantic Rules 294 11.4 Type Systems 295 11.5 Operational Semantics 297 11.5.1 Operational Semantics for a Functional Language 297 11.5.2 Relating Type Systems and Operational Semantics 299 11.5.3 Operational Semantics for an Imperative Language 299 11.5.4 Unstructured Control 303 11.5.5 Nontermination and Nondeterminism 305 11.6 Static Semantics 305 11.7 Languages That Have Formal Semantics 307 11.8 Further Reading 307 11.9 Exercises 307 12 Exploring the Limits 312 12.1 Limits of Computation 312 12.2 Limits on Program Features 315 12.3 Languages at the Limit 319 12.3.1 Reversible Programming Languages 319 12.3.2 Quantum Programming Languages 326 12.4 Further Reading 327 12.5 Exercises 327 A Index 331 Index 331

Exceptionally comprehensive in approach, this book explores the major issues in both design and implementation of modern programming languages and provides a basic introduction to the underlying theoretical models on which these languages are based. The emphasis throughout is on fundamental concepts—readers learn important ideas, not minor language differences—but several languages are highlighted in sufficient detail to enable readers to write programs that demonstrate the relationship between a source program and its execution behavior—e.g., C, C++, JAVA, ML, LISP, Prolog, Smalltalk, Postscript, HTML, PERL, FORTRAN, Ada, COBOL, BASIC SNOBOL4, PL/I, Pascal.

Begins with a background review of programming languages and the underlying hardware that will execute the given program; then covers the underlying grammatical model for programming languages and their compilers (elementary data types, data structures and encapsulation, inheritance, statements, procedure invocation, storage management, distributed processing, and network programming). Includes an advanced chapter on language semantics—program verification, denotational semantics, and the lambda calculus.

For computer engineers and others interested in programming language designs.

Booknews

Describes programming language design by means of the underlying software and hardware architecture. Examples of language constructs are given in several languages to demonstrate their universality, and brief summaries are given of 11 languages. Models of program design covered include applicative programming and text processing applications. Assumes familiarity with a procedural language. This fourth edition contains new material on the Web's impact on programming, distributed computing, and the PERL and Postscript languages. Pratt is affiliated with NASA Goddard Space Flight Center. Zelkowitz is affiliated with the University of Maryland. Annotation c. Book News, Inc., Portland, OR (booknews.com)

This concise textbook is intended as a guide for programming-language designers and users to better help them understand consequences of design decisions. The text aims to provide readers with an overview of the design space for programming languages and how design choices affect implementation. It is not a classical compilers book, as it assumes the reader is familiar with basic compiler implementation techniques; nor is it a traditional comparative programming languages book, because it does not go into depth about any particular language, instead taking examples from a wide variety of programming languages to illustrate design concepts. Readers are assumed to already have done at least a bit of programming in functional, imperative, and object-oriented languages. Topics and features: Provides topic-by-topic coverage of syntax, types, scopes, memory management and more Includes many technical exercises and discussion exercises Inspires readers to think about language design choices, how these interact, and how they can be implemented Covers advanced topics such as formal semantics and limits of computation Suitable for advanced undergraduates and beginning graduates, this highly practical and useful textbook/guide will also offer programming language professionals a superb reference and learning toolkit. Torben Ægidius Mogensen is Associate Professor at the Dept. of Computer Science at the University of Copenhagen, Denmark. Exceptionally comprehensive in approach, this book explores the major issues in both design and implementation of modern programming languages and provides a basic introduction to the underlying theoretical models on which these languages are based. The emphasis throughout is on fundamental concepts—readers learn important ideas, not minor language differences--but several languages are highlighted in sufficient detail to enable readers to write programs that demonstrate the relationship between a source program and its execution behavior--e.g., C, C++, JAVA, ML, LISP, Prolog, Smalltalk, Postscript, HTML, PERL, FORTRAN, Ada, COBOL, BASIC SNOBOL4, PL/I, Pascal. Begins with a background review of programming languages and the underlying hardware that will execute the given program; then covers the underlying grammatical model for programming languages and their compilers (elementary data types, data structures and encapsulation, inheritance, statements, procedure invocation, storage management, distributed processing, and network programming). Includes an advanced chapter on language semantics--program verification, denotational semantics, and the lambda calculus. For computer engineers and others interested in programming language designs. This describes programming language design by means of the underlying software and hardware architecture that is required for execution of programs written in those languages