wiki.visual-prolog.com - User contributions [en]

Compound and List Domains

2022-09-07T11:09:12Z

Magnus Jacobsen: /* Using the Equal Sign to Unify Compound Domains */

In this tutorial we will introduce compound domains (sometimes called algebraic data structures). Compound domains are used to handle several pieces of data as a single entity. Lists is an example of compound domains. Lists are used so much that they have even received special syntactical sugaring.

Compound and list domains are created using built-in domains and other compound and list domains. Visual Prolog help describes built-in domains: integral, real, string, symbol, char, string8, pointer, binary, boolean, object.

==Compound Domains and Functors==

Compound domains allow you to treat several pieces of information as a single item in such a way that you can easily pick them apart again. Consider, for instance, the date "October 15, 2003". It consists of three pieces of information – the month, day, and year – but it is useful to treat the whole thing as a single data with a treelike structure:

<pre> DATE
/|\
/ | \
/ | \
/ | \
October 15 2003</pre>You can do this by declaring a domain containing the compound domain '''date''':

<vip>domains
date_cmp = date(string Month, unsigned Day, unsigned Year).</vip>

and then simply writing e.g.

<vip>D = date("October", 15, 2003),</vip>

This looks like a Prolog fact, but it isn't here – it is just a value, which you can handle in much the same way as a string or number. It begins with a name, usually called a functor(in this case date), followed by three arguments.

Note carefully that a functor in Visual Prolog has nothing to do with a function in other programming languages. '''''A functor does not stand for some computation to be performed.''''' it is just a name that identifies a kind of compound value and holds its arguments together.

The arguments of a compound value can themselves be compound. For instance, you might think of someone's birthday as an information structure like this:

<pre> birthday
/ \
/ \
/ \
/ \
/ \
person date
/ \ / | \
/ \ / | \
"Per" "Schultze" "Apr" 14 1960</pre>In Prolog you would write this as:

<vip>birthday(person("Per", "Schultze"), date("Apr",14,1960)).</vip>

In this example, there are two sub-parts in the compound birthday value: the argument person("Per", "Schultze") and the argument date("Apr", 14, 1960). The functors of these values are person and date.

==Unification of Compound Domains==

A compound value can unify either with a simple variable or with a compound value that matches it(perhaps containing variables as parts of its internal structure). This means you can use a compound value to pass the whole collection of items as a single value, and then use unification to pick them apart. For example, <vp>date("April", 14, 1960)</vp> matches <vp>X</vp> and binds <vp>X</vp> to <vp>date("April",14,1960)</vp>. Also <vp>date("April", 14, 1960)</vp> matches <vp>date(Mo, Da, Yr)</vp> and binds <vp>Mo</vp> to <vp>"April"</vp>, <vp>Da</vp> to <vp>14</vp>, and <vp>Yr</vp> to <vp>1960</vp>.

===Using the Equal Sign to Unify Compound Domains===

Visual Prolog performs unification in two places. The first is when a call or goal matches the head of a clause. The second is across the '''''equal'''''(=) sign, which is actually an infix predicate(a predicate that is located ''between'' its arguments rather than ''before'' them).

Visual Prolog will make the necessary bindings to unify the values on both sides of the '''''equal''''' sign. This is useful for finding the values of arguments within a compound value. For example, the following code excerpt tests if two people have the same last name, then gives the second person the same address as the first.

<vip>class my
domains
person = person(name, address).
name = name(string First, string Last).
address = addr(street, string City, string State).
street = street(integer Number, string Street_name).

predicates
run :().
end class

implement my
clauses
run():-
console::init(),
P1 = person(name("Jim", "Smith"),
addr(street(5, "1st st"), "igo", "CA")),
P1 = person(name(_, "Smith"), Address),
P2 = person(name("Jane", "Smith"), Address),
!,
stdio::write("P1 = ", P1, "\n"),
stdio::write("P2 = ", P2, "\n")
or
stdio::write("No solution").
end implement

goal
my::run.</vip>

==Treating Several Items as One==

Compound values can be regarded and treated as single values in your Prolog clauses, which greatly simplifies programming. Consider, for example, the fact

<vip>owns("John", book("From Here to Eternity", "James Jones")).</vip>

in which you state that John owns the book "From Here to Eternity", written by "James Jones". Likewise, you could write

<vip>owns("John", horse("Blacky")).</vip>

which can be interpreted as

John owns a horse named Blacky.

The compound values in these two examples are

<vip>book("From Here to Eternity", "James Jones")).</vip>

and

<vip>horse("Blacky").</vip>

If you had instead written two facts:

<vip>owns("John", "From Here to Eternity").
owns("John", "Blacky").</vip>

you would not have been able to decide whether Blacky was the title of a book or the name of a horse. On the other hand, you can use the first component of a compound value – the functor – to distinguish between different kinds of values. This example used the functors book and horse to indicate the difference between the values.

'''Remember''': Compound values consist of a functor and the arguments belonging to that functor, as follows:

<vip>functor(argument1, argument2, ..., argumentN)</vip>

===An Example Using Compound Domains===

An important feature of compound domains allows you to easily pass a group of values as one argument. Consider a case where you are keeping a telephone database. In your database, you want to include your friends' and family members' birthdays. Here is a section of code you might have come up with:

<vip>predicates
phone_list :(string First, string Last, string Phone, string Month, intege Day, integer Year) determ.

clauses
phone_list("Ed", "Willis", "422-0208", "aug", 3, 1955).
phone_list("Chris", "Grahm", "433-9906", "may", 12, 1962).</vip>

Examine the data, noticing the six arguments in the fact phone_list; five of these arguments can be broken down into two compound domains, like this:

<pre> person birthday
/ \ / | \
/ \ / | \
First Name Last Name Month Day Year</pre>It might be more useful to represent your facts so that they reflect these compound domains. Going back a step, you can see that person is a relationship, and the first and last names are the arguments. Also, birthday is a relationship with three arguments: month, day, and year. The Prolog representation of these relationships is

<vip>owns("John", "From Here to Eternity").
owns("John", "Blacky").</vip>

You can now rewrite your small database to include these compound domains as part of your database.

<vip>domains
name = person(string First, string Last).
birthday = b_date(string Month, integer Day, integer Year).

