CSC 431, Spring 2010

Schedule/Homeworks

This is a compilers class. In this class, you will build a compiler.

The benefits of building a compiler are manyfold; here are two important ones. First, you get a much better understanding of how to translate higher level languages into assembly language. Second, you get to build and maintain a ball of code that’s somewhat larger than you handle in many other courses (between 2K and 10K lines of code, depending on your language of implementation).

As a result, this course lives at the intersection of Programming Languages, Architecture, and Software Engineering. With luck, you’ll learn something about each of these.

1 Outcomes

2 Prerequisites

Students taking this course must be able to design and implement small programs (~ 1 KLOC) efficiently. Students must have a basic understanding of mathematics.

3 Names, Times, Locations

Google Calendar:

See my Cal Poly Home Page for my calendar, including times & locations of labs, lectures, and office hours. You can add it to your calendar, if that makes your life easier.

3.1 Instructor

• name: John Clements

• telephone number: 756-6528

• e-mail address: aoeuclements @ brinckerhoff.org

• office hours: see my calendar

3.2 Lecture & Lab

Section 01/02:

• Lecture: 14:00-15:00, MWF, room 14-250

• Lab: 15:00-16:00, MWF, room 014-302

3.3 Web Page

This is the course web page, its link is http://www.csc.calpoly.edu/~clements/csc431-sp10.

4 Readings

This course uses a textbook. I’m sorry to report that it’s your classic made-from-dead-trees/costs-lots-of-money kind of textbook. The textbook is by Keith Cooper and Linda Torczon, and it’s called Engineering a Compiler.

5 Communication

There is a google group, csc431-sp10 . You will need to join this group. You can request this by visiting the url

http://groups.google.com/group/csc431-sp10

I will use this group to tell you about important changes and updates to the assignments. However, it will also be a forum for you to help each other. As long as you’re not posting code, I strongly encourage you to ask questions and to respond to questions on the group. For this reason, I also require you to sign up in individual e-mail mode, and not in digest mode. Finally, you need to make sure that your postings are professional and civil. Imagine that your boss is reading them (I am).

6 Teams

This class allows teams of size two. You are not required to work with a partner, but I strongly encourage it. Since your work through the quarter will all be on a single project, you will be working with the same partner for the duration of the class, though it is possible to change partners after the first project.

7 Assignments/Milestones

The work in this class will consist principally of one quarter-long development project (hint: it’ll be a compiler). The first milestone will be a CSC-430-style implementation of the target language, to get the ball rolling. Subsequent milestones will consist of in-lab demonstrations and/or public code and design reviews.

Unless otherwise specified, all assignments are due at 11:00 PM.

8 Handin

This class will use a central subversion repository, hosted on li128-9.members.linode.com. We will use this repository to synchronize all work in the class. That is: in order to hand in your code, just make sure that it’s in the repository.

If you’ve never used revision control: yikes! Okay, here’s a brief summary: systems like subversion (and git and...) "keep track of" a directory or set of directories on your machine by tracking all changes to these directories and allowing you to synchronize these directories with other users on other machines. Revision control systems allow you to "roll back" any accidental or unwanted changes ("oh dear, that refactoring isn’t going to work out after all") and to make sure that you and the others you’re working with are both working on the same set of sources. That’s an absurdly brief overview, and should give you enough to google on.

Your login ids will be the same as your calpoly.edu login ids. I will mail your repository ids to you separately. The repository is organized like this:

/

- public

- clements

- bogusman

- nonexistiamus

...

- private

- clements

- bogusman

- nonexistiamus

...

That is, each member of the class has a path in both public and private. The public paths may be used to share test cases, and the private paths are for your own code. Everyone has read access to the entire public tree, and each person has write access to his or her subdirectory of the public tree. Each person has read and write access to his or her subdirectory of the private tree.

In order to get you started, I’m going to provide a number of command-line examples of how you might check out your own portion of the tree, add a directory, commit it, and update to see whether anyone else has made any other changes.

8.1 Checking Out for the first time

Checking out your own portions of the repository, assuming your name is glognar (N.B.: watch out for wrapped lines in the below):

cd ~

mkdir csc431

cd 431

svn co http://li129-8.members.linode.com/csc431-repository/public public

<enter user name and password; if svn guesses user id wrong, hit return for a chance to enter the right one.>

svn co http://li129-8.members.linode.com/csc431-repository/private/glognar/ private/glognar

Obviously, you can choose your own parent path, but I suggest keeping the other bits in the same places relative to each other, so that you directory structure mirrors that on the build machine. If you want to refer to code that lives in the public repository, you can then use a path like "../../public/clements/whatever".

8.2 Adding a Directory

cd private/glognar

mkdir foo

svn add foo

