HELP READPATTERN                                 Aaron Sloman, Oct 1996

LIB READPATTERN

To make this available do

    uses readpattern

Unless ! has been made autoloadable, in $poplocal/local/auto/!.p


CONTENTS - (Use <ENTER> g to access required sections)

 -- Prerequisites
 -- Introduction
 -- -- pop_pattern_lvars (default true)
 -- -- pop_lvars_warning (default true)
 -- Motivation for "!"
 -- FMATCHES and DOESMATCH
 -- Examples of the use of "!"
 -- -- list_between
 -- -- Using ![ ... ] outside a procedure definition
 -- Do not use "vars" with ![ ... ]
 -- The structures created using "!"
 -- -- Example of use with with "vars"
 -- -- Example using lvars
 -- -- ?<var> and ??<var> are ignored in embedded vector expressions
 -- -- "!" works with a list inside an embedded vector expression
 -- -- Note on tracing procedures using "!"
 -- -- WARNING: avoid quoted occurrences of "?" and "??"
 -- Using a restriction procedure held in an lvars variable
 -- Using an optional procedure to constrain doesmatch
 -- Use of "!" with section variables
 -- Using "!" with dlvars
 -- Type3 lvars bound by the matcher
 -- Using "!" with database procedures
 -- -- Some examples of "!" used with the database
 -- . present
 -- . allpresent
 -- . foreach
 -- . forevery
 -- . which and which_values

-- Prerequisites ------------------------------------------------------
It is assumed that the reader is familiar with the Pop-11 pattern
matcher. See HELP * MATCHES for a summary overview.

For a full tutorial introduction see the following
    TEACH *MATCHES
    TEACH *MATCHES2
    TEACH *MOREMATCH
    TEACH *MATCHARROW
        (Birmingham only. Revised version of MATCHES2)

or the POP-11 Primer TEACH * PRIMER, chapter 7.
From Poplog version 15.0 this is available as TEACH * PRIMER7

For information about the Pop-11 database, which makes use of the
matcher, see
    HELP * DATABASE

A tutorial introduction can be found in
    TEACH * DATABASE
    TEACH * FOREACH
    TEACH * RIVER2
        (Improved version available at Birmingham.)


-- Introduction -------------------------------------------------------

LIB READPATTERN makes available a new syntactic operator "!" and a new
syntax word "where", for creating patterns in which the words
representing pattern variables are replaced by identifers, so that the
pattern matcher can be used with lvars and with variables that are local
to sections, in the following sort of construct

    [ .... ] matches ![ ... ?x .... ??y ...]

The pattern variables "x" and "y" will be replaced, at compile time,
with identifiers.

The main addition is "!". The syntax word "where" is for use with a new
more general version of the matcher, defined in LIB DOESMATCH, which
takes an optional extra procedure for checking whether a match is
satisfactory. See HELP DOESMATCH. If you use only "matches" then you can
ignore "where".

In addition a utility procedure, readpattern, is provided.

-- -- pop_pattern_lvars (default true)
Note: by default the identifiers introduced by "!" will be defined as
lexical idents. I.e. they will be compatible with existing lvars
declarations of the variables used, or will create new implicit
lvars declarations, so that the variables are totally local to a
procedure, as they should be. This default can be turned off, by the
assignment

    false -> pop_pattern_lvars;

However, in general it may be better to leave the default and do a
separate assignment.

-- -- pop_lvars_warning (default true)

If a pattern variable has not yet been declared, or if it is to be
automatically declared as lvars in a procedure and the only
declaration currently in scope is as a permanent variable using "vars",
then a warning message is displayed, unless pop_lvars_warning is false.

Warning messages are displayed by a procedure that users can redefine.
Its default definition is

define global vars pr_patt_var_warning(word);
    printf(word, ';;; WARNING DECLARING PATTERN VARIABLE %P AS LVARS\n');
    if popfilename then
        printf(popfilename, ';;; IN FILE %P\n');
    endif;
    if isinteger(poplinenum) then
        printf(poplinenum, ';;; LINE %P\n');
    endif
enddefine;


-- Motivation for "!" -------------------------------------------------

