Homework 6 - Apply, variadic functions
Accept the assignment on GitHub Classroom here.
Do the assignment 🐫.
Upload the assignment on Gradescope. The most convenient way to do this is by uploading your assignment repo through the integrated GitHub submission method on Gradescope, but you may also upload a .zip of your repo.
In this homework you'll extend the function calls developed in class with two additional features:
applyoperation takes in the name of a function and a list (as defined in homework 4--either
()or a pair where the second element is a list) of arguments, and calls the function on those arguments. Here's a program that uses apply:
(define (f x y) (+ x y)) (print (apply f (pair 1 (pair 2 ()))))
- Variadic functions can take additional arguments beyond those given static
names. The additional arguments are put into a list that the function can then
access. Here's an example of a program with a variadic function:
(define (f x xs ...) (pair x xs)) (print (f 1 2 3 4))
This program should print
(pair 1 (pair 2 (pair 3 (pair 4 ())))).
A function's arity is the number of arguments it takes; variadic functions are
also called variable-arity functions. In class, we implemented static arity
checking: since we know at compile-time how many arguments we're passing when
calling a function, we can throw a compile-time error when this doesn't match
the function's arity. In order to correctly implement
switch to dynamic arity checking, checking the number of arguments at runtime.
We recommend implementing these features in the order described below.
The starting language for this assignment includes nil (
homework 4. It also includes a unary operator
empty? that returns
its argument is
The stencil also includes updated AST definitions and parser. We've added the case
Apply of string * expr to the definition of the
expr type (for
apply), and added the
rest: string option field to the
defn type (for variadic functions). As described below, you will be modifying the interpreter and compiler stencil to support these new syntax elements.
apply in the interpreter and the compiler. The first argument to
apply needs to be a function name, i.e., a symbol. The second argument is an
expression that evaluates to a list.
In the interpreter, implement
apply by evaluating the second argument and then
walking through the list, adding each element to the environment with the
corresponding argument name.
In the compiler, implement
apply by walking through the elements of the list,
adding each to the stack where the function arguments would go.
You should throw a (runtime) error if the second argument isn't a list. For now,
don't implement arity-checking for
apply in the compiler.
Dynamic arity checking
Now that we have
apply, we can't guarantee at compile-time that a function
will be called with the right number of arguments. So we'll need to add this check to our compiled functions before the function body.
To do this in the compiler, we will compile functions so that they expect an additional first
"argument" on the stack which specifies the number of actual arguments passed
in. You'll need to modify the code for
apply and regular function calls to pass in this extra "argument". Note that this will shift the stack index of the "normal" arguments, so you will need to change the expected stack index that is computed for each argument name. Then, add instructions which check that the number of actual arguments passed in is equal
to the number of arguments it expects and error otherwise. Finally, you can remove the static error checking from regular function calls, since they will now be checked dynamically.
Note that the interpreter already implements dynamic arity checking, since there are no "compile-time" checks.
Variadic functions in our language look like this:
(define (add args ...) (if (empty? args) 0 (+ (left args) (apply add (right args)))))
We can call this method with
(add 1 2 3) (which returns
(add 1 2 3 4) (which returns
10), or even
(apply add (pair 1 (pair 2 ()))) (which returns
indicates that the function is variadic. The last named parameter (called the
rest parameter) gets a list of all of the "extra" arguments passed
in. Consider the following program:
(define (f a b c ...) (pair a (pair b c))) (f 1 2 3 4 5)
f's body is executed,
(pair 3 (pair 4 (pair 5 ()))) (i.e., a list containing 3, 4, and 5). If a variadic function has
N regular parameters in addition to the rest parameter, it is an error to call
it with less than
N arguments. If it is called with exactly
N arguments, the
rest parameter will be bound to the empty list.
We have extended the
defn type shown in class with an extra
which is a
string option. This field will be
None for non-variadic
functions. For variadic functions, it will be
Some "<name of rest parameter>". Note that when
rest is not
None, its name is not included in the list
args. In other words, the
defn record for
(define (f a b ...) a) will have
In the interpreter, support variadic functions by adding a binding to the environment for the rest parameter. You'll need to convert an OCaml list of arguments to a Lisp list.
In the compiler, we recommend calling variadic functions just like regular
functions: push all of the arguments onto the stack. In other words, the code to
call a function shouldn't need to change to support variadic functions. When compiling variadic functions, you'll need to add a loop that copies any extra arguments
from the stack into a freshly-allocated list. You should have already implemented
dynamic arity checking, so you'll be able to tell how many of these extra
arguments there are. After this loop, add instructions that put a pointer to this list (tagged as usual) onto the stack as the
N+1-th argument. Then, when compiling the body of the function, add a binding to the symbol table that maps the rest parameter to this stack index, so that the function body can reference this list.
In implementing variadic function support, you may find the
function helpful. It returns the number of bindings in a symbol table.
The grammar your new interpreter and compiler should support is as follows:
<program> ::= <defn> ... <expr> <defn> ::= (define (<id> <id> ...) <expr>) + | (define (<id> <id> ... <id> "...") <expr>) <expr> ::= <num> | <id> | true | false | () | (<z-prim>) | (<un_prim> <expr>) | (<bin_prim> <expr> <expr>) | (<id> <expr> ...) + | (apply <id> <expr>) | (if <expr> <expr> <expr>) | (let ((<id> <expr>) ...) <expr>) | (do <expr> <expr> ...) <z-prim> ::= read-num | newline <un_prim> ::= add1 | sub1 | zero? | num? | not | pair? | empty? | left | right | print <bin_prim> ::= + | - | = | < | pair