Is this Prolog terminology correct? (fact, rule, procedure, predicate, ...)

Question

Getting the terminology correct is part of the success to communicating a concept and when the wrong terminology is used here at SO with the Prolog tag the respondents nicely point out the mistake.

In reading "Clause and Effect - Prolog Programming for the Working Programmer" by William F. Clocksin in 1997 (WorldCat) is the paragraph

A Prolog program consists of a collection of procedures. Each procedure defines a particular predicate, being a certain relationship between its arguments. A procedure consists of one or more assertions, or clauses. It is convenient to think of two kinds of clauses: facts and rules.

While I understand all of the words, is each bold word the currently correct terminology for use when communicating about Prolog?

In particular the use of rule seems to be frowned upon.

Answer 1

From the Prolog ISO Standard

ISO/IEC 13211-1 (First edition 1995-06-01)

Information technology - Programming languages - Prolog

Part 1: General Core

which has an extensive glossary on pages 2-10.

3.6 anonymous variable: A variable (represented in a term or Prolog text by _) which differs from every other variable (and anonymous variable) (see 6.1.2, 6.4.3)

3.7 argument: A term which is associated with a predication or compound term.

3.9 arity: The number of arguments of a compound term. Syntactically, a non-negative integer associated with a functor or predicate.

3.10 assert, to: To assert a clause is to add it to the user-defined procedure in the database defined by the predicate of that clause.

3.19 body: A goal, distinguished by its context as part of a rule (see 3.154).

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

3.32 clause: A fact or a rule. It has two parts: a head, and a body.

3.35 complete database The set of procedures with respect to which execution is performed (see 7.5).

3.37 compound term: A functor of arity N, N positive, together with a sequence of N arguments.

3.45 control construct: A procedure whose definition is part of the Prolog processor (see 7.8).

3.52 database: The set of user-defined procedures which currently exist during execution (see 7.5).

3.57 directive: A term D which affects the meaning of Prolog text (see 7.4.2) and is denoted in that Prolog text by the directive-term :-(D).

3.59 dynamic (of a procedure): A dynamic procedure is one whose clauses can be inspected or altered during execution, for example by asserting or retracting clauses (see 7.5.2).

3.72 fact: A clause whose body is the goal true. NOTE - A fact can be represented in Prolog text by a term whose principal functor is neither (:-)/1 nor (:-)/2.

3.77 functor: An identifier together with an arity.

3.81 goal: A predication which is to be executed (see body, query, and 7.7.3).

3.84 head (of a rule): A predication, distinguished by its context.

3.88 identifier: A basic unstructured object used to denote an atom, functor name or predicate name.

3.96 instantiated: A variable is instantiated with respect to substitution if application of the substitution yields an atomic term or a compound term.

3.113 named variable: A variable which is not an anonymous variable (see 6.1.2, 6.4.3)

A term is instantiated if any of its variables are instantiated.

3.129 predicate: An identifier together with an arity.

3.131 predicate indicator: A compound term A/N, where A is an atom and N is a non-negative integer, denoting one particular procedure (see 7.1.6.6).

3.133 predication: A predicate with arity N and a sequence of N arguments.

3.136 procedure: A control construct, a built-in predicate, or a user-defined procedure. A procedure is either static or dynamic. A procedure is either private or public (see 7.5).

3.141 Prolog text: A sequence of read-terms denoting directives and clauses (see 6.2, 7.4).

3.143 query: A goal given as interactive input to the top level.

3.154 rule: A clause whose body is not the goal true. During execution, if the body is true for some substitution, then the head is also true for that substitution. A rule is represented in Prolog text by a term whose principal functor is (:-)/2 where the first argument is converted to the head, and the second argument is converted to the body.

3.164 static (of a procedure): A static procedure is one whose clauses cannot be altered (see 7.5.2).

3.185 top level: A process whereby a Prolog processor repeatedly inputs and executes * queries.

3.193 uninstantiated: A variable is uninstantiated when it is not instantiated.

3.195 user-defined procedure: A procedure which is defined by a sequence of clauses where the head of each clause has the same predicate indicator, and each clause is expressed by Prolog text or has been asserted during execution (see 8.9).

3.200 variable: An object which may be instantiated to a term during execution.

Notes

Basic overview

h(A,B,C) :- g(A,B),h(B,C),j(A,C).
<------------------------------->  - A (HORN) CLAUSE, which is also a RULE. 
            <------------------>   - BODY of the RULE, which also a GOAL.
                                     ... only one literal: ATOMIC GOAL.
