On this page:
2019 Spring - 406 - Compiler Construction - 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 Spring - 406 - Compiler Construction - 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 Southwick 407 at TR 1100-1215.
Jay’s office hours are TR 1230-1400 in DAN 341.
There is a mailing list hosted at Google Groups. Use it to ask non-revealing questions and receive answers, as well as general course announcements. You are responsible for reading the content of this mailing list.

1 Important Course Details

Description.
Includes both theory and practice. A study of grammars, specification and classes, the translation pipeline: lexical analysis, parsing, semantic analysis, code generation and optimization, and syntax-directed translation. Use of automatic generation tools in the actual production of a complete compiler for some language.

This course provides the following Essential Learning Outcomes (ELOs):

Information Literacy (IL): The ability to use digital technologies, communication tools and/or networks to define a problem or an information need; devise an effective search strategy;identify, locate, and evaluate appropriate sources; and manage, synthesize, use and effectively communicate information ethically and legally.

Applied and Integrative Learning (AIL): Applied and Integrative Learning is an understanding and disposition that a student builds across curriculum and co-curriculum, fostering learning between courses or by connecting courses to experiential learning opportunities.
Readings. (EC) We’ll be using the book Essentials of Compilation, by Jeremy Siek. For your convenience, I have included a copy of the book in PDF form on this site. I highly recommend this guide to X86-64 assembly.
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

 

Tue

 

01/22

 

Preliminaries

 

EC 1

Links: 1.pdf

Next Task: 1

2

 

Thu

 

01/24

 

Integers and Variables

 

EC 2

Links: 2.pdf

Next Task: 11

3

 

Tue

 

01/29

 

Integers and Variables

 

EC 2

Links: 3.pdf

Next Task: 27

4

 

Thu

 

01/31

 

Integers and Variables

 

EC 2

Links: 4.pdf

Next Task: 33

5

 

Tue

 

02/05

 

Register Allocation

 

EC 3

Links: 5.pdf

Next Task: 51

6

 

Thu

 

02/07

 

Register Allocation

 

EC 3

Links: 6.pdf

Next Task: 55

7

 

Tue

 

02/12

 

Register Allocation

 

EC 3

Links: 7.pdf

Next Task: 59

8

 

Thu

 

02/14

 

Control Flow

 

EC 4

Links: 8.pdf

Next Task: 67

 

Tue

 

02/19

 

No class

9

 

Thu

 

02/21

 

Control Flow

 

EC 4

Links: 9.pdf

Next Task: 85

10

 

Tue

 

02/26

 

Control Flow

 

EC 4

Links: 10.pdf

Next Task: 89

11

 

Thu

 

02/28

 

Heap Allocation and GC

 

EC 5

Links: 11.pdf

Next Task: 96

12

 

Tue

 

03/05

 

Heap Allocation and GC

 

EC 5

Links: 12.pdf

Next Task: 111

13

 

Thu

 

03/07

 

Heap Allocation and GC

 

EC 5

Due: Checkpoint #1

Links: 13.pdf

Next Task: 125

 

Tue

 

03/12

 

No class

 

Thu

 

03/14

 

No class

14

 

Tue

 

03/19

 

Functions and Closures

 

EC 6

Links: 14.pdf

Next Task: 126

15

 

Thu

 

03/21

 

Functions and Closures

 

EC 6

Links: 15.pdf

Next Task: 145

 

Tue

 

03/26

 

No class

16

 

Thu

 

03/28

 

Functions and Closures

 

EC 6 & 7

Links: 16.pdf

Next Task: 153

17

 

Tue

 

04/02

 

Functions and Closures

 

EC 7

Links: 17.pdf

Next Task: 163

18

 

Thu

 

04/04

 

Control-Flow Analysis

 

k-CFA (see Matt Might’s blog)

Links: 18.pdf

Next Task: 164

19

 

Tue

 

04/09

 

Control-Flow Analysis

 

cont.

Links: 19.pdf

Next Task: 164

20

 

Thu

 

04/11

 

Control-Flow Analysis

 

cont.

Links: 20.pdf

Next Task: 164

21

 

Tue

 

04/16

 

Macro Expansion

 

Macro History Naive Expansion by Example

Links: 21.pdf

Next Task: 164

22

 

Thu

 

04/18

 

Macro Expansion

 

Hygeine through Marks

Links: 22.pdf

Next Task: 166

23

 

Tue

 

04/23

 

Macro Expansion

 

Sets of Scopes - Video 1 - Video 2

Next Task: 166

24

 

Thu

 

04/25

 

Compilation Tools

 

Parser Generators

Next Task: 166

25

 

Tue

 

04/30

 

Compilation Tools

 

LLVM - LLVM video

Next Task: 168

26

 

Thu

 

05/02

 

Compilation Tools

 

Nanopass - Nanopass video

Due: Checkpoint #2

Next Task: 170

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 C 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 build a compiler for a high-level language to X86-64 assembly code. The lectures (and textbook) will walk through a particular design for this compiler that you will be expected to implement. 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 source and target languages, as well as the overall design.

The textbook contains many code excerpts that are meant to be illustrative of how you could program the compiler. Do not copy them. You should do your own work. In addition, you should use the language you want to use, not necessarily Racket. Furthermore, the code excerpts in the book are not complete and need a large amount of massaging to function properly, even if you use Racket.
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

 

Define data types for R0 program ASTs.

Recall the definition of R0:
image

 

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:
image

 

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:
image

 

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:
image

 

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:
image

 

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:
image
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:
image

 

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:
image

 

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:
image
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:
image
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:
image

 

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:
image

 

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:
image
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:
image
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:
image

 

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:
image
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+

 

 

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 CS406. 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.
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 Google Group. First, see if I have already answered your question. Then, send your own email.
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 [CS406] 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.