Cannot catch continuation through findall/3

Help!
1

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.

This all works.

To apply this to a DCG rule, I first do

all_outcomes(Rule) -->
    state(S0, States),
    { findall(S1, phrase(Rule, [S0], [S1]), States) }.

So that I have a list I can select from in my mc_amb, find the best one, and continue on.

However, I get:
Cannot catch continuation through findall/3.

Is there a way to do what I want to do without the above problem?

2

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.

3

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.

4

Are there particularly slow parts in delimited continuations?

7

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.

10

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.

1 Like
11

@anon95304481

My problem is that the goal I want to trial-run is specifically the current continuation.

Forgive the contrived example, but imagine representing a game this this:

play_game -->
  init_board,
  play_moves_or_end.

play_moves_or_end -->
  play_move, !, 
  next_turn,
  play_moves_or_end.

play_moves_or_end -->
  end_game.

Some players play randomly. Game flow is declarative, so to randomize a move can I do:

all_outcomes(Rule) -->
    state(S0, States),
    { findall(S1, phrase(Rule, [S0], [S1]), States) }.

random_outcome(Rule) -->
    all_outcomes(Rule),
    state(Outcomes, Chosen),
    { random_member(Chosen, Outcomes) }.

Great, now I can have players that play randomly.

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.

12

Just found this relatively new implementation of delimited control in Prolog, which maintains choice points. https://www.researchgate.net/publication/369963285_Disjunctive_Delimited_Control

2 Likes
15

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:

euchre_rounds_until_win -->
    req(p1p3_score:Score1),
    req(p2p4_score:Score2),
    try((
        { Score1 < 10, Score2 < 10 },
        euchre_round,
        next_dealer,
        euchre_rounds_until_win
    )).

(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

strategize(Rule) -->
    req(turn:Player),
    req((Player:strategy):Strategy),
    {Term =.. [Strategy, Rule]},
    Term.

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).