[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 grades. **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 grade. **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 Integrity][UVM-CAI]. [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