Programming Languages: Build, Prove, and Compare
- Length: 600 pages
- Edition: N
- Language: English
- Publisher: Cambridge University Press
- Publication Date: 2022-10-27
- ISBN-10: 110718018X
- ISBN-13: 9781107180185
- Sales Rank: #769808 (See Top 100 Books)
Computer scientists often need to learn new programming languages quickly. The best way to prepare for this is to understand the foundational principles that underlie even the most complicated industrial languages. This text for an undergraduate programming languages course distills great languages and their design principles down to easy-to-learn ‘bridge’ languages implemented by interpreters whose key parts are explained in the text. The book goes deep into the roots of both functional and object-oriented programming, and it shows how types and modules, including generics/polymorphism, contribute to effective programming. The book is not just about programming languages; it is also about programming. Through concepts, examples, and more than 300 practice exercises that exploit the interpreter, students learn not only what programming-language features are but also how to do things with them. Substantial implementation projects include Milner’s type inference, both copying and mark-and-sweep garbage collection, and arithmetic on arbitrary-precision integers.
Cover Half-title Title page Copyright information Dedication Contents Preface Acknowledgments Credits Table of Judement Forms and Important Functions Symbols and Notation Introduction Part I. Foundations 1 An Imperative Core 1.1 Looking at languages 1.2 The Impcore language 1.3 Abstract syntax 1.4 Environments and the meanings of names 1.5 Operational semantics 1.6 The interpreter 1.7 Operational semantics revisited: Proofs 1.8 Extending Impcore 1.9 Summary 1.10 Exercises 2 Scheme, S-expressions, and First-class Functions 2.1 Overview of μScheme and this chapter 2.2 Language I: Values, syntax, and initial basis 2.3 Practice I: Recursive functions on lists of values 2.4 Records and trees (more data) 2.5 Combining theory and practice: Algebraic laws 2.6 Language II: Local variables and let 2.7 Language III: First‐class functions, lambda, and locations 2.8 Practice III: Higher‐order functions on lists 2.9 Practice IV: Higher‐order functions for polymorphism 2.10 Practice V: Continuation‐passing style 2.11 Operational semantics 2.12 The interpreter 2.13 Extending μScheme with syntactic sugar 2.14 Scheme as it really is 2.15 Summary 2.16 Exercises 3 Control Operators and a Small-step Semantics: μScheme+ 3.1 The μScheme+ language 3.2 Procedural programming with control operators 3.3 Operational semantics: Evaluation using a stack 3.4 Operational semantics: Lowering to a core language 3.5 A semantics of Core μScheme+ 3.6 The interpreter 3.7 Stacks, control, and semantics as they really are 3.8 Summary 3.9 Exercises 4 Automatic Memory Management 4.1 What garbage is and where it comes from 4.2 Garbage‐collection basics 4.3 The managed heap in μScheme+ 4.4 Mark‐and‐sweep collection 4.5 Copying collection 4.6 Debugging a collector 4.7 Mark‐compact collection 4.8 Reference counting 4.9 Garbage collection as it really is 4.10 Summary 4.11 Exercises 5 Interlude: μscheme in ML 5.1 Names and environments, with ıntroduction on ML 5.2 Abstract syntax and values 5.3 Evaluation 5.4 Defining and embedding primitives 5.5 Notable differences between ML and C 5.6 Free and bound variables: Deeper into μScheme 5.7 Summary 5.8 Exercises 6 Type Systems for Impcore and μScheme 6.1 Typed Impcore: A statically typed imperative core 6.2 A type‐checking interpreter for Typed Impcore 6.3 Extending Typed Impcore with arrays 6.4 Common type constructors 6.5 Type soundness 6.6 Polymorphic type systems and Typed μScheme 6.7 Type systems as they really are 6.8 Summary 6.9 Exercises 7 ML and type inference 7.1 Nano‐ML: A nearly applicative language 7.2 Abstract syntax and values of nano‐ML 7.3 Operational semantics 7.4 Type system for nano‐ML 7.5 From typing rules to type inference 7.6 The interpreter 7.7 Hindley‐Milner as it really is 7.8 Summary 7.9 Exercises Part II. Programming at Scale 8 User-defined, algebraic types (and pattern matching) 8.1 Case expressions and pattern matching 8.2 Algebraic data types in μML 8.3 Equational reasoning with case expressions 8.4 Syntactic sugar: Patterns everywhere 8.5 Type generativity and type equivalence 8.6 Abstract syntax and values of μML 8.7 Theory and implementation of user‐defined types 8.8 Theory and implementation of case expressions 8.9 Algebraic data types as they really are 8.10 Summary 8.11 Exercises 9 Molecule, Abstract Data Types, and Modules 9.1 The vocabulary of data abstraction 9.2 Introduction to Molecule, part I: Writing client code 9.3 Introduction, part II: Implementing an abstraction 9.4 The Molecule language 9.5 Molecule’s initial basis 9.6 Program design: Abstractions 9.7 Key feature: Inspecting multiple representations 9.8 Molecule’s type system: Enforcing abstraction 9.9 Notes on the interpreter 9.10 Abstract data types, modules, and overloading as they really are 9.11 Summary 9.12 Exercises 10 Smalltalk and Object-orientation 10.1 Object‐oriented programming by example 10.2 Data abstraction all over again 10.3 The μSmalltalk language 10.4 The initial basis of μSmalltalk 10.5 Object‐oriented programming techniques 10.6 Technique I: Method dispatch replaces conditionals 10.7 Technique II: Abstract classes 10.8 Technique III: Multiple representations the object-oriented way 10.9 Technique IV: Invariants in object‐oriented programming 10.10 Operational semantics 10.11 The interpreter 10.12 Smalltalk as it really is 10.13 Objects and classes as they really are 10.14 Summary 10.15 Exercises Afterword Bibliography Key words and phrases Concept index
Donate to keep this site alive
1. Disable the AdBlock plugin. Otherwise, you may not get any links.
2. Solve the CAPTCHA.
3. Click download link.
4. Lead to download server to download.