[plt-scheme] Algebraic patterns

From: Eli Barzilay (eli at barzilay.org)
Date: Tue Oct 1 02:01:32 EDT 2002

So, I've slapped a quick implementation...  And the result is very
nice -- just like all "other" languages.  Running examples at bottom
of this email.

The summery is:

1. There are several places where bindings appear: `lambda' arguments,
   and the `define', `let', and `set!' families.

2. In all of these, an identifier can now be a pattern form which is a
   constructor for some type -- the subparts of this form are used as
   the actual variables and the given argument is deconstructed

3. One such special form is `(values)' which is only available as the
   outermost form for non `-values' syntaxes -- and the effect of that
   is to use the corresponding `-values' syntax.

4. A very important feature is that all overridden Scheme keywords can
   be used with the same semantics -- a `define-values' is still a
   single `define-values' form, and the same for the rest, all with
   attempting to do minimal work at runtime.  If no patterns are used,
   then nothing is changed from the built-in primitives, so as long as
   you don't `(define (list ...) ...)' often, it behaves exactly the
   same with no costs other than compile-time.  This is unlike

5. Such extended argument form keywords for `(foo ...)' are determined
   by the existence of a syntax binding by the name of
   `extended-arg-keyword:foo'.  It is expected to be bound to a list
   of two functions that are used to pull out the subexpressions from
   such a pattern that are the actual bound variables, and to convert
   a value expression to multiple values of the matching arity.

6. This means that modules can be used to extend the set of available
   patterns, and that it is easy to extend it to any wild pattern like
   most of the stuff in match.ss.  The only limitation is that a
   keyword should always identify the pattern since the intention is
   for ML-like patterns that have the same syntax as the
   constructors.  As an example, I implemented `quote' that uses
   "implicit" lists and vectors, but it could be extended to literals

7. Since any bindings can be pulled out of such a pattern, and an
   arbitrary form can be used to convert it to a value, it should also
   be possible to hack things like an `(integer foo)' pattern that
   will check that the given argument is an integer etc.  Also, the
   object doesn't need to be fully deconstructed, for example, only a
   few keys can be used to pull out values from a has-table (should be
   roughly like matching records in OCaml, but I don't remember much
   of that syntax).

Some possible nice extensions are --

1. If a form looks like `make-foo', then check if `foo' is a struct
   keyword and do the right thing.

2. Extend list matching so it has all the &-keyword features in

3. Make a `case-lambda' that can catch failures and use the next
   available pattern.

If anyone is interested in playing with this, I've put it at


Examples for using it follow.

  > (require "patterns.ss")
  > (define (values a (list (vector b c) (vector d) (list)) e)
            (values 1 (list (vector 2 3) (vector 4) (list)) 5))
  > (list a b c d e)
  (1 2 3 4 5)
  > (set! (list a b c d e) (list e d c b a))
  > (list a b c d e)
  (5 4 3 2 1)
  > (let (((values a (list (vector b c) (vector d) (list)) e)
           (values 1 (list (vector 2 3) (vector 4) (list)) 5)))
    (list a b c d e))
  (1 2 3 4 5)
  > (let* (((list x y) (list 1 2)) ((list x y) (list y x))) (list x y))
  (2 1)
  > (let (((values a '(#(b c) #(d) ()) e)
           (values 1 '(#(2 3) #(4) ()) 5)))
      (list a b c d e))
  (1 2 3 4 5)
  > (map (lambda ((list x y)) (list y x)) '((1 2) (3 4)))
  ((2 1) (4 3))
  > (module foo mzscheme
      (provide (struct point (x y)) extended-arg-keyword:make-point)
      (define-struct point (x y))
      (define-syntax extended-arg-keyword:make-point
        (list (lambda (vars) (syntax-case vars () ((x y) vars)))
              (lambda (expr vars)
                (quasisyntax/loc expr
                  (values (point-x #,expr) (point-y #,expr)))))))
  > (require foo)
  > (define a (make-point 1 2))
  > (let (((make-point x y) a)) (+ x y))

I guess that now it should be clear that this is very different from

          ((lambda (x) (x x)) (lambda (x) (x x)))          Eli Barzilay:
                  http://www.barzilay.org/                 Maze is Life!

Posted on the users mailing list.