On this page:
Programming Language Design (Fall 2013)
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 2013)

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

We meet in 134 TMCB at 11-11:50am MWF.

Jay McCarthy’s office hours are 6am-11am M-F in 3328 TMCB. TAs are in the Special Weapons Research Lab (3325 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.

For more information, refer to our infomercial.

2 Lectures

 

Day

 

Date

 

Topic

 

Links

 

Notes

 

1

 

09/04

 

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

 

code screen

 

PLAI2 1 / HtDP 2

 

2

 

09/06

 

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

 

code screen

 

HtDP 3-6, 9

 

3

 

09/09

 

Racket: Recursive Structures / Higher-order Functions

 

code screen

 

HtDP 14 & 20

 

4

 

09/11

 

Parsing

 

code screen

 

PLAI2 2

 

5

 

09/13

 

Basic Interpretation

 

code screen

 

PLAI2 3

 

6

 

09/16

 

Desugaring

 

code screen

 

PLAI2 4

 

7

 

09/18

 

Functions

 

code

 

PLAI2 5*

 

8

 

09/20

 

Functions, cont.

 

code

 

PLAI2 5*

 

9

 

09/23

 

Environments

 

code screen

 

PLAI2 6*

 

10

 

09/25

 

Environments, cont.

 

code screen

 

PLAI2 6*

 

11

 

09/27

 

First-class Functions

 

code

 

PLAI2 7*

 

12

 

09/30

 

First-class Functions, cont.

 

code screen

 

PLAI2 7*

 

13

 

10/02

 

Mutation: Basics

 

code screen

 

PLAI2 8-8.1.5

 

14

 

10/04

 

Mutation: The Store

 

code screen

 

PLAI2 8.1.6-8.1.8

 

15

 

10/07

 

Mutation: Variables

 

code screen

 

PLAI2 8.1.8-8.4

 

16

 

10/09

 

Recursion

 

code screen

 

PLAI2 9

 

17

 

10/11

 

Objects: Basics

 

code screen

 

PLAI2 10-10.1.8

 

18

 

10/14

 

Objects: Dispatch, Inheritance, Mixins

 

code screen

 

PLAI2 10.1.9-10.3.5

 

19

 

10/16

 

Memory management: GC

 

code screen

 

PLAI2 11, Wilson 1

 

20

 

10/18

 

Memory management: Reference Counting & Mark and Sweep

 

code screen

 

PLAI2 11, Wilson 2.1-2.3

 

21

 

10/21

 

Memory management: Stop and Copy

 

code screen

 

PLAI2 11, Wilson 2.4-4.5

 

22

 

10/23

 

Memory management: Generational Collection

 

code screen

 

PLAI2 11, Wilson 4.6-9

 

23

 

10/25

 

Representation Decisions and Church Encoding

 

code screen

 

PLAI2 12

 

24

 

10/28

 

Desugaring

 

code screen

 

PLAI2 13

 

25

 

10/30

 

Control: Web Basics

 

code screen

 

PLAI2 14.1

 

26

 

11/01

 

Control: CPS

 

code screen

 

PLAI2 14.2

 

27

 

11/04

 

Control: CPS Interpreeter

 

code screen

 

PLAI2 14.3-4

 

28

 

11/06

 

Control: Tail Calls and call/cc

 

code screen

 

PLAI2 14.4-5

 

29

 

11/08

 

Control: Generators, Threads, OSes

 

code screen

 

PLAI2 14.6

 

30

 

11/11

 

Types: Basics

 

code screen

 

PLAI2 15.1-15.2.1

 

31

 

11/13

 

Types: Conditionals and Recursion

 

code screen

 

PLAI2 15.2.2-15.2.3

 

32

 

11/15

 

Types: Data

 

code screen

 

PLAI2 15.2.4-15.2.5 & 15.3.3 & 15.3.6

 

33

 

11/18

 

Types: Mutation and Parametric Polymorphism

 

code screen

 

PLAI2 15.2.6-15.3.1

 

34

 

11/20

 

Types: Type Inference

 

code screen

 

PLAI2 15.3.2

 

35

 

11/22

 

Types: Let-Polymorphism, Structural vs Nominal, Subtyping

 

code screen

 

PLAI2 15.3.2.3 & 15.3.4-5 & 15.3.7

 

36

 

11/25

 

Types: Objects and Curry-Howard

 

code screen

 

PLAI2 15.3.7.3-15.3.8

 

37

 

11/26

 

Laziness

 

code screen

 

PLAI2 17.1

 

38

 

12/02

 

Reactivity

 

code screen

 

PLAI2 17.2

 

39

 

12/04

 

Prolog

 

code screen

 

PLAI1 32-34

 

40

 

12/06

 

Contracts: Basics

 

code screen

 

PLAI2 16

 

41

 

12/09

 

Contracts: Extensions

 

code screen

 

PLAI2 16

 

42

 

12/11

 

Expressiveness

 

code screen

 

 

43

 

12/19

 

Final @ 11am

 

 

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

This schedule is likely to change—because it’s the first year with a new book and I’m not 100% sure that haven’t given too much time for some subjects. Similarly, as we progress, I will update the schedule to better reflect what sections (precisely) were covered on the day.

3 Assignments

Programming

 

Assignment

 

Code

 

Out

 

Due

 

Basic Racket*

 

basic

 

09/04

 

09/06

 

Rudimentary Interpreter

 

rinterp-java

 

09/04

 

09/23

 

Lists and Trees

 

lists

 

09/06

 

09/09

 

Higher-order Functions*

 

hof

 

09/09

 

09/11

 

Extended Interpreter*

 

xinterp

 

09/18

 

10/08

 

Game Survey

 

gsurvey

 

10/09

 

10/29

 

Garbage Collectors

 

gc

 

10/16

 

11/11

 

Web Game Survey

 

webgsurvey

 

10/30

 

11/13

 

Type Checker*

 

typec

 

11/11

 

11/19

 

Type Inferrer

 

typei

 

11/11

 

12/03

 

Laziness and Infinite Data

 

lazy

 

11/26

 

12/11

 

Prolog*

 

prolog

 

12/04

 

12/18

Writing

 

Assignment

 

Code

 

Out

 

Due

 

Language Analysis the First

 

wlang1

 

09/04

 

10/21

 

Analysis: Garbage Collection

 

wgc

 

10/16

 

10/30

 

Language Analysis the Second

 

wlang2

 

10/23

 

12/18

 

Analysis: Continuations

 

wcont

 

10/30

 

11/19

 

Analysis: Type Systems

 

wtype

 

11/11

 

12/06

 

Final

 

final

 

 

 

12/19

Evaluations

 

Assignment

 

Code

 

Out

 

Due

 

Survey*

 

survey

 

09/04

 

09/10

 

Unofficial Course Evaluation the First*

 

mid-eval1

 

10/01

 

10/04

 

Unofficial Course Evaluation the Second*

 

mid-eval2

 

10/30

 

11/01

 

Official Course Evaluation*

 

byu-eval

 

11/22

 

12/18

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 48 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.

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

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 "48 hours later" and such. However, nothing is ever due on the weekend (Saturday or Sunday), so sometimes 48 hours is actually 72, etc.

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 second 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.6 (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, Typed PLAI, 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

The textbook and lectures uses another language called Typed PLAI, but we won’t use it for assignments.

To install Typed PLAI: Open DrRacket. From the File menu, click Install Package and type plai-typed.

To use Typed PLAI: Open DrRacket. From the Language menu, click Choose Language.... Select the Determine language from source. Then you can copy in the code from the book or class.