Assignment 5: Patterns

Due: Monday, May 6, 11:59PM EST

The goal of this assignment is to extend a compiler with new pattern matching forms for matching lists, vectors, and predicates.

You are given a file knock-plus.zip on ELMS with a starter compiler similar to the Knock language we studied in class. You are tasked with:

• implementing the list pattern,

• implementing the vector pattern, and

• implementing the ? pattern.

Unlike previous assignments, you do not need to bring forward your past features to this language; there is no need to implement cond, case, etc.

The following files have already been updated for you and should not be changed by you:

• ast.rkt

• parse.rkt

• interp.rkt

• interp-prim.rkt

• compile-op.rkt

As a convenience, two new n-ary primitives have been added (and fully implemented): list and vector. The list primitive takes any number of arguments and produces a list containing the arguments as elements; the vector primitive does the same, but constructs a vector.

Examples

> (list)

'()

> (list 1 2 3)

'(1 2 3)

> (list 1 #t #\c)

'(1 #t #\c)

> (vector)

'#()

> (vector 1 2 3)

'#(1 2 3)

> (vector 1 #t #\c)

'#(1 #t #\c)

List patterns

The (list p1 ... pn) pattern matches a list of elements. The pattern matches a list with as many elements as there are patterns p1 through pn and each element must match the respective pattern.

Examples

> (match (list)     [(list) #t]     [_ #f])

#t

> (match (list 1 2 3)     [(list x y z) x])

1

> (match (list (list 1) (list 2))     [(list (list x) (list 2)) x])

1

Vector patterns

The (vector p1 ... pn) pattern matches a vector of elements. The pattern matches a vector with as many elements as there are patterns p1 through pn and each element must match the respective pattern.

Examples

> (match (vector)     [(vector) #t]     [_ #f])

#t

> (match (vector 1 2 3)     [(vector x y z) x])

1

> (match (vector (vector 1) (vector 2))     [(vector (vector x) (vector 2)) x])

1

Predicate patterns

The (? f) pattern matches any value for which the predicate f returns a true value (any value other than #f) when applied to the value being matched. In Knock+, f must be the name of a user defined function.

Examples

> (define (is-eight? x) (= x 8))

> (define (id x) x)

> (match 8     [(? is-eight?) #t]     [_ #f])

#t

> (match (vector 1 2 3)     [(and (? id) x) x])

'#(1 2 3)

> (match 16     [(? is-eight?) #t]     [_ #f])

#f

Submitting

Submit a zip file containing your work to Gradescope. Use make submit.zip from within the knock-plus directory to create a zip file with the proper structure.