<------>                           - HEAD of the RULE, which can appear
                                     as GOAL depending on context.

f(A,B,C).                          - A CLAUSE with the elided body `true`.
                                     This is a FACT, but _not_ a RULE.
                                     Also called a UNIT CLAUSE.
f(A,B,C)  :- true.                 - Same as above, still not a RULE.
f(A,B,C)  :- !.                    - Is it a RULE? We don't know!

          :- f(A,B,C).             - A DIRECTIVE.
          :- (foo(bar)).           - Another DIRECTIVE.

Slightly different definitions can be found at the entry for Horn Clause a Wikipedia. In particular, "fact" is said to be "a unit clause without variables" - this is not in accordance wit the ISO definition.

The non-terminal indicator

In addition to the predicate indicator notation A/N (functor/arity), there is the notation A//N, which is not in the ISO standard (or not yet, see this draft). It tells the reader that this predicate is used in a Definite Clause Grammar (DCG) and takes 2 hidden arguments for the input "difference list" (or "list difference") pair in addition to the number of arguments indicated.

In the standard proposal indicated above, it is described as:

3.19 non-terminal indicator: A compound term A//N where A is an atom and N is a non-negative integer, denoting one particular non-terminal

Most implementations translate a non-terminal nt//n to a predicate nt/n+2. However, one cannot rely on the precise way of translation and the outcome of calling a non-terminal directly by calling the corresponding predicate, that is, with the same name and two extra arguments is not defined. In particular the second additional argument has to be handled with care. A direct use might violate steadfastness, in particular when using dcg-semicontext.

Note on directive

The directive can be another way of writing a query. From the SICStus Prolog manual:

Queries and directives are ways of directing the system to execute some goal or goals. (...) The principal use for directives (as opposed to queries) is to allow files to contain directives that call various predicates, but for which you do not want to have the answers printed out. In such cases you only want to call the predicates for their effect, i.e. you do not want terminal interaction in the middle of consulting the file.

A directive can also be source file markup, whose position is important (i.e. code meta-information). From the SWI Prolog manual on the module directive:

This directive can only be used as the first term of a source file. It declares the file to be a module file, defining a module named Module.

The predicates used in a directive may be quite peculiar, giving instructions and predicate meta-information to the Prolog processor. From the SWI Prolog manual on "declaring predicate properties":

This section describes directives which manipulate attributes of predicate definitions.

For example, "load the library for constraint logic programming over finite domains":

:- use_module(library(clpfd)).

The rule with the empty head :- foo, which could be interpreted as false :- foo is not used in Prolog to express the constraint "it is never the case that foo". It is used that way in implementations of Answer Set Programming like "ASP Prolog" (which has Prolog-y syntax but otherwise is nothing like Prolog).

Note on built-in predicate

In chapter 8, on page 63, we find:

"A built-in predicate is a procedure which is provided by a standard-conforming processor"

Colloquially, "the built-in predicate is part of the Prolog language". Other predicates may be library predicates which need to be pulled into the Prolog program by appropriate directive. Example from SWI Prolog: library predicates.

Note on fact

Colloquially, a "flat fact" is a fact represented by ground term - a term without variables.

Note on functor

This has nothing to do with the "functor" of Category Theory. On the functor of Category Theory, Wikipedia has this to say:

The word functor was borrowed by mathematicians from the philosopher Rudolf Carnap, who used the term in a linguistic context; see function word.

And on "function word":

In linguistics, function words (also called functors) are words that have little lexical meaning or have ambiguous meaning and express grammatical relationships among other words within a sentence, or specify the attitude or mood of the speaker.

So the choice of "functor" for Prolog is a bit unfortunate.

Additionally, the logician W.V.O Quine uses the word functor in "Predicate Functors Revisited" (and earlier) to describe a combinator that rearranges the arguments of the (atomic) predicate that (syntactically) follows it. See also: "Combinatory Logic - Alternative approaches: basic logic and predicate functors" at the Stanford Encyclopedia of Philosophy.

See also the question Definition of "functor"; Haskell vs. C++.

Note on goal

The goal can be what one would describe as "simple", e.g. p(X), in which case it is an atomic goal, or a tree composed of subgoals e.g. p(X),q(Y) because , is a predication with the principal functor (',')/2.

In fact, goal is generally taken to be anything that can appear as a rule body. For example, p(X) -> q(Y) ; r(Z), with principal functor ; (not ->) is absolutely a goal.

The goal could also be a variable resolving to a goal, which might be passed to a meta-predicate like call/1 for example: X=(Z is 1+2), call(X)..

