On this page:
2019 Summer - 301 - Organization of Programming Languages - Syllabus
1 Important Course Details
2 Schedule
3 Work in this Course
3.1 Checkpoints
3.1.1 Checkpoint #1
3.1.2 Checkpoint #2
3.2 Course Grade
3.3 Course Project
3.4 Presentation Policy
4 Help
5 Fine Print

2019 Summer - 301 - Organization of Programming Languages - Syllabus

This class is taught by Jay McCarthy. Call him Jay. Email him at first-name DOT last-name AT gmail DOT com.
We meet in Tong 222 at MWR 0800-1020.
Jay’s office hours are MW 1300-1400 in DAN 341.
There is a discussion group for the class on reddit. 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 group.

1 Important Course Details

Description. See below.
Readings. There is no required text and the class is not strictly tied to any book. There are some good resources I recommend for another take on the material. (PLAI) Programming Languages: Application and Interpretation (2nd edition) by Shriram Krishnamurthi. (Wilson) Paul Wilson’s survey of Garbage Collection methods. (PLLC & SEwPR) Programming Languages and Lambda Calculi, by Matthias Felleisen and Matthew Flatt. It was later adapted into another book, Semantics Engineering with PLT Redex by Matthias Felleisen, Robert Bruce Findler, and Matthew Flatt.
Policy. We do not allow electronic devices, such as laptops, phones, and tablets, to be used during class, without an explicit accomodation exception. I will first ask you to put it away and then I will ask you to leave.

2 Schedule

Day

 

Date

 

Topic

 

Notes

1

 

Mon

 

05/20a

 

Big Step

 

PLLC 1 & 4, PLAI 1-4

Next Task: 1

2

 

Mon

 

05/20b

 

Little Step & Contexts

 

PLLC 4 & 5

Next Task: 12

3

 

Wed

 

05/22a

 

Evaluation Contexts & CC

 

PLLC 5 & 6.1

Next Task: 16

4

 

Wed

 

05/22b

 

CK: Continuations & Stacks

 

PLLC 6.3

Next Task: 19

5

 

Thu

 

05/23a

 

Functions & Tail Calls

 

PLLC 3 & 7, PLAI 5

Next Task: 24

6

 

Thu

 

05/23b

 

Closures & Environments (CEK)

 

PLLC 3 & 6.4, PLAI 6-7

Next Task: 30

 

Mon

 

05/27

 

No class

7

 

Wed

 

05/29a

 

The Lambda Calculus

 

PLLC 3

Next Task: 38

8

 

Wed

 

05/29b

 

Recursion

 

PLLC 3.6, PLAI 9

Next Task: 39

9

 

Thu

 

05/30a

 

Data

 

PLLC 13, PLAI 10

Next Task: 43

10

 

Thu

 

05/30b

 

Mutation

 

PLLC 10, PLAI 8

Next Task: 48

11

 

Mon

 

06/03a

 

Variables

 

PLLC 10, PLAI 8.2

Next Task: 52

12

 

Mon

 

06/03b

 

Errors

 

PLLC 9

Next Task: 55

13

 

Wed

 

06/05a

 

Control

 

PLLC 9, PLAI 14

Next Task: 58

14

 

Wed

 

06/05b

 

Checkpoint Day

 

Due: Checkpoint #1

Next Task: 64

15

 

Thu

 

06/06a

 

Concurrency

 

Racket documentation

Next Task: 64

16

 

Thu

 

06/06b

 

Safety & Contracts

 

PLLC 11, PLAI 16

Links: 16.py

Next Task: 68

17

 

Mon

 

06/10a

 

Macros

 

PLAI 13

Next Task: 72

18

 

Mon

 

06/10b

 

Logic Programming

 

PLAI 17.3

Links: 18.rkt

Next Task: 74

19

 

Wed

 

06/12a

 

Memory Management: Manual & Reference Counting

 

Wilson, PLAI 11

Next Task: 75

20

 

Wed

 

06/12b

 

Memory Management: Mark & Sweep

 

Wilson, PLAI 11

Next Task: 75

21

 

Thu

 

06/13a

 

Memory Management: Stop & Copy

 

