match-abs

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

      
   

Re: match-abs

[Ludovic Courtès]

Hi Stefan!

Stefan Israelsson Tampe <stefan.tampe@spray.se> writes:

> I've hacked on extension on ice-9/match for making modular matching possible
> with a reasonable interface.

That sounds like a worthy goal to me.  Pattern matching in Scheme
appears to be limited in this respect compared to other functional
languages (OCaml, Scala, & co. whose pattern matchers are effectively
extended by defining new types.)

> ;;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. 

Hmm, sorry, I don’t understand what you mean here.  Can you come up with
a simpler example?

What does ‘<>’ mean?  Is there a connection between occurrences of
‘<op>’ in patterns and the fact that the procedure is bound to ‘<op>’?

Thanks,
Ludo’.

Re: match-abs

[Ludovic Courtès]

BTW I added a small section in the manual describing (ice-9 match):

  http://git.savannah.gnu.org/cgit/guile.git/commit/?id=358663caf54994e2b7d0c2eb1dd8ce8794116971

Comments & improvements welcome!

Thanks,
Ludo’.

Re: match-abs

[Stefan Israelsson Tampe]

On Tuesday, August 31, 2010 12:55:15 am Ludovic Courtès wrote:
> Hmm, sorry, I don’t understand what you mean here.  Can you come up with
> a simpler example?
> 
> What does ‘<>’ mean?  Is there a connection between occurrences of
> ‘<op>’ in patterns and the fact that the procedure is bound to ‘<op>’?
> 
> Thanks,
> Ludo’.


Don't be sorry, Communicating is not my strongest asset.

Anyway  consider a list [a a b b] and let <a> be a function so that

(<a> [a a b b]) -> (cons [a a] [b b])
(<b> [b b])     -> (cons [b b] [])

e.g. <a> macthes a sequence of a:s and <b> macthes a sequence of b:s. a
failure in this protocol is represented by the car of the retruning cons 
beeing false.

Note, we could use a plain multiple return values protocol but that is for
later discussion.

so using match-abs we would like the following 

(match [a a b b] ((<a> <b>)  (append <b>.r <a>.r)))

to result in [b b a a].

e.g. function <a> retrurn in (cons [a a] [b b]), where <a>.r is bounded 
to the car, e.g. [a a] and [b b] is fed into the next one, <b>. For which
<b> returns (cons [b b] []), where the car, e.g. [b b] is binded to <b>.r
and the cdr is matched aginst '() and the whole match succeeds and the result
expressing is calcultaed yielding [b b a a].

Now, the construct is anaphoric and also some magic happens so that <a> is
understood as beeing a matcher abstraction.

One idea that is coded is to name the matchers and corresponding variables
that is bound to leading to the suggested 

(match abstractions ((<a> <a>.r1 <a>.r2) (<b> <b>.r))
       [a a b b a a]
       ((<a> <b> <a>)   (append <b>.r <a>.r1 <a>.r2)))

Note how we use <a> two times and the first time it is bound to <a>.r1 and the 
second time it's result is bound to <a>.r2.

Now putting some semmatics in a header can make the matchers themselves look
cleaner and save on vertical space. In match-abs there is an alternative way
of express this acording to

(match [a a b b a a]
       ([(<> <a> <a>.r1) (<> <b> <b>.r) (<> <a> <a>.r2)]
        (append <b>.r <a>.r1> <a>.r2)))

Now, this is more direct, it's simple to implement and are more general. But
The resulting matchers are much harder to read and I would personally prefere 
the header approach when using matchers in 90% of the cases.

Now the rest of the previous mail just describes that we can send parameters
down to the matcher to take full use of an abstraction. 

Another interesting extension that I think You indicate is that one might want 
to use custom variants of car,cdr,pair?,equal?

