Welcome to the CS132Spring2011 web

Course Information

• Course Syllabus (pdf)
• HomeworkAssignments

Lecture Slides and Related Material

• Lecture 25: Summary and Suggestions for Further Reading

• Lecture 24: Compiling Functional Languages

• Lecture 23: Type Inference and Unification

• Lecture 22: PEGs and Packrat Parsing
  • Rats
    • A packrat parser generator for Java.
  • The Packrat Parsing and Parsing Expression Grammars Page
    • Includes links to the original papers by Brian Ford, some followup papers, and references to other PEG parser generators.
  • Project Fortress, current home of the Fortress programming language
    • Much material is still only on their old website, such as Fortress by Example and their Blog on their language-design choices.
  • Eric Allen et al., Growing a Syntax
    • Paper on using PEGs to make the syntax of Fortress extensible
    • The Slides for their Talk may be easier to follow.

• Lecture 21: Redundancy Elimination

• Lecture 20: Loop Optimizations
  • Steven S. Muchnick, Advanced Compiler Design and Implementation
    • A great text for all sorts of compiler optimizations (and register allocation, and other advanced topics)

• Lecture 19b: Partial Evaluation
  • Neil Jones, Carsten Gomard, and Peter Sestoft, Partial Evaluation and Automatic Program Generation
    • The best book on Partial Evaluation, available for download now that it is out of print.

• Lecture 19a: Profiling
  • Susan L. Graham et al., gprof: A Call Graph Execution Profiler

• Lecture 18: Basic Optimizations
  • David Goldberg, What Every Computer Scientist Should Know About Floating-Point Arithmetic, 1991.
  • Henry S. Warren Jr., Hacker's Delight, 2002.
    • The best book on low-level bit manipulation (counting bits in a byte, implementing signed operations with unsigned instructions and vice-versa, implementing division with multiplication, shuffling bits, etc.)
    • Chapter 2, “Basics,” is available in PDF from the book's web page.
    • Honnald/Mudd Library has a copy.
  • Donald E. Knuth, The Art of Computer Programming: Combinatorial Algorithms, Part 1, 2011.
    • Includes a section on bit manipulation.

• Lecture 17: Register Allocation
  • Gregory Chaitin, Register Allocation and Spilling via Graph Coloring, 1982.
    • The first full description of graph-coloring register allocation.
  • Preston Briggs, Keith D. Cooper, and Linda Torczon, Improvements to Graph Coloring Register Allocation, 1994.
    • Discusses optimistic coloring (among other things).
  • Lal George and Andrew W. Appel, Iterated Register Coalescing, 1986.
    • The standard in graph-coloring register allocation for many years.
  • Some more recent research approaches
    • Fernando Magno Quintão Pereira and Jens Palsberg, Register Allocation via Coloring of Chordal Graphs, 2005.
    • Fernando Magno Quintão Pereira and Jens Palsberg, Register Allocation after Classical SSA Elimination is NP-Complete, 2006.
    • Fernando Magno Quintão Pereira and Jens Palsberg, Register Allocation by Puzzle Solving, 2008.
    • Fernando Magno Pereira and Jens Palsberg, SSA Elimination after Register Allocation, 2009.

• Lecture 16: Target Code Cleanup and Interference Graphs

• Lecture 15: Function Calls
  • x86 Function Calling Conventions

• Lecture 14: Garbage Collection
  • Paul R. Wilson, Uniprocessor Garbage Collection Techniques Revised and extended version of the paper from class.

• Lecture 13: Activation Records

• Lecture 12: Overloading, Class and Object Representations
  • Stanley B. Lippman, Inside the C++ Object Model, 1996.
    • A very readable book on how C++ compilers can implement constructors, inheritance, mulitple inheritance, virtual inheritance, etc.
  • Alpern et al., Efficient implementation of Java interfaces: Invokeinterface considered harmless, 2001
  • The c++filt command that comes with g++ can do unmangling

