I’m having problem understanding how tabling could memoize a predicate: here’s
an example from 2022 advent of code (problem 8):
mat([[3,0,3,7,3], [2,5,5,1,2], [6,5,3,3,2], [3,3,5,4,9], [3,5,3,9,0]]). at(Mat, X-Y, Elem) :- length(Mat, Len), [X, Y] ins 1..Len, nth1(Y, Mat, Row), nth1(X, Row, Elem). upper_shadow(Mat, X-1, 0) :- length(Mat, Len), X in 1..Len. upper_shadow(Mat, X-Y, N) :- length(Mat, Len), [X, Y] ins 1..Len, Y #> 1, Y1 #= Y - 1, upper_shadow(Mat, X-Y1, N1), at(Mat, X-Y1, C), N #= max(N1, C), format('~w-~w~n', [X, Y]). % ?- mat(Mat), upper_shadow(Mat, X-Y, Shadow), false.
format statement, I can see that the predicate upper_shadow is called many times with the same arguments. In the effort of getting some memoization, I tried including a number of tabling directive (with and without subsumption), but I couldn’t get the memoization properties I want.
My questions are:
- How can I memoize this efficiently with tabling?
- How should I think about tabling from an operational semantic viewpoint?
- Are there ways of inspecting the tables?
any insight is appreciated