Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!ucbvax!bloom-beacon!dont-send-mail-to-path-lines
From: jeff@aiai.edinburgh.ac.UK (Jeff Dalton)
Newsgroups: comp.lang.scheme
Subject: Destructuring / pattern-matching (was: Multiple return values)
Message-ID: <12542.9104111347@subnode.aiai.ed.ac.uk>
Date: 11 Apr 91 13:47:48 GMT
Sender: daemon@athena.mit.edu (Mr Background)
Organization: The Internet
Lines: 134

> Date: Thu, 4 Apr 91 13:01:00 PST
> From: Jon L White <jonl%kuwait@lucid.com>
> Message-Id: <9104042101.AA28583@kuwait>
> To: Scheme@mc.lcs.mit.edu

> In fact, Lisp/370 (predecessor to IBM's "Uncommon Lisp" called
> LISP/VM) had automatic destructuring in every lambda argument
> position, including the input arguments.  By 1980, such an 
> extension was working in parts of MacLisp and in VAX/NIL.  In
> fact, it even "destructured" over vectors as well as lists;
> [...]

> This was particularly useful in the VAX/NIL compiler and assembler
> where much more use was made of simple vectors rather than lists.  
> We even had a version that would destructure over DEFSTRUCT instances,
> in the expectation that "objects" like vectors and structures would 
> displace lists as the more common data structure "of choice".

I think this is an excellent example of how language design can affect
the program development and debugging.  (Which is not to say that many
of the problems couldn't be solved by changing the development
environment rather than the language.)

One problem with destructuring (as opposed to pattern matching) is
that it may not bother to check whether the object being destructured
has the right shape.  Of course, the corresponding problem with
pattern matching is that it makes the check even when it is
unnecessary.

Another problem with patterns in general is that they usually do not
respect the abstract structure of objects.  If something is the third
element of a list, a pattern will depend on it being the third
element; if something is a slot of a struct, the pattern will depend
on it being a slot (rather than being accessed some other way).  This
is a serious hassle in Prolog, where changing the structure of a term
often requires changing patterns all over the program; and since the
contents of terms are accessed positionally, it's easy to make a
mistake.

When people talk of the advantages of pattern-matching in Prolog and
functional languages, they seldom mention that it has this disadvantage
too.

On the other hand, Lisp programmers often fail to make all the
appropriate checks when examining a list.  One often sees code
that does something like (EQ (CAR EXPR) 'LAMBDA) and then assumes
that the entire list is a proper lambda-expression, even when
the list is accessed abstractly by calling functions such as
LAMBDA-EXPR-PARAMETER-LIST (which just does a CADR).

This suggests that it may be a good idea to have both destructuring
and pattern-matching in Lisp, especially if something can be done
about the problems mentioned above.

Fortunately, something can be done (or so I'm told).  For example, in
functional languages it may be possible to define abstract "views" of
objects for use in patterns.  In Prolog, it may be possible to use
code unfolding (read macro expansion) to define structures and
patterns abstractly.  But not all languages or implementations have
such facilities, and (in Prolog at least), most programmers do not use
them.

This suggests that it helps to make such features a standard part of
the language and so encourage their use.  However, there are so many
different ways to express patterns, with different advantages and
disadvantages, that it is not clear that s single mechanism should
be chosen.  As JonL mentioned:

> There was no technical difficulty in extending these ideas for Common 
> Lisp; but instead a debate arose over whether the pattern should be 
> defined to be a data object (i.e., a cons cell implying taking the CAR 
> and CDR of the input argument) or to be a program [i.e., for the above
> example, write `(,a `#(,b ,c) . ,l) instead of (a #(b c) . l)].

The obvious answer in Lisp seems to be: write a macro to do whatever
pattern-matching or destructuring you want.  Unfortunately, it seems
to be sufficiently hard to design a good macro that programmers often
write out what they want by hand instead, even when they can make use
of DESTRUCTURING-BIND.  JonL writes:

> I'm always having to intersperse lines of LET's amongst multiple
> incarnations of DESTRUCTURING-BIND, as well as with MULTIPLE-VALUE-BIND's.

Nonetheless, it should be possible for those so inclined to write
_some_ macros.  But then we often encounter another problem.  For
example, I wrote some macros that let me do such things as

   (defpat
     ((app () y)          y)
     ((app (cons a x) y)  (cons a (app x y))))

In the Scheme version I could also write

   (defpat
     ((app `() y)          y)
     ((app `(,a . ,x) y)   `(,a . ,(app x y))))

All I had to do was tell my macro how to compile (some cases of)
quasiquote.  But it's a pain to do this for Common Lisp, because
backquote can expand into so many different things.  Indeed, Common
Lisp often fails to define what happens at the level just below the
one you're meant to use, which makes it hard to define facilities
that are similar but not identical to those offered as standard.
GJC made this point about a month ago:

   From: gjc@mitech.COM
   Newsgroups: comp.lang.scheme
   Subject: Dear JONL: an ode to SQUID.
   Message-ID: <9103121148.AA07598@schizo>
   Date: 11 Mar 91 11:21:06 GMT

   The lack of SQUID and the foolishness of the "#," approach first
   struck me when dealing with the port of the FORTRAN->LISP
   translator from MACLISP to COMMON-LISP.

   By "#," approach I mean a tendency, first seen in the LISPMACHINE
   at MIT, to avoid an *OPEN* implementation policy, generally a
   SEMANTICS FIRST, then SYNTAX, has a tendency to be the most open,
   and instead go as soon as possible to some concept limited by the
   imagination of the lisp implementor of *EXACTLY* what the user will
   *REQUIRE*.

   One result is that many significantly complex applications, e.g.
   Macsyma, Fortran->Lisp, generally any imbedded language, depended
   critically on internal undocumented representations (e.g. the
   readmacro expansion of "#," and internal flags such as
   SI:COMPILER-XYX-FLAG) so as to be frustratingly fragile to systems
   changes.

Nonetheless, I think the best way to proceed would be for people to
write macros that they find useful, let others use them, and see what
solutions evolve. 

-- jeff