I’m using DCGs for implicit state management for a game.
I’m also using delimited continuations to implement a Monte Carlo Tree Search version of the amb operator (call it mc_amb for short).
There is a proof of concept here "Monte-Carlo amb" in Prolog, proof of concept · GitHub
amb is an operator (useful in other languages) where we capture the current continuation, and try selecting a member of a list until our continuation doesn’t fail. (This is not particularly useful in Prolog where we get this for free.)
The idea of mc_amb, is we want to select a member of a list, and run the continuations for each selection. Assuming the continuations contain randomness (like in a game), we replay each to get statistical info on the “utility” of our selection, and find a suitable selection.
You have to remember that a continuation does not capture the choice points. That, if I recall correctly, is one of the reasons why it doesn’t work well with e.g., findall/3. You have to make sure that both the reset/3 and shift/1 are inside the goal of the findall/3.
The problem is not entirely clear to me. As you suggest though, it seems Prolog doesn’t need continuations to solve this problem. If this is the case, I’d avoid them. They are relatively slow and indeed do not add much to Prolog. The motivating coroutining examples can all be implemented with other means that are more efficient. The reason for adding them to SWI-Prolog is that they allow for a fairly simple and still fairly efficient implementation of tabling. The limitations imposed by continuations are already limitations of tabling anyway. Otherwise, engines seem to be a cleaner way to implement coroutines.
In essence I need “select_once with agency”, where this “smart select” knows that the continuation post-selection, contains calls to random. And so this “smart select” can run simulations on the continuation to see what likelyhood of success its selections might have.
In any case. I think I can keep my findall outside of the reset.
The example doesn’t need shift/reset. There is no state in run_with_amb_fail/1.
You can implement it without shift/reset. Just define:
amb(Choice, List) :- random_member(Choice, List).
That run_with_amb_fail/1 has no state is seen in that it has only one argument.
It does not some threading of something abstractly. On the other hand run_with_monte_carlo_amb/2 has a state, the Count as state. But I
wonder whether one needs shift/reset at all. Your code on GitHub doesn’t
have some comments, it does not describe what the predicates do, so its
difficult to judge what your intention is. Since shift/reset does backtrack state,
I also have doubts that what you do with the Counter, is what you expect that
it does with a Counter. As I see it, it does only some deepening. The ISO
core standard allows block comments /* */ and line comments %.
Edit 08.12.2023
Ok, my bad, I see, Count is even not a state. Its the number of samples
that are taken for an amb instruction? And the sampling is used
to find a choice with a high count, and then use this choice?
But you don’t use amb/2 in the helper predicate guess_the_dice_total/1.
There its directly random_member/2. So you use sampling to estimate some
likelihood, and then choose the parameter with maximum estimated likelihood.
Sounds interesting because it suggests, I think, shift/reset would be useful for linear ordered ancestor resolution prover. For a long time, IMHO, tabling in general seems close to that prover. I will review old codes of mine on the prover.
On the other hand, I dropped all shift/reset from my zdd implementation, because of the existence strange 0 (not true), and shift/1 is not module transparent, which are not serious at all, but for my use of shift/reset as DCG, I lost gradually merits of shift/reset. Now I use the b_setval for shift/reset in stead.
I am rather interested for handling local stacks to implement such like the current shift/reset, reminding me of spaghetti-stack controls in InterLisp a long long time ago.
In your case you are using a delimited continuation by invoking
it multiple times, i.e. call/cc, because of the sampling. Whats also
discussed are one-shot delimited continuations, i.e. call/1cc.
call/1cc is often enough if you are threading some state. That
you call it multiple times is seen here. What you call Goal as formal
parameter is actually a continuation:
run_n_trials(0, _, _, _, 0).
run_n_trials(N, Goal, Choice, Item, TotalWins) :-
N > 0,
N1 is N - 1,
run_n_trials(N1, Goal, Choice, Item, Wins),
(\+ \+ (Choice = Item, run_with_amb_fail(Goal))
->
TotalWins is Wins + 1
;
TotalWins is Wins
).
But you call it with \+ \+ and =, simulating a kind of beta-reduction, one
that is also throwing away Prolog logical variables binding side effect
of calling the delimited continuation. So that you can then implement
run_n_trials/5 recursively. So you basically invented an implementation
of library(aggregate) and counting samples, that doesn’t use a generator
to backtrack over a predicate that succeeds and fails, and then count the
success, rather use a continuation tail recursively.
Edit 09.12.2023
Just compare with the source code of library(aggregate), how the counting
is done via backtracking. But it uses the non-logical nb_setarg/3, I guess it can
be critized for this logical impurity? Maybe this was the motivation for run_n_trials/5?
The SWI-Prolog system comes with batteries included, right?
If you call aggregate_all/3 with a Goal that has between/3 in it,
a call/cc is basically done through the Prolog system itself, such a
call/cc happens more or less for a conjunction (‘,’)/2 of Prolog anyways,
for the conjunction Generator, Test, if you view the Test as a continuation,
then Prolog backtracking is call/cc from the Generator to the Test. There
are two generators in the solution below, namely guess/1 and between/3.
between/3 is used to repeat the stochastic experiment. guess/1 is used
to run through all possible choices. No manual beta-reduction with = and
undoing bindings through \+ \+ needed, thats included in the backtracking.
Edit 09.12.2023
Maybe Choice = Item can be also moved out of run_n_trials/5.
Choice and Item are always the same two parameters of run_n_trials/5.
Don’t know. I have Choice = Item through guess/1 generator completely
outside of aggregate_all/3. This is the idea of the run_n_trials/5, right?
To run each stochastic experiment with the same value?
It is simply a quite involved process. shift/1 creates a representation of the stack frames between the shift/1 and reset/3 calls as a Prolog term. Calling this has to rebuild the stack frames from this. There might be some more room for optimization. With the implementation of tabling using this, I did most of the low-hanging fruit though.
If I want a player with a (Monte Carlo Tree Search) strategy, then the Goal I want to trial is “the rest of the game from this point”, I.e., the current continuation, with the possible move selections generated with findall.
Maybe there’s some CPS transform I can do to always have the continuation on hand.
I doubt that it is the current continuation. Because the current continuation
can include also other things than your game. Its must be anyway a delimited
continuation, delimited by some surrounding reset/3. And this could give you
some hint how to use ordinary goals, instead of continuation. There was
for example the language of BinProlog, which had the current continuation
accessible, like in this example 1 and this example 2. On the other hand
the SWI-Prolog continuation goals obtained from reset/3 are delimited, they are
not the current Prolog system continuation which can be much larger, they only
reach to the end of the goal argument in the initial reset/3. So maybe you can use
this insight to remove reset/3 and shift/1 from your code all together.
Edit 10.12.2023
Wikipedia uses the terminology slice instead of delimited:
Delimited continuation
In programming languages, a delimited continuation, is a “slice” of a
continuation frame that has been reified into a function. Delimited continuation - Wikipedia
In SWI-Prolog the reification happens during or after shift/1, and
the slice goes from shift/1 to the surrounding reset/3 bound. When
you call later reset/3 again with this reified slice, you will also not break
out of this bound. It will keep its delimited nature, the next time a shift/1
happens. In Scryer Prolog its even a little bit more complicated to
call reset/3 again. Thats a convenience of SWI-Prolog that you can directly
supply a continuation to reset/3, in Scryer Prolog you need to use call_continuation/1 inside reset/3 to indicated that you call a continuation.
This convenience of SWI-Prolog blurs goal and continuation, which was seen
in your run_n_trials/5 where you named the argument Goal and not Cont.
You are correct. My terminology was off. I was trying to emphasize that the “goal” I was interested was the delimited continuation I (currently) had at hand. And not a term I could easily construct because program flow is implicit in my DCG and not explicitly handled.
Yes, but, not the way I want to represent things.
I have older code with explicit state handling, where a game must implement: possible_moves(State, Moves) apply_move(State, Move, NextState)
The “engine” that runs these games uses Monte Carlo Tree Search for all players.
This all works and I’ve coded a few games this way. But my code with explicit state management is tedious.
So I’, trying to express game state transitions with DCG syntax for state management. Still working on the best way to express things, but I can do things like:
(req looks up an assoc K:V from current state, try attempts something and commits, otherwise succeeds).
Now, any time a player’s legal moves is dictated by some rule Rule, I could simply invoke Rule and this would allow me to enumerate all possible games.
Instead, I’d like to “wrap” the rules with strategize like so
I showed the random strategy above (find all outcomes of a rule and select a random member). The Monte Carlo strategy would/might use delimited continuations and the amb trick to perform the Monte Carlo analysis.
I find it quite appealing too. Specifically, the “dumber” the sampling is, the easier it is to make it fast and parallelizable. I already have code playing some small strategic games better than me, and solving some game-puzzles that I didn’t expect would be solvable this way (because so much of the game-tree would be left unexplored).
In any case, my “problem” isn’t one of “how can I make Prolog do this thing”.
It’s, specifically:
With what Prolog features, DSLs, syntax can I most declaratively state game rules and transitions, AND have opponents play the game with different strategies (including a strategies that can make use of said rules/transitions to play hypothetical simulation games).