CS 301 Spring 2019
Compiler and Runtime System Design

What is CS 301?

CS 301 covers principle and practice in the design and implementation of compilers and programming language runtime systems. CS 301 runs in tutorial format and includes a semester-long software implementation project.

Compiler and runtime system design is a great CS capstone topic that unifies core computer science theory and practice to build essential programming tools. Compilers are nominally program translators, but they do much more, from automatic optimization to sophisticated program analysis. The toolkit we develop for thinking about programming languages, compilers, and runtime systems, and program analysis has applications to a range of problems in software reliability, systems, security, privacy, energy efficiency, probabilistic computing, accessibility, fairness, biology… really every application of computing (and beyond).

Goals

This course aims to prepare you:

  • To understand the theoretical foundations and practical architectures of compilers and runtime systems.
  • To apply foundations from core computer science in practice to implement a compiler.
  • To design, implement, and document a non-trivial software artifact using effective style and structured development practices.
  • To consume technical literature independently and communicate technical knowledge effectively in oral and written form.
  • To engage with current research in programming languages, compilers, and program analysis.
  • To apply the programming language/analysis reasoning toolbox to a broad range of computational problems.

Topics

The course home page hosts the working schedule. Course topics include:

  • lexical analysis, scanning
  • syntax analysis, parsing
  • abstract syntax trees, symbol tables
  • semantic analysis, scope, type-checking
  • intermediate representations
  • code generation
  • optimization
  • runtime systems
  • static and dynamic program analysis

When Should You Take CS 301?

CS 301 is a great capstone topic that draws on foundations from the entire core CS curriculum. It is a good choice for juniors or seniors who have taken a couple (or more) core CS courses and enjoyed CS 240 or CS 251. To succeed in CS 301, you need some maturity (and joy) as a programmer and learner, some interest in foundations, some background in core CS foundations, an eagerness to build things, and the drive and independence to tackle large challenges.

Minimum Prerequisite: CS 230 and at least one of CS 240 or CS 251.

Recommended Prerequisite: At least two of CS235, CS 240, CS 251. CS 231 is also helpful. The more core CS courses you have taken, the more big-picture connections you will see.

The success of your experience and your peers’ experiences in the tutorial format and the semester-long team project depends on all participants making significant intellectual investments. Expect CS 301 to be more immersive (and more fun!) than CS 240 or CS 251. If you are considering taking CS 301 concurrently with CS 240 or CS 251, please consult me and the instructors of those courses to discuss whether the pairing is a good idea for you. Electing credit/non grading with a plan to spend less time on the course is not wise. If you wish to elect credit/non grading for other reasons or if you have other questions about the course, please come chat!

Logistics

The CS 301 Spring 2019 website and email list carry schedule, materials, and timely announcements.

Staff

Name Contact Locale Drop-in Hours
Class Instructor Ben Wood benjamin.wood SCI S580 (office) + Microfocus (lab) Microfocus: Wednesday 3:00pm - 4:30pm, Friday 2:45pm - 4:30pm; or by appointment
Classmates CS 301 Spring 2019 email list SCI Microfocus, around campus by appointment

Meetings

Note: this schedule differs from that published by the registrar since there is no official support for tutorial format.

  1. The first course meeting takes place Tuesday 29 January 1:30-2:45pm in the Microfocus lab (not SCI 264). Participation is required.
  2. Work meetings take place Fridays 1:30-2:45pm in the Microfocus lab (not SCI 364). Agenda items are listed on Fridays in the calendar. Participation is expected.
  3. Tutorial meetings take place weekly on Tuesdays (possibly Monday evenings or Wednesday mornings) starting in the second week in my office. Tutorial topics are listed on Tuesdays in the calendar. Preparation and participation are required.

Please silence and stow phones out of sight during course meetings.

Course Materials

All tutorial assignments and project assignments are linked from the calendar on the course website.

Texts

Reading is essential to CS 301. Most course readings rely on two main textbooks:

Both books have great parts and quirky parts. We mix and match from these and other provided material. We typically use Dragon a bit more than EC, but for many readings there is a choice between the two, and with some experience, you may find that you prefer the style of one or the other.

New hardcovers are expensive, but reasonable used/paperback/international copies are usually available for $15 - $60 by searching online booksellers for “aho lam sethi ullman” or “cooper torczon”. Electronic options are available as well. Note that one popular electronic option seems to be missing many symbols on every page, making it downright confusing. Get in touch with me if you’re uncertain about a particular option. Many past CS 301 students appreciated reading/highlighting/scribbling on old-school paper, whatever its source. I have a few physical copies of each book to share, but this course involves enough reading that you will definitely appreciate being able to roam with your own copy.

