Status of mode directed tabling, especially min/max

I’m using: SWI-Prolog version 8.1.13 (Linux Ubuntu 18.04LTS)

I wander about the status of mode directed tabling is, especially the min/max modes.

Here is a simple example where tabling make the predicate just fail. The result should be 206 (103+103). But perhaps I don’t correctly understand how mode directed tabling works in SWI-Prolog.

go :-
        abolish_all_tables,
        L1 = [1,2,3,5,98,3,103,4,4,21],

        % -> false
        test1(L1,L1, Val1),
        nl.

%%
%% Don't work as expected:
%% ->  false
%% Should be 206.
%%
:- table test1(+,+,max).
test1(L,L2, Val) :-
        member(Val1,L),
        member(Val2,L2),
        Val is Val1+Val2.

Here are two more “serious” examples (i.e. Project Euler problems) where mode tabling with max/min give wrong answer or fails :

  • http://hakank.org/swi_prolog/euler14.pl
    The failing predicate is euler14xxx/0 which give the correct length of the longest Collatz cycle (525), but the number (N) that yield this longest cycle is not correct. It should be 837799, but seems to output the first number in the between/3 generated list of N’s (2).

  • http://hakank.org/swi_prolog/euler18.pl
    The failing predicate is euler18xxx which just fails when using the min mode.

Note: These programs use these modules:

[Both these tabling programs are ported from my Picat program. Picat is based on the B-Prolog engine and works - what I understand - as in B-Prolog. They where inspired by/copied from code by Neng-Fa Zhou.]

3 Likes

Turns out to be a bug in trie_gen/2,3. I start to understand what is wrong, but I fear it will keep me busy for a little while to understand it fully.

As a whole, mode directed tabling has fallen behind compared to normal tabling. The test set is fairly small and while there have been a lot of changes to the tables to improve the classical tabling, the code for mode directed tabling is updated minimally and without an extensive test set easily leads to regression.

When the normal tabling code becomes stable the plan is to fully synchronize the code for mode directed tabling. Until then, performance and memory usage are way worse than normal tabling and some regression is to be expected.

I’ll fix this, add this to the test cases and keep you posted. Thanks for the small and clear test.

2 Likes

Thanks, Jan.

It’s good to know that it should work.

/Hakan

Pushed 511594ae56c7ef35de1263f698ea4b73a6419f73, which fixes both.

3 Likes

