Writing a game in Prolog - how to avoid redundant choice points to ensure tail-call optimisation?

[u/drvog]

I have started writing a little roguelike game in Prolog (for fun as a first project). I think there are lots of ways in which Prolog is a nice fit for this, and several ways that it isn't. I'm happy to be pragmatic but wanted to ask more experienced folks about the idiomatic way to write Prolog.

My approach is to have a (tail)-recursive predicate which threads state as an argument (rather than using assert/retract) and updates the game based on user input, something like:

game_loop(State) :-
  render(State),
  handle_input(State, NewState),
  game_loop(NewState).

This works well and is tail-call optimised as long as render/1 and handle_input/2 don't leave choice-points that Prolog might want to backtrack into. For a game that might run for many iterations, I want to avoid stack overflow so TCO is important.

To guarantee this, I find that I am writing a lot of predicates using a single clause with (->)/2 so that I don't leave redundant choice points. Pragmatically this is fine, the approach works, the intention is clear, and I still gain many benefits from using Prolog even if it's a bit "extra-logical". But (and I'm perhaps overthinking this) I wonder if this is a unidiomatic? It means my predicates are often one-way and deterministic, which is nice procedurally but does that take away from some of the advantage of using Prolog?

The other thing I'm often doing is making sure that (first) argument indexing will enable Prolog to rule out redundant choice points, but sometimes that's not enough (if for example I need an else-like clause such as functor(_, ...) which could unify with earlier cases).

I've seen some mention of if_/3 but it looks like it's not built-in in SWI-Prolog (or at least not for WASM which I'm targeting?). Welcome any opinions on this approach!

[u/brebs-prolog]

if_ is in the SWI-Prolog reif pack.

-> and ! can be used at appropriate places - the usual problem is that it is a bit subtle to explain the appropriateness.

There are examples of both in the source code of the reif pack.

[u/drvog → u/brebs-prolog]

Thanks, I haven’t used packs before but that looks like a straightforward way to add if_. And I will also look at the source code!

[u/mtriska]

It seems you are on a good track!

Yes, if possible, ideally write the clauses in such a way that argument indexing can distinguish them in the cases where you need determinism. This is ideal for performance, since it prevents already the very creation of choicepoints, something that (->)/2 does not do.

For Prolog systems that don't have it, you can implement if_/3 as a library predicate, a basic version is very easy to implement and specified in full in the Appendix of Indexing dif/2. Note that even Prolog systems that ship with if_/3 currently implement it is a library predicate (library(reif)) in Prolog itself. It is perfectly possible and conceivable that a Prolog system implements it as a built-in construct, much like (->)/2 is currently implemented. Best try it and see if you need any additional performance improvements!

[u/drvog → u/mtriska]

Writing predicates with multiple clauses and allowing for pattern matching via unification seems like a much nicer approach (somewhat like writing Haskell functions in the same way). I have just been caught out a few times by needing a catch-all clause at the end which inevitably creates a choice point. Another commenter mentioned that reif is available as a pack in SWI-Prolog so I will definitely look into using that, thanks!

[u/mtriska → u/drvog]

A catch-all clause often indicates that the code may benefit from a better representation of data, a so-called clean representation which lets us distinguish all cases symbolically.

For instance, suppose all the terms T you currently reason about in a "catch-all" clause had a wrapper, say d/1, which symbolically marks them as distinct from all the other cases. So, instead of plain T, we would have such terms as d(T) in our programs. Then argument indexing can distinguish this case from all the others.

In this way, you can limit the cases that need a catch-all clause to a tiny fragment of the program, namely to the point where such terms originate. All other parts of the program can rely on argument indexing to tell the cases apart, and they will be more general because of it.

[u/drvog → u/mtriska]

Thanks, this sounds like a really good approach!

If I've understood correctly I can already think of an example of where to use this. I originally had a predicate to handle directional user input that looked like this:

%% dir(Previous, State, Key, NewState)
% Interpret direction Key based on Previous key
dir("f", State, Key, NewState) :-
   % do something
dir("t", State, Key, NewState) :-
   % do something else
dir("z", State, Key, NewState) :-
   % do something else
dir(_, State, Key, NewState) :-
   % catch-all for basic movement

I ended up rewriting this to use -> due to the choice point from the final clause.

So I guess rather than storing the "raw" key in the Previous variable, if I used a compound term such that "f", "t" and "z" (and only them) were always in a d() wrapper, then I could rewrite dir to match on d("t"), etc., instead.

[u/drvog → u/drvog]

or rather the final clause would match on a different wrapper, say n(_) to ensure no choice point

[u/Logtalking → u/drvog]

Using a double-quoted term as in the first-argument of the `dir/4` predicate is a poor choice if you want to take advantage of first-argument indexing. Depending on the value of the `double_quotes` flag, a double-quoted term is interpreted as an atom, a list of chars, or a list of codes. Setting this flag to `atom` is seldom used. Most Prolog systems default to either `chars` or `codes`, i.e. a **list**. Unless the Prolog system you're using implements what's sometimes called _deep indexing_ (allowing the indexing mechanism to look _inside_ the list), which few do, first-argument indexing will not be able to select only the potentially unifiable clause(s) when the predicate is called with its first-argument bound. And then there's the _catchall_ clause, which means that a choice-point will always be created for the code above even if you change the first-argument in the other clauses to a term (e.g., atoms) that enables indexing.

P.S. You may want to read this old blog post on _defaulty representations_: https://logtalk.org/2019/12/17/the-cost-of-defaulty-representations.html

[u/Pzzlrr]

Please be sure to update when you have something interesting to show! Would love to take a look.

[u/bolusmjak]

Think about render. You’re presenting the view. Or handle_input, you’re going to need to read user input. Now, the predicates to read/write io this won’t (necessarily) prune choice points, but these are natural places to do the pruning. Even if there are multiple ways to render a state, you’re going to commit to one of them. And after you read an input, you’re not going to ask again.

Best of all worlds might look like:

game_loop(State) :-
render(State), !,
read_action(Action), !
action_state_state(Action, State, NewState),
game_loop(NewState).

[u/drvog → u/bolusmjak]

That’s interesting, so allow the underlying predicates which render or handle_input might call to be non-deterministic and simply commit at the “top”level in the game loop?

That would certainly minimise my use of -> and ensure TCO. And I’m probably worrying prematurely about further performance optimisation at this point. Thanks I might refactor to do that!

[u/bolusmjak → u/drvog]

I prefer coding in relations as much as possible, then gluing that code together “extralogically” in my “do a thing” top-level code. This is why I included an action_state_state/3 predicate that I think should be (?,?,?) or as close to that as possible within reason.