fib(2000,F). A very short and very personal note

[haijinSk]

“[T]hat is why I am a mathematician, I hate numbers.” in The Story of COMAL [a programming language] told by Børge Christensen

Not a mathematician, but I know something about hating numbers and yet seeing something very interesting, important and beautiful in things like category theory.

Today, in my computer, I found a file fib.pl with this text:

:- use_module(library(tabling)).
:- table fib/2.

fib(0, 0).
fib(1, 1).
fib(N, F) :- 
  N #> 1,
  N1 #= N - 1,
  N2 #= N - 2,
  fib(N1, F1),
  fib(N2, F2),
  F #= F1 + F2.

/*
?- fib(2000,F).
   F = 4224696333392304878706725602341482782579852840250681098010280137314308584370130707224123599639141511088446087538909603607640194711643596029271983312598737326253555802606991585915229492453904998722256795316982874482472992263901833716778060607011615497886719879858311468870876264597369086722884023654422295243347964480139515349562972087652656069529806499841977448720155612802665404554171717881930324025204312082516817125
;  ... .
*/

I fell in love with a modern Prolog, and especially with Scryer, because of https://github.com/triska/the-power-of-prolog

Because of pio and clpz library. Because of definite clause grammars; dif/2 & the bi-directional company…

Because strings are lists of characters, not numbers. Because Scryer was fast and memory consumption great (small) in context of my own (strings/text) computations. Because I’m a naive programmer: almost a non-programmer, and Scryer was so friendly to me.

And when I learned about tabling, I loved Scryer even more. fib(2000,F). The love letter. The F as 418 numbers/characters I loved.

Sometimes, I want to go back, to the future.

[infradig]

I tend to be skeptical of tabling and that's why I haven't put much effort into it. Maybe because all the promotional examples i've seen just take naively written Prolog and make it seemingly efficient, whereas a better implementation in Prolog will be even faster.

For example naive Finonacci:

fib(0,0) :- !.
fib(1,1) :- !.
fib(N,R) :-
    N1 is N - 1,
    N2 is N1 - 1,
    fib(N1,R1),
    fib(N2,R2),
    R is R1 + R2.

... don't even bother trying to run fib(2000,F) with it.

vs. well written:

fib(0,0) :- !.
fib(A,B) :-
    fib_(A,0,1,B).

fib_(1,_,A,A).
fib_(A,B,C,D) :-
    A > 1,
    E is A-1,
    F is B+C,
    fib_(E,C,F,D).

?- time(fib(2000,F)).
   % CPU time: 0.008s, 10_031 inferences
   F = 4224696333392304878706725602341482782579852840250681098010280137314308584370130707224123599639141511088446087538909603607640194711643596029271983312598737326253555802606991585915229492453904998722256795316982874482472992263901833716778060607011615497886719879858311468870876264597369086722884023654422295243347964480139515349562972087652656069529806499841977448720155612802665404554171717881930324025204312082516817125

which is much faster than the tabled version (about 10s on my machine).

Maybe there are compelling use-cases for tabling though.

[haijinSk]

Thank you very much for you response.

Personally, I care about DCGs and text/string/list computations more than about numbers (but I want constraint programming with numbers). As I understand it, or as I want to see it, tabling means more declarative or simpler code (the future, so to speak), with numbers (like the Fibonacci "explosive" computation) or grammars, at least in some cases where memory helps.

I wanted to express my nostalgia. With a computationally naive, but mathematically correct version of the definition, I can't do fib(2000,F). anymore. Tabling in Scryer doesn't work (as it worked before).

Thank you. And thank you very much for your great Trealla Prolog. I love Trealla too.

[haijinSk]

So, I did some "software archaeology", I compiled "Feb 29, 2024" v0.9.4 from the Releases:

https://github.com/mthom/scryer-prolog/archive/refs/tags/v0.9.4.zip

And with "my" naive, but tabled version, I have my futuristic number back:

?- time(fib(2000,F)).
   % CPU time: 7.557s, 9_858_065 inferences
   F = 4224696333392304878706725602341482782579852840250681098010280137314308584370130707224123599639141511088446087538909603607640194711643596029271983312598737326253555802606991585915229492453904998722256795316982874482472992263901833716778060607011615497886719879858311468870876264597369086722884023654422295243347964480139515349562972087652656069529806499841977448720155612802665404554171717881930324025204312082516817125
;  ... .

I hate numbers, and it's not 0.008 s, but with a naive Fibonacci program, isn't it beautiful, in itself? :-)

[haijinSk]

And, for example, using a naive Fibonacci definition in/with Racket:

#lang datalog

fib(0, 0).
fib(1, 1).
fib(N, F) :- 
  N != 1,
  N != 0,
  N1 :- -(N, 1),
  N2 :- -(N, 2),
  fib(N1, F1),
  fib(N2, F2),
  F :- +(F1, F2).

fib(2000, F)?

$ time racket fib-racket.rkt
fib(2000, 4224696333392304878706725602341482782579852840250681098010280137314308584370130707224123599639141511088446087538909603607640194711643596029271983312598737326253555802606991585915229492453904998722256795316982874482472992263901833716778060607011615497886719879858311468870876264597369086722884023654422295243347964480139515349562972087652656069529806499841977448720155612802665404554171717881930324025204312082516817125).

real	0m1,633s
user	0m1,436s
sys	0m0,198s

As I see it, provocatively, of course, there is some future for more declarative/direct definitions; in Prolog, or elsewhere.

[haijinSk]

Oh, mea culpa... at least for fib(2000,F). and in one direction, I don't need any 2024 "software archaeology", it works with master. It doesn't work with (now e282ee9) rebis-dev :

?- fib(2,F).

thread 'main' panicked at src/machine/copier.rs:456:17:
internal error: entered unreachable code
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

And with fib(2000,F). , before panicking, it will consume RAM, like 0.5 GB per second.

But, I'm not saying that tabling with master works as one would expect; it doesn't: #2701

[infradig]

What's the secret sauce with Datalog, auto-memoization?

[haijinSk]

Yes: "[...] The use of Datalog syntax and an implementation based on tabling intermediate results ensures that all queries terminate."

https://docs.racket-lang.org/datalog/index.html

[haijinSk]

With an example from here:

https://github.com/dtonhofer/prolog_notes/blob/master/swipl_notes/about_continuations/README.md#correct-switching-using-tail-recursion-to-generate-new-reset-points

Where I changed(Cont == 0)to (Cont == none) and middle(Cont) to ( Cont = cont(C), middle(C) ).

:- use_module(library(cont)).

go :- middle(lower([a,b])).

middle(Goal) :-
   reset(Goal,A,Cont),
   format("Back in middle with A = ~q\n",[A]),
   ((Cont == none) -> true ; ( Cont = cont(C), middle(C))).

lower([X|Xs]) :-
   format("Sending ~q\n",[X]),
   shift(X),
   format("Back in lower\n",[]),
   lower(Xs).

master works as expected:

?- go.
Sending a
Back in middle with A = a
Back in lower
Sending b
Back in middle with A = b
Back in lower
   false.

But with rebis-dev:

?- go.
Sending a
Back in middle with A = a

thread 'main' panicked at src/machine/system_calls.rs:1044:59:
called `Option::unwrap()` on a `None` value
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

[triska]

Awesome! Could you please file a dedicated issue for this? Thank you a lot!

[haijinSk]

Thank you... I wanted to know, why tabling doesn't work... continuations are too much for my naive approach to Prolog, but I will try to find some more "minimal" example, or I will report this example as it is.

[haijinSk]

The issue: #2920

[haijinSk]

Now with rebis-dev https://github.com/mthom/scryer-prolog/tree/af99c8c5cefc31f4df1b094bbb19e6c5f9a8e03e

I can do fib(2000,F). again: #2920 (comment)

[haijinSk]

Tabling news! :-)

Markus @triska fixed another problem e74f05a

Now, at least at this moment it seems to me, rebis-dev's tabling can be used with lists/strings as well.

Thank you very much.