What algorithm is used in Scheme for pattern matching in syntax-case?

Question

R. Kent Dybvig in his Writing Hygienic Macros in Scheme with Syntax-Case paper (p. 9) uses this example to illustrate Scheme's pattern matching:

(define-syntax let1
  (lambda (x)
    (syntax-case x ()
     ((((i v) ...) e1 e2 ...)
      (syntax ((lambda (i ...) e1 e2 ...) v ...))))))

I'm curious, what is the algorithm used for matching it? I am aware of the existence of different pattern matching algorithms, but here it seems that the algorithm needs to be something very simple given the very restricted nature of the patterns (unique identifiers, very simple grammar), but I was not able to find any references describing it in greater detail.

In the example above e1 e2 ... is quite simple, since it can be matched as-is or by the subpattern e2 ... alone (?). The part ((i v) ...) is more tricky as it doesn't match directly i ... nor v ..., so here it can either do some more complex matching or just considers it as "the other ellipsis".

• What exactly is the algorithm?
• Where I could find more information on it?

Answer 1

I seem to have found the answer in the papers Writing Macros in Continuation-Passing Style by Erik Hilsdale and Daniel P. Friedman, Macro-by-Example by Eugene E. Kohlbecker and Mitchell Wand, and Syntactic Abstraction: The syntax-case expander by R. Kent Dybvig.

My mistake was misunderstanding the meaning of the .... I assumed it is a wildcard for "anything that follows", while in fact e2 ... and (i v) ... should be read as "PATTERN and the following elements alike". In such a case e1 e2 ... matches the series of one or more e[j] objects, while (i v) ... matches a series of (i v)[j] pairs so that the elements can be extracted individually like i[j]... and v[j]... if we abuse the notation and add indexes in the square brackets.

So indeed the matching algorithm is rather simple: it matches the literals as-is, matches objects with keywords, matches the structures creating subpatterns (lists), but also has ... for "the last pattern can be repeated". As noticed by mnemenaut in the comment (+1), the more complicated and interesting part is rather expanding the templates with the pattern, as described in the mentioned papers.