book

Programming Languages: Concepts and Implementation

Name: Programming Languages: Concepts and Implementation
Author: Saverio Perugini
ISBN: 9781284222739

by Saverio Perugini

December 2021

Beginner

840 pages

47h 29m

English

Jones & Bartlett Learning

Read now

Unlock full access

Cover
Title Page
Copyright Page
Contents
Dedication
Preface
About the Author
List of Figures
List of Tables
1 Introduction

1.1 Text Objectives
1.2 Chapter Objectives
1.3 The World of Programming Languages
1.3.1 Fundamental Questions1.3.2 Bindings: Static and Dynamic1.3.3 Programming Language Concepts
1.4 Styles of Programming
1.4.1 Imperative Programming1.4.2 Functional Programming1.4.3 Object-Oriented Programming1.4.4 Logic/Declarative Programming1.4.5 Bottom-up Programming1.4.6 Synthesis: Beyond Paradigms1.4.7 Language Evaluation Criteria1.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 Expressions2.3.2 Finite-State Automata2.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 Syntax2.8.2 Parse Trees
2.9 Grammar Disambiguation
2.9.1 Operator Precedence2.9.2 Associativity of Operators2.9.3 The Classical Dangling else Problem
2.10 Extended Backus–Naur Form
2.11 Context-Sensitivity and Semantics
2.12 Thematic Takeaways
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 Parser3.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 PLY3.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 Programming5.2.2 Lambda Calculus5.2.3 Lists in Functional Programming
5.3 Lisp
5.3.1 Introduction5.3.2 Lists in Lisp
5.4 Scheme
5.4.1 An Interactive and Illustrative Session with Scheme5.4.2 Homoiconicity: No Distinction Between Program Code and Data
5.5 cons Cells: Building Blocks of Dynamic Memory Structures
5.5.1 List Representation5.5.2 List-Box Diagrams
5.6 Functions on Lists
5.6.1 A List length Function5.6.2 Run-Time Complexity: append and reverse5.6.3 The Difference Lists Technique
5.7 Constructing Additional Data Structures
5.7.1 A Binary Tree Abstraction5.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* Expressions5.9.2 The letrec Expression5.9.3 Using let and letrec to Define a Local Function5.9.4 Other Languages Supporting Functional Programming: ML and Haskell
5.10 Advanced Techniques
5.10.1 More List Functions5.10.2 Eliminating Expression Recomputation5.10.3 Avoiding Repassing Constant Arguments Across Recursive Calls
5.11 Languages and Software Engineering
5.11.1 Building Blocks as Abstractions5.11.2 Language Flexibility Supports Program Modification5.11.3 Malleable Program Design5.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 Problem6.10.2 The Upward FUNARG Problem6.10.3 Relationship Between Closures and Scope6.10.4 Uses of Closures6.10.5 The Upward and Downward FUNARG Problem in a Single Function6.10.6 Addressing the FUNARG Problem
6.11 Deep, Shallow, and Ad Hoc Binding
6.11.1 Deep Binding6.11.2 Shallow Binding6.11.3 Ad Hoc Binding
6.12 Thematic Takeaways
6.13 Chapter Summary
6.14 Notes and Further Reading
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 Conversion7.4.2 Type Casting: Explicit Conversion7.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 Form8.3.2 Currying and Uncurrying8.3.3 The curry and uncurry Functions in Haskell8.3.4 Flexibility in Curried Functions8.3.5 All Built-in Functions in Haskell Are Curried8.3.6 Supporting Curried Form Through First-Class Closures8.3.7 ML Analogs
8.4 Putting It All Together: Higher-Order Functions
8.4.1 Functional Mapping8.4.2 Functional Composition8.4.3 Sections in Haskell8.4.4 Folding Lists8.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 Arrays9.2.2 Records9.2.3 Undiscriminated Unions9.2.4 Discriminated Unions
9.3 Inductive Data Types
9.4 Variant Records
9.4.1 Variant Records in Haskell9.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: TreeNode9.6.2 Camille Parser Generator with Tree Builder
9.7 Data Abstraction
9.8 Case Study: Environments
9.8.1 Choices of Representation9.8.2 Closure Representation in Scheme9.8.3 Closure Representation in Python9.8.4 Abstract-Syntax Representation in Python
9.9 ML and Haskell: Summaries, Comparison, Applications, and Analysis
9.9.1 ML Summary9.9.2 Haskell Summary9.9.3 Comparison of ML and Haskell9.9.4 Applications9.9.5 Analysis
9.10 Thematic Takeaways
9.11 Chapter Summary
9.12 Notes and Further Reading
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 Values10.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 Camille10.6.2 Simple Interpreter for Camille10.6.3 Abstract-Syntax Trees for Arguments Lists10.6.4 REPL: Read-Eval-Print Loop10.6.5 Connecting the Components10.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 Camille11.2.2 Closures11.2.3 Augmenting the evaluate_expr Function11.2.4 A Simple Stack Object
11.3 Recursive Functions
11.3.1 Adding Support for Recursion in Camille11.3.2 Recursive Environment11.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 Evaluation12.2.2 Illustration of Pass-by-Value in Camille12.2.3 Reference Data Type12.2.4 Environment Revisited12.2.5 Stack Object Revisited
12.3 Survey of Parameter-Passing Mechanisms
12.3.1 Pass-by-Value12.3.2 Pass-by-Reference12.3.3 Pass-by-Result12.3.4 Pass-by-Value-Result12.3.5 Summary
12.4 Implementing Pass-by-Reference in the Camille Interpreter
12.4.1 Revised Implementation of References12.4.2 Reimplementation of the evaluate_operand Function
12.5 Lazy Evaluation
12.5.1 Introduction12.5.2 β-Reduction12.5.3 C Macros to Demonstrate Pass-by-Name: β-Reduction Examples12.5.4 Two Implementations of Lazy Evaluation12.5.5 Implementing Lazy Evaluation: Thunks12.5.6 Lazy Evaluation Enables List Comprehensions12.5.7 Applications of Lazy Evaluation12.5.8 Analysis of Lazy Evaluation12.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
13 Control and Exception Handling
13.1 Chapter Objectives
13.2 First-Class Continuations
13.2.1 The Concept of a Continuation13.2.2 Capturing First-Class Continuations: call/cc
13.3 Global Transfer of Control with Continuations
13.3.1 Nonlocal Exits13.3.2 Breakpoints13.3.3 First-Class Continuations in Ruby
13.4 Other Mechanisms for Global Transfer of Control
13.4.1 The goto Statement13.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 Calls13.5.2 Lexically Scoped Exceptions: break and continue13.5.3 Stack Unwinding/Crawling13.5.4 Dynamically Scoped Exceptions: Exception-Handling Systems13.5.5 First-Class Continuations
13.6 Control Abstraction
13.6.1 Coroutines13.6.2 Applications of First-Class Continuations13.6.3 The Power of First-Class Continuations
13.7 Tail Recursion
13.7.1 Recursive Control Behavior13.7.2 Iterative Control Behavior13.7.3 Tail-Call Optimization13.7.4 Space Complexity and Lazy Evaluation
13.8 Continuation-Passing Style
13.8.1 Introduction13.8.2 A Growing Stack or a Growing Continuation13.8.3 An All-or-Nothing Proposition13.8.4 Trade-off Between Time and Space Complexity13.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 Predicates14.3.2 Conjunctive Normal Form
14.4 Resolution
14.4.1 Resolution in Propositional Calculus14.4.2 Resolution in Predicate Calculus
14.5 From Predicate Calculus to Logic Programming
14.5.1 Clausal Form14.5.2 Horn Clauses14.5.3 Conversion Examples14.5.4 Motif of Logic Programming14.5.5 Resolution with Propositions in Clausal Form14.5.6 Formalism Gone Awry
14.6 The Prolog Programming Language
14.6.1 Essential Prolog: Asserting Facts and Rules14.6.2 Casting Horn Clauses in Prolog Syntax14.6.3 Running and Interacting with a Prolog Program14.6.4 Resolution, Unification, and Instantiation
14.7 Going Further in Prolog
14.7.1 Program Control in Prolog: A Binary Tree Example14.7.2 Lists and Pattern Matching in Prolog14.7.3 List Predicates in Prolog14.7.4 Primitive Nature of append14.7.5 Tracing the Resolution Process14.7.6 Arithmetic in Prolog14.7.7 Negation as Failure in Prolog14.7.8 Graphs14.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 Calculus14.9.2 Reflection in Prolog14.9.3 Metacircular Prolog Interpreter and WAM
14.10 The CLIPS Programming Language
14.10.1 Asserting Facts and Rules14.10.2 Variables14.10.3 Templates14.10.4 Conditional Facts in Rules
14.11 Applications of Logic Programming
14.11.1 Natural Language Processing14.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 FunctionsA.7.2 Positional Vis-à-Vis Keyword ArgumentsA.7.3 Lambda FunctionsA.7.4 Lexical ClosuresA.7.5 More User-Defined FunctionsA.7.6 Local Binding and Nested FunctionsA.7.7 Mutual RecursionA.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
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 FunctionsB.8.2 Lambda FunctionsB.8.3 Pattern-Directed InvocationB.8.4 Local Binding and Nested Functions: let ExpressionsB.8.5 Mutual RecursionB.8.6 Putting It All Together: Mergesort
B.9 Declaring Types
B.9.1 Inferred or DeducedB.9.2 Explicitly Declared
B.10 Structures
B.11 Exceptions
B.12 Input and Output
B.12.1 InputB.12.2 Parsing an Input FileB.12.3 Output
B.13 Thematic Takeaways
B.14 Appendix Summary
B.15 Notes and Further Reading
Appendix C Introduction to Haskell
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 FunctionsC.9.2 Lambda FunctionsC.9.3 Pattern-Directed InvocationC.9.4 Local Binding and Nested Functions: let ExpressionsC.9.5 Mutual RecursionC.9.6 Putting It All Together: Mergesort
C.10 Declaring Types
C.10.1 Inferred or DeducedC.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
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 LanguageD.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
E.1 Appendix Objective
E.2 Camille 0.1: Numbers and Primitives
E.3 Camille 1.χ: Local Binding and Conditional Evaluation
E.4 Camille 2.χ: Non-recursive and Recursive Functions
E.5 Camille 3.χ: Variable Assignment and Support for Arrays
E.6 Camille 4.χ: Sequential Execution
Bibliography
Index
Colophon

Content preview from Programming Languages: Concepts and Implementation

9.6 Abstract-Syntax Tree for Camille

A goal of Part II of this text is to establish an understanding of data abstraction techniques so we can harness them in our construction of environment-passing interpreters, for purposes of simplicity and efficiency, in Part III.

9.6.1 Camille Abstract-Syntax Tree Data Type: TreeNode

The following abstract-syntax tree data type TreeNode is used in the abstract-syntax trees of Camille programs for our Camille interpreters developed in Part III:

A set of 17 code lines in a Camille program that uses the data type Tree Node. — Description

Continuation of the code in a Camille program that uses the data type Tree Node consisting of 35 lines. — Description

9.6.2 Camille Parser Generator ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Concepts and Semantics of Programming Languages 1

Publisher Resources

ISBN: 9781284222739

Cloud Computing

Data Engineering

Data Science

AI & ML