Pattern match function in Scheme Meta Circular Evaluator

Question

I'm trying to add a pattern matching function to an existing scheme meta circular evaluator (this is homework) and I'm a bit lost on the wording of the instructions. I was hoping someone more skilled in this regard could help me interpret this.

The syntax for match should look like the following: (match a ((p1 v1) (p2 v2) (p3 v3)))

And it could be used to find length like so:

(define length (lambda (x)
   (match x (('() 0)
             (('cons a b) (+ 1 (length b))))))

The pattern language in the function should contain numeric constants, quoted constants, variables, and cons. If patterns are exhausted without finding a match, an error should be thrown.

I thought I understood the concept of pattern matching but implementing it in a function this way has me a bit thrown off. Would anyone be willing to explain what the above syntax is doing (specifically, how match is used in length above) so I can get a better understanding of what this function should do?

Is this actually supposed to be a function, or a macro/source transformation? — Joshua Taylor, Feb 25 '15 at 22:01

score 1 · Answer 1 · edited Feb 25 '15 at 22:02

1

I suggest you read the chapter four, Structured Types and the Semantics of Pattern Matching, from The Implementation of Functional Languages. The chapter is written by Simon L. Peyton Jones and Philip Wadler.

edited Feb 25 '15 at 22:02

Joshua Taylor

84,998
9
154
353

answered Feb 25 '15 at 19:49

soegaard

30,661
4
57
106

The chapter shows the rewrite rules needed to implement a pattern matcher. – soegaard Feb 26 '15 at 12:47

score 1 · Answer 2 · answered Feb 25 '15 at 21:59

(match x (('() 0)
          (('cons a b) (+ 1 (length b)))))

It may be most helpful to consider what this code would need to expand into. For each pattern, you'd need a test to determine whether the object you're trying to match matches, and you'd need code to figure out how to bind variables to its subparts. In this case, you'd want an expansion roughly like:

(if (equal? '() x)
    0
    (if (pair? x)
        (let ((a (car x))
              (b (cdr x)))
          (+ 1 (length b)))
        ;; indicate failure to match
        'NO-MATCH))

You could write that with a cond, too, of course, but if you have to procedurally expand this, it might be easier to use nested if forms.

If you're actually implementing this as a function (and not as a macro (i.e., source transformation), then you'll need to specify exactly how you can work with environments, etc.

Pattern match function in Scheme Meta Circular Evaluator

2 Answers2