Grade

Time

Lines

1

Define data types for R0 program ASTs.

Recall the definition of R0:

F-

2m (0.07%) (1h)

+10 / -0 (0.20%) (10)

2

Write a pretty-printer for R0 programs.

You could print them out in a syntax you like, or just as simple ASTs.

F-

2m (0.07%) (1h)

+20 / -5 (0.49%) (25)

3

Build a test suite of a dozen R0 programs.

I do not recommend writing a parser for R0 yet. Instead, directly embed the construction of the program ASTs into your test suite. Furthermore, you’ll have to work out by hand what value these programs should return and verify that your interpreter returns the correct values.

F-

4m (0.14%) (1h)

+22 / -1 (0.90%) (46)

4

Write an interpreter for R0 programs.

This interpreter should have an interactive mode that interacts with the user on read and an automated mode that takes the input from a test case. In some languages, it is possible to make the automated mode use the interactive mode by faking input, but if you can’t do that, just make two different modes.

F-

3m (0.11%) (1h)

+16 / -1 (1.20%) (61)

5

Write a function that generates an R0 program that computes 2^N for a given N.

The purpose of this function is so that you can easily generate very large test programs. Use it to test your interpreter!

F-

2m (0.07%) (1h)

+16 / -3 (1.45%) (74)

6

Write a function that generates a random R0 program of depth N.

For example, if N is zero, then it should generate a random number of a call to read, but if it is positive, then it should generate a negation or binary addition of programs of smaller depth.

F-

4m (0.14%) (1h)

+34 / -6 (2.01%) (102)

7

Extend your test suite to generate a large number of random programs.

You won’t be able to predict what their value will be, but you will be able to test if the interpreter crashes and these will be useful as you extend the language. You’ll have to figure out a way to detect the number of calls to read and automatically provide an appropriate amount of input.

F-

0m (0.00%) (1h)

+3 / -1 (2.04%) (104)

8

Write some optimizer tests.

Verify that some programs are actually simplified by your optimizer.

F-

6m (0.21%) (1h)

+38 / -18 (2.44%) (124)

9

Write an optimizer for R0.

This is a function that takes R0 programs and returns new R0 programs that are simpler. In particular, they should remove all computations that do not depend on read.

F-

6m (0.21%) (1h)

+27 / -1 (2.95%) (150)

10

Extend your test suite to use your optimizer.

You should ensure that every program returns the same value when interpreted directly and after optimized.

F-

6m (0.21%) (1h)

+22 / -8 (3.22%) (164)

11

Extend your data types from R0 to R1.

Recall the definition of R1:

F-

1m (0.04%) (1h)

+6 / -1 (3.32%) (169)

12

Extend your pretty printer from R0 to R1.

Again, use whichever syntax you think looks nice.

F-

2m (0.07%) (1h)

+5 / -2 (3.38%) (172)

13

Write a dozen test R1 programs.

Obviously, these should incorporate variables and let expressions.

F

4m (0.14%) (1h)

+28 / -4 (3.85%) (196)

14

Extend your interpreter from R0 to R1.

You’ll need to incorporate an evironment that maps variables to values.

F

1m (0.04%) (1h)

+12 / -6 (3.97%) (202)

15

Extend your random generation function from R0 to R1.

You should have an environment that records which variables are bound by prior lets and allow these variables to be used in depth-0 expressions.

F

3m (0.11%) (1h)

+19 / -9 (4.17%) (212)

16

Write some R1-specific optimizer tests.

Again, to verify that you are actually optimizing the programs.

F

1m (0.04%) (1h)

+11 / -9 (4.21%) (214)

17

Extend your optimizer from R0 to R1.

In particular, you should inline variables that have been reduced to values or other variables.

F

5m (0.18%) (1h)

+21 / -7 (4.48%) (228)

18

Define data types for X0 program ASTs.

Recall the definition of X0:

F

6m (0.21%) (1h)

+35 / -2 (5.13%) (261)

19

Write an emitter for X0 programs.

This should emit in the syntax of the assembler you will use. It should take a parameter whether variables should be allowed in the output (which only makes sense for debugging.)

F

11m (0.39%) (2h)

+54 / -12 (5.96%) (303)

20

Build a test suite of a dozen X0 programs.

I recommend having your interpreter only return the value of rax on a retq, rather the entire state of the machine. Ideally, these programs will be manually compiled versions of some of your test R1 programs.

F

7m (0.25%) (2h)

+66 / -2 (7.21%) (367)

21

Write an interpreter for X0 programs.

The register file is a simple fixed vector where the registers are indices and the stack is a stack. You’ll have to have a special case for when you callq to a "system" function, like read or print.

F

18m (0.64%) (2h)

+59 / -10 (8.18%) (416)

22

Connect your X0 test suite to your system assembler.

I recommend creating an intermediate file containing the assembly on disk, so that you can look at the assembly you producing during compilation in the future. Make sure that you automatically compare the results of the assembled program and your interpreter.

F

15m (0.54%) (2h)

+105 / -51 (9.24%) (470)

23

Define data types for C0 program ASTs.

Recall the definition of C0:

F

2m (0.07%) (2h)

+19 / -3 (9.55%) (486)

24

Write a pretty printer for C0 programs.

This is purely a debugging tool.

F

5m (0.18%) (2h)

+28 / -1 (10.08%) (513)

25

Build a test suite of a dozen C0 programs.

Ideally, these programs will be manually compiled versions of your test R1 programs.

F

9m (0.32%) (3h)

+52 / -1 (11.09%) (564)

26

Write an interpreter for C0 programs.

This should use a global environment for variables values and should error when undefined variables are referenced.

F+

7m (0.25%) (3h)

+33 / -6 (11.62%) (591)

27

Write a few tests for uniquify that predict its output.

This is only possible if your unique names are predictable. These tests should be explicitly designed to have multiple occurrences of the same variable in the input that mean different things.

F+

4m (0.14%) (3h)

+32 / -11 (12.03%) (612)

28

Implement the uniquify pass for R1 programs.

This accepts R1 programs and returns new R1 programs that are guaranteed to use unique variables in each let expression. I recommend doing something to make the unique names deterministic, so it is possible to write tests.

F+

4m (0.14%) (3h)

+26 / -1 (12.52%) (637)

29

Connect uniquify to your test suite.

Ensure that every test program behaves the same before and after the uniquify pass by using the R1 interpreter.

F+

5m (0.18%) (3h)

+9 / -3 (12.64%) (643)

30

Write a half-dozen tests for resolve-complex that predict its output.

Work through the complicated examples and especially ensure that you don’t introduce aliases unnecessarily.

F+

6m (0.21%) (3h)

+30 / -10 (13.03%) (663)

31

Implement the resolve-complex pass for R1 programs.

This accepts R1 programs and returns new R1 programs that do not use complex expressions in argument positions. We can express this as a new language:

F+

16m (0.57%) (3h)

+33 / -1 (13.66%) (695)

32

Connect resolve-complex to your test suite.

Ensure that every test program behaves the same before and after resolve-complex by using the R1 interpreter. You could also write a function that checks to see if your result is in the correct form. Remember, this pass requires uniquify to have already run.

F+

38m (1.36%) (4h)

+74 / -31 (14.51%) (738)

33

Write a half-dozen tests for explicate-control that predict its output.

Work through the complicated examples and especially ensure that the order of operations (especially read calls) is preserved.

F+

13m (0.46%) (4h)

+84 / -27 (15.63%) (795)

34

Implement the explicate-control pass for R1 programs.

This accepts R1 programs and returns new C0 programs by lifting variables definitions outside of the bound expression position of let forms. Remember to use the mutually recursive functions explicate-control-tail and explicate-control-assign.

F+

4m (0.14%) (4h)

+22 / -1 (16.04%) (816)

35

Connect explicate-control to your test suite.

Ensure that every test program behaves the same before and after explicate-control by using the C0 interpreter. Remember, this pass requires resolve-complex to have already run.

F+

3m (0.11%) (4h)

+9 / -3 (16.16%) (822)

36

Write a few tests for uncover-locals that predict its output.

This should be very easy to do!

F+

4m (0.14%) (4h)

+39 / -19 (16.55%) (842)

37

Implement the uncover-locals pass for C0 programs.

This pass collects the set of variables used in the program and stores them for later passes in the auxiliary field of C0 programs.

F+

4m (0.14%) (4h)

+18 / -1 (16.89%) (859)

38

Connect uncover-locals to your test suite.

Ensure that every test program behaves the same before and after uncover-locals by using the C0 interpter. (This is trivial because uncover-locals shouldn’t effect the behavior of programs. You’re just doing this to make sure you call it and to make you didn’t accidentally change anything important during this pass.)

F+

6m (0.21%) (4h)

+85 / -76 (17.06%) (868)

39

Write a half-dozen tests for select-instr that predict its output.

You’ll want to make sure that you maintain the correct order and select the write assembly instructions.

F+

7m (0.25%) (5h)

+40 / -8 (17.69%) (900)

40

Implement the select-instr pass for C0 programs.

This pass takes C0 programs and returns X0 programs. It should preserve the set of variables used in the program. Remember to use helper functions for each kind of C0 AST.

F+

6m (0.21%) (5h)

+32 / -1 (18.30%) (931)

41

Connect select-instr to your test suite.

Ensure that every test program behaves the same before and after select-instr by using the X0 interpreter.

F+

9m (0.32%) (5h)

+32 / -20 (18.54%) (943)

42

Write a few tests for assign-homes that predict its output.

You’ll want to make sure that the output program contains no variables and that variables are assigned homes consistently.

F+

8m (0.29%) (5h)

