This clearly written textbook provides an accessible introduction to the three programming paradigms of object-oriented/imperative, functional, and logic programming. Highly interactive in style, the text encourages learning through practice, offering test exercises for each topic covered. Review questions and programming projects are also presented, to help reinforce the concepts outside of the classroom. This updated and revised new edition features new material on the Java implementation of the JCoCo virtual machine. Topics and features: includes review questions and solved practice exercises, with supplementary code and support files available from an associated website; presents an historical perspective on the models of computation used in implementing the programming languages used today; provides the foundations for understanding how the syntax of a language is formally defined by a grammar; illustrates how programs execute at the level of assembly language, through the implementation of a stack-based Python virtual machine called JCoCo and a Python disassembler; introduces object-oriented languages through examples in Java, functional programming with Standard ML, and programming using the logic language Prolog; describes a case study involving the development of a compiler for the high level functional language Small, a robust subset of Standard ML. Undergraduate students of computer science will find this engaging textbook to be an invaluable guide to the skills and tools needed to become a better programmer. While the text assumes some background in an imperative language, and prior coverage of the basics of data structures, the hands-on approach and easy to follow writing style will enable the reader to quickly grasp the essentials of programming languages, frameworks, and architectures.
Author(s): Kent D. Lee
Publisher: Springer
Year: 2017
Language: English
Pages: 370
Preface
Acknowledgements
For Teachers
Contents
1 Introduction
1.1 Historical Perspective
1.2 Models of Computation
1.2.1 The Imperative Model
1.2.2 The Functional Model
1.2.3 The Logic Model
1.3 The Origins of a Few Programming Languages
1.3.1 A Brief History of C and C++
1.3.2 A Brief History of Java
1.3.3 A Brief History of Python
1.3.4 A Brief History of Standard ML
1.3.5 A Brief History of Prolog
1.4 Language Implementation
1.4.1 Compilation
1.4.2 Interpretation
1.4.3 Virtual Machines
1.5 Types and Type Checking
1.6 Chapter Summary
1.7 Review Questions
1.8 Solutions to Practice Problems
1.8.1 Solution to Practice Problem 1.1
1.8.2 Solution to Practice Problem 1.2
1.8.3 Solution to Practice Problem 1.3
1.8.4 Solution to Practice Problem 1.4
1.8.5 Solution to Practice Problem 1.5
2 Syntax
2.1 Terminology
2.2 Backus Naur Form (BNF)
2.2.1 BNF Examples
2.2.2 Extended BNF (EBNF)
2.3 Context-Free Grammars
2.3.1 The Infix Expression Grammar
2.4 Derivations
2.4.1 A Derivation
2.4.2 Types of Derivations
2.4.3 Prefix Expressions
2.4.4 The Prefix Expression Grammar
2.5 Parse Trees
2.6 Abstract Syntax Trees
2.7 Lexical Analysis
2.7.1 The Language of Regular Expressions
2.7.2 Finite State Machines
2.7.3 Lexer Generators
2.8 Parsing
2.9 Top-Down Parsers
2.9.1 An LL(1) Grammar
2.9.2 A Non-LL(1) Grammar
2.9.3 An LL(1) Infix Expression Grammar
2.10 Bottom-Up Parsers
2.10.1 Parsing an Infix Expression
2.11 Ambiguity in Grammars
2.12 Other Forms of Grammars
2.13 Limitations of Syntactic Definitions
2.14 Chapter Summary
2.15 Review Questions
2.16 Exercises
2.17 Solutions to Practice Problems
2.17.1 Solution to Practice Problem 2.1
2.17.2 Solution to Practice Problem 2.2
2.17.3 Solution to Practice Problem 2.3
2.17.4 Solution to Practice Problem 2.4
2.17.5 Solution to Practice Problem 2.5
2.17.6 Solution to Practice Problem 2.6
2.17.7 Solution to Practice Problem 2.7
2.17.8 Solution to Practice Problem 2.8
2.17.9 Solution to Practice Problem 2.9
2.17.10 Solution to Practice Problem 2.10
2.17.11 Solution to Practice Problem 2.11
3 Assembly Language
3.1 Overview of the JCoCo VM
3.2 Getting Started
3.3 Input/Output
3.4 If-Then-Else Statements
3.4.1 If-Then Statements
3.5 While Loops
3.6 Exception Handling
3.7 List Constants
3.8 Calling a Method
3.9 Iterating Over a List
3.10 Range Objects and Lazy Evaluation
3.11 Functions and Closures
3.12 Recursion
3.13 Support for Classes and Objects
3.13.1 Inheritance
3.13.2 Dynamically Created Classes
3.14 Chapter Summary
3.15 Review Questions
3.16 Exercises
3.17 Solutions to Practice Problems
3.17.1 Solution to Practice Problem 3.1
3.17.2 Solution to Practice Problem 3.2
3.17.3 Solution to Practice Problem 3.3
3.17.4 Solution to Practice Problem 3.4
3.17.5 Solution to Practice Problem 3.5
3.17.6 Solution to Practice Problem 3.6
3.17.7 Solution to Practice Problem 3.7
3.17.8 Solution to Practice Problem 3.8
3.17.9 Solution to Practice Problem 3.9
3.17.10 Solution to Practice Problem 3.10
3.17.11 Solution to Practice Problem 3.11
3.17.12 Solution to Practice Problem 3.12
4 Object-Oriented Programming
4.1 The Java Environment
4.2 The C++ Environment
4.2.1 The Macro Processor
4.2.2 The Make Tool
4.3 Namespaces
4.4 Dynamic Linking
4.5 Defining the Main Function
4.6 I/O Streams
4.7 Garbage Collection
4.8 Threading
4.9 The PyToken Class
4.9.1 The C++ PyToken Class
4.10 Inheritance and Polymorphism
4.11 Interfaces and Adapters
4.12 Functions as Values
4.13 Anonymous Inner Classes
4.14 Type Casting and Generics
4.15 Auto-Boxing and Unboxing
4.16 Exception Handling in Java and C++
4.17 Signals
4.18 JCoCo in Depth
4.19 The Scanner
4.20 The Parser
4.21 The Assembler
4.22 ByteCode
4.23 JCoCo's Class and Interface Type Hierarchy
4.24 Code
4.25 Functions
4.26 Classes
4.27 Methods
4.28 JCoCo Exceptions and Tracebacks
4.29 Magic Methods
4.30 Dictionaries
4.30.1 Two New Classes
4.30.2 Two New Types
4.30.3 Two New Instructions
4.31 Chapter Summary
4.32 Review Questions
4.33 Exercises
4.34 Solutions to Practice Problems
4.34.1 Solution to Practice Problem 4.1
4.34.2 Solution to Practice Problem 4.2
4.34.3 Solution to Practice Problem 4.3
4.34.4 Solution to Practice Problem 4.4
4.34.5 Solution to Practice Problem 4.5
4.34.6 Solution to Practice Problem 4.6
4.34.7 Solution to Practice Problem 4.7
4.34.8 Solution to Practice Problem 4.8
4.34.9 Solution to Practice Problem 4.9
5 Functional Programming
5.1 Imperative Versus Functional Programming
5.2 The Lambda Calculus
5.2.1 Normal Form
5.2.2 Problems with Applicative Order Reduction
5.3 Getting Started with Standard ML
5.4 Expressions, Types, Structures, and Functions
5.5 Recursive Functions
5.6 Characters, Strings, and Lists
5.7 Pattern Matching
5.8 Tuples
5.9 Let Expressions and Scope
5.10 Datatypes
5.11 Parameter Passing in Standard ML
5.12 Efficiency of Recursion
5.13 Tail Recursion
5.14 Currying
5.15 Anonymous Functions
5.16 Higher-Order Functions
5.16.1 Composition
5.16.2 Map
5.16.3 Reduce or Foldright
5.16.4 Filter
5.17 Continuation Passing Style
5.18 Input and Output
5.19 Programming with Side-effects
5.19.1 Variables in Standard ML
5.19.2 Sequential Execution
5.19.3 Iteration
5.20 Exception Handling
5.21 Encapsulation in ML
5.21.1 Signatures
5.21.2 Implementing a Signature
5.22 Type Inference
5.23 Building a Prefix Calculator Interpreter
5.23.1 The Prefix Calc Parser
5.23.2 The AST Evaluator
5.23.3 Imperative Programming Observations
5.24 Chapter Summary
5.25 Exercises
5.26 Solutions to Practice Problems
5.26.1 Solution to Practice Problem 5.1
5.26.2 Solution to Practice Problem 5.2
5.26.3 Solution to Practice Problem 5.3
5.26.4 Solution to Practice Problem 5.4
5.26.5 Solution to Practice Problem 5.5
5.26.6 Solution to Practice Problem 5.6
5.26.7 Solution to Practice Problem 5.7
5.26.8 Solution to Practice Problem 5.8
5.26.9 Solution to Practice Problem 5.9
5.26.10 Solution to Practice Problem 5.10
5.26.11 Solution to Practice Problem 5.11
5.26.12 Solution to Practice Problem 5.12
5.26.13 Solution to Practice Problem 5.13
5.26.14 Solution to Practice Problem 5.14
5.26.15 Solution to Practice Problem 5.15
5.26.16 Solution to Practice Problem 5.16, see Fig.5.27
5.26.17 Solution to Practice Problem 5.17
5.26.18 Solution to Practice Problem 5.18
5.26.19 Solution to Practice Problem 5.19
5.26.20 Solution to Practice Problem 5.20
5.26.21 Solution to Practice Problem 5.21
5.26.22 Solution to Practice Problem 5.22
5.26.23 Solution to Practice Problem 5.23
5.26.24 Solution to Practice Problem 5.24
6 Compiling Standard ML
6.1 ML-lex
6.2 The Small AST Definition
6.3 Using ML-yacc
6.4 Compiling and Running the Compiler
6.5 Function Calls
6.6 Let Expressions
6.7 Unary Negation
6.8 If-Then-Else Expressions
6.9 Short-Circuit Logic
6.10 Defining Functions
6.10.1 Curried Functions
6.10.2 Mutually Recursive Functions
6.11 Reference Variables
6.12 Chapter Summary
6.13 Review Questions
6.14 Exercises
6.15 Solutions to Practice Problems
6.15.1 Solution to Practice Problem 6.1
6.15.2 Solution to Practice Problem 6.2
6.15.3 Solution to Practice Problem 6.3
7 Logic Programming
7.1 Getting Started with Prolog
7.2 Fundamentals
7.3 The Prolog Program
7.4 Lists
7.5 The Accumulator Pattern
7.6 Built-In Predicates
7.7 Unification and Arithmetic
7.8 Input and Output
7.9 Structures
7.10 Parsing in Prolog
7.10.1 Difference Lists
7.11 Prolog Grammar Rules
7.12 Building an AST
7.13 Attribute Grammars
7.13.1 Synthesized Versus Inherited
7.14 Chapter Summary
7.15 Review Questions
7.16 Exercises
7.17 Solutions to Practice Problems
7.17.1 Solution to Practice Problem 7.1
7.17.2 Solution to Practice Problem 7.2
7.17.3 Solution to Practice Problem 7.3
7.17.4 Solution to Practice Problem 7.4
7.17.5 Solution to Practice Problem 7.5
7.17.6 Solution to Practice Problem 7.6
7.17.7 Solution to Practice Problem 7.7
7.17.8 Solution to Practice Problem 7.8
7.17.9 Solution to Practice Problem 7.9
7.17.10 Solution to Practice Problem 7.10
7.17.11 Solution to Practice Problem 7.11 (See Fig.7.13)
7.17.12 Solution to Practice Problem 7.12
8 Standard ML Type Inference
8.1 Why Static Type Inference?
8.1.1 Exception Program
8.1.2 A Bad Function Call
8.2 Type Inference Rules
8.3 Using Prolog
8.4 The Type Environment
8.5 Integers, Strings, and Boolean Constants
8.6 List and Tuple Constants
8.7 Identifiers
8.8 Function Application
8.8.1 Instantiation
8.9 Let Expressions
8.10 Patterns
8.11 Matches
8.12 Anonymous Functions
8.13 Sequential Execution
8.14 If-Then and While-Do
8.15 Exception Handling
8.16 Chapter Summary
8.17 Review Questions
8.18 Exercises
8.19 Solutions to Practice Problems
8.19.1 Solution to Practice Problem 8.1
8.19.2 Solution to Practice Problem 8.2
8.19.3 Solution to Practice Problem 8.3
9 Appendix A: The JCoCo Virtual Machine Specification
9.1 Types
9.2 JCoCo Magic and Attr Methods
9.3 Global Built-In Functions
9.4 Virtual Machine Instructions
9.5 Arithmetic Instructions
9.6 Load and Store Instructions
9.7 List, Tuple, and Dictionary Instructions
9.8 Stack Manipulation Instructions
9.9 Conditional and Iterative Execution Instructions
9.10 Function Execution Instructions
9.11 Special Instructions
10 Appendix B: The Standard ML Basis Library
10.1 The Bool Structure
10.2 The Int Structure
10.3 The Real Structure
10.4 The Char Structure
10.5 The String Structure
10.6 The List Structure
10.7 The Array Structure
10.8 The TextIO Structure
Bibliography
