High-level programming languages like Python make programming a breeze, but how do they work? There's a big gap between Python and machine instructions for modern computers. Learn how to translate Python programs all the way to Intel x86 assembly language.
Most compiler courses teach one phase of the compiler at a time, such as parsing, semantic analysis, and register allocation. The problem with that approach is it is difficult to understand how the whole compiler fits together and why each phase is designed the way it is. Instead, each week we implement a successively larger subset of the Python language. The very first subset is a tiny language of arithmetic statements, and by the time we are done the language includes objects, inheritance, and first-class functions.
Prerequisites: Fluency in at least one programming language (Java, C, C++, Python, etc.). Students will do a lot of programming in Python, but prior knowledge of Python is not required. The course will start with a crash course on Python and Python is one of the easiest languages to learn. Prior knowledge of an assembly language helps, but is not required.
Distance Learning: This course is also offered through the CAETE program.
Time: MWF 9:00am-9:50am
Location: ECCS 1B28
Office hours: M 3:30-4:30pm, W 10-11am, F 11am-12 in ECOT 342, and by appointment.
Course notes: pdf
Lecture scribbles: zip
- Modern Compiler Implementation in Java 2nd edition by Andrew W. Appel (The book is also available in C and ML.)
- Compilers: Principles, Techniques, and Tools 2nd edition by Aho, Lam, Sethi, and Ullman
- Python in a Nutshell by Alex Martelli
Grading: participation 5%, homework 20%, quizzes 20%, final project 10%, midterm exam 20%, final exam 25%.
Workload: up to 12 hours of out-of-class work per week.
Quizzes for distance students (CAETE): The questions for quiz will be emailed to you on the morning of the posted date of the quiz and you will email the answers back to Jeremy by midnight of the same day. The quizzes are closed book and should be completed alone, just use your brain and only use the computer to type in your answers. For example, do not use the Python interpreter on your computer to help you answer the quiz.
- Integers and variables, due 9/7.
- Parsing with PLY (Python Lex-Yacc), due 9/18.
- Register allocation, due 9/28.
- Polymorphism and heap allocation, due 10/12.
- Functions, due 10/26.
- Objects and classes, due 11/9.
- Final project proposal due 11/16, instructions.
- Final project, first draft of write-up due 11/30.
- Final project, slides due 12/3.
Presentation schedule for the week of 12/10:
- Monday, 9:00-9:15, Andy Sayler and co.
- Monday, 9:15-9:30, Bharath Hegde and co.
- Monday, 9:30-9:45, Jerome Biotidara and co.
- Wednesday, 9:00-9:10, Anthony Cantor
- Wednesday, 9:10-9:25, Bharadway Dantu and co.
- Wednesday, 9:25-9:40, Chris Poulton and co.
- Wednesday, 9:40-9:50, Krishna
- Friday, 9:00-9:15, Chris Bubernak and co.
- Friday, 9:15-9:30, Krithika Parthan and co.
- Friday, 9:30-9:45, Sean Wiese and co.
- Friday, 9:45-9:55, Scott Pledger and co.
- Final project, final write-up and compiler due 12/14.
Instructions for turning in assignments: Assignments are due by 6am of the due date. Upload your compiler using the web-form at the URL announced on Piazza.
Quizzes (given in class):
- Midterm: in class on Oct. 29, solution
- Final: Dec. 17, 1:30pm-4:00pm, ECCS 1B28
Grades are posted here.
- Please send Jeremy a secret code word so that you can identify your grades.
- Assignments are graded on a 10 point scale.
- Quizzes are graded on a 10 point scale.
- Exams are graded on a 100 point scale.
- benchmark programs
- Garbage collector
- Uniprocessor Garbage Collection Techniques by Wilson.
- Chapter 13 of Modern Compiler Implementation in Java by Appel and Palsberg.
- Don't stop the BiBOP by Dybvig, Eby, and Bruggeman.
- Procedure inlining
- Fast and effective procedure inlining by Waddell and Dybvig.
- Type specialization
- Assignments 4 and 5 (a) from ECEN 4553 Fall 2008
- Chapter 17, Dataflow Analysis, of Modern Compiler Implementation in Java by Appel and Palsberg.
- Customization: optimizing compiler technology for SELF by Chambers and Ungar.
- Iterative type analysis and extended message splitting; optimizing dynamically-typed object-oriented programs. By Chambers and Ungar.
- A unified approach to global program optimization. By Kildall.
- Instruction Selection, Instruction Scheduling
- Chapter 9 and 20 of Modern Compiler Implementation in Java by Appel and Palsberg.
- Static Single-Assignment Form (SSA), Dead-Code Elimination, Constant Propagation,
- Assignment 5(b) from ECEN 4553 Fall 2008
- Chapter 19 of Modern Compiler Implementation in Java by Appel and Palsberg.
- Detecting equality of variables in programs. By Alpern, Wegman, and Zadeck.
- Single-pass generation of static single-assignment form for structured languages. By Brandis and Mossenbock.
- Register allocation
- Live Range Splitting in a Graph Coloring Register Allocator by Cooper and Simpson.
- The Priority-Based Coloring Approach to Register Allocation by Chow and Hennessy.
- Code scheduling and register allocation in large basic blocks by Goodman and Hsu.
- An implementation of a priority queue with update in Python: priority_queue.py, heap.py.
- Paper on live range splitting in register allocation.
- Runtime C functions: runtime.h, runtime.c, hashtable.h, hashtable.c, hashtable_itr.h, hashtable_itr.c, hashtable_utility.h, hashtable_utility.c, hashtable_private.h.
- Video about pair programming.
- Simple diagram of x86 architecture pdf
- Script to automate regression testing (needs to be updated for Fall 2012): run_tests.py and colors.py
- Examples from Python crash course.
- Printing floating point numbers in C, mimicking Python
- Python Lex-Yacc (PLY)
- IA32 Assembly for Compiler Writers
- Debugger for Python: PyDev is a plug-in for Eclipse
- Intel Manuals
Final project ideas and resources: