PLAI Typed S-Sxpression Matching
s-exp-match?
7.0

PLAI Typed S-Sxpression Matching

The plai-typed/s-exp-match library provides a single function, s-exp-match?, for checking that an S-expression has a particular shape, where the shape is described by a pattern that is also represented as an S-expression.

Compares the first S-expression, a pattern, to the second S-expression, a target.

To a first approximation, s-exp-match? is just equal? on the two S-expressions. Unlike equal?, however, certain symbols in the pattern and can match various S-expressions within the target.

For example, `NUMBER within a pattern matches any number in corresponding position within the target:

(test (s-exp-match? '(+ NUMBER NUMBER) '(+ 1 10))
      true)
(test (s-exp-match? '(+ NUMBER NUMBER) '(+ 1 x))
      false)
(test (s-exp-match? '(+ NUMBER NUMBER) '(- 1 10))
      false)

The following symbol S-expressions are treated specially within the pattern:

Any other symbol in a pattern matches only itself in the target. For example, `+ matches only `+.

(test (s-exp-match? `NUMBER '10)
      true)
(test (s-exp-match? `NUMBER `a)
      false)
(test (s-exp-match? `SYMBOL `a)
      true)
(test (s-exp-match? `SYMBOL '"a")
      false)
(test (s-exp-match? `STRING '"a")
      true)
(test (s-exp-match? `STRING '("a"))
      false)
(test (s-exp-match? `ANY '("a"))
      true)
(test (s-exp-match? `ANY '10)
      true)
(test (s-exp-match? `any '10)
      false)
(test (s-exp-match? `any `any)
      true)
 
(test (s-exp-match? '(SYMBOL) '(a))
      true)
(test (s-exp-match? '(SYMBOL) '(a b))
      false)
(test (s-exp-match? '(SYMBOL SYMBOL) '(a b))
      true)
(test (s-exp-match? '((SYMBOL) SYMBOL) '((a) b))
      true)
(test (s-exp-match? '((SYMBOL) NUMBER) '((a) b))
      false)
(test (s-exp-match? '((SYMBOL) NUMBER ((STRING))) '((a) 5 (("c"))))
      true)
(test (s-exp-match? '(lambda (SYMBOL) ANY) '(lambda (x) x))
      true)
(test (s-exp-match? '(lambda (SYMBOL) ANY) '(function (x) x))
      false)
 
(test (s-exp-match? '(SYMBOL ...) '(a b))
      true)
(test (s-exp-match? '(a ...) '(a b))
      false)
(test (s-exp-match? '(a ...) '(a a))
      true)
(test (s-exp-match? '(a ...) '())
      true)
(test (s-exp-match? '(a ... b) '())
      false)
(test (s-exp-match? '(a ... b) '(b))
      true)
(test (s-exp-match? '(a ... b) '(a a a b))
      true)
(test (s-exp-match? '((a ...) b ...) '((a a a) b b b b))
      true)
(test (s-exp-match? '((a ...) b ...) '((a a a) b c b b))
      false)