The Art of Prolog

The Art of Prolog

From「The Art of Prolog」。

The first time people understand the Prolog language, their previous ideas are transformed. This language, with its seemingly simple form, has unlimited potential and technical possibilities. However, there are few books that adequately convey its essence. Most of the explanatory books in the world are introductory.
This book responds to the intellectual needs of engineers who want to understand and master the essence of Prolog by explaining in an easy-to-understand manner the many applications and advanced practical programming techniques.
This book was originally written by Leon Sterling and Khud Shaplog to teach graduate students advanced “programming” in Prolog, and was published by MITPRESS as “Art of Prolog”.

The table of contents is as follows.

Part 1 Logic Programs 
Basic Components 
Database Programming 
Recursive Programming 
Computational Models of Logic Programs 
Theory of Logic Programs 

Part 2 Prolog Language 
Pure Prolog 
Pure Prolog Programming 
Arithmetic 
Structural Exploration 
Meta-logical Predicates 
Cut and Negation 
Extra-logical Predicates 
Theory of Practice
 
Part 3 Prolog Advanced Programming Techniques 
Nondeterministic Programming 
Incomplete Data Structures 
Parsing with Limited Clause Grammars 
Second-order Programming 
Search Techniques Meta-Integrators 

Part 4 Applications 
Game playing programs 
Credit evaluation expert systems 
Equation solving programs 
Compilers

These specific examples are discussed below.

Database programming using prolog

Prolog is a logic programming language that can also be used for database programming; in Prolog you can define facts and rules and use them to execute queries and search the database.

Below is a simple example of database programming using Prolog.

% Define people's relationships
parent_child_relationship(Taro_Tanaka, Hanako_Tanaka).
parent_child_relationship(Taro_Tanaka, Ichiro_Tanaka).
parent_child_relationship(Hanako_Tanaka, Jiro_Tanaka).

% Define sibling relationship
fraternal_relations(X, Y) :- parent_child_relationship(Z, X), parent_child_relationship(Z, Y), X \= Y.

% Query Execution
?- parent_child_relationship(parent, child).    % Parent-child relationship search
?- fraternal_relations(older_brother, young_brother).    % Sibling Relationship Search

In the above example, we define a fact called parent-child relationship and a rule called sibling relationship. The query is then used to search for parent-child and sibling relationships.

In Prolog, when a query is executed, the system performs a search based on the given rules and facts to find a solution that matches the query. If there is more than one matching solution, the system backtracks to find all solutions.

Recursive programming with prolog

Prolog is very well suited for recursive programming. By defining recursive rules, complex problems can be solved effectively. Below is an example of recursive programming using Prolog.

% Calculate the sum of natural numbers
total_amount(0, 0).                            % Base Case: Total of 0
total_amount(N, Sum) :- N > 0,                  % Recurrence case: N greater than 0
                N1 is N - 1,             % Decrease N by 1
                total_amount(N1, Sum1),         % Calculate the sum of N1
                Sum is Sum1 + N.         % Calculate the sum by adding N to Sum1

% Calculate the number of elements in a list
number_of_elements([], 0).                          % Base case: Number of elements in empty list is 0
number_of_elements([_|Tail], Count) :-              % Recursive case: ignore the first element in the list and calculate the number of remaining elements
                           number_of_elements(Tail, Count1),   % Calculate the number of remaining elements
                           Count is Count1 + 1.    % Add 1 to Count1 to compute the number of elements.

The above example defines two recursive rules: total and number of elements. The total rule calculates the sum of a given number, and the number of elements rule calculates the number of elements in a given list.

Recursive rules require a base case (termination condition) and a recursive case (recursive call). The base case defines the termination condition of the recursion, and the recursive case divides the problem into smaller subproblems, which are then solved recursively.

For example, the sum rule defines a zero sum as the base case, and the recursive case calculates the sum recursively, decreasing the given number by one.

Similarly, the number of elements rule defines the number of elements in an empty list to be 0 as the base case, and the recursive case calculates the remaining number of elements recursively, ignoring the first element in the list.

Recursive programming is a powerful technique for expressing problems in a natural form and finding efficient solutions, and Prolog’s recursive capabilities can be used to solve a wide variety of problems.

Meta-logical predicates using prolog

Metapredicates (Metapredicates) are predicates that take other predicates as parameters in Prolog. Metapredicates allow the definition of more general predicates and generalized operations, thereby increasing code reusability and flexibility.

Below is an example of using Prolog to define a meta-logical predicate. In this example, the meta-logical predicate maplist/3 is defined that applies the given predicate to the elements of a list.

