I'm writing a macro expansion algorithm for a programming project, and I am attempting to add an r7rs-small compliant macro expansion pass. One part of this expansion algorithm requires matching patterns.
However, I'm having difficulty coming up with a pattern-matching algorithm that deals with Scheme's repetition patterns. The given example is from the r7rs small spec, which expands let* into nested lets:
(define-syntax let*
(syntax-rules ()
((let* () body1 body2 ...)
(let () body1 body2 ...)
((let* ((name1 val1) (name2 val2) ....)
body1 body2 ...)
(let ((name1 val1))
(let* ((name2 val2) ...)
body1 body2 ...)))))
As you can see, the p ... syntax needs to be able to repeatedly match 0 or more repetitions of the pattern p.
My first attempt was:
-- This datatype is a given
data SExp = SAtom String | SPair SExp SExp | SEmpty
data Pat = PatEmpty -- ()
| PatPair Pat Pat -- (p1 . p2)
| PatWild -- _
| PatVar String -- x
| PatRepeated Pat -- p ...
| PatAtom String -- a
type MatchResult = Map String SExp
matchPat :: Pat -> SExp -> Maybe MatchResult
matchPat p e =
case (p, e) of
(PatEmpty, SEmpty) -> Just Map.empty
(PatWild, _) -> Just Map.empty
(PatVar x, _) -> Just (Map.singleton x e)
(PatAtom a, SAtom a') | a == a' -> Just Map.empty
(PatPair p1 p2, SPair e1 e2) -> do
-- This is the problem case
-- This implementation cannot handle repetitions,
-- since p1 should be able to consume parts of e2
res1 <- matchPat p1 e1
res2 <- matchPat p2 e2
Just (Map.union res1 res2)
_ -> Nothing
However, I'm skeptical that this pattern representation is good enough for implementing this kind of matching algorithm. Any help would be great.