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

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

@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?

Ok thanks, I would compare this to lets say Python yield.

Also since we got already a partition function in Picat.
There is also a Python partition function using yield (sic!):

In [2]: %timeit part(6666)
103 ms

https://rosettacode.org/wiki/Partition_function_P#Python:_Mathloger

Twice as fast as Picat! So imperative language yield is enemy
of Prolog, Picat, etc… But should check on same machine.

Side Note 1: We have also a SWI-Prolog partition function
to compare with: Partition number in ZDD reply

Side Note 2: I didn’t get it yet, how in Python, they can then
extract prime numbers from the partition function.

1 Like