On this page:
1 Introduction
2 Lectures
3 Assignments
4 Help
5 Turn In Policy
6 Readings
7 Software
8 Exams
9 Grading
9.1 Presentations
9.2 Written Assignments
9.3 Coding Assignments
10 Your Final Grade
11 Team Work
12 Codewalks
13 Advice

Programming Language Design (Fall 2011)

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

We meet in 3712 HBLL at 2pm and 3pm MWF.

Jay McCarthy’s office hours are 9am to 4pm, except during classes and lunch, 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. You are responsible for reading the content of this mailing list.

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/29

 

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

 

1 2 screen

 

HtDP 2

 

2

 

8/31

 

Racket: Designing Programs, Functions, Conditionals, Structures

 

1 2 screen

 

HtDP 3-6

 

3

 

9/2

 

Racket: Lists, Natural Recursion

 

1 2 screen

 

HtDP 9

 

4

 

9/7

 

Racket: Recursive Structures / Higher-order Functions

 

1 2 screen

 

HtDP 14 & 20

 

5

 

9/9

 

Code Review: Lists and Trees

 

1 2 screen

 

 

6

 

9/12

 

Modeling Languages

 

1 2 screen

 

PLAI 1

 

7

 

9/14

 

Basic Interpreters

 

1 2 screen

 

PLAI 2

 

8

 

9/16

 

Substitution

 

1 2 screen

 

PLAI 3

 

9

 

9/19

 

Functions

 

1 2 screen

 

PLAI 4*

 

10

 

9/21

 

Code Review: Rudimentary Interpreter

 

 

*

 

11

 

9/23

 

Deferring Substitution

 

1 2 screen

 

PLAI 5

 

12

 

9/26

 

First-class Functions

 

1 2 screen

 

PLAI 6

 

13

 

9/28

 

Laziness

 

1 2 screen

 

PLAI 7

 

14

 

9/30

 

Implementing Laziness

 

1 2 screen

 

PLAI 8

 

15

 

10/3

 

Recursion

 

1 2 screen

 

PLAI 9-10

 

16

 

10/5

 

Code Review: Extended Interpreter

 

 

 

17

 

10/7

 

Representation Choices

 

1 2 screen

 

PLAI 11

 

18

 

10/10

 

Mutation

 

1 2 screen

 

PLAI 12-13

 

19

 

10/12

 

Mutation, cont.

 

1 2 screen

 

PLAI 13

 

20

 

10/14

 

Variables

 

1 2 screen

 

PLAI 14

 

21

 

10/17

 

Code Review: Laziness and Infinite Data

 

 

 

22

 

10/19

 

Web Programming

 

1 2 screen

 

PLAI 15-16

 

23

 

10/21

 

Web Programming, cont.

 

1 2 screen

 

PLAI 17

 

24

 

10/24

 

Web Programming, cont. and CPS

 

1 2 screen

 

PLAI 17-18

 

25

 

10/26

 

Continuations

 

1 2 screen

 

PLAI 19

 

26

 

10/28

 

Implementating Continuations

 

1 2 screen

 

PLAI 20

 

27

 

10/31

 

Garbage Collection

 

 

PLAI 21, Wilson 1

 

28

 

11/2

 

GC: Reference Counting and Mark&Sweep

 

 

Wilson 2.1-2.3

 

29

 

11/4

 

GC: Stop&Copy and Generation Collection

 

 

Wilson 2.4-4.5

 

30

 

11/7

 

GC: Generational, Low-level, New features

 

 

Wilson 4.6-9

 

31

 

11/9

 

Types

 

 

PLAI 24-25

 

32

 

11/11

 

Typing Control

 

 

PLAI 26

 

33

 

11/14

 

Typing Data

 

 

PLAI 27

 

34

 

11/16

 

Type Soundness

 

 

PLAI 28

 

35

 

11/18

 

Explicit Polymorphism

 

 

PLAI 29

 

36

 

11/21

 

Type Inference

 

 

PLAI 30

 

37

 

11/22

 

Type Inference

 

 

PLAI 30

 

38

 

11/28

 

Implicit Polymorphism

 

 

PLAI 31

 

39

 

11/30

 

Prolog

 

1 2 screen

 

PLAI 32-33

 

40

 

12/2

 

Domain-specific Languages

 

1 2 screen

 

PLAI 35

 

41

 

12/5

 

Macros: Compiler Extension

 

1 2 screen

 

PLAI 36-37

 

42

 

12/7

 

Macros: Compiler Extension

 

