Programming Languages: Concepts and Implementation

Programming Languages: Concepts and Implementation

by Saverio Perugini
Released December 2021
Publisher(s): Jones & Bartlett Learning
ISBN: 9781284222739

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

Programming Languages: Concepts and Implementation 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.

Table of contents

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

Product information

  • Title: Programming Languages: Concepts and Implementation
  • Author(s): Saverio Perugini
  • Release date: December 2021
  • Publisher(s): Jones & Bartlett Learning
  • ISBN: 9781284222739