2021 Fall - 301 - Organization of Programming Languages

2021 Fall - 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 a virtual meeting on Zoom at TR 1100-1215.

Jay’s office hours are by appointment in Discord.

There is a discussion group for the class on reddit and on it, there’s a link to the Discord server. Use them to ask non-revealing questions and receive answers, as well as general course announcements. You are responsible for reading the content of this group and the Discord.

1 Important Course Details

Description.

See below for details.

Written and Oral Communication (WOC). This course meets the Essential Learning Outcome of Written and Oral Communication as defined under the Core Curriculum requirements. As such, the course will help students to enhance their abilities to develop and express ideas in written and/or oral formats, requiring the student to draw upon appropriate genres and styles with an emphasis on writing within the discipline.

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	Thu	09/02	Big Step	PLLC 1 & 4, PLAI 1-4 Links: 1-lecture.url 1-sexpr.c 1.pdf
2	Tue	09/07	Little Step & Contexts	PLLC 4 & 5 Links: 2-lecture.url 2.pdf
3	Thu	09/09	Evaluation Contexts & CC	PLLC 5 & 6.1 Links: 3-lecture.url 3.pdf
4	Tue	09/14	CK: Continuations & Stacks	PLLC 6.3 Links: 4-lecture.url 4.pdf
5	Thu	09/16	Functions & Tail Calls	PLLC 3 & 7, PLAI 5 Links: 5-lecture.url 5.pdf
6	Tue	09/21	Closures & Environments (CEK)	PLLC 3 & 6.4, PLAI 6-7 Links: 6-lecture.url 6.pdf
7	Thu	09/23	The Lambda Calculus	PLLC 3 Links: 7-lecture.url 7.pdf
8	Tue	09/28	Recursion	PLLC 3.6, PLAI 9 Due: Checkpoint : 1-26 Links: 8-lecture.url 8.pdf
9	Thu	09/30	Data	PLLC 13, PLAI 10 Links: 9-lecture.url 9.pdf
10	Tue	10/05	Mutation	PLLC 10, PLAI 8 Links: 10-lecture.url 10.pdf
11	Thu	10/07	Variables	PLLC 10, PLAI 8.2 Links: 11-lecture.url 11.pdf
12	Tue	10/12	Errors	PLLC 9 Links: 12-lecture.url 12.pdf
13	Thu	10/14	Control	PLLC 9, PLAI 14 Links: 13-lecture.url 13.pdf
14	Tue	10/19	Concurrency	Racket documentation Links: 14-lecture.url 14.pdf
15	Thu	10/21	Safety & Contracts	PLLC 11, PLAI 16 Links: 15-lecture.url 15.pdf
16	Tue	10/26	Macros	PLAI 13 Due: Checkpoint : 27-35 Links: 16-lecture.url 16.pdf
17	Thu	10/28	Logic Programming	PLAI 17.3 Links: 17-lecture.url 17.pdf
18	Tue	11/02	Memory Management: Manual & Reference Counting	Wilson, PLAI 11 Links: 18-lecture.url 18.pdf
19	Thu	11/04	Memory Management: Mark & Sweep	Wilson, PLAI 11 Links: 19-lecture.url 19.pdf
20	Tue	11/09	Memory Management: Stop & Copy	Wilson, PLAI 11 Links: 20-lecture.url 20.pdf
	Thu	11/11	No class
21	Tue	11/16	Memory Management: Generational Collection	Wilson, PLAI 11 Links: 21-lecture.url 21.pdf
22	Thu	11/18	Types: Basics & Gradual Typing	PLLC 11 & 12, PLAI 15, Siek’s blog Due: Checkpoint : 36-44 Links: 22-lecture.url 22.pdf
23	Tue	11/23	Types: Extensions	PLLC 13, PLAI 15 Links: 23-lecture.url 23.pdf
	Thu	11/25	No class
24	Tue	11/30	Types: Polymorphism	Jay will be away. PLLC 14 & 16, PLAI 15 Links: 24-lecture.url 24.pdf
25	Thu	12/02	Types: Subtyping	PLLC 18, PLAI 15 Links: 25-lecture.url 25.pdf
26	Tue	12/07	Types: Inference	Jay will be away. PLLC 15, PLAI 15 Links: 26-lecture.url 26.pdf
27	Thu	12/09	Everything Else	Due: Paper Due: Checkpoint : 45-64 Links: 27-lecture.url 27.pdf
Final	Thu	12/16	Final	You must submit by 1700. Due: Exam

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 Course Grade

Your course grade is based on your stand-up reports, a final exam, and how many tasks you complete in the course project at each checkpoint, as well as your grade on the paper.

Your stand-up reports count for 0.25. The final counts for 0.25. The project counts for 0.5. Each checkpoint is equally weighted, and you will receive a percentage of that weight based on what percentage of the required tasks you complete for that checkpoint. The last checkpoint, however, is special, because you can earn extra-credit, at a rate of 0.01 points per extra task completed.

Your paper counts for 0.25 points.

These points are totaled and converted to a letter grade according to the CollegeBoard’s assignment system.

3.2 Stand-Ups

Each class meeting, you will give a stand-up report where you announce your progress on the work of the course, state what you are going to be working on until the next stand-up, and inform the group of any blocking issues you’re having that are making it difficult to progress. These stand-ups will be given in alphabetical order. The number of reports you give in the course will be totaled, divided by the number of days in the course, and multiplied by the stand-up weight.

3.3 Exam

The course will end with a final exam. On the day that you take the exam (which must either be the last day of class or the day scheduled by the university), you must email me for your custom exam and then return your answers by email within three hours. The exam may contain questions on any material discussed in any lecture.

Your exam email request must have the subject: Request for CS301 Exam. If it does not have this subject, it will not be opened and I will treat it as though you did not request it, and thus did not complete an exam. This email must clearly include the name you used to register for the course. When you return your exam, you must reply to my reply to your original request email.

You may submit your answers as one of the following options: (a) plain-text in the body of the email, (b) an attached PDF, or (c) an attached sequence of JPEGs. I recommend you use (a) if possible, (b) if you prepare your answers electronically, and (c) if you prepare your answers on paper.

3.4 Checkpoint

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.

The schedule lists what day they are due on. You must email me by 5pm on the day listed. The email should look like this:

Subject: Turn-in for CS301

To: first-name DOT last-name AT gmail DOT com

Body:

${your-name}

${greatest-completed-task}

${link-to-git}

${link-to-youtube}

If your email does not contain this information, or if it is late, then it will not be graded and I will treat it as though you did not turn it in. No checkpoints will be accepted at any other time, for any reason.

${your-name} means that you should include your name. You might think I will be able to tell from your email address, but many times I cannot.

${greatest-completed-task} means that you should include the last task that you believe you completed.

${link-to-git} means you must submit a link to your Git repository. This repository must be online and private. There are many Git repository providers, like GitHub, Bitbucket, and Gitlab. I suggest using GitHub. Since it is private, you’ll have to share access with me. You can do that by my email address. Your Git repository is evidence that the work is yours. You must commit regularly (at least once per task) over the course of the semester.

${link-to-youtube} means you must submit a link to an unlisted video on YouTube. The purpose of this video is to argue that you completed the tasks by showing your code, test cases, proofs, paperwork, and other verification artifacts.

You must record yourself for up to fifteen minutes and email me a link to the video. You really don’t need to talk for more than fifteen minutes. This is a brief check-in of just a few points of your project.

I highly recommend that you use your operating system’s screen-recording capability and use a simple presentation mechanism, like a digital whiteboard. I recommend using OBS to record. You can use it to record yourself, and your screen, and then upload to YouTube afterwards. 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 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.

I will not pre-grade your checkpoint.

3.5 Paper

I will not pre-grade your paper 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 hand in your paper by emailing me a PDF by 5pm on the due date listed. Your email must have the subject: Paper 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.

Your turn-in must be prepared electronically. I recommend using LaTeX. You must use 0.5" margins, the font Times New Roman at 11pt, and single-spacing. Each page must be numbered in the footer. You must render with black ink (color may be used in diagrams, but not in the text) on white paper. I recommend using only mild formatting. You should not include long quotes, code samples, or large diagrams. You should reference sources using the BibTeX alpha style. Work that is incorrectly formatted will not be graded and I will consider it as though you never turned it in.

You should aim to write about five pages of content, not counting references.

Your paper will receive a grade from the closed interval between 0 and 1. I will evaluate your paper based on the veracity of its content, its logical structure, as well as its grammar, style, and form.

For your subject, choose one of the following two options.

Depth