1 2 screen

 

PLAI 36-37

 

43

 

12/15

 

Final @ 11:00am

 

 

 

44

 

12/16

 

Final @ 11:00am

 

 

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

This schedule may change.

3 Assignments

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

Late assignments will receive no credit.

 

Assignment

 

Team

 

Out

 

Due

 

Code

 

Weight

 

Survey

 

Solo

 

8/29

 

9/1

 

survey

 

1/60

 

Basic Racket

 

Solo

 

8/29

 

9/1

 

basic

 

1/40

 

Musical Notation

 

Solo

 

8/29

 

9/6

 

music

 

1/60

 

Lists and Trees

 

Solo

 

9/2

 

9/8

 

lists

 

1/40

 

Higher-order Functions

 

Solo

 

9/9

 

9/13

 

hof

 

1/40

 

Rudimentary Interpreter

 

Solo

 

9/14

 

9/20

 

rinterp

 

1/16

 

Substitution

 

One

 

9/16

 

9/27

 

wsubst

 

1/24

 

Extended Interpreter

 

Solo

 

9/21

 

9/29

 

xinterp

 

1/16

 

Laziness and Infinite Data

 

One

 

10/3

 

10/11

 

lazy

 

1/16

 

Laziness

 

One

 

10/3

 

10/11

 

wlazy

 

1/24

 

Raw Web Programming

 

One

 

10/7

 

10/13

 

rawweb

 

1/40

 

Language Design

 

Solo

 

10/12

 

10/18

 

wlang

 

1/60

 

Continuations

 

Two

 

10/26

 

11/1

 

wcont

 

1/24

 

Racket Web Programming

 

Two

 

10/28

 

11/3

 

pltweb

 

1/16

 

Garbage Collection

 

Two

 

11/9

 

11/15

 

wgc

 

1/24

 

Garbage Collectors

 

Two

 

11/4

 

11/17

 

gc

 

1/16

 

Type Checking

 

Three

 

11/16

 

11/22

 

wtypec

 

1/24

 

Type Checker

 

Three

 

11/18

 

11/22

 

typec

 

1/16

 

Type Inferrer

 

Three

 

11/21

 

12/1

 

typei

 

1/16

 

Type Inference

 

Three

 

11/21

 

12/1

 

wtypei

 

1/24

 

Prolog

 

Three

 

12/2

 

12/14

 

prolog

 

1/16

 

Final

 

Solo

 

 

 

 

 

final

 

1/10

This schedule may change.

4 Help

My job is to help you. Please ask for help. (But read 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.

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:

5 Turn In Policy

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

The subject line must be: "BYU - Fall 2011 - 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 contain 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 DrRacket (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 2011 - 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.rkt" and "wae2.rkt".

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 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.1.2 (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:

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 grade from 0 to 1, based on its correctness and your ability to show that you understand it is correct.

The entire written assignment receives the average of these grades.

9.3 Coding Assignments

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.

Each feature of a program receives a grade from 0 to 1, depending on (a) whether it is implemented correctly, (b) whether you adequately show (through tests) that the feature is implemented correctly, and (c) whether it is correctly documented (for example, in the contract and purpose statement and in explanations of what the tests show.)

If any of these missing for a given feature, you will receive no credit. This means that if you implement it correctly, but do not document that it is correct, you will receive no credit. This means you can do it correctly, but forget a simple test, and you will receive no credit.

The entire coding assignment receives the average of these grades.

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.

I will then run the following function to convert it to a letter:

> (define (convert-to-letter ng)
    (cond
      [(> ng 0.93) "A"]
      [(> ng 0.9) "A-"]
      [(> ng 0.86) "B+"]
      [(> ng 0.83) "B"]
      [(> ng 0.8) "B-"]
      [(> ng 0.76) "C+"]
      [(> ng 0.73) "C"]
      [(> ng 0.7) "C-"]
      [(> ng 0.66) "D+"]
      [(> ng 0.63) "D"]
      [(> ng 0.6) "D-"]
      [else "F"]))

Examples:

> (convert-to-letter 1)

"A"

> (convert-to-letter 0.94)

"A"

> (convert-to-letter 0.899999)

"B+"

> (convert-to-letter 0.81)

"B-"

> (convert-to-letter 0.74)

"C"

> (convert-to-letter 0.6999999)

"D+"

> (convert-to-letter 0.62)

"D-"

> (convert-to-letter 0.57)

"F"

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:

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

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!”

“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.”

“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!!!”

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

“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.”

“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.”