🚀 go-pugleaf

In article <RJC.90Jun6223015@brodie.uk.ac.ed.cstr>, rjc@uk.ac.ed.cstr (Richard Caley) writes:
> I think Jeff is right though, pattern matching in programing languages
> is far too concrete.  Just imagine implementing some kind of table ADT
> and being able to say that programs using the ADT should be able to
> match aginst it using (1) ( despite its being a hash table of has
> tables or something equally ghastly internally ).

There is no reason why pattern matching and abstraction couldn't go
hand in hand.  Pattern matching is just a special kind of constraint
solving.  What's required for Prolog-style matching is that there
be a constructor function
	mk_f : T_1 x ... x T_n -> T
that will take n arguments of the appropriate types and construct
something of type T, a recogniser function
	is_f : T -> bool
which is true of precisely the things constructed by f, and
n projection functions
	f_arg_i : T -> T_i
which can recover the information originally given to f.  Then we
can solve the equation
	X = f(X_1,...,X_n)
thus:  if X is a variable, set X to mk_f(X_1,...,X_n)
       if X is not a variable, and is_f(X) is false, fail
       if X is not a variable, and is_f(X) is true,
	solve X_1 = f_arg_1(X), ..., X_n = f_arg_n(X).
(Handling this in full generality may require coroutining.)

In a language with one-way matching (in the head of an equation, match
against existing terms, on the right hand side, construct new ones)
it can be determined at compile time when to use the constructor and
when to use the recogniser and projections.  Indeed, as long as you
have a recogniser and projections, e.g.
	view f(X:T) => (e_1:T_1,...,E_n:T_n) if test.
you can use pattern-matching *syntax* in one-way pattern matching
without requiring access to a constructor at all.  (Presumably this
is the "view" mechanism that has been mentioned here.)

Prolog doesn't do this because unification is supposed to be a
primitive and determinate in Prolog.  In ML, it would just be more
syntactic sugar.

-- 
"A 7th class of programs, correct in every way, is believed to exist by a
few computer scientists.  However, no example could be found to include here."