The computational model of Prolog-programs is based on the calculus of predicates, which is a mathematical apparatus that allows representing almost any knowledge. For example, the article describes a block of knowledge on constructing towers from planes, parallelepipeds, cylinders and other primitives, taking into account their sizes and positions.

Predicate logic defines the rules by which logical deduction can be made, but to write a program this is not enough – you need a programming language.

Each Prolog dialect has its own peculiarities. For example, Turbo Prolog uses the equals operator for assignment, while SWI and GNU Prolog use the is operator for assignment. There are even object-oriented dialects, such as Visual Prolog. Part of the dialects (Datalog) is a language for querying databases (analog of SQL, but for non-relational databases) and has some limitations – for example, does not support clipping operator. Prolog has an international standard, but most dialects do not comply with it.

From the point of view of asymptotic complexity evaluation, for which computational models are developed, the syntactic differences of these languages are not important. What is important is the following:

– the language has a set of mathematical and logical operators;
a program consists of predicates;
– the predicate consists of rules; the invocation of the predicate leads to the selection and execution of rules that fit the actual set of parameters of the invocation (a pattern-matching mechanism).
– the program uses lists, which in different dialects can be implemented differently (and have different asymptotic estimates of typical operations).
– automatic enumeration with returns is built into the language, due to which the predicate can return not one result but many;
Almost all modern Prolog dialects have a cut operator, which stops the enumeration with returns.

To perform an asymptotic evaluation of the complexity of Prolog programs, it is necessary to estimate the costs of specific Prolog mechanisms. For this, it is convenient to rely on the RAM model. RAM is based on an abstract machine on a tape of which commands are written. The machine reads and executes commands sequentially, however, the program execution process is fundamentally different. Instead of sequentially reading commands from the tape, it implements a search with returns.

The organization of the computational process of a Prolog program notes the following:

– any prologue program has a “goal” that sets the entry point into the program (with which the computation begins);
– each predicate rule consists of a “head” (describing the input parameters) and a “body” (describing the computation);
– a subset of facts, that is, predicates without a body, which are always true, can be distinguished from the set of predicates;
– the mechanism of pattern-matching is to check whether part of the goal and head of the predicate can be substituted;
– if the attempt to match the subgoal with the facts in the database fails and alternative (not yet applied rules or facts) remain, Prolog will go back and use these alternatives.

The last point corresponds to the description of the search mechanism with returns. Roughly speaking, to estimate the asymptotic complexity of Prolog programs, we need to estimate the “cost” of each of these mechanisms.
Facts imply the possibility to dynamically add/delete with functions like assert and retract. In Visual/Tubro Prolog, prototypes of facts are described in a special section facts or database, while in SWI Prolog, the keyword dynamic is used for this purpose.