match-abs

[Stefan Israelsson Tampe]

Hi,

I've hacked on extension on ice-9/match for making modular matching possible
with a reasonable interface. Here is an example,

;; new version of match with modular matching abatractions see 
;; http://gitorious.org/guile-unify/guile-
unify/blobs/master/module/ice-9/match-abs.scm
(use-modules (ice-9 match-abs))

;;Example, notice ((<op> A B)) means first result of <op> is stored in A and 
the second is in B
(define (<op> X)
  (match abstractions ((<op> A B))
         X
         (['- <op> <op>  . L]  (cons  (- B A)  L))
         (['+ <op> <op>  . L]  (cons  (+ A B)  L))
         (['* <op> <op>  . L]  (cons  (* A B)  L))
         (['/ <op> <op>  . L]  (cons  (/ B A)  L))
         ([(? number? X) . L]  (cons     X     L))
         (_                    (cons    #f    #f))))

;;alternatively one can use the more general but wordy <> notation
(define (<op> X)
  (match X
         (['- (<> <op> A) (<> <op> B)  . L]  (cons  (- A B)  L))
         (['+ (<> <op> A) (<> <op> B)  . L]  (cons  (+ A B)  L))
         (['* (<> <op> A) (<> <op> B)  . L]  (cons  (* A B)  L))
         (['/ (<> <op> A) (<> <op> B)  . L]  (cons  (/ A B)  L))
         ([(? number? X) . L]  (cons     X     L))
         (_                    (cons    #f    #f))))

(define (rpn x) (car (<op> (reverse x))))

;;and (rpn '(2 4 * 1 -)) evaluates to 7


So e.g. the protocol for a matcher is that the last argument for a matcher
is the list to match on. The matcher should return a cons cell, if the car
element is false the match fails and else it is the value of the match. the 
second argument represent the rest of the list after the match has been 
removed. 

More examples, this is a gready matcher that tries to match as much as 
possible
It has a curry feature thats cool.

(define (<*> <a> . r)
  (define (f x res)
    (let ((ret (<a> x)))
      (if (car ret)
          (f (cdr ret) (cons (car ret res)))
          (cons (reverse res) x))))
  (if (pair? r)
      (f (car r) '())
      (lambda (l) (f l '()))))


(define (<alternate> <a> <b> l)
  (match abstractions ((<a> a1 a2)(<b> b1 b2))
         l  
         ([<a> <b> <a> <b> . ls]  (cons (apend a1 a2 b1 b2) ls))
         (_                       (cons #f #f))))


and now we can do something like this thanks to the currying

(match abstractions ((<alternate> alt) (<*> m3))
       X
       ((<alternate> (<*> <match1>) (<*> <match2>) (<*> <match3>))
        (append m3 alt)))

Note here <match1>, ... , <match3> are all function arguments and does not
represent a part of the match hence these abstractions are not mensioned
at the abstraction definitions also the first two <*> is at function postions 
and also in function position. also this means that (<*> <match1>) will need
to use the currying feature of <*> in order to function correctly. So here we 
se a nice application of currying.

(match abstractions ((<alternate> alt) (<*> m3))
       X
       ((<> (<alternate> (<*> <match1>) (<*> <match2>) alt)(<*> <match3>))
        (append m3 alt)))

Using <> things gets clearer.


So Is this something that can be of any interests? It's been a good exercise
in syntax-case macro writing and I do feel like I'm mastering the ice-9 match
that we are currently working on so however we choose, we do not loose.

Note 1, I've used a similar tool in parsing prolog, but I do not use this for
operatore precedence handling.

Note 2. One can device a proper backtracking methodology so that we could
have matched  (bbbbbbba) with matcher ((<*> <b>) 'b 'a), where <b> matches b, 
(<*> <b>) will consume all the b:s and not backtrack when the rest fails 
((and 'b bs) ... 'b 'a) will do the trick though!)
but I feel that using prolog or the scheme version of it (schelog?) in the 
first place is a better tool to achive this. One need to play with 
continuatons
very much like working with the prolog code I made. If you like I can make 
that
work and/or.

Note 3 using (defmacro (/. p r) 
               `(lambda (l) (match l 
                                   ((,p . l) (cons ,r  l)) 
                                   (_       (cons #f #f)))))
or a correct define-syntax version of it means that we could write a matcher
like ((<*> (/. 'b 'b)) 'b 'a) in the above syntax

Cheers
Stefan