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

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

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

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.

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

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.