class predicates
phone_list : (name Name, string Ph_num, birthday Birthday) determ.
clauses
phone_list(person("Ed", "Willis"), "422-0208", b_date("aug", 3, 1955)).
phone_list(person("Chris", "Grahm"), "433-9906", b_date("may", 12, 1962)).</vip>

In this program, two compound '''domains''' declarations were introduced. We go into more detail about these compound data structures later in this chapter. For now, we will concentrate on the benefits of using such compound domains.

The phone_list predicate now contains three arguments, as opposed to the previous six. Sometimes breaking up your data into compound values will clarify your program and might help process the data.

Now add some rules to program. Suppose you want to create a list of people whose birthdays are in the current month. Here is the program code to accomplish this task; this program uses the standard predicate date to get the current date from the computer's internal clock. Predicate date will return the current year, month, and day from your computer's clock.

<vip>class my
domains
name = person(string First, string Last).
birthday = b_date(string Month, integer Day, integer Year).
predicates
phone_list : (name Name [out], string Ph_num [out], birthday Birthday [out]) multi.
get_months_birthdays : ().
convert_month : (string Name, integer Num [out]) determ.
check_birthday_month : (integer Month_num, birthday Birthday) determ.
write_person : (name Name).
end class

implement my
clauses
get_months_birthdays() :-
stdio::write("****** This Month's Birthday List *****\n"),
stdio::write(" First Name\t\t Last Name\n"),
stdio::write("***********************************\n"),
Now = time::now(),
Now:getDate(_, ThisMonth, _),
phone_list(Person, _, Date),
check_birthday_month(ThisMonth, Date),
write_person(Person),
fail.
get_months_birthdays() :-
stdio::write("\n Press any key to continue:\n"),
_ = console::readChar().

clauses
write_person(person(FirstName, LastName)) :-
stdio::write(" ", FirstName, "\t\t ", LastName, "\n").

clauses
check_birthday_month(Mon, b_date(Month, _, _)) :-
convert_month(Month, Month1),
Mon = Month1.

clauses
phone_list(person("Ed", "Willis"), "11-1111", b_date("Jan", 3, 1955)).
phone_list(person("Benjamin", "Thomas"), "222-2222", b_date("Feb", 5, 1965)).
phone_list(person("Ray", "William"), "333-3333", b_date("Mar", 3, 1955)).
phone_list(person("Tomas", "Alfred"), "444-4444", b_date("Apr", 29, 1975)).
phone_list(person("Chris", "Gralm"), "555-5555", b_date("May", 12, 1975)).
phone_list(person("Dastin", "Robert"), "666-6666", b_date("Jun", 17, 1975)).
phone_list(person("Anna", "Friend"), "777-7777", b_date("Jul", 2, 1975)).
phone_list(person("Naomi", "Friend"), "888-8888", b_date("Aug", 10, 1975)).
phone_list(person("Christina", "Lynn"), "999-9999", b_date("Sep", 25, 1975)).
phone_list(person("Kathy", "Ann"), "110-1010", b_date("Oct", 20, 1975)).
phone_list(person("Elizabeth", "Ann"), "110-1111", b_date("Nov", 9, 1975)).
phone_list(person("Aaron", "Friend"), "110-1212", b_date("Dec", 31, 1975)).
phone_list(person("Jenifer", "Faitlin"), "888-8888", b_date("Aug", 14, 1975)).

clauses
convert_month("Jan", 1).
convert_month("Feb", 2).
convert_month("Mar", 3).
convert_month("Apr", 4).
convert_month("May", 5).
convert_month("Jun", 6).
convert_month("Jul", 7).
convert_month("Aug", 8).
convert_month("Sep", 9).
convert_month("Oct", 10).
convert_month("Nov", 11).
convert_month("Dec", 12).
end implement

goal
console::init(),
my::get_months_birthdays().</vip>

How do compound domains help in this program? This should be easy to see when you examine the code. Most of the processing goes on in the get_months_birthdays predicate.

*First, the program makes a window to display the results.

*After this, it writes a header in the window to help interpret the results.

*Next, in get_months_birthdays, the program uses the built-in predicate date to obtain the current month.

*After this, the program is all set to search the database and list the people who were born in the current month. The first thing to do is find the first person in the database. The call phone_list(Person, _, Date) binds the person's first and last names to the variable Person by binding the entire functor person to Person. It also binds the person's birthday to the variable Date. 
Notice that you only need to use one variable to store a person's complete name, and one variable to hold the birthday. This is the power of using compound domains.

*Your program can now pass around a person's birthday simply by passing on the variable Date. This happens in the next subgoal, where the program passes the current month(represented by an integer) and the birthday(of the person it is processing) to the predicate check_birthday_month.

*Look closely at what happens. Visual Prolog calls the predicate check_birthday_month with two variables: The first variable is bound to an integer, and the second is bound to a birthday term. In the head of the rule that defines check_birthday_month, the first argument, This_month, is matched with the variable Mon. The second argument, Date, is matched against b_date(Month, _,_). 
Since all you are concerned with is the month of a person's birthday, you have used the anonymous variable for both the day and the year of birth.

*The predicate check_birthday_month first converts the string for the month into an integer value. Once this is done, Visual Prolog can compare the value of the current month with the value of the person's birthday month. If this comparison succeeds, then the subgoal check_birthday_month succeeds, and processing can continue. If the comparison fails(the person currently being processed was not born in the current month), Visual Prolog begins to backtrack to look for another solution to the problem.

*The next subgoal to process is write_person. The person currently being processed has a birthday this month, so it is OK to print that person's name in the report. After printing the information, the clause fails, which forces backtracking.

*'''''Backtracking always goes up to the most recent non-deterministic call and tries to re-satisfy that call.''''' In this program, the last non-deterministic call processed is the call to phone_list. It is here that the program looks up another person to be processed. If there are no more people in the database to process, the current clause fails; Visual Prolog then attempts to satisfy this call by looking further down in the database. Since there is another clause that defines get_months_birthdays, Visual Prolog tries to satisfy the call to get_months_birthdays by satisfying the subgoals to this other clause.

==Declaring Compound Domains==

In this section, we show you how instances of compound domains are defined. After compiling a program that contains the following relationships:

<vip>owns("John", book("From Here to Eternity", "James Jones")).</vip>

and

<vip>owns("John", horse("Blacky")).</vip>

you could query the system with this goal:

<vip>owns("John", X))</vip>

