Overview🔗

For this assignment, you are given a iniquity-plus.zip file on ELMS with a starter compiler similar to the Iniquity language we studied in class.

Rest arguments🔗

Many languages including JavaScript, C, C++, Java, Ruby, Go, PHP, and Racket provide facilities for defining functions that take a “rest argument” which allows the function to be called with more arguments than expected and these additional arguments will be bound to a single value that collects all of these arguments. In Iniquity, as in Racket, the obvious way of collecting these arguments into a single value is to use a list.

Here are some examples:

• (define (f . xs) ...): this function takes any number of arguments and binds xs to a list containing all of them,

• (define (f x . xs)  ...): this function takes at least one argument and binds x to the first argument and xs to a list containing the rest. It’s an error to call this function with zero arguments.

• (define (f x y z . xs)    ...): this function takes at least three arguments and binds 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 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: it should pass all of the arguments on the stack along with information about the number of arguments.

The compilation of function definitions that use a rest argument 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 which is then bound 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 on 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—call this m—and the caller communicates how many actual arguments have been supplied—call this n. The compiler needs to generate a loop that pops n-m times, constructing a list with with popped elements, and then finally pushes this list in order to bind it to the rest parameter.

Arity dispatch🔗

Some languages such as Java, Haskell, and Racket make it possible to overload a single function name with multiple definitions where the dispatch between these different definitions is performed based on the number (or kind) of arguments given at a function call.

In Racket, this is accomplished with the case-lambda form for constructing multiple-arity functions.

Here is an example:

Examples

> (define f     (case-lambda       [(x) "got one!"]       [(p q) "got two!"]))

> (f #t)

"got one!"

> (f #t #f)

"got two!"

> (f #t #f 0)

f: arity mismatch;

the expected number of arguments does not match the given

number

given: 3

This function can accept either one or two arguments. If given one argument, it evaluates the right-hand-side of the first clause with x bound to that argument. If given two arguments, it evaluates the right-hand-side of the second clause with p and q bound to the arguments. If given any other number of arguments, it signals an error.

A case-lambda form can have any number of clauses (including zero!) and the first clause for which the number of arguments is acceptable is taken when the function is called.

Note that case-lambda can be combined with rest arguments too. A clause that accepts any number of arguments is written by simply listing a parameter name (no parentheses). A clause that accepts some non-zero minimum number of parameters is written with a dotted parameter list.

For example:

Examples

> (define f     (case-lambda       [(x y z . r) (length r)]       [(x) "just one!"]))

> (f 1 2 3 4 5 6)

3

> (f #t)

"just one!"

> (f)

f: arity mismatch;

the expected number of arguments does not match the given

number

given: 0

> (f 1 2)

f: arity mismatch;

the expected number of arguments does not match the given

number

given: 2

This function takes three or more arguments or one argument. Any other number of arguments (i.e. zero or two) results in an error.

Examples

> (define f     (case-lambda       [(x y z) "three!"]       [xs (length xs)]))

> (f)

0

> (f 1 2)

2

> (f 1 2 3)

"three!"

> (f 1 2 3 4 5 6)

6

This function takes any number of arguments, but when given three, it produces "three!"; in all other cases it produces the number of arguments.

Representing the syntax of function definitions🔗

The Iniquity language has a single function definition form: (define (f x ...) e) which is represented with the following AST type:

; type Defn = (Defn Id (Listof Id) Expr)

(struct Defn (f xs e) #:prefab)

Because there are three different forms of function definition in Iniquity+, we use the following AST representation:

; type Defn = (Defn Id Fun)

(struct Defn (f fun) #:prefab)

; type Fun = (FunPlain [Listof Id] Expr)

;          | (FunRest [Listof Id] Id Expr)

;          | (FunCase [Listof FunCaseClause])

; type FunCaseClause = (FunPlain [Listof Id] Expr)

;                    | (FunRest [Listof Id] Id Expr)

(struct FunPlain (xs e)   #:prefab)

(struct FunRest  (xs x e) #:prefab)

(struct FunCase  (cs)     #:prefab)

What used to be represented as (Defn f xs e) is now represented as (Defn f (FunPlain xs e)).

The parser already works for these new forms of function definitions. Here are some examples of how function definitions are parsed, but you are encouraged to try out more to get a better sense:

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

'#s(Defn f #s(FunRest (x y z) q #s(Var q)))

> (parse-define     '(define f        (case-lambda          [(x y) 2]          [(z) 1]          [(a b c . d) "3+"]          [q "other"])))

'#s(Defn     f     #s(FunCase        (#s(FunPlain (x y) #s(Lit 2))         #s(FunPlain (z) #s(Lit 1))         #s(FunRest (a b c) d #s(Lit "3+"))         #s(FunRest () q #s(Lit "other")))))

Starter code🔗

The compiler code given to you is just an implementation of Iniquity, but updated to parse the new forms of function definitions and re-organized slightly to match the new AST representation.

The interpreter code given to you works on the full Iniquity+ language, so you do not need to update interp.rkt and can use the interpreter to guide your implementation of the compiler.

Examples

> (interp     (parse '(define (f x) x)            '(f 1)))

1

> (interp     (parse '(define (f . x) x)            '(f 1)))

'(1)

> (interp     (parse '(define (f . x) x)            '(f)))

'()

> (interp     (parse '(define (f . x) x)            '(f 1 2 3 4 5)))

'(1 2 3 4 5)

> (interp     (parse '(define f               (case-lambda                 [(x y) 2]                 [(z) 1]                 [(a b c . d) "3+"]                 [q "other"]))            '(cons (f 7)               (cons (f 3 4)                 (cons (f)                   (cons (f 7 8 9 10 11)                         '()))))))

'(1 2 "other" "3+")

Thus, you should only need to modify compile.rkt.

A small number of test cases are given as usual.

Submitting🔗

To submit, use make from within the iniquity-plus directory to create a zip file containing your work and submit it to Gradescope.