Programming languages : concepts and implementation

Programming Languages: Concepts and Implementation is a textbook on the fundamental principles of programming languages through a combination of concept-based and interpreter-based approaches. The book has an implementation-oriented focus and features conceptual and programming exercises that give students practical experience applying language theory and concepts. The book also showcases the construction of a progressive series of language interpreters in Python that cover the implementation of a host of core language concepts such as scope, first-class functions, and parameter passing. Other programming styles, including logic/declarative programming, and compelling language features, such as first-class continuations, are also discussed. Concepts are presented in Python, Scheme, JavaScript, Ruby, ML, Haskell, Prolog, and various other programming languages. This book is intended as a general-purpose textbook for a course on programming languages. Each new print textbook includes Navigate eBook Access, a digital-only e-book with 365-day access. Programming Languages Concepts and Implementation Title Page Copyright Dedication Contents Preface About the Author List of Figures List of Tables Part I Fundamentals 1 Introduction 1.1 Text Objectives 1.2 Chapter Objectives 1.3 The World of Programming Languages 1.3.1 Fundamental Questions 1.3.2 Bindings: Static and Dynamic 1.3.3 Programming Language Concepts 1.4 Styles of Programming 1.4.1 Imperative Programming 1.4.2 Functional Programming 1.4.3 Object-Oriented Programming 1.4.4 Logic/Declarative Programming 1.4.5 Bottom-up Programming 1.4.6 Synthesis: Beyond Paradigms 1.4.7 Language Evaluation Criteria 1.4.8 Thought Process for Problem Solving 1.5 Factors Influencing Language Development 1.6 Recurring Themes in the Study of Languages 1.7 What You Will Learn 1.8 Learning Outcomes 1.9 Thematic Takeaways 1.10 Chapter Summary 1.11 Notes and Further Reading 2 Formal Languages and Grammars 2.1 Chapter Objectives 2.2 Introduction to Formal Languages 2.3 Regular Expressions and Regular Languages 2.3.1 Regular Expressions 2.3.2 Finite-State Automata 2.3.3 Regular Languages 2.4 Grammars and Backus–Naur Form 2.4.1 Regular Grammars 2.5 Context-Free Languages and Grammars 2.6 Language Generation: Sentence Derivations 2.7 Language Recognition: Parsing 2.8 Syntactic Ambiguity 2.8.1 Modeling Some Semantics in Syntax 2.8.2 Parse Trees 2.9 Grammar Disambiguation 2.9.1 Operator Precedence 2.9.2 Associativity of Operators 2.9.3 The Classical Dangling else Problem 2.10 Extended Backus–Naur Form 2.11 Context-Sensitivity and Semantics 2.12 Thematic Take aways 2.13 Chapter Summary 2.14 Notes and Further Reading 3 Scanning and Parsing 3.1 Chapter Objectives 3.2 Scanning 3.3 Parsing 3.4 Recursive-Descent Parsing 3.4.1 A Complete Recursive-Descent Parser 3.4.2 A Language Generator 3.5 Bottom-up, Shift-Reduce Parsing and Parser Generators 3.5.1 A Complete Example in lex and yacc 3.6 PLY: Python Lex-Yacc 3.6.1 A Complete Example in PLY 3.6.2 Camille Scanner and Parser Generators in PLY 3.7 Top-down Vis-à-Vis Bottom-up Parsing 3.8 Thematic Takeaways 3.9 Chapter Summary 3.10 Notes and Further Reading 4 Programming Language Implementation 4.1 Chapter Objectives 4.2 Interpretation Vis-à-Vis Compilation 4.3 Run-Time Systems: Methods of Executions 4.4 Comparison of Interpreters and Compilers 4.5 Influence of Language Goals on Implementation 4.6 Thematic Takeaways 4.7 Chapter Summary 4.8 Notes and Further Reading 5 Functional Programming in Scheme 5.1 Chapter Objectives 5.2 Introduction to Functional Programming 5.2.1 Hallmarks of Functional Programming 5.2.2 Lambda Calculus 5.2.3 Lists in Functional Programming 5.3 Lisp 5.3.1 Introduction 5.3.2 Lists in Lisp 5.4 Scheme 5.4.1 An Interactive and Illustrative Session with Scheme 5.4.2 Homoiconicity: No Distinction Between Program Code and Data 5.5 cons Cells: Building Blocks of Dynamic Memory Structures 5.5.1 List Representation 5.5.2 List-Box Diagrams 5.6 Functions on Lists 5.6.1 A List length Function 5.6.2 Run-Time Complexity: append and reverse 5.6.3 The Difference Lists Technique 5.7 Constructing Additional Data Structures 5.7.1 A Binary Tree Abstraction 5.7.2 A Binary Search Tree Abstraction 5.8 Scheme Predicates as Recursive-Descent Parsers 5.8.1 atom?, list-of-atoms?, and list-of-numbers? 5.8.2 Factoring out the list-of Pattern 5.9 Local Binding: let, let*, and letrec 5.9.1 The let and let* Expressions 5.9.2 The letrec Expression 5.9.3 Using let and letrec to Define a Local Function 5.9.4 Other Languages Supporting Functional Programming: ML and Haskell 5.10 Advanced Techniques 5.10.1 More List Functions 5.10.2 Eliminating Expression Recomputation 5.10.3 Avoiding Repassing Constant Arguments Across Recursive Calls 5.11 Languages and Software Engineering 5.11.1 Building Blocks as Abstractions 5.11.2 Language Flexibility Supports Program Modification 5.11.3 Malleable Program Design 5.11.4 From Prototype to Product 5.12 Layers of Functional Programming 5.13 Concurrency 5.14 Programming Project for Chapter 5 5.15 Thematic Takeaways 5.16 Chapter Summary 5.17 Notes and Further Reading 6 Binding and Scope 6.1 Chapter Objectives 6.2 Preliminaries 6.2.1 What Is a Closure? 6.2.2 Static Vis-à-Vis Dynamic Properties 6.3 Introduction 6.4 Static Scoping 6.4.1 Lexical Scoping 6.5 Lexical Addressing 6.6 Free or Bound Variables 6.7 Dynamic Scoping 6.8 Comparison of Static and Dynamic Scoping 6.9 Mixing Lexically and Dynamically Scoped Variables 6.10 The FUNARG Problem 6.10.1 The Downward FUNARG Problem 6.10.2 The Upward FUNARG Problem 6.10.3 Relationship Between Closures and Scope 6.10.4 Uses of Closures 6.10.5 The Upward and Downward FUNARG Problem in a Single Function 6.10.6 Addressing the FUNARG Problem 6.11 Deep, Shallow, and Ad Hoc Binding 6.11.1 Deep Binding 6.11.2 Shallow Binding 6.11.3 Ad Hoc Binding 6.12 Thematic Takeaways 6.13 Chapter Summary 6.14 Notes and Further Reading Part II Types 7 Type Systems 7.1 Chapter Objectives 7.2 Introduction 7.3 Type Checking 7.4 Type Conversion, Coercion, and Casting 7.4.1 Type Coercion: Implicit Conversion 7.4.2 Type Casting: Explicit Conversion 7.4.3 Type Conversion Functions: Explicit Conversion 7.5 Parametric Polymorphism 7.6 Operator/Function Overloading 7.7 Function Overriding 7.8 Static/Dynamic Typing Vis-à-Vis Explicit/Implicit Typing 7.9 Type Inference 7.10 Variable-Length Argument Lists in Scheme 7.11 Thematic Takeaways 7.12 Chapter Summary 7.13 Notes and Further Reading 8 Currying and Higher-Order Functions 8.1 Chapter Objectives 8.2 Partial Function Application 8.3 Currying 8.3.1 Curried Form 8.3.2 Currying and Uncurrying 8.3.3 The curry and uncurry Functions in Haskell 8.3.4 Flexibility in Curried Functions 8.3.5 All Built-in Functions in Haskell Are Curried 8.3.6 Supporting Curried Form Through First-Class Closures 8.3.7 ML Analogs 8.4 Putting It All Together: Higher-Order Functions 8.4.1 Functional Mapping 8.4.2 Functional Composition 8.4.3 Sections in Haskell 8.4.4 Folding Lists 8.4.5 Crafting Cleverly Conceived Functions with Curried HOFs 8.5 Analysis 8.6 Thematic Takeaways 8.7 Chapter Summary 8.8 Notes and Further Reading 9 Data Abstraction 9.1 Chapter Objectives 9.2 Aggregate Data Types 9.2.1 Arrays 9.2.2 Records 9.2.3 Undiscriminated Unions 9.2.4 Discriminated Unions 9.3 Inductive Data Types 9.4 Variant Records 9.4.1 Variant Records in Haskell 9.4.2 Variant Records in Scheme: (define-datatype ...) and (cases ...) 9.5 Abstract Syntax 9.6 Abstract-Syntax Tree for Camille 9.6.1 Camille Abstract-Syntax Tree Data Type: TreeNode 9.6.2 Camille Parser Generator with Tree Builder 9.7 Data Abstraction 9.8 Case Study: Environments 9.8.1 Choices of Representation 9.8.2 Closure Representation in Scheme 9.8.3 Closure Representation in Python 9.8.4 Abstract-Syntax Representation in Python 9.9 ML and Haskell: Summaries, Comparison, Applications, and Analysis 9.9.1 ML Summary 9.9.2 Haskell Summary 9.9.3 Comparison of ML and Haskell 9.9.4 Applications 9.9.5 Analysis 9.10 Thematic Takeaways 9.11 Chapter Summary 9.12 Notes and Further Reading Part III Interpreter Implementation 10 Local Binding and Conditional Evaluation 10.1 Chapter Objectives 10.2 Checkpoint 10.3 Overview: Learning Language Concepts Through Interpreters 10.4 Preliminaries: Interpreter Essentials 10.4.1 Expressed Values Vis-à-Vis Denoted Values 10.4.2 Defined Language Vis-à-Vis Defining Language 10.5 The Camille Grammar and Language 10.6 A First Camille Interpreter 10.6.1 Front End for Camille 10.6.2 Simple Interpreter for Camille 10.6.3 Abstract-Syntax Trees for Arguments Lists 10.6.4 REPL: Read-Eval-Print Loop 10.6.5 Connecting the Components 10.6.6 How to Run a Camille Program 10.7 Local Binding 10.8 Conditional Evaluation 10.9 Putting It All Together 10.10 Thematic Takeaways 10.11 Chapter Summary 10.12 Notes and Further Reading 11 Functions and Closures 11.1 Chapter Objectives 11.2 Non-recursive Functions 11.2.1 Adding Support for User-Defined Functions to Camille 11.2.2 Closures 11.2.3 Augmenting the evaluate_expr Function 11.2.4 A Simple Stack Object 11.3 Recursive Functions 11.3.1 Adding Support for Recursion in Camille 11.3.2 Recursive Environment 11.3.3 Augmenting evaluate_expr with New Variants 11.4 Thematic Takeaways 11.5 Chapter Summary 11.6 Notes and Further Reading 12 Parameter Passing 12.1 Chapter Objectives 12.2 Assignment Statement 12.2.1 Use of Nested lets to Simulate Sequential Evaluation 12.2.2 Illustration of Pass-by-Value in Camille 12.2.3 Reference Data Type 12.2.4 Environment Revisited 12.2.5 Stack Object Revisited 12.3 Survey of Parameter-Passing Mechanisms 12.3.1 Pass-by-Value 12.3.2 Pass-by-Reference 12.3.3 Pass-by-Result 12.3.4 Pass-by-Value-Result 12.3.5 Summary 12.4 Implementing Pass-by-Reference in the Camille Interpreter 12.4.1 Revised Implementation of References 12.4.2 Reimplementation of the evaluate_operand Function 12.5 Lazy Evaluation 12.5.1 Introduction 12.5.2 ß-Reduction 12.5.3 C Macros to Demonstrate Pass-by-Name: ß-Reduction Examples 12.5.4 Two Implementations of Lazy Evaluation 12.5.5 Implementing Lazy Evaluation: Thunks 12.5.6 Lazy Evaluation Enables List Comprehensions 12.5.7 Applications of Lazy Evaluation 12.5.8 Analysis of Lazy Evaluation 12.5.9 Purity and Consistency 12.6 Implementing Pass-by-Name/Need in Camille: Lazy Camille 12.7 Sequential Execution in Camille 12.8 Camille Interpreters: A Retrospective 12.9 Metacircular Interpreters 12.10 Thematic Takeaways 12.11 Chapter Summary 12.12 Notes and Further Reading Part IV Other Styles of Programming 13 Control and Exception Handling 13.1 Chapter Objectives 13.2 First-Class Continuations 13.2.1 The Concept of a Continuation 13.2.2 Capturing First-Class Continuations: call/cc 13.3 Global Transfer of Control with Continuations 13.3.1 Nonlocal Exits 13.3.2 Breakpoints 13.3.3 First-Class Continuations in Ruby 13.4 Other Mechanisms for Global Transfer of Control 13.4.1 The goto Statement 13.4.2 Capturing and Restoring Control Context in C: setjmp and longjmp 13.5 Levels of Exception Handling in Programming Languages: A Summary 13.5.1 Function Calls 13.5.2 Lexically Scoped Exceptions: break and continue 13.5.3 Stack Unwinding/Crawling 13.5.4 Dynamically Scoped Exceptions: Exception-Handling Systems 13.5.5 First-Class Continuations 13.6 Control Abstraction 13.6.1 Coroutines 13.6.2 Applications of First-Class Continuations 13.6.3 The Power of First-Class Continuations 13.7 Tail Recursion 13.7.1 Recursive Control Behavior 13.7.2 Iterative Control Behavior 13.7.3 Tail-Call Optimization 13.7.4 Space Complexity and Lazy Evaluation 13.8 Continuation-Passing Style 13.8.1 Introduction 13.8.2 A Growing Stack or a Growing Continuation 13.8.3 An All-or-Nothing Proposition 13.8.4 Trade-off Between Time and Space Complexity 13.8.5 call/cc Vis-à-Vis CPS 13.9 Callbacks 13.10 CPS Transformation 13.10.1 Defining call/cc in Continuation-Passing Style 13.11 Thematic Takeaways 13.12 Chapter Summary 13.13 Notes and Further Reading 14 Logic Programming 14.1 Chapter Objectives 14.2 Propositional Calculus 14.3 First-Order Predicate Calculus 14.3.1 Representing Knowledge as Predicates 14.3.2 Conjunctive Normal Form 14.4 Resolution 14.4.1 Resolution in Propositional Calculus 14.4.2 Resolution in Predicate Calculus 14.5 From Predicate Calculus to Logic Programming 14.5.1 Clausal Form 14.5.2 Horn Clauses 14.5.3 Conversion Examples 14.5.4 Motif of Logic Programming 14.5.5 Resolution with Propositions in Clausal Form 14.5.6 Formalism Gone Awry 14.6 The Prolog Programming Language 14.6.1 Essential Prolog: Asserting Facts and Rules 14.6.2 Casting Horn Clauses in Prolog Syntax 14.6.3 Running and Interacting with a Prolog Program 14.6.4 Resolution, Unification, and Instantiation 14.7 Going Further in Prolog 14.7.1 Program Control in Prolog: A Binary Tree Example 14.7.2 Lists and Pattern Matching in Prolog 14.7.3 List Predicates in Prolog 14.7.4 Primitive Nature of append 14.7.5 Tracing the Resolution Process 14.7.6 Arithmetic in Prolog 14.7.7 Negationas Failure in Prolog 14.7.8 Graphs 14.7.9 Analogs Between Prolog and an RDBMS 14.8 Imparting More Control in Prolog: Cut 14.9 Analysis of Prolog 14.9.1 Prolog Vis-à-Vis Predicate Calculus 14.9.2 Reflection in Prolog 14.9.3 Metacircular Prolog Interpreter and WAM 14.10 The CLIPS Programming Language 14.10.1 Asserting Facts and Rules 14.10.2 Variables 14.10.3 Templates 14.10.4 Conditional Facts in Rules 14.11 Applications of Logic Programming 14.11.1 Natural Language Processing 14.11.2 Decision Trees 14.12 Thematic Takeaways 14.13 Chapter Summary 14.14 Notes and Further Reading 15 Conclusion 15.1 Language Themes Revisited 15.2 Relationship of Concepts 15.3 More Advanced Concepts 15.4 Bottom-up Programming 15.5 Further Reading Appendix A Python Primer A.1 Appendix Objective A.2 Introduction A.3 Data Types A.4 Essential Operators and Expressions A.5 Lists A.6 Tuples A.7 User-Defined Functions A.7.1 Simple User-Defined Functions A.7.2 Positional Vis-à-Vis Keyword Arguments A.7.3 Lambda Functions A.7.4 Lexical Closures A.7.5 More User-Defined Functions A.7.6 Local Binding and Nested Functions A.7.7 Mutual Recursion A.7.8 Putting It All Together: Mergesort A.8 Object-Oriented Programming in Python A.9 Exception Handling A.10 Thematic Takeaway A.11 Appendix Summary A.12 Notes and Further Reading Appendix B Introduction to ML (Online) B.1 Appendix Objective B.2 Introduction B.3 Primitive Types B.4 Essential Operators and Expressions B.5 Running an ML Program B.6 Lists B.7 Tuples B.8 User-Defined Functions B.8.1 Simple User-Defined Functions B.8.2 Lambda Functions B.8.3 Pattern-Directed Invocation B.8.4 Local Binding and Nested Functions: let Expressions B.8.5 Mutual Recursion B.8.6 Putting It All Together: Mergesort B.9 Declaring Types B.9.1 Inferredor Deduced B.9.2 Explicitly Declared B.10 Structures B.11 Exceptions B.12 Input and Output B.12.1 Input B.12.2 Parsing an Input File B.12.3 Output B.13 Thematic Takeaways B.14 Appendix Summary B.15 Notes and Further Reading Appendix C Introduction to Haskell (Online) C.1 Appendix Objective C.2 Introduction C.3 Primitive Types C.4 Type Variables, Type Classes, and Qualified Types C.5 Essential Operators and Expressions C.6 Running a Haskell Program C.7 Lists C.8 Tuples C.9 User-Defined Functions C.9.1 Simple User-Defined Functions C.9.2 Lambda Functions C.9.3 Pattern-Directed Invocation C.9.4 Local Binding and Nested Functions: let Expressions C.9.5 Mutual Recursion C.9.6 Putting It All Together: Mergesort C.10 Declaring Types C.10.1 Inferredor Deduced C.10.2 Explicitly Declared C.11 Thematic Takeaways C.12 Appendix Summary C.13 Notes and Further Reading Appendix D Getting Started with the Camille Programming Language (Online) D.1 Appendix Objective D.2 Grammar D.3 Installation D.4 Git Repository Structure and Setup D.5 How to Use Camille in a Programming Languages Course D.5.1 Module 0: Front End (Scanner and Parser) D.5.2 Chapter 10 Module: Introduction (Local Binding and Conditionals) D.5.3 Configuring the Language D.5.4 Chapter 11 Module: Intermediate (Functions and Closures) D.5.5 Chapter 12 Modules: Advanced (Parameter Passing, Including Lazy Evaluation) and Imperative (Statements and Sequential Evaluation) D.6 Example Usage: Non-interactively and Interactively (CLI) D.7 Solutions to Programming Exercises in Chapters 10–12 D.8 Notes and Further Reading Appendix E Camille Grammar and Language (Online) E.1 Appendix Objective E.2 Camille 0.1: Numbers and Primitives E.3 Camille 1.X:Local Binding and Conditional Evaluation E.4 Camille 2.X:Non-recursive and Recursive Functions E.5 Camille 3.X: Variable Assignment and Support for Arrays E.6 Camille 4.X: Sequential Execution Bibliography Index "Programming Languages: Concepts and Implementation is a textbook on programming language concepts from an implementation-oriented perspective. The book teaches language concepts from two complementary perspectives: implementation and paradigms. It covers the implementation of concepts through the incremental construction of a progressive series of interpreters in Python and Racket Scheme, for purposes of its combined simplicity and power, and assessing the differences in the resulting languages. The language being interpreted is called ChAmElEoN, referring to the recurring theme of morphing the implementation of the concepts in the language (e.g., from static scoping to dynamic scoping, or from pass-by-value to pass-by-reference)"-- Provided by publisher