consider working of objects [List,Depth,Length]
(#car    [List,Depth,Length])   -> [(car List),(+ Depth 1),0]
(#cdr    [List,Depth,Length])   -> [(cdr List),Depth,(+ Length 1)]
(#pair?  [List,Depth,Length])   -> (pair? List)
(#equal? [List,Depth,Length] A) -> (equal? List A)

Now just generate the usual matcher and search and replace and we can track
position and depth as we match. Kind of cool!

Regards
Stefan

Re: match-abs

[Stefan Israelsson Tampe]

On Tuesday, August 31, 2010 04:42:36 pm Ludovic Courtès wrote:
> BTW I added a small section in the manual describing (ice-9 match):
> 
>  
> http://git.savannah.gnu.org/cgit/guile.git/commit/?id=358663caf54994e2b7d0
> c2eb1dd8ce8794116971
> 
> Comments & improvements welcome!
> 
> Thanks,
> Ludo’.

I agree with the TODO: e.g. more examples are needed. But I think that we 
should write a proper match-test.scm for unit testing. We can then extract 
some
examples from this file into the documentation.

/Stefan

Re: match-abs

[Ludovic Courtès]

Hi!

Stefan Israelsson Tampe <stefan.tampe@spray.se> writes:

[...]

> But I think that we 
> should write a proper match-test.scm for unit testing.

Let your dreams come true: it’s already there!  :-)

Thanks,
Ludo’.

Re: match-abs

[Ludovic Courtès]

Hi Stefan,

Stefan Israelsson Tampe <stefan.tampe@spray.se> writes:

> Anyway  consider a list [a a b b] and let <a> be a function so that
>
> (<a> [a a b b]) -> (cons [a a] [b b])
> (<b> [b b])     -> (cons [b b] [])
>
> e.g. <a> macthes a sequence of a:s and <b> macthes a sequence of b:s. a
> failure in this protocol is represented by the car of the retruning cons 
> beeing false.

OK.

> Note, we could use a plain multiple return values protocol but that is for
> later discussion.
>
> so using match-abs we would like the following 
>
> (match [a a b b] ((<a> <b>)  (append <b>.r <a>.r)))
>
> to result in [b b a a].

OK, but...

In (ice-9 match), a pattern like ‘(a b)’ matches any 2-element list and
binds the first element to ‘a’ and the second to ‘b’.

To match 2-element lists where each element satisfies a certain
predicate, say ‘p’, and bind the elements to ‘a’ and ‘b’, one must write
‘((and (? p) a) (and (? p) b))’.

The syntax you suggest here departs from this, right?

[...]

> One idea that is coded is to name the matchers and corresponding variables
> that is bound to leading to the suggested 

Parse error.  :-)

Could you rephrase this sentence?

> (match abstractions ((<a> <a>.r1 <a>.r2) (<b> <b>.r))
>        [a a b b a a]
>        ((<a> <b> <a>)   (append <b>.r <a>.r1 <a>.r2)))

What’s ‘abstractions’ here?  Is it the name of a variable, and if so
what’s its value?  Is it a literal ‘abstraction’ interpreted as magic by
the ‘match’ macro?

> Note how we use <a> two times and the first time it is bound to <a>.r1 and the 
> second time it's result is bound to <a>.r2.
>
> Now putting some semmatics in a header can make the matchers themselves look
> cleaner and save on vertical space. In match-abs there is an alternative way
> of express this acording to
>
> (match [a a b b a a]
>        ([(<> <a> <a>.r1) (<> <b> <b>.r) (<> <a> <a>.r2)]
>         (append <b>.r <a>.r1> <a>.r2)))

Hmm.  So IIUC, the sub-pattern ‘(<> <a> <a>.r1)’ matches anything that
is a match according to custom matcher ‘<a>’, and binds the sub-match
‘r1’ of ‘<a>’ to ‘<a>.r1’, right?

Tricky...

Thanks,
Ludo’.

Re: match-abs

[Stefan Israelsson Tampe]

On Thursday, September 02, 2010 05:59:59 pm Ludovic Courtès wrote:
> Hi Stefan,
> 
> Stefan Israelsson Tampe <stefan.tampe@spray.se> writes:
> > Anyway  consider a list [a a b b] and let <a> be a function so that
> > 
> > (<a> [a a b b]) -> (cons [a a] [b b])
> > (<b> [b b])     -> (cons [b b] [])
> > 
> > e.g. <a> macthes a sequence of a:s and <b> macthes a sequence of b:s. a
> > failure in this protocol is represented by the car of the retruning cons
> > beeing false.
> 
> OK.
> 
> > Note, we could use a plain multiple return values protocol but that is
> > for later discussion.
> > 
> > so using match-abs we would like the following
> > 
> > (match [a a b b] ((<a> <b>)  (append <b>.r <a>.r)))
> > 
> > to result in [b b a a].
> 
> OK, but...
> 
> In (ice-9 match), a pattern like ‘(a b)’ matches any 2-element list and
> binds the first element to ‘a’ and the second to ‘b’.

Yeah, the <> construct is much more into line with the idea of match. My 
point is that it can be a bit tough on the eyes to see the overall 
pattern and I was suggesting prepair things in a header so that we still
have some hygiene. But the header approach is more error prone to typos
so <> is good for typos and header is good for logical errors.
 
> To match 2-element lists where each element satisfies a certain
> predicate, say ‘p’, and bind the elements to ‘a’ and ‘b’, one must write
> ‘((and (? p) a) (and (? p) b))’.

I think that (? p a) may be enough work :-)

> The syntax you suggest here departs from this, right?

It has a pointwise compainon in
(= f (? id a)) 
if I'm not misstaken though.
(take  (define (f x) (match x ('a 'a) (_  #f))) and we have an obfuscation
of an 'a match ... oh well a is bound to a' :-))
	
> [...]
> 
> > One idea that is coded is to name the matchers and corresponding
> > variables that is bound to leading to the suggested
> 
> Parse error.  :-)
> 
> Could you rephrase this sentence?

Here comes an idea (implemented but not solid in match-abs). Consider 
describing a syntax element <a> in a header as beeing special so that it 
can stand by it self in the matcher without a surrounding context form.
purist may not like it but it helps in spotting logical errors in longer
matchers. Now this syntactic elements will bind a variable so let us use 
a header of the form ((<a> a1 a2) ...) to mean that in a matcher the result
of the first match <a> is bound to a1, the second to a2 etc. Let's call
this header abstractions and get a match for like ....

 
> > (match abstractions ((<a> <a>.r1 <a>.r2) (<b> <b>.r))
> > 
> >        [a a b b a a]
> >        ((<a> <b> <a>)   (append <b>.r <a>.r1 <a>.r2)))
> 
> What’s ‘abstractions’ here?  Is it the name of a variable, and if so
> what’s its value?  Is it a literal ‘abstraction’ interpreted as magic by
> the ‘match’ macro?

see above.

> > Note how we use <a> two times and the first time it is bound to <a>.r1
> > and the second time it's result is bound to <a>.r2.
> > 
> > Now putting some semmatics in a header can make the matchers themselves
> > look cleaner and save on vertical space. In match-abs there is an
> > alternative way of express this acording to
> > 
> > (match [a a b b a a]
> > 
> >        ([(<> <a> <a>.r1) (<> <b> <b>.r) (<> <a> <a>.r2)]
> >        
> >         (append <b>.r <a>.r1> <a>.r2)))
> 
> Hmm.  So IIUC, the sub-pattern ‘(<> <a> <a>.r1)’ matches anything that
> is a match according to custom matcher ‘<a>’, and binds the sub-match
> ‘r1’ of ‘<a>’ to ‘<a>.r1’, right?

yes

> Tricky...

This do the trick :-)

((match-two abs v ((<> (f ...) p) . l) g+s sk fk i)
     (let ((res (f ... v)))
       (if (car res)
           (match-one abs (car res) g+s 
                      (match-one (cdr res) l g+s sk fk)
                      fk i)
           (isert-abs abs fk))))

But now I think it should be 
((match-two abs v ((<> f p) . l) g+s sk fk i)
     (let ((res (f v)))
       (if (car res)
           (match-one abs (car res) g+s 
                      (match-one (cdr res) l g+s sk fk)
                      fk i)
           (isert-abs abs fk))))

and demand currying in the protocol!

> Thanks,
> Ludo’.

Have fun!
Stefan

Re: match-abs

[Stefan Israelsson Tampe]

On Thursday, September 02, 2010 05:59:59 pm Ludovic Courtès wrote:
> Hmm.  So IIUC, the sub-pattern ‘(<> <a> <a>.r1)’ matches anything that
> is a match according to custom matcher ‘<a>’, and binds the sub-match
> ‘r1’ of ‘<a>’ to ‘<a>.r1’, right?

Hmm maybe need to clarify
<a>.r1 is just a variable name <a> is a function. So
(<> match-fkn pattern) is the ideom here!

/Stefan

Re: match-abs

[Ludovic Courtès]

Hi!

Stefan Israelsson Tampe <stefan.tampe@spray.se> writes:

> On Thursday, September 02, 2010 05:59:59 pm Ludovic Courtès wrote:
>> Hmm.  So IIUC, the sub-pattern ‘(<> <a> <a>.r1)’ matches anything that
>> is a match according to custom matcher ‘<a>’, and binds the sub-match
>> ‘r1’ of ‘<a>’ to ‘<a>.r1’, right?
>
> Hmm maybe need to clarify
> <a>.r1 is just a variable name <a> is a function. So
> (<> match-fkn pattern) is the ideom here!

Yes, I see.

Ludo’.