% c++filt
__Z3fooPKc
foo(char const*)

__ZNSsD1Ev
std::basic_string<char, std::char_traits<char>, std::allocator<char> >::~basic_string()

__ZNSt6vectorIiSaIiEEC1ERKS1_
std::vector<int, std::allocator<int> >::vector(std::vector<int, std::allocator<int> > const&)

__Z3fooSt6vectorIiSaIiEE
foo(std::vector<int, std::allocator<int> >)

__ZNSt6vectorIiSaIiEED1Ev
std::vector<int, std::allocator<int> >::~vector()

• Lecture 11: Low-Level Representations of Data and Control Flow
  • Scott Meyers, Effective STL, 2001. Item 15 describes several very different approaches to representing string objects in C++.

• Lecture 10: Intermediate Languages and SSA
  • Andrew Appel, SSA Is Functional Programming.
  • John Aycock and Nigel Horspool, Simple Generation of Static Single-Assignment Form

• Lecture 5: Lexer and Parser Generators
  • Alex: A lexical analyser generator for Haskell
    • Documentation
  • Happy: The parser generator for Haskell
    • Documentation
  • flex: The Fast Lexical Analyzer
    • Documentation
  • John Levine, Flex & Bison (amazon)
  • ANTLR
    • Lexical Analysis with ANTLR
    • An ANTLR expression parser/evaluator

• Lecture 4: Bottom-Up Parsing
  • Donald E. Knuth, On the translation of languages from left to right.
    • The first appearance of LR.
  • Dick Grune and Ceriel J.H. Jacobs, Parsing Techniques: A Practical Guide.
    • A well-written book covering all aspects of parsing.
    • First Edition Single PDF.
    • Second Edition PDFs for individual chapters. (Or use this download script on a machine with pdftk installed.)

• Lecture 3: Top-Down Parsing
  • David R. Hanson and Christopher W. Frazier. A Retargetable C Compiler: Design and Implementation (amazon)
    • This book contains the complete sources and explanation for the lcc C compiler, written in a “Literate Programming” style.
    • The entire C language is handled using recursive descent.

• Lecture 2: Lexing
  • Jeffrey Friedl, Mastering Regular Expressions
    • First Edition (online via Blais)
    • Third Edition (amazon)
  • A “regular” expression to check for prime numbers

• Lecture 1: Course Introduction
  • Section 5.8 of the C++ Standard
  • CLOC: Count Lines of Code (perl script)
  • Mail::RFC822::Address: regexp-based address validation
  • CS 351: Defense Against the Dark Arts
  • A few billion lines of code later: using static analysis to find bugs in the real world
  • CSS Compilers: Less: The Dynamic Stylesheet Language and SASS: Style with Attitude
  • LearnPads: automatic tool generation from ad hoc data

Haskell Links (Please add other useful resources!)

• Learn You A Haskell For Great Good
  • Despite the name, the recommended first tutorial.
• haskell.org
  • Lots of resources here
• Haskell Cheat Sheet (pdf)
  • 13 pages of short explanations for Haskell features.
  • Warning: parts are in order of complexity, other parts are alphabetical, and other parts seem random.
• “Yet Another Haskell Tutorial” (pdf)
• Tour of the Haskell Prelude (html, slightly abridged) (pdf)
  • Note: the “Haskell Prelude” is the collection of top-level built-in functions, like ++ and and take and sqrt
  • Warning: a few of the functions listed in this tour are not at top-level by default. E.g., functions like isSpace and toUpper are actually in the Char module, so you'd say Char.isSpace and Char.toUpper.
  • The above Tour is a concise summary, but you can also look at the official definition of the Prelude
• Information on some of the standard modules: List Char
• Information on some of the standard type classes: Eq, Ord, Show (and Read)
• More information can be found in the Haskell 98 Report
• Real World Haskell Free on-line version of the O'Reilly book on Haskell

CS132Spring2011 Web Utilities