Wilson, PLAI 11

Next Task: 75

22

 

Thu

 

06/13b

 

Memory Management: Generational Collection

 

Wilson, PLAI 11

Next Task: 77

23

 

Mon

 

06/17a

 

Types: Basics & Gradual Typing

 

PLLC 11 & 12, PLAI 15, Siek’s blog

Next Task: 77

24

 

Mon

 

06/17b

 

Types: Extensions

 

PLLC 13, PLAI 15

Next Task: 81

25

 

Wed

 

06/19a

 

Types: Polymorphism

 

PLLC 14 & 16, PLAI 15

Next Task: 81

26

 

Wed

 

06/19b

 

Types: Subtyping

 

PLLC 18, PLAI 15

Links: 26.pdf

Next Task: 81

27

 

Thu

 

06/20a

 

Types: Inference

 

PLLC 15, PLAI 15

Next Task: 81

28

 

Thu

 

06/20b

 

Everything Else

 

Next Task: 81

29

 

Mon

 

06/24

 

Flex

 

Next Task: 110

30

 

Wed

 

06/26

 

Flex

 

Next Task: 110

31

 

Thu

 

06/27

 

Flex

 

Next Task: 110

32

 

Mon

 

07/01

 

Checkpoint Day

 

Due: Checkpoint #2

Next Task: 110

3 Work in this Course

If you do a little work for this course every day, including reading the textbook and working on the assignments, you will find the course rewarding and easy enough. If you just search for answers in course material as you try to complete work, you will not do well.
I highly recommend that you read this article about grading. I also recommend you read this article about the stress that you may experience in a computer science program. Please try to make healthy, productive choices in your life. I would love the opportunity to help you in any ways I can.

3.1 Checkpoints

As you work on the projects in the class, you will reach various milestones and report back on your progress. These checkpoints are the main way that I will be able evaluate your work.
You will argue that you completed the tasks by showing your code, test cases, proofs, paperwork, and other verification artifacts.
You will present evidence that the work is yours by (for example) submitting a Git repository with regular commits (at least one per task) over the course of the semester; paperwork done in your own handwriting; your thoughts on the unique design and problem-solving angles you applied; etc.
If you submit a Git repository, you can create an archive (i.e. zip) of it (including the .git directory!) or you can send me a link to a private repository online.

3.1.1 Checkpoint #1

Prepare a presentation (see Presentation Policy for how to submit) that presents an argument for which tasks you completed in your project. If this argument is not well-formulated, or if you present work that is not your own, then you will get an F on the assignment.

3.1.2 Checkpoint #2

Prepare a presentation (see Presentation Policy for how to submit) that presents an argument for which tasks you completed in your project. If this argument is not well-formulated, or if you present work that is not your own, then you will get an F on the assignment.

3.2 Course Grade

Your course grade is based on how many tasks you complete in the course project on the second checkpoint. However, this grade is modified by two things: first, if you are a graduate student or Honors-by-Contract student, then you are expected to do more, so it will be reduced by one rank (i.e., A becomes B, S becomes A, and so on.); second, if you did not achieve a grade with the letter C in it on the first checkpoint, then your grade is also reduced by one rank.

3.3 Course Project

Your main project in this course is to implement a virtual machine for a programming language with features similar to JavaScript & Python. The lectures (and textbook) will walk through the specification of the various features of this language and various implementation techniques.

There is a lot of flexibility about how you do this; in particular, you can implement it in whatever language you want. However, we mandate the language itself, as well as a few key design points (which are noted below.) In general, we always restrict you from using the implementation language’s feature X to implement feature X.

I highly recommend that you split your program into two related programs. One in a high-level language (like Racket, Python, Java, etc) that manages your test suite and implements some features and one in a low-level language (like C) that is the actual virtual machine. The best case scenario is to eventually re-implement the first program in the language you are implementing so it bootstraps itself. This is the implementation technique I used and I will reference it in the notes below. HL stands for the high-level program. LL stands for the low-level program.

