CS 301 Spring 2021 T4
Compilers (Briefly)

What is CS 301, Compilers (Briefly)?

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, 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 students 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 and 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, plus intrinsic motivation, interest in the topic, and readiness to pick up new ideas quickly.

Recommended Prerequisite: At least one additional core course. CS 235, CS 240, and CS 251 are most relevant. CS 231 is also helpful. The more core CS courses you have taken, the more connections you will see.

The success of your experience and your peers’ experiences in the tutorial format and the course-long team project depends on all participants making significant intellectual efforts and time investments. There is a good chance that CS 301 will require the largest course workload you have encountered. 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 one or more other courses with workloads similar to CS 240 or CS 251, please consult me and your other instructors to discuss whether the pairing is a good idea for you. CS 301 should be rewarding if you are interested in the topic and excited to dive in, but there are many more efficient choices if your primarily goal is to fill out another CS 300-level. The purpose of this description is to set realistic expectations, not to scare you off. The course is offered now, so if you are excited about it, take it now.

If you are uncertain about any of this, please get in touch to chat!

Logistics

Role Name, Email Pronouns
Student You + Classmates (ask)
Instructor Ben Wood
benjamin.wood@wellesley.edu 		he/him/his

Instructor and Drop-in Hours

I am your instructor, Ben Wood. Please call me “Ben” (he/him/his). If “Professor …” is more comfortable for you, that’s fine too.

Drop-in hours are held by live video meeting with the option to sign up for a time slot in advance or just show up and see if I am free. The drop-in schedule, signups, and Zoom link are here.

Appointments outside regular hours are also available by request. To reach me privately (such as for accommodations or appointments), use email or a private message. For course questions that may be of interest to others or possibly could be answered by others, use the relevant discussion stream.

Meetings

  1. The first course meeting takes place Tuesday 13 April 5:30-8:15pm in the Zoom Workshop. If it is possible for you to join this first meeting, even if a bit uncomfortable in your timezone, please do so. (If not, please let me know.)
  2. Weekly large group meetings take place Tuesdays 5:30-8:15pm (and/or alternative TBD) in the Zoom Workshop. We will introduce an alternative option or adjust this time if it is untenable in some timezones. Agenda items are listed on Tuesdays in the calendar. These meetings will mix large group instruction, live problem-solving time, or project work time. Participation is expected.
  3. Weekly tutorial group meetings take place Thursdays (possibly Fridays) in the Zoom Workshop. Tutorial meeting times will be scheduled independently for each group at a mutually convenient time. Tutorial topics are listed on Thursdays in the calendar. Preparation and participation are required.

Communication

The CS 301 Zulip is used for all course communication in CS 301. It is organized into streams (these might evolve):

  1. #announcements: course announcements (Follow this stream regularly!)
  2. #questions: questions and responses/discussion about logistics, concepts, course work (do not post your code or complete/partial solutions), error messages, or software tools
  3. #community: everything else, hanging out, levity
  4. A private stream will be created for each project team as well.

Collaborating to ask and answer questions on the Zulip helps us all help each other by pooling our collective curiosity, experience, knowledge, and critical thought. Please engage enthusiastically, subject to these guidelines:

  1. Communicate respectfully and patiently with the goal of supporting others and yourself.
    • Asking a question is just as valuable a contribution as answering one.
  2. Before posting:
  3. Do not post complete or partial solutions to assignments/projects in the form of code, short answers, or detailed descriptions of algorithms in any human or programming language. Posting sections of starter code or code from course materials with attribution is OK.
  4. Use private messages, email, or appointments to communicate about private topics such as grades, extensions, or personal issues.

Using Zulip

Zulip messages belong to a topic within a stream. It’s like a more organized Slack also capable of long-form messages or a discussion forum also capable of quick chat. The 3-level organization allows flexible focus by selecting:

  • A topic: view only the messages within that topic chronologically.
  • A stream: view all messages from all topics in that stream chronologically.
  • All Messages: view everything chronologically.

Hygiene:

  • Reply (shortcut: r) to keep your message in the same topic; use a new topic for an unrelated message.
  • Move a message to a different topic or stream after the fact if it is out of place.
  • Formatting posts with Markdown or LaTeX can help readability, such as to separate code(snippets) from prose.
  • If showing a code example (not solution code), an error message, or other text, please post it as text (NOT a screenshot). Text is searchable, zoomable, reflowable, and more. Screenshots are much less useful than text for most programming communication. Preserve indentation, etc., by using simple code formatting in your message. Here’s an example. Use a screenshot if you need to show a graphical user interface that is not just text.

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. A few physical copies of each book are available in SCI L037 for use around SCI (please return them to this shelf!) if you are on campus. During difficult pandemic circumstances, we have electronic copies of the relevant excerpts available for CS 301 students ONLY. (Note if you experience good Google Drive behavior, it may now require enabling third-party cookies to work.)

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. Two weekly meetings explore theoretical foundations for compilers and runtime systems:
    • Weekly class meetings (plan: Tuesdays) will mix short lecture, group problem-solving, and open project work time.
    • Weekly tutorial meetings (plan: Thursdays or Fridays) use student-led presentation and discussion of readings and problem sets in small groups with the instructor.
    • Since two small-group tutorial meetings per week in the term system would be quite intense, we will alternate between the all-class format and the tutorial format, using each once per week. Some of the all-class meeting time will be similar in style to the tutorial meetings.
  2. A multi-stage team programming project puts theory into practice to build a compiler for a statically-typed programming over the semester.

