Logic vs. imperative programming

Programming with logic

Literally: using mathematical logic for computer programming. Logic is used as a declarative representation language, and as a theorem prover (for problem solving).

• Logic languages like Prolog are Turing-complete, and are typically used for planning, searches, rules and symbolic reasoning.
• Logic programming is declarative programming, and modern functional languages borrow some techniques from it.
• To achieve efficiency and pragmatism, some non-declarative mechanisms are used to control program execution, for example the cut operator in Prolog, which avoids backtracking.

Basic mechanisms of logic programming

1. Computation is about establishing in how many ways a goal can be solved (actually a stream of solutions), with an intrinsic trial-and-error exploration of a search space.
2. A goal is a relation (0-ary, 1-ary, binary, ternary, ...) over data elements, which are essentially untyped trees with holes.

Permutations in imperative programming

In idiomatic imperative programming (Java à la C), at each call the input is updated in place. The next permutation of an array is computed like this (NextPerm.java):

/**
 * works: permutes the input array in-place
 * ends: when no further permutation exists
 */
static boolean nextperm(int[] a) {
  int i, k;
  for (i = a.length - 2; i >= 0 && a[i] > a[i + 1]; i--);
  if (i < 0) {
    return false;
  }
  for (k = a.length - 1; a[i] > a[k]; k--);
  swap(a, i, k);
  k = 0;
  for (int j = i + 1; j < (a.length + i) / 2 + 1; j++) {
    swap(a, j, a.length - k - 1);
    k++;
  }
  return true;
}

/* e.g. */
int[] a = {1, 2, 3, 4};
do {
  System.out.println(Arrays.toString(a));
} while (nextperm(a));

To try it you need a JDK. In a terminal, jshell, then /open NextPerm.java, int[] a = {1, 2, 3, 4}, NextPerm.nextperm(a) and a; NextPerm.main(null) runs it whole, and java NextPerm.java does the same outside jshell.

It needs the input array to be in strictly ascending order, and returns true if the next permutation exists. It prints 24 lines, from [1, 2, 3, 4] to [4, 3, 2, 1].

Permutations in logic programming

In idiomatic logic programming (permutation.pl) the goal is to seek any permutation of a list.

• member/3 relates a list with any element in it, and the rest of the list;
• permutation/2 relates a list with any permutation of it;
• the empty list is a permutation of the empty list;
• given a list L, let H be any element of it, T the rest, and TP any permutation of T: then L has as permutation a list starting with H and having tail TP.

The same 24 permutations, from [1, 2, 3, 4] to [4, 3, 2, 1], with no array, no swapping, no loop, and no notion of "next": the program only says what a permutation is. Prolog explores the alternatives, and the whole set of results is a stream of solutions.

Permutations in functional programming

The Scala version (permutation.scala) produces a stream of permutations. It is highly inspired by idiomatic logic programming: member plays the role of member/3. Note that logic programming somewhat inherently deals with streams of results.

def member[A](l: List[A]): List[(A, List[A])] = l match
  case Nil => Nil
  case a :: t =>
    (a, t) :: (for (a2, l2) <- member(t) yield (a2, a :: l2))

def permutations[A](l: List[A]): Iterable[List[A]] = l match
  case Nil => Iterable(List())
  case _ =>
    for
      (a, l2) <- member(l)
      p <- permutations(l2)
    yield a :: p

To try it you need Scala 3: scala repl permutation.scala loads the file, then ask for permutations(List(1, 2, 3)), and :quit leaves.

Prolog is concise

Prolog solves some problems better than Java or C.

• Pros. If you master Prolog, you can directly and simply capture desired non-trivial behaviour. Prolog syntax and semantics are succinct. (Even though a new paradigm means new computational patterns!)
• Cons. If you do not understand it well, it is a problem. There is no recent, true school of clean coding for Prolog, and tooling is very viscous. Debugging is difficult, and incrementality is key to controlling programs.

Learning Prolog: steps

• Core Prolog: two main mechanisms, resolution and unification; basic goal-resolution examples; programming with lists.
• Full Prolog: additional non-core mechanisms and additional programming techniques.

Mechanism I: resolution

Computing in Prolog means finding one or more positive solutions to a goal (or list of goals): start from the first goal G, find the rules in the program whose head matches G, and for each try to solve the body B of the rule, by solving each goal in B in the same way, recursively. This is the so-called procedural interpretation of Prolog. Since many rules can match, at each step there is a choice that opens alternatives, all to be explored via backtracking.

Mechanism II: unification

A goal expresses a relation (0-ary, 1-ary, 2-ary, ...) between first-order terms. Terms are the data values processed by Prolog: basically untyped trees with functors as nodes, and either constants or variables as leaves. A match between terms is done by the unification algorithm, and returns a substitution that is incrementally refined during resolution. The result of the computation is actually a substitution, in case of success.