Acknowledgments

This course material is based on similar assignments and projects developed at Cornell University and by Stephen Freund (at Williams College).

Format and Course Work

CS 301 follows a tutorial format with two key components:

  1. topic Weekly tutorial meetings replace lectures, exploring theoretical foundations for compilers and runtime systems through student-led presentation and discussion of readings and problem sets in small groups with me.
  2. code A multi-stage team programming project puts theory into practice to build a compiler for a statically-typed programming over the semester.

Tutorial: topic

The first core component of the course is the tutorial, a small-group pedagogical method that is an immersive alternative to lectures.

Tutorial Overview

In the first week of the semester I form tutorial groups of 2-3 students, after collecting some input from you. Starting the second week of the semester, each tutorial group meets weekly with me to discuss the current reading and problem set assigned the week before. Weekly readings and problem sets consist of exercises to master theoretical foundations, explorations of design considerations, small programming exercises, or research paper reviews. Please read the advice below about technical reading for CS 301. There are no lectures.

You are expected to complete the reading and a rough draft of solutions to the problem set in preparation for each tutorial meeting. Meetings center around student-led discussion of the problem sets and concepts. My role is to watch and listen, ask useful questions, or give a nudge if we get stuck or head too far in the wrong direction. This means that, beyond simply reading and preparing solutions, you should prepare to participate actively: be ready to present your work and the key points of the readings. Do not prepare a polished lecture. Do take time to identify key ideas of the reading and problem set solutions, and how to present them orally, with the help of a whiteboard as needed. You will submit polished solutions for selected problems following the meeting in tutorial reviews to help capture and reinforce the concepts and connections that you figured out during the meeting.

The tutorial meeting format promotes growth and confidence in your skills for independent learning and clear oral technical communication. Meetings may seem intimidating to start. You may get stuck on a problem or an explanation, despite your best effort to solve it or understand it. Occasionally, you may get stuck presenting an idea you thought you understood (or one you know you don’t understand). Awkward pauses ensue. These are all fine, expected, and useful toward the purpose of tutorial meetings: learning. These meetings are rough drafts, not final products. When I ask you to prepare for meetings, the goal is to be prepared to learn during the meeting, which does require some understanding, but is not necessarily equivalent to being prepared to explain everything flawlessly. The opportunity to work through obstacles productively together, and at the right pace for you, is a merit of the format. The more you take charge, the more you learn.

Tutorial Work

There are three weekly course work elements attached to the tutorial component of the course:

  • Tutorial preparation includes reading, taking notes, attempting problems, and drafting solutions in preparation for tutorial meetings.
    • Preparation is not submitted or evaluated directly.
  • Tutorial participation is active engagement in tutorial meetings by presenting or discussing topics or problems and by asking or answering questions.
    • Participation is evaluated based on a combination of end result and growth to reach it.
    • Tutorial meetings are required. If you cannot attend your usual meeting one week, arrange with me in advance to join a different meeting that week.
  • Tutorial reviews are clear written solutions to selected tutorial problems, typeset with LaTeX and submitted after each tutorial meeting.
    • Reviews are evaluated based on the accuracy, and, where relevant, the insightfulness of discussion or elegance of solutions.
    • Reviews are due within 24 hours after the end of your tutorial meeting. An extra 24-hour grace period is available with advance notice.

The honor code definition for tutorial work describes acceptable collaboration.

Project: code

The second core component of the course is a semester-long team project applying the principles we learn to implement a full compiler for a statically-typed programming language.

Project Work

The project consists of four prescribed stages that require you to design and implement a compiler architecture to meet provided specifications, plus a final open-ended stage that requires you to design, implement, evaluate, present, and report on a program analysis or language feature extending the standard compiler project.

Project work will be evaluated base on correctness, efficiency, design, style, and documentation. Project work is maintained and submitted using Git version control repositories. Submitted project work will undergo evaluation and code review with me for all stages and some checkpoints. After code reviews, teams may fix issues or act on suggestions for improvement and optionally resubmit their revisions for re-evaluation.

Project Teams

You are highly encouraged to work on the project in self-formed teams of 3 students (optionally 2). The honor code definition for CS 301 project work describes acceptable team collaboration. Project teams are self-formed and may or may not align with tutorial teams. Mini-projects in the first couple weeks of the course are an opportunity to try out potential long-term teammates. Consider how well your schedule and courseload fit those of potential teammates. Although I may permit or require team reorganization later based on team dynamics, there is nontrivial time and shared-knowledge cost to do so. We aim to avoid it.

While individual project work is not strictly prohibited, it is strongly discouraged. You must make a strong case to me to receive permission to pursue the project alone.

Project Schedule