+41 / -5 (19.25%) (979)

43

Implement the assign-homes pass for X0 programs.

This pass takes X0 programs and returns new X0 programs which do not mention variables. For now, it should just assign everything to consistent stack locations in an arbitrary way based on the set of variables used in the program.

F+

7m (0.25%) (5h)

+34 / -1 (19.89%) (1012)

44

Connect assign-homes to your test suite.

Ensure that every test program behaves the same before and after assign-homes by using the X0 interpreter. You may want to also include a check that guarantees the result contains no variable references.

D-

14m (0.50%) (5h)

+77 / -53 (20.37%) (1036)

45

Write a half-dozen tests for patch-instructions that predict its output.

You’ll want to make sure memory references are legal.

D-

2m (0.07%) (5h)

+20 / -5 (20.66%) (1051)

46

Implement the patch-instructions pass for X0 programs.

This pass takes X0 programs and returns new X0 programs which mention memory either zero or one times per instruction.

D

4m (0.14%) (5h)

+26 / -1 (21.15%) (1076)

47

Connect patch-instructions to your test suite.

Ensure that every test program behaves the same before and after patch-instructions by using the X0 interpreter. Remember, this pass assumes that assign-homes has run.

D

2m (0.07%) (5h)

+8 / -2 (21.27%) (1082)

48

Implement your language runtime.

Initially, this is just two functions: read_int and print_int. The first corresponds to the read call and the second is automatically used at the end of programs.

D+

2m (0.07%) (5h)

+17 / -3 (21.55%) (1096)

49

Implement the main-generation pass for X0 programs.

This pass should extend your final X0 programs with the prelude and postlude operations that set up the stack pointer appropriately for your code.

D+

13m (0.46%) (6h)

+37 / -13 (22.02%) (1120)

50

Connect your test suite to your system assembler and language runtime.

Close the final knot and get an actual compiler by having your final X0 programs (that come out of main-generation) sent to the system assembler and linked with your language runtime. You finally have a working compiler! Aren’t you proud?

D+

47m (1.68%) (6h)

+268 / -206 (23.24%) (1182)

51

Write a dozen tests for uncover-live that predict its output.

I don’t remember using examples from real programs, because they are likely to be too complicated. Instead, use simple ones that you come up with by hand.

C-

10m (0.36%) (7h)

+65 / -7 (24.38%) (1240)

52

Implement the uncover-live pass for X0 programs.

This pass takes X0 programs and returns new X0 programs where the block’s auxiliary field contains a list of live-after sets corresponds to each instruction. Make sure that you add registers to the live sets, not just variables.

C-

21m (0.75%) (7h)

+77 / -16 (25.57%) (1301)

53

Write a dozen tests for build-interferences that predict its output.

These should be the same programs you tested uncover-live with.

C-

7m (0.25%) (7h)

+28 / -3 (26.07%) (1326)

54

Implement the build-interferences pass for X0 programs.

Don’t go overboard with finding and using a graph library for your language. These are really simple graphs. Relax.

C

17m (0.61%) (7h)

+53 / -3 (27.05%) (1376)

55

Write a dozen tests for color-graph that predict its output.

In addition to tests that use your build-interferences results, you should also make some examples that correspond to Sudoku boards.

C

1m (0.04%) (7h)

+1 / -1 (27.05%) (1376)

56

Implement the color-graph function on arbitrary graphs.

Using the greedy saturation algorithm described in the book.

C

28m (1.00%) (8h)

+45 / -4 (27.86%) (1417)

57

Replace assign-homes with a new pass named assign-registers and implement the stupid-allocate-registers pass for X0 programs.

assign-registers pass should expect an assignment of variables to registers or stack locations in the auxiliary field and remove variables from the program by using the given mapping. stupid-allocate-registers will generate this mapping from the set of variables by assigning them all to stack locations. This is a trivial generalization of assign-homes!

C

1m (0.04%) (8h)

+3 / -4 (27.84%) (1416)

58

Write a dozen tests for the assign-registers that predict its output and check their behavior.

You should manually come up with register assignments for some sample programs, verify that assign-registers (when given those assignments) does it job, and check that the programs behave the same as they did before assignment.

C+

1m (0.04%) (8h)

+4 / -2 (27.87%) (1418)

59

Write a dozen tests for allocate-registers that predict its output.

These should be the same programs you tested color-graph with. Make sure there are tests that actually spill to the stack.

C+

7m (0.25%) (8h)

+23 / -23 (27.87%) (1418)

60

Replace stupid-allocate-registers with a new allocate-registers pass on X0 programs.

This pass will assume uncover-live and build-interferences have been run and use color-graph to construct a register assignment for assign-registers.

C+

20m (0.71%) (8h)

+47 / -18 (28.45%) (1447)

61

Update the main-generation pass to save and restore callee-saved registers.

