Editing Logic programming (section)

===Algorithm = Logic + Control===
The procedural interpretation of logic programs, which uses backward reasoning to reduce goals to subgoals, is a special case of the use of a problem-solving strategy to '''control''' the use of a declarative, '''logical''' representation of knowledge to obtain the behaviour of an '''algorithm'''. More generally, different problem-solving strategies can be applied to the same logical representation to obtain different algorithms. Alternatively, different algorithms can be obtained with a given problem-solving strategy by using different logical representations.<ref>{{cite journal|author=R.A.Kowalski|title=Algorithm=Logic + Control|journal=[[Communications of the ACM]]|volume=22| issue = 7|date=July 1979|pages=424–436|doi=10.1145/359131.359136|s2cid = 2509896|doi-access=free}}</ref>

The two main problem-solving strategies are [[backward chaining|backward reasoning]] (goal reduction) and [[forward chaining|forward reasoning]], also known as top-down and bottom-up reasoning, respectively.

In the simple case of a propositional Horn clause program and a top-level atomic goal, backward reasoning determines an [[and-or tree]], which constitutes the search space for solving the goal. The top-level goal is the root of the tree. Given any node in the tree and any clause whose head matches the node, there exists a set of child nodes corresponding to the sub-goals in the body of the clause. These child nodes are grouped together by an "and". The alternative sets of children corresponding to alternative ways of solving the node are grouped together by an "or".

Any search strategy can be used to search this space. Prolog uses a sequential, last-in-first-out, backtracking strategy, in which only one alternative and one sub-goal are considered at a time. For example, subgoals can be solved in parallel, and clauses can also be tried in parallel. The first strategy is called '''{{Visible anchor|and-parallel}}''' and the second strategy is called '''{{Visible anchor|or-parallel}}'''. Other search strategies, such as intelligent backtracking,<ref>{{cite book |last1=Bruynooghe |first1=M. |last2=Pereira |first2=L.M. |date=1984 |chapter=Deduction revision by intelligent backtracking |pages=194–215 |title=Implementations of Prolog |publisher=Ellis Horwood |location=Chichester, England}}</ref> or best-first search to find an optimal solution,<ref>{{cite conference |last=Nakamura |first=K. |date=July 1985 |title=Heuristic Prolog: logic program execution by heuristic search |conference=Conference on Logic Programming |pages=148–155 |location=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg}}</ref> are also possible.

In the more general, non-propositional case, where sub-goals can share variables, other strategies can be used, such as choosing the subgoal that is most highly instantiated or that is sufficiently instantiated so that only one procedure applies.<ref>{{cite journal |last1=Genesereth |first1=M.R. |last2=Ginsberg |first2=M.L. |date=1985 |title=Logic programming |journal=[[Communications of the ACM]] |volume=28 |issue=9 |pages=933–941|doi=10.1145/4284.4287 |s2cid=15527861 |doi-access=free }}</ref> Such strategies are used, for example, in [[concurrent logic programming]].

In most cases, backward reasoning from a query or goal is more efficient than forward reasoning. But sometimes with Datalog and Answer Set Programming, there may be no query that is separate from the set of clauses as a whole, and then generating all the facts that can be derived from the clauses is a sensible problem-solving strategy. Here is another example, where forward reasoning beats backward reasoning in a more conventional computation task, where the goal <code>?- fibonacci(n, Result)</code> is to find the n<sup>th</sup> fibonacci number:
<syntaxhighlight lang="prolog">
fibonacci(0, 0).
fibonacci(1, 1).

fibonacci(N, Result) :-
    N > 1,
    N1 is N - 1,
    N2 is N - 2,
    fibonacci(N1, F1),
    fibonacci(N2, F2),
    Result is F1 + F2.    
</syntaxhighlight>

Here the relation <code>fibonacci(N, M)</code> stands for the function <code>fibonacci(N) = M</code>, and the predicate <code>N is Expression</code> is Prolog notation for the predicate that instantiates the variable <code>N</code> to the value of <code>Expression</code>.

Given the goal of computing the fibonacci number of <code>n</code>, backward reasoning reduces the goal to the two subgoals of computing the fibonacci numbers of n-1 and n-2. It reduces the subgoal of computing the fibonacci number of n-1 to the two subgoals of computing the fibonacci numbers of n-2 and n-3, redundantly computing the fibonacci number of n-2. This process of reducing one fibonacci subgoal to two fibonacci subgoals continues until it reaches the numbers 0 and 1. Its complexity is of the order 2<sup>n</sup>. In contrast, forward reasoning generates the sequence of fibonacci numbers, starting from 0 and 1 without any recomputation, and its complexity is linear with respect to n.

Prolog cannot perform forward reasoning directly. But it can achieve the effect of forward reasoning within the context of backward reasoning by means of [[tabling]]: Subgoals are maintained in a table, along with their solutions. If a subgoal is re-encountered, it is solved directly by using the solutions already in the table, instead of re-solving the subgoals redundantly.<ref>{{cite journal |last1=Swift |first1=T. |last2=Warren |first2=D.S. |date=January 2012 |title=XSB: Extending Prolog with tabled logic programming |journal=[[Theory and Practice of Logic Programming]] |volume=12 |issue=1–2 |pages=157–187|doi=10.1017/S1471068411000500 |arxiv=1012.5123 |s2cid=6153112 }}</ref>