[UVM CS 225: Programming Languages / Spring 2020](#title)

### Course Description

What does it mean for a C++ program to be “undefined”? What is the difference
between “proc” and “lambda” in Ruby? What is the difference between “function”
in Javascript and “lambda” in Python? What does “yield” do in the various
programming languages that support it? What is the difference between a
“variable”, a “pointer” and a “reference”? What's the difference between a
Javascript “prototype”, a Java “class”, and a Rust “trait”? If I wanted to
automatically translate python to javascript, and in a way that preserves the
original program's meaning, (1) how would I do it, and (2) how would I know I
did it correctly?

This course will explore topics in programming language design, implementation
and analysis. We will examine existing programming language designs, as well as
give a rigorous mathematical account for core subsets of programming language
features. Finally, we will use this mathematical account of programming
language semantics as a foundation for tools which analyze programs to (a) find
bugs in programs, (b) verify correctness and security properties of programs,
and (c) automatically construct programs which adhere to a specification.

This course is structured around *programming language interpreters* as an
avenue for exploring language features and mathematical properties of programs.
We will not study any single mainstream programming language, rather we will
focus on smaller core languages in order to focus on the essence of language
features in isolation. After studying language features through interpreters,
we will relate these features back to mainstream programming languages and
discuss their designs.

Students are expected to implement concepts discussed in the course in the
Haskell programming language, and manipulate mathematical definitions of
programming language semantics on paper. Students will be evaluated through
weekly programming assignments, a midterm exam and a final project. There will
be no final exam.

**Prerequisites:** CS 124 (Data Structures and Algorithms) and CS 125
(Computability and Complexity)

### Administration

**Lecture:** Tuesdays and Thursdays, 1:15–2:30pm, Aiken Center 102  
**Instructor:** [David Darais](http://david.darais.com)  
**TAs:** June Wunder, Walter the Doggo  
**Office Hours:**

- David: Wednesdays, 4-5pm, Innovation E456
- June: Mondays, 1-2pm, Innovation 4th floor

**Course [Piazza]**  
**Course [Gradescope]**

[Piazza]: https://piazza.com/class#spring2020/cs225
[Gradescope]: https://www.gradescope.com/courses/82117

Course announcements and discussion will take place on Piazza exclusively.
Homework-related questions sent to the instructor or TAs via email will receive
the following reply: “Please post this question to Piazza.” The instructor and
TAs are not required to respond to Piazza questions after 5pm, or any earlier
than 24 hours after the question is posted.

### Textbook

This course is loosely based on Shriram Krishnamurthi's [Programming Languages:
Application and Interpretation][PLAI], which is freely available online. The
book uses Racket for programming examples and exercises, wherease we will be
using Haskell. We also skip some topics, and expand on others. 

[PLAI]: http://cs.brown.edu/courses/cs173/2012/book/

### Software Tools

Throughout the course we will use the [Haskell] programming language. See
[Haskell Setup] for instructions on setting up Haskell. We will use Haskell GHC
version 8.6.5 for this course, along with the [Stack] tool for managing Haskell
compiler and package installations.

You may find [Hoogle] useful for looking up documentation of Haskell operators
and functions.

[Haskell]: https://haskell-lang.org
[Haskell Setup]: haskell-setup.html
[Stack]: https://haskellstack.org
[Hoogle]: https://www.haskell.org/hoogle/

### Policies

**Grades:** Your grade for the course will be calculated as follows: 60%
Assignments, 20% midterm and 20% final project. *I will drop your lowest
assignment grade.* This means that out of the 10 assignments, your best 9 will
be used to calculated 60% of your grade, so each assignment is worth 6.66% of
your total grade. Letter grades are calculated in the [usual
way][LetterGrades]. A+ will be given to students who achieve 97–100% as their
final grade *and* an outstanding final project.

[LetterGrades]: letter-grades.html

**Assignments:** There will be 10 weekly assignments. Each assignment is
released on a Tuesday after class and due the following Tuesday *before
class*. Your lowest assignment grade will be dropped when calculating final

**Quizes:** There will be in-class quizes that will not have any impact on your
grade, but will be used to prepare you for the midterm exam.

**Late Work:** Each assignment will be released after class on a Tuesday and
due before class one week later. *Late work will not be accepted.* The purpose
of my policy to drop your lowest homework grade (see above) is to accommodate
situations that interfere with turning in assignments on time: e.g., illness,
travel, extracurricular activities, or other coursework. Please use this “free”
assignment carefully, and only for situations that are truly outside your
control. Extensions will not be granted for any homework deadline.

**Extra Credit:** During the semester there will be ~8 guest lectures from
visiting faculty. *I will give 0.25% extra credit towards your final grade for
each of these lectures that you attend.* To receive extra credit, you must
bring a notepad to the lecture, take notes in person during the lecture, and
then turn your notes in to the instructor or TA personally at the end of the
talk. If you attend 8 lectures you will receive a 2.0% bump to your final

**Graduate Credit:** Graduate students taking this course for graduate credit
will be expected to complete a more substantial final project than those taking
the course for undergraduate credit.

**Collaboration:** Collaboration on the high-level ideas and approach on
assignments is encouraged. Copying someone else's work is not allowed. Copying
solutions from an online source is not allowed. Any collaboration or online
resources, even if used only at a high level, must be declared when you submit
your assignment. Every assignment must include a collaboration and resources
statement. E.g., “I discussed high-level strategies for solving problem 2 and 5
with Alex; I found this stackoverflow post helpful while working on problem 3
” Students caught copying work are eligible for immediate failure of the
course and disciplinary action by the University. All academic integrity
misconduct will be treated according to [UVM's Code of Academic

[UVM-CAI]: https://www.uvm.edu/policies/student/acadintegrity.pdf

**Small Group Assignments:** For homeworks 6–10 you will be allowed to work in
groups of size 1–2 (independently or in pairs). You may submit a single
solution to the assignment for 2-person groups.

**Midterm:** The midterm will be closed note, closed book and closed laptop.

**Final Group Project:** For the final project, you will be allowed to work in
groups of size 1–2, however I will expect a larger amount of work to be
completed for groups of 2. For the final project you will do the following, all
of which will be graded:

- Submit a project proposal
- Submit a project checkpoint each class day for three consecutive classes
- Present your project during the last week of classes
- Submit your final project on the last Friday of classes

### Homework Due Dates

| HW        | Release Date | Soft Deadline        | Hard Deadline        | Group Size? | Required?         |
| --------- | ------------ | -------------------- | -------------------- | ----------- | ----------------- |
| **HW06:** | Thu, Mar 19  | Thu, Mar 26, 11:59pm | Thu, Apr 02, 11:59pm | 1–2         | YES               |
| **HW07:** | Thu, Mar 26  | Thu, Apr 02, 11:59pm | Thu, Apr 09, 11:59pm | 1–2         | YES               |
| **HW08:** | Thu, Apr 09  | Thu, Apr 16, 11:59pm | Thu, Apr 23, 11:59pm | 1–2         | YES               |
| **HW09:** | Tue, Apr 14  | Tue, Apr 21, 11:59pm | Tue, Apr 28, 11:59pm | 1–2         | NO (extra credit) |

### Final Project Due Dates

| Project          | Soft Deadline | Hard Deadline           |
| ---------------- | ------------- | ----------------------- |
| Proposal         | Tue, April 21 | Thu, April 23           |
| Checkpoint 1     | Thu, Apr 23   | Fri, April 24           |
| Checkpoint 2     | Tue, Apr 28   | (same as Soft Deadline) |
| Checkpoint 3     | Thu, Apr 30   | (same as Soft Deadline) |
| Final Submission | Fri, May 01   | Fri, May 08             |

### Schedule

| Date        | Topic                                      | Homework                                    |
| ----------- | -----------------------------------------  | ------------------------------------------- |
| Tue, Jan 14 | Welcome [[LN01]]                           |                                             |
| Thu, Jan 16 | Technical Introduction [[LN02]]            |                                             |
| Tue, Jan 21 | Haskell Basics I [[LN03]]                  | HW01 Release [[HW01]] [[SL01]]              |
| Thu, Jan 23 | Haskell Basics II                          |                                             |
| Tue, Jan 28 | Trees 3 Ways [[LN05]]                      | HW01 Due ⌁ HW02 Release [[HW02]] [[SL02]]   |
| Thu, Jan 30 | Syntax, Interpretation ⅋ Sugar [[LN06]]    |                                             |
| Tue, Feb 04 | Partiality ⅋ Sets [[LN07]]                 | HW02 Due ⌁ HW03 Release [[HW03]] [[SL03]]   |
| Thu, Feb 06 | Binding and Scope [[LN08]]                 |                                             |
| Tue, Feb 11 | *NO CLASS*                                 | HW03 Due ⌁ HW04 Release [[HW04]] [[SL04]]   |
| Thu, Feb 13 | Environments [[LN09]]                      |                                             |
| Tue, Feb 18 | Substitution and Functions [[LN10]]        | HW04 Due ⌁ HW05 Release [[HW05]] [[SL05]]   |
| Thu, Feb 20 | Implementing Functions [[LN11]]            |                                             |
| Tue, Feb 25 | Higher Order Functions I [[LN12]]          | HW05 Due                                    |
| Thu, Feb 27 | **REVIEW FOR MIDTERM**                     |                                             |
| Tue, Mar 03 | *NO CLASS: Town Meeting Day*               |                                             |
| Thu, Mar 05 | **MIDTERM**                                |                                             |
| Tue, Mar 10 | *NO CLASS: Spring Recess*                  |                                             |
| Thu, Mar 12 | *NO CLASS: Spring Recess*                  |                                             |
| Tue, Mar 17 | *NO CLASS: Canceled*                       |                                             |
| Thu, Mar 19 | Higher Order Functions II [[LN13]] [[V13]] | HW06 Release [[HW06]] [[SL06]]              |
| Tue, Mar 24 | Mutation I [[LN14]] [[V14]]                |                                             |
| Thu, Mar 26 | Mutation II  [[LN15]] [[V15]]              | HW06 Due ⌁ HW07 Release [[HW07]] [[SL07]]   |
| Tue, Mar 31 | Objects I [[LN16]] [[V16]]                 |                                             |
| Thu, Apr 02 | Objects II [[LN17]] [[V17]]                | HW07 Due                                    |
| Tue, Apr 07 | Program Analysis I [[LN18]] [[V18]]        |                                             |
| Thu, Apr 09 | Program Analysis II [[LN19]] [[V19]]       | HW08 Release [[HW08]]                       |
| Tue, Apr 14 | Final Project Options [[LN20]] [[V20]]     | HW09 (optional) Release [[HW09]]            |
| Thu, Apr 16 | Type Systems [[LN21]] [[V21]]              | HW08 Due                                    |
| Tue, Apr 21 | Big-step and Small-step                    | HW09 (optional) Due ⌁ Project Proposals Due |
| Thu, Apr 23 | Core λ-calculus                            | Project Checkpoint 1 Due                    |
| Tue, Apr 28 | Monads                                     | Project Checkpoint 2 Due                    |
| Thu, Apr 30 | Project Presentations                      | Project Checkpoint 3 Due                    |
| Fri, May 01 | *NO CLASS*                                 | Project Due Soft Deadline (at 11:59pm)      |
| Fri, May 08 | *NO CLASS*                                 | Project Due Hard Deadline (at 11:59pm)      |

[LN01]: ln/ln01.html
[LN02]: ln/ln02.html
[LN03]: ln/ln03.html
[LN04]: ln/ln04.html
[LN05]: ln/ln05.html
[LN06]: ln/ln06.html
[LN07]: ln/ln07.html
[LN08]: ln/ln08.html
[LN09]: ln/ln09.html
[LN10]: ln/ln10.html
[LN11]: ln/ln11.html
[LN12]: ln/ln12.html
[LN13]: ln/ln13.html
[LN14]: ln/ln14.html
[LN15]: ln/ln15.html
[LN16]: ln/ln16.html
[LN17]: ln/ln17.html
[LN18]: ln/ln18.html
[LN19]: ln/ln19.html
[LN20]: ln/ln20.html
[LN21]: ln/ln21.html
[LN22]: ln/ln22.html
[LN23]: ln/ln23.html
[LN24]: ln/ln24.html
[LN25]: ln/ln25.html
[LN26]: ln/ln26.html
[LN27]: ln/ln27.html
[LN28]: ln/ln28.html
[LN29]: ln/ln29.html
[LN30]: ln/ln30.html

[LC01]: lc/Lc01.hs
[LC02]: lc/Lc02.hs
[LC03]: lc/Lc03.hs
[LC04]: lc/Lc04.hs
[LC05]: lc/Lc05.hs
[LC06]: lc/Lc06.hs
[LC07]: lc/Lc07.hs
[LC08]: lc/Lc08.hs
[LC09]: lc/Lc09.hs
[LC10]: lc/Lc10.hs
[LC11]: lc/Lc11.hs
[LC12]: lc/Lc12.hs
[LC13]: lc/Lc13.hs
[LC14]: lc/Lc14.hs
[LC15]: lc/Lc15.hs
[LC16]: lc/Lc16.hs
[LC17]: lc/Lc17.hs
[LC18]: lc/Lc18.hs
[LC19]: lc/Lc19.hs
[LC20]: lc/Lc20.hs
[LC21]: lc/Lc21.hs
[LC22]: lc/Lc22.hs
[LC23]: lc/Lc23.hs
[LC24]: lc/Lc24.hs
[LC25]: lc/Lc25.hs
[LC26]: lc/Lc26.hs
[LC27]: lc/Lc27.hs
[LC28]: lc/Lc28.hs
[LC29]: lc/Lc29.hs
[LC30]: lc/Lc30.hs

[HW01]: hw/src/src/HW01.html
[HW02]: hw/src/src/HW02.html
[HW03]: hw/src/src/HW03.html
[HW04]: hw/src/src/HW04.html
[HW05]: hw/src/src/HW05.html
[HW06]: hw/src/src/HW06.html
[HW07]: hw/src/src/HW07.html
[HW08]: hw/src/src/HW08.html
[HW09]: hw/src/src/HW09.html
[HW10]: hw/src/src/HW10.html

[SL01]: hw/src/Solutions/src/Solutions.SL01.html
[SL02]: hw/src/Solutions/src/Solutions.SL02.html
[SL03]: hw/src/Solutions/src/Solutions.SL03.html
[SL04]: hw/src/Solutions/src/Solutions.SL04.html
[SL05]: hw/src/Solutions/src/Solutions.SL05.html
[SL06]: hw/src/Solutions/src/Solutions.SL06.html
[SL07]: hw/src/Solutions/src/Solutions.SL07.html
[SL08]: hw/src/Solutions/src/Solutions.SL08.html
[SL09]: hw/src/Solutions/src/Solutions.SL09.html
[SL10]: hw/src/Solutions/src/Solutions.SL10.html

[V13]: https://youtu.be/IrGOTXe4wls
[V14]: https://youtu.be/zPiWPJBYiB8
[V15]: https://youtu.be/L8LYYRvfTdg
[V16]: https://youtu.be/4udi_KmG9iw
[V17]: https://youtu.be/u1XjNE_obGk
[V18]: https://youtu.be/JvbLUpKGR7I
[V19]: https://youtu.be/xpye3ArWj74
[V20]: https://youtu.be/xOCfSNY8v34
[V21]: https://youtu.be/C0OkWqmkiGU