[plt-scheme] Pattern matching for Scheme: Why too slow?

From: Andrey Fomichev (fomichev_andrei at mail.ru)
Date: Wed Jul 10 09:44:22 EDT 2002

Some times ago I was wonder the power of pattern matching facilities
in the programming languages such as SML. Now I use Scheme and my wish
is to find something suitable for using pattern matching style of
programming (I have a subtask for which pattern matching is very useful).
For this purposes I found library Pattern Matching for Scheme written
by Andrew K. Wright. It looks really good.

The problem is that for some not complicated patterns system
(I use v200 on win2k) works too slow. The example below is a piece of
code from my program. The time needed to evaluate this expression is
enormous (I wait more than 5 minutes on my Pentium IV and got no answer).

As I found, the problem is in (or ...) pattern. If you replace all
expressions
(const (type ,(or 'o 'u)) with expression (const (type u)) than time needed
to evaluate expression is 1-2 seconds.
Does somebody have an idea "why too slow"?


Example
-------

(require (lib "match.ss"))

(match
    '(child (type u)
            (child (type u)
                   (child (type u)
                          (doc (type u)
                               (const (type u) "sql2")
                               (const (type u) "SQL")
                               (const (type u) "Oracle")
                               (const (type u) "people")
                               (const (type u) "sdtd/sql2/people.scm")
                               (const (type u) 16))
                          (const (type u) (*element* table)))
                   (const (type u) (*element* tuple)))
            (const (type u) (*element* name)))
  [`(child (type ,(or 'o 'u))
           (child (type ,(or 'o 'u))
                  (doc (type ,(or 'o 'u))
                       (const (type ,(or 'o 'u)) ,source-name)
                       (const (type ,(or 'o 'u)) ,source-type)
                       (const (type ,(or 'o 'u)) ,source-brand)
                       (const (type ,(or 'o 'u)) ,table-name)
                       ,_
                       (const (type ,(or 'o 'u)) ,columns-num))
                  (const (type ,(or 'o 'u)) (*element* ,(or '* 'table))))
           (const (type ,(or 'o 'u)) (*element* ,(or '* 'tuple))))
   (list #t
         (list (list (list table-name columns-num '*)) '() #f)
         (list source-name source-type source-brand))]
  [`(child (type ,(or 'o 'u))
           (child (type ,(or 'o 'u))
                  (child (type ,(or 'o 'u))
                         (doc (type ,(or 'o 'u))
                              (const (type ,(or 'o 'u)) ,source-name)
                              (const (type ,(or 'o 'u)) ,source-type)
                              (const (type ,(or 'o 'u)) ,source-brand)
                              (const (type ,(or 'o 'u)) ,table-name)
                              ,_
                              (const (type ,(or 'o 'u)) ,columns-num))
                         (const (type ,(or 'o 'u)) (*element* ,(or '*
'table))))
                  (const (type ,(or 'o 'u)) (*element* ,(or '* 'tuple))))
           (const (type ,(or 'o 'u)) (*element* ,field)))
   (list #t
         (list (list (list table-name columns-num field)) '() #f)
         (list source-name source-type source-brand))]
  [_ 'nothing])




Best regards,
Andrey






Posted on the users mailing list.