Compilers

Hoopoe

hoopoe
Hoopoe

Due on Wednesday, May 1st at 11:59 PM. This is a compiler lab. If you have a partner, the two of you will complete this lab as a team. If you do not have a partner, you are effectively in a team by yourself.

If you are working with a partner, please be familiar with the Partner Etiquette guidelines. You and your partner share a single repository and, barring unusual circumstances, will receive the same grade. If you experience any difficulties in your partnership, please alert your instructor as soon as possible.

If you are working alone, please don’t hesitate to seek help if you get stuck. Since there are no ninjas for this course and you don’t have a partner, your instructor is the only interactive resource available to you and is happy to help you through any problems you might encounter.

In either case, be familiar with the academic integrity policy! You are permitted to discuss high-level details of your compiler project with other students, but you should never see or share anything that will be turned in for a grade. If you need help, please post on the Piazza forum or, if necessary, contact the instructor directly. Make sure to post privately if you are sharing code. If you have any doubts about what is okay and what is not, it’s much safer to ask than to risk violating the Academic Integrity Policy.

Overview

In this lab, we will extend the Gull compiler to include tail call optimization. We will call the resulting languge “Hoopoe”. Once you have completed this task, you will be able to compile arbitrary long-running computations using recursion for loops!

Transitioning to Hoopoe

As usual, you just need to merge a branch to get your Hoopoe starter code.

git fetch
git checkout hoopoe
git merge gull

After you merge, you’ll discover the usual updates in src/language/. The most relevant part for this lab is the change made in src/language/asts.ml: the EAppl constructor now takes three arguments rather than two. As a result of this, your code will not compile, but it won’t take much effort to get it back up and running.

The Hoopoe Language

The Hoopoe language is syntactically identical to Gull; there are no new forms of expressions or new language features available to the programmer. In fact, the only difference is the one described above: the abstract syntax of EAppl has changed from

| EAppl of expr * expr

to

| EAppl of expr * expr * bool

The additional boolean value indicates whether the EAppl in question is in a tail position: that is, whether the function call is the very last thing that this expression will do. The provided parser defaults to assuming that no calls are tail calls (since that is always safe). You will soon write a function to identify tail positions.

The first thing you should do in implementing Hoopoe is to modify your compiler so that this value is ignored during well-formedness and compilation. If you completed the Finch lab and have applications which are generated as part of closure conversion, use the value false for all EAppl you create. Finally, make your unit tests and run them to ensure that everything is still working.

Marking Tail Positions

Next, you need to mark tail positions in your AST. This is easiest to do as a function program -> program which examines each expression in the AST for tail calls that need to be marked. Then, call this function in the right place in your compiler. The particular approach you use does not matter as long as the tail position variable is being set correctly.

Tail Calls

Consider the following program:

def f x = x end
def g y = f y end
g 4

In Gull, which has no concept of tail calls, the following sequence of events would occur:

Tail call optimization begins with the observation that there was no point in returning to the body of g. We knew we would simply be returning its value, so the stack frame we’ve created for g is just taking up space. With tail call optimization, we want to bring about the following sequence of events instead:

This kind of optimization is especially important in functional languages, which make frequent and thorough use of recursion. With tail call optimization, recursive tail calls consume no additional stack memory and so work much like while loops in imperative languages. Without tail call optimization, long-running recursive loops will overflow the stack.

Implementing Tail Call Optimization

In tail call optimization, there are three main participants:

  1. The original caller. In the example above, this is the program’s main expression.
  2. The tail caller. In the example above, this is g.
  3. The tail callee. In the example above, this is f.

Not every call can be optimized. To apply our tail call optimization strategy, we must know the following facts:

Since the tail call position is known at compile time, it is the easiest part to handle: for a EAppl which is not in a tail position, we simply generate the same assembly as we would in Gull.

If the EAppl is in a tail position, we need to generate code which might perform a tail call. Remember that EAppl refers to two values: a closure and an argument. We’ll have our compiler generate assembly code which uses the following algorithm:

Note that the above algorithm requires that we know the number of parameters for the current function. You’ll probably need to modify your environment type to track this information and create a function in environment.ml that allows you to retrieve it. You are not required to perform tail calls in the bird_main expression; bird_main is handled a bit differently from your other functions, so it would require special effort to optimize and this work wouldn’t save that much stack memory overall.

It may be helpful to get this algorithm working for tail callees with an equal number of parameters first and then extend your implementation to tail callees with fewer parameters.

Testing Tail Call Optimization

Testing a compiler optimization is somewhat different than testing the compilation of a language feature. Our tests so far have treated the program as a black box and just checked its output. But an optimization should, by its very nature, not change what task a program accomplishes: it should just make the program smarter about how to accomplish that task.

In this case, however, we do know of an observable change in behavior. In Gull, long-running recursive functions will run out of stack memory and cause a segmentation fault. We can test the Hoopoe optimization by writing such programs and making sure they run correctly. Here are some examples of the sorts of tests you may want to run:

Summary

To complete this assignment, you’ll need to

Once you’ve done this, you have a complete language runtime: your programs can run indefinitely, never running out of stack or heap memory if written correctly!

Submitting

To submit your lab, just commit and push your work. The most recent pushed commit as of the due date will be graded. For more information on when assignments are due, see the Policies page.

After each lab, you will complete a brief questionnaire found here. In most cases, the questionnaire should take less than a minute. This questionnaire is required and will be used as part of your participation grade.

If You Have Trouble…

…then please contact your instructor! Piazza is the preferred method, but you can reach out via e-mail as well. Good luck!