CODEWITHSUNDEEP
macroscommon-lisp
nilsi
nilsi

Reputation: 10761

Common Lisp Macro Pattern match

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.

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?

Upvotes: 2

Views: 1353

Answers (2)

acelent
acelent

Reputation: 8135

I remember answering to a pattern matching question, but in a functional way: compare lists using wild cards. The following answer keeps context from that answer.

Your macro could do something like this:

  1. Evaluate expr once into a variable;
  2. Expand each (pattern &body body) clause into invoking cmp (or your match), keeping the result in a variable, and if non-nil, run the body.

Example:

(defmacro match-pattern (expr &rest clauses)
  (let ((expr-var (make-symbol (symbol-name '#:expr)))
        (bindings-var (make-symbol (symbol-name '#:bindings))))
    `(let ((,expr-var ,expr)
           (,bindings-var nil))
       (declare (ignorable ,expr-var))
       (cond ,@(mapcar #'(lambda (clause)
                           (destructuring-bind (pattern &body body)
                               clause
                             `((setf ,bindings-var (cmp ,expr-var ,pattern))
                               (let (,@(mapcar #'(lambda (var)
                                                   `(,var (cdr (assoc ',var ,bindings-var))))
                                               (pattern-vars pattern)))
                                 ,@body))))
                       clauses)))))

Given this, you still need to:

  • Define pattern-vars;
  • Adapt cmp (or your match) to return the alist of variable bindings instead of just t when there are variables in a matching pattern.

Upvotes: 1

SK-logic
SK-logic

Reputation: 9715

The common approach to this problem is following:

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

  2. 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.

  3. 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.

Upvotes: 3

Related Questions