These exercises are to write extensions to the pattern matcher defined in class. To do them, you need to download and load into Lisp match.lisp. This creates two packages:

To do the exercises

To test any particular exercise, just run the tests for that specific pattern extension. But before submitting your answers, do (run-tests) with no arguments, to run all the match tests. Make sure that all tests pass, except those for any exercise you haven't done yet.

A few examples are given here of each extension, but there are far many more tests in match.lisp. Study those tests before coding an answer. Also study how the existing extensions, such as ?and and ??, work as well.


MATCH-NOT, MATCH-OR, MATCH-=

Define the pattern function ?not such that the pattern (?not pattern) matches an input if and only if pattern does not match that input.

> (match-p '(?not ?x) 'a)
NIL
> (match-p '(?x (not ?x)) '(a b))
(((?X . A)))

Define the pattern function ?or such that the pattern (?or pattern1 pattern2 ...) returns bindings for every pattern that matches the input.

> (match-p '(?or a b) 'b)
(NIL)
> (match-p '(?or a b) 'c)
NIL
> (match-p '(?x ?y (?or ?x ?y ?z)) '(a b a))
(((?Y . B) (?X . A)) ((?Z . A) (?Y . B) (?X . A)))

Define the pattern function ?= -- "assign" -- so that matching the pattern (?= sub-pattern function-name argument1 argument2 ...) against an input form will first call (function-name form argument1 argument2 ...), and then match sub-pattern against the result.

> (defun square (x) (* x x))
SQUARE
> (defun contains (x y) (and (stringp x) (search y x)))
CONTAINS
> (match-p '(?= ?x square) 3)
(((?X . 9)))
> (match-p '(?= (?not nil) contains "foo") "some food")
(NIL)
> (match-p '(?= (?not nil) contains "foo") "some drink")
NIL

MATCH-CONTAINS

Define the pattern function ?contains such that the pattern (?contains pattern) matches an input if and only if pattern matches the input or some subexpression of the input.

Note: the order of variable bindings doesn't matter.
> (match-p '(?contains ?x) 'a)
(((?X . A)))
> (match-p '(?contains (?and (?? numberp) ?x)) '((a 12) c (((5)))))
(((?X . 5)) ((?X . 12)))

Faculty: Chris Riesbeck
Time: Monday, Wednesday, Friday: 1pm - 2pm
Location:Annenberg G15

Contents

Important Links