‘match’ and “k or more” patterns

‘match’ and “k or more” patterns

[Ludovic Courtès]

[-- Attachment #1: Type: text/plain, Size: 558 bytes --]

Hello Alex,

GNU Guile 1.9 now uses your implementation of ‘match’ as a nice
replacement for Wright’s implementation, so thank you!

I stumbled upon this incompatibility: Wright’s ‘match’ supports ‘..1’,
‘..2’, etc., which mean “1 or more”, “2 or more”, etc., and the
associated variable (when there’s one) is bound to the list that
matches:

  (match '(a 1 2) (('a x ..1) x))
  => (1 2)

AFAICS these patterns aren’t implemented in your ‘match’.

Do you have plans to implement them?

Thanks!
Ludo’.

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

Re: ‘match’ and “k or more” patterns

[Alex Shinn]

On Mon, Sep 6, 2010 at 12:04 AM, Ludovic Courtès <ludo@gnu.org> wrote:
>
> GNU Guile 1.9 now uses your implementation of ‘match’ as a nice
> replacement for Wright’s implementation, so thank you!
>
> I stumbled upon this incompatibility: Wright’s ‘match’ supports ‘..1’,
> ‘..2’, etc., which mean “1 or more”, “2 or more”, etc., and the
> associated variable (when there’s one) is bound to the list that
> matches:
>
>  (match '(a 1 2) (('a x ..1) x))
>  => (1 2)
>
> AFAICS these patterns aren’t implemented in your ‘match’.
>
> Do you have plans to implement them?

Yes, these can't be implemented in syntax-rules.

It would be straightforward to implement an alternate
syntax such as

  (match '(a 1 2) (('a x .. 1) x))

or generalize it to

  (match '(a 1 2) (('a x <M> .. <N>) x))

where the <N> could be #f or left out to mean infinity,
which would be strictly more powerful than Wright's
syntax.

The main reason I haven't bothered adding this is
I've never needed it, and was waiting to hear reports
from people who do.

Do you have any code which actually uses the ..k
patterns? :)

-- 
Alex

Re: ‘match’ and “k or more” patterns

[Ludovic Courtès]

Hi,

[Re-adding Cc: guile-devel@gnu.org.]

Alex Shinn <alexshinn@gmail.com> writes:

> On Mon, Sep 6, 2010 at 12:04 AM, Ludovic Courtès <ludo@gnu.org> wrote:
>>
>> GNU Guile 1.9 now uses your implementation of ‘match’ as a nice
>> replacement for Wright’s implementation, so thank you!
>>
>> I stumbled upon this incompatibility: Wright’s ‘match’ supports ‘..1’,
>> ‘..2’, etc., which mean “1 or more”, “2 or more”, etc., and the
>> associated variable (when there’s one) is bound to the list that
>> matches:
>>
>>  (match '(a 1 2) (('a x ..1) x))
>>  => (1 2)
>>
>> AFAICS these patterns aren’t implemented in your ‘match’.
>>
>> Do you have plans to implement them?
>
> Yes, these can't be implemented in syntax-rules.

Well, since there are only 9 of them, they could probably be implemented
as special cases, with an augmented ‘match-gen-ellipses’, which would be
told the minimum number of elements expected?

> It would be straightforward to implement an alternate
> syntax such as
>
>   (match '(a 1 2) (('a x .. 1) x))
>
> or generalize it to
>
>   (match '(a 1 2) (('a x <M> .. <N>) x))
>
> where the <N> could be #f or left out to mean infinity,
> which would be strictly more powerful than Wright's
> syntax.

Yes, this would be nice, too.

> The main reason I haven't bothered adding this is
> I've never needed it, and was waiting to hear reports
> from people who do.
>
> Do you have any code which actually uses the ..k
> patterns? :)

I do!  :-)

  http://git.sv.gnu.org/cgit/guile-rpc.git/tree/modules/rpc/compiler.scm#n312

Well it uses only ‘..1’.  The same code would work with ‘..1’ replaced
by ‘...’, but then errors in the input wouldn’t be detected as nicely.

Thanks,
Ludo’.

Re: ‘match’ and “k or more” patterns

[Alex Shinn]

On Mon, Sep 6, 2010 at 9:12 PM, Ludovic Courtès <ludo@gnu.org> wrote:
>
> Well, since there are only 9 of them, they could probably be implemented
> as special cases, with an augmented ‘match-gen-ellipses’, which would be
> told the minimum number of elements expected?

Oh, the Wright syntax limited you to 9 forms, so "..10" is illegal?

Then this could be done in pure syntax-rules.

>> Do you have any code which actually uses the ..k
>> patterns? :)
>
> I do!  :-)
>
>  http://git.sv.gnu.org/cgit/guile-rpc.git/tree/modules/rpc/compiler.scm#n312
>
> Well it uses only ‘..1’.  The same code would work with ‘..1’ replaced
> by ‘...’, but then errors in the input wouldn’t be detected as nicely.

