Grade

Time

Lines

1

(HL) Define data structures to represent J0 programs.

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.

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.

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.

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.

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.


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.

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.

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.


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.

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.

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.

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.

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.

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.

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+