pds@quintus.UUCP (Peter Schachte) (02/06/88)
The following query came in the xerox newsgroup. I formulated a reply, but decided that this was a better forum for such discussions. Note that while the specific maximum recursion depth he discusses is specific to Xerox Quintus Prolog, the issues are common to most Prolog implementations. > Hello, > I have a problem with Xerox Quintus Prolog : > I cannot do DEEP recursion. > I've partitioned the disk such that I have maximum space - 65000 pages, > but cannot do deeper than 5-10000 levels of recursion on a clean > sysout. This is interpreted code, compiled code is of > magnitude 10 better. (The twoliner test program is : > addone(I, Max) :- I<Max, J is I+1, addone(J,Max). > addone(_,_). > > ?- addone(1, 10000). ) > > IS THIS A REASONABLE RESULT ?! (or are there ways around). Your biggest problem is that you're using the interpreter. As you mentioned, compiling the code allows much deeper recursion. The interpreter keeps around lots of information that compiled code does not. In fact, I'll show you here how to write code that will run without any bound on recursion depth. CORRECTNESS Actually, one problem is that your program is subtly in error. Look at the second clause for addone/2. It simply does not say what you want it to say. What you really mean is: addone(I, Max) :- I<Max, J is I+1, addone(J,Max). addone(Max,Max). (or something similar). If you rewrote your procedure to compute something, it would be clearer. Let's take the factorial/2 procedure: % factorial(+N, ?F) % F = N!. factorial(N, F) :- N>0, N1 is N-1, factorial(N1, E), F is E*N. factorial(_, 1). This is written to parallel your example. If you type this in and try it, you'll see that it will indeed compute the factorial of a number, but it will also return all sorts of wrong answers: | ?- factorial(3, X). X = 6; X = 6; X = 3; X = 1; no This is because the second clause is wrong. What we really want is: % factorial(+N, ?F) % F = N!. factorial(N, F) :- N>0, N1 is N-1, factorial(N1, E), F is E*N. factorial(0, 1). EFFICIENCY: CHOICEPOINTS This fixes that problem; the code is now correct. But there is an efficiency problem: as this code is written, Prolog doesn't know that the second clause won't succeed until it gets to it. In the mean time, Prolog maintains a CHOICEPOINT, containing enough information to allow it to try the second clause if something fails. And it must keep the choicepoint until something fails, or until we force Prolog to look for another solution by typing ';' when it prints a solution. This choicepoint takes time to build, and time to destroy, but even worse, it takes space. One unneeded choicepoint is no big deal, but one left behind for every recursive call could be. Another important point: a choicepoint can last long after the procedure call that created it returns. That's necessary for backtracking to work properly. But it does mean that choicepoints can accumulate and drown an application. This is one of the most common efficiency problems in novice Prolog code, and it is usually easy to avoid! (This, of course, is not to say that procedures should never leave choicepoints. If you want your procedure to backtrack, by all means leave choicepoints. But try to avoid them when you don't want them.) So we've suppressed the wrong answers in our factorial/2 procedure, but we do leave around an unnecessary choicepoint for each recursive call. One solution to this problem is just to switch the clauses. Then we check to see if N = 1 up front, and don't have to save a choicepoint to allow us to check later. This is a perfectly good solution. % factorial(+N, ?F) % F = N!. factorial(0, 1). factorial(N, F) :- N>0, N1 is N-1, factorial(N1, E), F is E*N. A simple rule of thumb will often help: put the recursive clause last. This won't always avoid choicepoints, but it will save you from creating a choicepoint for each level of recursion. And if you call the procedure with enough information to choose between the clauses, as you usually will, you will not leave behind any choicepoints. USING IF-THEN-ELSE It's not always so easy, though. Sometimes we want to have more than one recursive clause. Sometimes we want to do some test, and based on the result of that test, choose one clause and completely rule out the other(s). For example, suppose we wanted N factorial to be 1 when N=<0. Then we might want the code to read: % factorial(+N, ?F) % F = N!. We take N!, where N =< 0, to be 1. factorial(N, 1) :- N=<0. factorial(N, F) :- N>0, N1 is N-1, factorial(N1, E), F is E*N. Notice that the first clause checks N=<0, so we can drop the N>0 test in the second clause, right? Nope. Each clause must be a true statement about the relation you're defining (unless you're using cuts (!), which you don't need to do, and I won't discuss here). The N>0 is a necessary part of the second clause. The clause is just not a true statement about factorial without it. Actually, it's an infinite loop without it. There IS a way to avoid redundant testing, though. What we want is to check if N=<0 once, and if so, do the rest of the first clause, otherwise do the body of the second clause. In a procedural language, we would use an "if...then...else" construct. We do the same in Prolog, only the syntax is a little different. We would code it as: % factorial(+N, ?F) % F = N!. We take N!, where N =< 0, to be 1. factorial(N, F) :- ( N=<0 -> F is 1 ; N1 is N-1, factorial(N1, F1), F is F1*N ). Now we only compare N with 0 once. Furthermore, this code won't create a choicepoint when it runs. It wouldn't even if you switched the then and else part (and the sense of the test). Prolog's if-then-else commits you to either the then or the else part, depending on the result of the test, without the ability to try the other later. That's just what we want here. EFFICIENCY: TAIL RECURSION But we can't run this without bound yet. The trouble is that it is not tail-recursive. A tail-recursive procedure is one whose last action is to call itself. In this case what we do last is a multiplication. This means that while we're off computing a recursive factorial, we have to remember that we're going to have to come back to do the multiplication later. This takes stack space. The solution is to rearrange the code to do the multiplication before we call factorial/2 recursively. But how can we multiply by a number we haven't computed yet? We introduce an accumulating parameter. This means that we introduce another argument to factorial/2 to hold the partial solution. In other words, we compute the multiplications on the way "down," rather than on the way "back up." Here is the code: % factorial(+N, ?F) % F = N!. We take N!, where N =< 0, to be 1. factorial(N, F) :- factorial(N, 1, F). % factorial(+N, +A, ?F) % F = A*N! factorial(N, A, F) :- ( N=<0 -> F is A ; N1 is N-1, A1 is A*N, factorial(N1, A1, F) ). This code is approximately optimal. However, compiling it and trying to test that the recursion depth is unbounded will prove rather frustrating. Factorial grows much too fast. Most Prologs do not handle integers larger than some small number of bits (28-32). (Xerox Quintus Prolog does, but at a tremendous cost in performance.) So here is your program written to be tail recursive and determinate (not create any choicepoints): addone(I, Max) :- ( I>=Max -> true ; J is I+1, addone(J, Max) ). This code, compiled, will run without any depth bound on recursion. Two more points. In none of these examples did we have to compare a number for equality. When you DO want to do this in an if-then-else, use =:=/2, rather than =/2. =:=/2 allows the compiler to generate better code when comparing numbers. INDEXING The second point that did not come up is indexing. This is very important. Indexing is even better than if-then-else, when it is applicable. If you can list all the possible first arguments to a predicate, indexing is for you. For example, a table of names and ages: age(bill, 30). age(tony, 17). age(walt, 72). If you call age(tony, X), Prolog will immediately go to the second clause, without trying the first, and without leaving a choicepoint indicating that it should try the third. This is more important in tail-recursive procedures, for example: append([], Y, Y). append([U|X], Y, [U|Z]) :- append(X, Y, Z). In both of these clauses, at least the "outer layer" of the structure of the first argument is specified, and different, and so can be distinguished by indexing. And in the recursive clause, the recursive call to append/3 is the last (and only) call, so it's tail recursive. Therefore, when the first argument of a call to append/3 is a proper list, append/3 is very efficient. WRAP-UP There are plenty more efficiency issues, but this is enough to get you started. Good luck. And don't forget to use statistics when in doubt. Do | ?- statistics, some_goal, statistics. and compare local stack space before and after some_goal. If it grows, you're leaving choicepoints around. That may be what you want. But often it's not. -- -Peter Schachte pds@quintus.uucp ...!sun!quintus!pds