Accumulators, Tail Recursion & Difference Lists

Last-call optimization (LCO): when the recursive call is the last goal and no choice points remain, Prolog reuses the stack frame → constant stack space.

23.1 Accumulators

Last-call optimization (LCO): when the recursive call is the last goal and no choice points remain, Prolog reuses the stack frame → constant stack space.

% Non-tail-recursive
len([], 0).
len([_|T], N) :- len(T, N0), N is N0 + 1.

% Tail-recursive with accumulator
len2(L, N) :- len_acc(L, 0, N).
len_acc([], N, N).
len_acc([_|T], N0, N) :- N1 is N0 + 1, len_acc(T, N1, N).

23.2 Difference lists

A list represented as a pair List-Tail (or two arguments) where Tail is an unbound variable; allows O(1) append.

DCGs are syntactic sugar for difference lists.

% [a, b, c | T] - T represents [a, b, c]
dl_append(A-B, B-C, A-C).

?- dl_append([1, 2|T1]-T1, [3, 4|T2]-T2, R-[]).   % R = [1, 2, 3, 4]

% O(n) flatten / tree-to-list using difference lists
tree_list(nil, L, L).
tree_list(t(Left, V, Right), L0, L) :-
    tree_list(Left, L0, [V|L1]),
    tree_list(Right, L1, L).

?- tree_list(t(t(nil, 1, nil), 2, t(nil, 3, nil)), L, []).   % L = [1, 2, 3]

23.3 Queues with difference lists

empty_queue(Q-Q).
enqueue(X, Q-[X|T], Q-T).
dequeue(X, [X|Q]-T, Q-T).