NetNews Usenet Archive 1992 #27/NN_1992_27.iso/spool/comp/lang/pop/58

Internet Message Format | 1992-11-18 | 6.5 KB

Path: sparky!uunet!usc!zaphod.mps.ohio-state.edu!saimiri.primate.wisc.edu!sdd.hp.com!cs.utexas.edu!qt.cs.utexas.edu!yale.edu!ira.uka.de!math.fu-berlin.de!news.netmbx.de!Germany.EU.net!mcsun!uknet!news.cs.bham.ac.uk!axs
From: [e-mail] (Aaron Sloman)
Newsgroups: comp.lang.pop
Subject: Re: A little Pop history
Summary: illustrating pattern matching in Pop-11
Message-ID: <[e-mail]>
Date: 16 Nov 92 01:50:01 GMT
References: <[e-mail]> <[e-mail]> <[e-mail]> <[e-mail]>
Sender: [e-mail]
Organization: School of Computer Science, University of Birmingham, UK
Lines: 204
Nntp-Posting-Host: emotsun

[e-mail] (Brian Harvey) writes:

> Date: 15 Nov 92 21:20:26 GMT
> Organization: University of California, Berkeley
>
> Of course, these examples are entirely equivalent to what could be done
> in Lisp.

Agreed, or in Prolog

> I think you should post examples using some of the more unusual
> POP features, such as pattern matching.

I am tempted. Hope it's not too long.

The Pop-11 pattern matchers (there are two now) are unlike
prolog unification in that they go only one way: i.e. you can have
variables only on the right: so you can't match two variables and
have a later binding of one of them propagate to the other). However
the Pop-11 matchers compensate for this (some would say more than
compensate, others would say less than compensate) by allowing
segment variables in the middle of a list, plus restriction
procedures.

Here's an example of the use of forevery, which uses the
(original) Pop-11 matcher;

    vars x, y, z;

    vars properties =
        [[g is h][e is f] [d is e] [b is c] [a is b] [h is i]];

    forevery [[?x is ?y][?y is ?z]] in properties do
        ;;; extend the list of properties
        [[^x is ^z] ^^properties] -> properties;
    endforevery;

    properties ==>
    ** [[a is c]
        [d is f]
        [g is i]
        [g is h]
        [e is f]
        [d is e]
        [b is c]
        [a is b]
        [h is i]]


Using the matcher you can define a very simple parser. In what
follows ?<var> matches a single item in a list ??<var> matches
an arbitrarily long segment of a list. If the <var> is followed
by a colon, then the next item is taken to refer to a restriction
predicate, as in ?word:noun. If a match is successful and the
restriction predicate returns a non-boolean result, then the
result is bound to the variable.

;;; first define recognisers for lexical categories
define recognise(word, category, list) -> result;
    lvars word, category, list, result;
    if member(word, list) then
        [^category ^word] -> result;
    else
        false -> result
    endif;
enddefine;;

;;; define particular recognisers by partially applying recognise

define noun =
    recognise(%"noun", [cat dog mouse elephant man mat tree owl]%)
enddefine;

define det =
    ;;; recogniser for determiners
    recognise(%"det", [each all every a the some]%)
enddefine;

define adj =
    recognise(%"adj", [happy hungry big rich yellow striped]%)
enddefine;

define verb =
    recognise(%"verb", [ate struck chased liked stroked tickled]%)
enddefine;

;;; a utility to check that all elements of a list satisfy a predicate
define all_are(list, pred) -> result;
    lvars list, pred, result = false, item;
    for item in list do
        returnunless(pred(item))
    endfor;
    true -> result;
enddefine;

;;; now recogniser/parsers for non-terminals

define np(list) -> result;
    ;;; parse noun phrases
    lvars list,result;

    vars word1,word2,word3,list1;   ;;; pattern variables

    if list matches [?word1:det ?word2:noun] then
        [np ^word1 ^word2]
    elseif list matches [?word1:det ?word2:adj ?word3:noun] then
        [np ^word1 ^word2 ^word3]
    elseif
        list matches [?word1:det ??list1: ^(all_are(%adj%)) ?word2:noun]
    then
        [np ^word1 [adjs ^list1] ^word2]
    else
        false
    endif -> result
enddefine;

define vp(list) -> result;
    ;;; parse verb phrases
    lvars list, result;
    vars word list2;
    if list matches [?word:verb ??list2:np] then
        [vp ^word ^list2]
    else
        false
    endif -> result;
enddefine;

define sentence(list) -> result;
    lvars list,result;
    vars list1, list2;
    if list matches [??list1:np ??list2:vp] then
        [sentence ^list1 ^list2]
    else
        false
    endif -> result
enddefine;

;;; now for a bit of magic

np([the dog]) =>
** [np [det the] [noun dog]]

np([the big dog]) =>
** [np [det the] [adj big] [noun dog]]

np([each hungry yellow cat]) =>
** [np [det each] [adjs [hungry yellow]] [noun cat]]

vp([chased the cat]) =>
** [vp [verb chased] [np [det the] [noun cat]]]

sentence([the dog chased the rich yellow cat]) ==>
** [sentence [np [det the] [noun dog]]
             [vp [verb chased]
                 [np [det the] [adjs [rich yellow]] [noun cat]]]]

sentence([every rich happy elephant tickled some
            big striped yellow mouse]) ==>
** [sentence [np [det every] [adjs [rich happy]] [noun elephant]]
             [vp [verb tickled]
                 [np [det some]
                     [adjs [big striped yellow]]
                     [noun mouse]]]]

;;; or with a more pictorial display
lib showtree

showtree(sentence([the big cat liked the striped mat]));

                /--------\
                |sentence|
                \---+----/
         /----------+----------\
        /+-\                  /+-\
        |np|                  |vp|
        \+-/                  \+-/
  /------+------\       /------+------\
/-+-\  /-+-\  /-+--\  /-+--\         /+-\
|det|  |adj|  |noun|  |verb|         |np|
\-+-/  \-+-/  \-+--/  \-+--/         \+-/
  |      |      |       |      /------+------\
  |      |      |       |    /-+-\  /-+-\  /-+--\
 the    big    cat    liked  |det|  |adj|  |noun|
                             \-+-/  \-+-/  \-+--/
                               |      |      |
                               |      |      |
                              the  striped  mat

Actually it looks nicer on a terminal with graphics, but that's
not for a news posting!

Of course, there are better ways to write parsers, but this
illustrates the matcher.

(The parsing example was based on one of Poplog Pop-11's online
"teach" files, most of which contain examples that can be run at the
terminal.)

Aaron
--
Aaron Sloman, School of Computer Science,
The University of Birmingham, B15 2TT, England
EMAIL   [e-mail]  OR [e-mail]
Phone: [phone]       Fax:   [phone]