Linguistics 482 - Computational Linguistics Prolog Notes A. C. Brett acbrett@uvic.ca
Department of Linguistics
University of Victoria
Clearihue C139
Last updated: 23 October 1999

Lists

Lists are special structures that represent sequences of Prolog terms. A closed or definite list is represented as follows:
   [e1, e2, ..., en]
where e1, e2, ..., en are called the elements of the list. The elements are separated by commas, and they may be any Prolog terms, including other lists or structures. The initial element, e1, is called the head of the list, and the remaining elements, e2, ..., en, comprise the tail of the list.

The sequence of elements comprising a list is enclosed in brackets (sometimes called "square brackets" to ensure there is no confusion with parentheses). A list can be empty, that is, it contains no elements, and the empty list is represented with just a left bracket and a right bracket as follows:

   []
A definite list might also consist of just one element:
   [e]
where e may be any Prolog term, including a list.

An open or indefinite list is represented as follows:

   [e, ... | T]
where the notation e, ... indicates that there is at least one element between the left bracket and the vertical stroke character, but there could be more than one element. If there is more then one element, they are separated by commas, but there is no comma between the last element and the vertical stroke. Elements to the left of the vertical stroke may be any Prolog terms. T, to the right of the vertical stroke, is normally a variable that stands for a list of as yet unknown additional elements. Any variable may be used in place of T.

The vertical stroke character can also be used in the representation of a closed or definite list. For example, the following definite list:

   [some, dogs, like, cats]
may also be represented by writing
   [some | [dogs, like, cats]]
which illustrates that the entity to the right of the vertical stroke is another list. In fact, the same list can be represented by any of the following alternatives:
   [some | [dogs | [like, cats]]]
   [some | [dogs | [like | [cats]]]]
   [some | [dogs | [like | [cats | []]]]]
The last of the foregoing representations is actually close in many respects to the form in which the Listener processes lists. A list is in fact a structure, and its representation as such can be revealed by using the display system predicate and typing the following goal (at the Listener prompt):
   display([some, dogs, like, cats]).
The Listener will respond by displaying the line
   .(some, .(dogs, .(like, .(cats, []))))
which shows the list represented by means of a Prolog structure with two arguments and with a dot or period, ".", as its name. In the first reference to this structure, the head atom of the list, some, appears in the first argument, and the tail of the list, [dogs, like, cats], appears in the second argument. This list is itself represented in the arguments of another reference to the dot structure. In this reference, the head element, dogs, appears in the first argument, and the tail, [like, cats], appears in the second, but represented as another reference to the dot structure. Consequently, when the complete list is represented, there is one reference to the dot structure for each element in the list with the second argument of the last reference being the null list.

The representation of a list in terms of the arguments of the dot structure demonstrates that a list is itself just a special structure. The representation of a list with brackets is simply a notational convenience that has been introduced to circumvent the need to type large numbers of periods and parentheses. The Listener translates this notation into the dot structure representation. Hence, it is not normally necessary to know about the dot structure and the details of how the Listener uses it to represent a list. It is necessary, however, to know something about how the Listener processes a list. In particular, one must understand how the Listener interprets the vertical stroke notation in the process of adding elements to, and removing elements from a list.

When a vertical stroke is used in the representation of a list, the entity to the right of the vertical stroke is itself a list. This fact can be demonstrated using the term equality predicate, the name of which is the equal sign, =. Thus, if one were to type the following goal (at the Listener prompt):

   [X | Y] = [some, dogs, like, cats]
the Listener will display the lines
   X = some
   Y = [dogs, like, cats]
indicating that the atom some has been instantiated on the variable X, and the list [dogs, like, cats] has been instantiated on the variable Y. The instantiation of these terms on the two variables occurs as the list [X | Y] is unified with the list [some, dogs, like, cats]. X in the list to the left of the equal sign unifies with the head of the list to the right and thereby gets instantiated with the atom some. Y unifies with the tail of the right-hand list and thereby gets instantiated with the list [dogs, like, cats].

Typing the goal

   [X, Y | Z] = [some, dogs, like, cats]
will elicit the following response from the Listener:
   X = some
   Y = dogs
   Z = [like, cats]
showing that the variables X and Y in the list to the left of the equal sign have unified with the first two elements of the list on the right so that the atoms some and dogs, respectively, are instantiated on them. The variable Z unifies with the tail of the right-hand list, so that [like, cats] gets instantiated on it.

The foregoing processes are employed if a Prolog program that includes the following clauses is consulted:

   pro(some).                          % Pro --> some
   det(some).                          % Det --> some
   n(dogs).                            % N --> dogs

   np([X | Y], Y) :- pro(X).           % NP --> Pro
   np([X, Y | Z], Z) :- det(X), n(Y).  % NP --> Det N
and the following goal is typed:
   np([some, dogs, like, cats], T).
The Listener will respond by displaying
   T = [dogs, like, cats] ;
   T = [like, cats] ;
   no
where the first line displayed shows that the list returned in the second argument of the np/2 goal, namely [dogs, like, cats], is just the tail of the list originally typed after its head, the atom some has been removed. This result indicates that some has been identified as a pronoun, and that it does constitute a noun phrase according to the first clause of the np/2 predicate in the program.

The semicolon to the right of the displayed list was typed so that the Listener would search for an alternative proof of the goal that has been typed. The Listener does find an alternative, and displays the second line which shows that the first two elements, some and dogs, have been removed from the original list. They have been identified as a determiner and a noun, respectively, according to the second clause of the np/2 predicate. The Listener then responds "no", after a semicolon is typed, because there are no further alternative proofs of the goal.

Linguistics 482 Prolog Introductory Notes Top of Page