Tutorial

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. Each tutorial group meets weekly with me to discuss the current reading and problem set assigned ahead of time. Tutorial 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.

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 or other visuals 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 submitted after each tutorial meeting.
    • Reviews are evaluated based on the accuracy, and, where relevant, the insightfulness of discussion or elegance of solutions.
  • For Spring 2021, reviews are due by Sunday night, but I suggest completing them ASAP after your tutorial session while the ideas are fresh in your mind.

The honor code definition for tutorial work describes acceptable collaboration.

Project

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 are listed on the calendar. Start each step early and meet each checkpoint.

Late Work

Project work is where the majority of your CS 301 learning will occur. You are strongly advised to keep up with deadlines. The course will move quickly, especially on the Term calendar. Falling behind on projects can make the work more difficult.

Sometimes, however, prioritizing completion of a project by the deadline may not be the right personal choice for you. To encourage you to learn from the projects while also affording flexibility when it benefits your health and well-being, you may use either of the following mechanisms to submit late work without penalty:

  1. Self-serve 48-hour late pass: You may delay any project or tutorial review deadline by 48 hours by submitting this late pass notification form before the original deadline. There is no need for any other communication in this case.
    • The form requires a brief summary of progress (e.g., “foobaz working, but stuck debugging frobnicator” or “not started”) and whether you anticipate seeking support (drop-in hours/appointment) for the project (yes/no).
    • If the 48-hour extended deadline falls during a break or weekend, it is automatically moved to the final day of that break or weekend.
  2. Custom extension: If you need to extend an deadline more than 48 hours, or if you did not submit a late pass notification in time, you must contact the instructor with an initial timeline and plan for when and how you will complete the project and report on progress.
    • We will adjust the plan together to make sure it is reasonable. The instructor may ask you to prioritize current work first. If you need custom extensions on multiple projects, the instructor may ask you to check in with your class dean to make sure you are getting the support you need to manage your course load.
    • You are never required to discuss details of your personal circumstances with an instructor to receive an extension, although we are happy to lend an ear. If you choose to share, please note that reporting duties prevent instructors from holding strict confidentiality in all cases.

The above extension mechanisms are subject to the following limitations:

  1. No extension may surpass the last day of Reading Period unless your class dean supports it.
  2. Feedback and grading for work submitted under an extension will be completed as time allows. This may take arbitrarily long, possibly past the end of classes and exams.

Preparation and class activities are generally not subject to these policies, since their timeliness matters for making best use of the associated meeting. However, grading of these components is built with leeway for the assumption that you might occasionally miss out on preparation or class activities. If participation is regularly an issue, please get in touch about accommodations.

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.

Project work can be resubmitted repeatedly in response to feedback. Only the final status of the project work will factor into the course grade. See more detail on the project review process on the project overview page.

Collaboration and Resources

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

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 2021 T4 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

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 2021 T4 students to interpret error messages, subject to the above policy on viewing code.
  • Reference:
    • You may consult course material from CS 301 Spring 2021 T4 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.

Accommodations

Accessibility and Disability

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 during the course, or before the course begins, since some situations can require significant time for review and accommodation design. If you need immediate accommodations, please arrange an appointment 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.

Religious Observance

Students whose religious observances conflict with scheduled course events should contact the instructors in advance to discuss alternative arrangements. You may do this through the Wellesley College Religious Observance Notification system if you prefer.

2020-2021 Circumstances

For many, 2020 and 2021 have been a tougher and more unpredictable years than usual. Please be in touch if you are concerned about the impact of your circumstances on your ability to participate in CS 301 beyond the levels supported by the late policy. I will work with you to determine a reasonable approach for you and CS 301.

Policies on Discrimination, Harassment, and Sexual Misconduct

Wellesley College considers diversity essential to educational excellence, and we are committed to being a community in which each member thrives. The College does not allow discrimination or harassment based on race, color, sex, gender identity or expression, sexual orientation, ethnic or national origin or ancestry, physical or mental disability, pregnancy or any other protected status under applicable local, state or federal law.

If you or someone you know has experienced discrimination or harassment, support is available to you:

  • Confidential reporting: Students can report their experiences to Health Services (781.283.2810); Stone Center Counseling Service (781.283.2839); or Religious and Spiritual Life (781.283.2685). These offices are not required to report allegations of sexual misconduct to the College.
  • Non-confidential reporting:
    • You can let either of your CS 301 instructors know. As faculty members, we are obligated to report allegations of sex-based discrimination to the Nondiscrimination/Title IX Office.
    • You can report directly to the Nondiscrimination/Title IX Office (781.283.2451) to receive support, and to learn more about your options for a response by the College or about reporting to a different institution.
    • You can report to the Wellesley College Police Department (Emergency: 781.283.5555, Non-emergency: 781.283.2121) if you believe a crime has been committed, or if there is an immediate safety risk.