CSC324: Principles of Programming Languages

Welcome to the Summer 2020 offering of CSC324.

This website is under construction!

Sales Pitch and Course Overview

Some of you may be wondering why taking this class would be a better use of your summer than learning the tin flute or finishing Infinite Jest:

Up to this point, your study of programming languages has been restricted to those in the imperative programming style: in such languages, a program is a series of statements, executed in turn, that change the values of data structures within the program (including, to take into account changes in control flow, the program counter of the computer's CPU).

While undeniably useful, the imperative programming style has its limits. As any CS student debugging a "how did this variable get set to THIS??" puzzle at 2:30 AM will tell you, mutable state makes programs harder to understand, particularly as programs become larger, more complex, and more parallel.

You have also seen strategies for abstracting a large program into smaller pieces by modularizing related functions into a shared library, or hiding private pieces of data within an instance of a class.

Building such abstractions, however, ends at changing the language itself. For instance, Java does not let developers design a new kind of loop construct, new syntax cannot be added (with some very limited exceptions), and instances where core language features can be changed are typically considered bugs. (For fun, in python 2.x, try assigning (True, False) to (False, True) and see if the value produced by (1 == 2) == False makes sense to you!)

By contrast, when one programs in a language that supports metaprogramming, functionality is extended not just by building reusable components and exposing them as classes or libraries, but by extending the programming language itself into a domain-specific language, that interfaces tidily with other parts of a program.

We will also begin a study of type theory, a branch of mathematics related to set theory and abstract algebra. Type theory allows a wide range of bugs to be caught at compile time, and, in the limit, can generate machine-checked proofs of correctness about components of a program.

In this course, we will learn how to quantify the limits of the imperative programming style and propose ones that address their shortcomings by the formal study of programming languages. Concretely, you will learn about the functional programming paradigm through the study of two such languages: Racket, and Haskell. By contrasting these languages with traditional imperative languages like Python and Java, we’ll gain greater insight into the important questions surrounding program language design, and ultimately the design of programs itself.

By the end of this course, you will be in a good position to learn industrial functional programming languages such as Scala, FP-inspired extensions to languages such as TypeScript, or even improve the code you write in imperative languages. You will also be prepared for further study in advanced programming language topics, such as compiler construction, the theory of computation, and language runtime design.

Course materials

Announcements and discussions will take place on Quercus (login required). Please keep an eye out for any course communications posted there.

There is no official textbook; but we will be using David Liu's notes for this class.

Lecture streams are listed on the course's Blackboard Collaborate page.

Please see the syllabus for detailed course information. For course-related questions, please contact the course staff or post on the course forum.

Course schedule

Topics Materials Coursework Other materials
Week 1 (6 May)
  • Course overview
  • The downsides of programming with state
  • Metaprogramming: modifying programs with programs
  • An introduction to type theory
Lecture 0 slides
Lecture 1 slides

Wat: A short humourous tour of unintended consequences in programming language design

Growing A Language: a lecture that presents metaprogramming in a clever, self-recursive way. Note: the opening example is clearly dated, but the presenter addresses his oversimplified example later on in the talk.

An experiment in software prototyping productivity: A user study that makes a compelling argument for programming in the functional style

 

Week 2 (13 May)
  • Syntax, semantics, and grammars
  • The Lambda Calculus
  • Computation on recursive datatypes
  • Patterns for pattern matching
  • List operations as algebra
  • Tail-call optimisation

Lecture 2 slides
Lecture 3 slides



Lecture 3 Racket file

Exercise 1
Lab 1

Implementing primitives in the Lambda Calculus

Racket pattern matching syntax

 

HTdP: What is '()? What is cons?

"Hey, cat, you got a tail?": Your animal fix for the week.

 

HTdP: Designing with Self-Referential Data Structures

 

Week 2 (20 May)
Mini-week: no lab on 18 May
  • Algebraic data types
  • Higher-order functions on lists: map, filter, fold,...
  • Currying and partial evaluation
  • Functions returning functions

Lecture 4 slides
Lecture 5 slides

Lecture 4 Racket file
Lecture 5 Racket file

Exercise 2
Lab 2

Data constructors as first class values
LYAH: Algebraic data types

Mini-lecture: name binding using let and lambda

Week 3 (27 May)
  • Static and Dynamic Scope
  • Strict and non-strict evaluation

Lecture 6 slides
Lecture 7 slides


Lecture 6 Racket file
Lecture 7 Racket file

Exercise 3
Lab 3

A tutorial on the universality and expressiveness of fold"

Video example of quasiquoting

Week 4 (3 June)
  • Object systems
  • Pattern-based macros

Lecture 8 slides Lecture 9 slides

Lecture 8 racket file
Lecture 9 racket file

Exercise 4
Lab 4

Fear of Macros Basic Macrology

Week 5 (10 June)
  • Self-reference in classes
  • Generators, lazy evaluation and streams

Lecture 10 slides 

Lecture 11 slides

 

Lecture 10 racket file
Lecture 11 racket file

 

 

Quiz 1: Take on Monday, 8 June

Mini-lecture: Structural recursion worked example

COURSE BREAK

Assignment 1: Due by Friday, 26 June Mini-lecture: Co-recursion and Lindenmayer Systems
Week 6 (6 July) 

  • The ambiguous operator and non-deterministic expressions
  • Local mutation
  • Continuations

Lecture 12 slides

Lecture 12 notes

 

Lecture 13 slides

Lecture 13 racket file

Exercise 5
Lab 5

"Why are they called shift and reset?"

"Why did Church choose the notation lambda?"

Week 7 (13 July)

  • Continuations (continued)
  • Backtracking
  • Type Systems
Lecture 14 slides
Lecture 15 slides

Exercise 6
Lab 6

Walkthrough of "compare and swap" from a hardware/concurrency perspective (begins at 21 minutes 30 seconds)
Week 8 (20 July)

  • Type systems
  • Parametric polymorphism
Lecture 16 slides
Lecture 17 slides

Exercise 7
Lab 7

 

Data constructors vs type constructors
Week 9 (27 July)

  • Typeclasses & ad-hoc polymorphism
Lecture 18 slides
Lecture 19 slides

Exercise 8

Qualified Types: Theory and Practice

Cheat Codes for Covariance and Contravariance

 

"How are typeclasses compiled?" (begins at 28m54s)

Week 10 (3 August)

  • Functors and Monads
  • Option, Either, and List as Monads

Lecture 20 slides

Lecture 20 Haskell file


Lecture 21 slides

No Lab 9 (Holiday Monday)

 

Assignment 2: Due by Friday, 7 August

The Functor Design Pattern
Week 11 (10 August)

  • The State monad
  • The IO Monad
Lecture 22 slides
Lecture 23 slides

Quiz 2: Take on Monday, 10 August

Exercise 9 (due Monday 17 August)

 

Assessment (17 August)

Lecture 24 slides Exercise 10

F-Bounded Polymorphism and Recursive Types

As this are due the last week of class, Exercise 10 will have a different due date than the usual "saturday before midnight" date.  See MarkUs for specifics.


Last updated on Sun Aug 16 12:58:17 2020.