The Most Unusual Programming Language
Tags: prolog, logic
Published: 2022-03-20 18:10:51

---
title: The Most Unusual Programming Language
published: true
description: Motivating the programming language Prolog
tags: prolog, logic
cover_image: https://upload.wikimedia.org/wikipedia/commons/5/57/Aryballos_owl_Louvre_CA1737.jpg
---

There are many different programming languages and paradigms out there. But I would argue no programming language is so different and unusual as *Prolog*. It really bends your intuitions for what programming even means. Prolog is a so called *logic programming* language. There are no loops, no if-else, no variable assignment (at least not in the way you think). 

If you had any Prolog exposure so far, then probably through a university course. And I also predict you didn't like it. Prolog is such an unusual approach to programming, that it takes a while to overcome the initial confusion and frustration. In my opinion it's worth it though. Mainly just to broaden your horizon. But you'll find that Prolog is exceptionally well suited for solving certain hard problems, to the point that they become trivial.

Now, instead of doing a standard introduction to the language by explaining all the syntax and all the jargon, I just want to showcase one unique Prolog property: A single piece of code can often serve many different functions.

If you want to run the following Prolog snippets, you don't have to install anything. There is a [great online IDE you can use](https://swish.swi-prolog.org/):

![web IDE example query](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/15klk0mnmkatvqrqq6pv.gif)

Ok. In pretty much any programming language you have a way to append (aka. concatenate) two lists (aka. arrays). Maybe you have a function `append` that accepts the two lists as arguments...

```prolog
append([1,2,2], [3,6]).
```
...and then returns the result list:
```prolog
[1,2,2,3,6]
```

In Prolog you do it like this:
```prolog
append([1,2,2], [3,6], X).
```
Syntactically, this still looks like a function call **but it isn't**. This thing does not have a return value. Instead it will use, what looks like a third argument `X` here, to provide the output. If we run this, Prolog outputs:
```prolog
X = [1,2,2,3,6]
```
If you now think: "Oh, that's like in C, where you pass a memory reference as an argument and ..." NO!

`append` describes a *logical* relation between three things: the start of a list, the end of a list and the list as a whole. We can put a capital `X` somewhere and ask Prolog: "What would `X` have to be to make this true?". For example we could also do this:

```prolog
append([1,2,2], X, [1,2,2,3,6]).
```
and Prolog outputs
```prolog
X = [3,6]
```
Now we can already use `append` for two seemingly very different purposes. Concatenating two lists; and also removing a chunk from the beginning of a list. In other programming languages you usually have a separate implementation for this (sometimes called `stripPrefix`). We can take it further:
```prolog
append(X, [3,6], [1,2,2,3,6]).
```
gives
```prolog
X = [1,2,2]
```
We can pretty much put the `X` anywhere we want:
```prolog
append([1,2,2], [X,6], [1,2,2,3,6]).
```
```prolog
X = 3
```

We don't have to use `X` at all actually:
```prolog
append([1,2,2], [3,6], [1,2,2,3,6]).
```
```prolog
true
```
So we can also use `append` to simply check that the third list is in fact the concatenation of the first two lists. Also something that would usually require a separate function (`isAppend` maybe?).

We can also use `X` multiple times:
```prolog
append([1,2,2], [3,6], [1,X,X,3,6]).
```
```prolog
X = 2
```
Here we ask: "What is this item that appears twice in the result list?". Of course, this kind of query doesn't have an answer in all situations. If we rephrase the question like this:
```prolog
append([1,2,2], [3,6], [1,X,2,X,6]).
```
```prolog
false
```
then there is no answer and the query fails. Again, don't think of `false` here as the "boolean return value" of this. It's just how Prolog denotes that this query has no solution.

However, if we do this:
```prolog
append([1,2,2], [3,6], [1,X,2,Y,6]).
```
We get an answer again:
```prolog
X = 2,
Y = 3
```
`X` and `Y` are called variables. Think of them as *holes* that can be filled in different ways. It's Prologs job to figure out what these different ways are. 

