A declarative Fibonacci in no time without memoization/tabling (a note of a naive user)

[haijinSk]

"[Larry] Wall argues that Perl itself has no “theoretical axes to grind” or “any agenda at all, other than to be maximally useful to the maximal number of people. To be the duct tape of the Internet, and of everything else.” Wall asks, “How is duct tape like the Force? It has a light side, and a dark side, and it holds the universe together.”"

Norberto Gomez Jr.: The Art of Perl: How a Scripting Language (inter)Activated the World Wide Web, 2013 (dissertation)

---

Not a math/number person, but I was dreaming about "quick fibs": #2896

and at the end of the day (or in the morning, so to speak) I ended up in a pessimism--hope "quantum state": #2947

I'm almost a non-programmer yet fascinated by and with programming languages, as they are digital incarnations of ideas ready to be used for "real things", a kind of magic...

It's not relevant here, but I have no sympathy for any "AI" things (as I see it, at best, the "AI" is a gargantuan, brutally-commercial recyclation of human created content without any, any compensation for the authors). As I see it, the best AI are programming languages themselves. "The world needs less AI and better programming languages": https://mitpress.mit.edu/9780262548717/moral-codes/

Back to the Fibs. I saw this Raku "fibs-idiom" recently:

0,1,*+* ... *

It's a sequence:

[0] > WHAT 0,1,*+* ... *
(Seq)

and it's lazy:

[1] > .is-lazy with 0,1,*+* ... *
True

For example, the first 20 elements:

[2] > 0,1,*+* ... * ==> head(20)
(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181)

And, in no time, at the position 10_000 (starting from zero):

[8] > 0,1,*+* ... * ==> *[10000]()
33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875

Lazy lists or not, now, I want that declarative 10000 "in no time" in Scryer and Trealla.

My file to consult (I let it be short, except when libraries are explicit):

:- use_module(library(dcgs)).
:- use_module(library(clpz)).
:- use_module(library(lambda)). 

fib(0,_,_) --> [].
fib(L,N,N1) --> { L#>0, N2#=N+N1, L1#=L-1 }, [N], fib(L1,N1,N2).

And the "one-liner". For "pretty-printing" I'm using notation from lambda for selecting only one varable to be displayed:

?- F+\(phrase(fib(10001,0,1),Fs),phrase((...,[F]),Fs)).
   F = 33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875
;  false.

It's not "in no time" in both directions, though. Of course, it can be written without using CLPZ and DCGs, without constructing a list and some steroids in a form of the cut ! might be added, for extended "in no time" behavior, but I'm not the right person for the cut things.

Thank you.

[hurufu]

Just use closed-form Binet's formula if you need it really fast ;) In programming performance is usually achieved by changing the algorithm and not by doing micro-optimizations.

[jjtolton]

Very cool, @haijinSk !

I've never met an "almost non-programmer" who can write DCGs before!! I barely know any PROGRAMMERS that can write DCGs! This is great!

I was inspired to play around with it! Not nearly as elegant as your formulation but it does address the list carry and the redundant choice point from the defaulty representation. Thanks for the write-up!

:- use_module(library(dcgs)).
:- use_module(library(time)).
:- use_module(library(lambda)).
:- use_module(library(reif)).
:- use_module(library(lists)).
:- use_module(library(clpz)).

clpz:monotic.

% using "successor notation" so that you don't have a "defaulty respresentation"
% in the DCG
succs(N, S) :- succs_(0, N, S).

succs_(A,B,s(C)) :-
        #A1 #= #A+1,
        if_(A=B,
            C=0,
            succs_(A1,B,C)
           ).

?- succs(3,S).
   S = s(s(s(s(0)))).

%% using semicontext notation "stack" so you don't need to carry the whole list in memory
fib_(A,B), [B,C] --> { #C #= #A + #B }.

fib(0) --> [_].
fib(s(N)) --> [A,B], fib_(A,B), fib(N).

?- phrase(fib(s(s(0))), [0,1], [Res]).
   Res = 2.

%% convenient API
fib(N, Res) :-
        0 #=< N, % so that you don't have to specify domain of N at toplevel
        succs(N,S), % so that you don't have "defaulty" representation
        phrase(fib(S), [0,1], [Res]). % so that you don't carry the whole list 

?- fib(N, R).
   N = 0, R = 1
;  N = 1, R = 2
;  N = 2, R = 3
;  N = 3, R = 5
;  N = 4, R = 8
;  N = 5, R = 13
;  N = 6, R = 21
;  N = 7, R = 34
;  ... .

% boring co-recursive version!
fib(A,B,N,R) :-
        #C #= #A + #B,
        #N0 #= #N - 1,
        if_(N=0,
            R=B,
            fib(B,C,N0,R)
           ).

fib1(N,R) :-
        fib(1,1,N,R).


?- fib1(N,R).
   N = 0, R = 1
;  N = 1, R = 2
;  N = 2, R = 3
;  N = 3, R = 5
;  N = 4, R = 8
;  N = 5, R = 13
;  ... .

?- fib(N,R),fib1(N,R).
   N = 0, R = 1
;  N = 1, R = 2
;  N = 2, R = 3
;  N = 3, R = 5
;  N = 4, R = 8
;  N = 5, R = 13
;  N = 6, R = 21
;  ... .

?- \((N=10001, fib(N,R), fib1(N,R))).
   true.

?- \time(fib(10001, _)).
   % CPU time: 0.042s, 200_076 inferences
   true.

?- \time(fib1(10001, _)).
   % CPU time: 0.042s, 150_062 inferences
   true.

[jjtolton]

Here's a weird version that goes all in on the stack and doesn't use any DCG params:

:- use_module(library(dcgs)).
:- use_module(library(time)).
:- use_module(library(lambda)).
:- use_module(library(reif)).
:- use_module(library(lists)).
:- use_module(library(clpz)).

clpz:monotic.

fib_(N, A,B), [N0,B,C] --> { #C #= #A + #B, #N0 #= #N - 1 }.

fib --> [0,A].
fib --> [N,A,B], { #N #> 0 }, fib_(N,A,B), fib.

?- phrase(fib, [N,1,1], [Last]).
   N = 0, Last = 1
;  N = 1, Last = 2
;  N = 2, Last = 3
;  N = 3, Last = 5
;  N = 4, Last = 8
;  N = 5, Last = 13
;  N = 6, Last = 21
;  N = 7, Last = 34
;  ... .


?- \time(phrase(fib, [10001,1,1], [Last])).
   % CPU time: 0.035s, 150_050 inferences
   true
;  % CPU time: 0.000s, 4 inferences
   false.

[triska]

This is awesome to read, the latest state-of-the-art constructs such as lambda, quads, if_/3 casually thrown around like it's nothing, haha!