Destructuring / pattern-matching (was: Multiple return values) 
Author Message
 Destructuring / pattern-matching (was: Multiple return values)

Quote:
> Date: Thu, 4 Apr 91 13:01:00 PST



> 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:

Quote:
> 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:

Quote:
> 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:


   Newsgroups: comp.lang.scheme
   Subject: Dear JONL: an ode to SQUID.

   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



Mon, 27 Sep 1993 21:47:48 GMT  
 Destructuring / pattern-matching (was: Multiple return values)


   > 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".

   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, 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.

I think a simple macro solution is largely sufficient.  For example,
we have a simple DESTRUCTURING-LET macro in our Lisp.  In
approximately 60,000 lines of Lisp kernel code, there are exactly four
uses of this macro.  We avoid extensive use of such a feature because
there are very few list structures being passed around which need to
be destructured.  If we need to look at certain object components
within a function, it is best to use accessors to avoid dependency on
implementations of objects using particular slot names; in this case,
LET is sufficient.

-- Harley Davis
--
------------------------------------------------------------------------------
nom: Harley Davis                       ILOG S.A.

tel: (33 1) 46 63 66 66                 94253 Gentilly Cedex, France



Tue, 28 Sep 1993 15:16:28 GMT  
 Destructuring / pattern-matching (was: Multiple return values)

Quote:

> 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.

(Self-adverti{*filter*}t:  "The Craft of Prolog" _does_ talk about this and
what to do about it.)

A possible answer in Lisp-like languages would be to introduce a
new form

        (define-pattern (<name> <parameter>...)
                <simple backquote expression>)

where <simple backquote expressions> are sufficiently restricted for
a simple program to figure out how to invert them (say: each

only at the end of a list, something like that).  One also introduces a
new , variant:  ,=(<pattern name> <backquote expression>...).

If I used
        (define-pattern (assoc-link Key Val Rest)

then
        (let ((foo `,=(assoc-link foo 9 ,bar)))
            ...)
would have the effect of

            ...)
and
        (destructure `,=(assoc-link ,k ,v ,bar) foo
            ...)
would have the effect of

            ...)

It's certainly doable.
--
It is indeed manifest that dead men are formed from living ones;
but it does not follow from that, that living men are formed from dead ones.
                        -- Tertullian, on reincarnation.



Fri, 01 Oct 1993 18:37:38 GMT  
 Destructuring / pattern-matching (was: Multiple return values)

   Date: 15 Apr 91 10:37:38 GMT

   Organization: Comp Sci, RMIT, Melbourne, Australia


   > 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.

   (Self-adverti{*filter*}t:  "The Craft of Prolog" _does_ talk about this and
   what to do about it.)

   A possible answer in Lisp-like languages would be to introduce a
   new form

           (define-pattern (<name> <parameter>...)
                   <simple backquote expression>)

   . . .

For another pattern matching extension to Scheme see Erik Ruf's Stanford
Computer Systems Lab Tech report "LogScheme: Integrating Logic Programming into
Scheme" an earlier draft of which appeared in the proceedings of the 4th ACM
Conference on Functional Programming Languages and Computer Architecture under
the title "Nondeterminism and Unification in LogScheme".
--------------------
Morry Katz

--------------------



Sat, 02 Oct 1993 23:57:11 GMT  
 
 [ 4 post ] 

 Relevant Pages 

1. Destructuring / pattern-matching (was: Multiple return values)

2. LOOP destructuring and multiple values

3. returning a part of string using pattern matching

4. pattern matching for multiple line?

5. expect: Matching patterns from multiple spawns simultaneously

6. How to return multiple matches in Regexp?

7. Q:Pattern for nil return values

8. string match return value

9. iss-matching - the free Regular Expression / Pattern Matching cluster

10. return multiple values from an awk function?

11. ???Eiffel idiom for multiple return values???

12. Tuples, iterators, and multiple return values in Eiffel?

 

 
Powered by phpBB® Forum Software