Every high-level language is implemented by a combination of translator and run-time system. The translator targets low-level abstractions and instructions, many of which are provided by a target machine. Machine-level abstractions are typically supplemented by other abstractions which are implemented in the run-time system. Run-time abstractions can be high-level, but they are implemented by hand, not by a translator. Run-time abstractions may support such language features as procedure calls, exceptions, threads, dynamically allocated objects, and others.

The course provides a 50,000-foot view of the design and implementation of run-time systems, both classic and “modern.”

What will we learn and why?

The purpose of the course is to help us all learn how a run-time system should be designed and implemented. This learning should serve the following goals:

What will we learn from?

A lot of the important stuff never seems to get written down. We will nevertheless prioritize written sources, of these kinds:

To these typical academic sources we will add

The sources will be drawn from three populations:

I would love to finish this seminar with a coherent and comprehensive view of run-time systems, but the topic is broad, and there are significant gaps in the literature. We will do our best.

How will you influence our learning?

A class like this is inevitably influenced by the instructor’s biases. Here are some of mine:

What kind of class is this? How is it different?

Most classes in computing are organized around lectures and homeworks (problem sets or programming assignments), perhaps with some laboratory experiences. This class is a seminar,1 and as such it is organized around small-group collaboration. So that you understand the distinction, I compare the two kinds of classes.

In my mind, a good lecture course has these properties:

Our seminar will offer a dramatically different experience.

One way to view what is going on is that we have a semester-long conversation that leads us to consensus on:

Why do we teach seminars? Primarily because this is the way real science is done: through extended, vigorous conversations about problems and ideas. When it goes well, a seminar is among the most rewarding experiences you can have in a classroom.

What will happen in the classroom?

Class periods will be spent on discussion questions grounded in outside reading (including reading of source code). Ideally, questions will be available two days before class. Discussions are intended not only to solidify our understanding of what we have learned from the outside material, but to call our attention to gaps and omissions in what we have read.

During discussion, we may often split into subgroups.

Study code? How will that work?

Almost everyone is keen to do a case study of a real run-time system. I’ll find a way to make it work. We’ll start out studying code in the same way that we study papers: by focusing on prepared discussion questions. Based on classes I have taught that have studied code, I expect to make a few adjustments, such as putting code up on the projector or asking students to bring portable computers to class. Also, when you’re preparing discussion questions about code, I probably will ask a bit more of you than I would for a paper—you might become a mini-expert on some part of a system.

How much will we read and discuss?

In advanced CS seminars, it’s typical to read 12-page conference papers and to take one or two class sessions per paper. But for whatever reason, information about run-time systems is rarely found in short papers—we are going to read longer-form sources. I cannot say in advance exactly how much time we might spend reading and discussing each source, and therefore I can’t say how many sources we might grapple with over the course of one semester. I will balance these competing concerns:

What is expected of me outside of class?

Outside the classroom, you will

These expectations are described in detail below. Reading and analysis are typical of other seminars. Developing questions is less common, and “scouting” is unique to this course. The final deliverable comes in one of three forms (a review, a system guide, or a white paper); you choose the form most suited to your interests. The final deliverable emphasizes analysis, thinking, and writing; it is not a “project,” and it does not require project-style work.

How will I help others prepare?

With your classmates, you will take turns helping prepare discussion questions for class. Discussion questions for a Wednesday class will normally be ready by noon the preceding Monday; discussion questions for a Monday class will be ready by noon the preceding Thursday.2 Questions for each class will be prepared by me with the help of a student:

One set of questions is prepared for each class, not one for each paper or for each software system. I will do my best to distribute the work equitably.

You can sign up to prepare questions by editing post 7 (a pinned post) on Piazza.

What do discussion questions look like?

