Xref: utzoo comp.lang.functional:159 comp.lang.prolog:2763 Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!umich!samsung!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: <2798@syma.sussex.ac.uk> Date: 5 Jun 90 02:32:25 GMT References: <2584@skye.ed.ac.uk> <3077@goanna.cs.rmit.oz.au> <2790@syma.sussex.ac.uk> <2631@skye.ed.ac.uk> Organization: School of Cognitive & Computing Sciences, Sussex Univ. UK Lines: 123 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] => ** 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]] => ** 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 => ** x, y, z=> ** 2 2 [5] [1 2 3 4 4 3 2 1] fmatches [??x ??y] where x = rev(y) => ** 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