Here is a detailed general outline of the procedure that the Prolog interpreter runs to execute Prolog Text.

The input to this procedure is a single goalcome, say, as the body of a question . The output is an answer Yes or No to 'whether the goal is satisfiable', and, if a Yes , a substitution of terms for the variables that occur in the goal.

Basically, the interpreter satisfies goals by searching for facts and rules in the run-time database , that can be used for this purpose. A goal may get satisfied and resatisfied several times within the work on some parent goal. Every new time when a goal is to be satisfied, some part of the database gets skipped by the corresponding search, because the rules and facts in it have already been given their turn in earlier times.

To describe how this takes place precisely, it is useful to have in mind a work-state of execution. This work-state contains every goal that is , at the current point of time, subject to resatisfaction , together with a pointer into the database . This pointer separates the part of the database still subject to search from the part already processed. The work-state as a whole is a sequence of goal-and-pointer pairs. The initial work-state is the one with the single goal available and a pointer to the first item of the database.

The procedure consists of basically two kinds of steps, called forward steps and backward steps , and some control on taking them.

A forward step for a given goal corresponds to either a fact or a rule in the Prolog database with its head successfully unifiable with the goal. Performing a forward step means that:

 1. The interpreter allocates all the variables that occur in the fact or rule in question.
 2. Next it unifies the fact, or the head of the rule, if a rule is the case, with the goal, letting the variables that get substituted by this unification to be instantiated to these substitutes. Note that variables that come with the goal, and are not newly allocated, can get instantiated at this point too.
 3. If the database item that triggers the forward step is a fact, the above completes the step as a successful one. If this item happens to be a rule, the sequence of goals that are the body of the rule is processed to try to satisfy the goals themselves by applying the entire backtracking procedure on each of them, with all the instantiations so far made in effect. This is done by attaching their conjunction to the beginning of the work-state with a pointer to the first item of the database.

Performing a backward step , that is needed in case some forward steps are still needed, though made impossible by the choices of the database items to work with, is undoing the above actions, that constitute a forward step.

Now the control over forward and backward steps is as follows:

The topmost goal-and-pointer is extracted from the work-state. A forward step is made with the goal selected and the first item from the run-time database that is at the pointer position or lower, and successfully unifies with the goal. If this item happens to be a rule, its body takes the topmost position in the new work-state together with a pointer to the beginning of the run-time database, as stated above. In both cases a pointer into the database, pointing to the item just next to the one extracted, gets stored. Informally, the above are the actions taken to initiate the application of a rule, or to find an appropriate fact.

The above control step is repeated as long as possible. With the case of rules in mind, where body-goals take place in the work-state, and when having reached its top, get processed by corresponding forward steps, one can imagine how a complex goal gets processed by a series of successful forward steps.

Normally, there are also failures to satisfy a goal. The work-state represents failure as an attempt to find an item in the database to launch a forward step, when the pointer component of the topmost element of the work-state points to the very end of the database, i.e. no more choices of facts and rules are available. Then the interpreter makes a backward step by undoing the forward step for the latest successfully satisfied goal, and places it, together with the pointer into the database that was stored upon its forward step, on top of the work-state. As this pointer points just next to the run-time database item that launched that forward step, the new work-state dictates an attempt to resatisfy the same goal using the same database without the items already proven not successful.

Remark: The above can be viewed as just a case of the more general backtracking procedure as described in the literature on programming.