Project
The final assessment for this course consists of an individually completed project that is split into two parts: implementing some extensions to functions (worth 40% of the final project grade) and implementing the new features of exceptions and exception handling (worth 60% of the final project grade).
We will provide you with more detailed instructions and starter code for the function extension part, while purposefully having higher-level instructions and minimal starter code for the exception handling part. This decision is purposeful, to give you the opportunity to exercise your compiler design chops and good judgment.
The starter code, which is based on Loot, is available on ELMS in the Final Project assignment text. Note that you do not need to bring forward features from past assignments, and we have already provided the necessary AST and parser code with a matching interpreter so you can focus on implementing the compiler.
Please be sure to read the entire problem description before starting. We’ve included a number of Suggestions on how to approach the assignment near the end.
Due: Monday, May 19, 12:30PM
Arity Checking, Rest Arguments, and Apply
This part of the project asks you to extend a modified Loot compiler with the following features:
Run-time arity checking for function calls (i.e., raising a error when a function is called with an incompatible number of arguments).
Variadic (variable-arity) functions using a “rest parameter”.
The apply function, which allows for applying a function to a dynamically computed list of arguments.
Checking arity
In Iniquity, we implemented a language with function definitions and calls. We noted that bad things can happen when a function is called with the incorrect number of arguments. While it’s possible to statically check this property of Iniquity programs, it’s not possible in more expressive languages, so arity checking must be done at run-time. You are tasked with implementing such a run-time arity checking mechanism.
Here is the basic idea: You need to add a run-time checking mechanism that will cause the following program to signal an error:
(define (f x y) (+ x y)) (f 1)
The function call knows how many arguments are given, and the function definition knows how many arguments are expected. The generated code should check that these two quantities match when the function call is executed.
A simple way to do this is to pick a designated register that will be used for communicating arity information. The caller should set the register to the number of arguments before jumping to the function. The function should check this number against the expected number and signal an error when they don’t match.
Since we’re using Loot for this project, there are two places to update the caller code: compile-app-tail and compile-app-nontail. These two functions are responsible for generating the jumps into a function body, so these are where we will update our designated arity checking register with the number of arguments received at run-time.
The function body definition will also need to be updated. In Loot, this will be done in compile-lambda-define.
No changes need to be made to the parser, and the interpreter has been updated to perform arity checking; additionally, arity checking has been implemented in the compiler for the simple cases of regular application of plain functions. What is left for you to do is to ensure arity checking works in all cases, which means it needs to work for Variadic functions and Apply.
Variadic functions
Many programming languages, such as JavaScript, C, and Racket, provide facilities for defining functions that take a variable number of arguments, also called “variadic functions”. Most commonly, this is implemented by somehow distinguishing the final parameter in the function’s parameter list. When the function is called, the normal parameters are bound in the normal way, but all the additional arguments beyond those necessary for binding the normal parameters are bound to the distinguished parameter as some kind of collection that can be used as a single value within the body of the function. We will follow Racket’s example and use a list to accumulate these values.
Here are some examples:
The function (define (f . xs) ...) takes any number of arguments and binds xs toa list containing all of them.
The function (define (f x . xs) ...) takes at least one argument, binding x to the first argument and xs to a list containing the rest. It’s an error to call this function with zero arguments.
The function (define (f x y z . xs) ...) takes at least three arguments, binding x, y, and z to the first three arguments and xs to a list containing the rest. It’s an error to call this function with 0, 1, or 2 arguments.
Here are some examples using these function templates in Racket to get a sense of the behavior:
Examples
> (define (f . xs) (list xs)) > (f) '(())
> (f 1) '((1))
> (f 1 2) '((1 2))
> (f 1 2 3) '((1 2 3))
> (f 1 2 3 4) '((1 2 3 4))
> (define (f x . xs) (list x xs)) > (f) f: arity mismatch;
the expected number of arguments does not match the given
number
expected: at least 1
given: 0
> (f 1) '(1 ())
> (f 1 2) '(1 (2))
> (f 1 2 3) '(1 (2 3))
> (f 1 2 3 4) '(1 (2 3 4))
> (define (f x y z . xs) (list x y z xs)) > (f) f: arity mismatch;
the expected number of arguments does not match the given
number
expected: at least 3
given: 0
> (f 1) f: arity mismatch;
the expected number of arguments does not match the given
number
expected: at least 3
given: 1
> (f 1 2) f: arity mismatch;
the expected number of arguments does not match the given
number
expected: at least 3
given: 2
> (f 1 2 3) '(1 2 3 ())
> (f 1 2 4) '(1 2 4 ())
The code generated for a function call should not change, aside from what you did for Checking arity: it should pass all of the arguments on the stack along with information about the number of arguments.
The compilation of function definitions for variadic functions should generate code that checks that the given number of arguments is acceptable and should generate code to pop all “extra” arguments off the stack and construct a list from them, binding that list to the rest parameter.
It is worth remembering that arguments are pushed on the stack in such a way that the last argument is the element most recently pushed onto the stack (i.e., it’s “on top” of the stack). This has the benefit of making it easy to pop off the extra arguments and to construct a list with the elements in the proper order.
HINT: The function definition knows the number of “required” arguments,
i.e., the minimum number of arguments the function can be called with —
The parser and interpreter have been updated with these changes; you only need to implement the changes in the compiler. We have left TODO comments for you in the places where you need to make changes. (You are allowed to make other changes if you see fit.)
Apply
Dynamic function application is the yin to the yang of variadic functions (or maybe it’s the other way around). Whereas a rest parameter lets a function take arbitrarily many “extra” arguments and packages them as a list, apply will apply a function to a list as though the elements of the list were given as arguments normally.
Examples
> (define (f x y) (+ x y)) > (apply f (list 1 2)) 3
> (define (flatten ls) (apply append ls)) > (flatten (list (list 1 2) (list 3 4 5) (list 6))) '(1 2 3 4 5 6)
> (define (sum ls) (apply + ls)) > (sum (list 5 6 7 8)) 26
In these examples, you can see apply taking two things: a function, and a single argument, which is a list. The apply function is calling the given function, using the elements in the list as the arguments.
As it turns out, apply can also take additional arguments in addition to the list, and it passes them along to the function being called as well:
Examples
> (define (f x y) (+ x y)) > (apply f 1 (list 2)) 3
> (apply list 1 2 3 4 (list 5 6 7)) '(1 2 3 4 5 6 7)
Note that if the function expects a certain number of arguments and the list has a different number of elements, it results in an arity error:
Examples
> (define (f x y) (+ x y)) > (apply f (list 1 2 3)) f: arity mismatch;
the expected number of arguments does not match the given
number
expected: 2
given: 3
The concrete syntax for an apply expression is:
(apply ef e0 ... en)
Note that an apply expression consists of two or more sub-expressions. The first sub-expression ef must evaluate to a function, and the final sub-expression en must evaluate to a list (it is an error if it evaluates to anything other than a list). Any additional sub-expressions e0 ... can evaluate to anything at all.
While it’s allowable to have only the function and the list argument, it’s a syntax error to leave off a list argument altogether:
Examples
> (parse-e '(apply f xs)) '#s(Apply #s(Var f) () #s(Var xs))
> (parse-e '(apply f)) '#s(App #s(Var apply) (#s(Var f)))
(Note that the second example above returns an App AST node rather than an Apply node, meaning that unless the user has defined a function that is named apply, this code will fail at compile-time due to generating a reference to an undeclared label. It does not literally raise an error in Racket, although it would in a more advanced parser.)
The interpreter has been updated to handle all of this already:
Examples
> (interp (parse '(define (f x y) (cons y x)) '(apply f (cons 1 (cons 2 '()))))) '(2 . 1)
When used with variadic functions, apply makes it possible to write many functions you may like to use:
Examples
> (interp (parse ; an append that works on any number of lists '(define (append . xss) (if (empty? xss) '() (if (empty? (car xss)) (apply append (cdr xss)) (cons (car (car xss)) (apply append (cdr (car xss)) (cdr xss)))))) ; the list function! '(define (list . xs) xs) '(append (list 1 2 3) (list 4) (list 5 6 7)))) '(1 2 3 4 5 6 7)
In compile.rkt, the compile-e function now has an added case for Apply AST nodes that calls compile-apply. Your job is to complete the implementation of compile-apply in accordance with the above specification.
HINT: The apply function is very similar to a normal function call, but with some changes. The implementation should:
Generate a label for the return point and push that onto the stack.
Evaluate the first argument ef and check that it evaluates to a procedure.
Evaluate the regular arguments e0 ... and push them onto the stack.
Evaluate the list argument en, and then traverse the list at run-time, pushing the elements onto the stack until the end of the list is reached.
Execute the function in the first argument.
Exceptions and Exception Handling
Exceptions and exception handling mechanisms are widely used in modern programming languages. Implement Racket’s raise and with-handlers forms to add exception handling.
Here are the key features that need to be added:
(raise e) will evaluate e and then “raise” the value, side-stepping the usual flow of control and instead jumping to the most recently installed compatible exception handler.
(with-handlers ([p1 f1] ...) e) will install a new exception handler during the evaluation of e. If e raises an exception that is not caught, the predicates p1 ... should be applied to the raised value until finding the first pi that returns a true value, at which point the corresponding function fi is called with the raised value and the result of that application is the result of the entire with-handlers expression. If e does not raise an error, its value becomes the value of the with-handler expression.
Here are some examples to help you understand. NOTE: For our purposes, we restrict p1 ... f1 ... to be expressions, so primitive operations cannot actually be used in the place of predicates or handlers. These examples are for illustrative purposes.
Examples
> (with-handlers ([string? (λ (s) (cons "got" s))]) (raise "a string!")) '("got" . "a string!")
> (with-handlers ([string? (λ (s) (cons "got" s))] [number? (λ (n) (+ n n))]) (raise 10)) 20
> (with-handlers ([string? (λ (s) (cons "got" s))] [number? (λ (n) (+ n n))]) (+ (raise 10) 30)) 20
> (let ((f (λ (x) (raise 10)))) (with-handlers ([string? (λ (s) (cons "got" s))] [number? (λ (n) (+ n n))]) (+ (f 10) 30))) 20
> (with-handlers ([string? (λ (s) (cons "got" s))] [number? (λ (n) (+ n n))]) 'nothing-bad-happens) 'nothing-bad-happens
> (with-handlers ([symbol? (λ (s) (cons 'reraised s))]) (with-handlers ([string? (λ (s) (cons "got" s))] [number? (λ (n) (+ n n))]) (raise 'not-handled-by-inner-handler))) '(reraised . not-handled-by-inner-handler)
Notice that when a value is raised, the enclosing context is discarded. In the third example, the surrounding (+ [] 30) part is ignored and instead the raised value, 10, is given the exception handler predicates, selecting the appropriate handler.
Thinking about the implementation, what this means is that a portion of the
stack needs to be discarded —
This suggests that a with-handlers expression should stash away the current value of 'rsp. When a raise happens, it grabs the stashed-away value and installs it as the current value of 'rsp, effectively rolling back the stack to its state at the point at which the exception handler was installed. It should then jump to code that will carry out the applying of the predicates and right-hand-side functions.
Since with-handlers can be nested, you will need to maintain an arbitrarily large collection of exception handlers, each of which has a pointer into the stack and a label for the code to handle the exception. This collection should operate like a stack: each with-handlers expression adds a new handler to the handler stack. If the body expression returns normally, the top-most handler should be removed. When a raise happens, the top-most handler is popped and used.
NOTE: The requirement that your with-handlers forms can support an arbitrary number of predicate-handler clauses significantly increases the difficulty of this component of the project. To help you out, we’ve capped the value of supporting two or more clauses at 10% of this part of the project, i.e., you can get 90% of the points for the exceptions part of the project by only supporting with-handlers that have zero or one clauses.
HINT: Go slowly —
Starter code changes
We have updated the base Loot AST and parser for you. Some of these changes might be challenging to understand at first glance, so here is a brief summary of those changes with some rationale.
Arity checking does not require any changes in the AST or parser —
Variadic functions require a new function form that uses the special dot notation to distinguish the “rest parameter” from the others. To handle this, and to make distinguishing the different functions easier, we now have two top-level function definition forms and two lambda forms in the AST:
; type Defn = (Defn Id Fun) (struct Defn (f fun) #:prefab) ; type Fun = (FunPlain [Listof Id] Expr) ; | (FunRest [Listof Id] Id Expr) (struct FunPlain (xs e) #:prefab) (struct FunRest (xs x e) #:prefab) ; type Expr = ... ; | (LamPlain Id (Listof Id) Expr) ; | (LamRest Id (Listof Id) Id Expr) ... (struct LamPlain (f xs e) #:prefab) (struct LamRest (f xs x e) #:prefab)
What used to be represented as (Defn f xs e) is now represented as (Defn f (FunPlain xs e)). Similarly, what used to be represented as (Lam f xs e) is now represented as (LamPlain f xs e).
The parser has been updated to handle these forms:
Examples
> (parse-define '(define (f x) x)) '#s(Defn f #s(FunPlain (x) #s(Var x)))
> (parse-define '(define (f . xs) xs)) '#s(Defn f #s(FunRest () xs #s(Var xs)))
> (parse-define '(define (f x y z . xs) xs)) '#s(Defn f #s(FunRest (x y z) xs #s(Var xs)))
> (parse-e '(λ (x) x)) '#s(LamPlain lamplain65400 (x) #s(Var x))
> (parse-e '(λ xs xs)) '#s(LamRest lamrest65401 () xs #s(Var xs))
> (parse-e '(λ (x y z . xs) xs)) '#s(LamRest lamrest65402 (x y z) xs #s(Var xs))
Apply requires a new corresponding AST node and an extension to the parser. The new AST node has the following definition:
; type Expr = ... ; | (Apply Expr (Listof Expr) Expr) ... (struct Apply (ef es e) #:prefab)
The parser has been updated to handle concrete syntax of the form:
(apply ef e0 ... en)
For example:
Examples
> (parse-e '(apply f x y zs))
'#s(Apply
#s(Var f)
(#s(Var x) #s(Var y))
#s(Var zs))
> (parse-e '(apply f '())) '#s(Apply #s(Var f) () #s(Lit ()))
> (parse-e '(apply f 1 (cons 2 '())))
'#s(Apply
#s(Var f)
(#s(Lit 1))
#s(Prim2 cons #s(Lit 2) #s(Lit ())))
Exceptions and exception handling require new AST nodes and an extension to the parser. The new AST nodes have the following definitions:
; type Expr = ... ; | (Raise Expr) ; | (WithHandlers (Listof Expr) (Listof Expr) Expr) ... (struct Raise (e) #:prefab) (struct WithHandlers (ps hs e) #:prefab)
The parser has been updated to handle concrete syntax of the form:
(raise e)
as well as:
(with-handlers ([p h] ...) e)
For example:
Examples
> (parse-e '(raise 42)) '#s(Raise #s(Lit 42))
> (parse-e '(with-handlers () #t)) '#s(WithHandlers () () #s(Lit #t))
> (parse-e '(with-handlers ([(λ (x) (= x 42)) (λ (x) (+ x 17))]) (raise 42)))
'#s(WithHandlers
(#s(LamPlain
lamplain65403
(x)
#s(Prim2 = #s(Var x) #s(Lit 42))))
(#s(LamPlain
lamplain65404
(x)
#s(Prim2 + #s(Var x) #s(Lit 17))))
#s(Raise #s(Lit 42)))
Suggestions
This is a tricky project. The amount of code you have to write is relatively small, but you may spend a long time slogging through the project if your approach is to hack first and think later. Here are some suggestions for how to approach the project. We recommend making sure you get each of the pieces working before moving on.
Read up on Checking arity; this should be the easiest part to implement, but it requires finishing some of the other parts to even have a place to implement it, so just keep it in mind as you go on.
Move on to Variadic functions. You could start by emitting code that checks that the number of required arguments is acceptable. Then, iterate over the remaining arguments, popping the appropriate number off and ignoring their values, and then pushing the empty list as a temporary solution to bind to the rest parameter. This will work like a proper variadic function in that it should accept any number of arguments beyond the required minimum, but the rest parameter itself will always be bound to the empty list. Once this is working, modify the code to build a list as you pop the extra arguments and bind this list to the rest parameter instead. Test that it works.
For Apply, at first don’t worry about arity checking. Instead, consider the case where there are no explicit arguments given, i.e., focus first on (apply ef en). Once you have that working, consider the more general case of (apply ef e0 ... en). Then figure out how to add in the arity checking part. Finally, make sure you’re detecting error cases such as when ef is not a procedure and en is not a proper list.
After getting the rest working, implement Exceptions and Exception Handling. A good idea might be to open the Racket REPL and work through some examples of raise and with-handlers to make sure you really understand the semantics of what you’re implementing. Implement the compiler, but try to take logical, discrete steps in the implementation process (e.g., make it work for exactly one exception handler first, then generalize to arbitrarily many, and so on).
Submitting
Submit a .zip file containing your work to Gradescope. Use make submit.zip from within the loot-plus directory to create a zip file with the proper structure.