Search Top Index
HELP MATCHES A. Sloman, March 1982 Modified 29 Jun 2009 <list> matches <list with pattern elements> -> <boolean>; <list> --> <list with pattern elements>; For a tutorial introduction to the POP-11 matcher see the following TEACH files: TEACH *MATCHES TEACH *MATCHES2 TEACH *MOREMATCH CONTENTS - (Use <ENTER> g to access required sections) -- THE POP-11 MATCHER -- PATTERN ELEMENTS WITH ADDITIONAL RESTRICTIONS -- THE MATCHER ARROW -- Note on "!" with patterns -- THE POP-11 MATCHER -------------------------------------------------- MATCHES is an infix operator which takes two arguments, returns a boolean result (TRUE or FALSE), and as a side effect can bind variables. The first argument is any list, and the second argument is a list which may contain pattern elements. MATCHES works by attempting to find a match between the two lists; ordinary list elements must be identical, but list elements in the first list may match pattern elements in the second. These elements make certain restrictions on what can be in that position in the list. Pattern elements may be: = match one item == match an arbitrary number of items ?<variable> match one item and bind it to the variable ??<variable> match any number of items (possibly none), make a list of them, and bind the list (possibly []) to the variable. (Note: MATCHES can also be used with vectors as arguments, but ?<variable> and ??<variable> do not work on vectors; MATCHES simply behaves like = under these circumstances.) -- PATTERN ELEMENTS WITH ADDITIONAL RESTRICTIONS ----------------------- ??<variable>:integer e.g. ??x:3 Restrict the variable to match the given number of items. ?<variable>:<procedure name> e.g. ?x:isword ?<variable>:<procedure> e.g. ?x: % ismorethan(%0%) % Before allowing the match, apply the procedure to the matching item. If the result is FALSE, don't allow the match to succeed. If the result is TRUE, allow it. If the result is anything else, allow the match, but bind the result to the variable. ??<variable>:<procedure name> e.g. ??x:noun_prhase ??<variable>:<procedure> e.g. ??x: % refersto(%item%) % Other elements of patterns are compared with corresponding elements of the list, using the equality test = rather than strict equality ==, so that two lists, strings or vectors with the same elements will match. -- -- Examples of the matcher at work: vars list x y; [a b c d e] -> list; list matches [a b c d e] => ** <true> list matches [ a == e] => ** <true> list matches [ a = c = e] => ** <true> list matches [ a = d = e ] => ** <false> -- -- Examples with variable binding: list matches [?x b c d e] => ** <true> x=> ** a list matches [?x d e] => ** <false> list matches [??x d e] => ** <true> x => ** [a b c] list matches [??x c ??y] => ** <true> x=> ** [a b] y=> ** [d e] list matches [??x ??y] => ** <true> x=> ** [] y=> ** [a b c d e] -- -- Repeated Variables: If the same variable is used more than once in the pattern, the match will succeed only if it is matched against the same thing in all its occurrences. Thus: [a b c a b c] matches [??x ??x] => ** true x=> [a b c] [a b c c b a] matches [??x ??x]=> ** false -- -- Examples with restrictions on matches: list matches [??x:3 ??y] => ** <true> x => ** [a b c] y=> ** [d e] list matches [?x:isinteger ??y] => ** <false> list matches [?x:isword ??y] => ** <true> x=> ** a y=> ** [b c d e] list matches [??x:length d e] => ** <true> x=> ** 3 define value(item); if item == "a" then 10 elseif item == "b" then 20 else false endif enddefine; list matches [?x:value == ] => ** <true> x=> ** 10 list matches [== ?x:value] => ** <false> list matches [??x:value d e] => ** <false> [a 3 ] matches [a ?x: %nonop>(%0%)%] => ** <true> x=> ** 3 -- THE MATCHER ARROW --------------------------------------------------- The infix operator --> calls MATCHES, but instead of producing a boolean result it produces no result, but causes an error if the arguments don't match. It can therefore function as a multiple assignment, e.g. list --> [?x ?y ?z] will assign the three elements of LIST to X, Y and Z. -- -- WARNING: If a match fails, variables in the pattern have undefined values. I.e. the value can be altered by either a successful or an unsuccessful match. -- Note on "!" with patterns ------------------------------------------ An extension to Pop-11 produced at Birmingham allows patterns to be preceded by "!" which has the effect that if the pattern is used inside a procedure, then the pattern variables preceded by "?" or "??" can be made "lvars", so that they do not need to be declared as "vars". SEE TEACH * VARS_AND_LVARS This reduces bugs in programs due to unintended interactions between global variables, and also allows variables declared as "lvars" to be used in patterns. Example: define next_after(item, list) -> next; ;;; given item and list, return the first thing after item in list ;;; or false if there isn't one. ;;; Note: input and output variables (item, list and next) are ;;; automatically declared as lvars. lvars found; ;;; the pattern variable if list matches ! [ == ^item ?found == ] then found -> next else false -> next endif enddefine; /* ;;; Test that: next_after(3, [1 2 3 4 5]) => ** 4 next_after(6, [1 2 3 4 5]) => ** <false> next_after("cat", [the cat [did sit] on mat] ) => ** [did sit] */ That procedure would not work without the "!" list prefix. The space between "!" and "[" is not required. It was inserted for clarity. Strictly speaking, preceding a pattern with "!" inside a procedure does TWO things. First it treats all the pattern variables in the list, i.e. all those following "?" or "??", as lvars local to the current procedure. If you have not declared those variables as lvars you will get a warning message. Try removing the lvars declaration from the above procedure and recompiling it. Secondly it changes the pattern so that instead of words following "?" or "??" it contains identifier records, which the pattern matcher can use to "communicate with" the local lvars in the procedure. This is possible only since Poplog Version 15.0 The change to the pattern contents may show up if you use the Pop-11 tracer. This is how patterns print out without and with "!". [ == cat ?next == ] => ** [== cat ? next ==] ! [ == cat ?next == ] => ** [== cat ? <ID next <undef next>> ==] The <ID ...> tells you that a word has been replaced with an identifier, and the <undef next> tells you that this is an undefined global variable. If you give the identifier a value, its value shows when the pattern is printed out: "dog" -> next; ! [ == cat ?next == ] => ** [== cat ? <ID next dog> ==] Inside a procedure, the default undefined value is likely to be 0, though that depends on the implementation. See also HELP *MATCHESONEOF - takes a list of patterns and tries to find one match *MATCHESALLOF - takes a list of patterns, all of which must match *DATABASE - use of the POP-11 DATABASE *AREIN - matches a list of patterns against list elements *ISIN - matches a single pattern against list elements *FMATCHES - a version of the matcher that can use lexical variables, work in sections, and solve some matching problems that -matches- cannot. This is now redundant because of "!" --- C.all/help/matches --- Copyright University of Sussex 1990. All rights reserved. ----------