CS441 Fall 2001

Project #1: Prolog, Mercury, and the Logic Language Family

Adam Dang (ad056@umkc.edu)

Yenor Liang (yol4b7@umkc.edu)

Sarah Wang (sw6bf@umkc.edu)

Prolog (PROgramming LOGic) is a declarative logic programming language that has become one of the most widely used languages for artificial intelligence (AI). Prolog became a serious competitor to LISP because it represented a fundamentally new approach to computing.

Early attempts at logic-based languages in the United States included Micro-Planner and Conniver. Both attempts failed to replace LISP as an artificial intelligence programming language because they were extremely inefficient. Prolog grew out of work on natural language processing done by Alain Colmerauer in Montréal and later in Marseille, and separate work on the use of logic for programming by Robert Kowalski at Imperial College, London. It was first implemented 1972 in ALGOL-W. Early collaboration between The University of Aix-Marseille and Kowalski (who had moved to the University of Edinburgh) continued until about 1975. The fact that Prolog overcame the problems that bedeviled Micro-Planner and Conniver is due to Kowalski’s work on the efficient implementation of Prolog.

Prolog is based on SLD (Selected Literal Definite) clause resolution, theorem proving, and unification. The first versions had no user-defined functions and no control structure other than the built-in depth-first search with backtracking.

Early implementations included C-Prolog, ESLPDPRO, Frolic, LM-Prolog, Open Prolog, SB-Prolog, UPMAIL Tricia Prolog. Currently, the most common Prologs in use are Quintus Prolog, SICSTUS Prolog, LPA Prolog, SWI Prolog, AMZI Prolog, SNI Prolog.

2. Overview of Prolog

Logical programming represents an effort by computer science to free the programmer from "the drudgery of memory management, stack pointers, etc.", and instead allow the program designer to fully concentrate on describing the problem and the properties of the correct answer. Languages used for logical programming belong to the declarative paradigm: the program specifies a computation by giving the properties of a correct answer. This is quite different from the more familiar procedural paradigm where the program specifies a computation by saying how it is to be performed. However, it should be noted that there is no well-defined boundary between procedural and declarative paradigms. Procedural languages commonly include logic testing capabilities, and declarative languages by necessity provide some procedural features such as input/output facilities.

Prolog is the most widely used VHLL (Very High Level Language), which clearly possesses many characteristics of declarative languages. The Prolog compiler, not the programmer, is responsible for translating a description of the problem and solution into the low level instructions of whatever computer happens to host the program. By allowing the programmer to model the logical relationships among objects and processes, complex problems are inherently easier to solve, and the resulting program is easier to maintain through its lifecycle. Given the necessary facts and rules, Prolog will use deductive reasoning to solve many programming problems. The Prolog programmer only needs to supply a description of the problem and the ground rules for solving it. From there, the Prolog system is left to determine how to find a solution. Because of this declarative (rather than procedural) approach, well-known sources of errors such as loops that carryout one too many or one too few operations are eliminated right from the start. Prolog encourages the programmer to start with a well-structured description of the problem, so that, with practice, Prolog can also be used as both a specification tool, and the implementation vehicle for the specified product.

Prolog uses facts and rules. Apart from some initial declarations, a Prolog program essentially consists of a list of logical statements, either in the form of facts, such as:

father ("John", "Mary") "John is the father to Mary"

or in the form of rules, such as :

sister (X, Y) :- father(Z,X),

where X Y, Z are variables, which are used to specify bindings between the different relations. Variables can be any name starting with an uppercase letter.

Prolog can make deductions. Given some goals, for example, to conditions:

Goal father ("John", "Mary").

Prolog will answer true because the goal matches the stored facts.

If variables are used in the goals, Prolog will find values for the variables:

Goal father (X, "Mary").

Prolog will answer X="John" because it can look it up in the facts. There is no difference between using facts and rules, for example if the goal is:

Goal sister (X, "Mary").

Prolog will answer X="Sally" because "Sally" can satisfy the rule for sister.

Similarly, Prolog can use its deductive ability to find all solutions to the problem:

Goal father ("John", X).

Prolog will answer

X="Mary"

The solutions are found through backtracking where all combinations are tried.

Another representative of the declarative paradigm is Mercury, which is being developed in the University of Melbourne, Australia. Mercury is a logic/functional programming language, which combines the clarity and expressiveness of declarative programming with advanced static analysis and error detection features. Its highly optimized execution algorithm delivers efficiency far in excess of existing logic programming systems, and close to conventional programming systems. Mercury addresses the problems of large-scale program development; allowing modularity, separate compilation, and numerous optimization/time trade-offs.

