Prolog first steps: predicates, metapredicates, lambdas
Tags: prolog, logicalprogramming, programming
Published: 2024-06-30 00:11:24

I first became interested in Prolog after I watched a talk by Joe Armstrong, creator of Erlang, in which he mentioned this small, niche language twice. The first time, he explains how he took inspiration from the Prolog syntax to write Erlang's. The second, he mentions that if he were to choose only 4 languages to learn, Prolog would be among them.

I have always found it super instructive to learn languages that are very distinct from one another. There isn't much to learn from a third dynamically-typed imperative language. But coming from, say, imperative to fuctional or, in this case, logical paradigm is quite the mind-bending experience. It makes us see things we think we know from a different angle, and provides _new ways of expressing ideas and operations_.

This is my first contact with logical programming, so everything here is basic and rudimentary. It is a first step in learning how logical programming works and why it is interesting.

# Deductions: logical results

Prolog provides a very interesting functionality, one that I haven't seen in other languages. While all languages provide results for problems such as,

> Let X = A, Y = B, what is the result R of X + Y ?

Prolog provides a way to find _all possible values of variables that make a problem true_. For example,

> Let X + Y = R, what are the possible values of X and Y for which R = C

# Predicates: defining our data set

In Prolog, we define _relations between terms_. These relations are called predicates, statements that evaluate to `true`. Let us define some.

```prolog
% astrology.pl 

ruler(aries, mars). 
ruler(taurus, venus). 
ruler(gemini, mercury). 
ruler(cancer, moon). 
ruler(leo, sun). 
ruler(virgo, mercury). 
ruler(libra, venus). 
ruler(scorpio, mars). 
ruler(sagittarius, jupiter). 
ruler(capricorn, saturn). 
ruler(aquarius, saturn). 
ruler(pisces, jupiter). 

element(taurus, earth).
element(virgo, earth).
element(capricorn, earth).
element(aquarius, air).
element(libra, air).
element(gemini, air).
element(pisces, water).
element(cancer, water).
element(scorpio, water).
element(aries, fire).
element(sagittarius, fire).
element(leo, fire).
```

Undefined possible relations such as `ruler(aries, pluto)` evaluate to `false`.

# Queries: deducting results from the data set

Let us generate some new information from the data we have, using logical deduction.

## Get a value from relations

Suppose we have two friends whose star sign we do not know, but for whom we can imagine, from their personality, their ruler planets and elements. We can deduce their signs based on those traits. 

To extract values from queries, we use variables, terms starting with an uppercase letter.

```prolog
?- element(Sign, fire), ruler(Sign, sun).
Sign = Leo.
```

Alfred is has a fiery spirit and a sunny personality. By deduction, his sign is no other than Leo.

```prolog
?- element(Sign, water), ruler(Sign, mars).
Sign = scorpio.
```

Beth loves the ocean, and is very combative, like the god Ares. By deduction, her sign has to be scorpio.

```prolog
?- element(Sign, water), ruler(Sign, venus) .
false.
```

Charles also loves the ocean, and is beautiful like Aphrodite. But there is no sign that fits this combination. Our assumptions about him must be wrong. 


## Get multiple valid results from relations

In our premises, we have not defined any direct relation between planets and elements. However, planets rule signs, therefore we can establish indirect relations. For example, we can ask for planets that have the earth element; in other words, _"what is the planet X that rules some sign Y of the earth element?"_

```prolog
?- element(Y, earth), ruler(Y, X).
Y = taurus,
X = venus ;
Y = virgo,
X = mercury ;
Y = capricorn,
X = saturn.
```

Prolog is telling us that Venus, Mercury, and Saturn are ruled by earth signs (taurus, virgo, capricorn). It is noteworthy in our dataset, while a single _sign_ has a single element (1-n), a single _planet_ may have multiple elements (n-n).

```prolog
?- element(Y, air), ruler(Y, X).
Y = aquarius,
X = saturn ;
Y = libra,
X = venus ;
Y = gemini,
X = mercury.
```

We see that Saturn and Mercury are also air planets in this world.

## Get a list of valid results

