🚀 go-pugleaf

jeff@aiai.ed.ac.uk (Jeff Dalton) writes:

>
> In article <2790@syma.sussex.ac.uk> aarons@syma.sussex.ac.uk
> (Aaron Sloman) writes:
> >I don't see any difference between this problem and the problem
> >arising in any programming language where you define procedures or
> >functions with arguments of certain types and then have to invoke
> >them by giving the right number of arguments in the right order.
>
> Do you really see no advantage to using functions to extract
> parts of structures rather than some positional notation?

I was not aware that I was commenting on that. All I was commenting
on was the point you made (I think) about the difficult of keeping
programs consistent in languages that use pattern matching. I was
simply suggesting that this is a general difficulty with positional
notations, used in many programming languages, not just pattern
matching programs.

Yes, I do think there are occasions when it is nicer to use a
function to extract a component of a structure, e.g.

    last(x)

But that doesn't mean pattern matching is inferior in all contexts.

>
> A possibly related question is: do you find nothing wrong with
> functions/procedures that take, say, 7 positional arguments?

I wasn't commenting on that either. I have occasionally had to use
such functions. In general it's probably a good idea to keep ones
functions simpler than that, if possible. I seem to remember Bob
Boyer once telling me that in order to write a lisp pretty printer
he had to have a procedure with some large number of arguments
(about 14?) on most of which it recursed.

>
> >E.g. to check whether something (x) is a list one of whose elements
> >is a list containing "a" preceded by "b" with an arbitrary number of
> >elements in between, in Pop-11 you'd write
> >
> >    if x matches [ == [ == a == b == ] == ] then ....
> >
> >where "==" matches an arbitrary number of items. In most languages
> >you'd have to write at least three nested loops to do this and would
> >probably not get it right first time.
>
> In Common Lisp:
>
>   (some #'(lambda (sublist) (member 'b (member 'a sublist))) x)

I think a picture of what you mean (i.e. a pattern) is much easer to
understand, and to get right first time.

> Not that this proves anything.  Besides, what you'd really do in Lisp
> would be to write some procedures or macros that made it easier to
> express such things.

Why not add a pattern matcher instead? (Lots of Lispers have used
them at one time or another, e.g. microplanner, planner, QA4, etc).

> By the way, what happens with a pattern like
>
>     [[??a ??b] ??a]
>
> "[??a ??b]" can match in more than one way.  Will more than one
> possibility be tried when trying to match the second "??a"?
>
Good point. In fact the standard Poplog Pop-11 matcher cannot find
the way to match this successfully (though the Alphapop matcher
designed by Jon Cunningham can).

Implementing such a matcher requires use of a state-saving
technique, which is liable to be comparatively slow and generate
garbage. But I think it is sufficiently useful that I shall probably
add a Pop-11 library procedure to the next release of Poplog that
solves this problem, and others. It's called fmatches (for "full"
matches), and it allows a "where" qualifier to control a match.

Your example:

[[1 2 3 4 5] 1 2] fmatches [[??a ??b] ??a] =>
** <true>

a,b =>
** [1 2] [3 4 5]

An example where TWO indeterminate matches have to be made mutually
consistent:

[[1 2][2 1]] fmatches [[??x ??y][??y ??x]] =>
** <true>

x,y =>
** [1] [2]

Illustrating the use of "where" to force retries:

[1 3 2 5 2 4] fmatches [== ?x ??z ?y ==] where x == y =>
** <true>

x, y, z=>
** 2 2 [5]

[1 2 3 4 4 3 2 1] fmatches [??x ??y] where x = rev(y) =>
** <true>

x, y =>
** [1 2 3 4] [4 3 2 1]

One can also attach "restrictions" to pattern variables.

This version of the matcher will also, at last, work with sections
and a subset of lexically scoped variables, the "dlvars" of Poplog.

The standard Pop-11 matcher has problems because it uses -valof- on
words, and this can have a different interpretation at run time from
what the user expected at compile time, e.g. if sections (the Pop-11
variant of packages/modules) are used.

Aaron