Predicate Logic as Programming Language – Kowalski 1974
The purpose of programming languages is to enable the communication from man to machine of problems and their general means of solution.
Kowalski shows us that predicate logic can be used as the basis of a “useful and practical, high-level, non-deterministic programming language with sound theoretical foundations.” This is the foundation for Prolog and Datalog.
As a programming language, predicate logic is the only language which is entirely user-oriented. It differs from existing high-level languages in that it possesses no features which are meaningful only in machine terms.
Sentences are expressed in clausal form with a very simple syntax.
B1,...,Bm <- A1,...,An
which can be interpreted as meaning B1 or … or Bm is implied by A1 and … and An.
It is our thesis, that clausal form defines a natural and useful language in its own right, that thoughts can be conveniently expressed directly in clausal form, and that literal translation from another language, such as full predicate logic, often distorts the original thought.
The Horn clause subset of predicated logic is that where clauses contain at most one disjunction (B) term. This is the form used for computation in the paper.
A simple factorial example is given. Let Fact(x,y) denote the fact that the factorial of x is y, and let s(x) be the successor of x in the natural numbers. Finally, let Times(x,y,z) denote that x * y is z. Then:
-- the factorial of 0 is s(0), i.e. 1 Fact(0,s(0)) <- -- if v is the factorial of x, and s(x) * v is u, then -- the factorial of s(x) is u Fact(s(x),u) <- Fact(x,v), Times(s(x),v,u)
To read these programs, I mentally insert an ‘if’ ; we can deduce the terms on the left if the terms on the right are true. Contrast this to a functional declaration where we mentally insert an ‘is’:
factorial 0 = 1 factorial (n+1) = (n+1) * factorial n
Non-determinism and the potential for parallelism
Predicate logic is an essentially non-deterministic programming language. Non-determinism is due to the fact that a given program and activating goal statement may admit more than a single legitimate computation.
This is nicely illustrated with a program for sorting lists. Let Sort(x,y) denote that y is a sorted version of x; Perm(x,y) that y is a permutation of x; Ord(y) that y is ordered; Del(x,y,z) that deleting x from y results in z; and LE(x,y) that x is less than or equal to y; then:
Sort(x,y) <- Perm(x,y), Ord(y)
Perm(nil,nil) <-
Perm(z,cons(x,y)) <- Perm(z',y), Del(x,z,z')
Del(x,cons(x,y),y) <-
Del(x,cons(y,z),cons(y,z')) <- Del(x,z,z')
Ord(nil) <-
Ord(cons(x,nil)) <-
Ord(cons(x,cons(y,z))) <- LE(x,y), Ord(cons(y,z))
Consider three difference approaches to computing the sorted version of a list based on these declarations:
- Generate a permutation y of x, and then test to see if y is ordered, or
- Generate an ordered list y, and then test to see if it is a permutation of x, or
- Grow increasingly longer ordered subsets of x, adding one element from x at each stage.
Clearly the difference in efficiency can be enormous, but the meaning, as determined by the input-output relation Sort(x,y), computed by the program, is the same. It is in this sense that the sequencing of procedure calls can be said to have no semantics.
This is fundamentally what enables highly-parallel executions in languages such as Dedalus, a Datalog derivative:
The use of parallel processes and co-routines is a particular way of sequencing procedure calls. The possibility of independent parallel processing arises when, for example, different procedure calls in the same body share no variables. In such a case, the independent procedure calls can be activated simultaneously and, given a single processor, their execution sequences can be interleaved arbitrarily.
40 years later, and we’re seeing a mini-revival in interest in Datalog and its derivatives.