Difference between revisions of "Compound and List Domains"

From wiki.visual-prolog.com

Line 506: Line 506:
[[ru:Cоставные Домены и Списки]]

Revision as of 09:29, 16 October 2007

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:

        / | \
       /  |  \
      /   |   \
  October 15  2003

You can do this by declaring a domain containing the compound domain date:

    date_cmp = date(string Month, unsigned Day, unsigned Year).

and then simply writing e.g.

D = date("October", 15, 2003),

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:

             /    \
            /      \
           /        \
          /          \
         /            \
   person             date
    /  \              / | \
   /    \            /  |  \
"Per" "Schultze"  "Apr" 14 1960

In Prolog you would write this as:

birthday(person("Per", "Schultze"), date("Apr",14,1960)).

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,

date("April", 14, 1960)

matches X and binds X to date("April",14,1960). Also

date("April", 14, 1960)

matches date(Mo,Da,Yr) and binds Mo to "April", Da to 14, and Yr to 1960.

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.

class my
        person = person(name, address).
        name = name(string First, string Last).
        address = addr(street, string City, string State).
        street = street(integer Number, string Street_name).
        run :().
end class
implement my
            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")
            stdio::write("No solution").
end implement

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

owns("John", book("From Here to Eternity", "James Jones")).

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

owns("John", horse("Blacky")).

which can be interpreted as

John owns a horse named Blacky.

The compound values in these two examples are

book("From Here to Eternity", "James Jones")).



If you had instead written two facts:

owns("John", "From Here to Eternity").
owns("John", "Blacky").

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:

functor(argument1, argument2, ..., argumentN)

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:

    phone_list :(string First, string Last, string Phone, string Month, intege Day, integer Year) determ.
    phone_list("Ed", "Willis", "422-0208", "aug", 3, 1955).
    phone_list("Chris", "Grahm", "433-9906", "may", 12, 1962).

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:

       person                birthday
        /   \                /  |  \
       /     \              /   |   \
First Name  Last Name    Month Day Year

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

owns("John", "From Here to Eternity").
owns("John", "Blacky").

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

    name = person(string First, string Last).
    birthday = b_date(string Month, integer Day, integer Year).
class predicates
    phone_list :(name, string Ph_num, birthday) determ.
    phone_list(person("Ed", "Willis"), "422-0208",
          b_date("aug", 3, 1955)).
    phone_list(person("Chris", "Grahm"), "433-9906",
          b_date("may", 12, 1962)).

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.

class my
        name = person(string First, string Last).
        birthday = b_date(string Month, integer Day, integer Year).
        phone_list :(name, string Ph_num, birthday) multi(o,o,o).
        get_months_birthdays :().
        convert_month :(string Name, integer Num) determ(i,o).
        check_birthday_month :(integer Month_num, birthday) determ.
        write_person :(name).
end class
implement my
        get_months_birthdays() :-
            stdio::write("****** This Month's Birthday List *****\n"),
            stdio::write(" First Name\t\t Last Name\n"),
            CurTime = time::new(),
            CurTime:getDate(_, ThisMonth, _),
            phone_list(Person, _, Date),
            check_birthday_month(ThisMonth, Date),
        get_months_birthdays() :-
            stdio::write("\n Press any key to continue:\n"),
            _ = console::readChar().
        write_person(person(FirstName, LastName)) :-
            stdio::write("  ", FirstName, "\t\t ",  LastName, "\n").
        check_birthday_month(Mon, b_date(Month, _, _)) :-
            convert_month(Month, Month1),
            Mon = Month1.
        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)).
        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

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:

owns("John", book("From Here to Eternity", "James Jones")).


owns("John", horse("Blacky")).

you could query the system with this goal:

owns("John", X))

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:

owns :(string, string).

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

owns :(name, articles).

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

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

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:

    articles = book(string Title, string Author);
            horse(string Name); boat; bankbook(real Balance).

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

class my
        articles =
            book(string Title, string Author) ;
            horse(string Name) ; boat ; bankbook(real Balance).
        owns :(string Name, articles) nondeterm(i,o) determ(i,i).
end class
implement my
        owns("John", book("A friend of the family", "Irwin Shaw")).
        owns("John", horse("Blacky")).
        owns("John", boat).
        owns("John", bankbook(1000)).
end implement
    my::owns("John", Thing),
    stdio::write("Thing: ", Thing, "\n"),
    stdio::write("The end.").

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

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

Writing Domain Declarations: a Summary

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

domain = alternative1(D, D, ...);
               alternative2(D, D, ...);

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).


  • 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

book("The Ugly Duckling", "Andersen").

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

book("The Ugly Duckling", author("Hans Christian", "Andersen")).

In the old domain declaration

book(string Title, string Author).

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:

author = author(string First_name, string Last_name).

which leads to the following declarations:

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

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

       /  \
      /    \
  title   author
           /   \
          /     \
   First_name  Last_name

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:

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

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.

    age = i(integer); r(real); s(string).
class predicates
    your_age :(age).
    your_age(i(Age)) :- stdio::write(Age).
    your_age(r(Age)) :- stdio::write(Age).
    your_age(s(Age)) :- stdio::write(Age).

Visual Prolog does not allow the following domain declaration:

/* Not permitted. */
    age = integer; real; string.


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

class predicates
    teacher :(string First_name, string Last_name, string Class) determ.
    teacher("Ed", "Willis", "english1").
    teacher("Ed", "Willis", "math1").
    teacher("Ed", "Willis", "history1").
    teacher("Mary", "Maker", "history2").
    teacher("Mary", "Maker", "math2").
    teacher("Chris", "Grahm", "geometry").

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.

    classes = string*.   /* declare a list domain */
class predicates
    teacher :(string First_name,  string Last_name,  classes Classes) determ.
    teacher("Ed", "Willis", ["english1", "math1", "history1"]).
    teacher("Mary", "Maker", ["history2", "math2"]).
    teacher("Chris", "Grahm", ["geometry"]).

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:

    integer_list = integer*.

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:

    integer_list = integer*.
class predicates
    test_scores :
        (string First_name,
          string Last_name,
          integer_list Test_Scores)
    test_scores("Lisa", "Lavender", [86, 91, 75]).
    test_scores("Libby", "Dazzner", [79, 75]).
    test_scores("Jeff", "Zheutlin", []).

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.

    tree_list = tree*.
    tree = tree(string Text, tree_list TreeList).
class predicates
    family :(tree) determ.
                [tree("Eric", []),
                 tree("Mark", []),
                 tree("Leonard", []) ] ),
             tree("Ellen", [])


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.