Homework 6 - Apply, variadic functions

Assignment Instructions

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.

Introduction

In this homework you'll extend the function calls developed in class with two additional features:

The apply operation 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 apply, we'll switch to dynamic arity checking, checking the number of arguments at runtime.

We recommend implementing these features in the order described below.

Starting point

The starting language for this assignment includes nil (()) from homework 4. It also includes a unary operator empty? that returns true if its argument is () and false otherwise.

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`

Implement 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

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 6) or (add 1 2 3 4) (which returns 10), or even (apply add (pair 1 (pair 2 ()))) (which returns 3).

The ... 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)

When f's body is executed, a is 1, b is 2, and c is (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 rest field, 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 args of ["a"] and rest of Some("b").

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 Symtab.cardinal function helpful. It returns the number of bindings in a symbol table.

Grammar

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