Programming Language Principles and Paradigms

PDF version of this text.

This document was built on Jan 27, 2024.

Foundations

• Introduction
• Basic Python
  • Variables
  • Basic Data Structures
  • Compound Statements
  • Function Definitions
  • Class Definitions
  • Modules
  • Executing a Module
  • Python Reference Semantics
• Basic Elements
  • Levels of Description
    • Lexical Structure
    • Syntax
    • Semantics
  • Entities, Objects, and Variables
  • L-Values and R-Values
  • Expressions
  • Statements
• Names and Environments
  • Blocks
  • Name Lookup
  • Nested Inline Blocks
  • Scope in Functions
  • Static Scope
  • Dynamic Scope
  • Point of Declaration or Definition
  • Implementation Strategies
• Control Flow
  • Expression Sequencing
    • Short Circuiting
    • Explicit Sequences
    • Compound Assignment
  • Statement Sequences
  • Unstructured Transfer of Control
  • Structured Control
    • Conditionals
    • Loops
    • Loop Termination
  • Exceptions
• Memory Management
  • Storage Duration Classes
    • Static Storage
    • Automatic Storage
    • Thread-Local Storage
    • Dynamic Storage
  • Value and Reference Semantics
  • RAII and Scope-Based Resource Management
  • Garbage Collection
    • Reference Counting
    • Tracing Collectors
    • Finalizers
• Grammars
  • Regular Expressions
  • Context-Free Grammars
  • Grammars in Programming Languages
    • Vexing Parse

Functional Programming

• Introduction to Scheme
  • Expressions
  • Definitions
  • Compound Values
  • Symbolic Data
• Functions
  • Keyword Arguments
  • Default Arguments
  • Variadic Functions
  • Parameter Passing
  • Evaluation of Function Calls
• Recursion
  • Activation Records
  • Tail Recursion
• Higher-Order Functions
  • Function Objects
  • Functions as Parameters
    • Function Pointers
    • Binding Policy
  • Nested Functions
    • Decorators
• Lambda Functions
  • Scheme
  • Python
  • Java
  • C++
  • Common Patterns
    • Sequence Patterns
      • Map
      • Reduce
      • Filter
      • Any
    • Composition
    • Partial Application and Currying
• Continuations
  • Restricted Continuations
    • Subroutines
    • Exceptions
    • Generators
  • First-Class Continuations
    • Signaling Errors
    • Call and Return
    • Exceptions

Theory

• Lambda Calculus
  • Non-Terminating Computation
  • Normal-Order Evaluation
  • Encoding Data
    • Booleans
    • Pairs
    • Church Numerals
  • Recursion
  • Equivalent Models
• Operational Semantics
  • Language
  • States and Transitions
  • Expressions
    • Arithmetic Expressions
    • Order of Evaluation
    • Boolean Expressions
  • Statements
  • Examples
  • Operational Semantics for Lambda Calculus
• Formal Type Systems
  • Variables
  • Functions
  • Subtyping
    • Subtyping and Arithmetic Operators
    • The Top Type
    • Subtyping and Functions
  • Full Typing Rules

Data Abstraction

• Functional Data Abstraction
  • Pairs and Lists
  • Message Passing
  • Lists
  • Dictionaries
  • Dispatch Dictionaries
• Object-Oriented Programming
  • Members
  • Access Control
  • Kinds of Methods
  • Nested and Local Classes
  • Implementation Strategies
• Inheritance and Polymorphism
  • Types of Inheritance
  • Class Hierarchies
  • Method Overriding
    • Covariance and Contravariance
    • Accessing Hidden or Overridden Members
  • Implementing Dynamic Binding
    • Full Lookup and Dispatch Process
  • Multiple Inheritance
    • Dictionary-Based Implementation
    • Record-Based Implementation
• Static Analysis
  • Types
    • Type Equivalence
    • Type Compatibility
    • Type Inference
  • Control-Flow Analysis
• Dynamic Typing
• Generics
  • Implicit Parametric Polymorphism
  • Explicit Parametric Polymorphism
    • Non-Type Parameters
    • Constraints
    • Implementation
    • Java Generics
    • Curiously Recurring Template Pattern
  • Duck Typing
• Modules and Namespaces
  • Translation Units
  • Modules, Packages, and Namespaces
  • Linkage
  • Information Hiding
  • Initialization

Declarative Programming

• Logic Programming
  • Prolog
    • Lists
    • Arithmetic
    • Side Effects
  • Unification and Search
    • Search Order and Backtracking
  • The Cut Operator
  • Negation
  • Examples
• Constraints and Dependencies
  • Constraint Logic Programming
    • Search
    • Examples
  • Make
• Pattern Matching

Metaprogramming

• Macros and Code Generation
  • Scheme Macros
  • CPP Macros
    • Stringification and Concatenation
    • The Macro Namespace
  • Code Generation
• Template Metaprogramming
  • Pairs
  • Numerical Computations
  • Templates and Function Overloading
  • SFINAE
  • Ensuring a Substitution Failure
  • Variadic Templates
• Example: Multidimensional Arrays
  • Points
  • Domains
  • Arrays
  • Stencil
  • Nested Iteration

Concurrent Programming

• Parallel Computing
  • Parallelism in Python
    • Threading
    • Multiprocessing
  • The Problem with Shared State
  • When No Synchronization is Necessary
  • Synchronized Data Structures
  • Locks
  • Barriers
  • Message Passing
  • Application Examples
    • Web Crawler
    • Particle Simulator
  • Synchronization Pitfalls
    • Under-synchronization
    • Over-synchronization
    • Deadlock
  • Conclusion
• Asynchronous Tasks
  • Limiting the Number of Tasks
  • Launch Policy

About

This text is based on many resources, including the classic textbook Structure and Interpretation of Computer Programs (SICP) by Abelson and Sussman, its Python adaptation Composing Programs by DeNero et al (available here), and Wikipedia. These resources are all licensed for adaptation and reuse under Creative Commons.

This text was originally written for EECS 490, the Programming Languages course at the University of Michigan, by Amir Kamil in Fall 2016. This is version 0.4 of the text.

This text is licensed under the Creative Commons Attribution-ShareAlike 4.0 International license.