Start off by saving and restoring all callee-saved registers, then make it sensitive to what you actually use.

C+

23m (0.82%) (9h)

+70 / -50 (28.84%) (1467)

62

Connect your test suite to the new main-generation and allocate-registers passes.

You now have a better compiler!

C+

14m (0.50%) (9h)

+19 / -14 (28.94%) (1472)

63

Write a few test programs that have opportunities for move-biasing to be effective.

The book contain some examples. You should come up with at least one R1 program that has the property; in addition to X0 programs.

B-

5m (0.18%) (9h)

+49 / -3 (29.84%) (1518)

64

Extend your build-interferences pass to construct a move-graph.

Update your build-interference tests to check that the move-graph is constructed correctly.

B

7m (0.25%) (9h)

+28 / -13 (30.14%) (1533)

65

Extend your color-graph function to incorporate move-biasing with an optional input argument.

Translate your move-biasing tests to color-graph problems and expected outputs.

B+

7m (0.25%) (9h)

+13 / -6 (30.27%) (1540)

66

Update your allocate-registers pass to make use of the move-biasing feature of color-graph.

This should be a trivial step of connecting the dots.

B+

9m (0.32%) (9h)

+36 / -32 (30.35%) (1544)

67

Extend your data types from R1 to R2.

Recall the definition of R2:

I recommend not making explicit constructors for binary subtraction, and, or or, but have those be pseudo-ASTs that expand to other forms. For example, in Racket, (define (make-and-ast x y) (make-if-ast x y (make-false-ast))). This is not required, but will simplify the rest of your compiler. You could do this with not as well and turn some of the comparisons into not’d versions of others, but I don’t recommend that, because X86-64 supports all of these operations nicely. and and or are specifically useful because their short-circuiting behavior is annoying to implement otherwise.

B+

5m (0.18%) (10h)

+19 / -1 (30.71%) (1562)

68

Extend your pretty printer from R1 to R2.

Again, use whichever syntax you think looks nice.

A-

1m (0.04%) (10h)

+6 / -2 (30.78%) (1566)

69

Write a dozen test R2 programs.

Obviously, these should incorporate the new features.

A-

5m (0.18%) (10h)

+43 / -1 (31.61%) (1608)

70

Extend your interpreter from R1 to R2.

There’s nothing very special about this.

A-

2m (0.07%) (10h)

+7 / -2 (31.71%) (1613)

71

Write type-checker tests for R2.

These should be programs that fail to type-check.

A-

5m (0.18%) (10h)

+60 / -41 (32.08%) (1632)

72

Write a type-checker for R2.

You’ll need an environment mapping variables to their types. Integrate this into your R2 tests so that every program you’ve written is type-checked before being used.

A-

18m (0.64%) (10h)

+124 / -75 (33.05%) (1681)

73

Extend your random generation function from R1 to R2.

You should have two helper functions. The first should generate an R2 program that returns a number and the other should generate one that returns a boolean. You’ll need to extend your environment to record the type of let-bound variables.

A-

18m (0.64%) (10h)

+34 / -14 (33.44%) (1701)

74

Write some R2-specific optimizer tests.

Again, to verify that you are actually optimizing the programs.

A-

7m (0.25%) (10h)

+27 / -6 (33.85%) (1722)

75

Extend your optimizer from R1 to R2.

You should expand the partial evaluation of boolean operations and by removing ifs with known values. Another thing is to remove nots by flipping the branches of ifs. If you substitute variables are bound to (not var), then you can do this more completely too.

A-

10m (0.36%) (11h)

+51 / -30 (34.26%) (1743)

76

Extend the uniquify pass from R1 to R2 programs, with a few test cases to check its output.

The new features don’t meaningfully change this pass.

A-

1m (0.04%) (11h)

+9 / -4 (34.36%) (1748)

77

Extend your data types from C0 to C1.

Recall the definition of C1:

A-

2m (0.07%) (11h)

+6 / -1 (34.46%) (1753)

78

Extend your pretty-printer from C0 to C1 programs.

The gotos everywhere will be a little ugly.

A

3m (0.11%) (11h)

+9 / -2 (34.60%) (1760)

79

Write a half-dozen C1 test programs.

Obviously, use the new features.

A

6m (0.21%) (11h)

+51 / -3 (35.54%) (1808)

80

Extend your interpreter from C0 to C1 programs.

You’ll want to hold an environment mapping labels to tails for use with gotos.

A

3m (0.11%) (11h)

+14 / -7 (35.68%) (1815)

81

Extend your data types from X0 to X1.

Recall the definition of X1:

A

2m (0.07%) (11h)

+10 / -2 (35.84%) (1823)

82

Extend your emitter from X0 to X1 programs.

The only annoying part is keeping track of the byte version of the registers.

A

6m (0.21%) (11h)

+10 / -2 (35.99%) (1831)

83

Write a half-dozen X1 test programs.

Obviously, use the new features.

