[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

### Schedule

Date        | Topic                                                                 | Homework                       
Tue, Jan 14 | Welcome [[LN01]]                                                      |
Thu, Jan 16 | Technical Introduction [[LN02]]                                       |
Tue, Jan 21 | Haskell Basics I [[LN03]]                                             | HW 01 Release [[HW01]]
Thu, Jan 23 | Haskell Basics II                                                     |
Tue, Jan 28 | Trees 3 Ways [[LN05]]                                                 | HW 01 Due ⌁ HW 02 Release [[HW02]] 
Thu, Jan 30 | Syntax ⅋ Interpretation                                               |
Tue, Feb 04 | Lists, Trees, Sets ⅋ Variables                                        | HW 02 Due ⌁ HW 03 Release 
Thu, Feb 06 | Binding and Scope                                                     |
Tue, Feb 11 | Substitution                                                          | HW 03 Due ⌁ HW 04 Release 
Thu, Feb 13 | Functions ⅋ Environments                                              |
Tue, Feb 18 | First-class Functions                                                 | HW 04 Due ⌁ HW 05 Release 
Thu, Feb 20 | Higher Order Haskell                                                  |
Tue, Feb 25 | Mutation                                                              | HW 05 Due ⌁ HW 06 Release 
Thu, Feb 27 | **REVIEW FOR MIDTERM**                                                |
Tue, Mar 03 | *NO CLASS: Town Meeting Day*                                          | HW 06 Due
Thu, Mar 05 | **MIDTERM**                                                           |       
Tue, Mar 10 | *NO CLASS: Spring Recess*                                             |
Thu, Mar 12 | *NO CLASS: Spring Recess*                                             |
Tue, Mar 17 | Self Reference ⅋ Core OO                                              | HW 07 Release 
Thu, Mar 19 | Objects                                                               |
Tue, Mar 24 | Inheritance                                                           | HW 07 Due ⌁ HW 08 Release 
Thu, Mar 26 | Types I                                                               |
Tue, Mar 31 | Types II                                                              | HW 08 Due ⌁ HW 09 Release 
Thu, Apr 02 | Program Analysis I                                                    |
Tue, Apr 07 | Program Analysis II                                                   | HW 09 Due ⌁ HW 10 Release 
Thu, Apr 09 | Final Project Options I                                               |
Tue, Apr 14 | Final Project Options II                                              | HW 10 Due
Thu, Apr 16 | Big-step ⅋ Small-step                                                 | Project Proposals Due (9pm)
Tue, Apr 21 | Monads                                                                | Project Checkpoint 1 Due (before class)
Thu, Apr 23 | Software Verification                                                 | Project Checkpoint 2 Due (before class)
Tue, Apr 28 | Project Presentations I                                               | Project Checkpoint 3 Due (before class)
Thu, May 30 | Project Presentations II                                              |
Fri, May 01 | *NO CLASS*                                                            | Project Due (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]: sl/Sl01.hs
[SL02]: sl/Sl02.hs
[SL03]: sl/Sl03.hs
[SL04]: sl/Sl04.hs
[SL05]: sl/Sl05.hs
[SL06]: sl/Sl06.hs
[SL07]: sl/Sl07.hs
[SL08]: sl/Sl08.hs
[SL09]: sl/Sl09.hs
[SL10]: sl/Sl10.hs