# Tutorial

# 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

**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

**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

**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

**Tutorial Assignment: ir.pdf**

- Optimizing Dynamically-Typed Object-Oriented Languages With Polymorphic Inline Caches
- Property Caches Revisited

### topic Code Generation

**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

**Tutorial Assignment: runtime.pdf**

### topic Program Analysis

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)

### Reference

- LaTeX Documentation (Overleaf)
- LaTeX WikiBook
- LaTeX Cheatsheet
- All the symbols!
- LaTeX Stack Exchange
- If you use Emacs, try AUCTeX.