The outline is available in the UWaterloo Outline Repository, and is duplicated here for convenience.

Principles of Programming Languages Winter 2023
CS 442 / CS 642

Published Jan 05, 2023

Class Schedule

Section Location Time Instructor(s)
CS 442 001 [LEC] MC 4020
Tuesdays & Thursdays
4 p.m. - 5:20 p.m.
Gregor Richards
CS 642 001 [LEC]
Tuesdays & Thursdays
4 p.m. - 5:20 p.m.
This table is generated automatically

Instructor / TA Information

Instructor: Gregor Richards

Office: DC3118

Office hours: Fridays 10–11AM, or by request

TAs:

Elshamy, Abdallah: akamelsh@uwaterloo.ca

Jin, Ende: e5jin@uwaterloo.ca

Oliveira, Pedro Jorge Magnan Cavalcante: pjmcoliv@uwaterloo.ca

Zila, Owen: ozila@uwaterloo.ca

Course Description

CS 442

An exposure to important concepts and issues in contemporary programming languages. Data types, abstraction, and polymorphism. Program structure. Lambda calculus and functional programming, logic programming, object-oriented programming. Semantics of programming languages. Critical comparison of language features and programming methodologies using examples drawn from a variety of programming languages including Lisp, Prolog, ML, Ada, Smalltalk, Icon, APL, and Lucid. Programming assignments involve the use of some of these languages.

Prereq: CS 240; Computer Science students only

CS 642

An exposure to important concepts and issues in contemporary programming languages. Data types, abstraction, and polymorphism. Program structure. Lambda calculus and functional programming, logic programming, object-oriented programming. Semantics of programming languages. Critical comparison of language features and programming methodologies using examples drawn from a variety of programming languages including Lisp, Prolog, ML, Ada, Smalltalk, Icon, APL, and Lucid. Programming assignments involve the use of some of these languages.

Lambda calculus

  • Grammar
  • Binding, scope, and substitution
  • Reduction strategies (eager vs. lazy evaluation)
  • Confluence and normalization
  • Simulating common programming language features (Booleans, natural numbers, lists, recursion)
  • Programming languages based on untyped lambda calculus (e.g., Lisp, Scheme, Racket)
  • Techniques for efficient interpreters (environments, closures, stores)

Formal semantics

  • Category theory and programming languages as calculi
  • Post system/Post rules
  • Formal semantics for Lambda calculus
  • Proofs with formal semantics
  • Small-step and big-step semantics
  • Operational and denotational semantics
  • Semantics of common programming language features (Booleans, natural numbers, lists)

Typed lambda calculus and statically-typed languages

  • Typing rules and type-checking algorithms
  • Recovering expressibility through extensions
  • Progress and preservation theorems
  • Type inference algorithms
  • Programming languages based on typed lambda calculus (e.g. SML, OCaml, Haskell)

Programming paradigms and exemplar languages

  • Functional languages and Haskell
  • Logic languages and Prolog
  • Imperative langauges and Pascal
  • Object Oriented languages and Smalltalk
  • Concurrent languages and Erlang
  • Systems languages and C/CompCert
  • Impacts of paradigm choice on formal semantics
  • Implementation techniques for different paradigms

 

Learning Outcomes

By the end of this course students should be able to:
Write efficient, readable programs from scratch in several new programming languages
Define and implement (via interpreters written in these new programming languages) operational semantics for extensions of the lambda calculus distilling features from said languages
Define typing rules for these extensions compatible with the type systems provided by said languages and implement type checking and type inference algorithms based on these rules
State and prove relevant theorems (e.g., progress, preservation) about type systems

Tentative Course Schedule

