Course Overview

Final Grades

Course Learning Objectives
This course examines the fundamental theory and practice of implementing today's programming languages. The overall learning objective is for students to emerge with a good appreciation for the implementation issues and strategies behind making programs written in general purpose, domain-specific, or scripting languages execute correctly on a target machine. A major part of the course is the practical experience of implementing various phases of language implementation. Students learn translation methodology that is useful in many other situations in addition to compilation, including command interpreters, report-generating systems, programmable applications, configuration file handling, preprocessors, debuggers, static program analysis tools, testing tools, virtual machines, integrated development environments, and many other software engineering tools.

You should register for CISC 471 if you are curious about:

• the inner workings of a basic compiler
• the implementation of programming language features
• the answers to many of your questions about how programming languages work
• the issues in gaining good performance from a high level language program on a particular target architecture

AND you have the proper prerequisites: CISC 260 and CISC 303. Note: There is no assumption of previous coursework in compilers or programming languages.

Content

• Dealing with the form of programs:
  • Specification of a language's lexical and syntactic components
  • Scanning (lexical analysis) and automatic scanner generation (e.g., lex, flex, JLex)
  • Parsing (syntax analysis) and automatic parser generation (e.g., yacc, bison, JavaCup)
• From form to meaning in a portable way:
  • Intermediate code representations
  • Semantic analysis and intermediate code generation
  • Handling scope through symbol table creation and management
• Managing the runtime environment:
  • Implementing program flow through the runtime stack
  • Managing storage based on object lifetimes
  • Specifics to implementing object-oriented languages
  • Automatic garbage collection strategies

The Learning Process and Skills Development
Classtime will be devoted to discussions about programming language design choices and the associated challenges and strategies for implementing the features. Students will be actively involved in both individual and group projects to gain experience with the state-of-the-art tools for implementing programming languages. Each student will learn to automatically generate scanners and parsers, build analyzers that traverse intermediate representations for different program analysis and code instrumentation tasks, generate an alternate code representation, and explore different garbage collection techniques.

Why Am I teaching this course?

I have been conducting research in compilers for a long time - over 20 years. My dissertation was in incremental compilation - the problem of reusing results from previous compilations of the same program in future compilations. We developed techniques to examine a programmer's edits and redo the compilation work to deal only with the edits, without redoing all of the compilation from scratch. In particular, my dissertation focused on the problem of how to perform incremental compilation when the compiler performs optimizing transformations to improve the program's performance. More recently, my research group has made contributions in optimizations of parallel programs to automatically overlap communication and computation, compiler techniques to integrate register allocation and instruction scheduling for better overall program performance, using dynamic compilers for solving software engineering problems, and developing compilation-based techniques for providing mobile code integrity.

Course Requirements

Readings

Required Textbook
Programming Languages Pragmatics, Michael L. Scott, Morgan Kaufmann Publishers, 2005, ISBN 0126339511.

Supplemental
John Levine, lex & yacc, O'Reilly and Associates, Inc., 1992.

Compilers: Principles, Techniques and Tools (Dragon book), Aho, Lam, Sethi and Ullman, Addison-Wesley, 2006, ISBN 0321486811.

Engineering a Compiler (Ark book), Keith D. Cooper, Linda Torczon, Morgan Kaufman Publishers, 2003, ISBN 1-55860-698-X.

Modern Compiler Implementation in Java (Tiger book), A.W. Appel, Cambridge University Press, 1998, ISBN 0-52158-388-8.

Assignments and Grading

Your grade will be based on your performance in the various activities in the course. Some of the activities will be done in groups, and some will be done individually. There will be two in-class examinations. The first exam (at midterm time) will concentrate on the first half of the course, while the second exam (during final exam week) will concentrate on the second half of the course. The relative weights of the components of the grade will be approximately:

• (15%) Project 1: Inventing and Implementing a New Drawing Language
• (15%) Project 2: Syntax-directed iloc code generator
• (12%) Project 3: Register allocator
• (5%) Weekly (every Tuesday) Quizzes
• (15%) Homeworks
  • (10%) Short paper/pencil homework problems
  • (2%) Case study of a publicly available compiler architecture
  • (3%) Empirical investigation of compiler optimization flags
• (3%) Class participation - taking part in class discussions, activites,or distinguished speaker seminars listed on syllabus. All of these efforts count toward the class participation grade.
• (17%) First Exam - first half of course
• (18%) Second Exam - second half of course

Weekly Quizzes

The objectives of the weekly quizzes are: (1) to reinforce the concepts in recent classes and readings, (2) to assess individual student understanding of recent topics/skills, and (3) to encourage class preparation. Each quiz will take about 5 minutes at the beginning of class. It will contain 1-2 short questions based on recent class discussions and readings. There will be a quiz EVERY TUESDAY, unless announced otherwise. The quiz will focus on the previous week's classroom and reading topics. Each student's lowest two quiz grades will not be counted toward their final grade. Thus, there WILL BE NO MAKEUP quizzes. Any missed quizzes will be counted as zeros in the grading scheme above. Thus, if you miss more than two quizzes, all additional missed quizzes and all other quiz grades will be counted toward your final grade.

Calendar

Date	Topic	Readings for Today	Assignment
Tu 2/12	Overview of a Compiler and its Context	pgs 3-22
W 2/13	SEMINAR: Using Software Engineering Technology to Reduce Medical Errors,Lori Clarke, UMass
Th 2/14	Overview of compiler phases	pgs 22-32
Tu 2/19	Scanning: lex specs	pgs 37-41/flex docs	Project 1 OUT
W 2/20	SEMINAR: Margaret Martonosi, Princeton
Th 2/21	Scanning: the process	pgs 46-61	Project 1 D0 due
F 2/22	CS Research Day 10am-5pm
M 2/25	LAST DAY TO DROP without W/charge		Project 1 D1 due
Tu 2/26	Critique/discussion: lex specs Error Checking	Flex docs
Th 2/28	Parsing: Specifying syntax with CFGs	pgs 42-46	2/29: Project 1 D2 due extended to 3/4 8am
Tu 3/4	Parsing: Bison specs	Bison docs
W 3/5	SEMINAR: Tools and Approaches for Large-scale Parallel Computing, Rusty Lusk, Argonne National Lab
Th 3/6	Parsing: Adding actions	Bison docs	3/7 Project 1 D3 due extended to 3/10 8 am
Tu 3/11	Parsing:top down	pgs 61-70
Th 3/13	Parsing: top down	pgs 61-70	3/17: Project 1 D4 due Extended to 3/21
Tu 3/18	Parsing: bottom up	pgs 80-92
Th 3/20	Parsing: bottom up	pgs 80-92	3/21: Project 1 D5 due Extended to 3/25
Tu 3/25	Semantic Analysis Attribute Grammars	pgs 161-186
Th 3/27	Attribute Grammars	pgs 161-186	3/28: Project 1 D6 due
4/1	SPRING BREAK
4/3	SPRING BREAK
Tu 4/8	Review Game		Symbol Table homework OUT
Th 4/10	FIRST EXAM	Study Guide Review Game Questions
Tu 4/15	Scoping and the Symbol Tables	pgs 114-135	Compiler project 2 out
Th 4/17	Discussion of symbol table homeworks		Symbol Table homework due
Tu 4/22	Object Lifetimes and Storage Management: The Runtime Stack	pgs 106-110: 408-409; 417-432Slides
Th 4/24	Optimizing an Optimizer	Cavazos's Slides
Tu 4/29	The Heap and Garbage Collection	pgs 111-114; handout; Garbage Collection arti cle	4/30: Project 2 deliverable 1 due Compiler case study OUT
Th 5/1	Implementing OOP Languages: Inheritance, Polymorphism	pgs 502-509
Tu 5/6	Register allocation	cd 248	Project 2 deliverable 2 due midnight
Th 5/8	Case Studies of Publicly Available Compilers Open64: Ben R, Cliff SUIF: Peter W, Peter H Phoenix: Joel LLVM: Matt SableCC: Ben B., Brennen Soot: Joe Trimaran: Trevor, Jeff Zephyr: Shannon abc: Zak Flex:Mee Scale:Doug, Rosh	Slides Directory	Compiler case study DUE
Tu 5/13	Building an optimizing compiler for parallel programs		Optimization Experiment OUT
W 5/14	SEMINAR: Saving the Digital World, Fran Berman, San Diego Supercomputer Center
Th 5/15	Using Dynamic Compilers for Software Testing
Tu 5/20	SECOND EXAM	Study Guide	Optimization Experiment DUE Friday 5/23 2 pm
Th 5/22	READING DAY
Finals Week