The project is a significant amount of work throughout the semester. Project stages are substantial and cumulative. Falling behind results in significant and cascading impacts on the rest of the project. To help keep on schedule, project stages contain intermediate checkpoint deadlines in addition to the overall stage deadline. Project deadlines, listed on the calendar, are typically Fridays. Start each step early and meet each checkpoint.

Late Policy

Project work is due at the date and time specified in the assignment manifest. Each project team is allotted a budget of 5 × 24-hour project late passes to delay project checkpoints or project deadlines no later than the last day of scheduled classes.

  • Multi-day stretches without scheduled classes (i.e. weekends and breaks) are charged against your late pass budget as if they are exactly 24 hours long. A late pass applied to a deadline on the day before a weekend or break extends that deadline to the same time on the last day of that weekend or break.
  • Any number of available passes may be applied to any project checkpoint or project deadline.
  • No work is accepted past the end of final exam period, regardless of available late passes.
  • Late passes are not transferable, reusable, or divisible.

Meet with me as early as possible if your team will miss a deadline beyond your late pass budget.

Consult your instructor and class dean for alternative arrangements in case of extenuating circumstances.

Evaluation

Overall course letter grades weight tutorial work and project work roughly evenly.

Individual units of tutorial and project work are generally evaluated using the following scale, along with qualitative feedback:

∅ missing or unsatisfactory, falls far short of expectations, extensive problematic issues
✓− satisfactory, meets some expectations but falls short of others, some nontrivial issues
✓ good, meets expectations, no issues or few trivial issues
✓+ excellent, notably exceeds expectations, especially insightful, effective, or elegant
2✓ outstanding, expands the instructor’s understanding

This scale should not be interpreted as equivalent to a particular set of letter grades. Expect that ✓ is common, while ∅ (assuming you have made an effort) and 2✓ are rare.

Honor Code

The Wellesley Honor Code applies to CS 301, including through CS 301-specific policies for acceptable resources (collaboration, assistance, and reference) in course work. The general spirit of these policies should not be surprising, but the details are key to boosting the quality of your learning and maintaining a fair and rigorous academic environment for you and your classmates. Full definitions appear below. Please read the entire policy. If in doubt about details, please ask for clarification. Violations of these policies are handled through the appropriate Honor Code charge or resolution processes.

Tutorial Policy: topic

Small-group collaboration is generally encouraged in tutorial preparation and participation with one main restriction: do not copy solutions. When you wish to remember something you developed collaboratively, it is most effective for memory and understanding to write or draw your own notes. Do not take a photograph.

More specifically:

  • Tutorial preparation may be done collaboratively with other CS 301 Spring 2019 students (in your tutorial group or in others), including to attempting draft solutions to problem sets together, if collaborators participate in roughly similar measure. Considering the workload and intellectual demands of the material, you are encouraged to collaborate on preparation in this way, but please keep your groups small: not much larger than a tutorial group.
  • Tutorial participation is naturally collaborative.
  • Tutorial reviews must be your own work. Your submitted reviews must cite all collaboration, assistance, and reference (excluding course materials, reference linked from the course website, and notes/happenings from your tutorial meeting) that you used to prepare them. List each person or resource with a short phrase identifying the topic or nature of collaboration, assistance, or reference.

Project Policy: code

Teammates must contribute to all stages of the project in similar measure. You are encouraged to do pair/team programming, but sometimes it may be advantageous to sketch a design together and then divide and conquer programming tasks. Regardless, all team members should understand and be comfortable explaining all components of the project implementation.

  • Your team’s submitted solutions must be your team’s own work.
  • Your submissions must cite all collaboration, assistance, and reference (excluding course materials and reference linked from the course website) that you used to prepare it. List each person or resource with a short phrase identifying the topic or nature of collaboration, assistance, or reference.
  • Collaboration:
    • You may discuss high-level ideas or strategies with other teams in small groups.
    • You must not communicate detailed algorithms, implementations, code, formulae, or other detailed solution steps with other teams.
    • You must not, under any circumstances, view, share, prepare, or accept written solutions or assignment code outside your team.
  • Assistance:
    • You may accept help from course staff to locate errors, interpret error messages, and correct errors of syntax.
    • You may accept help from other CS 301 Spring 2019 students to interpret error messages, subject to the above policy on viewing code.
  • Reference:
    • You may consult course material from CS 301 Spring 2019 and external documentation of required tools.
    • You may consult external reference resources for general concepts and techniques, provided you cite them.
    • You must not consult solutions to this or any similar assignment.
    • Code reuse and adaptation:
      • You may reuse and adapt provided starter code in your solution without restriction.
      • You may reuse and adapt code from other course materials only with prior written approval from the instructor and explicit attribution of the source.
      • You must not reuse or adapt any other code.
  • After the semester:
    • Some students students may wish to include work from CS 301 in portfolios, resumes, etc. Please do not post code publicly (including on GitHub, GitLab, Bitbucket, your own website, etc.), but feel free to show your code privately to potential employers or others who are not students. Do not make your code accessible or viewable by current or future CS 301 students.