As we saw, a planet may have multiple elements based on its ruled signs. Let us try now to get the elements of a certain planet. This time, we will wrap those in a list, using the buit-in predicate `findall/3`.

```prolog
elem(El, Planet) :-
    element(Sign, El), ruler(Sign, Planet).

?- findall(El, elem(El, mercury), Elements).
    Elements = [earth, air].
```    

First, we wrap the same query for elements of some planet from the previous topic in a function (more precisely, in a _conditional predicate_). Functions in Prolog are **Horn clauses**, a form of implication that reverses the position of `p -> q` to `q <- p`, or "q if p", in natural language.

Our Horn clause states that, _"E is the element of a planet P if E is the element of a sign S, and the sign S is the ruler of the planet P"_.

Then we find the elements of the planet Mercury, and throw those in a list. The built-in predicate `findall/3` evaluates all elements for which P(El, ...) is true, and appends them to a list of valid elements.

One amazing feature of Prolog is that, because it deals with values that evaluate to two, the `elem/2` serves not only to find elements of a planet, but also planets of an element! In other words, we can query both `elem(E, mercury)` and `elem(earth, P)`, and both return the valid results that we look for. It is a feature I have never seen in a language.

# Metapredicates

Metapredicates are the logical programming equivalents of _higher-order functions_ in functional programming. They are predicates that have predicates as arguments. The predicate `findall/3` mentioned earlier is such an example.

Metapredicates are very useful generalizations on common operations. We may go beyond the metapredicates already predefined in the standard library, and define our own.

For example, suppose we want to judge whether all planets in a list of planets are rulers of some sign. We may define a predicate `all_rulers`, such as:

```prolog
all_rulers([]).
all_rulers([P|Ps] :-
    ruler(_, P),
    all_rulers(Ps). ?- all_rulers([mercury, sun]).
true

?- all_rulers([mercury, pluto, sun]).
false
```

The predicate is defined recursively, and states that all planets are rulers if the first element of the list is a ruler, and all other elements are also rulers.

Judging whether all elements in a list are true according to some condition is so useful that we would be wise to define a general operation that accepts not just `ruler/2`, but any condition.

```prolog
ruler(P) :- ruler(_, P)

all([], _).
all([E|Es], Pred) :-
    call(Pred, E),
    all(Es, Pred).

?- all([mercury, sun], ruler).
true
```

## Lambdas

We have an inconvenient limitation in our program: `all/2/` only accepts as arguments predicates with _arity_ 1 (i.e. that take one argument). That is becase we make use of `call(Pred, E)`, which applies the current element to the predicate.

To further generalize our metapredicate, we can make use of lambdas, anonymous predicates that allow us not only to apply predicates of different arities, but also to define predicates on runtime.

Let's define another metapredicate `any`, which judges whether any element in a list is valid according to a condition.

```prolog
any([], _) :- false.
any([E|Es], Pred) :-
    call(Pred, E);
    any(Es, Pred).

?- pack_install(lambda).
true.

?- use_module(library(lambda)).
true.

?- any([pluto, mercury, uranus], \X^ruler(_,X)).
true

?- any([pluto, uranus], \X^ruler(_,X)).
false.

```

The metapredicate `any/2` is very similar to `all/2`, except that instead of using AND operators (`,`), it uses OR operators (`;`); in other words, `any/2` is true if the predicate for the first element of the list is true, or if it is true for some other subsequent element.

This time, we are not passing a predicate previously defined in compilation, but rather a dynamic predicate with a lambda (we install and require the `lambda` package first). Lambdas empower us to call a 2-arity predicate such as `ruler/2` by wrapping it in an anonymous 1-arity anonymous predicate.

# Conclusion

Prolog is an interesting language, with a mind-bending paradigm. In this article, we have explore some of its features, such as: 

- getting bidirectional results;
- finding multiple solutions to a problem using variables;
- defining functions as Horn clauses;
- generalizing particular predicates into metapredicates;
- stating anonymous predicates with lambdas.

I hope you liked this article, and I look forward to exploring Prolog further. I have just started using this language, so I apologize for any incorrect terminology or explanations. If you have any comments or suggestions, I'll be happy to read them.