@j4n_bur53. The two Euler problems mentioned above (#14 and #18) are ported to B-Prolog with the same result (and almost as fast) as the Picat versions.

http://hakank.org/bprolog/euler14.pl
http://hakank.org/bprolog/euler18.pl

I’m not sure that I understand all your questions, but I’ll give it a try. Sorry for the long post (and I hope that it’s not off-topic for the forum).

Let’s start with euler14.pl (http://hakank.org/bprolog/euler14.pl )

%%
%% From
%% http://hakank.org/picat/euler14.pi
%% which is slightly adjusted from
%% http://picat-lang.org/euler/p14.pi
%% 
%% All numbers 2..999999: 1.4s
%% Odd numbers: 3..2..999999: 1.3s
%% (My Picat version using odd numbers takes ~ 1.2s)
%%
euler14 :-
    max_chain(N,_Chain,Len),
    writeln([n=N,len=Len]).

:- table max_chain(-,-,max).
max_chain(N,Chain,Len) :-
        between(2,999999,N),  % checking all numbers        
        % between(3,2,999999,N),  % just checking the odd numbers
        gen(N,Chain,Len).

:- table gen(+,-,-).
gen(1,Chain,Len) :-
        Chain=[1],
        Len is 1.

gen(N,Chain,Len)  :-
        N > 1,
        N mod 2 =:= 0,
        T is N div 2,
        gen(T,Chain1,Len1),
        Chain=[N|Chain1],
        Len is Len1+1.

gen(N,Chain,Len) :-
        N > 1,
        N mod 2 =:= 1,
        T is 3*N+1,
        gen(T,Chain1,Len1),
        Chain=[N|Chain1],
        Len is Len1+1.
    
between(From,Step,To,N) :-
        To2 is To div Step,
        between(From,To2,Tmp),
        N is (Tmp-From)*Step+From.

If the first table is commented out, i.e.
:- table max_chain(-,-,max).
then there’s no generation at all of the numbers: it just handle N=2 (the first number) and then stops. I.e. it acts as a kind of generator. I’m not sure how to consider this case.

The second tabling:

:- table gen(+,-,-).

is just for caching the previous results. Commenting it out give the correct answer but takes a very long time (116s vs 1.5s).

Here’s the second example, euler18.pl (http://hakank.org/bprolog/euler18.pl )

euler18 :-
        p18(Tri),
        pp(1,1,Tri,Sum),
        writeln(max_val=Sum).

p18(Triangle) :- 
        Triangle  = [[75],
                     [95,64],
                     [17,47,82],
                     [18,35,87,10],
                     [20, 4,82,47,65],
                     [19, 1,23,75, 3,34],
                     [88, 2,77,73, 7,63,67],
                     [99,65, 4,28, 6,16,70,92],
                     [41,41,26,56,83,40,80,70,33],
                     [41,48,72,33,47,32,37,16,94,29],
                     [53,71,44,65,25,43,91,52,97,51,14],
                     [70,11,33,28,77,73,17,78,39,68,17,57],
                     [91,71,52,38,17,14,91,43,58,50,27,29,48],
                     [63,66, 4,68,89,53,67,30,73,16,69,87,40,31],
                     [ 4,62,98,27,23, 9,70,98,73,93,38,53,60, 4,23]].

%%
%% From Neng-Fa Zhou.
%%
:- table pp(+,+,+,max).
pp(Row,_Column,Tri,Sum) :-
        length(Tri,Len),
        Row > Len,
        Sum is 0.
pp(Row,Column,Tri,Sum) :-
        length(Tri,Len),
        Row =< Len,
        Row1 is Row+1,
        pp(Row1,Column,Tri,Sum1),
        matrix_element(Tri,Row,Column,TriRC),
        Sum is Sum1 + TriRC.

pp(Row,Column,Tri,Sum) :-
        length(Tri,Len),
        Row =< Len,
        Row1 is Row + 1, 
        Column1 is Column + 1,
        pp(Row1,Column1,Tri,Sum1),
        matrix_element(Tri,Row,Column,TriRC),        
        Sum is Sum1 + TriRC.    

matrix_element(X, I, J, Val) :-
        nth1(I, X, Row),
        nth1(J, Row, Val).

If the table statement

:- table pp(+,+,+,max).

is commented out, the program don’t loop through the complete matrix, just a single pass of each line and then stops with an incorrect answer (the last). So it acts as a generator as well.

Does this answer any of your questions?

After your comments, I realize that these two examples might not work in SWI-Prolog even after Jan W have fixed the found tabling bug. They might just work in B-Prolog/Picat land.
(Neng-Fa has written some other B-Prolog programs with tabling using min/max: http://www.picat-lang.org/bprolog/examples/#TAB , but I have not analyzed them. )

2 Likes

Possibly need to try what works. I think SWI-Prolog has a daily build page for Windows here. So those that have a Windows machine, and dont’t build on their own, can test fixes in about 24 hours.

https://www.swi-prolog.org/download/daily/bin/

I have now tested the B-Prolog tabling examples from http://www.picat-lang.org/bprolog/examples/#TAB in SWI-Prolog . The result is mixed: some works and some don’t work/yield errors.

Below is the full list. For most of the programs I had to slightly edit the B-Prolog programs, e.g. skipping user input and change the timing statistics. Note that I’m not sure if this comparison is really that useful since it seems that the tabling in B-Prolog is not (exactly ) the same as in SWI-Prolog.

  • ackerman.pl
    :- table a/3.
    http://hakank.org/swi_prolog/ackermann2.pl
    Works as expected.

  • farmer.pl
    :-table plan(+,-,min).
    http://hakank.org/swi_prolog/farmer2.pl
    works as expected.

  • fib.pl
    :- table fib/2.
    http://hakank.org/swi_prolog/fib.pl
    works as expected.

  • knapsack.pl
    :- table knapsack(+, +, max).
    http://hakank.org/swi_prolog/knapsack2.pl
    This does not work as expected:
    $ swipl knapsack2.pl
    ?- make,go.
    % 8,796,210 inferences, 1.166 CPU in 1.166 seconds (100% CPU, 7542280 Lips)
    false.

    Expected output:

    There is a solution for this knapsack problem
    The maximal number of items is 93
    
  • lcs.pl
    :- table lcs(+,+,max).
    http://hakank.org/swi_prolog/lcs.pl

    This does not work as expected.
    $ swipl lcs.pl
    ?- make,go.

    SWI-Prolog [thread 1 (main) at Sat Sep  7 07:52:54 2019]: received fatal signal 11 (segv)
    C-stack trace labeled "crash":
    [0] PL_strtod() at ??:? [0x7f1cc647c88b]
    [1] bstore_print_backtrace_named() at ??:? [0x7f1cc647ca4e]
    [2] bstore_print_backtrace_named() at ??:? [0x7f1cc647cb41]
    [3] PL_get_signum_ex() at ??:? [0x7f1cc64104da]
    [4] killpg() at ??:? [0x7f1cc5fbff20]
    [5] add_choice() at ??:? [0x7f1cc6449723]
    [6] add_choice() at ??:? [0x7f1cc6449e05]
    [7] add_choice() at ??:? [0x7f1cc644a0fd]
    [8] PL_next_solution() at ??:? [0x7f1cc63ada19]
    [9] pl_skip_list3_va() at ??:? [0x7f1cc63f64b0]
    [10] pl_skip_list3_va() at ??:? [0x7f1cc63f6d5b]
    [11] PL_toplevel() at ??:? [0x7f1cc63a68dd]
    [12] swipl(+0x735) [0x55e081679735]
    [13] __libc_start_main() at /build/glibc-OTsEL5/glibc-2.27/csu/../csu/libc-start.c:344 [0x7f1cc5fa2b97]
    [14] swipl(+0x77a) [0x55e08167977a]
    Running on_halt hooks with status 139
    

    Expected result:

    The length of the longest common subsequence is 79
    
  • matrix.pl
    :- table sc(+,min,-,-).
    http://hakank.org/swi_prolog/matrix.pl

    This does not work as expected.
    $ swipl matrix.pl
    ?- go.

    ERROR: Uninstantiated argument expected, found 50
    

    Expected output:

    Scalar Multiplication is 889137
    

    If this is used instead
    :- table sc(+,min,+,+).
    then there’s no error, but the result is simply false.

  • obst.pl
    :- table obst(+, min, -).
    http://hakank.org/swi_prolog/obst.pl

    This does not work as expected.
    $ swipl obst.pl
    ?- go.

  SWI-Prolog [thread 1 (main) at Sat Sep  7 08:05:01 2019]: received fatal signal 11 (segv)
  C-stack trace labeled 'crash':
  [0] PL_strtod() at ??:? [0x7f4a276a388b]
  [1] bstore_print_backtrace_named() at ??:? [0x7f4a276a3a4e]
  [2] bstore_print_backtrace_named() at ??:? [0x7f4a276a3b41]
  [3] PL_get_signum_ex() at ??:? [0x7f4a276374da]
  [4] killpg() at ??:? [0x7f4a271e6f20]
  [5] add_choice() at ??:? [0x7f4a27670723]
  [6] add_choice() at ??:? [0x7f4a27670e05]
  [7] add_choice() at ??:? [0x7f4a276710fd]
  [8] PL_next_solution() at ??:? [0x7f4a275d4a19]
  [9] pl_skip_list3_va() at ??:? [0x7f4a2761d4b0]
  [10] pl_skip_list3_va() at ??:? [0x7f4a2761dd5b]
  [11] PL_toplevel() at ??:? [0x7f4a275cd8dd]
  [12] swipl(+0x735) [0x55ded34de735]
  [13] __libc_start_main() at /build/glibc-OTsEL5/glibc-2.27/csu/../csu/libc-start.c:344 [0x7f4a271c9b97]
  [14] swipl(+0x77a) [0x55ded34de77a]
  Running on_halt hooks with status 13.

Expected output:

Optimal value is 4379

When Jan W has fixed the table bug mentioned earlier in this thread, I’ll be happy to re-test these programs.

Ah. I just saw that the bug was fixed a “long” time ago. I’ll check it out again as soon as possible.

This might be part of the puzzle. According to my docs, - says first answer. Now, gen/3 is recursive. I cannot tell easily whether it calls a variant of itself, but if it does the tabling suspension mechanism kicks in and the order is pretty much undefined. Tabled execution using using - and otherwise ground arguments could use early completion optimization, i.e., stop after the first answer. SWI-Prolog does this for normal tabling of ground sub goals, but not for this case (yet).

Its a nice example illustrating the need for and the opportunities to implement a few optimizations :slight_smile: Whether or not the program is correct, I cannot tell.

Unfortunately, I couldn’t compile the Git version (problem with ODBC), but testing with the Windows nightly build (swipl-w64-2019-09-07.exe) worked quite well.

Summary: All problems with the B-Prolog programs are fixed in the nightly build. For matrix.pl one have to change the tabling to:
:- table sc(+,min,+,+).

Euler problem 18 works as well.

That’s really great!

The only problem left is Euler 14 (http://hakank.org/swi_prolog/euler14.pl ) which give the same error ([n=2,len=525] instead of [n=837799,len=525]).
It seems that the jury is still out if this should work in SWI-Prolog.

3 Likes

In theory it should drop building the ODBC interface if it cannot configure it. Which platform and which ODBC version is installed? Still, you can use CMAKE -DSWIPL_PACKAGES_ODBC=OFF and it should drop trying to build the odbc, even if the requirements seems present.

Interesting list of programs at http://hakank.org/swi_prolog/!

2 Likes

This link is dead :frowning:

For me (on linux,version 8.1.13-21-ga03215660 ), one still has problems:

  • matrix.pl:
1 ?- go.
% 22 inferences, 0.000 CPU in 0.000 seconds (99% CPU, 764818 Lips)
ERROR: Uninstantiated argument expected, found 50
  • All the others work fine including euler14:
3 ?- go.
euler14a: [n=837799,len=525]
% 78,128,905 inferences, 24.553 CPU in 25.455 seconds (96% CPU, 3182057 Lips)

euler14b: [837799,525]
% 78,129,412 inferences, 24.914 CPU in 25.899 seconds (96% CPU, 3135921 Lips)

true.

Thanks Jan for such a great work!!

This has been discussed when answer subsumption was added to SWI. The conclusion was that calling a tabled predicate with an instantiated argument in the location of an argument for which answer subsumption applies should be an error. I don’t have all arguments in my head anymore.

I do get the correct answer for both SWI and XSB using table sc(_,po((<)/2),_,_).

Thanks for the tip about compiling. And your kind words.

Sorry about the broken link. http://hakank.org/swi_prolog/ackermann2.pl is now fixed.

Regarding “matrix.pl”, did you change the tabling to
:- table sc(+,min,+,+).

I’ve updated the program at my webpage with this tabling: http://hakank.org/swi_prolog/matrix.pl

In “euler14.pl”, the problematic predicate is euler14xxx. The other two predicate that you tested use the simple (and unproblematic) tabling :- table collLength/2..

Great, thanks, that makes sense!

Thanks hakank, I get the same results as you do now.

As Jan mentioned, that is quite a nice collection of programs you have there! Thanks for sharing g it!

1 Like

@swi Thanks!

As for now I’ve just ported some of my Picat CLPFD programs just to learn SWI-Prolog (especially how to solve the problems without foreach loops/list comprehensions/indexing/re-assignments etc). The real plan is to the more unique/cool stuff in SWI-Prolog. And hopefully to do some GOFAI as well. (Right now, I’m struggling with some Project Euler problems as you might have guessed.)

Note to others: The page we are talking about is “My SWI-Prolog page”: http://hakank.org/swi_prolog/ .

1 Like