The table below shows how long it took me to implement the project and how big the program was at each step. The final program was 1,899 lines, includes 353 lines (19%) of C code, 418 lines (22%) in my standard library, 680 lines (36%) in my compiler, and 442 lines (23%) of tests.
Following is a list of the tasks you should accomplish during the class in the order you should do them. In a few small cases, it is technically possible to do them in a different order, but don’t!
When you complete one, you should make a separate commit message in your repository that says Completed "Task #N - Description". This will make it easy for me to understand what you think you did.
You can download this list in the Todo.txt format: TODO. You could commit this file to your repository and mark tasks as completed when you do them.

 

 

Grade

 

Time

 

Lines

1

 

(HL) Define data structures to represent J0 programs.

image

 

F-

 

1m (0.14%) (1h)

 

+9 / -1 (0.36%) (8)

2

 

(HL) Write a pretty-printer for J0 programs.

 

F-

 

2m (0.28%) (1h)

 

+15 / -1 (0.98%) (22)

3

 

(HL) Write a test-suite of a dozen J0 programs.

A test suite means examples with their expected output.

 

F-

 

1m (0.14%) (1h)

 

+15 / -2 (1.56%) (35)

4

 

(HL) Implement a big-step interpreter for J0.

Connect to your test suite.

 

F-

 

2m (0.28%) (1h)

 

+21 / -10 (2.06%) (46)

5

 

(HL) Define a data structure to represent Sexprs.

image

 

F-

 

1m (0.14%) (1h)

 

+6 / -1 (2.28%) (51)

6

 

(HL) Convert your J0 test-suite into Sexprs.

 

F-

 

1m (0.14%) (1h)

 

+11 / -7 (2.46%) (55)

7

 

(HL) Implement a desugar function that converts Sexprs into J0.

Test it by verifying that the J0 Sexprs produce the original J0 examples. From now on, whenever you write test programs, write them as Sexprs and run them through desugar.

 

F-

 

2m (0.28%) (1h)

 

+13 / -3 (2.90%) (65)

8

 

(HL) Define data structures to represent J1 programs, with pretty printers.

image

 

F-

 

2m (0.28%) (1h)

 

+14 / -9 (3.13%) (70)

9

 

(HL) Write a test-suite of a dozen J1 programs.

These should be written as Sexprs.

 

F

 

2m (0.28%) (1h)

 

+23 / -8 (3.80%) (85)

10

 

(HL) Extend desugar to emit J1 programs.

 

F

 

2m (0.28%) (1h)

 

+15 / -4 (4.29%) (96)

11

 

(HL) Extend your interpreter for J1.

 

F

 

1m (0.14%) (1h)

 

+9 / -5 (4.47%) (100)

12

 

(HL) Define data structures to represent contexts.

image

 

F

 

1m (0.14%) (1h)

 

+11 / -1 (4.92%) (110)

13

 

(HL) Implement plug, a function that fills the hole in a context with a program.

 

F

 

2m (0.28%) (1h)

 

+13 / -1 (5.45%) (122)

14

 

(HL) Implement find-redex, a function that breaks a term into a context and a redex.

It should indicate failure if there are no redexes. It should consider every term in the program without regard to evaluation context restrictions.

 

F

 

7m (0.97%) (1h)

 

+32 / -2 (6.79%) (152)

15

 

(HL) Implement a small-step interpreter for J1 using contexts.

It should repeatedily call find-redex and plug until there are no more redexes. You should test it by verifying that it returns the same thing as the big-step interpreter.

 

F

 

6m (0.83%) (1h)

 

+40 / -13 (8.00%) (179)

16

 

(HL) Refine your definition of contexts to only allow evaluation contexts.

image

 

F

 

1m (0.14%) (1h)

 

+5 / -3 (8.09%) (181)

17

 

(HL) Refine find-redex so that it looks for evaluation contexts.

It should be able to more quickly identify the redex.

 

F

 

5m (0.69%) (1h)

 

+19 / -30 (7.60%) (170)

18

 

(HL) Implement the CC0 machine interpreter for J1.

This can be written as a while-loop that references a local variable for the code and another for the context. You should test it by verifying against the big-step interpreter.

 

F+

 

12m (1.66%) (1h)

 

+49 / -5 (9.56%) (214)

19

 

