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
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
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
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:
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
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
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.
- 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.
- 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.
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.
Submit a tutorial review by uploading the PDF to GradeScope under your @wellesley.edu ID.
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.
LaTeX takes a little learning, but these days, tools make it straightforward to get started easily.
- Options for running LaTeX:
- Sample Review Document in Tongue-in-Cheek Style
- Learn LaTeX in 30 Minutes (Overleaf)