Node:Last Call Optimization, Next:, Previous:The Determinacy Checker, Up:Writing Efficient Programs



Last Call Optimization

Another important efficiency feature of SICStus Prolog is last call optimization. This is a space optimization technique which applies when a predicate is determinate at the point where it is about to call the last goal in the body of a clause. For example,

     % for(Int, Lower, Upper)
     % Lower and Upper should be integers such that Lower =< Upper.
     % Int should be uninstantiated; it will be bound successively on
     % backtracking to Lower, Lower+1, ... Upper.
     
     for(Int, Int, _Upper).
     for(Int, Lower, Upper) :-
             Lower < Upper,
             Next is Lower + 1,
             for(Int, Next, Upper).
     

This predicate is determinate at the point where the recursive call is about to be made, since this is the last clause and the preceding goals (<)/2 and is/2) are determinate. Thus last call optimization can be applied; effectively, the stack space being used for the current predicate call is reclaimed before the recursive call is made. This means that this predicate uses only a constant amount of space, no matter how deep the recursion.