A

11m (0.39%) (11h)

+38 / -3 (36.68%) (1866)

84

Extend your interpreter from X0 to X1 programs.

Use bitmasking to pull out the appropriate byte from registers.

A

13m (0.46%) (11h)

+38 / -16 (37.11%) (1888)

85

Extend the resolve-complex pass from R1 to R2 programs, with a few test cases to check its output.

The new features don’t meaningfully change this pass. Comparisons are complex, while ifs can be complex or expressions, depending on whether they are in tail position. The test expression of an if should be a comparison.

A

72m (2.57%) (13h)

+180 / -78 (39.12%) (1990)

86

Extend the explicate-control pass from R1 to R2 programs, with a half-dozen tests that predict its output.

This will be much more complicated than before, because you’ll be outputing multiple labels when there are ifs in the code. You’ll want to have a new helper for predicate positions.

A

44m (1.57%) (13h)

+84 / -11 (40.55%) (2063)

87

Extend the uncover-locals pass for C1 programs.

Nothing exciting here.

A

1m (0.04%) (13h)

+9 / -4 (40.65%) (2068)

88

Extend the select-instr pass for C1 programs, with a few test cases to check its output.

This should actually quite easy because the new C1 features map directly to new X1 features.

A

28m (1.00%) (14h)

+75 / -15 (41.83%) (2128)

89

Write a half-dozen tests for the uncover-live pass.

In particular, you need to make sure you are handling multiple blocks correctly.

A+

4m (0.14%) (14h)

+1 / -1 (41.83%) (2128)

90

Extend your uncover-live pass for X1 programs.

You’ll need to produce the blocks in topological order so you can identify the appropriate after blocks.

A+

37m (1.32%) (15h)

+94 / -23 (43.23%) (2199)

91

Extend your build-interference pass for X1 programs, with a few test cases to check its output.

This should be easy. You should update alloc-registers as well.

A+

4m (0.14%) (15h)

+18 / -16 (43.27%) (2201)

92

Extend the patch-instructions pass for X1 programs, with a few test cases to check its output.

cmpq and movzbq cannot have a constant in the second position.

A+

29m (1.04%) (15h)

+58 / -5 (44.31%) (2254)

93

Update your runtime to support printing out booleans, in addition to integers.

Use a convenient syntax, but don’t expose that booleans are really numbers.

A+

1m (0.04%) (15h)

+6 / -1 (44.41%) (2259)

94

Update your main-generation pass for boolean-outputting programs.

You’ll want to keep track the whole time what the final type of the program is so you can print the right kind of thing.

A+

11m (0.39%) (15h)

+63 / -49 (44.68%) (2273)

95

Extend your compiler to support conditional moves.

This requires a change to the C and X languages. The most interesting change is to the explicate-control pass. You would use these when the RHS of a let is a simple if.

A+

66m (2.36%) (16h)

+88 / -51 (45.41%) (2310)

96

Extend your data types from R2 to R3.

Recall the definition of R3:

It is important to understand that vectors are not arrays: the field referenced or mutated is statically known. They are more like C structures.

A+

2m (0.07%) (16h)

+11 / -3 (45.57%) (2318)

97

Extend your pretty printer from R2 to R3.

Again, use whichever syntax you think looks nice.

A+

4m (0.14%) (16h)

+12 / -2 (45.76%) (2328)

98

Write a dozen test R3 programs.

Make sure you create different sized vectors and verify that shallow copying works.

A+

5m (0.18%) (17h)

+28 / -1 (46.29%) (2355)

99

Extend your interpreter from R2 to R3.

There’s nothing very special about this.

A+

1m (0.04%) (17h)

+10 / -4 (46.41%) (2361)

100

Write type-checker tests for R3.

These should be programs that fail to type-check.

A+

4m (0.14%) (17h)

+19 / -1 (46.77%) (2379)

101

Extend your type-checker from R2 to R3.

This is not very interesting.

A+

6m (0.21%) (17h)

+26 / -11 (47.06%) (2394)

102

Extend your random generation function from R2 to R3.

You’ll need to have a new helper that generates a random vector of a certain length with a certain type at a particular index.

A+

9m (0.32%) (17h)

+28 / -5 (47.51%) (2417)

103

Write a function that generates an R3 program that uses N bytes of memory and makes it unreachable M times.

You’ll use this for testing garbage collection.

A+

33m (1.18%) (17h)

+40 / -2 (48.26%) (2455)

104

Write some R3-specific optimizer tests.

Again, to verify that you are actually optimizing the programs.

S-

2m (0.07%) (17h)

+7 / -4 (48.32%) (2458)

105

Extend your optimizer from R2 to R3.

At the least, you’ll want to inline vectors that are never mutated and then remove uses of vector-ref. If you want to be really complicated, then when a vector field is set to a constant, you can track that in the continuation of the mutation with a variant of the environment mapping variables to constants.

