Programming Language Design (Fall 2009)

This class is taught by Jay McCarthy.

We meet in TMCB 120 at 8am MWF.

Jay McCarthy’s office hours are 1pm to 4:45pm in 3328 TMCB.

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.

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 Assignments

All assignments are due by 5 PM (Provo time) on the day listed. (Why? No, really.)

Assignments that are late by a second will receive no credit.

Assignment

Team

Out

Help

Due

Code

Points

Weight

Musical Notation

Solo

8/31

9/7

music

1/60

Survey

Solo

8/31

9/4

survey

1/60

Basic Scheme

Solo

8/31

9/1

9/4

basic

245

1/40

Lists and Trees

Solo

9/4

9/8

9/10

lists

188

1/40

Higher-order Functions

Solo

9/11

9/15

9/17

hof

194

1/40

Rudimentary Interpreter

Solo

9/18

9/22

9/25

rinterp

204

1/16

Substitution

One

9/23

9/30

wsubst

1/24

Extended Interpreter

Solo

10/2

10/6

10/9

xinterp

360

1/16

Laziness and Infinite Data

One

10/5

10/6

10/13

lazy

142

1/16

Laziness

One

10/5

10/13

wlazy

1/24

Raw Web Programming

One

10/9

10/16

rawweb

1/40

Language Design

Solo

10/14

10/21

wlang

1/60

Continuations

Two

10/28

11/4

wcont

1/24

PLT Web Programming

Two

10/30

11/3

11/6

pltweb

1/16

Garbage Collectors

Two

11/6

11/10

11/20

gc

1/16

Garbage Collection

Two

11/11

11/18

wgc

1/24

Type Checking

Three

11/18

11/25

wtypec

1/24

Type Checker

Three

11/20

11/24

11/27

typec

332

1/16

Type Inferrer

Three

11/27

12/1

12/4

typei

338

1/16

Type Inference

Three

11/25

12/2

wtypei

1/24

Prolog

Three

12/4

12/8

12/18

prolog

1/16

Final

Solo

final

1/10

Help sessions are held at 3pm to 4:30pm in 1029 TMCB on the day listed.

This schedule will change.

3 Lectures

	Date		Topic		Notes
	8/31		Overview / Scheme: Numbers, Expressions		HtDP 2 (Jay away)
	9/2		Scheme: Designing Programs, Functions		HtDP 3 (Jay away)
	9/4		Scheme: Conditionals		HtDP 4, Jay away
	9/9		Scheme: Structures, Function Templates		HtDP 6
	9/11		Scheme: Lists, Natural Recursion, Recursive Structures		HtDP 9 & 14
	9/14		Scheme: Higher-order Functions		HtDP 20
	9/16		Modeling Languages		PLAI 1
	9/18		Basic Interpreters		PLAI 2
	9/21		Substitution		PLAI 3
	9/23		Functions		PLAI 4
	9/25		Deferring Substitution		PLAI 5
	9/28		Code Review: Rudimentary Interpreter		(Jay away)
	9/30		Code Review: Rudimentary Interpreter		(Jay away)
	10/2		First-class Functions		PLAI 6
	10/5		Laziness		PLAI 7
	10/7		Implementing Laziness		PLAI 8
	10/9		Recursion		PLAI 9
	10/12		Code Review: Extended Interpreter
	10/14		Implementing Recursion		PLAI 10
	10/16		Mutation		PLAI 12-13
	10/19		Mutation, cont.		PLAI 13
	10/21		Variables		PLAI 14
	10/23		Web Programming		PLAI 15-16
	10/26		Web Programming, cont.		PLAI 17
	10/28		Web Programming, cont. and CPS		PLAI 17-18
	10/30		Continuations		PLAI 19
	11/2		Implementating Continuations		PLAI 20
	11/4		Garbage Collection		PLAI 21, Wilson 1 (Jay away)
	11/6		GC: Reference Counting and Mark&Sweep		Wilson 2.1-2.3 (Jay away)
	11/9		GC: Stop&Copy and Generation Collection		Wilson 2.4-4.5
	11/11		GC: Generational, Low-level, New features		Wilson 4.6-9
	11/13		Types		PLAI 24-25
	11/16		Typing Control		PLAI 26
	11/18		Typing Data		PLAI 27
	11/20		Type Soundness		PLAI 28
	11/23		Explicit Polymorphism		PLAI 29
	11/24		Type Inference		PLAI 30
	11/30		Implicit Polymorphism		PLAI 31
	12/2		Prolog		PLAI 32-33
	12/4		Implementing Prolog		PLAI 34
	12/7		Domain-specific Languages		PLAI 35
	12/9		Macros: Compiler Extension		PLAI 36-37
	12/15		Final @ 7am

