PL. Programming Languages (5 core hours)

PL1. History and overview of programming languages (core -- 2 hours)

  Early languages (FORTRAN, ALGOL, COBOL, LISP, BASIC)
  The evolution of procedural languages
  Object-oriented paradigm and languages
  Mostly-functional, algorithmic, higher-order languages with eager evaluation
  Purely-functional, algorithmic paradigm
  Declarative (non-algorithmic) languages
  Parallel programming paradigms
  Scripting paradigm

PL2. Virtual machines (core -- 1 hour)

What is a virtual machine?
Hierarchy of virtual machines presented to the user

PL3. Introduction to language translation (core -- 2 hours)

Comparison of pure interpreters vs. compilers
Language translation phases (lexical analysis, parsing, code generation, optimization)

PL4. Language translation systems

  Application of regular expressions in lexical scanners
  Parsing (concrete and abstract syntax, abstract syntax trees)
  Code generation by tree walking
  Optimization techniques
  Application of CFGs in table-driven and recursive descent parsing

PL5. Type systems

  Data type as set of values with set of operations
  Data types (elementary, product, coproduct, algebraic, recursive, arrow, parameterized)
  Type checking models
  Semantic models of user-defined types (type abbreviations, ADTs, type equality)
  Parametric polymorphism
  Subtype polymorphism
  Type-checking algorithms

PL6. Models of execution control

  Order of evaluation of sub-expressions
  Exceptions and exception handling
  Parallel composition (S1||S2)
  Functions with delayed evaluation (closures, lazy evaluation)

PL7. Declaration, modularity, and storage management

  Declaration models (binding, visibility, scope, and lifetime)
  Parameterization mechanisms
  Type parameterization
  Mechanisms for sharing and restricting visibility of declarations
  Garbage collection

PL8. Programming language semantics

  Informal semantics
  Overview of formal semantics
  Denotational Semantics.
  Axiomatic Semantics

PL9. Functional programming paradigms

  Overview and motivation
  Recursion over lists, natural numbers, trees, and other recursively-defined data
  Pragmatics (debugging by divide and conquer; persistency of data structures)
  Amortized efficiency for functional data structures
  Closures, and uses of functions as data (infinite sets, streams)

PL10. Object-oriented programming paradigms

  Mechanisms for defining classes and instances
  Object creation and initialization
  Inheritance and dynamic dispatch
  Sketch of run-time representation of objects and method tables
  Distinction between subtyping and inheritance
  Advanced OO type problems

PL11. Language-based constructs for parallelism

  Communication primitives for tasking models with explicit communication
  Communication primitives for tasking models with shared memory
  Programming primitives for data-parallel models
  Comparison of language features for parallel and distributed programming
  Optimistic concurrency control vs. locking and transactions
  Coordination languages (Linda)
  Asynchronous remote procedure calls (pipes)
  Other approaches (functional, nondeterministic)