Prolog: Part 1

Prolog is a fun and rewarding programming language. The elegance of predicate logic cannot be denied.

If you get through all of the blogs in this series, I promise this meme will never apply to us. Let's jump right in.

Clauses

Clauses in Prolog are statements of truth in a specific domain. Clauses do not provide instructions on how to solve any particular problem. Instead, Prolog uses clauses to determine how to produce a solution via a combination of depth first search (DFS), unification, and backtracking through the solution space.

Note: not all problems have pure declarative specifications, so sometimes extralogical statements are needed.

There are two types of clause: facts and rules.

Facts are of the form: head. (with full stop)

  • head is called the head of the clause (or the head of the rule)

The head of a clause can also be viewed as a goal or something you are trying to prove, with the components of its body viewed as subgoals, or things you need to prove in order to prove the head.

Rules are of the form: head:-t1,t2, ... , tk. (k>=1, with full stop)

  • :- is called the neck of the clause (or the "neck operator") and can be thought of as "implies." Notably, the neck operator points to the left, which is unlike the implies arrow in predicate logic, which points to the right. In other words: in Prolog, body implies head.
  • t1,t2, ... , tk. is called the body of the clause (or the body of the rule). It specifies the conditions that must be met in order for the conclusion, represented by the head, to be satisfied. The body consists of one or more components, separated by commas. The components are goals.

Example: <functorX>(s, X):-<functorY>(X),<functorZ>(X)

Syntax of terms

Prolog's syntax is extremely simple. Everything in Prolog is a "term." There are 3 kinds of terms:

  • Constants: names an individual (atoms, symbols)
  • Compound terms: names an individual with parts. For example, here is a compound term with an arity of 3: <functor>(C1, C2, C3)
  • Variables: individuals unable to be named. Note: variables in Prolog are generally not assigned a value by the programmer (remember, Prolog is declarative). Rather, variables are handled by Prolog unification

Unification

To understand unification of terms, start by representing terms as trees. Then, note all of the co-referring variables, and begin processing using DFS. Perform an analysis at each position for unification. Remember, two predicates with different functor names can't unify.

In this example, you can see that the following terms unify:

  • f(X, a(b, c))
  • f(d, a(Z, c))

Consider the following terms. Do they unify?

  • g(Z, f(A, 17, B), A + B, 17)
  • g(C, f(D, D, E), C, E)

If we take a look at a the pictorial representation our terms, we can see that they do unify when we apply Robinson's Unification Algorithm:

Z/17+17,C/17+17,A/17,D17,B/17,E/17

Comments