Rocksolid Light

Welcome to RetroBBS

mail  files  register  newsreader  groups  login

Message-ID:  

"If you are afraid of loneliness, don't marry." -- Chekhov

devel / comp.lang.prolog / Re: Reifying backtracking for Haskell programmers

SubjectAuthor
* Reifying backtracking for Haskell programmersMild Shock
`* Re: Reifying backtracking for Haskell programmersMild Shock
 `- Re: Reifying backtracking for Haskell programmersMild Shock

1
Reifying backtracking for Haskell programmers

<urgmgt$js8i$1@solani.org>

  copy mid

https://www.rocksolidbbs.com/devel/article-flat.php?id=2304&group=comp.lang.prolog#2304

  copy link   Newsgroups: comp.lang.prolog
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!reader5.news.weretis.net!news.solani.org!.POSTED!not-for-mail
From: janburse@fastmail.fm (Mild Shock)
Newsgroups: comp.lang.prolog
Subject: Reifying backtracking for Haskell programmers
Date: Mon, 26 Feb 2024 01:37:50 +0100
Message-ID: <urgmgt$js8i$1@solani.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Mon, 26 Feb 2024 00:37:49 -0000 (UTC)
Injection-Info: solani.org;
logging-data="651538"; mail-complaints-to="abuse@news.solani.org"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Firefox/91.0 SeaMonkey/2.53.18.1
Cancel-Lock: sha1:TW62JF/iPyzzGAZBe1+yTzgsw3I=
X-Mozilla-News-Host: news://news.solani.org:119
X-User-ID: eJwNysEBwCAIA8CVRCDIOAJm/xHae58rBB0Ghzmd1Fr3sJEa8tbWwkzcLE6d3taZ5Y2nJsP/RwdzuU4r9zv5AXMfFm0=
 by: Mild Shock - Mon, 26 Feb 2024 00:37 UTC

One buzzword that Markus Triska is using is:

Reifying backtracking
https://www.metalevel.at/acomip/

But he is more up to meta interpreters.

Can we turn the whole thing into something small step?

Here is a take:

% step(+Bool, +List, +List, -Bool, -List, -List)
step(true, [write(Term)|Cont], CPs, true, Cont, CPs) :- !, write(Term).
step(true, [nl|Cont], CPs, true, Cont, CPs) :- !, nl.
step(true, [Goal|Cont], CPs, Flag, Cont2, CPs2) :-
findall(Goal-Body, rule(Goal, Body), Pairs),
pick(Pairs, [Goal|Cont], CPs, Flag, Cont2, CPs2).
step(fail, _, [Pairs-Cont|CPs], Flag, Cont2, CPs2) :-
pick(Pairs, Cont, CPs, Flag, Cont2, CPs2).

% pick(+Bool, +List, +List, -Bool, -List, -List)
pick([], Cont, CPs, fail, Cont, CPs).
pick([Goal-Body|Pairs], Cont, CPs, true, Cont3, [Pairs-Cont|CPs]) :-
copy_term(Cont, [Goal|Cont2]),
append(Body, Cont2, Cont3).

% run(+Bool, +List, +List)
run(Flag, Cont, CPs) :-
step(Flag, Cont, CPs, Flag2, Cont2, CPs2),
run(Flag2, Cont2, CPs2).

It only carries around a state consisting of flag for CALL
or REDO, and the continuations and the choicepoints. The meaning
of the transformed flag is EXIT or FAIL.

Re: Reifying backtracking for Haskell programmers

<urgmi7$js8i$2@solani.org>

  copy mid

