# [TECH] [2021. VI] Elegance of Prolog

>“Language that doesn't change the way one thinks is not worth learning.”

## What is Prolog?
Prolog is, regrettably, somewhat of a living dinosaur among programing languages(1). It is one of the oldest logic programming languages based on procedural interpretation of Horn clauses(2). Its original use-case was for natural language processing, but it has also seen extensive use in theorem proving, expert systems, etc.

The most common programing languages are imperative - they describe the sequence of commands that change the program's state. Prolog, on the other hand, is a declarative language - it describes the logic of computation without specifying the commands needed for its execution. Solving a problem in a declarative language makes one approach it in a completely different way and that shift in thinking is reason enough why a language such as Prolog is worth considering - it deepens the understanding of computing.

## Ask “What?” not “How?”
In imperative paradigm one asks “How?” - how to compute, how to construct, etc. In declarative paradigm the driving question is “What?” - what are the conditions to be satisfied, what is the (full) definition of the object to be examined, etc. More generally, in imperative paradigm one thinks in terms of verbs, while in declarative in terms of nouns and adjectives.

## A small example
Finding the powerset(3) is a good example that illustrates the imperative paradigm, its power and elegance. To find a powerset one needs a clear definition of subset relation. Let the relation corresponding to A⊆B be denoted by `subset(A,B)`. Define `subset(A,B)` as follows:

```
subset([],[]).
subset([X|Ss],[X|Xs]) :- subset(Ss,Xs).
subset(Ss,[_|Xs]) :- subset(Ss,Xs).
```

The first line states that the empty list is it own sublist. The second line states that a list starting with the same term (element) as another list is its sublist if its tail is the sublist of the other list's tail. Finally, the third line states that the list is a sublist of a list starting with a different term is its sublist if it is a sublist of the other list's tail. Indeed, this is the complete description of the subset/sublist relation.

Now, to find the powerset, one needs just a simple query. For example,

```
subset([a,b,c],X).
```

gives what one expects:

```
X = [a, b, c] ;
X = [a, b] ;
X = [a, c] ;
X = [a] ;
X = [b, c] ;
X = [b] ;
X = [c] ;
X = [].
```

## Intrigued?

A good set of problems/puzzles for exploring and learning Prolog is the P-99 set:
=>https://www.ic.unicamp.br/~meidanis/courses/mc336/2009s2/prolog/problemas/ <1> P-99: Ninety-Nine Prolog Problems

# Back matter
## Footnotes
(1) More precisely - a family of programming languages.
(2) A Horn clause is a clause (disjunction of literals) with at most one unnegated literal. They are the basis of logic programming in which they are commonly used to express implication.
(3) The powerset of a set is a set of all its subsets.
## External Links
=>https://www.ic.unicamp.br/~meidanis/courses/mc336/2009s2/prolog/problemas/ <1> P-99: Ninety-Nine Prolog Problems