Logic programming is considered by some to be far superior to procedural programming. Among the advantages of declarative languages are:

Short development time

Easy to Read - Easy to Modify - Easy to learn

Easy Manipulation of Complex Data Structures

With such impressive characteristics, it is not surprising that Prolog, Mercury and other logic programming languages find solid following and support in the programming and scientific communities.

 3. Handling of Data Objects in Prolog

Prolog programs consist of collections of statements. All Prolog statements are constructed from terms. The basic Prolog terms are

o        Integer - A positive or negative number whose absolute value is less than some implementation-specific power of 2.

o        Atom - A text constant beginning with a lowercase letter

o        Variable - begins with an uppercase letter or underscore (_)

o        Structure - Complex terms. The general form is functor(parameter list). The functor is any atom and is used to identify the structure and the parameter list can be any list of atoms, variables or other structures.

Prolog has two basic statement forms. These correspond to the headless and headed Horn clauses of predicate calculus. The simplest form of headless Horn clause in Prolog is a single structure, which is interpreted as an unconditional assertion or fact.

The syntax for a fact is

          pred(arg1, arg2, … argN).

Where

          pred - The name of the predicate

          arg1, … - The arguments

          N - The arity

          . - The syntactic end of all Prolog clauses

For example

          female(shelley).

          male(bill).

          Father(bill, shelley).

The other basic form of Prolog statement for constructing the database corresponds to a headed Horn clause. This form can be related to a known theorem in mathematics from which a conclusion can be drawn if the set of given conditions is satisfied. If the antecedent (the right side of a clausal form proposition) of a Prolog statement is true, then the consequent of the statement must also be true. Headed Horn clauses are called rules because they state rules of implication between propositions.

For example

          Ancestor(mary, shelley)       :- mother(mary, shelley).

States that if mary is the mother of shelley, then mary is an ancestor of shelley.

In Prolog, the statements for logical propositions, which are used to describe both known facts and rules that describe logical relationships among facts, are called goals, or queries.

For example, we could have

          man(fred).

To which the system will respond either yes or no. The answer yes means that the system has proved the goal was true under the given database of facts and relationships. The answer no means that either the goal was proved false or the system was simply unable to prove or disprove it.

Conjunctive propositions and propositions with variables are also legal goals. When variables are present, the system not only asserts the validity of the goal but also identifies the instantiations of the variables that make the goal true.

For example,

          father(X, mike).

Can be asked. The system will then attempt, through unification (see next paragraph), to find an instantiation of X that results in a true value for the goal.

To prove that a goal is true, Prolog finds solutions by unification: binding a variable to a value. For an implication to succeed, all goal variables on the left side of :- must find a solution by binding variables from the clauses, which are activated on the right side. Standard Prolog evaluates clauses from left to right. When all clauses are examined and all goal variables are bound, the goal succeeds. In other words:

Goalclause(Vg) is true if clause1(V1) and … and clausem(Vm) are true.

The following table summarizes the unification process.

But if a variable can not be bound for a given clause, that clause fails. When any clause fails, Prolog backtracks - it backs up in the goal to the reconsideration of a previously proven subgoal. Backtracking gives Prolog the ability to find multiple solutions to for a given query or goal.

Handling of Data Objects - Comparison of Prolog and Mercury

·        Unlike Prolog, Mercury supports additional constructs that declare type, mode, and other constraints. Data types supported by the language include: integers, reals, strings, and a very flexible record/union type; the standard library supports a wide variety of collection types including arrays, lists, trees, maps, etc. The three important additional features Mercury has over Prolog are Types, Modes and Determinism.

·        Mercury is a strongly typed language. Mercury's type system is based on many-sorted logic with parametric polymorphism, very similar to the type systems of modern functional languages such as ML and Haskell. Programmers must declare the types they need and the type signatures of the predicates they define. Declaring the type of a predicate specifies the sets of values from which the predicate variables may be drawn. Mercury has a polymorphic type system and its standard types include:

        char

        int

        float

        string - equivalent to Mercury's string type

        list(int)

·        Mercury is a strongly moded language. The programmer must declare the instantiation state of the arguments of predicates at the time of the call to the predicate and at the time of the success of the predicate. Currently only a subset of the intended mode system is implemented. Declaring the modes of a predicate specifies which of the variables are to be viewed as input parameters and which are to be viewed as output parameters. The compiler will infer the mode of each call, unification and other built-in in the program. It will reorder the bodies of clauses as necessary to find a left to right execution order; if it cannot do so, it rejects the program. Like type-checking, this means that a large class of errors is detected at compile time.