S-

21m (0.75%) (18h)

+70 / -17 (49.36%) (2511)

106

Modify your type-checker so that it wraps every expression in its type.

You’ll want a new data-structure like has-type that stores an expression and its type. Update your tests so that they verify this.

S-

52m (1.86%) (19h)

+130 / -37 (51.19%) (2604)

107

Extend the uniquify pass from R2 to R3 programs, with a few test cases to check its output.

The new features don’t meaningfully change this pass.

S-

3m (0.11%) (19h)

+53 / -28 (51.68%) (2629)

108

Implement the expose-allocation pass on typed R3 programs.

You’ll be transforming programs that mention vector into ones that use allocate. The language has the following change:

The most annoying part of this is synthesizing the has-type forms.

S-

23m (0.82%) (19h)

+111 / -8 (53.71%) (2732)

109

Extend your R3 interpreter to handle these new forms.

You can have a very fake implementation of collect (which does nothing) and allocate (which gets more space) if your language supports growable arrays.

S-

16m (0.57%) (19h)

+24 / -21 (53.76%) (2735)

110

Extend the resolve-complex pass from R2 to R3 programs, with a few test cases to check its output.

The new features don’t meaningfully change this pass. The main annonyance is making sure you preserve the has-type information.

S

22m (0.79%) (20h)

+74 / -25 (54.73%) (2784)

111

Extend your data types from C1 to C2.

Recall the definition of C2:

S

4m (0.14%) (20h)

+15 / -3 (54.96%) (2796)

112

Extend your pretty-printer from C1 to C2 programs.

There’s no standard syntax here, so follow your bliss.

S

4m (0.14%) (20h)

+15 / -5 (55.16%) (2806)

113

Write a half-dozen tests for C2.

Using the new features!

S

1m (0.04%) (20h)

+3 / -1 (55.20%) (2808)

114

Extend your interpreter from C1 to C2 programs.

Follow the same strategy in interpreting allocation that you did for R3.

S

3m (0.11%) (20h)

+19 / -7 (55.44%) (2820)

115

Extend your explicate-control pass to target C2.

There’s nothing much interesting going here.

S

14m (0.50%) (20h)

+36 / -13 (55.89%) (2843)

116

Extend your uncover-locals pass from C1 to C2.

The big change is that rather than only knowing the names of variables, you’ll need to record their types. One way to do this is to include the type in the syntax of set! or variable references in C.

S

15m (0.54%) (20h)

+112 / -97 (56.18%) (2858)

117

Extend your data types from X1 to X2.

Recall the definition of X2:

S+

1m (0.04%) (20h)

+4 / -1 (56.24%) (2861)

118

Extend your emitter from X1 to X2 programs.

You’ll want to emit a global data region for type information when types appear in arguments. If you are lazy, you can allocate many for each occurrence of a type. If you are not lazy, then you should ensure that each identical type appears only once.

S+

1m (0.04%) (20h)

+4 / -1 (56.30%) (2864)

119

Extend the select-instr pass to target X2.

The book walks through doing this very well.

S+

23m (0.82%) (21h)

+75 / -45 (56.89%) (2894)

120

Write a half-dozen X2 test programs.

Obviously, use the new features.

S+

17m (0.61%) (21h)

+17 / -15 (56.93%) (2896)

121

Extend your interpreter from X1 to X2 programs.

Again, use fakery for allocation for now.

S+

36m (1.29%) (22h)

+51 / -35 (57.24%) (2912)

122

Extend remaining passes for X2.

The big change here is being sensitive to the type of the variables when you are generating interferences so that live vectors are spilled (to the "root stack".) You’ll also have to generate a data region in your assembly to reference the types used in your program.

S+

61m (2.18%) (23h)

+127 / -88 (58.01%) (2951)

123

Update your runtime to support the allocation interface.

Initially, make this totally fake: collect just bumps the free pointer after calling your system’s malloc then leak that memory. At this point, all of your test programs should run, but your program that allocates lots of memory will use NxM bytes even though it should only ever use N bytes.

S+

88m (3.14%) (24h)

+387 / -232 (61.06%) (3106)

124

Update your runtime to support printing out vectors.

You’ll pay attention to the type information you embed in the objects to do this.

S+

63m (2.25%) (25h)

+43 / -13 (61.65%) (3136)

125

Update your runtime to actually do garbage collection.

This is a big deal, but it is hard to break down into steps. The book is very thorough walking through all the different things that you need to do. If you are having a lot of trouble, one strategy is to implement real collection in your interpreters too.

S+

28m (1.00%) (26h)

+260 / -38 (66.01%) (3358)

126

Extend your data types from R3 to R4.

Recall the definition of R4:

This is a big change from your past program forms, so I recommend making a new program AST constructor that just accepts an expression and synthesizes this form.

SS-

15m (0.54%) (26h)

