Madhavan Mukund

Programming Language Concepts

January-April, 2024

Administrative details

• Instructors: Madhavan Mukund, S P Suresh

• Teaching Assistants: Ashwin Baskar (ashwin), Arghyadip Chakraborty (arghyadip), Shubh Sharma (shubhsharma)

• Evaluation:

  • Quizzes (10%), assignments (30%), midsemester exam (20%), final exam (40%)

  • Copying is fatal

• Textbooks and lecture notes:

  John C Mitchell: Concepts in Programming Languages, Cambridge University Press (2004)

  Michael L Scott: Programming Language Pragmatics, (4th edition), Morgan Kaufmann (2016)

  Alfred V Aho, Monica S Lam, Ravi Sethi, Jeffrey D Ullman: Compilers: Principles, Techniques, and Tools, Pearson (2013)

  Madhavan Mukund: Lecture notes on Programming Language Concepts (2004)

  Madhavan Mukund: Lecture notes on Generic Programming in Java (2006)

• Assignment 1, 11 April 2024, due 22 April 26 April 2024.

• Assignment 2, 25 April 2024, due 3 May 2024.

Lecture summary

• Lecture 1, 9 Jan 2024 (Class Notes (pdf))

  • Introduction
  • Declarative vs imperative programming
  • Modular software development and refinement
  • Abstract datatypes and objects

  Mitchell: Chapter 9 (upto 9.2.2)

• Lecture 2, 11 Jan 2024 (Class Notes (pdf))

  • Object-oriented programming: abstraction, subtyping, dynamic dispatch, inheritance
  • Classes and objects: Python examples and the need for public/private modifiers

  Mitchell: Chapter 10 (upto 10.2)

• Lecture 3, 16 Jan 2024 (Class Notes (pdf))

  • Introduction to Java: compilation, basic datatypes, control flow

• Lecture 4, 18 Jan 2024 (Class Notes (pdf) )

  • Java: Control flow
  • Java: Classes, subclasses and inheritance
  • Java: Dynamic dispatch, runtime polymorphism, type casting

• Lecture 5, 23 Jan 2024 (Slides (pdf) )

  Java: class hierarchy and polymorphism

  • Modifiers: private, static, final
  • Java class hierarchy
  • Overriding methods

  Interfaces

  • Interfaces and implementations
  • Private classes and nested objects

• Lecture 6, 25 Jan 2024 (Slides (pdf) )

  • Java: Interfaces — callbacks, iterators
  • Java: Structural polymorphism and generics

• Lecture 7, 30 Jan 2024 (Slides (pdf) )

  • Java: generics
  • Introduction to memory management

  Quiz 1, Solutions.

• Lecture 8, 01 Feb 2024 (Slides (pdf) )

  • Storage allocation: scope and lifetime of variables, activation records, call graphs and call stack, control and access link, heaps and dynamic allocation, memory management, garbage and dangling pointers

  Reading material: (Note, there will be details in the references below that were not discussed in class.)

  • Mitchell: Chapter 7, 7.1, 7.2, 7.3.1, 7.3.3
  • Scott: Chapter 3.1, 3.2, 3.3.1, 3.3.2
  • Aho et al: Chapter 7.1–7.4

• Lecture 9, 08 Feb 2024 (Class Notes (pdf), Rust Notebook (source, pdf) )

  • Introduction to Rust: variable declarations, mutability, typing, functions, expressions, control flow
  • Reference: The Rust Programming Language, Chapter 3

• Lecture 10, 13 Feb 2024 (Class Notes (pdf), Rust Notebook (source, pdf) )

  • Rust: ownership – moving and borrowing, references, slices
  • Reference: The Rust Programming Language, Chapter 4

• Lecture 11, 15 Feb 2024 (Class Notes (pdf), Rust Notebook (source, pdf) )

  • Rust: Tuples, arrays, structs, methods, generics, traits, lifetimes
  • Reference: The Rust Programming Language, Chapter 3.2, 5, 10

• Lecture 12, 20 Feb 2024 (Slides (pdf) )

  • Error handling in Java

  Quiz 2, Solutions.

• Lecture 13, 22 Feb 2024 (Rust Notebook (source, pdf) )

  • Rust: Enums, pattern matching, error handling
  • Reference: The Rust Programming Language, Chapter 6, 9

• Lecture 14, 05 Mar 2024 (Slides (pdf) )

  • Concurrency: Threads, Processes, Race Conditions, Mutual Exclusion

• Lecture 15, 07 Mar 2024 (Slides (pdf) )

  • PL support for concurrency: semaphores, monitors
  • Monitors and threads in Java

• Lecture 16, 14 Mar 2024 (Rust Notebook (source, pdf) )

  • Rust: Closures, threads, channels and message passing, mutexes and shared variables
  • Reference: The Rust Programming Language, Chapter 13.1, 15.4, 16.1, 16.2, 16.3

• Lecture 17, 19 Mar 2024 (Slides (pdf) )

  • Introduction to λ-calculus
  • Reading material: Lecture Notes on the Lambda Calculus, Peter Selinger

• Lecture 18, 21 Mar 2024 (Slides (pdf) )

  • Encoding arithmetic in the λ calculus — Church numerals, successor, addition, multiplication, exponentiation

• Lecture 19, 26 Mar 2024 (Slides (pdf) )

  • Introducing recursive functions: composition, primitive recursion, minimization
  • Example recursive functions: addition, multiplication, exponentiation, predecessor, subtraction, &hellip

• Lecture 20–21, 28 Mar/04 Apr 2024 (Slides (pdf) )

  • Encoding recursive functions
  • Encoding primitive recursion via iteration
  • Using fixed-point combinators to solve equations
  • Encoding mu-recursion by solving recursive equations

  Turing machines and recursive functions

  • Extra notes on the power of recursive functions
  • Encoding Turing machine configurations, transitions, and runs using primitive recursive functions
  • Checking whether a number codes a run of a Turing machine on a given input, using a primitive recursive predicate
  • Encoding a Turing computable function by applying mu-recursion on the above predicate
  • Kleene's normal form theorem

• Lecture 22, 09 Apr 2024 (Slides (pdf) )

  Properties of reduction

  • Normal forms
  • Do all terms have a normal form?
  • Multiple possible reductions and do they all lead to the same normal form?
  • Church-Rosser Theorem
  • Can we decide if a term has a normal form?

• Lecture 23, 16 Apr 2024 (Slides (pdf) )

  Typed λ-calculus

  • Basic rules for Curry typing
  • Curry typing examples
  • Typing encodings for natural numbers
  • Weak and strong normalization

• Lecture 24, 18 Apr 2024 (Slides (pdf) )

  • Principal types
  • Hindley-Milner algorithm for computing principal types
  • Handling local definitions
  • Handling local recursive definitions

• Lecture 25, 23 Apr 2024 (Slides (pdf) )

  • Unification algorithm and examples