·        Mercury has a strong determinism system. Predicates in Mercury may fail, succeed once or succeed more than once. The number of times a predicate should succeed is specified by the determinism of the predicate. Declaring the determinism of a predicate specifies how often it may succeed, if at all. For each mode of each predicate, the programmer should declare whether the predicate will succeed exactly once (det), at most once (semidet), at least once (multi) or an arbitrary number of times (nondet). As with types and modes, determinism checking catches many program errors at compile time.

·        Mercury handles dynamic data structures not through Prolog's assert/retract but by providing several abstract data types in the standard Mercury library that manage collections of items with different operations and tradeoffs.

·        Mercury also has a couple of differences in data-term from Prolog. The first one is that double-quoted strings are atomic in Mercury, they are not abbreviations for lists of character codes. The second is that Mercury provides several extensions to Prolog's term syntax: Mercury terms may contain record field selection and field update expressions, conditional (if-then-else) expressions, function applications, higher-order function applications, lambda expressions, and explicit type qualifications.

·        In Mercury, syntactically, a data-term is just a term. A data-term is either a variable, a data-functor, or a special data-term. A special data-term is a conditional expression, a record syntax expression, a lambda expression, a higher-order function application, or an explicit type qualification

4. Handling of Sequence Control in Prolog

• Trace model

Prolog has a built-in structure named trace that displays the instantiations of values to variables at each step during the attempt to satisfy a given goal. Trace is used to understand and debug Prolog programs.

The tracing model describes Prolog execution in terms of four events:

1.      call, which occurs at the beginning of an attempt to satisfy a goal

2.      exit, which occurs when a goal has been satisfied

3.      redo, which occurs when backtrack causes an attempt to resatisfy a goal

4.      fail, which occurs when a goal fails.

Call and exit can be related directly to the execution model of a subprogram in an imperative language.

From following example, you can tell how Prolog produces results by using trace mode.

Database and traced compound goal:

likes(jake, chocolate).

likes(jake, apricots).

likes(darcie, licorice).

likes(darcie, apricots).

Trace.

Likes(jake, X), likes(darcie, X).

(1) 1 call: likes(jake, _0)?

(1) 1 Exit: likes(jake, chocolate)

(2) 1 Call: likes(darcie, chocolate)?

(2) 1 Fail: likes(darcie, chocolate)

(1) 1 Redo: likes(jake, _0)?

(1) 1 Exit: likes(jake, apricots)

(3) 1 Call: likes(darcie, apricots)?

(3) 1 Exit: likes(darcie, apricots)

X = apricots

Consider each goal as a box with four ports - call, fail, exit, and redo. Control enters a goal in the forward direction through its call port. Control can also enter a goal from the reverse direction through its redo port. Control can also leave a goal in two ways: if the goal succeeded, control leaves through the exit port; if the goal failed, control leaves through the fail port. A model of the example above is shown in Figure 1.

Figure 1 - Control flow model for the goal likes(jake, X), likes(darcie, X)

• Repeat control structure

It always succeeds the first time it is called, and it always succeeds on backtracking. In other words, you can not backtrack through a repeat/0.

          Figure 2 - Flow of control in the repeat built-in predicate

A repeat/0 followed by some intermediate goals followed by a test condition will loop until the test condition is satisfied. It is equivalent to a 'do until' in other languages.

The following command_loop/0 will simply read commands and echo them until end is entered. The built-in predicate read/1 reads a Prolog term from the console. The term must be followed by a period.

  command_loop:-  

         repeat,

         write('Enter command (end to exit): '),

         read(X),

         write(X), nl,

         X = end.

The last goal will fail unless end is entered. The repeat/0 always succeeds on backtracking and causes the intermediate goals to be re-executed.

We can execute it by entering this query.

   ?- command_loop.

• Recursive control structure

Because logical variables cannot have their values changed by assignment, the commands must take two arguments representing the old state and the new state. The repeat-fail control structure will not let us repeatedly change the state in this manner, so we need to have a recursive control structure that recursively sends the new state to itself.

In Prolog, recursion occurs when a predicate contains a goal that refers to itself. Every time a rule is called, Prolog uses the body of the rule to create a new query with new variables. Since the query is a new copy each time, it makes no difference whether a rule calls another rule or itself.

A recursive definition always has at least two parts, a boundary condition and a recursive case. The boundary condition defines a simple case that we know to be true. The recursive case simplifies the problem by first removing a layer of complexity, and then calling itself. At each level, the boundary condition is checked. If it is reached the recursion ends. If not, the recursion continues.

