I’ve been learning Prolog and stumbled upon an interesting debate about the meaning of ‘semidet’. It seems there were two main interpretations:
A computation that succeeds at most once
A computation that leaves no choice points open when it succeeds
The first one is more general, while the second is more specific. I’m curious if the Prolog community has settled on a single definition since then.
Also, I’m wondering about the term ‘det’. Does it mean:
A computation that succeeds exactly once
A computation that succeeds once and leaves no choice points
These distinctions seem important but I’m not sure if there’s agreement. Should we use different terms for these concepts?
% Example of a potentially 'semidet' predicate
find_first_even([H|_], H) :- 0 is H mod 2, !.
find_first_even([_|T], X) :- find_first_even(T, X).
% Is this 'det' or just 'semidet'?
always_true(X) :- X = 42; X = 42.
Any insights on how these terms are used in practice would be helpful!
As someone who’s worked with Prolog for a while, I’ve seen the ongoing debate regarding the definitions of ‘semidet’ and ‘det’. From my perspective, the more specific, stricter definitions have become widely preferred. ‘Semidet’ is typically understood as a computation that succeeds at most once and leaves no choice points, while ‘det’ is seen as succeeding exactly once with no remaining choice points. In practice, these definitions offer clarity, especially when optimizing for performance or ensuring predictable behavior. For instance, in your example, find_first_even/2 fits the semidet category because it will either succeed once with the cut preventing backtracking or fail, whereas always_true/1 remains multi due to its inherent backtracking possibility.
hey, i’ve used prolog a bit and from what i’ve seen, most folks tend to go with the stricter definitions nowadays. semidet usually means it succeeds once max and doesn’t leave choice points. det is like, it always succeeds once, no choice points left. makes things clearer when you’re coding. your find_first_even looks semidet to me, but always_true is kinda multi cuz of the backtracking stuff.
In my experience working with Prolog, the community has largely converged on the stricter definitions for ‘semidet’ and ‘det’. ‘Semidet’ is now commonly understood as a predicate that succeeds at most once without leaving choice points, while ‘det’ refers to a predicate that always succeeds exactly once without choice points.
These definitions provide clarity and are crucial for optimization and determinism analysis. Your find_first_even/2 example fits the ‘semidet’ category perfectly. The always_true/1 predicate, despite appearing deterministic, is actually considered ‘multi’ due to its potential for backtracking.
Understanding these distinctions is vital for writing efficient and predictable Prolog code, especially in large-scale applications where performance and behavior consistency are paramount.