This schedule may change.

4 Help

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

Did you install PLAI Scheme? Click here for instructions. Having trouble with it? Read its manual.

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

If you are having trouble understanding the basics of Scheme, read the tutorial that comes with DrScheme.

If you are having trouble knowing what library functions will be useful in Scheme, read the following sections of the Guide to PLT Scheme: Scheme 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.

DrScheme 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.plt-scheme.org. Use the search box to find function and syntax documentation. (Everything the search box returns is clickable.)

PLAI Scheme. Most assignments are written with a library specifically designed for this class. It is documented in a separate manual. It is available here. This is where you will find documentation for define-type, type-case, test, test/pred, and test/exn.

5 Turn In Policy

Assignments are to be emailed to jay@cs.byu.edu.

The subject line must be: "BYU - Fall 2009 - CS 330 - x", x is the contents of the “Code” column for the assignment.

Only one email should be sent per team. If more than one is sent, I will grade the oldest one. The message body should be the names of the team members one per line.

You should attach a zip archive of your work. The archive should create a folder with the same name as the “Code” of the assignment. Even assignments with one file should create a folder. Each assignment specifies the names of files.

The only file formats that will be accepted are files produced by DrScheme (for code) and PDFs (for written assignments).

Assignments that do not have the correct format will receive no credit.

For example, if my name were Joseph Smith, I would submit the Rudimentary Interpreter assignment as follows. I would send an email with the subject “BYU - Fall 2009 - CS 330 - rinterp”. The email would contain “Joseph Smith” as the first line. The email would have an attachment named "rinterp.zip". When extracted, it would create a directory named "rinterp" that contained two files, "wae1.ss" and "wae2.ss".

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 PLT Scheme programming language.

For the majority of the course, we will use 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 DrScheme v4.2.1 for many programming assignments. This is already installed on the CS lab computers. (/users/groups/cs330) Do not use a different version of DrScheme!

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

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

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

8 Exams

There is no midterm. There will be a final in class during the scheduled time. It is one question. It isn’t that scary though.

9 Grading

Each assignment is graded with a number between 0 and 1.

9.1 Presentations

A presentation receives a 0 if you do not do it, a 0.5 if you do it poorly, and a 1 if you do it well.

9.2 Written Assignments

Each question on a written assigment receives a 0 if you do not do it, a 0.5 if you do it poorly, and a 1 if you do it well.

The entire written assignment receives the average of these grades.

9.3 Coding Assignments

Every coding assignment has a point target on the table of assignments. The number of points you receive on a coding assignment, as described below, are divided by this point target to produce the assignment’s total grade.

Note: Some assignments may include code, but are not considered coding assignments. These are graded as if they are written assignments where each piece of functionality is a separate question.

– – – –

Every required function that has a purpose statement that fully explains, in a sentence or two, what the function does gives you 5 points.

Every required function that has a contract that specifies its input and output gives you 5 points.

If all non-required functions have purpose statements and contracts, you get 10 points.

Every time you overload lists, rather than creating a new data-type with define-type, you lose 20 points.

Every legitimate test of a required function gives you 2 points. If your code passes this test, you get another 2 points.

Some functionality is important but hard to test in more than one way. This is a called a special test case and is worth the equivalent of 10 test cases.

If all non-required function pass all their legitimate test cases, you get 10 points.

– – – –

Not already knowing Scheme or having learned Scheme with a different style are not excuses for not following these requirements. We are using the coding style from How To Design Programs for this course.

Notice that you get no credit for untested functionality, even if it is correct! We require this to encourage good software development skills, but, more importantly, to force you to show us that you know what your code is supposed to do and that you’re not getting a correct answer by guessing. We will not give full credit to untested functionality, even if it is correct!

