Search                        Top                                  Index
TEACH PROGLECT3                                    Aaron Sloman Oct 1996
                                                        Updated Oct 2000

See TEACH PROGLECT1, PROGLECT2 for introductory material

This file is mainly about lists and their use in representing knowledge.


 -- Why lists are important
 -- -- Storing factual information
 -- -- Plans
 -- -- Patterns
 -- -- Storing information extracted from images
 -- -- Storing general information
 -- -- Building meta-level descriptions, e.g. grammars
 -- General descriptions can be used to generate instances
 -- General descriptions can be used to analyse instances
 -- A programmer's view of lists
 -- -- There are many procedures for operating on lists
 -- -- Also looping constructs for "iterating over" lists
 -- How are lists actually represented in the computer?

-- Why lists are important --------------------------------------------

    Lists are a derived data-structure, based on pairs, which are
    primitive data-structures in pop-11. They are explained in more
    detail in Chapter 6 of the Pop-11 primer, also in
    and other teach files.

    Lists provide a very flexible and general type of data-structure,
    with a large collection of system and library facilities for
    manipulating them, including many that are useful for AI purposes.

They can use used for at least the following sorts of purposes:

-- -- Storing factual information

They can be used for storing factual information (as in TEACH RIVER2)

        [at boat left]
        [at man left]
        [at fox left]
        [size b3 big]
        [colour b3 blue]

-- -- Plans
They can be used for storing plans

    [plan [putin chicken] [getin] [crossriver] [getout] ... ]

-- -- Patterns

A list can contain "pattern elements" which enable the list to be used
with the Pop-11 pattern matching facilities to test things and to
extract information stored in a database based on lists.

E.g. in Eliza

    if input matches [ ??thing can ??action ] then

        [ suppose ^^thing could not ^^action ] -> result


And also in connection with many Pop-11 database facilities illustrated

E.g. to check that there is at least one item in the database matching
a pattern:

    if present( ! [at ?thing ?place ] ) then
        [^thing is at ^place] =>

To do something relating to EACH database item that matches a pattern:

    foreach ![at ?thing ?place] do

        [^thing is at ^place] =>


To remove everything matching a pattern from the database:

    flush( ! [at ?thing ?place] );

Notice the difference between "?" or "??" and "^" and "^^".

The first two can be read as "Set the value of ...."

The last two can be read as "Use the value of ...."

However "?" and "??" work only in conjunction with the pattern
matcher. If you just create a list with them, they are simply components
of the list:

    [ ?person uttered ??sentence ] =>

Contrast this:

    vars person, sentence;

    "fred" -> person;
    [How are you today] -> sentence;

    [ ^person uttered: ^^sentence ] =>

    [ ^person uttered: ^sentence ] =>

So "^" and "^^" are used by the compiler as instructions when the list
is being built. "?" and "??" are used after the list is built, when
the pattern matching procedures run.

-- -- Storing information extracted from images

    showlib edgepic

    uses vturtle

    lib edgepic


    database ==>

-- -- Storing general information

