Syllabus

Syllabus / Schedule / Resources / Review Papers

Modern software must be both agile and adaptive.  By the first, we mean that software components should be easily reusable in different contexts, and/or take different roles in the same context.  By the second, we mean that most software will benefit by adapting to its run-time environment in some way, whether by loading environment-specific libraries at the start, or more ambitiously, by importing new functionality during program execution, perhaps to add new features or fix bugs, or to interact with another software system.  In this course, we will consider the mechanisms and programming paradigms needed to create agile and adaptive software.

Topics

The general thrust of the course will be on technologies that can cause a program or system to change at runtime, to adapt or adjust to changing demands and situations.  This idea mainly encompasses the following areas:

• Dynamic Linking.  Dynamic linking is frequently used to construct programs at run-time rather than compile-time. Shared libraries are loaded at the time a program starts (or as needed), based on the latest version available, and new modules can be loaded into a running system by user directive. For example, many server systems allow loading custom servlets. Examples of dynamic linking abound, from Java classloading, to ELF-style linking of shared libraries. 
• Runtime Code Generation.  Oftentimes, functions will be written to be general, but at runtime only a fraction of the function code will actually be exercised.  For example, the Berkeley Packet Filter (BPF) interpreter installed in many operating systems is designed to execute an legal BPF program.  In practice, though, a small number of these programs will be installed in an OS at any given time.  In this context, the generality of the interpreter is an impediment to performance.  An alternative approach is to specialize the interpreter to its programs.  That is, at runtime, we generate code for an interpreter that only knows how to interpret the programs that it knows about, thus eliminating many runtime checks and unneeded code.  Examples of this sort of system include Cyclone, Tempo, Vcode, and others.
• Dynamic Compilation.  Rather than specialize particular functions at run-time to the arguments that they take, as is the case in run-time code generation, a dynamic compiler can compile or recompile arbitrary system components at run-time. The challenge is that compilation times must be short to be outweighed by the performance benefit of faster code.  Java has popularized the use of "just in time" (JIT) compilers for its virtual machines.
• Dynamic Software Updating.  Dynamic updating (as opposed to simply dynamic linking) mechanisms allow programs to actually be modified as they run. These allow classes, modules, instances, data, and more to replaced or transformed to fix bugs or add new features, but without halting the program. Examples range from low-level modifications to running binaries, as in the dynInst API, to systems that focus on source-level development of updateable software. Systems have been developed for OO languages, distributed programming, active networks, and more.

The material we cover will be both theoretical (i.e. formalisms of relevant systems, mechanisms, etc.), and practical (i.e. descriptions of implementations or architectures).  The first few weeks of the course will focus on some background in programming languages.  In particular, for the first few weeks of the course we'll look at:

• Structured Operational Semantics.  This is a common technique for formalizing programming languages and their execution.
• Type Systems.  A formalization of the well-known concept of types, used to restrict which expressible programs in a language are sensible.
• Module systems.  These are mechanisms for programming "in the large," to support things like separate compilation and composition.  Different programming languages have different ways of supporting modular structure. Java provides both classes and packages, COM defines a notion of component, C provides file-based separate compilation, Standard ML and OCaml provide structures and functors over those structures.  We'll look at some of the theoretical underpinnings of module systems, mostly in terms of type systems.

Having taken CS 631 in the Fall will be helpful, but is not required.

Later in the course, time permitting, we may look at run-time analysis of objects, typically referred to as reflection, and run-time analysis of types, also known as intensional type analysis.

Class Structure and Grading

The majority of the course will consist of reading and discussing web-available technical papers on the above topics, originating both from industry and academia.  In general, the course (and grade) will have four elements:

