PLAI Typed S-Sxpression Matching

8.12

PLAI Typed S-Sxpression Matching🔗ℹ

(require plai-typed/s-exp-match)
	package: plai-typed-s-exp-match

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.

value
s-exp-match? : (s-expression s-expression -> boolean)

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:

`NUMBER — matches any number S-expression
`STRING — matches any string S-expression
`SYMBOL — matches any symbol S-expression
`ANY — matches any S-expression
`... — within a list S-expression, matches any number of repetitions f the preceding S-expression within the list; only one `... can appear as an immediate element of a pattern list, and `... is not allowed within a pattern outside of a list or as the first element of a list

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)