Is the definition of "predicate" correct in the Glossary of Terms?

General
1

Hi!

I am looking at this page, where it says that a predicate is a “Collection of clauses with the same functor (name/arity). If a goal is proved, the system looks for a predicate with the same functor, then uses indexing to select candidate clauses and then tries these clauses one-by-one. See also backtracking.”. I.e. this should be a predicate:

parent(X, Y):- mother(X, Y).
parent(X, Y):- father(X, Y).

To me this has a different meaning than the ISO definition: “An identifier or qualified identifier together with an arity.”, which I interpret as:

parent/2

/JCR

2

Very informally, the “predicate” from the SWI glossary is the predicate definition. The part of the ISO document you linked does not use the term “predicate definition” at all, and also doesn’t seem to define “clause” or “predicate clause” at all.

The “predicate” from the ISO document you linked is the “predicate indicator” from the SWI glossary.

2 Likes
3

Difficult stuff. The ISO docs uses predicate, predicate indicator and procedure. I cannot really find the right definitions in the ISO part I document (note that part II has not been implemented by any vendor AFAIK).

I think nobody would disagree that a predicate indicator is name/arity (or name//arity when accepting DCG notation). I never understood the difference between predicate and procedure. ISO says

3.21 built-in predicate: A procedure whose execution is implemented by the processor (see 8).

This (to me) indicate predicate and procedure are synonyms. Before ISO I think the term procedure was rarely used in the context of Prolog.

Does anyone know the history of this terminology?

edit Seems some people here were earlier involved in a StackOverflow discussion on this

It helps a little, notably the quote from “Programming in Prolog (5th ed.)” (Clocksin & Mellish 2003), it is simply said on p. 188"

The collection of clauses for a given predicate is called a procedure .

I’m not terribly happy :frowning: More in general it seems a procedure is claimed to be a reusable piece of code and a predicate is a procedure with a boolean result. That seems to come from mathematical logic, according to Wikipedia. A bit further on this page we find:

Informally, a predicate is a statement that may be true or false depending on the values of its variables.

Now the terminology relation between logic and Prolog is a bit of a mess (think of atom), but the above is really what we are doing and this claims a predicate is a statement. I can live with that :slight_smile:

Maybe this is similar to function, which in many languages also both has a function declaration and a function definition/implementation while we typically simply talk about a function?

I propose to add procedure to the glossary and make some adjustments. Any volunteers?

1 Like
4

According to both Wikipedia and How To Design Programs, a predicate is a function that returns a boolean.

Prolog is unusual in that all “functions” return booleans (making them all predicates), with traditional return values returned via parameters.

5

But would this also qualify as a predicate (what is returned is not a boolean)?

mother(marge, bart).
father(homer, bart).
parent(X, Y):-mother(X, Y).
parent(X, Y):-father(X, Y).

?-parent(X, bart).

6

Note:

?- parent(marge, bart).
true .

?- parent(burns, bart).
false.

So parent(?Parent, ?Child) is a predicate in that its return value is a boolean.

If you put in parent(X, bart)

?- parent(X, bart).
X = marge ;
X = homer.

The returned true is implicit. If you enter

?- parent(X, burns).
false.

you get an explicit false. But either way, the return value is a boolean, making it parent(?Parent, ?Child) predicate.

2 Likes
7

Thanks for clarifying.

1 Like
8

It’s an interesting subject. Note parent(_, bart). returns true. Several truths means true, but it’s more convenient to actually enumerate them. So if a predicate returns a grounded variable, it’s true.

1 Like
9

So the changes would be these?

  1. Change the definition of predicate to “A predicate is a statement that may be true or false depending on the values of its arguments”
  2. Add a definition for “procedure”: “A collection of clauses for a given predicate”.

Please let me know if i can help make the changes to the webpage :slight_smile:

/JCR

10

@joeblog Notably, C++ STL uses “predicate” to mean a function returning a boolean, usually provided as an argument to a library function like find_if(). EDIT: so not a function but a function object. At least here it says "a callable that returns a value testable as bool" :wink:

Every “predicate” in Prolog either succeeds or fails; this is the boolean. SWI-Prolog’s top level in particular does not print out the “true” if there is a binding to be reported, but other Prologs do print the “boolean” always. For example, in GNU-Prolog:

$ gprolog
GNU Prolog 1.4.5 (64 bits)
Compiled Jul  7 2020, 21:25:21 with gcc
By Daniel Diaz
Copyright (C) 1999-2020 Daniel Diaz
| ?- [user].
compiling user for byte code...
foo(bar).

user compiled, 1 lines read - 176 bytes written, 5478 ms

(1 ms) yes
| ?- foo(bar).

yes
| ?- foo(X).

X = bar

yes

(instead of “true” it says “yes”…)

But of course this is not even the full story. Some predicates succeed more than once. Some predicates throw exceptions. You can also easily write something that doesn’t terminate. But they are still called predicates in Prolog, and I guess you can’t know anyway what a predicate does before evaluating it.

1 Like
11

Sorry for the nitpick, but language is kinda important here. I realize that this post is me playing the thought police and I don’t like that, so please take it as just one opinion of a stranger on the internet.

Predicates in Prolog do not return values in the same way that functions do. You can emulate it but it is not the same.

Also, the variable binding that is reported by the top level does not need to be “grounded” (isn’t it rather “ground”? “Grounded” gives off electrical engineering vibes :wink:

But just try this in SWI-Prolog:

?- [user].
|: foo(bar(_)).
|: ^D% user://1 compiled 0.00 sec, 1 clauses
true.

?- foo(X).
X = bar(_17456).

I am also under the impression that “succeeds” is cleaner than “returns true” simply because it isn’t a functions and it doesn’t return, really. It kinda does but again, using language that is so common in other contexts (like any language that lets you write functions) seems to actively lead the mind away from what is really happening.

Or maybe I misunderstand what you meant?

12

The definition that a “predicate is a function that returns a boolean” is nice and simple and clear, so I like it.

Applied to Prolog, I find thinking of its core building blocks as predicates makes program composition much clearer since then it’s simply a series of booleans using commas as ands and semicolons as ors.

13

:smiley: H about “a callable that returns a value testable as bool”?

But then again, those are “functional programming” predicates. Apparently you find them everywhere these days, I didn’t realize that…

Java: Interface Predicate<T>

Javascript: “… callback: function is a predicate, to test each element of the array…”

Haskell: all over the place, really…

You can also find it all over the place when people talk about Python…

I suspect “predicate” is also used when people talk about SQL…

I guess the list goes on.

14

Hmmm. Not sure I like that, though this discussion has not found a conclusion yet. I’m thinking along the line that predicate is an ambiguous reference to either a predicate indicator or a predicate definition and the latter is a synonym for procedure (in the context of Prolog). How correct/wrong is that?

Note we have common sentences such as “Write a predicate that …”.

Checkout the git source (swipl-devel.git). There you find man/glossary.doc which is a LaTeX file that is being pre-processed and which eventually ends up on the web.

2 Likes
15

My opinion: yes, predicate is commonly used to mean either predicate indicator or predicate definition. The context matters. In addition to “Write a predicate that…” we have:

I don’t understand how the predicate foreach/2 really works.

In this example, I am using the predicate indicator but surely I meant to say I don’t understand how the predicate works, right?

My feeling is that when I just say predicate I often mean both the indicator and the definition, since neither can exist without the other. The difference matters only when we need to document a predicate (hehe) like listing/1:

Predicate indicator (Name/Arity or Name//Arity) Lists the indicated predicate

This still doesn’t inform me how the glossary of terms can be improved :frowning: At the moment:

  • The entry for “predicate” is synonymous with “predicate definition”
  • There is no entry for “predicate definition” but the current “predicate” entry is exactly that
  • There is an entry for “predicate indicator” which is not ambiguous
  • There is no entry for “procedure” but this term is not commonly used (is that correct?)

My opinion is that it can all stay as it is, or:

  • Rename “predicate” to “predicate definition”
  • Create a new “predicate” entry that explains the duality of the term
  • (Optional) add “procedure” as a synonym for “predicate definition” and point out that it is not commonly used.

I would like to emphasize that I strongly feel that “predicate” on its own can mean either the definition, or the indicator, or both at the same time.

PS: This re-defining of terms in the glossary is dangerous. Does it mean that docs have to be “upgraded”, so that now the sentence from the listing/1 example above reads:

Predicate indicator (Name/Arity or Name//Arity) Lists the definition of the indicated predicate.

?? This particular example is easy, but doing this properly sounds really unnecessary and takes the docs deeps into legalese territory.

2 Likes
17

I hope my comment won’t just add noise to the conversation but the meaning of “predicate” in the context of Prolog has been a huge source of confusion for me ever since I started learning Prolog and up to the first year and a half of my PhD (I study Inductive Logic Programming).

I remember, when I was first starting out, wondering “OK, so facts and rules are predicates. So what are queries?” because I had been taught the “facts, rules and queries” terminology and I had also been told that rules and facts make up predicates. So I was lost until a light bulb went on in my head, I decided that queries are also predicates and told all about it to anyone who couldn’t run away, with the exuberance of a novice mystic having an epiphany. Lesson number one: don’t trust epiphanies.

Later, in the first year of my PhD I was forced to re-do my early stage report and I had one of my submitted papers cruelly savaged in both cases by reviewers infuriated by my use of “predicate” to mean, well, everything and anything. parent(homer,bart)? A predicate (or worse, a term). parent/2? A predicate. parent(X,Y):- mother(X,Y). parent(X,Y):- father(X,Y).? A predicate. This time, there were no lightbulbs. I sat down and re-read carefully both J. W. Lloyd and the first half of Foundations of Inductive Logic Programming (which first half is basically a retell of most of the material in Lloyd). So now, if you ask me the difference between a predicate definition, a predicate symbol (and arity) and a predicate indicator in Prolog, I’ll know what to say (“Read Lloyd”).

Unfortunately, none of these foundational sources of knowledge for my field and Logic Programming include a definition of “predicate”. That’s right. “predicate” is not defined formally in the main Logic Programming (and ILP) source. What is semi-defined is “predicate symbol”, but “predicate” itself, is not.

So what the hell is a predicate?

I guess I’ll have to read a mathematical logic sourcebook to know for sure, because it seems to me that Logic Programming borrowed the terminology from mathematical logic -and nobody bothered to re-establish it since, well, duh, predicate, everyone knows what that is; I guess. On the other hand, “function” and even “constant” are formally defined in both Lloyd and Foundations of ILP (a constant is a 0-arity function). So why is predicate left hanging?

How about “a predicate is a function that returns a boolean”, that joeblog likes?

I hate it (sorry @joeblog)! I hate it from the point of view of the novice logic programmer I was all those years ago, confused, cold and alone, trying to figure out what this or that formal definition means and what are its implications.

For example, if “a predicate is a function that returns a boolean”- then where is that boolean? I’m a novice, trying to understand Prolog now, eh? Can I do this?

?- parent(_,bart) = true.

If the answer to that is “false”, does it mean that bart has no parent? Does it mean that _ is not bart’s parent? What does it mean? It sure doesn’t mean that parent(_,bart) is true! Because it’s not equal to true! So I’m hopelessly lost again, right when I thought that I’m finally going to understand what those “predicates” are, now that someone has taken the trouble to explain them to me in “nice and simple and clear” terminology that I already intuitively understand (why, I built my own web app in javascript at high school, I understand functions, I’ve written lots of them!).

And wait 'till I decide to dig a little deeper and get my hands on some ancient textbook, like Lloyd, and find out that:

Definition A term is defined inductively as follows:
(a) A variable is a term.
(b) A constant is a term.
(c ) If f is an n-ary function symbol and t_1,…,t_n are terms, then f(t_1,…,t_n) is a term.

Wait. So functions are terms? Aha! That’s why eveything in Prolog is occasionally described as a “term”! It’s because predicates are functions (that return booleans) and functions are terms! Light bulb!

To be fair, Prolog has made a meal of logic programming terminology and there’s no salvaging that with a mere glossary. So I have no suggestsions. I think Jan’s proposal is the most practical one (as usual): point out the confusion (“Teach the controversy!”). A predicate means different things in different contexts and you have to try to understand the context. After that, you’re on your own.

P.S. Lloyd has this to say about “procedures” in logic programming:

"However, what [Kowalski in “Predicate Logic as a Programming Language”] shows is that logic has a procedural interpretation, which makes it very effective as a programming language. Briefly, a program clause A ← B_1,…,B_n is regarded as a procedure definition. If ←C_1,…,C_k is a goal, then each C_j is regarded as a procedure call. A program is run by giving it an initial goal. If the current goal is ←C_1,…,C_k, a step in the computation involves unifying some C_j with the head A of a program clause A←B_1,…,B_n and thus reducing the current goal to the goal ←(C_1,…,C_{j-1},B_1,…,B_n, C_{j+1},…,C_k)θ where θ is the unifying substitution. Unification thus becomes a uniform mechanism for parameter passing, data selection and data construction. The computation terminates when the emtpy goal is produced.

So it is a program clause, not a predicate definition, that is a procedure definition. More confusion, this time with the ISO standard.

1 Like
19

That’s all true (and thanks for pointing out Clark which I didn’t know) but I think the ISO standard is probably the last place a novice programmer will look to for help in understanding what “predicate” means.

In general, there is a lot of subtext in Prolog that is not explained in any one source and that it takes a lot of effort to put together from disparate sources. It reminds me a bit of my frustration with R, the language, and how its peculiarities are often explained by “well, it’s a front-end for S”. Oh, good. What is S?

Edit: Rather, the turn of phrase I’ve often seen is that R “was built on top of S” (not that it’s a front-end for it). Apologies for the terminological blunder. In any case, the point is that if you don’t understand why something is the way it is in R, the answer is often that it was done that weay in S.

21

The query

`?- parent(_,bart) = true.
false.

is very confusing. I’ve no idea how Prolog interprets it. If it was testing for equality, I would think it should be true. If it was assuming = meant assignment, it should throw and error, so I’ve no idea what’s going on.

Edit. After consideration, I’m no longer confused. It’s false for the same reason (X is 1 + 1) = 2. is false. Prolog does not regard that as “is X equivalent to 2?”, but whether the entire statement on the left is the same as the entire statement on the right.

Back to predicates: The tendency of people in different fields to redefine commonly used words into “special cases” just strikes me as blunting language.

I’m in the process of relearning Racket by working through How To Design Programs for the third time, and the thing I love about the Lisp community – especially Matthias Felleisen and the rest of the HTDP team – is their use of language is so clear and refreshing compared to the word salad of jargon which unfortunately is so common in most programming languages.

I’ve also been learning Erlang, watching a lot of the late Joe Armstrong’s talks on youtube, and he was also brilliant at cutting through BS and communicating clearly and simply.

A core idea of Prolog is it is built entirely out of predicates, with “answers” returned as parameters instead of something a function substitutes itself with, a convention I guess started with Fortran, from which nearly every commonly used pogramming language is descended.

Thinking of functorX(arg1,...) :- statement1, statement2... as being a function that returns true or false (and if false meaning I need to include another functorX(diffarg1,...) :-... to match a different case, works for me.

24

It will try to unify the compound term parent(_, bart) with the atom true and fail (to do so).

We don’t have much choice. We hope that we share enough implicit knowledge with the people we are talking to. The other option is to keep on defining the term we are using, using other terms, and then defining those, until we bottom out at what exactly?. One side effect of this is that if we “understand” what the other person is saying, we tend to like it better (the thing and the person…)

And since this thread already drifted enough: talking about computation is necessary, but both dangerous and very easy to overdo. People don’t do the computation; the computer does. Computers, the way I like them, are dumb, predictable, and FAST. You give them a program and they execute it. We can look at the program, we can look at the result, or even at the process. We can “reap the reward”. But talking about it with other humans is just too difficult (… because the program is written by us, but only becomes truly useful when we give it to the computer; only the computer interprets it; we are working with an approximation, a model).

PS: this is one reason why “explain what the program does”, somewhat popular with teachers, irks me a little :slight_smile: look at the code, run it. Whatever I say is going to be a dirty rotten lie :slight_smile:

1 Like
25

The genius of SQL is it only has one type, relations, which allows one to compose any SQL application using relational algebra. (I don’t know how many people lost in the woods of text, number etc realise SQL only has one overarching type, which is where doing an excellent Mooc given by Stanford helps a lot)

Similarly, the genius of Prolog is it only has one overarching type, boolean, allowing all applications to be composed using predicate calculus.

As do all computer languages, SQL and Prolog are cluttered with stuff to manipulate text, numbers, etc. But the fact that they are founded on “algebras”, “calculī”, or whatever you want to call it helps one focus on a bigger picture, and that’s what makes them better than the ubiquitous C-family of programming languages.