(LL) Define data structures to represent J1 programs.

image
I highly recommend setting things up so that you can dynamically determine what kind of structure a pointer points to, such as by using a standard header struct with a tag. This goes for all LL structures.
You are doing this again because you are now implementing in the low-level language. If your "high-level language" was already quite "low-level", then you don’t need to do this step, but I highly discourage you from continuing down this path, because the high-level code is going to get a lot more complicated.

 

F+

 

4m (0.55%) (1h)

 

+39 / -0 (11.30%) (253)

20

 

(HL) Write a function that emit HL-J1 programs as LL-J1 programs.

My code works by producing a C file that calls the low-level J1 constructors.

 

F+

 

12m (1.66%) (2h)

 

+60 / -13 (13.40%) (300)

21

 

(LL) Define data structures to represent continuations.

image

 

F+

 

4m (0.55%) (2h)

 

+80 / -36 (15.37%) (344)

22

 

(LL) Implement the CK0 machine interpreter for J1.

I highly recommend writing functions to print out all LL objects so you can debug intermediate states of the virtual machine.

 

F+

 

35m (4.83%) (2h)

 

+106 / -4 (19.93%) (446)

23

 

(HL) Connect your test-suite to your CK0 interpreter to verify that it works.

In my system, I generate a C program that is linked to the CK0 interpreter, runs, and prints out the final value.

 

F+

 

18m (2.49%) (3h)

 

+64 / -6 (22.52%) (504)

24

 

(HL & LL) Define data structures to represent J2 programs and function definitions.

image

 

F+

 

13m (1.80%) (3h)

 

+54 / -20 (24.04%) (538)

25

 

(HL) Write a test-suite of a dozen J2 programs.

Make sure to include recursive functions and sets of mutually-recursive functions.

 

F+

 

5m (0.69%) (3h)

 

+40 / -6 (25.56%) (572)

26

 

(HL) Define a substitution function that plugs the value of a variable into references to that variable.

 

F+

 

2m (0.28%) (3h)

 

+13 / -1 (26.09%) (584)

27

 

(HL) Extend your big-step interpreter to evaluate J2 programs.

Add a mapping from function symbols to definitions as an argument and use your substitution function.

 

F+

 

9m (1.24%) (3h)

 

+54 / -48 (26.36%) (590)

28

 

(LL) Define a substitution function that plugs the value of a variable into references to that variable.

 

F+

 

7m (0.97%) (3h)

 

+32 / -2 (27.70%) (620)

29

 

(LL) Extend your CK0 machine into the CK1 to evaluate J2 programs.

 

F+

 

15m (2.07%) (3h)

 

+44 / -14 (29.04%) (650)

30

 

(LL) Modify your CK1 machine into the CEK0 machine.

 

D-

 

5m (0.69%) (3h)

 

+25 / -39 (28.42%) (636)

31

 

(LL) Write test cases that verify your CEK0 machine does NOT have dynamic scope.

 

D-

 

4m (0.55%) (4h)

 

+12 / -1 (28.91%) (647)

32

 

(LL) Make a tweak to the CEK0 machine to give it dynamic scope, commit that, then revert it.

 

D-

 

1m (0.14%) (4h)

 

+4 / -3 (28.95%) (648)

33

 

(HL) Remove your big-step interpreter from the HL.

We will no longer maintain this version.

 

D

 

1m (0.14%) (4h)

 

+7 / -27 (28.06%) (628)

34

 

(HL & LL) Define data structures to represent J3 programs and runtime values.

image
You’ll want to convert your previous J2 tests into J3, but some of them won’t work anymore. Keep them around until we add recursion in.

 

D

 

6m (0.83%) (4h)

 

+24 / -29 (27.84%) (623)

35

 

(HL) Write a test-suite of a dozen J3 programs.

Make sure you include tests for shadowing and closing over free variables.

 

D

 

2m (0.28%) (4h)

 

+11 / -1 (28.28%) (633)

36

 

(HL) Extend desugar to support let expressions.

You can add let* too, if you want.

 

D

 

2m (0.28%) (4h)

 

+16 / -1 (28.95%) (648)

37

 