The variable X can be bound to a different type: a book, a horse, or perhaps other types you define. Because of your definition of the owns predicate, you can no longer employ the old predicate declaration of owns:

<vip>owns :(string, string).</vip>

The second argument no longer refers to the string domain. Instead, you must formulate a new declaration to the predicate, such as

<vip>owns :(name, articles).</vip>

You can describe the articles domain in the domains section as shown here:

<vip>domains
articles = book(string Title, string Author);
horse(string Name).
/* Articles are books or horses */</vip>

The semicolon is read as ''or''. In this case, two alternatives are possible: A book can be identified by its title and author, or a horse can be identified by its name. The domains title, author, and name are all of the standard domain string.

More alternatives can easily be added to the domains declaration. For example, articles could also include a boat, a house, or a bankbook. For a boat, you can make do with a functor that has no arguments attached to it. On the other hand, you might want to give a bank balance as a figure within the bankbook. The domains declaration of articles is therefore extended to:

<vip>domains
articles = book(string Title, string Author);
horse(string Name); boat; bankbook(real Balance).</vip>

Here is a full program that shows how compound domains from the domain articles can be used in facts that define the predicate owns.

<vip>class my
domains
articles =
book(string Title, string Author) ;
horse(string Name) ; boat ; bankbook(real Balance).
predicates
owns :(string Name, articles) nondeterm(i,o) determ(i,i).
end class

implement my
clauses
owns("John", book("A friend of the family", "Irwin Shaw")).
owns("John", horse("Blacky")).
owns("John", boat).
owns("John", bankbook(1000)).
end implement

goal
console::init(),
my::owns("John", Thing),
stdio::write("Thing: ", Thing, "\n"),
fail
;
stdio::write("The end.").</vip>

Now load the program into Visual Development Environment and run it in window. Visual Prolog responds with:

<vip>Thing: book("A friend of the family","Irwin Shaw")
Thing: horse("Blacky")
Thing: boat()
Thing: bankbook(1000)
The end.</vip>

===Writing Domain Declarations: a Summary===

This is a generic representation of how to write compound domain declarations:

<vip>domain = alternative1(D, D, ...);
alternative2(D, D, ...);
...</vip>

Here, alternative1 and alternative2 are arbitrary(but different) functors. The notation(D, D, ...) represents a list of domain names that are either declared elsewhere or are one of the standard domain types(such as string, integer, real, etc).

'''Note''':

*The alternatives are separated by semicolons.

*Every alternative consists of a functor and, possibly, a list of domains for the corresponding arguments.

*If the functor has no arguments, you can write it as alternativeN or alternativeN( ) in your programs.

===Multi-Level Compound Domains===

Visual Prolog allows you to construct compound domains on several levels. For example, in

<vip>book("The Ugly Duckling", "Andersen").</vip>

instead of using the author's last name, you could use a new structure that describes the author in more detail, including both the author's first and last names. By calling the functor for the resulting new compound domain author, you can change the description of the book to

<vip>book("The Ugly Duckling", author("Hans Christian", "Andersen")).</vip>

In the old domain declaration

<vip>book(string Title, string Author).</vip>

the second argument of the book functor is Author that can only include a single name, so it is no longer sufficient. You must now specify that an author is also a compound domain made up of the author's first and last name. You do this with the domain definition:

<vip>author = author(string First_name, string Last_name).</vip>

which leads to the following declarations:

<vip>domains
articles = book(string Title, author Author); ...
/* First level */
author = author(string First_name, string Last_name).
/* Second level */</vip>

When using compound domains on different levels in this way, it is often helpful to draw a "tree":

<pre> book
/ \
/ \
title author
/ \
/ \
First_name Last_name</pre>A domain declaration describes only one level of the tree at a time, and not the whole tree. For instance, a book can't be defined with the following domain declaration:

<vip>/* Not allowed */
book = book(string Title, author(string First_name, string Last_name)).</vip>

==Compound Mixed-Domain Declarations==

In this section, we discuss three different types of domain declarations you can add to your programs. These declarations allow you to use predicates that

*take an argument, more than one type of more than one possible type

*take a variable number of arguments, each of a specified type

*take a variable number of arguments, some of which might be of more than one possible type

===Multiple-Type Arguments===

To allow a Visual Prolog predicate to accept an argument that gives information of different types, you must add a functor declaration. In the following example, the your_age clause will accept an argument of type age, which can be a string, a real, or an integer.

<vip>domains
age = i(integer); r(real); s(string).

class predicates
your_age :(age).
clauses
your_age(i(Age)) :- stdio::write(Age).
your_age(r(Age)) :- stdio::write(Age).
your_age(s(Age)) :- stdio::write(Age).</vip>

Visual Prolog does not allow the following domain declaration:

<vip>/* Not permitted. */
domains
age = integer; real; string.</vip>

===Lists===

Suppose you are keeping track of the different classes a professor might teach. You might produce the following code:

<vip>class predicates
teacher :(string First_name, string Last_name, string Class) determ.

clauses
teacher("Ed", "Willis", "english1").
teacher("Ed", "Willis", "math1").
teacher("Ed", "Willis", "history1").
teacher("Mary", "Maker", "history2").
teacher("Mary", "Maker", "math2").
teacher("Chris", "Grahm", "geometry").</vip>

Here, you need to repeat the teacher's name for each class he or she teaches. For each class, you need to add another fact to the database. Although this is perfectly OK in this situation, you might find a school where there are hundreds of classes; this type of data structure would get a little tedious. Here, it would be helpful if you could create an argument to a predicate that could take on one ''or more'' values.

A list in Prolog does just that. In the following code, the argument class is declared to be of a list type. We show here how a list is represented in Prolog.

<vip>domains
classes = string*. /* declare a list domain */

class predicates
teacher :(string First_name, string Last_name, classes Classes) determ.
clauses
teacher("Ed", "Willis", ["english1", "math1", "history1"]).
teacher("Mary", "Maker", ["history2", "math2"]).
teacher("Chris", "Grahm", ["geometry"]).</vip>

In this example, the code is more concise and easier to read than in the preceding one. Notice the domains declaration. The asterisk(*) means that classes is a list of strings. You can just as easily declare a list of integers:

<vip>domains
integer_list = integer*.</vip>

Once you declare a domain, it is easy to use it; just place it as an argument to a predicate declared in the predicates section. Here is an example of using an integer list:

<vip>domains
integer_list = integer*.

class predicates
test_scores :
(string First_name,
string Last_name,
integer_list Test_Scores)
determ.
clauses
test_scores("Lisa", "Lavender", [86, 91, 75]).
test_scores("Libby", "Dazzner", [79, 75]).
test_scores("Jeff", "Zheutlin", []).</vip>

In the case of ''Jeff Zheutlin'', notice that a list doesn't need to contain any elements at all.

One more example shows how one can use lists to describe the family-tree.

<vip>domains
tree_list = tree*.
tree = tree(string Text, tree_list TreeList).

class predicates
family :(tree) determ.
clauses
family(tree("Grandmother",
[tree("John",
[tree("Eric", []),
tree("Mark", []),
tree("Leonard", []) ] ),
tree("Ellen", [])
]
)).</vip>

==Summary==

These are the important points covered in this tutorial:

*A Visual Prolog program can contain many types of values: simple and compound, standard and user-defined.

*Simple values are numbers, strings, etc.

*''Compound domains'' allow you to treat several pieces of information as a single item. A compound domain consists of a name(known as a functor) and one or more arguments. You can define a domain with several alternative functors.

*A functor in Visual Prolog is not the same thing as a function in other programming languages. '''''A functor does not stand for some computation to be performed.''''' It is just a name that identifies a kind of a compound domain and holds its arguments together.

*Compound values can be regarded and treated as single values; you use the functor to distinguish between different kinds of compound values. Visual Prolog allows you to construct compound values on several levels; the arguments of a compound value can also be compound values. With compound mixed domain declarations, you can use predicates that:

*take an argument of more than one possible type(functor declaration).

*take a variable number of arguments, each of a specified type(list declaration).

*take a variable number of arguments, some of which might be of more than one possible type.

[[ru:Cоставные Домены и Списки]]
[[Category:Data types and handling]]

Lists and Recursion

2022-09-05T13:42:34Z

Magnus Jacobsen: /* Tail Recursion */

List processing – handling sequences of elements – is a powerful technique in Prolog. In this tutorial, we explain what lists are and how to declare them, and then give several examples that show how you might use list processing in your own applications. We also define two well known Prolog predicates – member and append – while looking at list processing from both a recursive and a procedural standpoint.

After that, we introduce findall, a Visual Prolog standard predicate that enables you to find and collect all solutions to a single goal. We round out this tutorial with a discussion of compound lists – combinations of different types of elements – and an example of parsing by difference lists.

==What Is a List?==

In Prolog, ''a list'' is an object that contains an arbitrary number of other objects within it. Lists correspond roughly to arrays in other languages, but, unlike an array, a list does not require you to declare how big it will be before you use it.

A list that contains the numbers <vp>1</vp>, <vp>2</vp>, and <vp>3</vp> is written as

<vip>[1, 2, 3]</vip>

The order of the elements in this list matters:

*Number "1" is the first element,

*"2" - the second,

*"3" - the third.

The list <vp>[1, 2, 3]</vp> is different from the list <vp>[1, 3, 2]</vp>.

Each item contained in the list is known as an element. To form a list data structure, you separate the elements of a list with commas and then enclose them in square brackets. Here are some examples:

<vip>["dog", "cat", "canary"]
["valerie ann", "jennifer caitlin", "benjamin thomas"]</vip>

The same element can be present in the list several times, for example:

<vip>[1, 2, 1, 3, 1]</vip>

== Lists Domains ==

It <vp>T</vp> is a type/domain then <vp>T*</vp> is the domain of lists containing <vp>T</vp> elements. I.e. an asterisk after a domain means "List of that domain".

The elements in a list can be anything, including other lists. However, all elements in a list must belong to the '''''same''''' domain.

== Heads and Tails ==

A list is really a recursive compound object. It consists of two parts: the head, of a list, which is the first element, and the tail, which is a list comprising all the subsequent elements.

The tail of a list is always a list; the head of a list is an element.

For example,

<vip>the head of [a, b, c] is a
the tail of [a, b, c] is [b, c]</vip>

What happens when you get down to a one-element list? The answer is that:

<vip>the head of [c] is c
the tail of [c] is []</vip>

If you take the first element from the tail of a list enough times, you will eventually get down to an empty list (<vp>[]</vp>).

The empty list cannot be broken into head and tail.

This means that, conceptually, lists have a tree structure just like other compound objects. The tree structure of [a, b, c, d] is:

<pre> list
/ \
a list
/ \
b list
/ \
c list
/ \
d []</pre>Further, a one-element list such as [a] is not the same as the element that it contains, because [a] is really the compound data structure shown here:

<pre> list
/ \
a []</pre>

==List Processing==

Prolog provides a way to make a head and a tail of a list explicit. Instead of separating elements with commas, you can separate the head and tail with a vertical bar (|). For instance,
<vip>[a, b, c]</vip>
is equivalent to
<vip>[a | [b, c]]</vip>
which continuing the process is equivalent to
<vip>[a | [b | [c]]]</vip>
which is equivalent to
<vip>[a | [b | [c | []]]]</vip>

You can even use both kinds of separators in the same list, provided the vertical bar is the last separator. So, if you really want to, you can write [a, b, c, d] as [a, b|[c, d]].

Table 1 gives more examples.
{|cellpadding="50" cellspacing="0" border="1"
|+'''Table 1: Heads and Tails of Lists'''
! List
! Head
! Tail
|-
| ['a', 'b', 'c']
| 'a'
| ['b', 'c']
|-
| ['a']
| 'a'
| []
|-
| []
| does not exist
| does not exist
|-
| [[1, 2, 3], [2, 3, 4], []]
| [1, 2, 3]
| [[2, 3, 4], []]
|}

Table 2 gives several examples of list unification.

{|cellpadding="5" cellspacing="0" border="1"
|+'''Table 2: Unification of Lists'''
!List 1
!List 2
!Variable Binding
|-
|[X, Y, Z]
|[egbert, eats, icecream]
|X=egbert, Y=eats, Z=icecream
|-
|[7]
|[X <nowiki>|</nowiki> Y]
|X=7, Y=[]
|-
|[1, 2, 3, 4]
|[X, Y <nowiki>|</nowiki> Z]
|X=1, Y=2, Z=[3,4]
|-
|[1, 2]
|[3 <nowiki>|</nowiki> X]
|fail
|}

