Re: [Chicken-users] matchable egg usage question

[Alex Shinn]

On Fri, Jan 28, 2011 at 2:21 PM, Alan Post <address@hidden> wrote:
> I'm trying to use the matchable egg to detect #!key parameters in
> functions I've constructed.  I have functions that accept multiple
> #!key parameters, and I'm not sure how to make the matchable egg
> match |(func ... mykey: myvalue ...)|.  That is, how to get the
> matchable egg to match two parameters anywhere in an input list.

Why not use Chicken's builtin #!key handling?

  (apply (lambda (#!key key1 key2)
                ;; code using key1 and key2
                ...)
             (list key1: val1 key2: val2))

> This is what I've got so far.  I am interested in whether the
> #!key paramater 'a' is set to #t:

OK, the original point of this style of pattern matching
was it was simple and fast - it does a simple linear
match against each possible pattern so is as fast as
using low-level destructuring and checking (faster if
the match library can eliminate common sub-patterns).

As soon as you introduce any ambiguity in how a
pattern can match the whole process becomes a
search algorithm, with backtracking in the general
case.  So whereas the pattern

  (a b c)

is constant time (O(m) in the pattern size),

  (a b c ...)

is linear (O(n) in the input size), which is fine, but

  (a b c ... d ...)

is O(n^2) in the input size depending on where
you choose to split between c and d.  And

  (a b c ... d ... e ...)

is O(n^3), etc.

Most of the time when you want to use this sort
of pattern, you don't want backtracking - you want
c to match as many elements as it can and then
"commit," and take the rest of the list as d.  So if
the match doesn't let you express the expensive
patterns, you have to iterate over one c at a time:

  (let lp ((ls ls) (c-ls '())
    (match ls
      ((c . rest) (lp (cdr ls) (cons c c-ls)))
      (else
       ;; match d's in remaining ls
       ...)))

This is O(n), and is the same sort of idiom many
complex syntax-rules libraries use.

So by deliberately limiting match we force people
to write faster code.  At the same time, it's more
verbose code - if you really want a match as powerful
as prolog you could implement it and deal with the
fact that it can be very slow in some cases.  And in
that case you will eventually need to add a way to
explicitly commit matches (i.e. "cut" in prolog) for
decent performance.

[I'm not completely consistent in this, though,
because the tree patterns I added do in fact
require more complex searching and backtracking.
But tree searches require this in general.]

-- 
Alex