<div class="notebook"> <div class="nb-cell markdown" name="md1"> # Tabling for memoizing This example illustrates the value of tabling for _memoizing_. In the example below we deal with normal forward execution where the same computation is done over and over. Another scenario where memoizing plays a role is if subgoals are ordered such that backtracking and re-trying causes the same goal to be executed over and over again. First we compute Fibonacci numbers the simple way: </div> <div class="nb-cell query" data-tabled="true" name="q1"> fib(37, X). </div> <div class="nb-cell program" name="p2"> :- table fib/2. </div> <div class="nb-cell markdown" name="md2"> Next, we mery add a table/1 declaration. Note that the query below uses the program immediately above it and the _global_ program at the bottom. The table/1 directive causes the program to be transformed and evaluated using SGL resolution. </div> <div class="nb-cell query" data-tabled="true" name="q2"> fib(1000, X). </div> <div class="nb-cell program" data-background="true" name="p1"> fib(0, 1) :- !. fib(1, 1) :- !. fib(N, F) :- N > 1, N1 is N-1, N2 is N-2, fib(N1, F1), fib(N2, F2), F is F1+F2. </div> <div class="nb-cell markdown" name="md3"> ## Exercise Implement an _efficient_ version of fib/2 in plain Prolog as fastfib/2. </div> <div class="nb-cell program" name="p3"> </div> <div class="nb-cell query" name="q3"> fastfib(1000, X). </div> </div>