For example

The following predicates tell us the first object is contained in second object.

        location(envelope, desk).

        location(flashlight, desk).

        location(desk, office).

        location(stamp, envelope).

        location(key, envelope).

Now, we need to find out

  ?- location(flashlight, office).

Even predicate tells us the flashlight is in the desk and the desk is in the office, but it does not indicate that the flashlight is in the office.

Using recursion, we will write a new predicate, is_contained_in/2, which will dig through layers of nested things, so that it will answer 'yes' if asked if the flashlight is in the office.

We can state a two-part rule which can be used to deduce whether something is contained in (nested in) something else.

o        A thing, T1, is contained in another thing, T2, if T1 is directly located in T2. (This is the boundary condition.)

o        A thing, T1, is contained in another thing, T2, if some intermediate thing, X, is located in T2 and T1 is contained in X. (This is where we simplify and recurse.)

The first rule translates into Prolog in a straightforward manner.

  is_contained_in(T1,T2) :-  location(T1,T2).

The recursive rule is also straightforward. Notice that it refers to itself.

  is_contained_in(T1,T2) :- location(X,T2), is_contained_in(T1,X).

Then try it.

  ?- is_contained_in(X, office).

  X = desk ;

  X = computer ;

  X = flashlight ;

  X = envelope ;

  X = stamp ;

  X = key ;

  no

  ?- is_contained_in(envelope, office).

  yes

How Recursion Works

As in all calls to rules, the variables in a rule are unique, or scoped, to the rule. In the recursive case, this means each call to the rule, at each level, has its own unique set of variables. So the values of X, T1, and T2 at the first level of recursion are different from those at the second level.

However, unification between a goal and the head of a clause forces a relationship between the variables of different levels. Using subscripts to distinguish the variables, and internal Prolog variables, we can trace the relationships for a couple of levels of recursion.

First, the query goal is

?- is_contained_in(XQ, office).

The clause with variables for the first level of recursion is

is_contained_in(T11, T21) :-

  location(X1, T21),

  is_contained_in(T11, X1).

When the query is unified with the head of the clause, the variables become bound. The bindings are

XQ = _01

T11 = _01

T21 = office

X1 = _02

Note particularly that XQ in the query becomes bound to T11 in the clause, so when a value of _01 is found, both variables are found.

With these bindings, the clause can be rewritten as

is_contained_in(_01, office) :-

  location(_02, office),

  is_contained_in(_01, _02).

When the location/2 goal is satisfied, with _02 = desk, the recursive call becomes

is_contained_in(_01, desk)

That goal unifies with the head of a new copy of the clause, at the next level of the recursion. After that unification the variables are

XQ = _01        T11 = _01       T12 = _01

                T21 = office    T22 = desk

                X1 = desk       X2 = _03

When the recursion finds a solution, such as 'envelope,' all of the T1s and X0 immediately take on that value.

Handling of Sequence Control - Comparison of Prolog and Mercury

·        Because Mercury is purely declarative, the goal `Goal, fail' is interchangeable with the goal `fail, Goal'. Also because it is purely declarative, there are no side effects to goals. As a consequence of these two facts, it is not possible to write failure driven loops in Mercury. Neither is it possible to use predicates such as assert or retract. However, all these can be done in Prolog. Failure driven loops in Prolog programs is similar to the ordinary tail recursion in Mercury.

·        ISO Prolog provides call/1, but there is no call/N (N>1). Most Prolog systems implement call/1 quite inefficiently, and the calls to univ/2 and append/3 make call/N even less efficient. Mercury provides a reasonably efficient call/1 and call/N (N>1). As a convenience, Mercury also provides lambda expressions, so that programmers can write a higher-order term without resorting to using an auxiliary predicate.

·        Input and Output control - Mercury is a purely declarative language. Therefore it cannot use Prolog's mechanism for doing input and output with side effects. The mechanism that Mercury uses is the threading of an object that represents the state of the world through the computation. The type of this structure is `io__state'. The modes of the two arguments that are added to calls are `di' for "destructive input" and `uo' for "unique output''. The first means that the input variable must be the last reference to the original state of the world, and that the output variable will be the only reference to the state of the world produced by this predicate.

Predicates that do input or output must have these arguments added.

For example the Prolog predicate:

write_total(Total) :-

    write('The total is '),

    write(Total),

    write('.'),

    nl.

In Mercury becomes

:- pred write_total(int, io__state, io__state).

:- mode write_total(in, di, uo) is det.

write_total(Total, IO0, IO) :-

    print("The total is ", IO0, IO1),

    print(Total, IO1, IO2),

    print('.', IO2, IO3),

    nl(IO3, IO).