"..1" is actually useful - it's the analog of "+" in regular
expressions, and allows simplifying many syntax-rules
patterns you see written (elt0 elt1 ...) as (elt ..1).  If
the elements are more complex patterns this is a big
win.

-- 
Alex

Re: ‘match’ and “k or more” patterns

[Ludovic Courtès]

Hi,

Alex Shinn <alexshinn@gmail.com> writes:

> On Mon, Sep 6, 2010 at 9:12 PM, Ludovic Courtès <ludo@gnu.org> wrote:
>>
>> Well, since there are only 9 of them, they could probably be implemented
>> as special cases, with an augmented ‘match-gen-ellipses’, which would be
>> told the minimum number of elements expected?
>
> Oh, the Wright syntax limited you to 9 forms, so "..10" is illegal?

From Wright’s 1995 paper & doc I thought k > 9 wasn’t supported but
apparently it is:

--8<---------------cut here---------------start------------->8---
guile> (use-modules (ice-9 match)) ;; <- Wright’s code
guile> (match (iota 30) ((a ..10) a))
$1 = (0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29)
guile> (match (iota 30) ((a ..22) a))
$2 = (0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29)
guile> (version)
$3 = "1.8.7"
--8<---------------cut here---------------end--------------->8---

:-(

> "..1" is actually useful - it's the analog of "+" in regular
> expressions, and allows simplifying many syntax-rules
> patterns you see written (elt0 elt1 ...) as (elt ..1).  If
> the elements are more complex patterns this is a big
> win.

Agreed.

So perhaps one solution would be to:

  1. Have a special case for ‘..1’, since it’s quite handy.

  2. Have a new syntax form, like ‘.. k’, as you suggested.

What do you think?

Thanks,
Ludo’.

Re: ‘match’ and “k or more” patterns

[Andy Wingo]

Hello,

On Wed 08 Sep 2010 04:18, Alex Shinn <alexshinn@gmail.com> writes:

> "..1" is actually useful - it's the analog of "+" in regular
> expressions, and allows simplifying many syntax-rules
> patterns you see written (elt0 elt1 ...) as (elt ..1).  If
> the elements are more complex patterns this is a big
> win.

Interesting. It would be a nice extension to syntax-rules itself; though
..1 is not a lovely spelling.

Andy
-- 
http://wingolog.org/

Re: ‘match’ and “k or more” patterns

[Ludovic Courtès]

[-- Attachment #1.1: Type: text/plain, Size: 729 bytes --]

Hi Alex,

Alex Shinn <alexshinn@gmail.com> writes:

> On Mon, Sep 6, 2010 at 9:12 PM, Ludovic Courtès <ludo@gnu.org> wrote:

[...]

>> I do!  :-)
>>
>>  http://git.sv.gnu.org/cgit/guile-rpc.git/tree/modules/rpc/compiler.scm#n312
>>
>> Well it uses only ‘..1’.  The same code would work with ‘..1’ replaced
>> by ‘...’, but then errors in the input wouldn’t be detected as nicely.
>
> "..1" is actually useful

The attached patch adds support for ‘..1’.  I’ll apply it to Guile if
you’re OK with applying it upstream.

What do you think?

BTW, I had fearfully avoided to hack a pattern matcher until now and I
was pleased to see how tractable this code is!

Thanks,
Ludo’.


[-- Attachment #1.2: Type: application/pgp-signature, Size: 197 bytes --]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: Type: text/x-patch, Size: 1941 bytes --]

diff --git a/module/ice-9/match.upstream.scm b/module/ice-9/match.upstream.scm
index 963b89f..bf3335b 100644
--- a/module/ice-9/match.upstream.scm
+++ b/module/ice-9/match.upstream.scm
@@ -125,7 +125,7 @@
 ;; pattern so far.
 
 (define-syntax match-two
-  (syntax-rules (_ ___ *** quote quasiquote ? $ = and or not set! get!)
+  (syntax-rules (_ ___ ..1 *** quote quasiquote ? $ = and or not set! get!)
     ((match-two v () g+s (sk ...) fk i)
      (if (null? v) (sk ... i) fk))
     ((match-two v (quote p) g+s (sk ...) fk i)
@@ -161,6 +161,10 @@
      (match-extract-vars p (match-gen-search v p q g+s sk fk i) i ()))
     ((match-two v (p *** . q) g+s sk fk i)
      (match-syntax-error "invalid use of ***" (p *** . q)))
+    ((match-two v (p ..1) g+s sk fk i)
+     (if (pair? v)
+         (match-one v (p ___) g+s sk fk i)
+         fk))
     ((match-two v (p . q) g+s sk fk i)
      (if (pair? v)
          (let ((w (car v)) (x (cdr v)))
diff --git a/test-suite/tests/match.test b/test-suite/tests/match.test
index 70a15ec..d1432d8 100644
--- a/test-suite/tests/match.test
+++ b/test-suite/tests/match.test
@@ -67,6 +67,16 @@
         ((x . rest)
          (and (eq? x 'a) (equal? rest '(b c)))))))
 
+  (pass-if "list ..1"
+    (match '(a b c)
+      ((x ..1)
+       (equal? x '(a b c)))))
+
+  (pass-if "list ..1, with predicate"
+    (match '(a b c)
+      (((and x (? symbol?)) ..1)
+       (equal? x '(a b c)))))
+
   (pass-if "tree"
     (let ((tree '(one (two 2) (three 3 (and 4 (and 5))))))
       (match tree
@@ -79,4 +89,15 @@
   (pass-if-exception "tree"
     exception:match-error
     (match '(a (b c))
-      ((foo (bar)) #t))))
+      ((foo (bar)) #t)))
+
+  (pass-if-exception "list ..1"
+    exception:match-error
+    (match '()
+      ((x ..1) #f)))
+
+  (pass-if-exception "list ..1, with predicate"
+    exception:match-error
+    (match '(a 0)
+      (((and x (? symbol?)) ..1)
+       (equal? x '(a b c))))))

Re: ‘match’ and “k or more” patterns

[Ludovic Courtès]

Hi Alex,

There was a bug in the patch at [0], whereby ‘..1’ would be considered
as the name of a pattern variable:

  scheme@(guile-user)> (match '((1 2) (3 4)) (((x ..1) ...) x))
  standard input:137:0: warning: possibly unbound variable `..1'
  standard input:137:1: In procedure module-lookup:
  standard input:137:1: Unbound variable: ..1

This is fixed by [1].

Let us know if you spot other problems so that Guile’s version remains
in sync with yours.

Thanks,
Ludo’.

[0] http://git.savannah.gnu.org/cgit/guile.git/commit/?id=1ffed5aa95d66123a552fa3513373e78a1679287
[1] http://git.savannah.gnu.org/cgit/guile.git/commit/?id=f2ee6341baa31d75f9734a93545eb2608dd5653c

Re: ‘match’ and “k or more” patterns

[Alex Shinn]

On Tue, Sep 28, 2010 at 6:56 AM, Ludovic Courtès <ludo@gnu.org> wrote:
>
> There was a bug in the patch at [0], whereby ‘..1’ would be considered
> as the name of a pattern variable:

Oh, I had already fixed that upstream (on synthcode.com),
sorry I forgot to mention it!

-- 
Alex

Re: ‘match’ and “k or more” patterns

[Ludovic Courtès]

Hi,

Alex Shinn <alexshinn@gmail.com> writes:

> On Tue, Sep 28, 2010 at 6:56 AM, Ludovic Courtès <ludo@gnu.org> wrote:
>>
>> There was a bug in the patch at [0], whereby ‘..1’ would be considered
>> as the name of a pattern variable:
>
> Oh, I had already fixed that upstream (on synthcode.com),
> sorry I forgot to mention it!

No problem.

Is there a public version control repository at synthcode.com?

Thanks,
Ludo’.

Re: ‘match’ and “k or more” patterns

[Alex Shinn]

On Tue, Sep 28, 2010 at 7:27 PM, Ludovic Courtès <ludo@gnu.org> wrote:
>
> Is there a public version control repository at synthcode.com?

Not for match.scm, but that's just a copy of the chibi-scheme
version with record patterns commented out:

  hg clone https://chibi-scheme.googlecode.com/hg/ chibi-scheme

-- 
Alex

Re: ‘match’ and “k or more” patterns

[Andy Wingo]

Greets,

On Sat 02 Oct 2010 09:13, Alex Shinn <alexshinn@gmail.com> writes:

> On Tue, Sep 28, 2010 at 7:27 PM, Ludovic Courtès <ludo@gnu.org> wrote:
>>
>> Is there a public version control repository at synthcode.com?
>
> Not for match.scm, but that's just a copy of the chibi-scheme
> version with record patterns commented out:
>
>   hg clone https://chibi-scheme.googlecode.com/hg/ chibi-scheme

Does chibi do cond-expand? If so you could only provide an
implementation of match-record-refs if you're using Chibi, and other
implementations could provide their own in a prelude or something.

Just a thought :)

Andy
-- 
http://wingolog.org/

Re: ‘match’ and “k or more” patterns

[Ludovic Courtès]

Hello,

Andy Wingo <wingo@pobox.com> writes:

> On Sat 02 Oct 2010 09:13, Alex Shinn <alexshinn@gmail.com> writes:
>
>> On Tue, Sep 28, 2010 at 7:27 PM, Ludovic Courtès <ludo@gnu.org> wrote:
>>>
>>> Is there a public version control repository at synthcode.com?
>>
>> Not for match.scm, but that's just a copy of the chibi-scheme
>> version with record patterns commented out:
>>
>>   hg clone https://chibi-scheme.googlecode.com/hg/ chibi-scheme

Great, thanks.

> Does chibi do cond-expand? If so you could only provide an
> implementation of match-record-refs if you're using Chibi, and other
> implementations could provide their own in a prelude or something.

+1

(That was actually the next thing I wanted to look at in ‘match’.)

Ludo’.