There is more to say about Prolog than can ever be said. At the same time, you also need to collect your own experiences with the language, and ponder certain aspects for yourself. Here are a few

For example, consider again

list_list_together([], Bs, Bs). list_list_together([A|As], Bs, [A|Cs]) :- list_list_together(As, Bs, Cs).It is easy to see that

(defun append (x y) (if x (This version ofcons(car x) (append (cdr x) y)) y))

It is somewhat remarkable that such a basic function is

In Prolog, many more predicates are

However, take into account that many Prolog programs are

For example, let us define the relation

list_element_rest([L|Ls], L, Ls). list_element_rest([L|Ls0], E, [L|Ls]) :- list_element_rest(Ls0, E, Ls).

- The relation quite obviously holds for the
list
`[L|Ls]`, its*first*element`L`, and the remainder`Ls`. *If*the relation holds for the list`Ls0`, one of its elements*E*, and the remainder`Ls`,*then*the relation also holds for`[L|Ls0]`and`E`, and the remainder`[L|Ls]`. This rule is clearly*tail recursive*, because the recursive call is its only goal.

This predicate is quite versatile. Operationally, we can use it to

?- list_element_rest([a,b], E, Rest). E = a, Rest = [b] ; E = b, Rest = [a] ; false.And also:

?- list_element_rest(Ls, c, [a,b]). Ls = [c, a, b] ; Ls = [a, c, b] ; Ls = [a, b, c] ; false.In the Prologue for Prolog draft and several Prolog systems, an almost identical predicate is available under the name

Using

list_permutation1([], []). list_permutation1(Ls, [E|Ps]) :- list_element_rest(Ls, E, Rs),Note that that this predicate islist_permutation1(Rs, Ps).

Let us now run a few benchmarks. We generate?- list_permutation1([a,b,c], Ps).Ps = [a, b, c] ; Ps = [a, c, b] ; Ps = [b, a, c] ; Ps = [b, c, a] ; Ps = [c, a, b] ; Ps = [c, b, a] ; false.

?- L in 9..11, indomain(L), portray_clause(L), length(Ls, L),Now consider an alternative definition of this relation, which we calltime((list_permutation1(Ls,_),false)).9.% 3,322,110 inferences, 0.440 CPU in 0.457 seconds (96% CPU, 7546288 Lips)10.% 33,221,103 inferences, 4.447 CPU in 5.166 seconds (86% CPU, 7470928 Lips)11.% 365,432,136 inferences, 49.162 CPU in 58.028 seconds (85% CPU, 7433257 Lips)

list_permutation2([], []). list_permutation2([L|Ls0], Ps) :-This version islist_permutation2(Ls0, Ls), list_element_rest(Ps, L, Ls).

?- L in 9..11, indomain(L), portray_clause(L), length(Ls, L),Note that this version istime((list_permutation2(Ls,_),false)).9.% 772,005 inferences, 0.094 CPU in 0.099 seconds (94% CPU, 8252942 Lips)10.% 7,666,725 inferences, 0.922 CPU in 1.044 seconds (88% CPU, 8313976 Lips)11.% 83,871,526 inferences, 10.084 CPU in 13.271 seconds (76% CPU, 8317163 Lips)

Together with the previous section, this example illustrates that tail recursion

This is a tough truth to accept for most Prolog programmers. There always seems hope that we can somehow outsmart the system and get away with

For example, many beginners can correctly write a Prolog predicate that describes a

list([]). list([_|Ls]) :- list(Ls).This is a very general relation that works in all directions. For example:

?- list([a,b,c]). true. ?- list(Ls). Ls = [] ; Ls = [_15346] ; Ls = [_15346, _15352] . ?- list(true). false.After seeing they can actually affect the control flow of Prolog with

For example, from a quick first glance, it may appear that the two clauses are

list([]) :-A quick test case "confirms" that!. %incorrect! list([_|Ls]) :- list(Ls).

?- list([a,b,c]). true.The

In Prolog, there are

?- list(Ls). Ls = []. %Thus, instead of anincompleteness!

To truly benefit from declarative programming, stay in the pure subset. Use

In such cases, consider the following query:

?- flatten(Xs, Ys).What is a valid answer in such situations? Suppose your predicate answers as follows:

Ys = [Xs].From a declarative point of view, this answer is

?- flatten(Xs, Ys), Xs = [a]. Xs = [a], Ys = [[a]].Thus,

?- Xs = [a], flatten(Xs, Ys). Xs = Ys, Ys = [a].This means that exchanging the order of goals

Your instructor should be able to understand this fundamental declarative shortcoming if you point it out. In practice, use

From a quick first glance, this may seem very inefficient to you, because we are visiting the same solutions over and over, although we need each of them only

Now consider a search tree of depth

Let us now sum this up to calculate the total number of visits:

Now the point: This sum is asymptotically

It also shows that people usually

Note that iterative deepening requires