[Solved]: Proper terminology in Prolog/logical programming theory?

Problem Detail: 

I have a good understanding of how to program using logic languages, but I'm currently writing up a paper describing some of my work, and I wanted to ensure that I wasn't abusing the proper terminology when describing logic languages. I have a few questions:

1. What exactly is a predicate? How does a predicate relate to rules/facts? I.e. are rules predicates but not all predicates facts and rules?
2. What is a clause, and how does it relate to a predicate?
3. When describing how a rule is tested/proven, what is the equivalent term for "calling a function"? Do we say that the rule is called, or that a goal is called?
4. What exactly is a goal? Is a goal equivalent to a query?

Like I said, I have a very good understanding of how Prolog works, just not a good knowledge of the right terms to describe the right things.

Asked By : jmite

Answered By : Daniel Lyons

If you understand Prolog then you're probably fine. The jargon in Prolog-land is not as fixed as you'd expect, because we really only have three things to refer to, with a dozen or more pieces of jargon to use on. These are my working definitions arrived at from reading books and reading/answering questions about Prolog on Stack Overflow. I may have a misconception in here.

This is a Horn clause:

foo(X) :- bar(X). 

It has two components: the head, which is foo(X), and the body, which is bar(Y).

A fact is a Horn clause consisting of just a head:

uncle(bob). 

In ISO Prolog, this is transformed into the equivalent clause:

uncle(bob) :- true. 

Similarly, a Horn clause with only a body is just a goal or a query:

:- uncle(X). 

A predicate is defined by a set of clauses. For instance:

foo(true). foo(X) :- bar(X). foo(X) :- succ(X0, X). 

The predicate foo/1 is thus defined. The 1 there is the arity. Every clause is a rule. I can talk about a bug in the second rule of the predicate or the second clause of the predicate, and in either case I am clearly referring to foo(X) :- bar(X).

"Goal" and "query" can be used interchangeably. You can prove or call a goal. I would "issue" a query, not sure if others would say that. When a Variable is given a value, I would say the variable unifies with value or the variable receives value. A goal, query or call can succeed or fail (not "return true" or "return false"). When it succeeds, its variables will be bound.

So to answer your questions directly:

1. A predicate is a unit of code with a name and arity. It is composed of one or more clauses. Each clause can be a rule or a fact, but that distinction is trivial and fairly useless. A predicate is made up of facts and rules. Every fact and every rule is a clause and implies a predicate.
2. Every clause is an alternative of some predicate. Every predicate has at least one clause.
3. Predicates can be called. Goals can be proven or called. Queries can be satisfied. Rules are not called (instead, they are chosen out of the set of alternatives while evaluating some query). (foo(X), bar(X)) is a compound goal, more likely called a query (but never called a predicate).
4. Goal and query are the same.

This is confusing in Prolog because the same syntax is used everywhere. So when you see foo(X), it might be a fact, or it might be a query. It can be given to a meta-predicate to be proven or it can be used simply as a structure. For instance:

foo(X).           % 1. "fact": foo(X) always succeeds. foo(X) :- true.   % 2. "predicate", same as above :- foo(X).        % 3. goal: prove foo(X). Will succeed without establishing binding. :- call(foo(X)).  % 4. goal, same as above :- write(foo(X)). % 5. struct: print out "foo(_G1657)" (or some other gensym variable name) 

For me, what's still vague is when we refer to a term as a structure versus as a functor. I think these usages are basically interchangeable, but I'm not sure.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12489