On Moodle


This course is designed to acquaint you with the fundamental ideas behind modern programming language design and analysis. Ultimately, you should come away with the ability to apply programming language techniques to your own projects.

The course has three broad topics:

The first part of this graduate-level course focuses on the semantics of a variety of programming language features (e.g., "what does a while loop really mean?"). We will study structural operational semantics as a way to formalize the intended execution and implementation of languages. Operational semantics are extremely powerful and flexible. They enjoy wide use in modern programming language research. In addition to operational reasoning, we will also survey axiomatic semantics, which provides a basis for verifying imperative programs. Finally, we'll briefly look at a third semantic style, denotational semantics, which is extremely useful for relating different languages (e.g., compilers do this).

The second part of this course provides an introduction to the study of type systems for programming languages. We will start our study of simple languages, moving toward the simply-typed lambda calculus, a simple version of another extremely powerful concept: the lambda calculi (broadly construed). Type systems and variations on the simply-typed lambda calculus abound in modern programming languages research, as they provide simple, yet highly-expressive languages for expressing computation in the abstract.

The last part of the course covers special topics drawn from research in areas.

In addition to the topics chosen by the instructor, students will have the opportunity to consider other related topics of interest in the form of a course project, most often in the form of a survey of recent research on a topic of interest.


The prerequisites for this course are programming and mathematical experience with prior exposure to several different programming languages, such as C, ML, and Java, which may be satisfied by taking CSCI 3155 or equivalent. The ideal programming experience is an undergraduate compilers course (e.g., CSCI 4555). The ideal mathematical experience is familiarity with mathematical logic and the ability to construct rigorous proofs (in particular by structural induction). Your desire to be exposed to this material is very important.

Advanced undergraduates may consider taking this course after talking with the instructor.


You will be responsible for the following:

Grading. There is no predetermined curve (i.e., I hope everyone gets an A based on the level of mastery demonstrated).

Resubmission Policy. This course is designed so that much of the learning happens on the homework assignments. To encourage iteration until mastery, you may "redo" any assignment via an oral interview with the instructor. This must be completed by the third to last week of the semester (November 22). You may request one interview per assignment up until the November 22 deadline. However, you may discuss your solutions with the instructors in office hours as much as you like before requesting the interview.

Late Assignment Policy. 25% of the total point value for the assignment will be deducted for any assignment that is late up to 3 days including weekends (i.e., on the 4th late day, the assignment will be accepted for comments but no longer for credit).

Make-Up Exam Policy. There will be no special or make-up examinations for any student (except in the case of emergency or the stated special accommodations).

Extra Credit and Participation. Extra credit opportunities may be offered during the course semester. Extra credit is recorded separately from normal grades and are only considered after final grades have been calculated. If your final grade is just below a grade cutoff, extra credit may bump you up to the next grade.

Home Submissions and Collaboration. You are encouraged to collaborate on the homework assignments. Assignments are the main opportunity to learn material in this course. Everyone will submit assignments, and you must cite your collaborators explicitly. Use Moodle to submit assignments and disclose collaboration. Late assignments overwrite earlier assignments, but are counted as "Late"; do not re-submit after the deadline unless you want these effects.

Textbook and Resources

There are two textbooks we will read (outside of class) and discuss (in class):

Additionally, these are good supplementary resources, for interested students:


Both your ideas and also the clarity with which they are expressed matter—both in your English prose and your code!

We will consider the following criteria in our grading:


Moodle. We will use Moodle for class discussion, grades and protected resources. If you do not already have an account, please create one and join the course moodle. The enrollment key is in the welcome e-mail. If you do not receive this e-mail, notify the instructor.

Off-Campus Access. The CU library has instructions for off-campus access to certain online resources (e.g., ACM Digital Library).


Computing. For a Linux environment, the following are some resources:

Collaboration Policy

You are welcome and encouraged to work together in learning the material. If you worked with someone on an assignment, or if your submission includes quotes from a book, a paper, or a web site, you should thank the source. Bottom line, feel free to use whatever resources that are available to you as long as you cite them in your submission.