Academic Support

Outside regular tutorial meetings and code review/project work sessions, I am available for drop-in hours or by appointment if you are stuck, struggling, curious, or want to talk for whatever other reason. There are no tutors for CS 301.

Most students struggle to some extent with readings and tutorial format at the start of CS 301. After all, technical reading skills are a first-class goal of this course and also something you have done rarely if at all in the past. Whatever your experience of “required” “reading” has been in other CS courses, CS 301 is likely to change how you understand both those words. So, don’t worry if you feel a bit overwhelmed the first couple times around. Learning the style of reading you need for this course takes practice and time. The reading hints below can help get you started on that journey.

How to Read for CS 301

Using technical reading as your primary means of knowledge acquisition can require significant adjustment from more passive lecture-based courses where you can rely on the instructor to highlight important points and provide alternative explanations. In this course, you and your group are in charge. I assist mainly by asking useful questions to guide you. Building skills for technical reading, as you do in this course, is invaluable as a computer scientist (and beyond).

It is rarely possible to read a technical document and absorb all the relevant detail in one pass. Instead, aim to read repeatedly at deepening levels of detail and work through examples. Read and work on exercises in stages:

  1. Do a cursory reading to identify important concepts and high-level structure within the topic (and also what looks less important so you can skip it initially). This is an important skill that takes time to develop.

  2. Do a detailed, methodical reading of each section and work through examples carefully, aiming to understand details. Become familiar with the important concepts of each section before moving on to the next. If you get stuck, take a break, jump ahead and come back later, or try a related exercise. Context from later material may provide the missing link for you.

  3. Begin the exercises once you have some working knowledge of the topic. Consider which concepts are at play in each exercise. Refer to the reading (especially examples) as needed. Exercises may reveal new connections. If an exercise involves a secondary detail you skipped during your detailed reading of important concepts, go back and read further.

  4. When you have completed the readings and exercises, take a few minutes to review them, pick out key points, and consider how to explain these.

  5. If you are still stuck on some idea or exercise, write down what you do know and how you think it might work so we can work from there in your meeting.

Tia Newhall (Swarthmore College) has more good advice on reading technical computer science material. It targets lecture courses, but many points can be extrapolated to this format.

Feedback

I am always open to considering your comments, suggestions, or concerns about the course or how we can make it more accessible to you. Please feel free to stop by for a conversation, send email, or use the anonymous feedback form if you would prefer.

Accommodations

If you have a disability or condition, either long-term or temporary, and need reasonable academic adjustments in this course, please contact Disability Services to get a letter outlining your accommodation needs, and submit that letter to me. You should request accommodations as early as possible in the semester, or before the semester begins, since some situations can require significant time for review and accommodation design. If you need immediate accommodations, please arrange to meet with me as soon as possible. If you are unsure but suspect you may have an undocumented need for accommodations, you are encouraged to contact Disability Services. They can provide assistance including screening and referral for assessments. Disability Services can be reached at disabilityservices@wellesley.edu, at 781-283-2434, by scheduling an appointment online at their website https://www.wellesley.edu/disability, or by visiting their offices on the 3rd floor of Clapp Library, rooms 316 and 315.

Students whose religious observances conflict with scheduled course events (e.g., labs, exams, etc.) should contact the instructors in advance to discuss alternative arrangements. You may do this through the new Wellesley College Religious Observance Notification system if you prefer.

Faculty Responsibilities on Disclosures of Discrimination, Harassment, and Sexual Misconduct

Pursuant to Wellesley College policy, all employees, including faculty, are considered responsible employees. That means that any disclosure of discrimination, harassment, or sexual misconduct to a faculty member will need to be shared with the College’s Director of Non-Discrimination Initiatives / Title IX and ADA / Section 504 Coordinator, Sonia Jurado (781-283-2451; sjurado@wellesley.edu). Students who do not wish to have these issues disclosed to the College should speak with confidential resources who are the only offices at the College that do not have this same reporting obligation. On campus, confidential resources include Health Services (781-283-2810 available 24/7), the Stone Center Counseling Services (781-283-2839 available 24/7) and the Office of Religious and Spiritual Life (781-283-2685). You should assume that any person employed on campus outside of these three confidential offices has an obligation to share information with Wellesley College through the Office of Non-Discrimination Initiatives.