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. CONTENTS -- 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 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 TEACH LISTS TEACH BOXES 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 elseif... And also in connection with many Pop-11 database facilities illustrated in TEACH RIVER2. 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] => endif; To do something relating to EACH database item that matches a pattern: foreach ![at ?thing ?place] do [^thing is at ^place] => endforeach 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 ] => or [ ^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 findlines(); 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. Reminder: 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 e.g. 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) explode(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 way 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(list_of_lists)=> 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 enddefine; 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 e.g. 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] See HELP FOR HELP LOOPS HELP CONTROL -- How are lists actually represented in the computer? ---------------- See TEACH * BOXES 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: TEACH * REVISE There is more on the pattern matcher in proglect4 --- $poplocal/local/teach/proglect3 --- Copyright University of Birmingham 2000. All rights reserved. ------