https://www.rocksolidbbs.com/devel/article-flat.php?id=2305&group=comp.lang.prolog#2305

  copy link   Newsgroups: comp.lang.prolog
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!reader5.news.weretis.net!news.solani.org!.POSTED!not-for-mail
From: janburse@fastmail.fm (Mild Shock)
Newsgroups: comp.lang.prolog
Subject: Re: Reifying backtracking for Haskell programmers
Date: Mon, 26 Feb 2024 01:38:32 +0100
Message-ID: <urgmi7$js8i$2@solani.org>
References: <urgmgt$js8i$1@solani.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 26 Feb 2024 00:38:31 -0000 (UTC)
Injection-Info: solani.org;
logging-data="651538"; mail-complaints-to="abuse@news.solani.org"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Firefox/91.0 SeaMonkey/2.53.18.1
Cancel-Lock: sha1:PQw8utmI/P0+31oTuciwrdy9III=
In-Reply-To: <urgmgt$js8i$1@solani.org>
X-User-ID: eJwNw4ENACEIA8CVRKDCOFhh/xH+LzlXCHgMDvPxUe7huL3qLl3H+taODv0jpYzGwkTeFOhSLlyaNF96oM4Hc3QV/A==
 by: Mild Shock - Mon, 26 Feb 2024 00:38 UTC

Does it work?

t assumes the rules and facts in a predicate rule/2, here an example:

% rule(-Term, -List)
:- dynamic rule/2.
rule(app([], X, X), []).
rule(app([X|Y], Z, [X|T]), [app(Y, Z, T)]).

rule(rev([], []), []).
rule(rev([X|Y], Z), [rev(Y,T),app(T,[X],Z)]).
Works fine:

?- run(true, [app(X,Y,[1,2,3]),write(('X'=X,'Y'=Y)),nl,fail], []).
X=[],Y=[1,2,3]
X=[1],Y=[2,3]
X=[1,2],Y=[3]
X=[1,2,3],Y=[]
false.

?- run(true, [rev([1,2,3],X),write('X'=X),nl,fail], []).
X=[3,2,1]
false.

Mild Shock schrieb:
> One buzzword that Markus Triska is using is:
>
> Reifying backtracking
> https://www.metalevel.at/acomip/
>
> But he is more up to meta interpreters.
>
> Can we turn the whole thing into something small step?
>
> Here is a take:
>
> % step(+Bool, +List, +List, -Bool, -List, -List)
> step(true, [write(Term)|Cont], CPs, true, Cont, CPs) :- !, write(Term).
> step(true, [nl|Cont], CPs, true, Cont, CPs) :- !, nl.
> step(true, [Goal|Cont], CPs, Flag, Cont2, CPs2) :-
>    findall(Goal-Body, rule(Goal, Body), Pairs),
>    pick(Pairs, [Goal|Cont], CPs, Flag, Cont2, CPs2).
> step(fail, _, [Pairs-Cont|CPs], Flag, Cont2, CPs2) :-
>    pick(Pairs, Cont, CPs, Flag, Cont2, CPs2).
>
> % pick(+Bool, +List, +List, -Bool, -List, -List)
> pick([], Cont, CPs, fail, Cont, CPs).
> pick([Goal-Body|Pairs], Cont, CPs, true, Cont3, [Pairs-Cont|CPs]) :-
>    copy_term(Cont, [Goal|Cont2]),
>    append(Body, Cont2, Cont3).
>
> % run(+Bool, +List, +List)
> run(Flag, Cont, CPs) :-
>    step(Flag, Cont, CPs, Flag2, Cont2, CPs2),
>    run(Flag2, Cont2, CPs2).
>
> It only carries around a state consisting of flag for CALL
> or REDO, and the continuations and the choicepoints. The meaning
> of the transformed flag is EXIT or FAIL.

Re: Reifying backtracking for Haskell programmers

<urgmjo$js8i$3@solani.org>

  copy mid

