Assignment 6: Apply, arity checking, and variable arity functions
Due: Saturday, December 19th, 11:59PM EST
The goal of this assignment is to (1) implement arity checking in a language with functions, (2) to implement the apply operation, a fundamental operation that allows functions to be applied to lists of arguments, and (3) to implement variable arity functions, i.e. functions that take any number of arguments.
You are given a repository with a starter compiler similar to the Iniquity language we studied in class.
This started code is slightly different from past code in that:
It implements all of the “plus” features we’ve covered in previous assignments. It is worth studying this code to compare with the solutions you came up with. Try to formulate a technical critique of both solutions.
Parsing has been eliminated. Instead the code uses read to read in an S-Expression and syntax checking is done at the level of S-Expressions. Hopefully you’ve noticed that as the langauge gets larger and more complicated, so too does the parsing. Writing the parsing code is both tedious and easy to get wrong. Why is this? Our data representation of Exprs is a subset of S-Expressions (the stuff you can write with quote). We’re trying to process an unstructured stream of tokens into a structured, nested datum, but also at the same time verify that datum follows the rules of Exprness.
This design can be simplified by first processing tokens into S-Expressions, then checking whether this S-Expression is in the Expr subset. Parsing the whole S-Expression set is actually easier than parsing the Expr subset. And we can use an existing tool for doing it: read.
This was in fact our first approach to parsing. We have returned from this detour so that hopefully you can appreciate the value in it’s approach. Concrete syntax and parsing are orthogonal to the semantics of a language, which is the real focus of a compiler.
Overview
Of all the assignments so far, this one asks you to write the least amount of code, and yet, is probably the most difficult.
You are free to tackle this parts in any order you see fit, but I recommend approaching them in the order described here so that you can peicemeal work up to a full solution. Tackling everything at once will make things harder.
Apply yourself
The apply operation gives programmers the ability to apply a function to a list as though the elements of that list are the arguments of the function. In other words, it does the following: (apply f ls) = (f v1 ...), where ls is (list v1 ...).
Your task is to implement (a slightly simplified version) of the apply operation, which takes the name of a function (this assignment is based on Iniquity, which only has second-class functions) and an argument that is expected to evaluate to a list. The given function is then called with the elements of the list as its arguments.
For example, this calls the f function, which expects two arguments and adds them together, with a list containing 1 and 2. The result is equivalent to (f 1 2), i.e. 3:
Examples
> (begin (define (f x y) (+ x y)) (apply f (cons 1 (cons 2 '())))) 3
Note that the list argument to apply is an arbitrary expression, which when evaluated, should produce a list. We could have written the example as follows to emphasize that the compiler cannot simply examine the sub-expression to determine the arguments to the function being called:
Examples
> (begin (define (f x y) (+ x y)) (define (g z) (cons z (cons 2 '()))) (apply f (g 1))) 3
This addition adds the following to Exprs:
; type Expr = ; ... ; | ‘(apply ,Variable ,Expr)
The syntax.rkt file contains code for checking the syntax of Iniquity+.
The interp.rkt file contains a reference implementation of apply.
The compile.rkt file contains the compile for Iniquity+, and has stubbed out a function for compile apply expressions:
; Variable Expr CEnv -> Asm (define (compile-apply f e c) '())
Your job is to correctly implement this function.
The key idea here is that evaluating e should produce a list. That list is going to be represented as a linked list of pair pointers in the heap that eventually terminates in the empty list. But in order to call a function, we need to have arguments placed appropriately on the stack.
The compiler will need to emit code to check the assumption that the argumgent is a list and signal an error if it is violated, but you might first try to get this working on examples that are correct uses of apply before thinking about the error cases.
Until now, the compiler has always known how many arguments are given: you just look at the syntax of the call expression. But here we don’t know statically how many elements of the list there are.
So, the compiler will need to emit code that traverses the list and places the element at the appropriate position on the stack. After this, the function can be called as usual.
Since the list can be arbitrarily large, the emitted “copy list elements to stack” code will need to be a loop. Here’s a sketch of how the loop operates:
it has a register containing the list (either empty or a pointer to a pair).
it has a register containing a pointer to the next spot on the stack to put an argument.
if the list is empty, the loop is done.
if the list is a pair, copy the car to the stack, set the register holding the list to cdr, and advance the register holding the pointer to the stack.
Once you have this working for “good examples,” revisit the code to interleave type checking to validate that the subexpression produced a list.
Arity-check yourself, before you wreck yourself
When we started looking at functions and function applications, we wrote an interpreter that did arity checking, i.e. just before making a function call, it confirmed that the function definition had as many parameters as the call had arguments.
The compiler, however, does no such checking. This means that arguments will silently get dropped when too many are supplied and (much worse!) parameters will be bound to junk values when too few are supplied; the latter has the very unfortunate effect of possibly leaking local variable’s values to expressions out of the scope of those variables. (This has important security ramifications.)
The challenge here is that the arity needs to be checked at run-time (at least it will be with the addition of first-class functions, or... apply). But at run-time, we don’t have access to the syntax of the function definition or the call. So in order to check the arity of a call, we must emit code to do the checking and to compute the relevant information for carrying out the check.
Here is the idea: when compiling a function definition, the arity of the function is clear from the number of parameters of the definition. If the caller of a function can communicate the number of arguments to the function, then the function can just check that this number matches the expected number.
When compiling a call, the number of arguments is obvious, so the call should communicate this number to the function (which then checks it).
How should this number be communicated? A simple solution is to pass the number as though it were the first argument of the function.
Hence, a function of n arguments will be compiled as a function of n+1 arguments. A call with m arguments will be compiled as a call with m+1 arguments, where the value of the first argument is m. The emitted code for a function should now check that the value of the first argument is equal to n and signal an error when it is not.
You will need to modify compile-call and compile-define to implement this arity checking protocol. You will also need to update compile-apply, but first try to get things working for normal calls.
Apply with arity checks
What happens now with your previously good examples of using apply? Why is everything coming up 'err now?
The problem is that once you implement the arity checking mechanism for function definitions, this checking will also happen when you call the function via apply, but your apply code is not communicating the number of arguments, so the call is likely to fail the check. (Pop quiz: can you make an example that “works,” i.e. calls a function via apply but avoids the arity check error?)
In order to get apply working again, you’ll need to have it follow the protocol for calling the function with the number of arguments as the first argument.
But how many arguments are there? Well, there are as many arguments as there are elements in the list. Update compile-apply so the emitted code computes this quantity and passes it in the appropriate spot on the stack. After doing this, all your earlier examples should work again, it should catch arity errors where the function expects a different number of arguments from the number of elements in the list.
Variable arity functions
So far, the arity of every function is some fixed natural number. However, it’s quite useful to have functions that can take any number of arguments.
This is possible in Racket with the use of variable arity functions.
For example:
Examples
> (begin (define (f . xs) xs) (f 1 2 3)) '(1 2 3)
Note the use of “.” in the formal parameters of the function. This syntax is indicating that f can be applied to any number of arguments (including 0). The arguments will be bundled together in a list, which is bound to the xs variable. So this application produces the list '(1 2 3).
We can also write a function like this:
Examples
> (begin (define (f x y . zs) zs) (f 1 2 3)) '(3)
This function must be applied to at least 2 arguments. The first two arguments are bound to x and y. Any additional arguments are bundled in a list and bound to zs. So this expression produces a list of one element: 3.
To accomodate this, the syntax of formal parameters in function definitions is updated from:
; type Formals = (Listof Variable)
; type Formals = ; | '() ; | Variable ; | (Cons Variable Formals)
Meaning the formals “list” can be an improper list and when it is, the final variable is the one that binds to a list containing all remaining arguments.
To implement variable arity functions, you’ll need to update compile-define to handle this form of function defintion. The code includes a stubbed case for matching variable arity function definitions; you just need to write the code.
The idea is inverse to that of apply: an arbitrary number of arguments are passed on the stack and the function must convert the appropriate number of stack arguments to a list.
You’ll need to implement this part of the assignment after adding the arity checking protocol. This is because the function caller needs to pass in the count of the number of arguments. Without this information, the function won’t know how many arguments to put in a list.
If the function requires at least n arguments and is called with m arguments, then m-n arguments should be placed in a list and the list should be passed in as the n+1th argument. (If the function is called with less than n arguments, then it is an arity error.) So like apply, you’ll need a loop, but instead of copy from a list to a stack, you’ll need to copy from the stack to a list.
Program Optimization
Choose one of the following compiler optimizations (you will want to read up on them a bit before you pick one):
Common sub-expression elimination
Constant folding/propagation
Dead store elimination (in our languages a ‘dead store’ would be creating a box that is then never used).
In your repos there is a file optimization.txt. For the optimization you have chosen write approximately 500-1000 words explaining how you might implement your chosen optimization in Shakedown in that file. Make sure you consider that Shakedown has the ability to perform arbitrary side-effects (printing to the screen, for example), and therefore your explanation should discuss how that might affect where the optimization might apply.
The wordcount is meant to be a ballpark, wordcounts below 500 might be okay, but it would probably be difficult to describe the important considerations. You can show code in your answer, but it will not count towards your word count.
Testing
You can test your code in several ways:
Using the command line raco test . from the directory containing the repository to test everything.
Using the command line raco test <file> to test only <file>.
- Pushing to github. You can see test reports at:
(You will need to be signed in in order see results for your private repo.)
Note that only a small number of tests are given to you, so you should write additional test cases.
Submitting
Pushing your local repository to github “submits” your work. We will grade the latest submission that occurs before the deadline.