Making the matcher robust? 
Author Message
 Making the matcher robust?

Quote:
Aaron writes:

| I was discussing recent developments with a new convert to Pop-11
| at Birmingham, Riccardo Poli, who uses it for teaching and research
| (even on evolutionary algorithms).
|
| When I mentioned that I had found a way to make the matcher work with
| lvars by using lib readpattern and the syntax ![ ..... ] for patterns,
| he commented that in effect that violated the spirit of lvars because
| the matcher is then a procedure defined elsewhere that has access to the
| lvars variables, which is not supposed to be possible with lexical
| scoping!

This is not true.

``All'' lexical scoping does is to prevent access to a variable except
though text written in the scope of the variables declaration. Thus it
is possible to *explicitly* export access to that variable, eg by
passing around its ident, without violating the ``spirit'' of lexical
scoping.

[You don't need idents, either; with full lexical scoping, you can pass
around procedures which read and write the variable. Lexical scoping
prevents *accidental* access to the variable, as opposed to dynamic
scoping, provided by dlocal, which can cause unexpected interactions
between code fragments just because of a variable name.]

| This is a point that had never occurred to me nor, it seems, to others
| who had wanted the matcher to be made to work with lvars.

Because it's not relevant. Your code simply provides a lexically
explicit access to the variable; there's nothing wrong with that.

| His argument, therefore (if I understood him), was that calls to the
| matcher should always be "inline" code, so that it was impossible to
| pass the matcher a pattern created elsewhere, or to use the matcher, or
| a procedure using the matcher, as a procedure argument to another
| procedure in which patterns are created.

He's gone ott.

| In fact, that's exactly what LIB FMATCHES does: it defines fmatches as a
| syntactic operator, not a procedure. I had always claimed that that was
| inadequate, because it made it impossible to define things like present,
| remove, allpresent, and other procedures that can take a pattern as
| input.

But patterns should be first-class objects; it's just that their casual
representation as lists (and their early implementations using valof)
made that less obvious.

| Riccardo's argument is that on the contrary, fmatches is right, and
| moreover the other things that operate on patterns should ALL be syntax
| words that occur "inline" with the patterns they act on, e.g. all
| analogues of present, lookup, remove, allpresent, etc. would have to be
| introduced as new syntax words, as forevery and foreach are already.

No, no, no. Simply have a way of writing patterns that *isn't* just a
list; that's the only thing that should be ``inline'', ie, a special
piece of syntax.

| I had previously thought about generalising fmatches in that direction
| but decided that being able to use the matcher as an ordinary procedure
| was too important to give up.

You're right.

All you need do is to provided a syntax for *patterns*. The rest
follows, because the argument that this would violate lexical spirits is
ill-founded.

Regards,    | ``"I can't suit myself," said Weinbaum, a little petulantly.
Kers.       | "I work for the Government".'' - Blish, "The Quincunx of Time".



Tue, 19 May 1998 03:00:00 GMT  
 Making the matcher robust?
Thanks for the further comments.

[AS]

Quote:
> | In fact, that's exactly what LIB FMATCHES does: it defines fmatches as a
> | syntactic operator, not a procedure. I had always claimed that that was
> | inadequate, because it made it impossible to define things like present,
> | remove, allpresent, and other procedures that can take a pattern as
> | input.

> But patterns should be first-class objects;

I am not sure what you mean by that. If you mean they should be objects
that can be created at run time, returned as procedure values, stored in
datastructures, passed as arguments, etc. then I agree with you. I think
Riccardo was claiming that such objects should not include lvars
identifiers that could be changed by valof anywhere.

This is different from the case of creating a lexical closure, which is
a procedure that can manipulate values of lexical variables, for there
all the code that does the manipulation is explicit within the scope of
the variable.

On the other hand if you aleady have a language that allows lists,
arrays and other datastructures to be updated outside the context in
which they are created, giving heebee jeebees to those committed to
functional programming, then perhaps there's not so much of a problem
allowing lexical variables also to be changed by hidden code.

Quote:
> ..it's just that their casual
> representation as lists (and their early implementations using valof)
> made that less obvious.

Not sure what you mean by "casual representation as lists". It's obvious
that as lists they are first class objects, isn't it?

[AS]

Quote:
> | I had previously thought about generalising fmatches in that direction
> | but decided that being able to use the matcher as an ordinary procedure
> | was too important to give up.

> You're right.

> All you need do is to provided a syntax for *patterns*. The rest
> follows, because the argument that this would violate lexical spirits is
> ill-founded.

Depends what's in the patterns. If they contain special data structures
then there's no problem. If they contain lexical identifiers you can
have code of this form

        lvars x .....;
                .... x ....

        foo(<pattern .... x ....>);

                .... x ....