Prior to Poplog version 15 a major weakness of the Pop-11 pattern
matcher was that because it used valof to manipulate pattern variables
it could not be used with lvars variables nor with section variables,
as the procedure valof was applied only to words, and worked only in the
current section, not the section in which a pattern had been
constructed. See HELP * VALOF

In Poplog version 15 the procedure valof was generalised so that it
could be applied to identifiers, often referred to as idents.
(See REF * IDENT). This made it possible to use the syntax operator "!"
to transform patterns to contain idents instead of words. This makes the
use of the matcher much safer, since it no longer requires access to
"permanent" variables (i.e dynamically scoped variables).

    See HELP * LEXICAL for a brief introduction to types of variables.
    REF * IDENT gives more detail.


-- FMATCHES and DOESMATCH ---------------------------------------------

LIB * FMATCHES was an early attempt to overcome the restriction of
MATCHES to dynamically scoped variables, but it had some serious
disadvantages, as it did not allow patterns to be given as arguments to
procedures. See HELP * FMATCHES

FMATCHES also remedied some deficiencies in the standard matcher, which
prevented it finding certain matches involving patterns with more than
one segment variable.

LIB DOESMATCH, available from the Birmingham ftp site, generalises the
matcher to cope with the extra matches not found by the standard
matcher, and also provides an optional extra "where" construct, when
used with "!". However, DOESMATCH can be used without "!" and "!" can be
used without DOESMATCH. (See HELP * DOESMATCH).

-- Examples of the use of "!" -----------------------------------------

Almost any use of the pattern matcher can be converted to work more
safely and efficiently with "!". Here are some examples.

-- -- list_between

E.g. here's a procedure to make a list of the items between two
specified elements in a list.

;;; Make sure readpattern has been compiled

uses readpattern

define list_between(item1, item2, list) -> found;
    ;;; Here found is automatically declared as lvars, as are the input variables
    ;;; in Poplog version 15

    unless list matches ![== ^item1 ??found  ^item2 ==] then
        false -> found;
    endunless;

enddefine;

;;; Now test the procedure

vars words = [a b c d e f g];

list_between("a", "g", words) =>
** [b c d e f]

list_between("c", "g", words) =>
** [d e f]

list_between("b", "b", words) =>
** <false>

list_between("g", "e", words) =>
** <false>

Note that the value returned by the procedure is the value of the output
local variable found, which is a lexical variable, which is given a
value by matches when the match is successful. This is possible only
because valof, which is used by the matcher, now works on identifier
records as well as words.

-- -- Using ![ ... ] outside a procedure definition

If ![ ... ] is used in a procedure definition then it is assumed by
default (unless pop_pattern_lvars is made false) that all pattern
variables are lvars. However if it is used outside a procedure
definition, the pattern variables are not redefined. Their current type
is simply used, i.e. permanent or lexical.

Here's an example with a permanent variable. At the top level, outside
the scope of an existing lvars declaration, "!" assumes that pattern
variables should be non-lexical, i.e. permanent.

Compile the next two lines separately:

vars silly1;

[1 2 3 4 5] matches ![== 2 ??silly1 = ], silly1 =>
** <true> [3 4]

Here's an example with a lexical variable. Mark and compile the next two
lines at once.

lvars silly2;

[1 2 3 4 5] matches ![== 2 ??silly2 = ], silly2 =>
** <true> [3 4]

If, outside a procedure definition, you use a pattern variable that has
not been declared previously, it will be declared automatically, as
usual:

[1 2 3 4 5] matches ![== 2 ??silly3 = ], silly3 =>
;;; DECLARING VARIABLE silly3
** <true> [3 4]


-- Do not use "vars" with ![ ... ] ------------------------------------

Because variables in patterns created with ![ ... ] are lexical by
default, they should not be declared as local variables with vars
or dlocal, or an error message will result.

vars silly4;

define test();
    dlocal silly4;

    [1 2 3 4 5] matches ![== 2 ??silly4 = ] =>

enddefine;

;;; MISHAP - LEXICAL IDENTIFIER IS ALREADY A DYNAMIC LOCAL
;;; INVOLVING:  silly4
;;; COMPILING:  test
;;; DOING    : ....

