Compound Lists

A list of integers can be simply declared as

    integerlist = integer*

The same is true for a list of real numbers, a list of symbols, or a list of strings.

However, it is often valuable to store a combination of different types of elements within a list, such as:

    [2, 3, 5.12, ["food", "goo"], "new"] /* Not correct Visual Prolog*/

Compound lists are lists that contain more than one type of element. You need special declarations to handle lists of multiple-type elements, because Visual Prolog requires that all elements in a list belong to the same domain. The way to create a list in Prolog that stores these different types of elements is to use functors, because a domain can contain more than one data type as arguments to functors.

The following is an example of a domain declaration for a list that can contain an integer, a character, a string, or a list of any of these:

DOMAINS                        /* the functors are l, i, c, and s */
    llist = l(list); i(integer); c(char); s(string)
    list = llist*

The list

    [ 2, 9, ["food", "goo"], "new" ]  /* Not correct Visual Prolog */

would be written in Visual Prolog as

    [i(2), i(9), l([s("food"), s("goo")]), s("new")]
                                          /* Correct Visual Prolog */

The following example of append shows how to use this domain declaration in a typical list-manipulation program.

/* Program ch07e09.pro */

Exercises

Write a predicate, oddlist, that takes two arguments. The first argument is a list of integers, while the second argument returns a list of all the odd numbers found in the first list.

Write a predicate, real_average, that calculates the average value of all the elements in a list of reals.

Write a predicate that takes a compound list as its first argument and returns a second argument that is the list with all the sub-lists removed. This predicate is commonly known as flatten, as it flattens a list of lists into a single list. For example, the call

    flatten([s(ed), i(3), l([r(3.9), l([s(sally)])])], r(4.21), X)

returns

    X = [s(ed), i(3), r(3.9), s(sally), r(4.21)]
    1 Solution

which is the original list, flattened.

Parsing by Difference Lists

Program 10 demonstrates parsing by difference lists. The process of parsing by difference lists works by reducing the problem; in this example we transform a string of input into a Prolog structure that can be used or evaluated later.

The parser in this example is for a very primitive computer language. Although this example is very advanced for this point in the tutorial, we decided to put it here because parsing is one of the areas where Visual Prolog is very powerful. If you do not feel ready for this topic, you can skip this example and continue on in the tutorial without any loss of continuity.

/* Program ch07e10.pro */

Load and run this program, then enter the following goal:

    Goal tokl("b=2; if b then a=1 else a=2 fi; do a=a-1 while a;",Ans),
       s_program(Ans,Res).

Visual Prolog will return the program structure:

    Ans=["b","=","2",";","if","b","then","a","=","1",
        "else","a","=","2","fi",";","do","a","=","a",
        "-","1","while","a",";"
        ],
    Res=program([assign("b",int(2)),
                        if_then_else(var("b"),assign("a",int(1)), assign("a",int(2))),
                        while(var("a"),assign("a",minus(var("a"),int(1))))
                        ])
    1 Solution

The transformation in this example is divided into two stages: scanning and parsing. The tokl predicate is the scanner; it accepts a string and converts it into a list of tokens. All the predicates with names beginning in s_ are parser predicates. In this example the input text is a Pascal-like program made up of Pascal-like statements. This programming language only understands certain statements: IF THEN ELSE, IF THEN, DO WHILE, and ASSIGNMENT. Statements are made up of expressions and other statements. Expressions are addition, subtraction, variables, and integers.

Here's how this example works:

The first scanner clause, s_program, takes a list of tokens and tests if it can be transformed into a list of statements.

The predicate s_statementlist takes this same list of tokens and tests if the tokens can be divided up into individual statements, each ending with a semicolon.

The predicate s_statement tests if the first tokens of the token list make up a legal statement. If so, the statement is returned in a structure and the remaining tokens are returned back to s_statementlist.

The four s_statement clauses correspond to the four types of statements the parser understands. If the first s_statement clause is unable to transform the list of tokens into an IF THEN ELSE statement, the clause fails and backtracks to the next s_statement clause, which tries to transform the list of tokens into an IF THEN statement. If that clause fails, the next one tries to transform the list of tokens into a DO WHILE statement.

If the first three s_statement clauses fail, the last clause for that predicate tests if the statement does assignment. This clause tests for assignment by testing if the first term is a symbol, the second term is "=", and the next terms make up a simple math expression.

The s_exp, s_exp1, and s_exp2 predicates work the same way, by testing if the first terms are expressions and--if so--returning the remainder of the terms and an expression structure back to s_statement.

See the Sentence Analyzer VPI\PROGRAMS\SEN_AN program on your disk for a more detailed example of parsing natural-language.

Summary

These are the important points covered in this chapter:

Lists are objects that can contain an arbitrary number of elements; you declare them by adding an asterisk at the end of a previously defined domain.

A list is a recursive compound object that consists of a head and a tail. The head is the first element and the tail is the rest of the list (without the first element). The tail of a list is always a list; the head of a list is an element. A list can contain zero or more elements; the empty list is written [].

The elements in a list can be anything, including other lists; all elements in a list must belong to the same domain. The domain declaration for the elements must be of this form:

    DOMAINS
        elementlist = elements*
        elements    = ....

where elements = one of the standard domains (integer, real, etc.) or a set of alternatives marked with different functors (int(integer); rl(real); smb(symbol); etc.). You can only mix types in a list in Visual Prolog by enclosing them in compund objects/functors.

You can use separators (commas, [, and |) to make the head and tail of a list explicit; for example, the list

    [a, b, c, d]

can be written as

    [a|[b, c, d]] or
    [a, b|[c, d]] or
    [a, b, c|[d]] or
    [a|[b|[c, d]]] or
    [a|[b|[c|[d]]]] or even
    [a|[b|[c|[d|[]]]]]

List processing consists of recursively removing the head of the list (and usually doing something with it) until the list is an empty list.

The classic Prolog list-handling predicates member and append enable you to check if an element is in a list and check if one list is in another (or append one list to another), respectively.

A predicate's flow pattern is the status of its arguments when you call it; they can be input parameters (i)--which are bound or instantiated--or output parameters (o), which are free.

Visual Prolog provides a built-in predicate, findall, which takes a goal as one of its arguments and collects all of the solutions to that goal into a single list.

Because Visual Prolog requires that all elements in a list belong to the same domain, you use functors to create a list that stores different types of elements.

The process of parsing by difference lists works by reducing the problem; the example in this chapter transforms a string of input into a Prolog structure that can be used or evaluated later.