One of the important consequences of the model for input and output is that predicates that can fail may not do input or output. This is because the state of the world must be a unique object, and each IO operation destructively replaces it with a new state. Since each IO operation destroys the current state object and produces a new one, it is not possible for IO to be performed in a context that may fail, since when failure occurs the old state of the world will have been destroyed, and since bindings cannot be exported from a failing computation, the new state of the world is not accessible.

In some circumstances, Prolog programs that suffer from this problem can be fixed by moving the IO out of the failing context. For example

    ...

    ( solve(Goal) ->

        ...

    ;

        ...

    ),

    ...

where `solve(Goal)' does some IO can be transformed into valid Mercury in at least two ways. The first is to make `solve' deterministic and return a status:

    ...

    solve(Goal, Result, IO6, IO7),

    ( Result = yes ->

        ...

    ;

        ...

    ),

    ...

The other way is to transform `solve' so that all the input and output takes place outside it:

    ...

    io__write_string("calling: ", IO6, IO7),

    solve__write_goal(Goal, IO7, IO8),

    ( solve(Goal) ->

        io__write_string("succeeded\n", IO8, IO9),

        ...

    ;

        IO9 = IO8,

        ...

    ),

    ...

o        Recursive Control - Prolog code is written in a way that traverses the input list left-to-right, appending elements to the tail of a difference list to produce the output. However, Mercury code traverses the input list right-to-left and constructs the output list bottom-up rather than top-down. It is tail-recursive on the first recursive call, not the second one.

In most circumstances, the need for difference lists is negated by the simple fact that Mercury is efficient enough for them to be unnecessary.

o        Prolog uses assert and retract methods to achieve goals. But Mercury has a standard library which includes modules for lists, stacks, queues, priority queues, sets, bags (multi-sets), maps (dictionaries), random number generation, input/output and filename and directory handling to manipulate its execution behavior. The implementation section must contain definitions for declarations, functions, predicates, and sub-modules exported by the module.

For example, here is the definition of a simple module for managing queues:

:- module queue.

:- interface.

% Declare an abstract data type.

:- type queue(T).

% Declare some predicates which operate on the abstract data type.

:- pred empty_queue(queue(T)).

:- mode empty_queue(out) is det.

:- mode empty_queue(in) is semidet.

:- pred put(queue(T), T, queue(T)).

:- mode put(in, in, out) is det.

:- pred get(queue(T), T, queue(T)).

:- mode get(in, out, out) is semidet.

:- implementation.

% Queues are implemented as lists. We need the `list' module

% for the declaration of the type list(T), with its constructors

% '[]'/0 % and '.'/2, and for the declaration of the predicate

% list__append/3.

:- import_module list.

% Define the queue ADT.

:- type queue(T) == list(T).

% Declare the exported predicates.

empty_queue([]).

put(Queue0, Elem, Queue) :-

         list__append(Queue0, [Elem], Queue).

get([Elem | Queue], Elem, Queue).

:- end_module queue.

5. Handling of Subprograms and Storage Management in Prolog

Prolog offers two fundamentally different ways of data representation. Structured Terms are used when data structure needs to be passed between procedures. Another way to represent data is as the Set of Facts. The choice of which representation to use can affect the procedures needed in order to search and manipulate, which, in turn affects the subprograms and how they are handled in memory. When representing data as structured terms, structures can get large, demanding more memory, and finding them can become tedious.

Here is an example of the use of structures in Prolog. A database of books in a library contains facts of the form:

A member of the library may borrow a book. When this is done, a "loan" is entered into the database recording the catalogue number of the book that was borrowed and the number of the member who borrowed it. The date at which the book was borrowed and the due date are also recorded. Dates are stored as structures of the form date(Year, Month, Day). For example:

:- module array.

:- interface.

% Declare an abstract data type.

:- type array(T).

% Declare some predicates that operate on the abstract data type.

:- pred empty_array(array(T)).

:- mode empty_array(out) is det.

:- mode empty_array(in) is semidet.

:- pred put(array(T), T, array(T)).

:- mode put(in, in, out) is det.

:- pred get(array(T), T, array(T)).

:- mode get(in, out, out) is semidet.

:- implementation.

% Arrays are implemented as lists. We need the `list' module

:- import_module list.

% Define the array ADT.

:- type array(T) == list(T).

% Declare the exported predicates.

empty_array([]).

put(Array0, Elem, Array) :-

         list__append(Array0, [Elem], Array).

get([Elem | Array], Elem, Array).

:- end_module Array.