Xref: utzoo comp.lang.functional:183 comp.lang.prolog:2792
Path: utzoo!attcan!uunet!mcsun!ukc!icdoc!syma!aarons
From: aarons@syma.sussex.ac.uk (Aaron Sloman)
Newsgroups: comp.lang.functional,comp.lang.prolog
Subject: Re: Pattern matching considered harmful
Message-ID: <2822@syma.sussex.ac.uk>
Date: 7 Jun 90 22:34:41 GMT
References: <1990Jun5.175706.415@newcastle.ac.uk> <2584@skye.ed.ac.uk> <3077@goanna.cs.rmit.oz.au> <2790@syma.sussex.ac.uk> <RJC.90Jun4134659@brodie.uk.ac.ed.cstr> <1990Jun07.020319.27609@comp.vuw.ac.nz>
Organization: School of Cognitive & Computing Sciences, Sussex Univ. UK
Lines: 59

brian@comp.vuw.ac.nz (Brian Boutel) writes:

> Organization: Dept. of Comp. Sci., Victoria Uni. of Wellington, New Zealand.
    .... stuff deleted ....
> Abstract data types, whose constructors are not visible, solve the
> problem of changing the implementation without having to change the use,
> but cannot be combined with pattern matching, where the constructors
> need to be visible.
>
> This does not make pattern matching "harmful". Pattern matching is what
> makes data-driven case analysis possible, and this is a good thing.
>
> Phil Wadler proposed the use of "views" to avoid this difficulty. A view
> is an alternative definition of a datatype, with a new set of
> constructors and with functions for mapping between the view and the
> real representation. An abstract data type defines a view whose
> constructors can be used for pattern matching, but the real
> representation is hidden and can be changed, without invalidating the
> user's code, if the mapping functions are also changed. The mapping
> functions are not explicitly used by the user, but inserted by the
> compiler where necessary.

As it happens this (if I understand it aright) is exactly how I like
to introduce list processing to students. I.e. we give them the
EXTERNAL representation (i.e. a "view"??) in terms of bracketed
sequences of items (words, numbers, strings, lists) without (for
quite a while) telling them ANYTHING about the implementation.

Instead we show them how useful these bracketed orderd structures
are for a collection of problems, and let them use pattern matching
to do tests, access components, etc. As far as they are concerned
the implementation might be as vectors (elements allocated
contiguously in store) list structures (elements linked via pairs)
or something much more complex. It makes no difference to their use,
and so the students don't need to know. Later they (or some of them)
learn how lists are implemented (at a suitable level of
abstraction), learn to use hd and tl, learn how recursing on the hd
of a list enables you to do some things that would be clumsy with
the pattern matcher, and so on.

For many uses where lists and pattern matching are natural the fact
that the underlying implementation is or is not a binary tree, or
that there are functions for getting at components of the lists, is
as irrelevant as the quantum mechanics of computer circuits is to
most computer scientists and software engineers. I.e. the underlying
"pair" abstract data-type is just a low level machine feature.

Unfortunately the Prolog pattern matcher is too limited to support
this "view" of lists because it forces you to treat lists as
asymmetrical. I presume that's mainly because, with bi-directional
unification, segment variables anywhere in a list would make
everything too indeterminate (a problem with the pattern matching
language of Carl Hewitt's Planner system in the early 70s I seem to
recall)?

Aaron Sloman,
School of Cognitive and Computing Sciences,
Univ of Sussex, Brighton, BN1 9QH, England
    EMAIL   aarons@cogs.sussex.ac.uk