Reifying backtracking for Haskell programmers

From	Mild Shock <janburse@fastmail.fm>
Newsgroups	comp.lang.prolog
Subject	Reifying backtracking for Haskell programmers
Date	2024-02-26 01:37 +0100
Message-ID	<urgmgt$js8i$1@solani.org> (permalink)

Show all headers | View raw

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.

Back to comp.lang.prolog | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

Reifying backtracking for Haskell programmers Mild Shock <janburse@fastmail.fm> - 2024-02-26 01:37 +0100
  Re: Reifying backtracking for Haskell programmers Mild Shock <janburse@fastmail.fm> - 2024-02-26 01:38 +0100
    Re: Reifying backtracking for Haskell programmers Mild Shock <janburse@fastmail.fm> - 2024-02-26 01:39 +0100

csiph-web