Watch this space for the latest updates.
The class mailing list is compsci701-1-s20@lists.wisc.edu. An archive of mail sent to the class can be found here.
Last updated: Sun Apr 5 23:53:13 CDT 2020
Meeting Times and Location
Mondays, Wednesdays, and Fridays, 11:00 AM - 12:15 PM, on the days indicated in the
course schedule, in 1257 CS.
Credits
3
How the Course Meets the Credit-Hour-Policy Standards
Modified ``3-Credit Course, Option B'':
The classroom is reserved for three 75-minute class periods each week over the
spring semester;
however, on average we will meet for two 75-minute class periods per week.
Until late March, we will front-load the classes and meet for three 75-minute class periods most weeks,
after which there will be no classes, and you will have about five uninterrupted weeks to work on a project
of your own choosing.
In the final week of the term, we will hold enough classes for each project-group to make
a short presentation about the work they carried out.
See the course schedule for the dates on which
classes will be held.
The class carries the expectation that students will work on course learning activities (reading, writing, problem sets, projects, etc) for about 3 hours out of the classroom for every class period.
More information about the expectations for student work can be found elsewhere on this page.
Instructional Mode
Lecture by the instructor, and at the end of the term, a short project presentation by each project-group.
Instructor
Professor Thomas Reps
Office: 6361 Computer Sciences
Office hours: By appointment
Phone: 262-2091
E-mail: reps at cs.wisc.edu
Home page: www.cs.wisc.edu/~reps/
Textbook and Notes
There is no required textbook for the course.
Much of the reading material for the course is available on-line;
see the course bibliography.
Over the semester, we will accumulate a set of on-line notes in this directory. The notes (will) cover the following topics:
So that you have an idea of the scope of an appropriate project, here are the abstracts of the presentations from the Fall 2015 version of the course: Fall 2015 abstracts.
To help keep you on track, I will impose five deadlines:
I will be looking for a few volunteers to prepare LaTeX notes for one
or more of the term's classes -- more about this topic later in the
semester.
Students who do such a task may receive extra credit.
Policy on Collaborative Work
A certain amount of discussion of problem sets and programming
problems is permitted.
You should not ``go to someone'' simply to get an answer;
the kind of collaboration intended is a discussion with someone else
in which you discover the answer jointly.
You are not to make a habit of it over the course of the semester.
(Points will be deducted if you do an excessive amount
of the course work in collaboration with other people.)
When you do work in collaboration with someone else, make a note of it on the solution set or program you turn in. In all cases, you are to do your own write-up. For the programming assignments, you are to do your own programming; sharing of code is not permitted.
For the end-of-course project, you are encouraged to work in groups of two.
It is useful for students to have completed an undergraduate compiler course, such as Wisconsin's CS 536; however, that course is not mandatory for CS 701.
CS 701 is a graduate course on compilation (broadly defined). Topics to be covered include partial evaluation, static program analysis, compiling for profiling, compiling for data mining and machine learning, and machine learning for compiling.
We will begin by studying static analysis, which provides a way to obtain information about the possible states that a program reaches during execution, but without actually running the program on specific inputs. Instead, static-analysis techniques explore a program's behavior for all possible inputs and all possible states that the program can reach. To make this feasible, the program is "run in the aggregate"---i.e., on descriptors that represent collections of many states. In particular, we will cover several varieties of interprocedural dataflow analysis.
What we learn about static-analysis methods will serve as a way to understand the back-propagation algorithm used in machine learning. Compiling for machine learning will be our second topic.
A third topic is partial evaluation. Partial evaluation involves evaluating a program when only part of the program's input has been supplied. A partial evaluator operates on a program p that takes a pair of inputs, s (for ``static'', or ``supplied'') and d (for ``dynamic'', or ``delayed''), of which only s is known at partial-evaluation time. Partial evaluation of p with respect to s produces a residual program ps with the property that ps applied to d produces the same answer as that obtained when p is applied to s and d together. Partial evaluation provides insight into such topics as translation, optimization, and run-time code generation.
One of the important issues one faces when trying to get a software system to perform as desired is to understand what it is actually doing. Thus, a fourth topic is compiling for profiling.
The remaining topics have the common feature of involving a search in a huge search space of possible results: superoptimization, program synthesis, and auto-tuning.
Note: we are not interested in flaws in presentation, such as trivial examples, confusing notation, or spelling errors. However, if you have a great idea on how some concept could be presented or formalized better, mention it.
What follows is a tentative schedule of topics:
DATES TOPIC READINGS
===========================================================================
1/22 Synopsis of CS536 (AST-based) compiler
project; course mechanics
1/24 From ASTs to CFGs
Uses for static-analysis information PPT
Static program analysis Lecture Notes
----------------------------------------------------------------------------
1/27 Brief intro to abstract interpretation
1/29 Static analysis as a path problem Lecture Notes
1/31 Intraprocedural dataflow analysis PPT
----------------------------------------------------------------------------
2/3 Collecting semantics as a path problem Lecture Notes
2/5 Abstract semantics as a path problem Lecture Notes
2/7 Automatic differentiation Lecture Notes
and back-propagation [Olah 2015]
----------------------------------------------------------------------------
2/10 Functional approach to intraprocedural
dataflow analysis
2/12 Interprocedural dataflow analysis Lecture Notes
[Sharir & Pnueli 81]
2/14 No class
----------------------------------------------------------------------------
2/17 No class
2/19 Interprocedural dataflow analysis Lecture Notes
[RHS 1995]
2/19 Problem Set 1 assigned
2/21 Program analysis via CFL-reachability [Reps 1998]
PLDI00 Tutorial Slides
Abstract interpretation and logic [RSY 2004]
----------------------------------------------------------------------------
2/24 Newtonian program analysis Lecture Notes
PPT
[RTP16],[RTP17]
2/26 Ball-Larus & Melski-Reps path profiling [BL 1996] and [MR 1999]
(Ancient) PowerPoint Slides for [MR 1999]
2/28 Whole program paths [Larus 1999]
Lecture Notes
2/28 Problem Set 1 due (5:15 PM, in the box outside 6361 CS)
----------------------------------------------------------------------------
3/2 Dataflow frequency analysis [SM 2002]
based on whole program paths Lecture Notes
3/4 Finish dataflow frequency analysis [SM 2002]
based on whole program paths Lecture Notes
3/6 Probabilistic calling context [BM 2007]
Efficient call-trace collection [WXCZZ 2016], PPT
Lecture Notes
----------------------------------------------------------------------------
3/9 Bottom-up rewrite systems (BURS) [FHP 1992], [AGT 1989]
3/9 Problem Set 2 assigned
3/11 Tree Transducers
3/13 Finish Bottom-up rewrite systems (BURS) Lecture Notes
----------------------------------------------------------------------------
3/14-22 Spring Recess
----------------------------------------------------------------------------
3/23 Intro to partial evaluation and [Jones et al. 93], Chapter 1
Futamura projections Notes on partial evaluation (Part 1)
Notes on partial evaluation (Part 2)
Hand-written notes from on-line lecture, Part 1
Partial-evaluation problems
3/24 Problem Set 2 due (5:15 PM, as a PDF file, by e-mail to reps at cs.wisc.edu)
3/25 Partial evaluation [Jones et al. 93], Section 3.3.3 and Chapter 4
Notes on partial evaluation (Part 2)
Hand-written notes from on-line lecture, Part 2
3/27 Partial evaluation Hand-written notes from on-line lecture, Part 3
3/27 Initial Course-Project Proposal Due (5:15 PM, as a PDF file, by e-mail to reps at cs.wisc.edu)
----------------------------------------------------------------------------
3/29 Problem Set 3 assigned
3/30 Generating extensions Notes on partial evaluation (Part 2; Generating Extensions)
4/1 Partial evaluation of a first-order Notes on partial evaluation (Part 2; Partial Evaluation of Function Programs)
functional language (Summary) [Jones et al. 93], Chapter 5
Tips on writing a research paper Slides
4/3 ``Mystery'' lecturer Recording; the password is Rptp6tSh; recommended speed: 1.25x
----------------------------------------------------------------------------
4/6 No class
4/8 No class
4/8 Course Project Milestone 1 Due (5:15 PM, as a PDF file, by e-mail to reps at cs.wisc.edu)
4/10 No class
4/10 Problem Set 3 due (5:15 PM, as a PDF file, by e-mail to reps at cs.wisc.edu)
----------------------------------------------------------------------------
4/13 No Class
4/15 No class
4/17 No class
4/17 Course Project Milestone 2 Due (5:15 PM, as a PDF file, by e-mail to reps at cs.wisc.edu)
----------------------------------------------------------------------------
4/20 No class
4/22 No class
4/24 No class
----------------------------------------------------------------------------
4/27 FINAL PROJECT ABSTRACTS DUE (11:00 AM, in plaintext, by e-mail to reps at cs.wisc.edu)
4/27 No class
4/29 FINAL PROJECT PRESENTATIONS
5/1 FINAL PROJECT PRESENTATIONS
----------------------------------------------------------------------------
5/4 FINAL PROJECT WRITEUPS DUE (5:15 PM, as a PDF file, by e-mail to reps at cs.wisc.edu)
----------------------------------------------------------------------------