How to Increase your Learning in CISC 471

• Read the textbook. At least read the chapter as each new topic is covered in class. Use the textbook as a reference during projects and for vocabulary and filling in the details of concepts covered in class and projects. The readings in this course are critical to your active participation in class meetings. Part of your grade is based on class participation. Besides, you should not expect to gain all understanding of the concepts from passively listening in the class periods alone.
• Speak up in class. This course is not meant to be a passive learning course, as it has been shown that the best learning occurs when the learner is an active participant, not a passive listener. Besides, classes are much more enjoyable when the audience actively participates!
• Take an active role in your group projects. Ask your group members to explain concepts you do not clearly understand, and share ideas among the group members. Meet regularly with your group.
• Form an informal study group outside of class. Compare your notes from class, work together on group projects, and discuss concepts you find unclear.
• Seek help if you start to feel lost, ASAP. Take advantage of instructor and TA office hours. Ask questions via email.

Course Policies

The due dates are to be taken seriously and you should not expect them to be extended. The pace of work is implicit in the due dates and necessary if you expect to finish by the end of the semester. Homeworks to be graded should be turned in at the start of class on the specified due date. Programming assignments should be dated before 11:59 PM on the due date. NO late programs or homeworks will be accepted FOR FULL CREDIT without discussion with me prior to the due date. If you can not reach me, leave a message on my voicemail. All other assignments not delivered by the due date are considered late.

My philosophy on late assignments is: (1) Everyone should try their best to complete all assignments by the specified due date. (2) People who work conscientiously to make the deadlines should be rewarded for their promptness and sacrifice of sleep. Thus, allowing others to hand in late assignments without some penalty is not fair to these people. However, there are various circumstances that may prevent you from completing an assignment by the due date. Allowing no late assignments would not give you much incentive to continue to work on the assignment, which is a major source of learning in this course. Thus, I believe late assignments are better than no assignment.

Late assignments will be penalized 5% off the total possible points if turned in within the first 24-hour period after the specified due date and time, and 5% per 24-hour period (or fraction of a day) (including weekends) after that time, up to a week after the due date. Late assignments will be accepted with penalty up to one week after the due date. Assignments submitted at any later time without an approved excuse will not be accepted. It is up to you to determine the version of your assignment to be graded. You must weigh the late penalty against the completeness of your assignment.

Regrading Policy:

If you are dissatisfied with a grade on a homework, programming assignment, or exam, you should consult the instructor directly within a week of the day the graded assignment was returned to you. No regrade requests will be considered after this week period.

Posting Grades:

With your permission, grades will be posted electronically via a link on the course web site. You will need to give me a secret code name for this posting in order to keep your grade posting anonymous. If no name is given, I will assume you do not want your grades to appear. Questions about accuracy of recorded grades should be addressed to me.

Policy on Academic Dishonesty