(LL) Extend CEK0 to CEK1 to evaluate J3 programs.

 

D+

 

7m (0.97%) (4h)

 

+28 / -16 (29.49%) (660)

38

 

(HL) Write a test program that evaluates factorial using only functions, except for a final conversion to numbers.

You should use Church-encoded booleans, numbers, pairs, as well as the Z combinator.

 

D+

 

28m (3.87%) (4h)

 

+97 / -33 (32.35%) (724)

39

 

(HL & LL) Extend your J3 data structures to J4.

image

 

D+

 

4m (0.55%) (4h)

 

+23 / -31 (31.99%) (716)

40

 

(HL) Extend desugar to allow not mentioning the recursive name, as well as provide a default.

I recommend rec as the default.

 

D+

 

1m (0.14%) (4h)

 

+6 / -1 (32.22%) (721)

41

 

(HL) Write a dozen test J3 programs, including extensions to your standard library.

I recommend including nat-unfold or do-times and some use cases, as well as converting your earlier J2 programs that stopped working.

 

D+

 

6m (0.83%) (5h)

 

+34 / -8 (33.38%) (747)

42

 

(LL) Extend the CEK1 machine to CEK2 to evaluate J4.

 

D+

 

10m (1.38%) (5h)

 

+22 / -8 (34.00%) (761)

43

 

(HL) Extend your J4 data structures to J5.

image

 

C-

 

2m (0.28%) (5h)

 

+8 / -1 (34.32%) (768)

44

 

(HL) Write a dozen test programs in J5 using the raw extensions.

Make sure to use each feature.

 

C-

 

5m (0.69%) (5h)

 

+27 / -1 (35.48%) (794)

45

 

(HL) Extend your standard library to include options and basic list functions, like map, filter, and fold.

 

C-

 

9m (1.24%) (5h)

 

+51 / -13 (37.18%) (832)

46

 

(HL) Write a dozen test J5 programs that use the standard library.

 

C

 

2m (0.28%) (5h)

 

+20 / -1 (38.03%) (851)

47

 

(LL) Extend your J4 data structures to J5 and extend the CEK2 machine to CEK3 to evaluate J5.

I recommend making as many things special primitives as possible, rather than core syntax.

 

C

 

27m (3.73%) (5h)

 

+94 / -41 (40.39%) (904)

48

 

(HL) Extend your data structures to represent J6 programs.

image

 

C

 

1m (0.14%) (5h)

 

+7 / -2 (40.62%) (909)

49

 

(HL) Extend your desugar standard library with mutation helpers.

You’ll want to include begin, begin0, when, unless, while, and for at least.

 

C

 

7m (0.97%) (6h)

 

+35 / -15 (41.51%) (929)

50

 

(HL) Write a dozen example J6 programs.

 

C+

 

5m (0.69%) (6h)

 

+41 / -24 (42.27%) (946)

51

 

(LL) Extend your data structures to J6 and the CEK3 machine to CEK4 to handle J6 programs.

Remember that the new mutation features of J6 can be represented as special primitives because your LL language almost certainly already has mutation. If it somehow doesn’t, then you’ll need to implement CESK0.

 

C+

 

6m (0.83%) (6h)

 

+24 / -4 (43.16%) (966)

52

 

(HL) Write a dozen example J7 programs.

image

 

C+

 

4m (0.55%) (6h)

 

+28 / -1 (44.37%) (993)

53

 

(HL) Extend desugar so that J7 programs are elaborated into J6 programs.

That is, mutated variables are implicitly boxed and unboxed. You should not box variables that are never mutated.

 

C+

 

24m (3.31%) (6h)

 

+71 / -20 (46.65%) (1044)

54

 

(HL) Extend desugar to support letrec.

You should now be able to reenable your mutually recursive functions from J2 (the last time we supported mutual recursion.)

 

C+

 

5m (0.69%) (6h)

 

+26 / -14 (47.18%) (1056)

55

 

(HL & LL) Extend your data structures to represent J9 programs.

image

 

B-

 

4m (0.55%) (6h)

 

+31 / -13 (47.99%) (1074)

56

 

(HL) Write a dozen example J9 programs.

 

