Common Lisp Macro Pattern match

Question

Been working on a macro for homework for a long time now but we are completely stuck, my teacher has limited time, and the deadline is far over the limit. This is our last try to solve this one.

The description is as follows:

We are gonna write a macro match-pattern that matches parameter expr against a number of parameters pattern_i. If it succeeds body_i is evaluated with the free variables in pattern_i bound during the evaluation.

A pattern is a s-expression
It must match exactly
The symbol quote can not be used

Expr should only be evaluated once

Example:

   * (match-pattern '((foo bar) foo baz)
        ((car . car)     `(:cons ,car ,car))
        ((one two three) `(:three ,one ,two ,three)))

   (:THREE (FOO BAR) FOO BAZ)

Our tactic so far is something like this:

1

A match function that we planned to use in the macro for comparing patterns. (Maybe not completely right but you getting the point)

    (defun match (sexpr1 sexpr2)
      (cond ((and (consp sexpr1) (consp sexpr2)) 
             (and (match (first sexpr1) (first sexpr2))
                  (match (rest sexpr1)  (rest sexpr2))))
            ((and (atom sexpr1) (atom sexpr2))
             t)
            (t nil)))

2

We want to loop all the patterns against expr, and by passing them to our match function we will get back true or nil. If it's true we assign expr to the body of the pattern.

(defmacro match-pattern (sexpr &body body)
  (cond
    ((match sexpr (car (car body))) (print "sexpr shall match with body here"))
    ((null (cdr body)) nil)
    (t `(match-pattern sexpr ,@(cdr body)))))

3

Don't know how the matching is intended to work, we tried to use #'mapcar in combination with an anonymous lambda function but didn't get further than that.

Does this seem like a reasonable approach? Having a lot of problem with quotes. In the Example in the description there is a quote on expr but not on the ones in the patterns in the body, why is this? And why are there:three and :cons in the body?

SK-logic SK-logic · Accepted Answer · 2013-01-20T13:27:49

The common approach to this problem is following:

Expand your matchers into a more elaborate intermediate representation, for example, a pattern and action pair (('a b) b) is translated into (match-action V1 (match-cons (match-quote a) (match-cons (match-bind b) (match-nil))) (progn b)).
Implement a simpler macro match-action, which unrolls a tree of commands into a sequence of nested bindings and checks. Each failing check returns a special failure value. For example, (match-action V1 (match-bind x) x) is expanded into (let ((x V1)) x), or (match-action V1 (match-cons (match-bind a) (match-bind b)) (cons b a)) is expanded into (if (listp V1) (let ((V2 (car V1)) (V3 (cdr V1)) (a V2) (b V3)) (cons b a)) match-failure). Note that match-bind command must check if its argument is already in the context, and in this case it should translate into a structural equality check.
Now, implementing a match macro is trivial - introduce a new variable (with gensym), bind it to the value of your expression, and apply matchers in sequence unless a matcher returns something different from match-failure.

I hope it's sufficient for you to implement your own matcher. Note that this approach is extensible, you can add more complicated patterns, like ellipsis, function matchers, regexps, and so on.

Common Lisp Macro Pattern match

2 Answers