In my classes, discussion questions typically range from very general questions, which could be asked about any paper, to very specific technical questions, which are almost like tiny homework problems. Overall, my questions skew deep and narrow. From past classes on advanced functional programming, dataflow analysis, and probabilistic programming, here are some examples:

  1. Most papers answer a question or advance a claim. Just to be sure we’re all on the same page, what is Hughes’s question or claim?

  2. Both C++ and Ada enable a programmer to overload functions, procedures, methods, and operators. So what’s the big deal about type classes? Are there things type classes can do that you can’t do in C++ or Ada? If so, list them and give an example of each.

  3. Given a general control-flow graph and a label L, what model-theoretic idea would you use to characterize the set of all possible paths from the entry point to L? In general, is this set finite or infinite?

  4. This question is about dominator analysis: Suppose that both D and D dominate L. Prove that exactly one of the following three relations holds:

  5. Using Church’s query or lex-query operation, do you understand what sorts of prior/posterior distributions you can work with, and what sorts of observations you can make? Are they sufficient for the dice problems?

  6. In the discussion of procedure values in section 2, is there a difference between an “ordinary procedure” and a closure?

How do I scout a software system?

You will “scout” one software system and judge how suitable it is for a case study. Scouting involves a somewhat cursory look at the source code and documentation (let’s say at most a couple of hours) and a short, written report which answers these questions:

I plan to spend one class period, in the first week of October, discussing scouting reports and choosing a system.

Scouting reports must meet these requirements:

What’s this about a final deliverable?

A final deliverable enables you to build knowledge that is deeper and more solid than is possible through discussion alone. To accommodate students with different interests and workloads, I have designed three potential deliverables:

What’s expected of a review?

You may write a review of any paper, technical report, dissertation (or dissertation chapter), or other written text describing some aspect of run-time systems. The review should be organized as if for a journal such as ACM Transactions on Programming Languages and Systems (TOPLAS), Software—Practice & Experience (SP&E), or possibly the Journal of Functional Programming (JFP). Your review should not only address the material you read but should outline how you would like to see the material expanded to make a good journal article.

If you haven’t had much practice writing reviews, this deliverable will give you some, for course credit. Beyond the typical challenges of reviewing technical work, the primary challenge here is to identify the important gaps and omission in the original work, which you would like to see remedied in a longer version.

To help you learn to write a review, I will pull together some “advice for reviewers” from SP&E, JFP, and other sources.

Your review must meet the following criteria:

I’ll judge your review based on how well it identifies interesting information that is either unclear or missing in the original work, and how clearly it identifies the information you want to appear in a revision.

The review is meant to be the easy option, but it will still take some time. I have written a lot of reviews, and it usually takes me about an hour and a half to read a good 12-page paper. Writing the review can take anywhere from another hour to another three hours, depending on quality. (A wise man once said to spend the most time reviewing the best papers.) Identifying good topics for a journal version might take me another half an hour. To estimate the amount of time you yourself might take, I recommend that you scale to the size of the paper you are reviewing, then (to account for inexperience) double or triple the number of hours.

What’s expected of a guide to a system?

A guide to a software system should steer its reader toward the worthy parts of a real implementation. Such a guide should say

A component might be worth special attention because it solves an interesting problem, embodies a new idea, was discussed in class, is especially well crafted, or has some other good property. If you think a component is interesting, others will probably also think it’s interesting.

Using your guide, a reader should be able to pick up the system and quickly understand what is going on, appreciate some part of the code, and perhaps think about modifying it—or know what modifications not to attempt. Your readers should feel confident in studying the source code and should feel that you have told them where the bodies are buried (or where to find buried treasure).

I’ll judge your review based on how confident I am that your classmates could use it as a starting point to learn something more about a system than was possible in class.

The system guide is meant to be an option for students who are focused more on software systems than on research, and who want to use this class as an opportunity to get deeper into a system than would be possible for the whole group.

Unlike a review, a system guide need not be individual work: you may write a system guide as part of a team of any size.

What’s expected of a white paper?