% maplist/3の定義
maplist(_, [], []).                 % Base case: If the list is empty, the result is also an empty list
maplist(Pred, [X|Xs], [Y|Ys]) :-    % Recursive case: apply the predicate to the first element of the list and recursively to the remaining elements
                                  call(Pred, X, Y),   % Apply Pred to X to obtain Y
                                  maplist(Pred, Xs, Ys). % Apply recursively to the remaining elements

The above example defines a meta-logical predicate called maplist/3. This predicate applies the given predicate (Pred) to the elements of the list and returns a list of results.

The behavior of maplist/3 is divided into a base case and a recursive case. In the base case, given an empty list, the result is also an empty list. In the recursive case, the predicate is applied to the first element of the list to obtain the result, and then applied recursively to the remaining elements.

call/2 is a built-in Prolog predicate that executes the given predicate. Here, the pred is used to apply the pred to X to obtain Y.

Thus, meta-logical predicates can be used to abstract common operations and write highly reusable code.

Extra-logical predicates using prolog

Extra-logical predicates (Extra-logical predicates) are predicates that are not related to the logical operations and reasoning of Prolog. These predicates are used to manipulate the control and output of the program, such as debugging, displaying, changing control flow, etc.

The following is an example of using Prolog to define extra-logical predicates.

% Debugging predicate: display message
debug_message(Message) :-
    write('Debug: '),
    write(Message),
    nl.

% Change of control flow: call different predicates depending on conditions
condition_predicate(X) :-
    ( X > 0 ->
        positive_case(X)
    ;
        negative_case(X)
    ).

% Display list elements
print_list([]).
print_list([X|Xs]) :-
    write(X),
    write(' '),
    print_list(Xs).

In the above example, several extra-logical predicates are defined.

The debug_message/1 predicate is used to display debug messages and uses Prolog’s built-in predicates write/1 and nl/0 to output the given message.

The condition_predicate/1 predicate changes the control flow to call different predicates based on conditions, calling positive_case/1 if the conditional expression is satisfied and negative_case/1 if not.

The print_list/1 predicate is used to print the elements of the list. Recursively, the elements of the list are retrieved and the elements are displayed using write/1.

These extra-logical predicates are not directly related to the logical reasoning of Prolog and are used for practical purposes such as program control, debugging and output manipulation.

Nondeterministic programming with prolog

Prolog is very well suited for nondeterministic programming. Nondeterministic programming allows multiple possibilities to be explored simultaneously and the entire solution space to be explored to find a solution.

Prolog uses a mechanism called backtracking to achieve nondeterminism. Backtracking means that if an option fails, it returns to the previous option and tries another.

Below is an example of nondeterministic programming using Prolog.

% Find the square of a given number
square(X, Y) :- Y is X * X.

% Find the square root of a given number
sqrt(X, Y) :- Y is sqrt(X).

% Find the absolute value of a given number
abs(X, Y) :- X >= 0, Y is X.
abs(X, Y) :- X < 0, Y is -X.

% クエリの実行
?- square(3, X).   % Find the square of 3
?- sqrt(16, X).    % Find the square root of 16
?- abs(-5, X).     % Find the absolute value of -5

In the above example, we define the predicates square/2, sqrt/2, and abs/2, which are non-deterministic.

The square/2 predicate computes the square of a given number and squares the given number as is to obtain the result; the sqrt/2 predicate computes the square root of a given number and uses the built-in predicate, sqrt/1, to compute the square root; the abs/2 predicate computes the absolute value of a given number and computes the absolute value as is if the given number is greater than or equal to 0, and the sign is negative. If the given number is greater than or equal to zero, the absolute value is obtained as is; if it is negative, the sign is reversed.

When executing these predicates, Prolog uses backtracking to search for possibilities and continues the search until it finds a solution that meets the given conditions. If multiple solutions exist, backtracking allows it to find all of them.

Nondeterministic programming is a powerful technique for effectively exploring the solution space of a problem and is one of Prolog’s distinguishing features.

Incomplete data structures using prolog

There are several ways to represent incomplete data structures using Prolog. Some common methods are listed below.

1. Data representation using function symbols: There are ways to represent incomplete data structures using function symbols. For example, empty data is represented by the function symbol empty, and if data exists, it is represented by another function symbol.

% Example of incomplete data structure: first element and remaining elements of a list
data(empty).
data(element(X, Rest)) :- data(Rest).

In this example, a predicate named data/1 is defined. data/1’s argument is given a data structure. Empty data is represented by the function symbol empty, and if an element exists, it is represented by the function symbol element(X, Rest). This type of representation can indicate incompleteness of data.