== Using Lists ==

Because a list is really a recursive compound data structure, you need recursive algorithms to process it. The most basic way to process a list is to work through it, doing something to each element until you reach the end.

An algorithm of this kind usually needs two clauses. One of them says what to do with an ordinary list (one that can be divided into a head and a tail). The other says what to do with an empty list.

=== Writing Lists ===

For example, if you just want to print out the elements of the list, here is what you do:

<vip>implement main

clauses
run() :-
write_a_list([1, 2, 3]).

class predicates
write_a_list : (integer* List).
clauses
write_a_list([]).
/* If the list is empty, do nothing more. */
write_a_list([H | T]) :-
/* Match the head to H and the tail to T, then... */
stdio::write(H),
stdio::nl,
write_a_list(T).

end implement main

goal
console::runUtf8(main::run).</vip>

Here are the two write_a_list clauses described in natural language:

*To write an empty list, do nothing.
*Otherwise, to write a list, write its head (which is a single element), then write its tail (a list).

The <vp>write_a_list</vp> predicate is called from <vp>run</vp> clause:

<vip>write_a_list([1, 2, 3])</vip>

This matches the second clause, with H=1 and T=[2, 3]; this writes 1 and then calls write_a_list recursively with the tail of the list:

<vip>write_a_list([2, 3]).
/* This is write_a_list(T). */</vip>

This recursive call matches the second clause, this time with H=2 and T=[3], so it writes 2 and again calls write_a_list recursively:

<vip>write_a_list([3]).</vip>

Now, which clause will this goal match? Recall that, even though the list [3] has only one element; it does have a head and tail; the head is 3 and the tail is []. So, again the goal matches the second clause, with H=3 and T=[]. Hence, 3 is written and write_a_list is called recursively like this:

<vip>write_a_list([]).</vip>

Now you see why this program needs the first clause. The second clause will not match this goal because [] cannot be divided into head and tail. So, if the first clause were not there, the goal would fail. As it is, the first clause matches and the goal succeeds without doing anything further.

===Counting List Elements===

Now consider how you might find out how many elements are in a list. What is the length of a list, anyway? Here is a simple logical definition:

*The length of an empty list, <vp>[]</vp>, is <vp>0</vp>. 
*The length of any other list is the length of its tail plus <vp>1</vp>.

Can you implement this? In Prolog it is very easy. It takes just two clauses:

<vip>class main

predicates
length_of : (A* List) -> integer Length.

end class

implement main

clauses
length_of([]) = 0.
length_of([_ | T]) = Length :-
TailLength = length_of(T),
Length = TailLength + 1.

end implement main

goal
console::init(),
Length = main::length_of([1, 2, 3]),
stdio::write(Length).</vip>

Take a look at the second clause first. Crucially, <vp>[_ | T]</vp> will match any nonempty list, binding <vp>T</vp> to the tail of the list. The value of the head is unimportant; as long as it exists, it can be counted it as one element.

So the goal:

<vip>Length = main::length_of([1, 2, 3])</vip>

will match the second clause, with <vp>T</vp> = <vp>[2, 3]</vp>. The next step is to compute the length of <vp>T</vp>. When this is done (never mind how), <vp>TailLength</vp> will get the value <vp>2</vp>, and the computer can then add <vp>1</vp> to it and bind <vp>Length</vp> to <vp>3</vp>.

So how is the middle step executed? That step was to find the length of <vp>[2, 3]</vp> by satisfying the goal

<vip>TailLength = main::length_of([2, 3])</vip>

In other words, <vp>length_of</vp> calls itself recursively. This goal matches the second clause, binding

*<vp>[3]</vp> in the goal to <vp>T</vp> in the clause and
*<vp>TailLength</vp> in the goal to <vp>Length</vp> in the clause.

Recall that <vp>TailLength</vp> in the goal will not interfere with <vp>TailLength</vp> in the clause, because '''''each recursive invocation of a clause has its own set of variables'''''.

So now the problem is to find the length of <vp>[3]</vp>, which will be <vp>1</vp>, and then add <vp>1</vp> to that to get the length of <vp>[2, 3]</vp>, which will be <vp>2</vp>. So far, so good.

Likewise, <vp>length_of</vp> will call itself recursively again to get the length of <vp>[3]</vp>. The tail of <vp>[3]</vp> is <vp>[]</vp>, so <vp>T</vp> is bound to <vp>[]</vp>, and the problem is to get the length of <vp>[]</vp>, then add 1 to it, giving the length of <vp>[3]</vp>.

This time it's easy. The goal:

<vip>TailLength = main::length_of([])</vip>

matches the ''first'' clause, binding <vp>TailLength</vp> to <vp>0</vp>. So now the computer can add <vp>1</vp> to that, giving the length of <vp>[3]</vp>, and return to the calling clause. This, in turn, will add <vp>1</vp> again, giving the length of <vp>[2, 3]</vp>, and return to the clause that called it; this original clause will add <vp>1</vp> again, giving the length of <vp>[1, 2, 3]</vp>.

Confused yet? We hope not. In the following brief illustration we'll summarize the calls. We've used suffixes to indicate that similarly named variables in different clauses – or different invocations of the same clause – are distinct. Please notice that you do not need to implement such predicate in your own code, you can use '''list::length''' predicate from PFC.

<vip>Length_1 = main::length_of([1, 2, 3]).
TailLength_1 = main::length_of([2, 3]).
TailLength_2 = main::length_of([3]).
TailLength_3 = main::length_of([]).
TailLength_3 = 0.
Length_3 = TailLength_3 + 1 = 1.
Length_2 = Length_3 + 1 = 2.
Length_1 = Length_2 + 1 = 3.</vip>

Notice that the code above can be written more compact without the use of intermediate variables like this:

<vip>
clauses
length_of([]) = 0.
length_of([_ | T]) = length_of(T) + 1.
</vip>

These clauses more or less directly states the original specification:

*The length of an empty list, <vp>[]</vp>, is <vp>0</vp>. 
*The length of any other list is the length of its tail plus <vp>1</vp>.

===Tail Recursion===

You probably noticed that <vp>length_of</vp> is not, and can't be, tail-recursive, because the recursive call is not the last step in its clause. Can you create a tail-recursive list-length predicate? Yes, but it will take some effort.

