Assignment 8: Patterns
Due: Tuesday, December 9, 11:59PM
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.
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
compile.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)
These are not directly useful in implementing the patterns above, but do make it easier to write examples and tests.
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
Representing the syntax of patterns
The AST of patterns is extended as follows:
; type Pat = ... ; | (List [Listof Pat]) ; | (Vect [Listof Pat]) ; | (Pred Id)
The parser includes a parse-pattern function that parses a single pattern:
Examples
> (parse-pattern 'x) '#s(Var x)
> (parse-pattern '(cons x y)) '#s(Cons #s(Var x) #s(Var y))
> (parse-pattern '(list x y z)) '#s(List (#s(Var x) #s(Var y) #s(Var z)))
> (parse-pattern '(vector x y z)) '#s(Vect (#s(Var x) #s(Var y) #s(Var z)))
> (parse-pattern '(? f?)) '#s(Pred 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.