Status of mode directed tabling, especially min/max

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

I am adding it to Useful Prolog references. As the page is a wiki you can edit also. :smiley:

2 Likes

As version 8.1.14 has arrived, I can now confirm that all the examples above - except euler14 - works as expected.

Thanks for the fix @jan .

1 Like

Looking at euler14.pl, we see

:- 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).

Now, my docs tell me that - means keep the first answer and max keep the largest answer, which makes SWI-Prolog’s answer [2,525] correct. If you want to keep the witness that belongs to the max, the values must be combined. The following works:

euler14 :-
    max_chain(Max),
    Max = ch(N,_Chain,Len),
    writeln([n=N,len=Len]).

:- table max_chain(lattice(max)).
max_chain(ch(N,Chain,Len)) :-
        between(2,999999,N),
%       between(2,9,N),
        gen(N,Chain,Len).

max(Current, New, Max) :-
        arg(3, Current, Len1),
        arg(3, New, Len2),
        (   Len2 > Len1
        ->  Max = New
        ;   Max = Current
        ).

It is slow though (55 sec) and uses a lot of memory (13Gb), for a large part to store all the chains in the gen/3 tables. If you change that to gen/2 you get the result in 15 sec with 2,5Gb mem usage.

1 Like

Thanks @jan for the suggestions.

The version you copied in the reply give correct result now (and is slow: 33s on my fastest machine). That’s great.

However, you indicated that skipping the Chain argument was faster. It’s surely faster (~20s), but don’t give the correct result: it yield [n=3,len=8] instead of [n=837799,len=525]. Here’s my version of it. It’s kind of strange since Chain should be relevant, it’s only N and Len that is needed. Probably I’ve missed some important change…

euler14xxx :-
        abolish_all_tables,
        max_chain(Max),
        Max = ch(N,Len),
        writeln([n=N,len=Len]).

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

max(Current, New, Max) :-
        arg(3, Current, Len1),
        arg(3, New, Len2),
        (   Len2 > Len1
        ->  Max = New
        ;   Max = Current
        ).

:- table gen(+,-).
gen(1,Len) :-
        !, 
        Len = 1.
gen(N,Len) :-
        N > 1,
        N mod 2 =:= 0, %% !,
        Ndiv2 is N div 2,
        gen(Ndiv2,Len1),
        Len is Len1+1.
gen(N,Len) :-
        N > 1,
        N mod 2 =:= 1, %%  !,
        T3N1 is 3*N+1,
        gen(T3N1,Len1),
        Len is Len1+1.

It give the following result:

[n=3,len=8]
% 80,777,613 inferences, 18.757 CPU in 20.154 seconds (93% CPU, 4306438 Lips)

Do you have an idea where I did wrong?

(An aside: Skipping the Chain argument in my Picat version shaved the time from 1.2s to 0.7s which is quite significant. Thanks for the idea!)

This should (now) be arg(2, ... :slight_smile:

What I do not like about this is that if you want to get the chain you need to write both versions of gen, one to find the N with the longest chain and gen/3 to find the actual chain (I guess that is fine without tabling).

I also start to understand the discussion between what is called answer subsumption in XSB and mode directed tabling in B/Yap :slight_smile:

@jan Thanks! (And: Of course! :slight_smile:

This now takes 11.3s (from 34s),

For this specific problem we don’t really need the Chain itself, but I do see your point.

It will be interesting to follow further development of tabling.