Programming Language Design (Fall 2012)

This class is taught by Jay McCarthy. Call him Jay.

We meet in 373 MARB at 10am and 11am MWF.

Jay McCarthy’s office hours are 9am to 4pm, except during classes and lunch, in 3328 TMCB. TAs are across the hall in the Special Weapons Research Lab.

There is a mailing list hosted at Google Groups. Use it to ask non-revealing questions and receive answers, as well as general course announcements. You are responsible for reading the content of this mailing list.

During class, you can use the Public Soundboard to make drops. Feel free to email me suggested drops.

1 Introduction

The fundamental tool of a computer scientist and software engineer is the programming language. Programming languages of all shapes and sizes are found under every rock in computing. There are large, mainstream languages that everyone uses regularly. But, there are also small, domain-specific languages that are like feudal lords: well-known to their subjects, but anonymous in the wider world.

Few of us will design a large mainstream language during our careers, but almost all of us will (need to) design and implement a small language. This design will be implicit and ad-hoc if we’re not educated.

This course will prepare you to understand the design of all languages and to design and implement small ones. In contrast to other courses of this nature, we will not treat programming languages like fish and try to make little boxes for them to fit in. Programming languages are not fish. Instead, we will explore the “periodic table” of languages features and concepts. In particular, this course will not teach you to program in many languages. There is too much noise in that approach that distracts from the real differences.

2 Lectures

Jay will not be present on days marked with a * in the Notes column.

This schedule may change.

3 Assignments

Programming

Writing

Evaluations

Assignments marked with a * are optional, extra credit.

Out dates are suggestions—you may need to start earlier.

This schedule may change.

4 Turn-In and Grading

You will turn in all your assignments via this Web site. It relies on your NetID to log in.

The site also has all grading information: each assignment’s grade, your final grade, etc. Please read this blog post about grading.

The site will not accept any work passed the deadline, instead the assignment will automatically receive a zero.

Some assignments are marked as extra credit. They still have due dates, but are purely optional and are added on top of the rest of your grade. However, you can not receive any extra credit (of any kind) if you do not fill out the assignments listed as "Evaluations".

4.1 Turn-In Workflow

When you do an assignment, you’ll create various files. When you turn in the assignment, you submit these files. If you are turning in source code, you should submit a text file with the actual output of the program. For all types of assignments, only plain-text files in UTF-8 encoding with 80 column lines are accepted with Unix (\n) line endings. If you would like use formatting, please use Markdown.

All files must be turned in by the deadline, or else the assignment is marked as a zero.

After the deadline for an assignment has passed, you have 24 hours to fill out a self-evaluation of the assignment’s correctness. Sharing the self-evaluation quiz is considered cheating and a violation of Your Holy Honor. If the self-evaluation is not completed by the deadline, the assignment is marked as a zero.

After the self-evaluation deadline has passed, you have 24 hours to do a peer-evaluation where you grade another student’s self-evaluation. (Because of this, if you care about the anonymity of your work, do not include any identifying details. This is your responsibility.) If the peer-evaluation is not completed by the deadline, the peer-portion of the assignment is marked as a zero.

Shortly after these deadline have passed, I will check your evaluations and you will receive the assignment grade.

4.2 Grading

Each assignment’s grade is based on the self- and peer-evaluations. 90% from the self and 10% from the peer.

The self grade is based on the idea that it is good for you to understand the correctness and limits of your program. It is computed as a weighted average of each question. Each question’s weight (displayed on the quiz) is multiplied by: 1 if you think you are correct and you are, 0 if you think you are wrong and you are, -0.1 if you think you are correct but you are wrong, and +0.1 if you think you are wrong but you are correct (and I can easily tell.) This punishes bluffing and consoles misunderstanding.

The peer grade is based on how close your grade of your peer matches my grade of your peer. (The more different you are—positive or negative—the fewer points you get.)

Your final grade is a weighted average of each assignment’s grade. The turn-in site has the weights.

4.3 What do self-evaluations ask?

Every program has a set of features that it must provide. For example, in the early assignments, each function is one of these features. However, once we start writing interpreters, each form in the language (arithmetic expressions, conditionals, etc) is its own feature. The set of features is consciously only implicitly specified in the assignment texts. If you have questions or doubts about a specific assignment, feel free to ask.

