Pattern matching, not optional arguments

[Jonathan A Rees <JAR@AI.AI.MIT.EDU>]

    Date: Mon, 13 Apr 87 15:19:27 est
    From: Chris Haynes <cth at iucs.cs.indiana.edu>

    <pattern> ::= <variable>
    	    | <number> | <string> | (quote <object>)
    	    | (vector <pattern> ...)
    	    | (? <predicate> <pattern>)
    	    | (<pattern> ...)
    	    | (<pattern> <pattern> ... . <pattern>)

Phil Wadler recently complained in SIGPLAN that Scheme has no built-in
pattern matching like ML and its affiliates do.  I think there may be
something to what he says.  Matching of the ML variety happens a fair
amount in informal notations (e.g. mathematics, denotational
semantics).  What you suggest is almost the same as ML's matching
facility, but not quite as elegant.  Yours treats lists and vectors
asymmetrically, and doesn't allow for additional constructors without
redefining the macro.  You should consider going even closer to ML,
which you could do by changing the last two alternatives to be

    	    | (list <pattern> ...)
    	    | (list* <pattern> <pattern> ... <pattern>)

(In ML you'd write <pattern>,<pattern>,... instead of
(list <pattern> <pattern> ...), and <pattern>::<pattern> instead of
(cons <pattern> <pattern>).)

This eliminates the reserved word problem; it is possible to take a list
apart and name its car VECTOR, and it is possible to make MATCH
understand new kinds of constructors without causing old code to break
due to name conflicts.  In fact, if you changed
  (? <predicate> <pattern>)
to
  ((? <predicate>) <pattern>)
then you could change the syntax to be simply

    <pattern> ::= <variable>
    	    | <number> | <string> | (quote <object>)
    	    | (<expression> <pattern> ...)

This would permit you to say things like

      (let ((widget list)) ...
	(match w
	  ((widget wrench connector) ...)))

to take a widget (implemented as a list) apart into its wrench and
connector components, and we have taken another step closer to being
like ML.  Giving a semantics for this in Scheme is harder than in ML
since Scheme is a dynamically-typed language with only one namespace,
and ML is statically typed and has four namespaces.  The feat can be
accomplished by making MATCH expand into a call to some procedure, call
it MATCH-INTERNAL:

	(match x ((exp pat ...) body ...) clause ...) ==>

        (let ((z x))
	  (match-internal exp number-of-pats-following-exp z
	     (lambda (val ...) (match val ...) ...)
	     (lambda () (match z clause ...))))

I.e. MATCH-INTERNAL takes the constructor, the number of arguments to
the constructor (i.e. subpatterns), the thing to be matched, and success
and failure continuations.  MATCH-INTERNAL then dispatches on the
constructor:

    (define (match-internal constructor nargs obj succeed fail)
      (cond ((eq? constructor list)
	     (if (and (list? obj)
		      (= (length obj) nargs))
		 (apply succeed obj)
	         (fail)))
	    ((eq? constructor list*) ...)
	    ((eq? constructor vector) ...)
	    ((?-constructor? constructor)
	     (if (and (= nargs 1)
		      ((?-predicate constructor) obj))
		 (succeed obj)
	       (fail)))
	    ...
	    (else (error "unknown constructor" ...))))

    (define (? pred)
      ...something which answers true to the ?-constructor? predicate ...)

This the same kind of mechanism as is used for T's equivalent of Common
Lisp's SETF.  Like T's SETF, it could be made user-extensible, and
it could be made efficiently compilable.

If it expanded macro forms, then it could also handle QUASIQUOTE with no
extra work (as long as the expansion conatained only constructors that
MATCH-INTERNAL knew about).

By the way, if numbers and strings can be patterns, then booleans and
characters ought to be patterns too.

Jonathan