B-

 

1m (0.14%) (6h)

 

+36 / -1 (49.55%) (1109)

57

 

(LL) Extend your CEK4 machine to CEK5 to support J9 programs.

I recommend doing this in two stages because you’ll be keeping the handling of abort, but throwing away the other code eventually.

 

B-

 

11m (1.52%) (7h)

 

+68 / -1 (52.55%) (1176)

58

 

(HL & LL) Extend your data structures to represent J10 programs, and remove support for J9 programs.

image

 

B-

 

2m (0.28%) (7h)

 

+9 / -9 (52.55%) (1176)

59

 

(HL) Write a dozen example J10 programs.

 

B-

 

1m (0.14%) (7h)

 

+9 / -1 (52.90%) (1184)

60

 

(HL) Modify your standard library and desugar to support J9 programs as J10 programs.

 

B-

 

4m (0.55%) (7h)

 

+23 / -8 (53.57%) (1199)

61

 

(LL) Extend your CEK4 machine to CEK6.

You’ll be including abort, but not the other features from CEK5.

 

B

 

28m (3.87%) (7h)

 

+37 / -62 (52.46%) (1174)

62

 

(HL) Extend your desugar to provide control constructs.

Such as return, break, and continue.

 

B

 

8m (1.10%) (7h)

 

+26 / -5 (53.40%) (1195)

63

 

(HL) Extend your standard library to support generators and write some example generators.

 

B

 

8m (1.10%) (7h)

 

+43 / -2 (55.23%) (1236)

64

 

(HL) Implement message-passing concurrency in your standard library.

You’ll want to include spawn, exit, channel, send, and recv.

 

B

 

10m (1.38%) (8h)

 

+74 / -10 (58.09%) (1300)

65

 

(HL) Write a dozen examples programs that use concurrency.

 

B

 

17m (2.35%) (8h)

 

+50 / -28 (59.07%) (1322)

66

 

(HL) Implement locks using message-passing concurrency.

 

B

 

6m (0.83%) (8h)

 

+40 / -1 (60.81%) (1361)

67

 

(HL) Implement futures (i.e. promises) using message-passing concurrency.

 

B

 

4m (0.55%) (8h)

 

+26 / -1 (61.93%) (1386)

68

 

(HL) Write a dozen example J12 programs.

 

B+

 

2m (0.28%) (8h)

 

+33 / -1 (63.36%) (1418)

69

 

(HL & LL) Extend your system from J11 to J12, thereby supporting runtime type inspection.

This should be a simple matter of extending the set of primitives. Inspecting function arity may require modifications to your closure representation.

 

B+

 

11m (1.52%) (8h)

 

+49 / -4 (65.37%) (1463)

70

 

(HL) Update your standard library to check types before performing operations.

At this point, it should never be possible for your program to error ungracefully, instead safety violations should always result in exceptions.

 

B+

 

18m (2.49%) (9h)

 

+143 / -45 (69.75%) (1561)

71

 

(HL) Extend your standard library and desugar to support contracts.

I recommend only using desugar to insert position information for positive and negative blame labels. Furthermore, I recommend hand-writing a small set of function contracts for fixed arities, rather than trying to make a fully generic function contract.

 

B+

 

38m (5.25%) (9h)

 

+183 / -55 (75.47%) (1689)

72

 

(HL) Implement a basic syntax-rules macro system.

Don’t work about renaming for hygeine.

 

B+

 

13m (1.80%) (9h)

 

+116 / -10 (80.21%) (1795)

73

 

(HL) Refactor your desugar function so that many of its features are now implemented in the standard library as macros.

 

B+

 

28m (3.87%) (10h)

 

+130 / -106 (81.28%) (1819)

74

 

(*) Download teachlog and write an interesting logic program.

If you don’t know what is interesting, feel free to ask me.

 

B+

 

3m (0.41%) (10h)

 

+37 / -1 (82.89%) (1855)

75

 

(HL) Write an example program that uses an obscene amount of memory without garbage collection.

Such as something that generates an exponential number of pairs.

 

B+

 

8m (1.10%) (10h)

 

+17 / -1 (83.60%) (1871)