and then the changes between the second and the fourth occurrences of
"x" are unpredictable, just as with the current matcher.

I suspect that what you are saying is close to what Riccardo said. I
elaborated it, perhaps misleadingly. (he's away for a few days, so I
can't ask him.) I think his main point was to object to my construct

        ![ .......]

which creates an object that contains lexical identifiers that can then
be passed out of the current lexical scope and directly manipulated
elsewhere using valof or idval. My impression was that you don't seem to
like that either: you want any such use of patterns to return some
explicit values, like the Pop-11 "which" construct

    which([x z], [[parent ?x ?y][parent ?y ?z]]) =>
    ** [ [tom harry] [tom mary] [lucy albert] ]

except that which ALSO gives x,y and z new values.

(See HELP WHICH, LIB * WHICH).

It has occured to me that I could change "!" so that it turns a pattern
into a declaration. I.e. the variables in the pattern are declared
as lvars, and can be used only AFTER the pattern has been created.

Thus

        lvars x;

                ..... x .....

                .... ![ .... ?x ....] ....

                ... x ....

would not be allowed, but
                .... ![ .... ?x ....] ....

                ... x ....

would, with no preceding use of x in the same scope (except maybe
a use in a pattern!).

However, this would require access at compile time to the current list
of locally declared variables in the current lexical block. I don't know
if pop_new_lvar_list already has all the relevant information.

Aaron



Tue, 19 May 1998 03:00:00 GMT  
 Making the matcher robust?
I was discussing recent developments with a new convert to Pop-11
at Birmingham, Riccardo Poli, who uses it for teaching and research
(even on evolutionary algorithms).

When I mentioned that I had found a way to make the matcher work with
lvars by using lib readpattern and the syntax ![ ..... ] for patterns,
he commented that in effect that violated the spirit of lvars because
the matcher is then a procedure defined elsewhere that has access to the
lvars variables, which is not supposed to be possible with lexical
scoping!

This is a point that had never occurred to me nor, it seems, to others
who had wanted the matcher to be made to work with lvars.

His argument, therefore (if I understood him), was that calls to the
matcher should always be "inline" code, so that it was impossible to
pass the matcher a pattern created elsewhere, or to use the matcher, or
a procedure using the matcher, as a procedure argument to another
procedure in which patterns are created.

In fact, that's exactly what LIB FMATCHES does: it defines fmatches as a
syntactic operator, not a procedure. I had always claimed that that was
inadequate, because it made it impossible to define things like present,
remove, allpresent, and other procedures that can take a pattern as
input.

Riccardo's argument is that on the contrary, fmatches is right, and
moreover the other things that operate on patterns should ALL be syntax
words that occur "inline" with the patterns they act on, e.g. all
analogues of present, lookup, remove, allpresent, etc. would have to be
introduced as new syntax words, as forevery and foreach are already.

I had previously thought about generalising fmatches in that direction
but decided that being able to use the matcher as an ordinary procedure
was too important to give up.

What do others think?
Aaron
PS
I've just realised that I could change my definition of LIB READPATTERN
so that pattern variables would not need to be declared explicitly
at all. They would simply automatically be declared as dlvars, (or
maybe lvars). What do others think?
--
Aaron Sloman, ( http://www.cs.bham.ac.uk/~axs )
School of Computer Science, The University of Birmingham, B15 2TT, England

Phone: +44-121-414-4775 (Sec 3711)       Fax:   +44-121-414-4281



Tue, 19 May 1998 03:00:00 GMT  
 Making the matcher robust?

Quote:

>I was discussing recent developments with a new convert to Pop-11
>at Birmingham, Riccardo Poli, who uses it for teaching and research
>(even on evolutionary algorithms).

>When I mentioned that I had found a way to make the matcher work with
>lvars by using lib readpattern and the syntax ![ ..... ] for patterns,
>he commented that in effect that violated the spirit of lvars because
>the matcher is then a procedure defined elsewhere that has access to the
>lvars variables, which is not supposed to be possible with lexical
>scoping!

>This is a point that had never occurred to me nor, it seems, to others
>who had wanted the matcher to be made to work with lvars.

(snip)

>What do others think?
>Aaron

I often write code (in languages other than pop11) which use a
procedural matcher (i've lost count of how many times i've written
simple, one-off, dedicated matchers :-). [Presumably anathema to
Chris Dollins ;-)].

If I had to now add matching to pop11, I would do it like this.
(1) use instances of a pattern variable class, instead of query
variable-name. A bit like the way prolog unification works.
(2) provide two pieces of syntactic sugar: to initialise lvars to
instances of pattern objects, and to de-reference them.

Some examples to show what this would look like:

;;; this
    vars x, y;
    if [?x ?y] matches [a b] then
        [first is ^x]=>
;;; becomes
    pvars x, y;
    if [^x ^y] matches [a b] then
        instantiate x;
        [first is ^x]=>

;;; and this
    lvars pat;
    vars x, y, z;
    [== ?x ??y ?z ==] -> pat;
    some_procedure_or_other(pat);
    do_something(x, y, z);
;;; becomes this
    lvars pat;
    pvars x, y = "??", z;
    [== ^x ^y ^z ==] -> pat;
    some_procedure_or_other(pat);
    instantiate x, y, z;
    do_something(x, y, z);

The examples are _not_ intended to specify what the syntax should be
like; there are lots of detailed design decisions needed. I intend only
to illustrate what I meant. In particular, you probably wouldn't use
the "pat" variable in the above example, but it does illustrate a
problem: after dereferencing x, y and z, you could still use the
pattern in pat, but you couldn't dereference x, y and z a second
time. You could, however, do something like

   lvars xx, yy, zz;
   foreach pat do
        x, y, z -> xx, yy, zz;
        instantiate xx, yy, zz;

The underlying mechanisms are ok and don't violate locality of access
to lvars whilst allowing matching procedures, but clearly better syntax
is needed.

But one further comment: Don't (as mentioned in an earlier post)
have two different pattern variable classes: there are many other
ways to extend pattern matching other than just adding segment
pattern elements. Use one class and allow subclassing (i.e. there should
be hooks in the matcher which call methods of the pattern variable
instance - an obvious use of this is in restriction procedures).

As an example of an extension, you could subclass
the segment pattern variable class to allow arbitrary order of
elements in the subsequence, so that the pattern (with ss a pvar)
    [== foo ^ss baz ^ss grum ==]
would match
    [cat foo dog hen baz hen dog grum cow]

Many other extensions spring to mind.

Jonathan Cunningham



Wed, 20 May 1998 03:00:00 GMT  
 Making the matcher robust?

| I often write code (in languages other than pop11) which use a
| procedural matcher (i've lost count of how many times i've written
| simple, one-off, dedicated matchers :-). [Presumably anathema to
| Chris Dollins ;-)].

