Madhavan Mukund

Programming Language Concepts

January-April, 2025

Administrative details

• Instructors: Madhavan Mukund, S P Suresh

• Teaching Assistants: TBA

• Evaluation:

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

  • Copying is fatal

• Course outline (tentative)

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

  • Object oriented programming: Classes, subclasses and inheritance, dynamic dispatch, runtime polymorphism, interfaces

  • Generic programming

  • Reference passing: ownership, moving and borrowing

  • Exception handling

  • Concurrent programming: threads, race conditions, mutual exclusion, semaphores, monitors, message passing, closures

  • Theory of functional programming

    • Untyped lambda calculus: syntax, reduction, encoding arithmetic, encoding recursive functions, normal forms, Church-Rosser theorem

    • Typed lambda calculus: Curry typing, weak and strong normalization, Hindley-Milner type inference, unification

• Prerequisites

  • Exposure to some imperative and functional programming languages (e.g. Python, Haskell)

  • Java and Rust will be introduced to illustrate concepts listed above

• Textbooks and lecture notes:

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

  • Steve Klabnik, Carol Nichols: The Rust Programming Language, No Starch Press (2023)

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

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

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

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

Assignments

• Assignment 1, 3 February 2025, due 12 February 2025.

Lecture summary

• Lecture 1, 7 Jan 2025 (Class Notes (pdf))

  • Introduction
  • Declarative vs imperative programming
  • Storage, passing references
  • Abstract datatypes and objects

• Lecture 2, 16 Jan 2025 (Class Notes (pdf))

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

• Lecture 3, 21 Jan 2025 (Class Notes (pdf))

  • Introduction to Java: basic datatypes, control flow, classes, subclasses

• Lecture 4, 23 Jan 2025 (Class Notes (pdf))

  Java: class hierarchy and polymorphism

  • Subclasses and inheritance
  • Dynamic dispatch and runtime polymorphism
  • Java class hierarchy
  • Overriding methods
  • Abstract methods and abstract classes
  • Interfaces and implementations

• Lecture 5, 28 Jan 2025 (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 6, 30 Jan 2025 (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

  Quiz 1, Solutions.

• Lecture 7, 4 Feb 2025 (Rust Notebook (source, pdf) )

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

• Lecture 8, 6 Feb 2025 (Slides (pdf) )

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

• Lecture 9, 11 Feb 2025 (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 10, 13 Feb 2025 (Slides (pdf) )

  • Error handling in Java

  Quiz 2, Solutions.