You say yes, I say no
Hello hello, how low.
Prolog
Forget about everything that you have been taught as a programmer. Take a deep breath. Whatever you are going to read soon is nothing but familiar. Beware of your clicks. As you may find yourself forever lost in the underworld of logic programming languages.
All You Need is Logic Programming Languages
Before getting into details, here is a quick shpargalka for the logic programming paradigm:
- Logic programs are declarative. You probably are familiar with procedural languages with all the assignments and stuff (more about that later). By contrast, in logic programming languages, the specifications are declared, not assigned. You should know that both declarative programming and logic programming refer to the same concept.
- Logic programming languages consist of facts and rules.
- Logic programming relies on predicate calculus.
- Prolog is the most widely used logic programming language.
- As declarative language semantics is much simpler than the semantics of imperative languages (i.e. most of the currently popular programming languages), language semantics is considered to be an advantage of logic programming over imperative programming.
Procedural vs Nonprocedural Programming
Imperative and functional programming languages can be considered as being procedural, that is, a programmer instructs the computer on exactly how a result should be computed. On the other foot, the logic programming paradigm is nonprocedural. This means that programs do not state exactly how the computation is to be done, but describe the form of the result.
Can’t Buy Me Prolog
As Prolog is the most widely used logic programming language, we are willing to discuss it. There are different dialects of Prolog — Marseille group, Edinburgh group, and the group developed for microcomputers. We will discuss Edinburgh syntax as the Concepts of Programming Languages book (see the end of the article) discusses it. More specifically, my personal taste will lean on SWI-Prolog, which is very simple and tidy.
Here Comes the Prolog
Prolog statements and data are constructed from terms, which are either a constant, variable, or structure.
A constant could be an atom or an integer. An atom, being similar to its Lisp counterpart, is either a string of letters, digits, and underscores beginning with a lowercase letter or a string of any printable.
A variable differs from a constant by being written beginning with an uppercase letter. The binding of a type to a variable is called an instantiation, which occurs in the resolution process.
Finally, we have a structure, identified by the functor:
functor(parameter list)
Fact statements
Facts can mean whatever the programmer wants them to mean. For example, “car” could be the speed in miles per seconds written in morse alphabet, and “500” could mean a roast chicken.
speed(car, 500)
Rule statements
If -> then. It should be clear I guess. Commas could be considered as logical AND operators. In general form, rules can be written as follows:
consequence :- antecedent_expression.
Goal statements
Goals (or queries) are, simply put, theorems that the system either proves or disproves by responding yes or no.
chicken(roasted)
Goals are syntactically very similar to facts, so the only way they are distinguished is dependent on which mode they are written in. For example, the online SWI-Prolog compiler has two separate windows — one for declaring rules and facts, and the other for queries (goals).
List Structures
In addition to atomic propositions, there is another basic data structure called list. We create a list as follows:
new_list([argon, jargon, gorgon])
If we are going to bring an analog with Lisp, CAR and CDR of a list can be denoted with the following expression:
new_list([Head | Tail])
That will make Head instantiated as [argon], and Tail as [jargon, gorgon].
Another similarity of Prolog to Lisp is append, which differs a little in its implementation. I will refer to the SWI-Prolog documentation, partly because I am lazy and partly because I don’t want to reinvent the bicycle.
Prolog Resolution
Goals can be compound, when each of their facts is called a subgoal. There are two approaches to match a goal to a fact in the database.
Bottom-up resolution or forward chaining is when we start with the facts and rules in the database and search for a sequence of matches that will lead to the goal.
Top-down resolution or backward chaining is when we start with the goal and search for a sequence of matches that will lead to some set of facts in the database. It works well when there is a small number of candidate answers, otherwise, forward chaining is preferable.
Prolog designers have decided to implement backward chaining for resolution instead of forward chaining.
When a goal has more than one structure, Prolog needs to choose between depth-first and breadth-first search. Depth-first search finds a complete sequence of propositions of a subgoal before working on others, whereas breadth-first search works on all subgoals in parallel.
Prolog designers have decided to implement depth-first search instead of breadth-first, as the latter requires a large amount of memory.
Back-tracking. When the system fails to prove a subgoal, it abandons the subgoal. Then the system goes on to reconsider the previous subgoal and find an alternative solution for it. Such reconsideration is called back-tracking.
Prolog Arithmetic
Prolog can work with integer variables and integer arithmetic. Originally, operators were only functors, but now Prolog supports the following expression:
A is B + C
When B and C (right-side) must already be instantiated when A (left-side) must not. It is not an assignment statement that we use in imperative programming. Not meeting one of the “must” conditions will result in the failure of the clause.
Prolog Example
For a better understanding of the logic that we have been discussing all along, let’s take the simplified example below which I took from the CPL book (see the reference):
distance(X, Y) :- speed(X, Speed), time(X, Time),
Y is Speed * Time.
The expression above calculates the distance of an instantiated atom. For example, after declaring both speed and time
speed(car, 50).
time(car, 10).
we can query to retrieve the distance.
distance(car, Cardist).
Do not mess up with the Capital letters. You can copy-paste the code and try it on the SWI-Prolog console.
Tracing Model
A built-in structure of Prolog called trace displays the instantiations of values to variables at each step. It is a debugging mechanism of Prolog programs.
The tracing model describes Prolog execution in four steps.
- Call
- Exit
- Redo
- Fail
Call happens in the beginning when we try to satisfy a goal, exit happens when the goal actually gets satisfied, redo happens during back-tracking, fail happens when the system cannot prove the query.
Resolution Order Control
As Prolog always matches in the same order, from the beginning of the database to the end, the user can increase the efficiency of a program by placing some rules to the beginning of the database. Prolog also allows some explicit control of backtracking with the help of the cut (!) operator.
a, b, !, c.
Here, if c fails, the whole goal fails, as the programmer assumes that whenever c fails, there is no need to resatisfy a or b.
Although the cut operator is important, it is possible to abuse it by making logic programs have a control flow similar to imperative programming styles. Of course, it undermines the importance of logic programming, as now we specify how solutions are to be found. That reduces the readability and writability of programs.
We have already noted that the semantics of logic programming languages is their main advantage over their imperative counterparts. However, trying to make use of resolution order control by increasing efficiency, one can clutter the code with all the unnecessary details of how the solutions are to be determined.
Limitations of Prolog
We have just discussed one limitation of Prolog. However, there are some more. So may I have your attention, please.
Closed-Word Assumption. Prolog’s world is so narrow; its knowledge is only bound within its database. If the database doesn’t have any information to prove the received query absolutely, then the system returns false. Prolog can prove that something is true, but it can’t prove if it is false. Innocent until proven guilty. But it is false logic: if a query isn’t absolutely true, then it isn’t necessarily false.
Another important limitation of Prolog, the Negation Problem, arises as a consequence of the closed-word assumption.
Again, as opposed to procedural programming, programmers specify what a program is supposed to do without a need for specifying how exactly. But that leads to some intrinsic limitations of Prolog.
For example, it is impossible to transform the description of a sorted list into some efficient algorithm for sorting. Even resolution is not capable of fixing that. Therefore, there is no way but to specify the details of how efficient sorting can be done, which unfortunately morphs the pure logic paradigm of Prolog into imperative or functional one.
Application of Logic Programming
Enough about Prolog. In Relational Database Management Systems (RDBMS) queries are often written in Structured Query Language (SQL) which is nonprocedural. A user doesn’t need to specify how to retrieve data. In addition to RDBMS, logic programming is also frequently used in Expert Systems and Natural-Language Processing.
Epilog
No, I am not a Beatle fan. Referencing doesn’t imply admiring. Except for the case below, of course.
Jai Guru Deva Om
Concepts of Programming Languages (12th ed.) by Robert W. Sebesta