CSCI 7000 -- Advanced programming language techniques for incremental computation
Course Information
| Instructor: | Matthew A. Hammer | |
| Meetings: | ECCR 108 | |
| M,W,F 10:00-10:50 | ||
| Meeting Schedule | ||
| Office Hours: | TBA | |
| Slack channels: | Class Announcements (public channel) | |
| Student Discussion (private to class members) | ||
| Standard Syllabus Statements | ||
Description
This course introduces the fundamental principles of programming language design, semantics, and implementation of incremental computations. Incremental computations are those that run faster after small input changes that naive recomputation of the updated output.
To express incremental computations that are efficient and correct (or sound, meaning consistent with from-scratch evaluation), we will study designs that combine new algorithms and programming language abstractions.
To understand these algorithms and PL abstractions in practice, we will use Adapton in Rust.
Course topics
Algorithmic techniques for incremental computing:- Memoization (aka, pure function caching)
- Hash-consing
- Persistent data structures
- Merkle trees
- Dependence graphs, and change propagation:
- Program dependence graph (PDG)
- Data dependence graph (DDG)
- Demanded computation graph (DCG)
- Basic foundations (e.g., from CSCI 5535):
- Inductive data structures
- Inductive proofs (by structural induction, by rule induction)
- Functional programming
- Operational semantics
- Higher-order type systems with algebraic datatypes
- Imperative programming abstractions, types and operational semantics
- Sub-structural (linear and affine) type systems
- Refinement type systems, dependent type systems
- Modal type systems
Schedule: Readings and programming tasks
Please see the schedule of lectures for the lecture topics and links to the readings and assignments.
Course requirements
The primary sources of information, and the students' responsibilities for this course, consist of doing the following:
- attend all lectures and class meetings,
- attempt (ideally, complete) the reaadings and associated programming assignments,
- actively participate in class discussion (both online, and in class meetings), and
- complete a course project (to begin in the later part of the course)
Course Project
Roughly half-way through the course, students will begin to work in pairs (or independently, with permission from the professor) on a course project. This project will consist of a combination of implementation work, theoretical work, and a literature survey. The final meetings of the class will consist of project teams giving oral presentations about their project. Additionally, each project team is required to submit a written report. See the course project page for details about the scope of these projects, and the requirements for presentations and reports.Grading
Class participation (discussion about readings and programming tasks) will account for 50% of your grade, and the project the other 50%. Your final letter grade will be determined in part based on your performance relative to the rest of the class, though we have no pre-determined distribution in mind.
Late homework assignments will not be accepted or graded. They count for zero points. If you have a special circumstance that is truly beyond your control which prevents you from completeing your homework on time, contact the instructor before the homework due date to request a special accommodation. Requests made on or after the due date will be categorically ignored.
Text
Robert Harper, Practical Foundations for Programming Languages (Second Edition). Cambridge University Press, 2016.
This text is suggested as a general textbook for programming languages. It is not required to complete this seminar course on incremental computation, but may be helpful for general background material on programming languages. The author has made a preview version available online.
Software
The programming languages we study and use in this course will be closely related to ML. Specifically, we will use the Rust implementation for homeworks that involve programming assignments.
Academic Integrity
As a condition for taking this course, you are responsible for compliance with the University Policy on Academic Integrity and Plagiarism.
In this course, you are authorized to use the books and notes linked from this Web site, as well as any other sources specifically allowed by the course staff. Any other source is unauthorized.
You are allowed to discuss homework assignments with other students. However, in order to ensure that the work you submit is still your own, we insist that you adhere to a whiteboard policy regarding these discussions: you are not allowed to take any notes, files, or other records away from the discussion. For example, you may work on the homework at the whiteboard with another student, but then you must erase the whiteboard, go home, and write up your solution individually. We take your ability to recreate the solution independently as proof that you understand the work that you submit.
This policy is our attempt to balance the tension between the benefits of group work and the benefits of individual work. We ask that you obey the spirit of the policy, as well as the letter: ensure that all work you submit is your own and that you fully understand the solution. This is in your best interest: the exam constitutes a significant part of your final grade and it will draw heavily on the terminology, concepts, and techniques that are exercised in in the homework. It is unlikely that you will be able to do well on the exam if you do not take full advantage of the learning opportunity afforded by the homework assignments.