Tabling and memoization across answers

Help!
1

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.

From the 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 :slight_smile:

2

Solved, I’m not sure what was happening before, probably something in the way the predicate was loaded. As soon that was fixed, I got warnings for my use of attributed variables, removed them and now everything works as intended. :slight_smile:

1 Like
3

Although it’s not documented, I think that tabling and attributed variables (which is what CLP(FD) uses) don’t play well together. I’m guessing that you removed the use of predicates such as (#=)/2 , to get things to work?

1 Like