svn commit -m "I added foo" .

8.3 Updating

svn up .

8.4 Creating a Branch to Hand in

Handin will consist of creating a branch (a.k.a. subdirectory) with a specified name. For standalone assignments, you can simply create this directory and do the work there. Here’s how you might do this for Assignment 1:

cd private/glognar

mkdir Assignment1

svn add Assignment1

svn commit -m "created new dir" .

Alternatively, if a particular assignment is just a step in a larger project (say, building a compiler), you’ll want to create a branch by copying the current state of the project into the named subdirectory. So, if you’re working in a subdirectory called "compiler", you could branch off an Assignment 1 handin like this:

cd private/glognar

svn cp compiler Assignment1

svn commit -m "created branch for Assignment1"

Keep in mind that making changes to that Assignment1 directory’s files would probably be a bad idea, because those changes would not appear along the main trunk.

That’s the briefest of introductions. Please let me know if I’ve made any mistakes, or if you have references to particularly helpful introductions to subversion.

8.5 Working with a partner

You and your partner should use the same repository subtree. After all, one of the most important advantanges of version control is that you can safely cooperate on the same source tree.

To make this work, you should designate one pair member’s repository tree as the one in which you’ll work, and both partners should share the password assigned to that subtree. Do all of the work in that set of trees (e.g., /public/glognar and /private/glognar).

9 Computing Environment

In our search for simplicity, I’ve decided that we’re all going to use the same language this time around. That language will be F#, a nifty Microsoft language based on OCAML, but with a bunch of really interesting extensions.

The advantage of this setup is that I can actually give you a well-defined framework for your compiler; in particular, I can define the data structures for you. This should rather dramatically decrease the amount of "originality" required on your part. For most of you, I think this will make your lives simpler and more straightforward.

The course will share a single centralized subversion server (I hope it doesn’t go down). The repository consists of two trees, the public and the private tree. Each student has a subdirectory of each one, and only that student (and his or her team-mates) may write to that tree. The public tree is world-readable, the private tree is not.

10 Code Walks

Each team will be required to conduct one code walk. During a code walk, the team must present its code in a top-down way that will allow everyone in the room to understand the design of the code and the role of each portion of the code.

Each presentation should begin with a summary of the data structures that the project uses. Yes, even though they’re the same for everyone.

Next, the presentation should describe the functions associated with the data structures.

Next, the presentation should show which code is associated with each function.

Finally, the presentation should provide illustrative fragments of code. During this portion of the code walk, it is crucial that the presenters have the entire code available, so that audience members may look at different parts of the code as they wish.

Here’s the number one most popular way to blow your code walk: stare at the screen and read your code. Don’t do it! The organization should come from you, not from your code.

10.1 Grading Methods and Expectations

I will grade submitted code by running test suites of my own devising and by running your test suites and by reading your code.

I will grade your demonstrations and code and design reviews based on the success of the demonstrated code and upon the delivery of the presentation.

Naturally, all grades contain an element of subjectivity.

11 Attendance Requirements

I do not formally state attendance requirements.

12 Final Project Submission

You must submit your final project at the date specified by the schedule. As stated above, along with any code you submit you must also include a Makefile whose default target builds the code, and a README that describes how to run the project against your tests.

13 Final Paper

Each group will submit a paper detailing the design and implementation of their compiler project. This paper must describe the data structures used, the solution architecture, and the algorithms implemented. It should also include a table showing each file in your solution, how many lines it is, and what its function is.

14 Cheating

In the programming assignments, you may not copy another team’s code (including test cases and pseudo-code). You may not share code with other teams in the class. That is, you may not allow another team to see the code you write for the class, deliberately or through obvious negligence.

Any code you submit that is attributable to another source must be clearly identified as such. In general, you will not receive credit for code that your team did not write.

I will use an automated tool to compare student submissions and identify cheating.

Students believed to be cheating–that is, both parties involved in the transfer of code–will receive a failing grade in the class.

15 Exams

There will be a final exam in the class, at the place and time chosen by the registrar. It will be closed-book, and closed-note. No electronic devices, including cell phones or mp3 players, will be permitted during the exams.

Make-up or early exams will not be given except in the most extreme situations. If you must miss an exam due to extreme illness, etc., contact the instructor (by phone or by e-mail) or leave a message with the Department of Computer Science office (805-756-2824) before the exam. Be sure to leave both the reason for missing the exam and some way to reach you.

16 Grades

Grades will be determined by performance on programming projects, the exams, and class interaction. A small fraction of the grade is determined by the instructor’s whim.

The breakdown of the grade is as follows:

• Assignments/Milestones: 35%

• Final Submission: 45%

• Exam: 15%

• Instructor’s Whim: 5%