The same error message would result if "vars" were used in the
definition instead of "dlocal".

The global variable pop_pattern_lvars, which defaults to true, can be
made false if you need to have a pattern variable which is dlocal. But
normally that is best done as follows.


vars silly4;

define test2();
    dlocal silly4;

    if [1 2 3 4 5] matches ![== 2 ??silly5 = ] then
        silly5 -> silly4;
        ;;; etc
    endif;

enddefine;


I.e. if the match is successful, use the lvars pattern variable (in this
case silly5) to set the value of the permanent variable which has been
made dlocal (in this case silly4). This method can be used with global
non-lexical variables such as database, cucharout, interrupt, etc.


-- The structures created using "!" -----------------------------------

It is possible to create and examine the lists that "!" creates.

-- -- Example of use with with "vars"

"vars" can be used to declare permanent identifiers. The use of ![ .... ]
allows a pattern to include the corresponding identifier records instead
of the words. E.g.

vars var1, var2;
![cat ?var1 mouse ??var2 ==]  =>
** [cat ? <ID var1 <undef var1>> mouse ?? <ID var2 <undef var2>> ==]

How the identifiers are shown when such a pattern is printed
out will depend on their values. Once an identifier has been given a
value, its printed appearance changes.

99 -> var2;
![?var1 ?var2] =>
** [? <ID var1 <undef var1>> ? <ID var2 99>]

Here var1 still lacks a value, whereas var2 has 99 as value. Once an
identifier has a value the printed form no longer indicates which
identifier it was, which can sometimes be a problem during debugging.

Note that because var1 and var2 are declared using "vars" the
declarations and the commands using them do not have to be compiled
simultaneously (as explained in TEACH * VARS_AND_LVARS).

Contrast the use of lvars:

-- -- Example using lvars

Ensure that both the following two lines are marked and loaded at once:

lvars lv1, lv2;
! [lv1 ?lv1 lv2 ?lv2 ] =>
** [lv1 ? <ID lv1 <undef>> lv2 ? <ID lv2 <undef>>]

Here the lexical idents are substituted after occurrences of "?".
Lexical idents do not show the original names, even if they have not
been initialised. If they have been given values, this is what happens:

lvars lv1 = 88, lv2 = 99;
! [lv1 ?lv1 lv2 ?lv2 ] =>
** [lv1 ? <ID lv1 88> lv2 ? <ID lv2 99>]

I.e. the values of the idents are shown.


If the pattern expression is compiled on its own, it is outside the
scope of the lexical declarations, so the lexical identifiers will not
be used:
! [A ?XX B ??Y] =>
;;; DECLARING VARIABLE XX
;;; DECLARING VARIABLE Y
** [A ? <ID XX <undef XX>> B ?? <ID Y <undef Y>>]

Note that this causes XX and YY to be declared globally. They are not
lvars.

If such a pattern occurred inside a procedure definition, however, the
variables would be made lexical locals to the procedure.


-- -- ?<var> and ??<var> are ignored in embedded vector expressions

Note that the occurrences of ?v2 inside an embedded vector expression
will not be replaced with identifiers. All occurrences of a word after
"?" or "??" which are not embedded in vector sub-expressions, will be
replaced.

vars v1,v2,v3;
! [v1 ?v1 {v2 ?v2 [?v2]} [v3 ??v3]] =>
** [v1 ? <ID v1 <undef v1>> {v2 ? v2 [? v2]} [v3 ?? <ID v3 <undef v3>>]]


-- -- "!" works with a list inside an embedded vector expression

vars v1, v2;
![{% ![?v1] % ?v2 }] =>
** [{[? <ID v1 <undef v1>>] ? v2}]

The sub expression ![?v1] works even though it is inside a vector
expression, because it is between "% ... %" implying that the code is to
be evaluated.


-- -- Note on tracing procedures using "!"

If doesmatch and other procedures using patterns created with "!" are
traced, then identifiers will show up in patterns with their current
values, not the names of the identifiers.

This example shows how identifiers look if they are initialised before
the patterns are created. Compile the next two lines together.