A variation is the incomplete atomic goal used by a meta-predicate. This names a callable predicate with some arguments "on the left" pre-set. The meta-predicate will adjoin arguments "on the right". This is called a closure although, unlike in functional programming, it isn't actually a function referring to context valid at function creation time.

For example, the three calls all output u v w:

foo(X,Y,Z) :- format("~q ~q ~q\n", [X,Y,Z]).

maplist(foo,    [u],[v],[w]). % call "foo" with 3 arguments
maplist(foo(u),     [v],[w]). % call closure foo(u) with 2 arguments
maplist(foo(u,v)       ,[w]). % call closure foo(u,v) with 1 argument

Note on predicate vs. procedure vs. predicate indicator

This concept of predicate seems to float in the "space of semantics" rather than the "space of syntax":

• the name or declaration of the "predicate thing" is the predicate indicator;
• the definition of the predicate of the "predicate thing" is the procedure (based presumably on code, Prolog or otherwise).

Example:

For the predicate fact of arity 2 which computes the factorial function:

fact/2 is the predicate indicator, and

fact(0,1) :- !.
fact(X,F) :- Xp is (X-1), fact(Xp,Fp), F is (Fp*X).

is the possible corresponding procedure.

In practice, predicate is used to denote any procedure as well and one writes the predicate indicator to identify it.

A procedure which admits to a logical interpretation and allows variables for any of its arguments would a relation in the database interpetation or the logic interpretation of that word.

In "Programming in Prolog (5th ed.)" (Clocksin & Mellish 2003), it is simply said on p. 188 that

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

Note on Prolog text

A "Prolog program" (a term which is not defined in the ISO Standard) would be the colloquial description of a set of Prolog texts to be run by the (possibly standard) processor.

Prolog text also includes text entered at the top level which is not a Prolog program, e.g.

?- X is 5 * 3.
X = 15.

Answer 2

Addendum concerning the usage of the term rule ... "is it cool to use rule?":

The ISO Prolog Standard defines rule on page 8:

3.154 rule: A clause whose body is not the goal true. During execution, if the body is true for some substitution, then the head is also true for that substitution. A rule is represented in Prolog text by a term whose principal functor is (:-)/2 where the first argument is converted to the head, and the second argument is converted to the body.

So "rule" is cool.

It is true the "rule" invokes mainly a piece of declarative knowledge known as the production rule used in forward-chaining (possibly backward-chaining) expert systems like CLIPS, Jess or Drools, where they can have a

• bottom-up logical/deduction interpretation or
• a non-logical state space trajectory interpretation

...possibly with "search". There are also the "Constraint Handling Rules", which are very much forward-chaining rules that can be compiled into Prolog programs and smoothly integrate with Prolog.

P.S.

For an appeal to authority, below is a citation from a blogpost by Robert Kowalski at RuleML.org, written in 2014:

The Sad State Concerning the Relationships between Logic, Rules and Logic Programming

He seems to use:

• production rule for a forward chaining rule,
• reactive rule for an action-inducing rule (which can be given a logical interpretation in an Abductive Logic Programming framework) and
• logic programming clause for, well, the logic programming clause.

Confusions about the relationships between logic, rules and logic programming are endemic in the world of computing.

...

I am particularly sensitive to the claim about the difference between deduction and search, because two of my earliest papers (1, 2) investigated the relationship between deduction and search. In my 2011 book (3), I discuss Thagard’s (4) various claims about logic and rules, and I argue that there are three varieties of production rules:

1. Rules like IF you pass forty Arts courses, THEN you graduate with a B.A. These are logic programming clauses, used to reason forwards from conditions to conclusions.
2. Rules like IF you want to go home for the weekend, and you have the bus fare, THEN you can catch a bus. These are “forward chaining” rules, used to simulate backward reasoning with logic programming clauses, such as, you go home for the weekend, if you have the bus fare, and you catch a bus.
3. Rules like IF you are hungry THEN eat something. These are reactive rules, used to make the conclusion of the rule true whenever the condition of the rule becomes true.

In the book, I argue that reactive rules have a more general syntax than logic programming clauses, and they are also more fundamental.

1. Kowalski, R. (1970), "Search Strategies for Theorem-proving" PDF.
2. Kowalski, R. (1972), "And-or Graphs, Theorem-proving Graphs and Bi-directional Search" PDF.
3. Kowalski, R. (2011) Computational Logic and Human Thinking: How to be Artificially Intelligent, Cambridge University Press. PDF of draft. Worldcat.
4. Thagard, P. (2005) Mind: Introduction to cognitive science. MIT press.