CMSC 838Y: Agile and Adaptive Programming Systems
Instructor Michael Hicks
CSI 3118 TuTh 12:30pm-1:45pm
Office Hours TuTh 2:00pm-3:00pm AVW 4131
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.
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,
- 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
- 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
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
- 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
- Final Exam. (30%) The final exam will be comprehensive and will
count for comp credit.
The project will take place in two stages:
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.
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
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
Presentations will be judged based on the following criteria (horked
from Chris Hawblitzel's course syllabus):
Remember that your two papers contain more detail than you can hope to cover
in a single lecture. This is
one reason that it's hard work to prepare a good presentation: not only
do you need to understand the paper, but you need to filter out the irrelevant
details and amplify the key arguments. You'll probably have omit entire
sections of the paper from your talk -- don't worry about it. Simply mimicking the structure of
the paper ("regurgitating it") tends to produce a disconnected sequence of boring facts.
A good talk should tell a story;
every idea should be motivated, and all facts should fit together in a coherent
picture. Telling such a story in a short time often requires
creating your own explanations, motivation, and examples.
- 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
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.
||Papers (by first author)
|Formal Semantics of Programming Languages
|Linking & Modules
|Dynamic Software Updating
|Dynamic Code Generation (Run-time Specialization)
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.
- 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