lvars lv4 = 99, lv5 = "cat" ;
![lv4 ?lv4 lv5 ?lv5] =>
** [lv4 ? <ID lv4 99> lv5 ? <ID lv5 cat>]

-- -- WARNING: avoid quoted occurrences of "?" and "??"

Patterns created using "!" must not contain evaluated sub-expressions
quoting "?" or "??", e.g.

    ![== [?x b] == [?x h ^(consword("?" >< 'foo')] ==], x =>
    ;;; MISHAP - NON-WORD AFTER ?
    ;;; INVOLVING:  'foo'

Finally note that patterns containing lexically scoped variables cannot
be compiled as list constants. (See LIB * COMPILE_MODE)


-- Using a restriction procedure held in an lvars variable ------------

When "!" is used to transform a pattern, the item following ":" can be a
lexical variable whose value is a procedure, or a number, as in this
example. Note the need to separate ":" and "^":

This will also work with matches:
lvars x, check = isword;
[a b c 3 4 c d 4 5 e] matches ![== ?x == ?x: ^check ==], x=>
** <true> c

The restriction can also be a number, restricting the length of a
segment variable. Find four items just before "c".

lvars x, check = 4;
[a b c 3 4 c d 4 5 e] matches ![== ??x: ^check c ==], x=>
** <true> [b c 3 4]

This also works with restriction held in vars variables.
vars x, num = 4;
[a b c 3 4 c d 4 5 e] matches ![== ??x: ^num c ==], x=>
** <true> [b c 3 4]

NB: the space between ":" and "^" is essential. (Why?)


-- Using an optional procedure to constrain doesmatch -----------------

Doesmatch can take an optional extra boolean procedure as third
argument, which it uses to check that the match is OK.

See HELP DOESMATCH for information on how a "where" clause can be used
with the "!" notation in some contexts. E.g.

lvars aaa, bbb;
[1 2 3 4] doesmatch ![?? aaa ?? bbb] where ([^aaa ^bbb] => false) ->;
** [[] [1 2 3 4]]
** [[1] [2 3 4]]
** [[1 2] [3 4]]
** [[1 2 3] [4]]
** [[1 2 3 4] []]

Compare the following, which does not use "!", and therefore cannot use
a where clause, but needs a procedure argument for doesmatch:

lvars aaa, bbb;
[1 2 3 4]
    doesmatch
        ([??aaa ?? bbb], procedure; [^aaa ^bbb] => false endprocedure) ->;
;;; DECLARING VARIABLE aaa
;;; DECLARING VARIABLE bbb
** [<undef> <undef>]
** [<undef> <undef>]
** [<undef> <undef>]
** [<undef> <undef>]
** [<undef> <undef>]

The reason for this unhelpful printout is that without using "!" the
pattern contains words, and when the matcher runs it uses the updater of
valof on the words. That does not access the lexical variables aaa and
bbb, and causes new global (permanent) variables to be declared.

Consequently aaa and bbb retain their undefined values in the procedure,
and these are printed out by the print command .

-- Use of "!" with section variables ----------------------------------

One of the problems with the Pop-11 matcher was this: If a procedure is
defined in a section, and then invoked in another section the matcher
was unable to access the variables that were in the section in which the
procedure was compiled. By using "!" to insert identifier records in
patterns we can overcome this restriction.

However, to prevent "!" always turning the lvars into lexical variables,
which is the default behaviour we can use the following to allow
pattern identifiers to be ether vars or lvars, depending on their
current status:

    false -> pop_pattern_lvars;

The default is

    true -> pop_pattern_lvars;


Mark and load the whole section, which exports the procedure test1,
which checks whether its input includes a word.

    section ss1 => test1;

    ;;; allow non-lexical pattern variables.
    false -> pop_pattern_lvars;

    vars item;
    define test1(list) -> x;
        dlocal item;
        if list matches ![== ? item:isword ==] then
            item -> x;
        else
            false -> x;
        endif;
    enddefine;

    endsection;

;;; test test1 outside the section.
test1([1 2 3 ]) =>
** <false>
test1([1 2 a 3 ]) =>
** a

Using "!", we can also import a procedure into a section without
importing its local vars. Compile the whole section below in one go,
after compiling test3

vars pp, list;
;;; allow non-lexical pattern variables.
false -> pop_pattern_lvars;

define test3(list) -> pp;
    ;;; find at least three elements in a five (or more) element list
    dlocal list, pp;
    unless list matches ![ == = ??pp:3 = ==] then
        false -> pp
    endunless
enddefine;

section ss2 test3;

test3([1 2 3 4]) =>

test3([1 2 3 4 5 6]) =>

endsection;

;;; it should print out
** <false>
** [2 3 4]

It would also work with doesmatch instead of matches, though it may not
find the same three elements. When there are several occurrences of
segment pattern elements, i.e. "==" and "??", in a pattern, the result
of matching can be non-determined.

Without "!" the matching would not work. (Why not?)

We can reset the default behaviour of "!" by doing
    true -> pop_pattern_lvars;


-- Using "!" with dlvars ----------------------------------------------

Reset the default.
    true -> pop_pattern_lvars;

In some cases dlvars can be more efficient than lvars, where no closure
is to be returned by the procedure, or stored anywhere.
(See HELP * LVARS)

This procedure looks in a list for a repeated segment of length >= 2.

define test2(list) -> p;
    lvars list;

    dlvars p, q ;   ;;; pattern variables

    unless list doesmatch ![== ??p == ??q == ]
        where p = q and length(p) > 1 and length(q) > 1
    then
        false -> p
    endunless;
enddefine;

test2([1 2 3]) =>
** <false>

test2([1 2 3 4 2 3 5]) =>
** [2 3]

;;; But it does not find them all
test2([1 2 3 4 a 2 3 4 5]) =>
** [2 3]

The above would also work with "lvars" instead of "dlvars".


-- Type3 lvars bound by the matcher -----------------------------------

Lexical pattern vars work with type 3 lvars as defined in REF VMCODE,
e.g. lvars that are non-local to a procedure that is returned as a
result.

define make_proc(list) -> proc;
    ;;; Return a procedure containing a lexical variable bound in
    ;;; the pattern match
    lvars list, proc, pp;

    if list matches ![ = ? pp = ] then
        ;;; return this procedure to access the value of pp
        procedure; pp endprocedure
    else
        false
    endif -> proc;

    ;;; Give the procedure an updater
    procedure();
        -> pp
    endprocedure -> updater(proc);
enddefine;

;;; use make_proc to create a procedure
vars proc = make_proc([1 2 3]);

;;; Test the procedure
proc()=>
** 2

;;; Test its updater
99 -> proc();
proc()=>
** 99

;;; Check that two such results do not interfere with each other.
;;; Make another procedure
vars proc2 = make_proc([5 6 7]);

;;; Test the new procedure
proc2()=>
** 6

;;; Has it affected the previous one?
proc() =>
** 99

;;; Test its updater
55 -> proc2();
proc2()=>
** 55

;;; Does proc still have the same stored value?
proc() =>
** 99

-- Using "!" with database procedures ---------------------------------

See HELP * DATABASE, TEACH * DATABASE

LIB FMATCHES could not be used to define procedures like the Pop-11
database procedures, present, remove, flush, allpresent, and the
iteration constructs foreach, forevery, etc. (see HELP * DATABASE).
The reason it could not be used was that fmatches could not be passed a
pattern created in another procedure, as is possible with doesmatch and
matches.

Consequently, it was not previously possible to use the Pop-11 database
procedures with lexical variables or section variables. This can now be
done using "!", whether the matcher used is matches or doesmatch.

-- -- Some examples of "!" used with the database

;;; Set up an initial database
[[a ison b][d ison c] [b ison table][e ison c][c ison table]] -> database;

-- . present
;;; We can use present with a pattern containing a lexical variable:
;;; See HELP * PRESENT

lvars x1; present( ![?x1 ison c] ), x1 =>
** <true> d

it =>
** [d ison c]

-- . allpresent
;;; We can make all the database facilities work with lvars, section
;;; variables, etc., if we use "!"
;;; See HELP * ALLPRESENT

;;; Compile the next two lines together

lvars item1, item2, item3;
allpresent(![[?item1 ison ?item2][?item2 ison ?item3][?item3 ison table]])=>
** <false>

;;; compile the next two lines together.
lvars item1, item2, item3;
allpresent(![[?item1 ison ?item2][?item2 ison ?item3]])=>
** <true>
them =>
** [[a ison b] [b ison table]]

(See HELP * ALLPRESENT)

-- . foreach
;;; Now try foreach with lvars pattern variables. See HELP * FOREACH

lvars x,y; foreach ![?x ison ?y] in database do [^x ^y] => endforeach;
** [a b]
** [d c]
** [b table]
** [e c]
** [c table]


;;; try it without "!", after cancelling x and y, and see what happens
cancel x,y;
lvars x,y; foreach [?x ison ?y] in database do [^x ^y] => endforeach;
;;; DECLARING VARIABLE x
;;; DECLARING VARIABLE y
** [<undef> <undef>]
** [<undef> <undef>]
** [<undef> <undef>]
** [<undef> <undef>]
** [<undef> <undef>]

Because "!" was not used, identifiers were not inserted in the list, so
the words "x" and "y" are left. The matcher uses the words as globals,
but the list expression [^x ^y] uses the lexical variables, which are
not bound by the matcher. Hence the undef values.

-- . forevery
;;; forevery also works with lvars, if we use !
;;; See HELP * FOREVERY

;;; Compile the next three lines together
lvars x,y,z;
forevery ![[ ?x ison ? y][?y ison ?z]] do [^x above ^z]=>
endforevery;
** [a above table]
** [d above table]
** [e above table]

;;; WARNING:
;;; you can't use "where" in the above database looping constructs

lvars x,y;
foreach ![?x ison ?y] where y == "table" do [^x ^y] =>
endforeach =>
** [? <ID x <undef>> ison ? <ID y <undef>>]


-- . which and which_values
Some of the database procedures, e.g. which, require slight
modifications to handle patterns containing identifier records, as they
explicitly check only for words.

See HELP * WHICH

;;; Set up an initial database
[[a ison b][d ison c] [b ison table][e ison c][c ison table]] -> database;
database ==>

which([x z], [[?x ison ?y][?y ison ?z]]) ==>
** [[a table] [d table] [e table]]


;;; This also works with ! provided the variables are not lvars.
vars x, z;
database ==>
which([x z], ![[?x ison ?y][?y ison ?z]]) ==>

It cannot work with lvars. However the following procedure which_values
loosely modelled on LIB * WHICH will work, provided that the first
argument uses "?" before each variable.


define which_values(Vars, Patternlist) -> List;
    ;;; Vars should be a list of variables prefixed by "?" transformed by "!"
    ;;; Patternlist should be a list of patterns, the whole having been transformed
    ;;; by "!"

    lconstant err_string = 'LIST NEEDED FOR "WHICH"';

    if ispair(Vars) then
        if ispair(Patternlist) then
            [%forevery Patternlist do
                lvars list;
                [%for list on Vars do
                    if hd(list) == "?" or hd(list) == "??" then
                        valof(hd(tl(list)))
                    endif
                  endfor%]
              endforevery%] -> List
        else mishap(err_string, [^Patternlist])
        endif;
    else
        mishap(err_string, [^Vars] )
    endif;
enddefine;

/*
;;; Now some tests
;;; Set up a database

[[a ison b][d ison c] [b ison table][e ison c][c ison table]] -> database;
database ==>

;;; Now we can do the following. We put "!" before the variable
;;; list as well as before the pattern.

;;; Find all the things x, z such that
;;;         there is a y, and x ison y and y ison z.

lvars x, y, z;
which_values(![?x ?z], ![[?x ison ?y][?y ison ?z]]) ==>
** [[a table] [d table] [e table]]
** [[a table] [d table] [e table]]

There may be some other database procedures that would have to be
rewritten to work with patterns transformed by "!"

At Birmingham, which_values is available as an autoloadable procedure.

--- $poplocal/local/newkit/prb/help/readpattern
--- $poplocal/local/help/readpattern
--- Copyright University of Birmingham 2000. All rights reserved. ------