+262 / -248 (66.29%) (3372)

127

Extend your pretty printer from R3 to R4.

Again, use whichever syntax you think looks nice.

SS-

7m (0.25%) (26h)

+24 / -5 (66.66%) (3391)

128

Write a dozen test R4 programs.

Make sure you pass and return all sorts of things from functions. Make sure you write a tail calling functions (recursive and mutually recursive) that use a huge amount of stack space if tail calls are not implemented correctly.

SS-

11m (0.39%) (26h)

+62 / -1 (67.86%) (3452)

129

Extend your interpreter from R3 to R4.

You’ll want to have an environment mapping function names to their implementations.

SS-

8m (0.29%) (26h)

+60 / -43 (68.19%) (3469)

130

Write type-checker tests for R4.

These should be programs that fail to type-check.

SS-

3m (0.11%) (26h)

+26 / -1 (68.68%) (3494)

131

Extend your type-checker from R3 to R4.

You will have to first gather types of all the functions, assume they are correct, then type-check them one-by-one.

SS-

34m (1.21%) (27h)

+77 / -32 (69.57%) (3539)

132

Extend your random generation function from R3 to R4.

You’ll need to have a new helper that generates a random function that accepts a particular value and returns one of some other type. Your random generation function will return a set of functions that are called and an expression.

SS-

58m (2.07%) (28h)

+157 / -76 (71.16%) (3620)

133

Write some R4-specific optimizer tests.

Again, to verify that you are actually optimizing the programs.

SS-

1m (0.04%) (28h)

+7 / -3 (71.24%) (3624)

134

Extend your optimizer from R3 to R4.

You’ll want to inline calls to functions with simple arguments (variables, constants, etc.) You’ll have to make sure that you don’t go into an infinite loop on recursive functions, but ideally you should be able to inline them a little bit in a form of loop-unrolling.

SS-

66m (2.36%) (29h)

+270 / -185 (72.91%) (3709)

135

Extend the uniquify pass from R3 to R4 programs, with a few test cases to check its output.

Function names will be renamed too.

SS-

6m (0.21%) (29h)

+31 / -10 (73.32%) (3730)

136

Implement the reveal-fun pass on R4 programs.

This locates function names and replaces them with a new form (fun-ref var). It is possible to do this at the same time as uniquify if you want. Make sure to write tests! You’ll need to update your interpreter to deal with these forms as well.

SS-

3m (0.11%) (29h)

+15 / -7 (73.48%) (3738)

137

Implement the limit-fun pass on R4 programs.

This modifies functions so that if they have more than six arguments, they are expected to be received via a vector. You also have to update the calls. Make sure to write tests!

SS-

31m (1.11%) (30h)

+138 / -7 (76.06%) (3869)

138

Extend the resolve-complex pass to R4 programs.

Function references are simple, while applications are complex, although you’ll want to allow them as expressions in tail position. I recommend also ensuring that the main expression immediately calls a newly designated function with no arguments.

SS-

52m (1.86%) (31h)

+138 / -16 (78.45%) (3991)

139

Extend your data types from C2 to C3.

Recall the definition of C3:

The final label in program forms is the main function. You can also remove read from C3 and replace it with a call. Similarly, you could add a print form to the language and remove that complexity from the main pass.

SS

7m (0.25%) (31h)

+12 / -10 (78.49%) (3993)

140

Extend your pretty-printer from C2 to C3 programs.

There’s no standard syntax here, so follow your bliss.

SS

15m (0.54%) (31h)

+251 / -213 (79.24%) (4031)

141

Write a half-dozen tests for C3.

Using the new features!

SS

37m (1.32%) (32h)

+4 / -2 (79.28%) (4033)

142

Extend your interpreter from C2 to C3 programs.

There’s nothing too exciting here either.

SS

20m (0.71%) (32h)

+89 / -78 (79.50%) (4044)

143

Extend your explicate-control pass to target C3.

Because you need to treat tail calls specially, you’ll want to track whether the expression you are converting is in tail position. One way to do this is with a boolean flag and another way is to have a separate function for converting in tail position. Just don’t duplicate code if you have the separate function—call the normal function in the non-app cases.

SS

29m (1.04%) (32h)

+72 / -41 (80.11%) (4075)

144

Extend your uncover-locals pass from C2 to C3.

This is pretty boring.

SS

14m (0.50%) (33h)

+132 / -109 (80.56%) (4098)

145

Extend your data types from X2 to X3.

Recall the definition of X3:

SS

8m (0.29%) (33h)

+13 / -6 (80.70%) (4105)

146

Extend your emitter from X2 to X3 programs.

Nothing too exciting here.

SS

16m (0.57%) (33h)

+331 / -316 (80.99%) (4120)

147

Write a half-dozen X3 test programs.

Obviously, use the new features.

SS

5m (0.18%) (33h)

+320 / -309 (81.21%) (4131)

148