76

 

(LL) Modify your virtual machine to perform stop & copy garbage collection.

This task has many many steps. You’ll want to intercept all allocations and put objects in a region you control. You’ll want to trace the heap and use the Cheney algorithm to copy objects and update their parent references. Don’t forget to install forwarding pointers!

 

B+

 

56m (7.73%) (11h)

 

+156 / -14 (89.95%) (2013)

77

 

(HL) Write a dozen programs that fail to type check.

 

A-

 

1m (0.14%) (11h)

 

+11 / -1 (90.39%) (2023)

78

 

(HL) Write a dozen programs that fail at runtime due to contract violations on untyped boundaries.

 

A

 

2m (0.28%) (11h)

 

+9 / -1 (90.75%) (2031)

79

 

(HL) Write a dozen programs that contain valid typed regions.

 

A+

 

1m (0.14%) (11h)

 

+9 / -1 (91.11%) (2039)

80

 

(HL) Implement a gradual type checker and elaborator that runs after your desugar function.

I recommend that the default context be untyped, so that you don’t need to support all forms initially. Only mark the task done, however, when you support the whole language.

 

A+

 

43m (5.94%) (12h)

 

+175 / -35 (97.36%) (2179)

81

 

Note. After this, most tasks can be done in any order.

The order shown is what I believe to be easier to harder.

 

S-

 

1m (0.14%) (12h)

 

+5 / -1 (97.54%) (2183)

82

 

(HL & LL) Modify your LL representation to use static variable offsets.

 

S-

 

28m (3.87%) (12h)

 

+49 / -49 (97.54%) (2183)

83

 

(HL & LL) Modify your LL representation to use flat closures, rather than the nested ones we’ve used so far.

 

S-

 

18m (2.49%) (13h)

 

+71 / -16 (100.00%) (2238)

84

 

(HL & LL) Create a bytecode format that enables your machine to instantly start without parsing.

I recommend using mmap to "read" the file.

 

S-

 

 

85

 

(HL & LL) Add seals to your language.

 

S

 

 

86

 

(HL) Extend your macro system to support hygiene via sets-of-scopes.

 

S

 

 

87

 

(HL & LL) Implement NaN boxing.

Here’s a great explanation: The Secret Life of NaN.

 

S

 

 

88

 

(HL) Modify your type elaborator to optimize programs using type information.

Reduce predicate tests to their value based on the type information.

 

S

 

 

89

 

(HL) Implement a reader for your language and give it a real syntax.

 

S

 

 

90

 

(HL) Extend your type system (and examples & violations) to support polymorphism.

You can compile like Java, because you are elaborating to an untyped language anyways.

 

S+

 

 

91

 

(HL) Extend your type system (and examples & violations) to support structural subtyping of object types.

 

S+

 

 

92

 

(HL) Extend your type system (and examples & violations) to use constraint-solving inference.

Make sure to remember the occurs check. Verify that you don’t go into an infinite loop!

 

S+

 

 

93

 

(HL) Implement a teachlog-style logic programming environment in your language using the non-determinism monad.

 

S+

 

 

94

 

(HL & LL) Extend your system to support continuation marks.

 

S+

 

 

95

 

(HL) Use continuation marks to make parameters.

 

S+

 

 

96

 

(LL) Extend your virtual machine to support mark-and-sweep as an option.

You should be able to flip between the two different collectors.

 

S+

 

 

97

 

(HL) Extend your type system to support F-bounded polymorphism.

 

SS-

 

 

98

 

(HL) Change your implementation of polymorphism to monomorphize.

 

SS-

 

 

99

 

(HL) Extend your type system (and examples & violations) to support iso-recursive types.

These are the ones that use fold and unfold.

 

SS-

 

 

100

 

(HL) Implement a logic programming environment in your language using first-class continuations and continuation marks.

 

SS

 

 

101

 

(HL) Use continuation marks to make exceptions work correctly with concurrency.

First demonstrate how it is broken without this. The current exception handler is essentially a parameter.

 

SS

 

 

102

 

(HL) Use continuation marks to make space-efficient contracts.

Use continuation marks to record the pending range checks and do not add a check more than once.

 