2. Data representation using property lists: Property lists provide a way to represent incomplete data structures as a list of attribute-value pairs. If an attribute exists, it is represented as a pair in the list, and if the attribute does not exist, it is represented as its absence.

% Example of incomplete data structure: property list
data([]).
data([property(X, Value)|Rest]) :- data(Rest).

In the above example, a predicate named data/1 is defined. data/1’s argument is given a data structure. If the property exists, it is represented by the pair property(X, Value); if the property does not exist, it is represented by an empty list[].

These examples use Prolog predicates to represent incomplete data structures. Recursive predicate definitions and the form of specific function symbols and property lists are used to represent incomplete data structures, which allows incomplete data structures to be handled in the program.

Second floor programming with prolog

Although Prolog is a language based on first-order predicate logic, there is a way to mimic second-order predicate logic: second-order programming takes predicates as arguments and allows manipulation of dynamically generated predicates.

The following is an example of second-order programming using Prolog.

% Definition of second-order predicates
my_predicate(Pred) :-
    Pred.

% test predicate
foo(X) :- X = 1.
bar(X) :- X = 2.

% Calling a second-order predicate
?- my_predicate(foo(1)).  % Call foo/1
?- my_predicate(bar(2)).  % Call bar/1

The above example defines a second-order predicate named my_predicate/1. This predicate executes a predicate received as an argument. Specifically, it receives the argument Pred and executes it.

As test predicates, foo/1 and bar/1 are defined, and these predicates are defined to satisfy specific conditions depending on their arguments.

When calling my_predicate/1, the predicate can be executed by giving the specific predicate as an argument. In the example, my_predicate(foo(1)) and my_predicate(bar(2)) are called.

In this way, second-order programming can take predicates as arguments and manipulate dynamically generated predicates. This allows for more flexible program definition and control, but since Prolog itself is based on first-order predicate logic, it does not provide the full functionality of second-order predicate logic.

Meta imprinter with prolog

Prolog has a meta-programming feature that allows the construction of a meta-interpreter (Meta-Interpreter). A meta-interpreter is a meta-program that controls the execution of a program and manipulates the program itself.

Below is an example of a simple meta-interpreter implementation using Prolog.

% Meta Interpreter Definition
interpret(true) :- !.
interpret((A, B)) :- !,
    interpret(A),
    interpret(B).
interpret(Head) :-
    clause(Head, Body),
    interpret(Body).

% test predicate
foo(a).
foo(b).
foo(c).

% Using the Meta Interpreter
?- interpret((foo(X), X = a)).

In the above example, a meta-interpreter named interpret/1 is defined. This meta-interpreter interprets and executes the given program.

The definition of interpret/1 handles three cases. First, if true is given, it exits as success. Second, if a program of the form (A, B) is received, it executes A and B in turn. Finally, the predicate CLAUSE/2 is used to obtain the correspondence between the head and body of the program, and the body is executed recursively.

As a predicate for testing, we define foo/1, which is defined as a simple fact.

The last query uses interpret/1 to execute the program (foo(X), X = a). This program executes foo(X), which means that it binds a to X.

Thus, a meta-interpreter can be constructed using Prolog’s metaprogramming facilities. The meta-interpreter is used as a flexible method to control the interpretation and execution of programs.

Credit Evaluation Expert System using PROLOG

A credit evaluation expert system will be a rule-based system for evaluating creditworthiness and reliability; to implement a credit evaluation expert system using Prolog, it is necessary to combine a rule-based knowledge base with an inference engine.

Below is an example of a simple credit evaluation expert system implementation using Prolog

% Rule-based definitions
trustworthy(X) :-
    has_good_reputation(X),
    has_completed_successful_projects(X).

has_good_reputation(john).
has_good_reputation(susan).

has_completed_successful_projects(john).

% Credit Rating Expert System Queries
?- trustworthy(john).

The above example defines a predicate that evaluates trustworthy/1. This predicate judges as trustworthy a person who satisfies both has_good_reputation/1 and has_completed_successful_projects/1.

has_good_reputation/1 and has_completed_successful_projects/1 are defined as facts, indicating whether a particular person meets each condition.

The last query uses trustworthy/1 to evaluate john’s creditworthiness. This query returns the result that john is trustworthy because it satisfies both has_good_reputation(john) and has_completed_successful_projects(john).

Thus, a credit evaluation expert system can be built using Prolog. By adding more complex rules and evaluation criteria, it is possible to build more sophisticated credit evaluation systems.