Choose one facet of programming language design, such as type systems, security, memory management, modularity, safety, expressiveness, alternative semantics (like constraint solving) etc. Introduce and define the facet (at least one page). Discuss its development in the field of programming languages by punctuating the history with particular examples of innovations and deployments. (Each such section should probably be at least a page, maybe more.) End with a brief summarization (roughly a page) of open issues and ideas that you have for developing it (this last part is the only place where your opinion can enter in.)

Breadth

Choose one programming language. (I suggest selecting a research or otherwise experimental language. A good place to start looking is Wikipedia.) Briefly introduce it and the historical circumstances of its development (less than a page.) Select a number of unique or interesting aspects of it (such as those listed above as "depth" topics) and discuss how it approaches them. The most important part of discussing the approach is walking through the consequences of the design in the lives of programmers and their software. (Each one should be at least a page and perhaps more.) End with a brief personal perpsective on what you think its influence has been or should be on the world of programming languages (roughly a page.)

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

		Time	Lines
1	(HL) Define data structures to represent J0 programs.	1m (0.14%) (1h)	+9 / -1 (0.36%) (8)
2	(HL) Write a pretty-printer for J0 programs.	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.	1m (0.14%) (1h)	+15 / -2 (1.56%) (35)
4	(HL) Implement a big-step interpreter for J0. Connect to your test suite.	2m (0.28%) (1h)	+21 / -10 (2.06%) (46)
5	(HL) Define a data structure to represent Sexprs.	1m (0.14%) (1h)	+6 / -1 (2.28%) (51)
6	(HL) Convert your J0 test-suite into Sexprs.	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.	2m (0.28%) (1h)	+13 / -3 (2.90%) (65)
8	(HL) Define data structures to represent J1 programs, with pretty printers.	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.	2m (0.28%) (1h)	+23 / -8 (3.80%) (85)
10	(HL) Extend desugar to emit J1 programs.	2m (0.28%) (1h)	+15 / -4 (4.29%) (96)
11	(HL) Extend your interpreter for J1.	1m (0.14%) (1h)	+9 / -5 (4.47%) (100)
12	(HL) Define data structures to represent contexts.	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.	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.	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.	6m (0.83%) (1h)	+40 / -13 (8.00%) (179)
16	(LL) Define data structures to represent J1 programs. 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.	4m (0.55%) (1h)	+39 / -0 (11.30%) (253)
17	(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.	12m (1.66%) (2h)	+60 / -13 (13.40%) (300)
18	(LL) Define data structures to represent continuations.	4m (0.55%) (2h)	+80 / -36 (15.37%) (344)
19	(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.	35m (4.83%) (2h)	+106 / -4 (19.93%) (446)
20	(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.	18m (2.49%) (3h)	+64 / -6 (22.52%) (504)
21	(HL & LL) Define data structures to represent J2 programs and function definitions.	13m (1.80%) (3h)	+54 / -20 (24.04%) (538)
22	(HL) Write a test-suite of a dozen J2 programs. Make sure to include recursive functions and sets of mutually-recursive functions.	5m (0.69%) (3h)	+40 / -6 (25.56%) (572)
23	(HL) Define a substitution function that plugs the value of a variable into references to that variable.	2m (0.28%) (3h)	+13 / -1 (26.09%) (584)
24	(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.	9m (1.24%) (3h)	+54 / -48 (26.36%) (590)
25	(LL) Define a substitution function that plugs the value of a variable into references to that variable.	7m (0.97%) (3h)	+32 / -2 (27.70%) (620)
26	(LL) Extend your CK0 machine into the CK1 to evaluate J2 programs.	15m (2.07%) (3h)	+44 / -14 (29.04%) (650)
27	(LL) Modify your CK1 machine into the CEK0 machine.	5m (0.69%) (3h)	+25 / -39 (28.42%) (636)
28	(LL) Write test cases that verify your CEK0 machine does NOT have dynamic scope.	4m (0.55%) (4h)	+12 / -1 (28.91%) (647)
29	(LL) Make a tweak to the CEK0 machine to give it dynamic scope, commit that, then revert it.	1m (0.14%) (4h)	+4 / -3 (28.95%) (648)
30	(HL) Remove your big-step interpreter from the HL. We will no longer maintain this version. You can get rid of your small-step, too.	1m (0.14%) (4h)	+7 / -27 (28.06%) (628)
31	(HL & LL) Define data structures to represent J3 programs and runtime values. 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.	6m (0.83%) (4h)	+24 / -29 (27.84%) (623)
32	(HL) Write a test-suite of a dozen J3 programs. Make sure you include tests for shadowing and closing over free variables.	2m (0.28%) (4h)	+11 / -1 (28.28%) (633)
33	(HL) Extend desugar to support let expressions. You can add let* too, if you want.	2m (0.28%) (4h)	+16 / -1 (28.95%) (648)
34	(LL) Extend CEK0 to CEK1 to evaluate J3 programs.	7m (0.97%) (4h)	+28 / -16 (29.49%) (660)
35	(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.	28m (3.87%) (4h)	+97 / -33 (32.35%) (724)
36	(HL & LL) Extend your J3 data structures to J4.	4m (0.55%) (4h)	+23 / -31 (31.99%) (716)
37	(HL) Extend desugar to allow not mentioning the recursive name, as well as provide a default. I recommend rec as the default.	1m (0.14%) (4h)	+6 / -1 (32.22%) (721)
38	(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.	6m (0.83%) (5h)	+34 / -8 (33.38%) (747)
39	(LL) Extend the CEK1 machine to CEK2 to evaluate J4.	10m (1.38%) (5h)	+22 / -8 (34.00%) (761)
40	(HL) Extend your J4 data structures to J5.	2m (0.28%) (5h)	+8 / -1 (34.32%) (768)
41	(HL) Write a dozen test programs in J5 using the raw extensions. Make sure to use each feature.	5m (0.69%) (5h)	+27 / -1 (35.48%) (794)
42	(HL) Extend your standard library to include options and basic list functions, like map, filter, and fold.	9m (1.24%) (5h)	+51 / -13 (37.18%) (832)
43	(HL) Write a dozen test J5 programs that use the standard library.	2m (0.28%) (5h)	+20 / -1 (38.03%) (851)
44	(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.	27m (3.73%) (5h)	+94 / -41 (40.39%) (904)
45	(HL) Extend your data structures to represent J6 programs.	1m (0.14%) (5h)	+7 / -2 (40.62%) (909)
46	(HL) Extend your desugar standard library with mutation helpers. You’ll want to include begin, begin0, when, unless, while, and for at least.	7m (0.97%) (6h)	+35 / -15 (41.51%) (929)
47	(HL) Write a dozen example J6 programs.	5m (0.69%) (6h)	+41 / -24 (42.27%) (946)
48	(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.	6m (0.83%) (6h)	+24 / -4 (43.16%) (966)
49	(HL) Write a dozen example J7 programs.	4m (0.55%) (6h)	+28 / -1 (44.37%) (993)
50	(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.	24m (3.31%) (6h)	+71 / -20 (46.65%) (1044)
51	(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.)	5m (0.69%) (6h)	+26 / -14 (47.18%) (1056)
52	(HL & LL) Extend your data structures to represent J9 programs.	4m (0.55%) (6h)	+31 / -13 (47.99%) (1074)
53	(HL) Write a dozen example J9 programs.	1m (0.14%) (6h)	+36 / -1 (49.55%) (1109)
54	(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.	11m (1.52%) (7h)	+68 / -1 (52.55%) (1176)
55	(HL & LL) Extend your data structures to represent J10 programs, and remove support for J9 programs.	2m (0.28%) (7h)	+9 / -9 (52.55%) (1176)
56	(HL) Write a dozen example J10 programs.	1m (0.14%) (7h)	+9 / -1 (52.90%) (1184)
57	(HL) Modify your standard library and desugar to support J9 programs as J10 programs.	4m (0.55%) (7h)	+23 / -8 (53.57%) (1199)
58	(LL) Extend your CEK4 machine to CEK6. You’ll be including abort, but not the other features from CEK5.	28m (3.87%) (7h)	+37 / -62 (52.46%) (1174)
59	(HL) Extend your desugar to provide control constructs. Such as return, break, and continue.	8m (1.10%) (7h)	+26 / -5 (53.40%) (1195)
60	(HL) Write a dozen example J12 programs.	2m (0.28%) (8h)	+33 / -1 (63.36%) (1418)
61	(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.	11m (1.52%) (8h)	+49 / -4 (65.37%) (1463)
62	(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.	18m (2.49%) (9h)	+143 / -45 (69.75%) (1561)
63	(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.	8m (1.10%) (10h)	+17 / -1 (83.60%) (1871)
64	(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!	56m (7.73%) (11h)	+156 / -14 (89.95%) (2013)
65	(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.	38m (5.25%) (9h)	+183 / -55 (75.47%) (1689)
66	(HL) Write a dozen programs that fail to type check.	1m (0.14%) (11h)	+11 / -1 (90.39%) (2023)
67	(HL) Write a dozen programs that fail at runtime due to contract violations on untyped boundaries.	2m (0.28%) (11h)	+9 / -1 (90.75%) (2031)
68	(HL) Write a dozen programs that contain valid typed regions.	1m (0.14%) (11h)	+9 / -1 (91.11%) (2039)
69	(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.	43m (5.94%) (12h)	+175 / -35 (97.36%) (2179)
70	Note. After this, most tasks can be done in any order. The order shown is what I believe to be easier to harder.	1m (0.14%) (12h)	+5 / -1 (97.54%) (2183)
71	(HL) Implement a basic syntax-rules macro system. Don’t work about renaming for hygeine.	13m (1.80%) (9h)	+116 / -10 (80.21%) (1795)
72	(HL) Refactor your desugar function so that many of its features are now implemented in the standard library as macros.	28m (3.87%) (10h)	+130 / -106 (81.28%) (1819)
73	(*) Download teachlog and write an interesting logic program. If you don’t know what is interesting, feel free to ask me.	3m (0.41%) (10h)	+37 / -1 (82.89%) (1855)
74	(HL) Extend your standard library to support generators and write some example generators.	8m (1.10%) (7h)	+43 / -2 (55.23%) (1236)
75	(HL) Implement message-passing concurrency in your standard library. You’ll want to include spawn, exit, channel, send, and recv.	10m (1.38%) (8h)	+74 / -10 (58.09%) (1300)
76	(HL) Write a dozen examples programs that use concurrency.	17m (2.35%) (8h)	+50 / -28 (59.07%) (1322)
77	(HL) Implement locks using message-passing concurrency.	6m (0.83%) (8h)	+40 / -1 (60.81%) (1361)
78	(HL) Implement futures (i.e. promises) using message-passing concurrency.	4m (0.55%) (8h)	+26 / -1 (61.93%) (1386)
79	(HL & LL) Modify your LL representation to use static variable offsets.	28m (3.87%) (12h)	+49 / -49 (97.54%) (2183)
80	(HL & LL) Modify your LL representation to use flat closures, rather than the nested ones we’ve used so far.	18m (2.49%) (13h)	+71 / -16 (100.00%) (2238)
81	(HL & LL) Create a bytecode format that enables your machine to instantly start without parsing. I recommend using mmap to "read" the file.
82	(HL & LL) Add seals to your language.
83	(HL) Extend your macro system to support hygiene via sets-of-scopes.
84	(HL & LL) Implement NaN boxing. Here’s a great explanation: The Secret Life of NaN.
85	(HL) Modify your type elaborator to optimize programs using type information. Reduce predicate tests to their value based on the type information.
86	(HL) Implement a reader for your language and give it a real syntax.
87	(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.
88	(HL) Extend your type system (and examples & violations) to support structural subtyping of object types.
89	(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!
90	(HL) Implement a teachlog-style logic programming environment in your language using the non-determinism monad.
91	(HL & LL) Extend your system to support continuation marks.
92	(HL) Use continuation marks to make parameters.
93	(LL) Extend your virtual machine to support mark-and-sweep as an option. You should be able to flip between the two different collectors.
94	(HL) Extend your type system to support F-bounded polymorphism.
95	(HL) Change your implementation of polymorphism to monomorphize.
96	(HL) Extend your type system (and examples & violations) to support iso-recursive types. These are the ones that use fold and unfold.
97	(HL) Implement a logic programming environment in your language using first-class continuations and continuation marks.
98	(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.
99	(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.
100	(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.
101	(HL) Implement select and asynchronous channels using message-passing concurrency. Be careful to not livelock when no channel is available.
102	(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.
103	(HL) Extend your macro system to support procedural macros. This will require compile-time evaluation of your code.
104	(HL) Implement a match macro.
105	(HL) Extend your macro system to support syntax-local-value.
106	(LL) Extend your virtual machine to support generational garbage collection. Don’t forget about intergenerational pointers and a write barrier!

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.

1	Important Course Details
2	Schedule
3	Work in this Course
4	Help
5	Fine Print