book

Programming Languages: Concepts and Implementation

by Saverio Perugini

December 2021

Beginner

840 pages

47h 29m

English

Jones & Bartlett Learning

Read now

Unlock full access

1.3.1 Fundamental Questions1.3.2 Bindings: Static and Dynamic1.3.3 Programming Language Concepts
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
2.3.1 Regular Expressions2.3.2 Finite-State Automata2.3.3 Regular Languages
2.4.1 Regular Grammars
2.8.1 Modeling Some Semantics in Syntax2.8.2 Parse Trees
2.9.1 Operator Precedence2.9.2 Associativity of Operators2.9.3 The Classical Dangling else Problem
3.4.1 A Complete Recursive-Descent Parser3.4.2 A Language Generator
3.5.1 A Complete Example in lex and yacc
3.6.1 A Complete Example in PLY3.6.2 Camille Scanner and Parser Generators in PLY
5.2.1 Hallmarks of Functional Programming5.2.2 Lambda Calculus5.2.3 Lists in Functional Programming
5.3.1 Introduction5.3.2 Lists in Lisp
5.4.1 An Interactive and Illustrative Session with Scheme5.4.2 Homoiconicity: No Distinction Between Program Code and Data
5.5.1 List Representation5.5.2 List-Box Diagrams
5.6.1 A List length Function5.6.2 Run-Time Complexity: append and reverse5.6.3 The Difference Lists Technique
5.7.1 A Binary Tree Abstraction5.7.2 A Binary Search Tree Abstraction
5.8.1 atom?, list-of-atoms?, and list-of-numbers?5.8.2 Factoring out the list-of Pattern
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.1 More List Functions5.10.2 Eliminating Expression Recomputation5.10.3 Avoiding Repassing Constant Arguments Across Recursive Calls
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
6.2.1 What Is a Closure?6.2.2 Static Vis-à-Vis Dynamic Properties
6.4.1 Lexical Scoping
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.1 Deep Binding6.11.2 Shallow Binding6.11.3 Ad Hoc Binding
7.4.1 Type Coercion: Implicit Conversion7.4.2 Type Casting: Explicit Conversion7.4.3 Type Conversion Functions: Explicit Conversion
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.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
9.2.1 Arrays9.2.2 Records9.2.3 Undiscriminated Unions9.2.4 Discriminated Unions
9.4.1 Variant Records in Haskell9.4.2 Variant Records in Scheme: (define-datatype ...) and (cases ...)
9.6.1 Camille Abstract-Syntax Tree Data Type: TreeNode9.6.2 Camille Parser Generator with Tree Builder
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.1 ML Summary9.9.2 Haskell Summary9.9.3 Comparison of ML and Haskell9.9.4 Applications9.9.5 Analysis
10.4.1 Expressed Values Vis-à-Vis Denoted Values10.4.2 Defined Language Vis-à-Vis Defining Language
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
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.1 Adding Support for Recursion in Camille11.3.2 Recursive Environment11.3.3 Augmenting evaluate_expr with New Variants
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.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.1 Revised Implementation of References12.4.2 Reimplementation of the evaluate_operand Function
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
13.2.1 The Concept of a Continuation13.2.2 Capturing First-Class Continuations: call/cc
13.3.1 Nonlocal Exits13.3.2 Breakpoints13.3.3 First-Class Continuations in Ruby
13.4.1 The goto Statement13.4.2 Capturing and Restoring Control Context in C: setjmp and longjmp
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.1 Coroutines13.6.2 Applications of First-Class Continuations13.6.3 The Power of First-Class Continuations
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.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.10.1 Defining call/cc in Continuation-Passing Style
14.3.1 Representing Knowledge as Predicates14.3.2 Conjunctive Normal Form
14.4.1 Resolution in Propositional Calculus14.4.2 Resolution in Predicate Calculus
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.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.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.9.1 Prolog Vis-à-Vis Predicate Calculus14.9.2 Reflection in Prolog14.9.3 Metacircular Prolog Interpreter and WAM
14.10.1 Asserting Facts and Rules14.10.2 Variables14.10.3 Templates14.10.4 Conditional Facts in Rules
14.11.1 Natural Language Processing14.11.2 Decision Trees
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
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.1 Inferred or DeducedB.9.2 Explicitly Declared
B.12.1 InputB.12.2 Parsing an Input FileB.12.3 Output
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.1 Inferred or DeducedC.10.2 Explicitly Declared
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)

Content preview from Programming Languages: Concepts and Implementation

4.1 Chapter Objectives

Describe the differences between a compiler and an interpreter.
Explore a variety of implementations for programming languages.

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.

Start your free trial

Concepts and Semantics of Programming Languages 1

Therese Hardin, Mathieu Jaume, Francois Pessaux, Veronique Viguie Donzeau-Gouge

Introduction to Programming Languages

Arvind Kumar Bansal

Learning Functional Programming

Jack Widman

Programming C# 10

Ian Griffiths

Publisher Resources

ISBN: 9781284222739