Extend your interpreter from X2 to X3 programs.

Ho-hum.

SS

50m (1.79%) (34h)

+284 / -276 (81.36%) (4139)

149

Extend the select-instr pass to target X3.

The book walks through doing this well.

SS

72m (2.57%) (35h)

+164 / -70 (83.21%) (4233)

150

Extend allocate-registers (and its helper passes) for X3.

Make sure that you add the correct inteferences when considering the new forms in X3. I find that this is a good stage to move some of the code that used to be in the main pass into the assign pass, because you’ll be dealing with spilling and stack management in multiple functions now. When I did this pass, I found a huge mistake from the very first time I start register allocation where I wasn’t adding registers to the live sets, which caused the assignment of arguments to registers to get messed up.

SS

237m (8.46%) (39h)

+671 / -546 (85.67%) (4358)

151

Extend patch-instructions for X3.

You’ll have to deal with the idiosyncracies of the new instructions and tail-jmp. Review the book.

SS

33m (1.18%) (40h)

+79 / -87 (85.51%) (4350)

152

Update your runtime to deal with printing references to functions and function types.

Just print out something like #<function>. This will also be the point at which you integrate everything and see if you really generated the assembly correctly.

SS+

102m (3.64%) (41h)

+187 / -98 (87.26%) (4439)

153

Extend your data types from R4 to R5.

Recall the definition of R5:

The variable before a lambda’s argument list is for recursive references to this anonymous function (because we don’t have a letrec form.)

SS+

1m (0.04%) (41h)

+1 / -1 (87.26%) (4439)

154

Extend your pretty printer from R4 to R5.

Again, use whichever syntax you think looks nice.

SS+

2m (0.07%) (41h)

+13 / -3 (87.46%) (4449)

155

Write a dozen test R5 programs.

Make sure you explore all the exotic forms of variable capture and recursion you can.

SS+

10m (0.36%) (42h)

+74 / -19 (88.54%) (4504)

156

Extend your interpreter from R4 to R5.

It doesn’t matter what closure representation you use.

SS+

3m (0.11%) (42h)

+15 / -3 (88.78%) (4516)

157

Write type-checker tests for R5.

These should be programs that fail to type-check.

SS+

1m (0.04%) (42h)

+5 / -1 (88.85%) (4520)

158

Extend your type-checker from R4 to R5.

You’ll be assuming that the function is correctly typed for recursive invocations.

SS+

6m (0.21%) (42h)

+23 / -4 (89.23%) (4539)

159

Extend your random generation function from R4 to R5.

It should be straight-forward to reuse your function creating code.

SS+

5m (0.18%) (42h)

+26 / -15 (89.44%) (4550)

160

Write some R5-specific optimizer tests.

To check that the optimizer really works!

SS+

1m (0.04%) (42h)

+9 / -5 (89.52%) (4554)

161

Extend your optimizer from R4 to R5.

You’ll want to inline calls to known lambdas. Do this syntactically, rather than doing any sort of data-flow analysis.

SS+

28m (1.00%) (42h)

+33 / -7 (90.03%) (4580)

162

Extend the boring passes from R4 to R5 programs.

Like uniquify and reveal-fun.

SS+

5m (0.18%) (42h)

+18 / -7 (90.25%) (4591)

163

Implement the convert-to-closure pass on R5 programs.

You’ll have to add a dumb "trust-me" type. You’ll be turning lambdas into vectors and lifting the body of the lambda to a new top-level function. Application will change and references to (other) top-level functions will get turned into closures will no free variables. All the other top-level functions will also need to be updated to receive the useless closure value.

SS+

97m (3.46%) (44h)

+277 / -87 (93.98%) (4781)

164

Add a simple macro system based on syntax-rules to your compiler.

Follow the algorithm in the paper!

SS+

61m (2.18%) (45h)

+116 / -24 (95.79%) (4873)

165

Use your macro system to replace some of the syntactic sugar in your compiler, like the and & or transformations.

From when you added control.

SS+

17m (0.61%) (45h)

+63 / -5 (96.93%) (4931)

166

Write a parser for your programs.

Use a parser generator if it is convenient in your language. Now, you can finally read programs from files and run them!

SS+

66m (2.36%) (47h)

+157 / -39 (100.00%) (5087)

167

Expand R5 to have more features.

You could add more primitives (like more arithmetic), add more primitive data types (like sized integers and floats), variants, variable-sized homogenous arrays, and so on.

SS+

43m (1.54%) (46h)

+68 / -30 (97.68%) (4969)

168

Implement k-CFA for R5 and incorporate it into your optimizer.

Make sure you write some programs that observe the inlining working. You should probably also run with k = 0.

SS+

169

Connect your compiler to LLVM.

You should swap out the X language for LLVM IR. I recommend emitting the textual representation of the IR, rather than directly connecting to the LLVM API. You could also experiment with outputing C code.

SS+