The problem with <vp>length_of</vp> is that you can't compute the length of a list until you've already computed the length of the tail. It turns out there's a way around this. You'll need a list-length predicate with two arguments.

* The first is the list, which the computer will whittle away on each call until it eventually becomes empty, just as before.
* The second is an counter that starts out as <vp>0</vp> and increments on each call.

When the list is finally empty, you'll return the counter as the list length.

<vip>class main

predicates
length_of : (A* List, integer Counter) -> integer Result.

end class

implement main

clauses
length_of([], Counter) = Counter.
length_of([_ | T], Counter) = Result :-
NewCounter = Counter + 1,
Result = length_of(T, NewCounter).

end implement main

goal
console::init(),
Length = main::length_of([1, 2, 3], 0), /* start with Counter = 0 */
stdio::write("Length = ", Length).</vip>

This version of the <vp>length_of</vp> predicate is more complicated, and in many ways less logical, than the previous one. We've presented it merely to show you that, ''by devious means, you can often find a tail-recursive algorithm for a problem that seems to demand a different type of recursion''.

=== Another Example – Modifying the List ===

Sometimes you want to take a list and create another list from it. You do this by working through the list element by element, replacing each element with a computed value. For example, here is a program that takes a list of numbers and adds 1 to each of them:

<vip>class main

predicates
add1 : (integer* NumberList) -> integer* IncrList.

end class

implement main

clauses
add1([]) = []. % boundary condition
add1([Head | Tail]) = Result :-
% separate the head from the rest of the list
Head1 = Head + 1, % add 1 to the first element
Tail1 = add1(Tail), % call element with the rest of the list
Result = [Head1 | Tail1]. % Put the new head infront of the new tail

end implement main

goal
console::init(),
NewList = main::add1([1, 2, 3, 4]),
stdio::write(NewList).</vip>

To paraphrase this in natural language:

To add 1 to all the elements of the empty list, 
just produce another empty list. 
 
To add 1 to all the elements of any other list, 
add 1 to the head and make it the head of the result, and then 
add 1 to each element of the tail and make that the tail of the result.

Runnig the the predicate with <vp>[1, 2, 3, 4]</vp>:

<vip>NewList = add1([1,2,3,4]).</vip>

Will result in

<code>NewList = [2, 3, 4, 5]</code>

=== Tail Recursion Again ===

Is <vp>add1</vp> tail-recursive? If you're accustomed to using Lisp or Pascal, you might think it isn't, because you think of it as performing the following operations:

*Split the list into <vp>Head</vp> and <vp>Tail</vp>.
*Add <vp>1</vp> to <vp>Head</vp>, giving <vp>Head1</vp>.
*Recursively add 1 to all the elements of <vp>Tail</vp>, giving <vp>Tail1</vp>.
*Combine <vp>Head1</vp> and <vp>Tail1</vp>, giving the resulting list.

This isn't tail-recursive, because the recursive call is not the last step.

But – and this is important – ''that is not how Prolog does it''. In Visual Prolog, <vp>add1</vp> is tail-recursive, because its steps are really the following:

*Bind the head and tail of the original list to <vp>Head</vp> and <vp>Tail</vp>.
*Bind the head and tail of <vp>Result</vp> to <vp>Head1</vp> and <vp>Tail1</vp>. (<vp>Head1</vp> and <vp>Tail1</vp> do not have values yet.)
*Add <vp>1</vp> to <vp>Head</vp>, giving <vp>Head1</vp>.
*Recursively add <vp>1</vp> to all the elements of <vp>Tail</vp>, giving <vp>Tail1</vp>.

When this is done, <vp>Head1</vp> and <vp>Tail1</vp> are ''already'' the head and tail of <vp>Result</vp>; there is no separate operation of combining them. So the recursive call really is the last step.

=== More on Modifying Lists ===

Of course, you don't actually need to put in a replacement for every element. Here's a program that scans a list of numbers and copies it, leaving out the negative numbers:

<vip>class main

predicates
discard_negatives : (integer*, integer* [out]).

end class

implement main

clauses
discard_negatives([], []).
discard_negatives([H | T], ProcessedTail) :-
H < 0,
!, /* If H is negative, just skip it */
discard_negatives(T, ProcessedTail).
discard_negatives([H | T], [H | ProcessedTail]) :-
discard_negatives(T, ProcessedTail).

end implement main

goal
console::init(),
main::discard_negatives([2, -45, 3, 468], X),
stdio::write(X).</vip>

For example, the goal

<vip>main::discard_negatives([2, -45, 3, 468], X)</vip>

gives

<vip>X=[2, 3, 468].</vip>

And here's a predicate that copies the elements of a list, making each element occur twice:

<vip>clauses
doubletalk([], []).
doubletalk([H | T], [H, H | DoubledTail]) :-
doubletalk(T, DoubledTail).</vip>

===List Membership===

Suppose you have a list with the names ''John'', ''Leonard'', ''Eric'', and ''Frank'' and would like to use Visual Prolog to investigate if a given name is in this list. In other words, you must express the relation "membership" between two arguments: a name and a list of names. This corresponds to the predicate

<vip>isMember : (name, name*).
/* "name" is a member of "name*" */</vip>

In the program below, the first clause investigates the head of the list. If the head of the list is equal to the name you're searching for, then you can conclude that Name is a member of the list. Since the tail of the list is of no interest, it is indicated by the anonymous variable. Thanks to this first clause, the goal

<vip>main::isMember("john", ["john", "leonard", "eric", "frank"])</vip>

is satisfied.

<vip>class main

predicates
isMember : (A, A*) determ.

end class

implement main

clauses
isMember(Name, [Name | _]) :-
!.
isMember(Name, [_ | Tail]) :-
isMember(Name, Tail).

end implement main

goal
console::init(),
main::isMember("john", ["john", "leonard", "eric", "frank"]),
!,
stdio::write("Success")
or
stdio::write("No solution").</vip>

If the head of the list is not equal to Name, you need to investigate whether Name can be found in the tail of the list.

In English:

Name is a member of the list if Name is the first element of the list, or 
Name is a member of the list if Name is a member of the tail.

The second clause of isMember relates to this relationship. In Visual Prolog:

<vip> isMember(Name, [_ | Tail]) :-
isMember(Name, Tail).</vip>

===Appending One List to Another: Declarative and Procedural Programming===