Week #DatesModule to readAssignments/exams
1Jan 9–Jan 151 
2Jan 16–Jan 222 
3Jan 23–Jan 293 
4Jan 30–Feb 54Feb 3:
Assignment 1
5Feb 6–Feb 125 (first half) 
6Feb 13–Feb 175 (second half)Feb 15:
Midterm exam
HH1101
7PM
Reading week
7Feb 27–Mar 56Mar 3:
Assignment 2
8Mar 6–Mar 127 (part)Mar 10:
Assignment 3
9Mar 13–Mar 197 (rest), 8 (part) 
10Mar 20–Mar 268 (rest)Mar 24:
Assignment 4
11Mar 27–Apr 29 
12Apr 3–Apr 1010THURSDAY Apr 6:
Assignment 5
Exam periodTBD:
Final exam

 

Texts / Materials

Title / Name Notes / Comments Required
Course notes https://student.cs.uwaterloo.ca/~cs442/W23/notes/ No

Course notes will be published as they are edited, well before they're needed.

Student Assessment

CS442
Component Value
Assignments 50% (10% each)
Midterm exam 20%
Final exam 30%
CS642
Component Value
Assignments 40% (8% each)
Midterm exam 16%
Final exam 24%
Final project 20%

Assignment submission is through UWaterloo submit. There is no automated grading. Late or missing assignments will be handled on a case-by-case basis, with the general rule being that they are worth 0%. Late submission or other accommodation is allowed in University-approved circumstances if the instructor is notified, such as medical issues with a verification of illness form, self-declared 48-hour absence, or AccessAbility Services requests.

Assignment Screening

MOSS (Measure of Software Similarities) is used in this course as a means of comparing students' assignments to ensure academic integrity. We will report suspicious activity, and penalties for plagiarism/cheating are severe. Please read the available information about academic integrity very carefully.

Administrative Policy

Territorial Acknowledgement: The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is centralized within the Office of Indigenous Relations

University Policy

Academic integrity: In order to maintain a culture of academic integrity, members of the University of Waterloo community are expected to promote honesty, trust, fairness, respect and responsibility. [Check the Office of Academic Integrity for more information.]

Grievance: A student who believes that a decision affecting some aspect of their university life has been unfair or unreasonable may have grounds for initiating a grievance. Read Policy 70, Student Petitions and Grievances, Section 4. When in doubt, please be certain to contact the department’s administrative assistant who will provide further assistance.

Discipline: A student is expected to know what constitutes academic integrity to avoid committing an academic offence, and to take responsibility for their actions. [Check the Office of Academic Integrity for more information.] A student who is unsure whether an action constitutes an offence, or who needs help in learning how to avoid offences (e.g., plagiarism, cheating) or about “rules” for group work/collaboration should seek guidance from the course instructor, academic advisor, or the undergraduate associate dean. For information on categories of offences and types of penalties, students should refer to Policy 71, Student Discipline. For typical penalties, check Guidelines for the Assessment of Penalties.

Appeals: A decision made or penalty imposed under Policy 70, Student Petitions and Grievances (other than a petition) or Policy 71, Student Discipline may be appealed if there is a ground. A student who believes they have a ground for an appeal should refer to Policy 72, Student Appeals.

Note for students with disabilities: AccessAbility Services, located in Needles Hall, Room 1401, collaborates with all academic departments to arrange appropriate accommodations for students with disabilities without compromising the academic integrity of the curriculum. If you require academic accommodations to lessen the impact of your disability, please register with AccessAbility Services at the beginning of each academic term.

Turnitin.com: Text matching software (Turnitin®) may be used to screen assignments in this course. Turnitin® is used to verify that all materials and sources in assignments are documented. Students' submissions are stored on a U.S. server, therefore students must be given an alternative (e.g., scaffolded assignment or annotated bibliography), if they are concerned about their privacy and/or security. Students will be given due notice, in the first week of the term and/or at the time assignment details are provided, about arrangements and alternatives for the use of Turnitin in this course.

It is the responsibility of the student to notify the instructor if they, in the first week of term or at the time assignment details are provided, wish to submit alternate assignment.