In general, everything that starts with a capital letter is a variable. Instead of `X` and `Y` we could also use more expressive names:
```prolog
append(Prefix, [3,6], [1,2,2,3,6]).
```
```prolog
Prefix = [1,2,2]
```

Now, at this point Prolog might look more like an equation solver than a general purpose programming language. Let me get back to more obviously useful applications. What other typical list operations can we implement with this?

JavaScript has `pop()` to remove the **last** element of a list; and `push()` to add a new element **at the end** of a list. In Prolog they are the same. The Only difference is, where you put the variables:

```prolog
append(ListPopped, [ToRemove], [1,2,2,3,6]).
```
```prolog
ToRemove = 6,
ListPopped = [1, 2, 2, 3]
```
and
```prolog
append([1,2,2,3], [6], ListPushed).
```
```prolog
ListPushed = [1, 2, 2, 3, 6]
```

JavaScript also has `shift()` to remove the **first** element of a list; and `unshift()` to add a new element **at the beginning** of a list. Again, in Prolog it's all the same:

```prolog
append([ToRemove], ListShifted, [1,2,2,3,6]),
```
```prolog
ToRemove = 1,
ListShifted = [2, 2, 3, 6],
```
and
```prolog
append([1], [2,2,3,6], ListUnshifted).
```
```prolog
ListUnshifted = [1, 2, 2, 3, 6]
```

Let's go deeper. 

What do you think happens, if we run following program?
```prolog
append(X, Y, [1,2,2,3,6]).
```
We're essentially asking: "What are the two lists I have to append to get `[1,2,2,3,6]`?". Well, there are multiple ways to do it, right? Initially, Prolog gives the slightly un-insightful answer:
```prolog
X = [],
Y = [1,2,2,3,6]
```
but if you run this query in [the web IDE](https://swish.swi-prolog.org/) that I mentioned earlier, you'll notice that Prolog allows you to generate more answers:

![web IDE generate multiple answers](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/omjgzz1irjq5r0p7o6kt.gif)
 
Eventually, Prolog generates all possible ways to **split a list**. At the end Prolog outputs `false` because there are no more possible answers. 

In some programming languages you have a function maybe called `splitAt` to split a list at a specific index. How can we achieve that? Say we want to split the list at index `3`. We would expect the answer:

```prolog
X = [1,2,2],
Y = [3,6]
```

At the moment we split the list *at every possible index*. We get multiple answers because we pose a very general question. If we can make the question more specific, we get a more specific answer. One way to do it, is to insist that the prefix list `X` has length 3. In Prolog, we can relate a list to it's length via `length`:

```prolog
length([1,2,2], Len).
```
```prolog
Len = 3
```

We can utilise `length` together with `append` as follows:

```prolog
length(X, 3), 
append(X, Y, [1,2,2,3,6]).
```
Here we ask: "What is the list `X` of length 3 and the other list `Y` that together form `[1,2,2,3,6]`?". 

*(I know I'm glossing over a lot of details here. I hope it's still enough to get a feel for logic programming.)*

Running this, we get the intended (single) answer:
```prolog
X = [1,2,2],
Y = [3,6]
```

Together with `length` we can also implement other common JavaScript functions like `indexOf`, `lastIndexOf`, `slice`, `splice`. I would have to explain a tiny bit more syntax though, which, I fear, is a more confusing than helpful for now (but if you're interested: [there you go](https://swish.swi-prolog.org/p/JavaScript%20array%20functions%20with%20append/length.pl)).

To wrap it up, I'm going to show you how `append` is implemented. I don't expect you to understand it. Especially because it's recursive, which already is kind of mind bender on its own. I just want you to appreciate how ridiculously short this implementation is:

```prolog
append([], Suffix, Suffix).
append([First|Rest], Suffix, [First|List]) :-
    append(Rest, Suffix, List).
```

3 lines of code! This implementation barely exists and yet it can be used for many different purposes.

I hope I could get across some of the appeal of logic programming. If you are interested in actually learning the language, I recommend [the Power of Prolog](https://www.metalevel.at/prolog).