Scheme syntax-rules pattern matching algorithm

Viewed 99

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.

0 Answers
Related