As given, the member predicate of the program works in two ways. Consider its clauses once again:

<vip>clauses
isMember(Name, [Name | _]) :-
!.
isMember(Name, [_ | Tail]) :-
isMember(Name, Tail).</vip>

You can look at these clauses from two different points of view: declarative and procedural.

*From a declarative viewpoint, the clauses say:Name is a member of a list if the head is equal to Name; 
if not, Name is a member of the list if it is a member of the tail.

*From a procedural viewpoint, the two clauses could be interpreted as saying:To find a member of a list, find its head; 
otherwise, find a member of its tail.

These two points of view correspond to the goals

<vip>member(2, [1, 2, 3, 4]).</vip>

and

<vip>member(X, [1, 2, 3, 4]).</vip>

In effect, the first goal asks Visual Prolog to check whether something is true; the second asks Visual Prolog to find all members of the list [1,2,3,4]. Don't be confused by this. The member predicate is the same in both cases, but its behavior may be viewed from different angles.

=== Recursion from a Procedural Viewpoint ===

The beauty of Prolog is that, often, when you construct the clauses for a predicate from one point of view, they'll work from the other. To see this duality, in this next example you'll construct a predicate to append one list to another. You'll define the predicate append with three arguments:

<vip>append(List1, List2, List3).</vip>

This combines List1 and List2 to form List3. Once again you are using recursion (this time from a procedural point of view).

If List1 is empty, the result of appending '' Lis''t''1'' and List2 will be the same as List2. In Prolog:

<vip>append([], List2, List2).</vip>

If List1 is not empty, you can combine List1 and List2 to form ''List3'' by making the head of List1 the head of List3. (In the following code, the variable H is used as the head of both List1 and List3.) The tail of List3 is L3, which is composed of the rest of List1 (namely, L1) and all of List2. In Prolog:

<vip>append([H | L1], List2, [H | L3]) :-
append(L1, List2, L3).</vip>

The append predicate operates as follows: While List1 is not empty, the recursive rule transfers one element at a time to List3. When List1 is empty, the first clause ensures that List2 hooks onto the back of List3.

=== One Predicate Can Have Different Uses ===

Looking at append from a declarative point of view, you have defined a relation between three lists. This relation also holds if List1 and List3 are known but List2 isn't. However, it also holds true if only List3 is known. For example, to find which two lists could be appended to form a known list, you could use a goal of the form

<vip>append(L1, L2, [1, 2, 4]).</vip>

With this goal, Visual Prolog will find these solutions:

<vip>1L1=[], L2=[1,2,4]
L1=[1], L2=[2,4]L1=[1,2], L2=[4]L1=[1,2,4], L2=[]4 Solutions</vip>

You can also use append to find which list you could append to [3,4] to form the list [1,2,3,4]. Try giving the goal

<vip>append(L1, [3,4], [1,2,3,4]).</vip>

Visual Prolog finds the solution

<vip>L1=[1,2].</vip>

This append predicate has defined a relation between an '' input set'' and an ''output set'' in such a way that the relation applies both ways. Given that relation, you can ask

Which output corresponds to this given input?

or

Which input corresponds to this given output?

The status of the arguments to a given predicate when you call that predicate is referred to as a ''flow pattern''. An argument that is bound or instantiated at the time of the call is an input argument, signified by (i); a free argument is an output argument, signified by (o).

The append predicate has the ability to handle any flow pattern you provide. However, not all predicates have the capability of being called with different flow patterns. When a Prolog clause is able to handle multiple flow patterns, it is known as an invertible clause. Many of list predicate can be found in the '''list''' class.

==Finding All the Solutions at Once==

Backtracking and recursion are two ways to perform repetitive processes. Recursion won out because, unlike backtracking, it can pass information (through arguments) from one recursive call to the next. Because of this, a recursive procedure can keep track of partial results or counters as it goes along.

But there's one thing backtracking can do that recursion can't do – namely, find all the alternative solutions to a goal. So you may find yourself in a quandary: You need all the solutions to a goal, but you need them all at once, as part of a single compound data structure. What do you do?

Fortunately, Visual Prolog provides a way out of this impasse. The built-in construction list comprehension takes a goal as one of its arguments and collects all of the solutions to that goal into an output single list. list comprehension takes two arguments:

*The first argument, VarName, specifies which argument in the specified predicate is to be collected into a list.

*The second, mypredicate, indicates the predicate from which the values will be collected.

*The output ListParam, is a variable that holds the list of values collected through backtracking.

This program uses list comprehension to print the average age of a group of people.

<vip>class main

domains
name = string.
address = string.
age = integer.

predicates
person : (name Name [out], address Address [out], age Age [out]) multi.
sumlist : (age* AgeList, age Age [out], integer Count [out]).

end class

implement main

clauses
sumlist([], 0, 0).
sumlist([H | T], Sum, N) :-
sumlist(T, S1, N1),
Sum = H + S1,
N = 1 + N1.

clauses
person("Sherlock Holmes", "22B Baker Street", 42).
person("Pete Spiers", "Apt. 22, 21st Street", 36).
person("Mary Darrow", "Suite 2, Omega Home", 51).

end implement main

goal
console::init(),
L = [Age || main::person(_, _, Age)],
main::sumlist(L, Sum, N),
Average = Sum / N,
stdio::writef("Average = %.", Average).</vip>

The list comprehension clause in this program creates a list L, which is a collection of all the ages obtained from the predicate person. If you wanted to collect a list of all the people who are 42 years old, you could give the following subgoal:

<vip>List = [Who || main::person(Who, _, 42)]</vip>

The following code will create the list of positive items:

<vip>List = [X || X in [2,-8,-3,6], X > 0]</vip>

==Compound Lists==

A list of integers can be simply declared as

<vip>integer*</vip>

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:

<vip>[2, 3, 5.12, ["food", "goo"], "new"] % Not correct Visual Prolog</vip>

''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:

<vip>domains
list = elem*.
elem = l(list List); i(integer Integer); c(char Char); s(string String).
% the functors are l, i, c, and s
</vip>

The list

<vip>[2, 9, ["food", "goo"], "new"] % Not correct Visual Prolog</vip>

would be written in Visual Prolog as:

<vip>[i(2), i(9), l([s("food"), s("goo")]), s("new")] % Correct Visual Prolog</vip>

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

<vip>class main