By including "variables" in the lists, we can use them for storing
constraints and other general information, as in TEACH PRBRIVER

    [constraint Eat

        [   [?thing1 isat ?side]
            [NOT man isat ?side]
            [?thing1 can eat ?thing2]
            [?thing2 isat ?side]

        [?thing1 will eat ?thing2 GO BACK]

Prolog makes a great deal of use of this sort of mechanism, though with
a very different syntax.

-- -- Building meta-level descriptions, e.g. grammars

Lists are often used for building descriptions of descriptions, e.g.
descriptions of sentences. See TEACH * GRAMMAR

    uses grammar;

E.g. here is a simple lexicon (a list of allowable words)

    vars mylex =
        ;;; start a list of lexical categories
        [noun  man girl number computer cup battle room car garage]
        [verb  hated stroked kissed teased married taught added]
        [prep  in into on above under beside]
        [det   the a every each one some]

And here is a simple grammar, using lists to express rules for
    s   - a sentence
    np  - a noun phrase
    snp - a simple noun phrase
    pp  - a preposition phrase
    vp  - a verb phrase

Notice that some of the rules use structures defined in other rules.

    vars mygram =
        ;;; start a list of rules
        ;;; a sentence is a NP followed by a VP
        [s [np vp]]

        [np [snp] [snp pp]]     ;;; a NP is either a simple NP
                                ;;; or a simple NP followed by
                                ;;; a prepositional phrase PP
        [snp [det noun]]        ;;; a simple NP is a determiner followed by
                                ;;; a noun
        [pp [prep snp]]         ;;; a PP is a preposition
                                ;;; followed by a simple NP.
        [vp [verb np]]          ;;; verbphrase = verb followed by NP
    ] ;

-- General descriptions can be used to generate instances -------------

TEACH GRAMMAR shows how you can use a grammar and a lexicon to generate
sentences corresponding to the grammar and lexicon.

    generate(mygram, mylex) ==>

    repeat 20 times generate(mygram, mylex) ==> endrepeat;

-- General descriptions can be used to analyse instances --------------

Parsing a sentence is working out what its structure is in accordance
with a grammar, i.e. which complex grammatical components it contains,
and what their grammatical subcomponents are, etc.

LIB GRAMMAR allows us to create a parser for our grammar and lexicon
using setup.

This takes the rules and creates "parsing" procedures corresonding to
the grammatical categories, s, np, vp, etc.

    mygram ==>  ;;; defined above
    mylex ==>

    ;;; Create the parser. ASsumes "s" is top level category

    setup(mygram, mylex);

    s =>
    np =>

    np( [one garage] ) ==>

    np( [the man in the garage] ) ==>

    s( [some man kissed one garage] ) ==>

We can show the parse tree using VED's character graphics.

    uses showtree;

    showtree( s( [some man kissed one garage] ) );

By tracing the procedures and repeating the parse we can see how
searching is involved in analysing the sentence.

    trace s np vp snp pp verb noun;

    s( [some man kissed one garage] ) ==>

    s( [the computer in some car teased some battle] ) ==>

    untrace s np vp snp pp verb noun;

    s( [a battle under each computer teased one room] ) ==>

    showtree( s( [the computer in some car teased some battle] ) );

-- A programmer's view of lists ---------------------------------------

One use of lists is to store variable length data structures.

    vars count, numbers;

    [% for count from 1 to 8 do count endfor %] -> numbers;

    numbers =>

    vars count, list;

    [% for count from 1 to 8 do gensym("thing_") endfor %] -> list;

    list =>

    [hello ] <> tl(list) =>

    list =>

    [hello ] <> tl(list) -> tl(list);

    list =>

    tl(list) =>

    tl(tl(tl(list))) -> tl(list);

    list =>

And many more.

    lists of lists of lists of .....

As in the grammar example.

This requires understanding how to manipulate lists.

-- -- There are many procedures for operating on lists

Creating lists

    999 :: numbers =>

    ;;; that does not change numbers.

    numbers =>

    ;;; neither does this:

    numbers <> list =>

    numbers =>

You will also learn to create lists using these formats:

    [ ^...  ^^...   %...% ]

    [^numbers ^^numbers] =>

Accessing parts of lists (or updating them)
    hd, tl,

    The pattern matcher is a particularly powerful mechanism for
    accessing components of lists. TEACH * MATCHES

    vars list = [the cat sat on the very old mat];

    vars between;

    list matches [== cat ??between old ==] =>

    between =>

    list matches [== the ??between old ==] =>

    between =>

    list matches [== = the ??between old ==] =>

    between =>

There are many more procedures for operating on lists. Here is a subset
that's widely used. (Some of them will give an error if applied to an
empty list.

    ITEM :: LIST -> LIST

    LIST <> LIST -> LIST

    hd(LIST) -> ITEM
    ITEM -> hd(LIST)

    tl(LIST) -> LIST
    LIST -> tl(LIST)

    dest(LIST) -> (ITEM, LIST)
        returns the head and the tail of the LIST

    last(LIST) -> ITEM
    ITEM -> last(LIST)

        Puts all elements of the LIST on the stack

    allbutfirst(N, LIST) -> SUB_LIST
    allbutlast(N, LIST) -> SUB_LIST
        Here N is an integer

        list =>
        allbutfirst(3, list) =>
        allbutlast(3, list) =>

    rev(LIST) -> LIST
        ;;; create a new list with numbers in reverse order

        rev(numbers) =>

    member(ITEM, LIST) -> boolean

        member(3, numbers) =>
        member(33, numbers) =>

    lmember(ITEM, LIST) -> false_or_sublist

    delete(ITEM, LIST)          -> LIST
        Return a list which does not contain ITEM

    delete(ITEM, LIST, N)       -> LIST
        Remove only the first N instances of ITEM

    length(LIST) -> N

    sort(LIST) -> LIST
        Sorts a list of words, or strings, or numbers in the expected

        sort([11 5 10 3 4 2 6 8]) =>
        sort([the cat sat on the back of the hairy dog]) =>

    syssort(LIST, PREDICATE) -> LIST
        More general sorting procedure

    applist(LIST, PROCEDURE)
        Applies the procedure to every item in the list.
        May or may not produce results on stack

    maplist(LIST, PROCEDURE) -> LIST

    oneof(LIST) -> ITEM
        Selects an element at random

    shuffle(LIST) -> LIST
        Rearranges the list elements at random

        shuffle([the cat sat on the back of the hairy dog]) =>

    flatten(LIST) -> LIST
        Recursively replaces every sublist with its elements
        ("removes list brackets").

        vars list_of_lists
            = [[the cat] [sat [on the [back]] of] the dog];


            flatten is a sort of reverse of parsing.

    copylist(LIST) -> LIST
    copytree(LIST) -> LIST

These are all explained in TEACH PRIMER, and a more complete overview
is given in REF LISTS.

-- -- Also looping constructs for "iterating over" lists

Often it is useful to do something to each element of a list. The
procedure applist can do that, e.g.

    define double(x);
        x * 2

    applist([ 1 2 3 4 5], double) =>
    ** 2 4 6 8 10

However the for ... endfor construct is often more useful if you don't
want to create a special procedure to give to applist, e.g.

    vars item;

    for item in [1 2 3 4 5] do item*2 endfor =>
    ** 2 4 6 8 10

More generally, the form is

    for item in list do action endfor
        (Like applist and maplist)

It is also sometimes useful to do something first to the head of the
list, then to its tail, then to the tail of the tail, etc. For this use
a for loop with "on" instead of "in"

    for item on list do action endfor


    vars sublist;
    for sublist on [1 2 3 4 5] do sublist => endfor;
    ** [1 2 3 4 5]
    ** [2 3 4 5]
    ** [3 4 5]
    ** [4 5]
    ** [5]



-- How are lists actually represented in the computer? ----------------


For lower level gory details: TEACH * WAL
 (What Are Lists)

See also the Pop11 PRIMER, Chapter 6, on lists.

For some general revision of Pop-11 and VED see the test questions in:


There is more on the pattern matcher in proglect4

--- $poplocal/local/teach/proglect3
--- Copyright University of Birmingham 2000. All rights reserved. ------