Another data point from “The Art of Prolog”, pp.11:
Logic programs can incorporate alternative definitions, or more technically disjunction, by having alternative rules, as for parent :
parent(X,Y) ← father(X,Y) .
parent(X,Y) ← mother(X,Y) .
We still teach a semester of logic in first year and then a semester of logic programming and constraint programming in third year. I think the places that have given up on Prolog and even on logic are the ones that tend to follow fads, etc. There are only a handful of programming paradigms, with logic programming being the most different one from the others, and many top places still understand that a computer scientist is simply not complete without learning about logic programming (the same as with functional programming). I hope the relevance of Prolog and (C)LP will only increase with the growing relevance of neurosymbolic computing.
Btw, teaching (constraint) logic programming / Prolog to CS students that are already very capable with imperative programming has some challenges, but our students systematically tell us that the course widens their programming horizons. If all this is interesting for you, some of our experiences are reflected in a few papers, e.g., Some Thoughts on How to Teach Prolog, in Prolog - The Next 50 Years, Springer LNCS 13900, July 2023, or Teaching Pure LP with Prolog and a Fair Search Rule. Proc. 40th ICLP Workshops, CEUR-WS.org, Vol. 3799, October 2024. Also, the Prolog Education group organizes workshops, online discussions, and meetings related to teaching Prolog.
OK, so:
p([]).
… is a conjunction when considered as part of the program logic (because it is in the list of predicates in the program), and is a disjunction when considered at runtime (executable alternative).
A Programmer is naturally going to view it as a disjunction.
I view this conjunction vs disjunction as being different to a declarative vs procedural reading of the program:
- Declarative reading: Are constraints defined sufficiently
- Procedural reading: Will the program execute correctly, in a timely manner, without falling into infinite loops etc.
Yes, because the LHM is defined as the unique, least Herbrand model of a logic program. The existence of a smaller HM would contradict this definition.
What I’d say is that whereas a logic program is formally a conjunction of definite clauses and the language was designed with that semantics in mind (as noted by @herme above with respect to CNF) it is often interpreted as a disjunction because of the way that observing program execution makes it look like rules are executed similar to a series of conditional jumps or the cases of a switch statements in an imperative language.
That’s what I mean by he “procedural interpretation” or “procedural reading”. I mean it literally: because it follows from observing the execution of the program while holding in mind a model of program execution in a procedural language. Or in other words we use our understanding of how a program in a procedural language works to understand how a Prolog program works.
I don’t think that’s a mistake btw, but I think it’s useful to understand the formal semantics also.
Sorry, that’s not what I meant. What I was saying is that in The Craft of Prolog the only thing called a “disjunction” is the ;/2 built-in. The book never calls a set of clauses a disjunction nor refers to them as alternatives. Of course ;/2 should be used as a disjunction operator. No problem with that, nor does it go against anything I said to have an explicit disjunction operator. On the contrary.
Well… that idea came from somewhere didn’t it? I wouldn’t bother with it if it wasn’t so wide-spread. I don’t know if this originated with Sterling and Shapiro. It’s worth trying to find them and ask them about it.
But I think Sterling and Shapiro were just doing like everyone else and trying to make Prolog easier to understand by presenting it in terms more familiar to programmers. I don’t know much about Sterling but Shapiro in particular should be well aware of the formal definition of a set of clauses as a CNF formula.
Or not, I don’t know. After all logic programming is obviously a discipline with a root in both logic and programming. There’s going to be different views on it from different people in the community.
I’m myself trying not to say what is right and what is wrong because I don’t want to be bullish about it. The formal interpretation I note that a set of definite clauses is a conjunction should really not be controversial I mean it’s in the books. It’s just not the books on Prolog. I guess the bottom line is Prolog programmers don’t really care? Only prolog logicians care? And those few of us who live in between the two worlds must forever suffer from cognitive dissonance 
Preach it padre! 
Thanks, the subject is indeed of great interest to me. I’ll have a look.
I think many do care but they want a semantics that’s consistent with their understanding of the programming language they’re using. So given the query ?- fruit(X)., X is unified with a specific fruit, not the set of all fruit. In my non-logician mind, that’s “consistent” with disjunction in first order logic. But then I’m not trying to understand a Prolog program in any other way than how Prolog itself understands it and doing so doesn’t help me.
You may be interested in taking Prolog syntax and defining a different (second order?) semantics. Perhaps disjunction disappears because it’s absorbed into the concept of sets (a disjunction of values). That’s fine if it helps you accomplish whatever you’re trying to do, but I do think it is contrary to established Prolog programming practice and needs to be incrementally built from the ground up so us non-logician Prolog programmers can understand what you’re proposing.
Now there are a few “standard predicates” for building sets (findall and friends). From “The Art of Prolog”, chap. 17.
This chapter in contrast shows programming techniques that are missing from the basic logic programming model, but can nonetheless be incorporated into Prolog by relying on language features outside of first - order logic . These techniques are called second-order, since they talk about sets and their properties, rather than about individuals .
If every query was wrapped in a findall (or friend), then the interpretation of “Sets of rules as conjunctions..” (IMO) would be easier to comprehend:
?- findall(X,fruit(X),SetOfFruit).
SetOfFruit = [apple, banana, durian].
Perhaps you can’t tell whether a “Set of Rules” is a conjunction or a disjunction just looking at the rules; it depends on how they are used (pure Prolog/ backtracking or extended Prolog/findall). So, in the context of this forum, what was the objective in asking the original question?
I think it’s the other way around. The problems begin when programmers try to understand Prolog by falling back to the semantics of procedural languages like we’re used to. Prolog is not a procedural language, its semantics are those of predicate logic (with some differences; e.g. see the first/second order thing I discuss below) and in FOL a set of definite clauses, or, really, any set of clauses, is a conjunction of disjunctions as in Conjunctive Normal Form (CNF). That’s the theoretical basis of Prolog and there’s nothing that can be done to drastically change it without inventing a new logical paradigm from the ground up.
So it’s not that I would have to define a new semantics. It’s the actual semantics I care about. The issue is that learning Prolog has gone a certain way historically and that’s also very hard to come back from now. If The Art of Prolog says that a set of clauses is a disjunction, that’s what everyone who reads the book and who doesn’t know about CNF (which btw I don’t think is in the book) will learn. Then that gets very hard to unlearn.
Strange but the Second-Order Programming chapter in my copy of TAoP is chapter 16, not 17.
I don’t know why S&S say setof/3 etc have to do with second-order logic. Normally, when we talk about the second-order of logic we mean that quantifiers can range over the sets of predicate and function symbols, not only the set of first-order terms. [EDIT: what I mean is that FOL too works with “sets and their properties”, not just second-order logic.]
But that distinction only makes sense in predicate logic where there are such things as sets of predicate and function symbols. In Prolog we only have “functors” which can be used anywhere in a Prolog “term” (and I put that in quotes because even the definition of a “term” is different in Prolog and logic). So for example, as I pointed out above p(X,p(X, Y)) :- a, b, c. is perfectly valid Prolog but it is not valid FOL because the symbol “p” can’t be both the symbol of a term and its argument.
In second order logic, p(X,p(X,Y)) :- a, b, c. is perfectly fine because then “p” is obviously a predicate symbol and “p(X,Y)” is an atomic formula passed as an argument to (a different instance of) itself. Not a problem there at all.
All of which tells us that Prolog is already … well, not second order exactly but certainly not first order. And yet, every Prolog textbook will tell you that Prolog is a language with the syntax of first-order logic. That’s just not true.
So why do textbooks do that?
Here’s my best guess: Prolog is already extreme demanding on the programmer’s mind. I know this well myself, I struggled endlessly as an undergraduate trying to learn it. Why make things even harder by introducing complicated concepts like the different orders of logic? And, let’s be fair, while there is a lot of knowledge on FOL, the further you move up in the orders of logic, the harder it gets to find both authoritative information and common understanding. Second Order Logic, eh, OK, you can find stuff about it here and there. Third Order and beyond? Forget about it. So I think people just fudge and simplify - maybe sometimes also to make it easier for themselves to understand the material that they want to teach.
Well, I was hoping that if there exists a forum on the internet where a deep and informed discussion on Prolog semantics can be had, it would be this one or the ILP Discord server where I first raised this issue.
I like having deep and informed discussions on Prolog. Sue me, I don’t know. Maybe some people think that’s just aimless faffing about? But to me, because I’m also an ILP researcher as well as a Prolog programmer, the knowledge I got from discussions like that has been indispensible and I would not have been able to advance in my discipline without it.
I used to complain to my thesis advisor that he had it good when he was doing his PhD because he could go down the corridor and speak to all the greats of symbolic AI most of which are now retired. That’s… part of the reason I’m talking about this stuff here. I’m just starved for good conversations on Prolog, logic and ILP.
It’s inevitable when there’s so few of us left.
Perhaps https://discourse.prolog-lang.org/
Yes, when going through the learning process 
While I’m probably not the right person to partake in the discussion, let me try to expand on my previous post.
Taking the fruit example, it’s just a predicate (relation?) defined by a set of clauses (facts/rules) defining what is true. If you want to view this a conjunction, which defines what a fruit is in the context of the program, that’s fine. But isn’t it incomplete in terms of the semantics, which is also dependent on the question which isn’t part of the program?
For example, if I ask the question ?- fruit(X). the relation fruit/1 implies that X=apple ; X=banana ; X=durian, i.e. a disjunction. If I ask the question ?- findall(X,fruit(X),S)., S is a list of all fruit (which could mean a set). If I ask the question ?- fruit(X),fruit(Y). the “answer” is a disjunction of conjunctions. So what did the original fruit/1 predicate “mean”, if not all of those things.
And from the outside, the semantics isn’t any different than if I had defined fruit/1 as:
fruit(X) :- X = apple ; X = banana ; X = durian.
The semantics is the same (isn’t it?) but I suggest the argument that it’s a conjunction isn’t very compelling. Calling it anything but a predicate/relation seems like overreach.
Personally speaking, I stopped thinking much about these things several (too many?) decades ago. It is what it is, and I don’t find basic Prolog particularly confusing once unification and backtracking are mastered. In fact if one could unlearn imperative programming, it’s pretty simple (IMO). But then I’m not a logician, or even a mathematician.
I think both the declarative and operational views are very useful and should both be taught. This is one of the arguments of the papers I mentioned above on teaching Prolog. The declarative view gives us the incredible beauty of the Prolog language: I think something important is lost if we just teach the operational view without making the student experience the beauty of clear and succinct specifications that ‘run’ in all directions, types and properties that can also be generators of tests (“inhabitants”), specifications that can be evolved into very efficient algorithms, etc. At the same time the operational semantics helps us understand termination and cost, which are necessary concerns in a real programming language (v.s. just a problem representation tool), as Prolog is, and plainly lets us use Prolog exactly the same as any other language, but with powerful additional mechanisms, which is also useful at times. Prolog can be seen as both an executable specification language and a sort of “improved Python with backtracking and unification”, and for me at least the fact that both views can coexist makes the language even more powerful and attractive.
No, that’s the point. A definite logic program is defined as a set of definite program clauses i.e. rules and facts. Prolog goals/queries are not program clauses they are… goals.
And a set of definite clauses is a conjunction. That’s the correct semantics and that should not be controversial. The procedural interpretation comes in later when we execute the program.
But, see, in that case, too, declaratively speaking we have a conjunction. Because we are trying to prove that the conjunction of the program clauses and the goal is unsatisfiable.
But that’s a different thing now isn’t it? Here you have a disjunction between a set of Prolog atoms (FOL constants) in the body of a clause.
Whereas here:
fruit(apple).
fruit(banana).
fruit(durian).
you have a set of facts. Yes, if you query both definitions with fruit(X) you’ll see the same results at the top-level but you’ll get those results for different reasons and in different ways. We want to know what the difference is, no?
So just to be clear again what I’m saying is that a set of definite clauses is a conjunction. Not that the set of bindings of a variable at the top-level is a conjunction.
It’s a subtle difference because when you get the bindings of a variable at the top-level what Prolog is really saying is “if you bind this variable that way in your goal, you get a true fact”. So when you see X = apple in here:
?- fruit(X).
X = apple
That means that there is a fact fruit(apple) that is a logical consequnce of your program. Or, in other words, fruit(apple) is a member of a model of your program. And that model is a set of facts that are all true according to your program. And because all those facts are true, no exceptions, they can be seen as a conjunction.
And I agree that you can also see the bindings of the variables as a disjunction, but what I’m arguing is that you can’t only see it that way. I think you’re wrong to stick to one interpretation only because that’s not going to give you the whole story. “It’s just a disjunction” is not the complete view.
To be fair, you can also see the atoms in your disjunction as a set of facts. However apple, as a 0-arity fact, is a different fact than fruit(apple).
I think we need clearer terms 
I view “declarative” as “Are constraints defined sufficiently” - this is the “beauty of clear and succinct specifications that ‘run’ in all directions” as @herme mentioned.
So, “declarative” to my mind is declaring constraints, rather than involving nth-order logic and getting back into the disjunction vs conjunction viewpoints (both viewpoints are equally valid, they are just from different perspectives).
Looks like we need unambiguous terms to describe:
- conjunction viewpoint
- “Are constraints defined sufficiently” whilst in the disjunction viewpoint
I’m afraid you’re losing me here. If it isn’t controversial, then why has this thread gone beyond 30 posts?
So why is a set of clauses with the same functor/arity a conjunction and what is it a conjunction of (pardon the dangling participle)? I don’t think you’re saying that a prolog program (the “knowledge base”) is just a conjunction of all its clauses (that’s what it would “mean” to a Prolog loader/compiler), are you?.
And I see it as a disjunction of unifications, but how is the semantics/meaning different? What (non-meta) goal could distinguish between the two implementations?
But how is that relevant to the discussion? Aren’t we talking about semantics rather than process?
Do we? Why?
I would state it differently. The model of the program is all the goals that can be proven with that program. I concede that’s a conjunction but I don’t see how that’s particularly useful. (In many cases, e.g., non-termination, it’s not even finite.)
But I don’t see how “knowing the whole story”, whatever that may be, helps me as a Prolog programmer. (Sorry, so many questions.) I guess I’m trying to understand how it helps you.
I think you’re right, this thread has grown a bit too long. Thank you and everyone else for the engaging conversation.
You’re right of course. It’s a disjunction of =/2’s. My bad.
To clarify the meaning of the disjunction in the body of a clause (which is definitely a disjunction) vs conjunctions of clauses, I think it may be useful to do some transformations on:
fruit(X) :- X = apple ; X = banana ; X = durian.
I do it in propositional form to save typing:
f <- a v b v d.
Just reversing:
a v b v d -> f
We apply: p → q = ~p v q
~( a v b v d ) v f
We apply De Morgan to move the negation inside the disjunction:
( ~a ^ ~b ^ ~c ) v f
Distributing:
( ~a v f ) ^ ( ~b v f ) ^ ( ~d v f )
Back to implications, using again ~p v q = p → q
( a -> f ) ^ ( b -> f ) ^ ( c -> f )
Reversing again:
( f <- a ) ^ ( f <- b ) ^ ( f <- d )
Note that here we got a conjunction of three clauses. I.e., in Prolog notation:
f :- a. f :- b. f :- d.
And, if we go back to the original clause we get:
fruit(X) :- X = apple.
fruit(X) :- X = banana.
fruit(X) :- X = durian.
which is the same as:
fruit(apple).
fruit(banana).
fruit(durian).
Referring this back to conjunctive normal form (CNF), what happens is that the original clause with the disjunctions is not really in CNF, but Prolog allows us to write clauses like that for convenience. What we have done with the transformations above is to put the clause with the disjunction in CNF. This results in three clauses.
No need to apologize; “dangling preposition” is a made-up rule by John Dryden (1672) and Bishop Robert Lowth (1762), who thought that a Germanic language (English) should follow Latin grammar rules (and Latin doesn’t have things like phrasal verbs or trennbare Verben). Even The Economist – which incorrectly eschews spitting infinitives – agrees that it’s usually OK, or often preferred, to dangle prepositions.
W.r.t. to the questions on queries, suppose we want to prove that there
exist a list whose length is less than 3 (and obtain the
solutions). In Prolog we would write:
?- list(X), length_lt(X,3)).
Let’s see what this Prolog notation really means.
The query in logic
To write “there exists a list whose length is less than 3” directly
in logic we can do it as follows:
exists X ( list(X) ^ length_lt(X,3) )
with ^ being conjunction.
Now, in resolution (Prolog’s ‘operational’ semantics) we prove things
by contradiction, i.e., we start by negating what we want to prove, and
try to show that this is false (and thus that the converse is
true). I.e., we try to prove that there do indeed exist lists whose
lengths are less than 3. Furthermore, while doing it, and thanks to
resolution, we even find counter examples, i.e., lists that are indeed
of length less than 3, namely [], [_], and [_,_], which are then our
answers.
OK, so, in order to prove things, we have to negate what we want to
prove, so, we write our query (using ~ for negation) as follows:
~( exists X ( list(X) ^ length_lt(X,3) ) )
Let’s call this expression [a].
Relating the two notations
But, how does [a] relate to:
?- list(X), length_lt(X,3)).
It is in fact exactly the same. Let’s see it.
First, the ?- above is standing for :- . Using ‘?’ instead of ‘:’ is
just Prolog notation reminding us that this is a query. So our query
is really:
:- list(X), length_lt(X,3)).
If we write this using logic notation we have:
true <- list(X) ^ length_lt(X,3)).
reversing → :
list(X) ^ length_lt(X,3)) -> true
using again p → q = ~p v q, we have:
~( list(X) ^ length_lt(X,3) ) v true
equivalent to:
~( list(X) ^ length_lt(X,3) )
which, is indeed [a], i.e., our query, negated. So,
?- list(X), length_lt(X,3)).
is the same as [a] and represents the negation of what we want to
prove (i.e., what we want to ‘run’).
What about the quantifiers?
We normally do not write quantifiers in both CNF and Prolog because
when we convert to CNF we eliminate the existential ones, and, since
then all variables have a forall, normally we do not write them. But
they are there, and, in CNF, they are always the outermost thing, i.e.,
~( list(X) ^ length_lt(X,3) )
is really:
forall X ~( list(X) ^ length_lt(X,3) )
Moving the forall inside the negation (which changes it to an exists),
we have:
~( exists X ( list(X) ^ length_lt(X,3) ))
I.e., exactly [a].
Is the query a Horn clause?
Finally, is our query,
?- list(X), length_lt(X,3)).
equivalently:
~( exists X ( list(X) ^ length_lt(X,3) ))
a Horn clause? Let’s see, we have:
~( exists X (list(X) ^ length_lt(X,3)) )
If we move the quantifier outside the negation (changes to forall) we get:
forall X ~( list(X) ^ length_lt(X,3) )
And, if we move the negation inside the conjunction by De Morgan we
get:
forall X (~list(X) v ~length_lt(X,3))
As usual we can drop the forall:
~list(X) v ~length_lt(X,3)
Note that this is a disjunction of literals, all negated (none of them
non-negated), which is the definition of a Horn clause of type query
(zero non-negated literals). I.e., our query is indeed a Horn clause, and of type “query”.
I missed the whole discussion, but the answer - conjunction - seems to be obvious and indisputable.
For instance.
A set of facts means that each fact is true: conjunction.
The standard append program means that its fact AND it rule are true: conjunction.
{a:-b. a:-c.} means that both rules hold: conjunction.