• Paper summaries. (20%) You will be asked to write a one to two paragraph summary of each paper we read in class, summarizing the key contributions and merits of the paper.  Do not simply rephrase the abstract of the paper: the review should contain your personal insights into the contribution of the paper, and why you think the paper is important or not important. These must be submitted before the class that covers that paper takes place, using the web submission form.
• Paper presentations and class participation. (15%) The instructor will give roughly half of the lectures for the class.  The remainder will be assigned to students.  You will be graded on your presentation, and on your participation in class. See below for more.
• Project. (35%) The student will propose a project idea roughly 1/3 of the way through the semester, to be finalized 1/2 of the way through, and then completed by the end of the semester. Students may also propose to work in groups of two, but the expectation of the project quality/difficulty will be twice as great. See below for more information.
• Final Exam. (30%) The final exam will be comprehensive and will count for comp credit.

Project

The project will take place in two stages:

1. Project proposal. The initial proposal should be about one page that indicates your thoughts on projects. You should indicate what areas you are interested in exploring (e.g. dynamic linking, extensible systems, module systems, dynamic updating, etc.), and how you hope to explore them. The latter part should express your general feeling as to methodology (e.g. whether you want to do something theoretical or practical, whether you want to implement something, do a survey, etc.). You should then justify both the relevance of the project to the course (why will you learn something by doing it?), and also the magnitude of the effort (can you get it done this semester, or at least get some reasonable piece done that fits into a more ambitious effort?).

   The initial proposal could contain a could contain a couple of different ideas, to be refined through discussion with the instructor. The final proposal will be a somewhat lengthier (perhaps 2 pages) version of the initial proposal, with goals and deliverables more clearly laid out.

2. Do the project. Projects should at the least have a written component, reporting what you accomplished. My belief is that the best projects will have both an implementation and analytic component. For example, you could build a software system using two different component technologies and compare the performance and ease-of-use of each one. As another example, you could implement and evaluate a new form of runtime adaptation mechanism. However, a survey is also acceptable. That is, you could pick an area we have considered in this class, and carefully survey all of the related research. The survey should be both informative and evaluative: you should say what the past work did, how it compares to other work, and how well it solves the problem set forth. You should also propose ideas for future study.

Some project ideas are on the resources page.

Presentations

Each student will give one lecture during the second half of the semester (following Spring Break). Presentation quality is important: read your papers early and be sure you fully understand them. I will be available for help, if you need it. Be sure that you have prepared a good presentation (consider practicing it beforehand). Some information about giving good technical presentations can be found on the course schedule.

Presentations will be judged based on the following criteria (horked from Chris Hawblitzel's course syllabus):

• understanding: does the presenter understand the material?
• thoughtfulness: does the presenter have insights and opinions beyond what was in the paper?
• background/perspective: did the presenter read background papers?
• clarity: can the audience understand the presentation? is the "big picture" clear? are there useful examples?
• materials: do the slides or use of blackboard illustrate and support the talk? are there diagrams to help convey the technicalities? (when your talk gets into deep territory, a diagram is worth 10K words)
• delivery: has the the presenter practiced?
• non-regurgitation: did the presenter do something beyond simply typing sections of the paper as bullet points? did the presenter motivate the ideas in their own words or just state ideas from the paper verbatim?
• answering questions: can the presenter handle questions from the audience?

The papers for thirteen lectures are available; please choose a lecture topic (the bold headings) and e-mail it to me as soon as possible. Topic preferences are first come, first-served (so specify a couple of alternates). I will update the topics list as I receive preferences from students. The lectures are to be presented in the order listed, starting the first class after Spring Break.

Final Exam

The final exam will consist of four questions drawn from the following topics.  The exam will be open-notes/open-book.  That is, you can bring any notes or papers listed with you for reference.  Each question will require a medium-length answer (2 pages or so of text plus diagrams), either of the flavor of a critical comparative analysis, a design proposal, or problem to solve using one or more of the systems.

There are other resources related to these papers (like slides) on the schedule page.  You might also check out other student reviews of the papers.  Bring extra paper and pencils with you to work out your answers before writing them on the exam.

Academic Dishonesty

• The college policy on academic dishonesty is strictly followed.  All graded materials (whether exams, summaries, presentations, or projects) must be strictly individual efforts.  In the case of a group project, only collaboration amongst the group is permitted.