The self-evaluations basically just ask you to provide evidence that each feature is implemented correctly. In addition, you will be asked to provide evidence of documentation (such as contracts) for all definitions.

In most cases, you can simply use line numbers from your program as evidence. For example, suppose a question is, "Did you implement the launch-the-missiles function correctly?" You might reference line 10 (because that’s where the function is defined), lines 20 through 30 (because that’s where your test cases are), and line 200 (because that’s the line of the output that says "All 42 tests passed!".) You can simply write "L10 L20-L30 L200" rather than a long and verbose paragraph.

The uses of ranges for questions like "Did you have one test case?" and "Did you have a second test case?" is not allowed. You should reference a unique test case in each situation.

In some cases, just a line number isn’t good enough though. For example, suppose the question is, "Does the launch-the-missiles function work correctly with Dunstable as a target?" But you don’t have a test case that directly and obviously targets Dunstable, but you have one that targets Groton, you might say "L30 targets Groton, which is close enough to Dunstable." That is, if you don’t have exactly and simply what is asked, you should probably use English to argue your program is correct anyways.

The word "evidence" is used very deliberately. If you have a correct feature, but fail to provide evidence, you will receive no credit.

For written assignments, the self-evaluation is generally "Do you have the correct answer?"

4.4 Exceptions

In the text above, it repeatedly says "24 hours later" and such. However, nothing is ever due on the weekend (Saturday or Sunday), so sometimes 24 hours is actually 48, when the assignment was due on Friday.

In the case of some assignments, such as the survey, student evaluations, the final, etc, you won’t submit files. Instead you’ll just type out that you did it in the text box and I’ll verify it manually.

The two language papers also have a unique grading arrangment. Collectively, they are worth a fifth of your grade. However, you get decide how to allocate this 20% between the two. (You must make this decision after you receive the grade for the first paper.) If I think you haven’t made a good enough effort on the first paper, then I will automatically split it 10%/10%.

5 Help

My job is to help you. Please ask for help. (But read this section this first.)

Sign up for the Google Group, I may have already answered questions about the assignment.

If you are having trouble understanding the basics of Racket, read the tutorial that comes with DrRacket and maybe Teach Yourself Racket.

If you are having trouble knowing what library functions will be useful in Racket, read the following sections of the Guide to Racket: Racket Essentials, Symbols, and Pairs and Lists. Late in the course you will find Continuations, Web Interaction, and Pattern-Based Syntax Matching useful.

If you are having trouble knowing where to start, use the design recipe from How to Design Programs.

DrRacket comes with an extensive manual and help system. The documentation is available by clicking the Help|Help Desk menu item. This will open up a browser window to your local copy of http://docs.racket-lang.org. Use the search box to find function and syntax documentation. (Everything the search box returns is clickable.)

PLAI. Most assignments are written with a library specifically designed for this class. It is documented in a separate manual that is available by clicking the plai in the #lang instructions for each assignment. Try it:

#lang plai

6 Readings

In the beginning of the course, we will use the free online textbook How to Design Programs (HtDP), by Matthias Felleisen, Robert Bruce Findler, Matthew Flatt, and Shriram Krishnamurthi, to introduce the Racket programming language.

For the majority of the course, we will use the first edition of the free online textbook Programming Languages: Application and Interpretation (PLAI), by Shriram Krishnamurthi. Eventually we will look at Paul Wilson’s survey of Garbage Collection methods later in the course.

We will not be using the textbook in the traditional way. Think of the textbook as your lecture notes. Don’t read it before a class, but refer to it afterwards. The book is superb, so you won’t need to distract yourself from the discussion by taking copious notes. (You may want to take note of your ideas and insights, but the content of the lecture will be in the textbook.)

7 Software

We will use DrRacket v5.3 (or higher) for many programming assignments. Do not use an older version of DrRacket!

We will use three language extensions: Basic Student, Intermediate Student with Lambda, and PLAI.

To use Basic Student: Open DrRacket. From the Language menu, click Choose Language.... Expand How to Design Programs. Select Basic Student. Click OK.

To use Intermediate Student with lambda: Open DrRacket. From the Language menu, click Choose Language.... Expand How to Design Programs. Select Intermediate Student with Lambda. Click OK.

To use PLAI: Open DrRacket. From the Language menu, click Choose Language.... Select the Determine language from source. Type this at the beginning of your program:

#lang plai