We will go by the honor code set forth by the University:

All students of the University of Colorado at Boulder are responsible for knowing and adhering to the academic integrity policy of this institution. Violations of this policy may include: cheating, plagiarism, aid of academic dishonesty, fabrication, lying, bribery, and threatening behavior. All incidents of academic misconduct shall be reported to the Honor Code Council and those students who are found to be in violation of the academic integrity policy will be subject to both academic sanctions from the faculty member involved and non-academic sanctions given by the Honor Code Council (including but not limited to university probation, suspension, or expulsion).

Please refer to to view the specific guidelines. If you have any questions related to this policy, please contact the Honor Code Council at

Classroom Behavior

We trust and expect everyone to behave in a civil and courteous manner.

Discrimination and Sexual Harassment

We will go by the policies set forth by the University:

The University of Colorado at Boulder policy on Discrimination and Harassment, the University of Colorado policy on Sexual Harassment and the University of Colorado policy on Amorous Relationships apply to all students, staff and faculty. Any student, staff or faculty member who believes s/he has been the subject of sexual harassment or discrimination or harassment based upon race, color, national origin, sex, age, disability, creed, religion, sexual orientation, or veteran status should contact the Office of Discrimination and Harassment (ODH) at 303-492-2127 or the Office of Judicial Affairs at 303-492-5550. Information about the ODH, the above referenced policies and the campus resources available to assist individuals regarding discrimination or harassment can be obtained at

Special Accommodations

We will make every effort to make special accommodations that are reasonable and fair to all students. Please note that we will accept requests for adjustments during the first four weeks of class.


We will go by the disability guidelines set forth by the University:

If you qualify for accommodations because of a disability, please submit to the course staff a letter from Disability Services within the first four weeks of class so that your needs can be reasonably addressed. Disability Services determines accommodations based on documented disabilities (303-492-8671, Willard 322).

If you have a temporary medical condition or injury, see these guidelines.

Disability Services' letters for students with disabilities indicate legally mandated reasonable accommodations.

Religious Observances

We will go by the policy for religious observances set forth by the University:

Campus policy regarding religious observances requires that faculty make every effort to deal reasonably and fairly with all students who, because of religious obligations, have conflicts with scheduled exams, assignments or required attendance. In this class, we will try to accommodate religious conflicts in a reasonable manner. Please check the exam dates and submit all requests for adjustments within the first four weeks of class.

See for further details on the policy.

Homework Assignments

All homework must be submitted individually. You may discuss the problems with others, but you must turn in your own work. If you discuss the problems with someone, you must cite them (following the collaboration policy).

Homework solutions should be submitted by 11:55 p.m. on the due date. Your write-up should be submitted as a pdf or plain text file along with any code (if applicable). No other formats please. Either a typeset or a legible handwritten write-up is acceptable.

Specific assignments and their due dates are available on Moodle.

Final Projects

Project Guidelines

Students are expected to select and complete a substantial course project during the semester on a topic related to the class.

The first step is to submit a project proposal. The proposal should explain what you expect to learn from the project (i.e., why is it interesting to you?) and should include a work schedule. Make sure to budget time for writing a short project paper (~5 pages) describing the project and for preparing a short (~15-20 minutes, depends on number of projects) project presentation during the last week of classes. The project proposal should be one or two pages long. The main purpose of the proposal is for me to give you feedback on its feasibility.

The main goal of the project is to allow you to customize the content of the course to your own interests. The goal is not to force you all to produce novel results in one semester. Course projects like this often lead to collaborations that eventually yield exciting research. In the hopefully-likely event that you end up enjoying your project, come see me about taking it further (say, to publication).

Project Scale

I do not expect each project to lead to novel results, though I hope some projects will lead to publication!

Project Kinds

Projects on any subject related to the class are acceptable. The goal is to allow you to customize the project to your interests. There are three main types of projects: research projects, survey projects, and implementation projects.

In general, I recommend that you try to do a research project. They are typically a bit harder but much more rewarding than either survey or implementation projects.

Research Projects

There are many kinds of research projects, including the following:

These projects are harder because they always involve some survey work and often involve some implementation. If you want to do a research project, and you are not yet sufficiently familiar with the area of the project, you should start with a brief survey and then turn it into a research project. While research is necessarily open-ended, be sure that you have a well-defined goal for the end of the semester so that you have something to write up and present.

Survey Projects

Pick an area in which you are interested. Read at least six papers thoroughly and at least six other papers "superficially". I will help, but you should do most of the work in finding the relevant papers. Then, write a paper on what you have learned:

Keep the scope narrow enough so that you can say something interesting. Please do not pick an area that already has good survey papers available (or be sure to provide evidence to me that your survey will be different in some way).

Implementation Projects

Pick a fragment of a language or a relevant algorithm, and implement it! There is no firm limit on the amount of code.

An implementation project should feature "numbers": controlled, experimental results that help to sway your audience in favor of a point you are making. You should actually have a point: "I implemented a register allocator" is not quite good enough. You will want something more like: "Graph-coloring register allocation yields fewer spills and thus smaller and faster code than greedy register allocation. On the X benchmarks for the Y architecture, replacing a greedy register allocator in the Z compiler with a graph-coloring one resulting in a A% decrease in code size and a B% decrease in average executing time."

Your implementation must be relevant to language design or analysis. It could also be relevant to language implementation, provided that it has sufficient conceptual content and is close enough to the course. Graph-coloring register allocation wouldn't actually cut it.

The Status Update

The Status Update is a short write-up (less than one page). It should explain what you have done so far and how you plan to meet your goals in the final month of the project.

The Presentation

The presentation should be short and should describe what the problem was, what the difficulties were, and what was accomplished or learned. You will find it much easier to prepare the talk using slides (perhaps 8 to 15 slides, depending on your speed).

While preparing the talk keep in mind who your audience is. You will be presenting to colleagues who are eager to find out (1) about new exciting facets of programming languages and (2) how much fun you had. Plan to motivate the project (i.e., why is this important?) and to describe what you learned from it. Keep in mind that your colleagues have not read all the papers that you have read to do the project.

The Paper

Your write up at the end of the semester should be in the form of a short research paper. The project paper should have an abstract and an introduction describing the tackled problem, its motivation, and a very brief summary of the accomplishment. Then you should write a description of your notations (especially if they are different from what we used in class). Then you continue with the body of the material. The paper should end with a conclusion putting in perspective the accomplishment of the project and mentioning the open problems and with a bibliography of cited papers. Research and implementation papers should also have a related work section in which they compare the work with previous research results.

You should write your project paper as if you were submitting it to, for example, the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). You might want to browse the papers from PLDI 2014 or POPL 2014. Aside from giving you a number of data points for how the paper should look graphically, reading the electronic editions might help you to find a topic. Extending previously-published work is often not a bad start.

Your project paper should be 5-10 pages, as necessary. You will turn in a PDF as well as your sources. You will want to use the LaTeX class file or Word template produced by SIGPLAN.

Peer Review. You will have the opportunity to write reviews of your peers' project papers for extra credit.

Class Participation on Moodle

It is important to attend class and read the readings.

Class participation includes in-class participation, as well as participation on the Moodle discussion forum. All enrolled students are assigned to post "a moment's thought" on each lecture and reading set---at least 1 substantive comment, question, or answer. Initial comments, questions, or answers for each lecture must be posted the night before the next meeting (i.e., comments for Tuesday's meeting must be posted by Wednesday night, and comments for Thursday's meeting must be posted by the following Monday night). The goal is to identify concepts that need reviewing in the subsequent class.

You may and are encouraged to post comments or questions about the reading before the class where we will cover it. Posting early will help focus our discussion.

In place of class participation, distance students are expected to participate more heavily on the discussion forums (e.g., at least 1 extra substantive comment than required for everyone each week).

Here are some examples of good comments:

The intent of the forum post is definitely not to have you perform extra reading or web searching, but rather to take a moment to reflect upon the day's reading or class discussion.

Acknowledgments for this Course

This course is based on similar courses taught by others: