Xref: utzoo comp.lang.functional:178 comp.lang.prolog:2789 Path: utzoo!attcan!uunet!fernwood!decwrl!elroy.jpl.nasa.gov!sdd.hp.com!samsung!munnari.oz.au!bruce!goanna!ok From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) Newsgroups: comp.lang.functional,comp.lang.prolog Subject: Re: Pattern matching considered harmful Message-ID: <3194@goanna.cs.rmit.oz.au> Date: 8 Jun 90 05:36:05 GMT References: <2584@skye.ed.ac.uk> <3077@goanna.cs.rmit.oz.au> Followup-To: comp.lang.functional Organization: Comp Sci, RMIT, Melbourne, Australia Lines: 44 In article , 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."