A white paper should propose a question or problem for research. I’m looking for about two pages in ACM two-column format, but a white paper of one to four pages is acceptable. A white paper should answer some of the questions we would expect to be answered by a full research proposal:

If you want to exceed my expectations, you can enrich your white paper with more of the elements I would expect to find in a full research proposal:

I’ll judge your white paper based on how clearly you state the problem or question and how much evidence you marshal in favor of claims that the problem is important, interesting, and solvable. If, in addition, your white paper contains an original idea, I will be very favorably impressed.

The white paper is meant to be an option for students who are considering research in run-time systems or who want practice writing a proposal or a thesis prospectus. It is the most open-ended and therefore the most challenging of the final deliverables.

Unlike a review, a white paper need not be individual work: you may write a white paper as part of a team of any size.

What’s the schedule for final deliverables?

Final deliverables work on an “iterate until satisfied” model: as long as you submit early enough, I will look at as many drafts as you like. Only the final draft counts toward your grade. In order to help you produce your best work, I am suggesting several preliminary deadlines:

If you want to send your work to a peer reviewer first and then to me, that is OK, too.

That said, this is a graduate course, and I will not be evaluating or grading your ability to meet preliminary deadlines. I will evaluate only the work you deliver on December 14.

What kind of peer feedback do I have to give?

You are expected to be available to provide feedback on either a review or a white paper. (You need not, unless you want to, provide feedback on a system guide.3) You will read a draft and provide this sort of feedback:

Peer feedback is a lightweight way for you to help your fellow students. It need not be written; you can give oral feedback in person. While I hope you will give feedback of high quality, I will not evaluate your feedback—only your willingness to serve.

Depending on what choices your fellow students make about their final deliverables, you may or may not be called upon to provide feedback.

How long will my out-of-class commitments take?

To give you an educated guess about how many hours you might be committing to, here are some estimates:

How will everyone be evaluated?

My evaluation of your work, and your final course grade, will be based primarily on class participation and secondarily on your final deliverable. In detail, here is what I expect:

How might these expectations relate to your grades? Well, you are an experienced student and well versed in computer science, or you would not be eligible to take a seminar like this one. You probably also know how to contribute effectively in a small-group setting, how to look at code, and how to write a short technical text. In my past experience with these kinds of classes, a large majority of students have earned straight A’s or better, and almost every student has earned at least an A-minus. The occasional exception is the student who talks well in class but who delivers written work that shows no evidence of effort. Such students receive grades that are not sufficient for graduate credit.

Finally, here’s how I expect you to evaluate me:

What challenges should I expect?

Any small-group discussion class poses predictable challenges. In addition, a class like this one, which studies a topic that is not well documented in the literature, poses special challenges. Here are some that I know about:

What do I need to know coming in?

To succeed in this course, you must already be able to read research papers of the sort found in PLDI, OOPSLA, ICFP, ISMM, ESOP, Compiler Construction, and the like. You must also understand programming-language implementation at the level of COMP 40: You must understand the basic workings of registers, cache, memory, and the instructions that manipulate them, and you must be able to look at C code (or something similar) and explain what is happening at the machine level. You need not be able to explain how a compiler gets from here to there.

What else can I do to succeed?

Regarding a similar class, one of my former students contributed this advice:

The same former student also had this comment about his experience in class:

  1. According to the Oxford English Dictionary, a seminar is a select group of advanced students associated for special study and original research under the guidance of a professor.

  2. Exceptions: If a Wednesday class is discussing the same paper or code as the previous Monday’s class, then the preparation of Wednesday’s questions will await the outcome of Monday’s class, and the questions will be ready by noon Tuesday. And discussion questions for the Monday after Thanksgiving will be ready by noon the preceding Monday.

  3. Reviews and proposals are part of every project in our field, and every research student should know how to evaluate one. System guides are sui generis, and I feel that developing the skills needed to evaluate one is not worth your time.