domains
list = elem*.
elem = l(list List); i(integer Integer); c(char Char); s(string String).

predicates
test : ().

end class

implement main

class predicates
append : (A*, A*, A* [out]).
clauses
append([], L, L).
append([X | L1], L2, [X | L3]) :-
append(L1, L2, L3).

clauses
test() :-
append([s("likes"), l([s("bill"), s("mary")])], [s("bill"), s("sue")], Ans),
stdio::write("FIRST LIST: ", Ans, "\n\n"),
append([l([s("This"), s("is"), s("a"), s("list")]), s("bee")], [c('c')], Ans2),
stdio::write("SECOND LIST: ", Ans2, "\n\n").

end implement main</vip>

== Parsing by Difference Lists ==

The ch07e10.pro program demonstrates [[wikipedia:parsing|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 reading the tutorial without any loss of continuity.

<vip>/*******************************************
* Lexer
*******************************************/

class lexer

predicates
tokl : (string Input) -> string* TokenTL.

end class lexer

implement lexer

clauses
tokl(Input) = [Tok | tokl(Rest)] :-
string::fronttoken(Input, Tok, Rest),
!.
tokl(_) = [].

end implement lexer

/*******************************************
* Parser
*******************************************/

class parser

domains
program = statement*.

domains
statement =
if_Then_Else(expression Condition, statement ThenPart, statement ElsePart);
if_Then(expression Condition, statement ThenPart);
while(expression Condition, statement Body);
assign(id Variable, expression Expression).

domains
expression =
plus(expression, expression);
minus(expression, expression);
var(id);
int(integer).

domains
id = string.

predicates
program : (string* TL) -> program ProgramTree determ.

end class

implement parser

clauses
program(TL) = Prog :-
Prog = statement_list(TL, TL0),
[] = TL0.

class predicates
statement_list : (string* TL1, string* TL0 [out]) -> program Program determ.
clauses
statement_list([], []) = [] :-
!.
statement_list(TL1, TL0) = [Statement | Program] :-
Statement = statement(TL1, TL2),
TL2 = [";" | TL3],
Program = statement_list(TL3, TL0).

class predicates
statement : (string* TL1, string* TL0 [out]) -> statement Statement determ.
clauses
statement(["if" | TL1], TL0) = if_then_else(Condition, ThenPart, ElsePart) :-
Condition = expression(TL1, TL2),
TL2 = ["then" | TL3],
ThenPart = statement(TL3, TL4),
TL4 = ["else" | TL5],
!,
ElsePart = statement(TL5, TL6),
TL6 = ["fi" | TL0].

statement(["if" | TL1], TL0) = if_then(Condition, Statement) :-
!,
Condition = expression(TL1, TL2),
TL2 = ["then" | TL3],
Statement = statement(TL3, TL4),
TL4 = ["fi" | TL0].

statement(["do" | TL1], TL0) = while(Condition, Statement) :-
!,
Statement = statement(TL1, TL2),
TL2 = ["while" | TL3],
Condition = expression(TL3, TL0).

statement([ID | TL1], TL0) = assign(Id, Exp) :-
string::isname(ID),
TL1 = ["=" | TL2],
Exp = expression(TL2, TL0).

class predicates
expression : (string* TL1, string* TL0 [out]) -> expression Expression determ.
clauses
expression(TL1, TL0) = Exp :-
PreTerm = term(TL1, TL2),
Exp = termTail(TL2, TL0, PreTerm).

class predicates
termTail : (string* TL1, string* TL0 [out], expression PreExpr) -> expression Expr determ.
clauses
termTail(["+" | TL1], TL0, Exp1) = Exp :-
!,
Exp2 = term(TL1, TL2),
Exp = termTail(TL2, TL0, plus(Exp1, Exp2)).

termTail(["-" | TL1], TL0, Exp1) = Exp :-
!,
Exp2 = term(TL1, TL2),
Exp = termTail(TL2, TL0, minus(Exp1, Exp2)).

termTail(TL, TL, Exp) = Exp.

class predicates
term : (string* TL1, string* TL0 [out]) -> expression Expression determ.
clauses
term([Int | Rest], Rest) = int(I) :-
try
I = toTerm(Int)
catch _ do
fail
end try,
!.

term([Id | Rest], Rest) = var(Id) :-
string::isName(Id).

end implement parser

goal
console::init(),
TokenTL = lexer::tokl("b=2; if b then a=1 else a=2 fi; do a=a-1 while a;"),
if ProgramTree = parser::program(TokenTL) then
foreach Stmt in ProgramTree do
stdio::write(Stmt, "\n")
end foreach
else
stdio::write("Parse error\n")
end if.</vip>

The program will write:

<source lang="text">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))))</source>

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. 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 '''program''' predicate takes a list of tokens call the '''statement_list''' predicate on that list. And then is test that all tokens was used in the parse process.
*The predicate '''statement_list''' takes a list of tokens and tests if the tokens can be divided up into individual statements, each ending with a semicolon.
*The predicate '''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 '''statement_list'''.
*The four clauses of the '''statement''' correspond to the four types of statements the parser understands.
**If the first '''statement''' clause is unable to transform the list of tokens into an ''IF THEN ELSE'' statement, the clause fails and backtracks to the next '''statement''' clause.
**The second clause tries to transform the list of tokens into an ''IF THEN'' statement.
**If that clause fails, the next clause tries to transform the list of tokens into a ''DO WHILE'' statement.
**And if all the first three '''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 '''expression''', '''term''', and '''termTail''' predicates work in simailar ways, by testing if the first terms are expressions and – if so – returning the remainder of the terms and an expression structure back to '''statement'''.

==Summary==

These are the important points covered in this tutorial:

*''Lists'' 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:

<vip>domains
element_list = elements*.
elements = ....</vip>

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 compound objects/functors.

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

<vip>[a, b, c, d]</vip>

can be written as:

<vip>[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
[a | [b | [c | [d | []]]]]</vip>

*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 list predicates can be found in the '''list''' class.

*Visual Prolog provides a built-in construction, list comprehension, which takes a goal as one of its arguments and collects all of the solutions to that goal into a single list. It has the syntax

<vip>Result = [Argument || myPredicate(Argument)]</vip>

*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 tutorial transforms a string of input into a Prolog structure that can be used or evaluated later.

[[ru:Списки и рекурсия]]
[[Category:Data types and handling]]