You will be told specifically which assignments are to be done collaboratively in groups, and which ones should be done individually without collaboration. For individual assignments, you should be directing your questions to the instructor, not to other students, unless the question is a clarification question. Any evidence of collaboration other than this kind will be handled as stated in the Official Student Handbook of the University of Delaware. You should not be using or examining any program code used for projects for this course in any prior instantiations of this course. If you are in doubt regarding the requirements, please consult with me before you complete any requirement of this course.

Collaboration Policy:

General philosophy

This course requires a significant amount of programming. You are allowed to choose a programming partner for some or all of the programming assignments. This document should make it very clear what is and what isn't considered acceptable collaboration, so there is no ambiguity.

The general premise of this policy is that your submissions must be your own independent and original work. You should not give or receive any aid which makes the assigned tasks significantly easier. Discussion and help is allowed among students, but it is expected that you document any significant help that you receive. On my part, I will treat you with trust and will protect the honorable student's interests by investigating and prosecuting dishonorable behavior.

Collaboration on coding projects

"Your code is like your boyfriend or girlfriend. It's okay to talk about it on an abstract, high level. But you don't want to go into the specific details, and you certainly don't want to share."

- Pascal Van Hentenryck, Professor of CS, Brown University, 1997

For the purposes of the collaboration policy, students choosing to work with a partner are effectively considered as one entity, and are freely allowed to exchange, help, design, and code with one other, but the guidelines below apply outside the partnership (neither of you should be debugging, sharing code, etc. with other people or teams). There are also some specific rules that apply within the partnership.

Things that are always allowed

These things are encouraged and allowed at all times for all students.

• Discussing material covered in lecture or handouts.
• Discussing the requirements of an assignment.
• Discussing features of any programming language (including the one for which we are writing a compiler).
• Discussing how to use the tools or development environments.
• Discussing general techniques of coding or debugging.
• Any discussion between the student and a TA, or me. You are welcome to discuss any and all ideas, design, code, debugging, and details with the course staff (TA and instructor). They are the best folks to talk to because they are knowledgeable about all the material and know how to help you without giving away the farm. They also have the authority to give you definitive answers to your questions.

Collaboration that is allowed if documented

Two students engaging in a more detailed discussion of the project specifics can cross into the area of collaboration that is acceptable only if documented. I require that you include the name of those whom you received specific assistance from and properly credit their contribution, as you would cite a reference in a research paper. Some examples:

• Discussing the design of the project. Design is a crucial part of the programming process, and discussion can be valuable, but you should take care to document any design input you got from others.
• Getting help from another student in order to debug your code. You should credit their assistance.
• Sharing advice about testing. For example, if the team next to you tells you about some lesson learned ("our program didn't handle the case where the input file didn't end with a newline") that you then use to improve your program's robustness, you should credit them for providing you with that insight.

Collaboration that is NOT allowed

Basically, the rule is that you should be handing in code which represents your original, independent work. It should not be based on, influenced by, or copied from anyone else's.

• Copying code. This is the most blatant violation. You should not be copying anyone else's work. You should also not allow anyone else to copy yours. You should keep your work secure (restrict access on the filesystem, don't leave printouts lying around, etc.)
• Using work from past semesters. Using someone's work or solutions from a previous semester is an obvious violation.
• Looking for this project on the Internet and copying the code.
• Studying someone else's code. You should not be reading anyone else's code whether it is on the screen or written out by hand.
• Debugging someone else's code. Debugging along with someone makes it too easy to look over their code and allow (sometimes unintended) code-copying. Describing to someone a problem and asking for advice on how to track it down is okay, but you should do the actual debugging yourself.

Closing thoughts

Above all you should use your common sense. If you suspect that what you are about to do is a violation, play it safe and ask a staff member first rather than take risks with your academic career.

Cheating is taken very seriously in this course. Please do your part in maintaining a community where academic work is done with a high standard of integrity!

Some parts of this document are based on a similar collaboration policy for CS courses at Brown, Drexel, and Stanford.