No, no. I prefer generality, but it's always nice to have another go at
rewriting code.

| If I had to now add matching to pop11, I would do it like this.
| (1) use instances of a pattern variable class, instead of query
| variable-name. A bit like the way prolog unification works.
| (2) provide two pieces of syntactic sugar: to initialise lvars to
| instances of pattern objects, and to de-reference them.

I'd provide some pattern constructors and accessors, plus a matching
primitive (of course), and probably some syntactic sugar for the boring
cases.

[Oh rats, I've just accidentally justified the rest of jon's message,
making it unquotable. Still ...]

For example, I'd have pattern constructors

    pattern_id( name )          A pattern variable
    pattern_ident name          Ditto, except bound to ``ident name''
    pattern_id_value( pattern ) Gets value from pattern_id

plus the obvious

    pattern_seq( p1, p2 )       Sequencing
    pattern_alt( p1, p2 )       Alternative
    pattern_rep( p )            Repetition
    pattern_sat( p, pred )      Pattern constrained by predicate

plus

    pattern_match_bool( target, pattern )   simple test
    pattern_match_how( target, pattern )    test + answers

the latter returning the ``results'' in terms of what matched how,
probably as stuff on the stack, but with lists and vectors as
alternatives. Other possibilities come readily to mind. For example,
there's no reason to constrain matching to lists; matching over records
and vectors would be natural.

As with Jon's example, the details (such as the actual names of the
constructors) would need deeper thought. And there would be special
syntax for common cases, so one could write:


        -> lvars (a, b, two);
        ...
    else
        ;;; either nothing or 0 on the stack, need to think about it
    endif

``## [?a ?b]'' is just syntax for something like

    pattern_seq( pattern_id( "a" ), pattern_seq( pattern_id( "b" ), [] ) )

Regards | "Always code as if the guy who ends up maintaining your code will be
Kers.   | a {*filter*} psychopath who knows where you live." - John F. Woods



Fri, 22 May 1998 03:00:00 GMT  
 
 [ 5 post ] 

 Relevant Pages 

1. Regular Expression Matcher v1.1

2. Pattern Matcher class?

3. FoSM Forth String Matcher

4. Forth Pattern Matcher Design

5. Regular expression pattern matcher in Modula-2?

6. string regular expression matcher?

7. Matcher

8. Matcher

9. Rete matcher wanted

10. Bigloo's pattern matcher

11. showmatch.py, regex matcher

12. A little template matcher

 

 
Powered by phpBB® Forum Software