Can Prolog execute non-deterministic code as fast as C?

Help!
1

Historically Prolog had an advantage over other languages because it provided backtracking. But a couple of imperative languages now provide at least generators as well:

I am not sure. But the advantage of yield is that it can make a scope of a choice point that includes loops. Whereas in Prolog tail recursion, used for loops, somehow kills and creates choice points.

What happens in Picat if it has non-determinism inside loop and assigment?
Are there some opportunities to improve Prolog? Asking for a friend…

1 Like
2

@j4n_bur53 Regarding Picat and non-determinism in a loop.

If I understand your question correctly, if there’s an non-determinism in a foreach loop then Picat backtracks and redo the assignment in the loop. Here’s a silly/contrived example using member/2 as the non-determinism in p/1 (as a kind of generator):

go ?=>
  println(p(5)),
  fail,
  nl.
go => true.

p(N) = Res =>
  Sum = 0,
  foreach(I in 1..N)
    member(Res1,1..I),
    Sum := Sum + Res1
  end,
  Res = Sum.

The output:

5
6
7
8
9
6
7
8
9
10
7
8
9
...
13
10
11
12
13
14
11
12
13
14
15

Does this answer your question?

4

There is actually a Prolog implementation built on top of yield for Python, C#, and JavaScript: http://yieldprolog.sourceforge.net/

It shows one example where coding “Prolog” in the host language looks more-less nice. However, in my opinion, yield has awful ergonomics for writing non-deterministic code, at least in JavaScript. I tried to use it to port a small pair assignment app from Prolog to JavaScript for easier deploy. The app is used on gatherings to distribute people into pairs so that each pair can chat only once but everyone gets to chat with everyone else - a NP problem imho. It quickly leads into a mess as every “predicate call” turns into a new loop in the “predicate body”.

The performance of deeply nested generators was not that good either.