Preparation

Readings and problem sets to prepare in advance of tutorial meetings on the listed date. You do not need polished solutions for the meeting. A rough draft or attempted solution is the goal. Sometimes you will have unsolved problems.

topic Regular Expressions, Finite Automata

← Friday, 1 February - Tuesday, 5 February

Tutorial Assignment: regex.pdf

Preview Slides: regex-outline.pdf
Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, …), Russ Cox.

topic Lexers, Grammars, Top-Down Parsing

← Friday, 8 February - Friday, 15 February

Tutorial Assignment: parse-down.pdf

Refer again as needed to last week’s readings, including Russ Cox’s article.
Fun: We built a simplified URL regex. How about one for email addresses?

topic Bottom-Up Parsing

← Friday, 15 February - Friday, 22 February

Tutorial Assignment: parse-up.pdf

Meetings run on an alternative schedule this week due to Presidents Day and Monday schedule running Tuesday.
Refer again as needed to last week’s readings and exercises, especially on FIRST and FOLLOW.

topic Abstract Syntax Trees, Symbol Tables

← Tuesday, 26 February

Tutorial Assignment: ast-symbol.pdf

Code for exercise 1: tiny-cup.tar.gz
Refer back to our Tiny compiler front end and back end as needed.

topic Scope and Types

← Tuesday, 5 March

Tutorial Assignment: scope-type.pdf

Type Systems, Luca Cardelli.
Lambda calculus reference:
- Lambda calculus on Wikipedia
- A short introduction to the Lambda Calculus, Achim Jung.

topic Type Polymorphism, Information Flow

← Tuesday, 12 March

Tutorial Assignment: polytype.pdf

Type Systems, Luca Cardelli.
On Understanding Types, Data Abstraction, and Polymorphism, Luca Cardell and Peter Wegner
Java Generics Tutorial
Language-Based Information-Flow Security, Andrei Sabelfeld and Andrew C. Myers.
EnerJ: Approximate Data Types for Safe and General Low-Power Computing (technical paper) and EnerJ, the Language of Good-Enough Computing (article for more general audience), Adrian Sampson, et al..

topic Intermediate Code, Method Dispatch

← Tuesday, 19 March

Tutorial Assignment: ir.pdf

topic Code Generation

← Tuesday, 2 April

Tutorial Assignment: codegen.pdf

This week, we will discuss code generation and x86-64 assembly in class.

topic Optimization, Data-Flow Analysis

← Friday, 5 April - Tuesday, 9 April

Tutorial Assignment: opt.pdf

This set of reading and exercises is a little larger than usual, since we did not have meetings this past week. We will preview some parts during class on Friday ahead of tutorial meetings.

topic Data-Flow Analysis Framework

← Friday, 12 April - Tuesday, 16 April

Tutorial Assignment: dataflow.pdf

We will review some from last week or preview some of this material in class on Friday to get a head start.

topic Runtime Systems

← Tuesday, 23 April

Tutorial Assignment: runtime.pdf

topic Program Analysis

← Tuesday, 30 April

This week, we will discuss a few papers. Pick at least 1 static analysis paper and 1 dynamic analysis paper to read. Come to tutorial prepared to ask questions, summarize or critique the program analyses described (and their evaluations). Glean what you can and do a little external searching to learn more about the terms/concepts that seem important.

Static analysis:

KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs. Cristian Cadar, Daniel Dunbar, Dawson Engler. OSDI 2008.
All You Ever Wanted to Know about Dynamic Taint Analysis and Forward Symbolic Execution (but Might Have Been Afraid to Ask). Edward J. Schwartz, Thanassis Avgerinos, David Brumley. Oakland 2010.
Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints. Patrick and Radhia Cousot. POPL 1977.
Dataflow Analysis for Concurrent Programs Using Datarace Detection. Ravi Chugh, et al. PLDI 2008.
Escape Analysis for Java: Theory and Practice. Bruno Blanchet. TOPLAS vol. 25 issue 6, November 2003.
Lecture Notes: Pointer Analysis. Jonathan Aldrich.

Dynamic analysis:

Valgrind: A Framework for Heavyweight Dynamic Binary Instrumentation. Nicholas Nethercote, Julian Seward. PLDI 2007.
Tracking Bad Apples: Reporting the Origin of Null and Undefined Value Errors. Michael Bond, et al. OOPSLA 2007.
FastTrack: Efficient and Precise Dynamic Race Detection. Cormac Flanagan, Stephen N. Freund. PLDI 2009.
Coz: Finding Code that Counts with Causal Profiling. Charlie Curtsinger, Emery D. Berger. SOSP 2015.
TaintDroid: An Information-Flow Tracking System for Realtime Privacy Monitoring on Smartphones. William Enck, et al. TOCS vol. 32, issue 2, June 2014.
Efficient Path Profiling. Thomas Ball, James Larus. MICRO 1996.
Dynamically Discovering Likely Program Invariants to Support Program Evolution. Michael Ernst, et al. ICSE 1999.

Participation

Weekly tutorial meetings are in my office. More info.

Reviews

Tutorial reviews are clear written solutions to a subset of problems from the tutorial assignment selected during each tutorial meeting and submitted after each tutorial meeting.

Reviews are intended to help package up loose ends and capture your understanding of key concepts that we focused on in the tutorial meeting. They should be prepared carefully, but efficiently.
Reviews are evaluated based on the accuracy, and, where relevant, the insightfulness of discussion or elegance of solutions.
Reviews must be typeset with LaTeX to produce a PDF. Diagrams may be produced electronically or by hand, but must be included in the LaTeX PDF document.
After the first tutorial, your review will be due by the end of Friday, to allow time for assistance using LaTeX during drop-in hours if needed.
Thereafter, reviews are due within 24 hours after the end of your tutorial meeting. An extra 24-hour grace period is available with advance notice.

Submitting

Submit a tutorial review by uploading the PDF to GradeScope under your @wellesley.edu ID.

LaTeX

Tutorial reviews must be prepared with LaTeX, to help you learn tools relevant to the field. Here is a silly example tutorial review to demonstrate some common LaTeX features, and Overleaf, one easy way to use LaTeX.

LaTeX is the canonical system for typesetting technical material with a mathematical bent. Most papers (and many books) on programming languages, compilers, runtime systems, and most other fields of CS are prepared with LaTeX.

Getting Started

LaTeX takes a little learning, but these days, tools make it straightforward to get started easily.

Options for running LaTeX:
- Use Overleaf
- Use LaTeX on the lab workstations (your favorite editor + pdflatex)
- Install LaTeX on your own computer
Sample Review Document in Tongue-in-Cheek Style
Learn LaTeX in 30 Minutes (Overleaf)