SS

 

 

103

 

(HL) Use continuation marks (with keys) to implement sandboxed evaluation via security-through-stack-inspection.

Use a mark to indicate that system access is denied.

 

SS

 

 

104

 

(HL) Implement select and asynchronous channels using message-passing concurrency.

Be careful to not livelock when no channel is available.

 

SS+

 

 

105

 

(HL & LL) Extend your system to support IO via special channels.

You’ll need a kernel process that polls the system for when IO is ready.

 

SS+

 

 

106

 

(HL) Extend your macro system to support procedural macros.

This will require compile-time evaluation of your code.

 

SS+

 

 

107

 

(HL) Implement a match macro.

 

SS+

 

 

108

 

(HL) Extend your macro system to support syntax-local-value.

 

SS+

 

 

109

 

(LL) Extend your virtual machine to support generational garbage collection.

Don’t forget about intergenerational pointers and a write barrier!

 

SS+

 

 

3.4 Presentation Policy

Consult the checkpoint details for details about the content of the presentation.
I will not pre-grade your presentation through email, but I can try to discuss it with you, although it is most effective to discuss it with you in my office.
You must record yourself for fifteen minutes and email me a link to the video. I highly recommend that you upload it as an unlisted YouTube video and send me that link. It is the most convenient for everyone. You must send this link to me before 5pm on the listed due date. No presentations will be accepted at any other time, for any reason. In extenuating circumstances, we can arrange an in-person presentation.
Your email must have the subject: Turn-in for CS301. If it does not have this subject, it will not be graded and I will treat it as though you did not turn it in.
Ensure that your email clearly says the last task that you believe you completed.
I highly recommend that you use your operating system’s screen-recording capability and use a simple presentation mechanism, like a digital whiteboard. If you don’t how to get your OS to record the screen, a cross-platform option is Google Hangouts on Air. (If you use Hangouts, make sure you sign up right away, because there is a waiting period before streaming.) You can use it to record yourself, and your screen, and it can automatically archive to YouTube. If you are presenting code, it makes sense to present from within your editor and show the code working. In any case, remember: the most important part of your presentation is the words you say.
Your presentation should be designed like you are teaching a class or having a conversation about something you deeply understand with a friend. You should not use a script or have any substantial notes. If you need notes, then write down ten (10) words that will help prompt you and keep you on track.

4 Help

My job is to help you.
One of the best ways for me to help you is to teach you how to help yourself. The main way I will put this idea into practice is that I will not answer your question until you have shown that you’ve read the relevant part of the textbook and have a concrete question or point of confusion about it.
If you need a "shallow" amount of help, then look at the discussion group. First, see if I have already answered your question. Then, make your own post.
Only send me personal email if you need to talk about something private, such as your grades. Anything else is best discussed in public, so others can benefit. If you do send personal email, put [CS301] as a prefix in the subject.
If you need a "deep" amount of help, please come to my office or contact me on Google Hangouts and we’ll talk and try to resolve whatever ails you.

5 Fine Print

In this course, all work is to be each student’s own. Students should therefore be familiar with the University’s rules on academic dishonesty, which can be found in the Bulletin of Undergraduate Studies and in the Schedule of Classes. In particular, plagiarism will not be tolerated! Any student caught plagiarizing another’s work will automatically receive a grade of F for the course. If you are unsure as to what constitutes plagiarism, it is your responsibility to check with the instructor. Other forms of dishonesty will result in similar actions. You may collaborate with your classmates on the design and results of the programs you will write in this course, but each student must implement these programs alone. Submission of shared student code is not permissible, and will result in a grade of F for the course. Help files are typically provided for each programming assignment, and students are encouraged to cut and paste useful code from these help files into their assignment submissions, but all other code must be the specific work of each student.
You are not allowed to post solution code to problem sets assigned in this class in public places (e.g. Github). This includes your own solutions as well as solutions that may be provided by the instructors.
This policy is a courtesy to future students, who — to the fullest extent possible — should have the opportunity to struggle with the problems in the same way that you do.
Non-compliance will be pursued rigorously per UMass Lowell’s academic integrity policy.