https://www.rocksolidbbs.com/devel/article-flat.php?id=2306&group=comp.lang.prolog#2306

  copy link   Newsgroups: comp.lang.prolog
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!reader5.news.weretis.net!news.solani.org!.POSTED!not-for-mail
From: janburse@fastmail.fm (Mild Shock)
Newsgroups: comp.lang.prolog
Subject: Re: Reifying backtracking for Haskell programmers
Date: Mon, 26 Feb 2024 01:39:22 +0100
Message-ID: <urgmjo$js8i$3@solani.org>
References: <urgmgt$js8i$1@solani.org> <urgmi7$js8i$2@solani.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 26 Feb 2024 00:39:20 -0000 (UTC)
Injection-Info: solani.org;
logging-data="651538"; mail-complaints-to="abuse@news.solani.org"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Firefox/91.0 SeaMonkey/2.53.18.1
Cancel-Lock: sha1:b3qfkBaluAkDCH9NIPj+ccbPC7s=
In-Reply-To: <urgmi7$js8i$2@solani.org>
X-User-ID: eJwNwoERwEAEBMCW4nGiHIfvv4Rkdl0h6DA4zO9vqgwvuzdcJvVqnJ3hO8cfL0vKLjsqhA6NJISNTB5I3w9zBBYp
 by: Mild Shock - Mon, 26 Feb 2024 00:39 UTC

But what does it do?

A step goes through the Byrd Box, just like a Prolog debugger:

The Byrd Box Model And Ports
models each predicate in a Prolog program as a
state machine (“box”) that transitions through
states (“ports”) as a program is evaluated.
https://www.swi-prolog.org/pldoc/man?section=byrd-box-model

Mild Shock schrieb:
>
> Does it work?
>
> t assumes the rules and facts in a predicate rule/2, here an example:
>
> % rule(-Term, -List)
> :- dynamic rule/2.
> rule(app([], X, X), []).
> rule(app([X|Y], Z, [X|T]), [app(Y, Z, T)]).
>
> rule(rev([], []), []).
> rule(rev([X|Y], Z), [rev(Y,T),app(T,[X],Z)]).
> Works fine:
>
> ?- run(true, [app(X,Y,[1,2,3]),write(('X'=X,'Y'=Y)),nl,fail], []).
> X=[],Y=[1,2,3]
> X=[1],Y=[2,3]
> X=[1,2],Y=[3]
> X=[1,2,3],Y=[]
> false.
>
> ?- run(true, [rev([1,2,3],X),write('X'=X),nl,fail], []).
> X=[3,2,1]
> false.
>
> Mild Shock schrieb:
>> One buzzword that Markus Triska is using is:
>>
>> Reifying backtracking
>> https://www.metalevel.at/acomip/
>>
>> But he is more up to meta interpreters.
>>
>> Can we turn the whole thing into something small step?
>>
>> Here is a take:
>>
>> % step(+Bool, +List, +List, -Bool, -List, -List)
>> step(true, [write(Term)|Cont], CPs, true, Cont, CPs) :- !, write(Term).
>> step(true, [nl|Cont], CPs, true, Cont, CPs) :- !, nl.
>> step(true, [Goal|Cont], CPs, Flag, Cont2, CPs2) :-
>>     findall(Goal-Body, rule(Goal, Body), Pairs),
>>     pick(Pairs, [Goal|Cont], CPs, Flag, Cont2, CPs2).
>> step(fail, _, [Pairs-Cont|CPs], Flag, Cont2, CPs2) :-
>>     pick(Pairs, Cont, CPs, Flag, Cont2, CPs2).
>>
>> % pick(+Bool, +List, +List, -Bool, -List, -List)
>> pick([], Cont, CPs, fail, Cont, CPs).
>> pick([Goal-Body|Pairs], Cont, CPs, true, Cont3, [Pairs-Cont|CPs]) :-
>>     copy_term(Cont, [Goal|Cont2]),
>>     append(Body, Cont2, Cont3).
>>
>> % run(+Bool, +List, +List)
>> run(Flag, Cont, CPs) :-
>>     step(Flag, Cont, CPs, Flag2, Cont2, CPs2),
>>     run(Flag2, Cont2, CPs2).
>>
>> It only carries around a state consisting of flag for CALL
>> or REDO, and the continuations and the choicepoints. The meaning
>> of the transformed flag is EXIT or FAIL.
>

1
server_pubkey.txt

rocksolid light 0.9.81
clearnet tor