Fibonacci numbers in Prolog

Example for versions Poplog 15.5 (Prolog)

Straightforward recursive implementation is too memory inefficient to be executed in Poplog, so this example shows a more advanced technique — recursion with memoization. An additional predicate memo(Goal) is defined so that the first time Goal is evaluated, the result of its evaluation is added to facts database, and next time it is questioned, it is not re-evaluated but taken as a known fact.

After this predicate fib(N,F) is defined recursively, but each call to fib is wrapped in memo, so for each value of N fib(N,F) is evaluated only once. With such approach printing calculated numbers can be done immediately after their calculation, without extra loop. 

% fibonacci.pl
:- dynamic(stored/1).

memo(Goal) :-
    stored(Goal) -> true;
    Goal, assertz(stored(Goal)).

fib(1,1) :- !, write('1, ').
fib(2,1) :- !, write('1, ').
fib(N,F) :-
    N1 is N-1, memo(fib(N1,F1)), 
    N2 is N-2, memo(fib(N2,F2)), 
    F is F1 + F2,
    write(F), write(', ').

% interactive
[-fibonacci].
fib(16,X), write('...'), nl.