If i read the room correctly, what it says in the current glossary entry (a collection of clauses with the same functor (name/arity)) actually captures the meaning conventionally attributed to “predicate” rather well. So maybe what needs to be changed is the ISO text, leaving the glossary entry untouched?
About the duality of “predicate” either meaning a predicate indicator or a collection of clauses with the same head (procedure), to me predicate indicator just seems to be a name or symbol (that refers to the collection of clauses with the same head). Is this really the meaning of predicate, that “predicate” refers to a name for something? Do we not mean the thing that predicate indicator references when we say “predicate” (i.e. the collection of clauses with the same head)?
In this case it’s imperative languages that are redefining “predicate”, which is a term from First Order Logic (FOL) a.k.a. Predicate Logic, a.k.a. the First Order Predicate Calculus. Informally, in FOL a “predicate” is the name of a relation over entities in the domain of discourse. Still informally, the concept of relation is a generalisation of the concept of function, where in a relation any number of objects are mapped to any number of objects, rather than to a single object. For instance, ƒ:X, Y → Z is a function mapping elements of the sets X and Y to elements of the set Z, ƒ(x,y) is an instance of ƒ and ƒ(x,y) = z is the instance of ƒ that maps x ∈ X, y ∈ Y to z ∈ Z. Whereas p(x,y,z) is the relation p/3 that maps elements of X, Y and Z to each other.
Bottom line: functions have “return” values, relations don’t have return values, predicates are relations, not functions, and predicates don’t have return values.
This also comes from FOL which has no concept of replacing a term by its value. FOL also doesn’t have any concept of substituting variables, for example. FOL only has syntax, the rules that determine whether a formula is a well-formed formula (wff) or not, and the rules of the four logical connectives (∧, ∨, → and ¬) and the two quantifiers, ∀ and ∃.
Everything else belongs to something outside of FOL. The idea of replacing functions with their values comes from algebra, I reckon. The idea of substituting variables for terms (variables, functions or constants) is from proof theory.
Incidentally, FOL has functions, but again those are not the usual functions that are replaced by their values. Functions are defined recursively as follows: a constant, or a variable, is a term. If ƒ is a function symbol of arity n and t₁, ..., tₙ are terms, then ƒ(t₁, ..., tₙ) is a term, sometimes called a functional term, or simply function.
But those functions cannot be replaced by their values in FOL. For example, suppose p(ƒ(x), y) is an atom of the predicate p/2. FOL doesn’t tell you how you can replace ƒ(x) by its value, so there is no way to go from p(ƒ(x), y) to, say, p(2, 1). Various proof procedures let you substitute variables for other terms, so for example under SLD resolution with unification you might end up with an atom p(ƒ(ƒ(x)), y) by substituting x for ƒ(x), but note that again you are not replacing ƒ(x) with a value. You’re only creating a new term.
It’s a bit of a mindbend and it takes a lot time staring at it to get one’s head around. Most of this time is taken letting go of the idea that things are replaced by their values.
Edit: Let’s digest this first but it occurs to me you might be wondering about the value of predicates as true or false. The thing to remember is that FOL predicates dont’ have truth values. Instead, the atoms of predicates are assigned true or false values by an interpretation (literally, an assignment of truth values to predicate atoms). Then the truth value of well-formed-formulae are determined according to the rules of the logical connectives and the two quantifiers, depending on the values of atoms under the current interpretation. Proof procedures are used to determine the truth of well-formed formulae. SLD-resolution is a proof procedure restricted to one kind of well-formed formulae, the Horn clauses.
Oh right. I posted my informal definition of “predicate” earlier, replying to @joeblog having forgotten the discussion up to my reply. My informal definition is that “a predicate is the name of a relation between entities in the domain of discourse”.
But that’s no use in Prolog, where we want to have a name for the expressions we write in a source file. I think the way you explain it makes the most sense, in that (prorgamming) context: a predicate is a name attached to a set of clauses that have the same symbol and arity in their head literal. A “predicate indicator” is simply a short-hand for a predicate that also gives us its arity, so that we can distinguish between predicates with the same symbol but different arities (which are distinct sets of clauses in the source code). So I think it makes sense to say that a predicate indicator is a reference to a predicate with a specific symbol and arity.
To be honest, I’d prefer to separate “predicate” from “predicate definition” because you can have multiple definitions for the same predicate. For instance, I might have two Prolog module files and have a separate definition of the predicate father/2 in each of them, each for a different family, for example. But this could cause even more confusion.
It’s funny but if you go back to the foundational text on logic programming, J. W. Lloyd (“Foundations of logic programming” and note that this is about logic programming in general, not just Prolog, for which you probably want Clocksin & Mellish) he doesn’t use “predicate” or “definition”, much. Rather, he uses program: logic program, definite program, normal program, etc.
All those program’s are sets of clauses. In fact, that’s the definition of a logic program: a set of Horn clauses. Only, if you’re actually coding a logic program you end up creating a whole bunch of sub-programs, that each do different things and it make sense, pragmatically speaking, that you want to know how to refer to those things. In practice, we call them “predicates” so for example append/3 is one predicate, member/2 is another predicate and so on, and I wager that what we think of as a “predicate” also includes sub-predicates, which we often call “auxiliaries”. It’s sub-programs all the way down.
All this is very easy to understand when one is looking at source code where it’s very obvoius where one (sub-) program begins and another ends. But it gets hairy quickly when trying to explain this to newcomers or to speak formally of such things. See again my comment about being confused when I first started coding in Prolog. I think back then my confusion only started to clear up when I read “Prolog and Natural-Language Analysis” by Fernando Pereira and M. Shieber:
Although I had to read it many, many times carefully. Skimming through it again I can’t remember why or where it was that the lightbulb went off, but I remember it as being truly enlightening.
I think the glossary item (and maybe more) should be changed. It is still a bit unclear how. We clearly have a predicate indicator, which is in its full form module:name/arity (or //arity for DCG rules, but let us skip that for now) and in abbreviated form name/arity. Whatever you call it, predicate indicator is the official name in the ISO standard and seems pretty much a “reference to a set of clauses” Just a name (Prolog atom) doesn’t fulfill this role as predicates with the same name and different arities are unrelated. We can also refer to a predicate using [module:]name(…arg…). For example predicate_property/2 does this. That kind of suggests that such a term is a predicate … It is sometimes also called a head. And finally, of course we have the set of clauses that X to a predicate. That is a clear entity you want to be able to talk about.
Somehow during all these years I thought a predicate is the set of clauses and a predicate indicator is the reference to it. That gives all terms a clear role, but it seems wrong
Note that humans often don’t care too much about whether something is a reference or the thing itself. In “Bob is happy”, Bob is clearly a reference to an ever changing set of cells, but we tend to ignore that
As is, the best I can think of is to explain the mess and write that predicate can mean either a reference or the set of clauses. Better solutions are of course welcome.
I think that’s a more detailed and technical definition of a (logical) interpretation than the informal one I gave above: “an assignment of truth values to a predicate’s atoms”.
But note that an interpretation assigns truth values to atoms not to a predicate (in FOL). So in that sense, a predicate is still not a function that returns a boolean. A predicate doesn’t return anything and it doesn’t even have a value.
Another way to look at this is that a “predicate” is a set of atoms (facts) with the same symbol and arity. Atoms can be associated with a true or false value, which is the job of an interpretation, but not a property of the predicate itself.
This makes it harder to explain how and why Prolog “predicates” can be defined as both facts and rules, or a mix of two. I have seen (but I’m not sure where) an intensional definition of a predicate (one composed of a set of rules) referred to as a “name” for the predicate, but that would clearly sow the chaos of confusion far and wide- further and wider than what it already is.
This is only true if your domain is the Herbrand domain or when you define truth as atom diagrams (you can have atom diagrams with or without Herbrand domain). But FOL is not restricted to Herbrand domains and the schoolbook definition of FOL interpretation doesn’t use the diagram approach.
The schoolbook definition of FOL is here:
The diagram approach or the Herbrand domains is from universal algebra and mathematical logic, and usually involves more advanced mathematics. Prolog ows much to these advanced approaches, for example Hebrands theorem makes use of it, which is the grand mother of
all automated theorem proving and of all logic programming.
Edit 29.09.2021:
Nothing prevents you to add all of this to a glossary. Its just a matter of scope.
I’m not sure exactly about the “Herbrand domain”. Do you mean as in a Herbrand interpretation, mapping each constant to itself? Can you give an example?
Ah, with you. I know a “Herbrand domain” as “Herbrand universe” and “atom diagram” as “Herbrand base”. I think we’re just using slightly different terminologies, probably because we’ve studied different texts.
I wish there was an easy accessible resource for the theory behind logic programming - and Prolog in particular. A theory resource for the practicing programmer.
