CS440: Programming Languages and Translators, Spring 2023

Instructor: Stefan Muller,
Office Hours:

Monday: 11am-12pm (Zoom; see Blackboard for link)

Thursday: 3:30-4:30pm (SB 218E)

TA: Xincheng Yang,
Office Hours:

Tuesday: 1-3pm (Online; by appointment: https://calendly.com/xyang76)

Wednesday: 2-4pm (SB 004)


Lectures:

Section 01: Tue, Thur 10:00-11:15 AM, SB 104
Section 02: Online only - see Attendance


Schedule     Assignments     Resources     Policies


Schedule

Note: this schedule is tentative and subject to change.

For the readings posted:
"PDB" = "Purple Dragon Book" (Aho et al.)
"OCP" = "OCaml Programming" (linked below)
"TAPL" = Types and Programming Languages (Pierce)
"PFPL" = Practical Foundations for Programming Languages (Harper)

Topic Readings Notes
January 10 Intro Languages and course overview Slides
12 Compiler structure, interpreters, OCaml Slides HW0 Out
17 OCaml OCaml evaluation, types, expressions OCP 1-2.3 Code
19 Functions and recursion OCP 2.4 Code
24 More on types OCP 3.3-3.4 Code
26 Options and Lists OCP 3.1, 3.7 Code HW0 Due, HW1 Out
31 Tail recursion, records and algebraic data types OCP 3.1.9, 3.2, 3.4, 3.9 Code
February 2 ADTs, Higher-order functions OCP 4.1-4.6 Code
7 Higher-order functions Code
9 OCaml wrap-up Code HW1 Due
14 Interpreters Building an interpreter Slides AST Code
16 Closures (Updated) Slides
21 Refs and More Closures Code
23 Recap on interpreters Slides
28 Types Type checking overview Slides
March 2 Midterm exam
7 Unification Notes
9 Type checking Slides   Code
14 No class - spring break
16 No class - spring break
21 Semantics Big-step semantics TAPL 3.1-3.4; PFPL 2, 7.1 Notes
23 Big-step semantics TAPL 3.1-3.4; PFPL 2, 7.1 Notes HW3 Due
28 No class
30 Lambda calculus TAPL 5; PFPL 21 Notes
April 4 Lambda calculus TAPL 5; PFPL 21 Notes HW4 Due
6 Types Simply-typed lambda calculus TAPL 9.1-9.2; PFPL 8.1 Notes
11 Type safety and pairs TAPL 8; PFPL 6.1-6.2 Notes
13 Misc. Continuation passing style Code HW5 Due
18 Continuation passing style Code
20 Applications of continuations Code
25 Verification and Hoare logic Notes
27 Wrap-up Slides HW6 Due

Assignments

#TopicDueAssignment Link
0Setting up OCaml Jan. 26, 11:59pm https://classroom.github.com/a/t4GMsXj1
1Lists and Recursion Feb. 9, 11:59pm https://classroom.github.com/a/QwbpxOO7
2ADTs and HOFs Feb. 23, 11:59pm https://classroom.github.com/a/DhrCRTyG
3MiniML Interpreter Mar. 23, 11:59pm https://classroom.github.com/a/pH52xZg4
4MiniML Type checker Apr. 4, 11:59pm https://classroom.github.com/a/pH52xZg4
5Semantics and Lambda Calculus Apr. 13, 11:59pm N/A - Submit on BB
6Type Systems and CPS Apr. 27, 11:59pm Submit on BB - Code handout

Resources

Textbooks: There are no required textbooks for the class, but the following may be helpful as references or if you want to go deeper into any of the material.

Compilers: Principles, Techniques, & Tools, 2nd ed., Alfred V. Aho et al.,2006.

Crafting Interpreters, Robert Nystrom, 2021.

OCaml Programming: Correct + Efficient + Beautiful, Fall 2022 edition. (Creative Commons License)

Types and Programming Languages, Benjamin Pierce, 2002.

Practical Foundations for Programming Languages, Second Edition, Robert Harper, 2016. Preprint available online.

Discord:

We will use the #cs440 channel on Discord for discussions, Q&A, and announcements. An invitation link will be provided if you're not already on the CS Discord server. Please make sure to join and check the channel regularly as some important announcements will only appear there.

Other Resources:

Official OCaml site

OCaml Standard Library Reference

OCaml Playground (helpful for trying out small bits of OCaml code in a web interface, but not a substitute for compiling programs)

Similar to above, with same caveat: TryOCaml: try.ocamlpro.com

OCaml Static Semantics Cheat Sheet

Cornell CS3110's OCaml Style Guide

Learn the Basics of Git in Under 10 Minutes

Policies

Attendance

The 01 section of the course is live, in-person. Attendance and participation won't be recorded or explicitly graded, but if a student is at a grade boundary at the end of the semester, I'll be more inclined to give the benefit of the doubt to students who have shown they understand the material and have put effort into the class through asking/answering questions, etc. Attending lectures and participating is one way to do that.

The 02 section is virtual. Section 02 students will complete the same assignments and exams, but not attend lectures in person (lecture videos will be available on Blackboard shortly after each lecture). Due to space restrictions in the lecture hall, online students should not attend lecture in person without checking with the instructor.

Grading

Final grades will be based on the following:

50%Homeworks (~6, may not be evenly weighted)
20%Midterm Exam
30%Final Exam

Final letter grades will be calculated as follows:

>=90A
80-90B
70-80C
60-70D
<60E

That said, my main grading policy is fairness: asking for a higher grade (without pointing to specific things that have been graded incorrectly) won't succeed, because that wouldn't be fair to the rest of the students.

Late Days/Late Work

Each student has 6 "late days" to use on homeworks over the course of the semester. Using a late day extends the deadline by 24 hours. You do not need to let us know you're using late days; they'll be deducted automatically when you hand in the work.

Important: No more than two late days may be used on any one assignment. Late days may not be used on exams.

If you have used up your late days, work will be accepted up to 48 hours late with a 10% penalty per day.

No work will be accepted more than 48 hours after the deadline (except in exceptional circumstances like medical emergencies, which should be brought to the instructor's attention as soon as possible).

Collaboration and Using Outside Sources

Discussing general course concepts with other students to get a better understanding is permitted (and encouraged!). More specific discussions about homework questions is permitted as long as:

  • Discussion is two-way: it's not just one person giving the other help.
  • Discussion is at the level of concepts and general strategies (e.g., an approach to solving a problem); no specific answers or code are shared.
  • All students involved write up their solutions/code independently.

When working on homeworks, you may use the course notes and videos as well as any other resources provided by the course staff or on this web page. You may also use other resources to get more understanding of course content, but may not look up solutions to specific problems.

In general, you should not use any code from outside sources. If you really think you need to use outside code for a small, common task, run it by the instructor or TA first. In any case (even when using code from lecture or class resources), include a comment near the relevant code with where it came from (just like you'd cite a quote if you were writing a paper). We are checking code for similarity to other submissions as well as code from other sources, and these citations will help sort out any issues that might arise.

For each homework, you must list any collaborators as well as any outside resources you used (no need to mention course textbooks, notes or other resources provided by course staff, or discussions with the course staff). When citing outside sources (both in code citations and in your listing on each homework), be as specific as possible and give URLs (e.g., don't just say "I googled alpha-equivalence", but actually list the website(s) you looked at).

If you're ever in doubt about whether something would violate the policy, don't hesitate to contact the instructor or TA. It's always better to ask and be sure.

Illinois Tech's Sexual Harassment and Discrimination Information

Illinois Tech prohibits all sexual harassment, sexual misconduct, and gender discrimination by any member of our community. This includes harassment among students, staff, or faculty. Sexual harassment of a student by a faculty member or sexual harassment of an employee by a supervisor is particularly serious. Such conduct may easily create an intimidating, hostile, or offensive environment.

Illinois Tech encourages anyone experiencing sexual harassment or sexual misconduct to speak with the Office of Title IX Compliance for information on support options and the resolution process.

You can report sexual harassment electronically at iit.edu/incidentreport, which may be completed anonymously. You may additionally report by contacting the Title IX Coordinator, Virginia Foster at foster@iit.edu or the Deputy Title IX Coordinator at eespeland@iit.edu.

For confidential support, you may reach Illinois Tech's Confidential Advisor at (773) 907-1062. You can also contact a licensed practitioner in Illinois Tech's Student Health and Wellness Center at student.health@iit.edu or (312)567-7550.

For a comprehensive list of resources regarding counseling services, medical assistance, legal assistance and visa and immigration services, you can visit the Office of Title IX Compliance website at https://www.iit.edu/title-ix/resources.