On this page:
1 Introduction
2 Lectures
3 Assignments
4 Turn-In and Grading
4.1 Turn-In Workflow
4.2 Grading
4.3 What do self-evaluations ask?
4.4 Exceptions
5 Help
6 Readings
7 Software

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

 

Day

 

Date

 

Topic

 

Links

 

Notes

 

1

 

8/27

 

Overview / Modeling Langauges / Racket: Numbers, Symbols, Expressions, Check Expect

 

1 2

 

PLAI 1 / HtDP 2

 

2

 

8/29

 

Racket: Designing Programs, Functions, Conditionals, Structures, Lists, Natural Recursion

 

1 2

 

HtDP 3-6, 9

 

3

 

8/31

 

Racket: Recursive Structures / Higher-order Functions

 

1 2

 

HtDP 14 & 20

 

4

 

9/5

 

Basic Interpreters

 

1 2

 

PLAI 2

 

5

 

9/7

 

Code Review: Lists and Trees and Higher-order Functions

 

 

 

6

 

9/10

 

Substitution

 

1 2

 

PLAI 3

 

7

 

9/12

 

Functions

 

1 2

 

PLAI 4

 

8

 

9/14

 

Code Review: Rudimentary Interpreter

 

 

 

9

 

9/17

 

Deferring Substitution

 

1 2

 

PLAI 5

 

10

 

9/19

 

First-class Functions

 

1 2

 

PLAI 6

 

11

 

9/21

 

Laziness

 

1 2

 

PLAI 7

 

12

 

9/24

 

Implementing Laziness

 

1 2

 

PLAI 8

 

13

 

9/26

 

Code Review: Extended Interpreter

 

 

 

14

 

9/28

 

Recursion

 

1 2

 

PLAI 9-10

 

15

 

10/1

 

Representation Choices

 

1 2

 

PLAI 11

 

16

 

10/3

 

Code Review: Laziness and Infinite Data

 

 

 

17

 

10/5

 

Mutation

 

1 2

 

PLAI 12-13

 

18

 

10/8

 

Mutation, cont.

 

1 2

 

PLAI 13

 

19

 

10/10

 

Variables

 

1 2

 

PLAI 14

 

20

 

10/12

 

Web Programming

 

1 2

 

PLAI 15-16

 

21

 

10/15

 

Web Programming, cont.

 

1 2

 

PLAI 17

 

22

 

10/17

 

Web Programming, cont. and CPS

 

1 2

 

PLAI 17-18

 

23

 

10/19

 

Continuations

 

1 2

 

PLAI 19

 

24

 

10/22

 

Implementating Continuations

 

1 2

 

PLAI 20

 

25

 

10/24

 

Garbage Collection

 

 

PLAI 21, Wilson 1

 

26

 

10/26

 

GC: Reference Counting and Mark&Sweep

 

 

Wilson 2.1-2.3

 

27

 

10/29

 

GC: Stop&Copy and Generational Collection

 

 

Wilson 2.4-4.5

 

28

 

10/31

 

GC: Generational, Low-level, New features

 

 

Wilson 4.6-9

 

29

 

11/2

 

Types

 

 

PLAI 24-25

 

30

 

11/5

 

Typing Control

 

 

PLAI 26

 

31

 

11/7

 

Typing Data

 

 

PLAI 27

 

32

 

11/9

 

Code Review: Garbage Collectors

 

 

 

33

 

11/12

 

Type Soundness

 

 

PLAI 28

 

34

 

11/14

 

Explicit Polymorphism

 

 

PLAI 29

 

35

 

11/16

 

Type Inference

 

 

PLAI 30

 

36

 

11/19

 

Type Inference

 

 

PLAI 30

 

37

 

11/20

 

Implicit Polymorphism

 

 

PLAI 31

 

38

 

11/26

 

Prolog

 

1 2

 

PLAI 32-34

 

39

 

11/28

 

Code Review: Type Inferrer

 

 

 

40

 

11/30

 

Domain-specific Languages

 

1 2

 

PLAI 35

 

41

 

12/3

 

Macros: Compiler Extension

 

1 2

 

PLAI 36-37

 

42

 

12/5

 

Macros: Compiler Extension

 

 

PLAI 36-37

 

43

 

12/10

 

Final 1 @ 11:00am

 

 

 

44

 

12/12

 

Final 2 @ 2:30pm

 

 

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

This schedule may change.

3 Assignments

Programming

 

Assignment

 

Code

 

Out

 

Due

 

Basic Racket*

 

basic

 

8/27

 

8/29

 

Lists and Trees

 

lists

 

8/29

 

8/31

 

Higher-order Functions*

 

hof

 

8/31

 

9/5

 

Rudimentary Interpreter

 

rinterp

 

9/10

 

9/13

 

Extended Interpreter*

 

xinterp

 

9/17

 

9/25

 

Laziness and Infinite Data

 

lazy

 

9/21

 

10/2

 

Raw Web Programming

 

rawweb

 

10/3

 

10/11

 

Racket Web Programming

 

pltweb

 

10/17

 

10/23

 

Garbage Collectors

 

gc

 

10/26

 

11/8

 

Type Checker*

 

typec

 

11/9

 

11/15

 

Type Inferrer

 

typei

 

11/9

 

11/27

 

Prolog

 

prolog

 

11/28

 

12/6

Writing

 

Assignment

 

Code

 

Out

 

Due

 

Language Analysis the First

 

wlang1

 

8/27

 

10/15

 

Analysis: Laziness

 

wlazy

 

9/21

 

10/12

 

Analysis: Continuations

 

wcont

 

10/12

 

10/24

 

Language Analysis the Second

 

wlang2

 

10/17

 

12/6

 

Analysis: Garbage Collection

 

wgc

 

10/24

 

11/2

 

Analysis: Type Systems

 

wtype

 

11/2

 

11/28

 

Final

 

final

 

 

 

12/12

Evaluations

 

Assignment

 

Code

 

Out

 

Due

 

Survey*

 

survey

 

8/27

 

8/28

 

Unofficial Course Evaluation the First*

 

jay-eval1

 

10/1

 

10/3

 

Unofficial Course Evaluation the Second*

 

jay-eval2

 

10/29

 

10/31

 

Official Course Evaluation*

 

byu-eval

 

11/16

 

12/6

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