Welcome to the Summer 2020 offering of CSC324.
This website is under construction!
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.
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.
Topics | Materials | Coursework | Other materials |
---|---|---|---|
Week 1 (6 May)
|
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)
|
Lecture 2 slides |
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
|
Exercise 2 Lab 2 |
Data constructors as first class values |
|
Week 3 (27 May)
|
Lecture 6 slides |
Exercise 3 Lab 3 |
|
Week 4 (3 June)
|
Exercise 4 Lab 4 |
||
Week 5 (10 June)
|
Lecture 10 racket file
|
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)
|
|
||
Week 7 (13 July)
|
Lecture 14 slides Lecture 15 slides |
Walkthrough of "compare and swap" from a hardware/concurrency perspective (begins at 21 minutes 30 seconds) | |
Week 8 (20 July)
|
Lecture 16 slides Lecture 17 slides |
|
Data constructors vs type constructors |
Week 9 (27 July)
|
Lecture 18 slides Lecture 19 slides |
Qualified Types: Theory and Practice Cheat Codes for Covariance and Contravariance
"How are typeclasses compiled?" (begins at 28m54s) |
|
Week 10 (3 August)
|
No Lab 9 (Holiday Monday)
|
The Functor Design Pattern | |
Week 11 (10 August)
|
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. |