You might think that there is no notion of “full” credit, because you are required to come up with your own test cases and there are seemingly infinite numbers of test cases you could include. This is not the case. There are only so many test cases for each assignment that are legitimate. Each assignment gives you an idea about how many that is, without telling you what they are.

Remember that good testing strikes a good balance between testing individual features and testing the program as a whole. It actually tests the program. That means not only executing the program but also checking the output to ensure it is what you expected. And it includes comments to explain the purpose of each test.

10 Your Final Grade

Recall that each assignment is graded with a number between 0 and 1.

The table of assignments has weights for each assignment (and the final).

Each assignment’s grade times its weight and summed is your final numeric grade.

11 Team Work

Most assignments for this class will be done in teams (pairs, with a single triple if enrollment is an odd number). Our assignments tend to be short on code but long on thinking, so this will give you the opportunity to fully discuss a solution with another person. You will work with three different people over the course of the semester.

Programming in teams does not mean each person writes part of the code and the team simply pastes together these contributions. Each person is responsible for every line of code, documentation, etc. turned in. This responsibility extends over written assignments as well. It includes getting or losing points for quality, being able to explain the work, and also incurring penalties in case of plagiarism or other violations. That said, we will sometimes ask you questions individually and, if you are unable to answer them, we may give you less credit than your teammates. In short, working in teams is meant to help you learn material better, not to enable you to do less work than you would have if the assignment had to be done individually.

For team projects, you may not discuss the assignment with a student not on your team.

We recommend that teams develop the software together using pair-programming techniques (of the form preached by Extreme Programming) though this is a suggestion, not a requirement. Pair-programming in a nutshell:

• Both programmers share a single computer, monitor, and keyboard.

• One person is the typist, the other watches what is being typed and critiques it.

• Programmers switch roles at regular intervals. (Note that this is also good for preventing RSI!)

• Both programmers jointly own every single line of code, no matter who typed it.

While this does require that you schedule times to work with your team, we think that pair-programming will increase your productivity and aid you in taking responsibility for all of your code.

You may not work with the same partner on multiple teams.

Once you have selected a partner please inform the course staff. If you are having difficulty finding someone to be your partner, please contact us and we will attempt to match you with another student.

12 Codewalks

We will use codewalks, a common practice at software companies, to evaluate some of your programs. A codewalk is a presentation where you, the programmer, convince us, a jury, of specific properties of your program. You accomplish this by presenting your program and answering questions about it. We are most interested in

• correctness: does it do the right thing?,

• extensibility: how adaptable is it to related tasks?,

• robustness: is it built like a house of cards?, and

• performance: does it avoid poor implementation decisions?.

Each program will receive about 30 minutes of scrutiny. The code you present must the be the same code you turned in electronically. We will not tell you if we will conduct a codewalk for an assignment until after you have turned in a solutions for it. No excuses or exceptions; you read it here.

13 Advice

Here is some advice from past students in the class:

“Go see Jay early when they are stuck on a project. Starts the projects early. Don’t get discouraged!”

“Learn Scheme.”

“Don’t despair. It gets better. If you do the assignments and try to understand them, you will do better than you think you’re doing.”

“Don’t be afraid to ask for help, ’cause Jay is quite willing to answer questions. And turn in assignments early, because you can get your work corrected and resubmit it if you did something wrong.”

“Notes are not so very helpful in most of the class. Focus on understanding first.”

“Go to Jay’s office a lot.”

“Start early and ask good questions.”

“Be prepared to spend far more time on this class than you were expecting to.”

“Start projects earlier and take it from Jay McCarthy!!!”

“Work hard from the beginning of the class and get a head start so you don’t have to figure out Scheme later on when you already have enough new concepts to deal with.”

“Learn to talk to Jay. Go up to his office. He’s unbelievably helpful.”

“Start with Scheme early, and I think using the book more might be useful. I don’t know because I haven’t used it much.”

“Be prepared to sacrifice a lot of time for this class if you really want to understand the topics well, and to do well on the assignments.”

“Learn Scheme as quickly as you can. It’s a huge advantage because not only is it used for almost every programming assignment, but it really grows on you when you know what you’re doing, which makes the course more enjoyable. Give yourself enough time to adequately finish the assignments, and use Jay!”

“Talk to the teacher! Don’t go it alone, you’ll get lost.”