The Most Unusual Programming Language

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:

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...

append([1,2,2], [3,6]).

...and then returns the result list:

[1,2,2,3,6]

In Prolog you do it like this:

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:

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:

append([1,2,2], X, [1,2,2,3,6]).

and Prolog outputs

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:

append(X, [3,6], [1,2,2,3,6]).

gives

X = [1,2,2]

We can pretty much put the X anywhere we want:

append([1,2,2], [X,6], [1,2,2,3,6]).

X = 3

We don't have to use X at all actually:

append([1,2,2], [3,6], [1,2,2,3,6]).

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:

append([1,2,2], [3,6], [1,X,X,3,6]).

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:

append([1,2,2], [3,6], [1,X,2,X,6]).

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:

append([1,2,2], [3,6], [1,X,2,Y,6]).

We get an answer again:

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:

append(Prefix, [3,6], [1,2,2,3,6]).

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:

append(ListPopped, [ToRemove], [1,2,2,3,6]).

ToRemove = 6,
ListPopped = [1, 2, 2, 3]

and

append([1,2,2,3], [6], ListPushed).

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:

append([ToRemove], ListShifted, [1,2,2,3,6]),

ToRemove = 1,
ListShifted = [2, 2, 3, 6],

and

append([1], [2,2,3,6], ListUnshifted).

ListUnshifted = [1, 2, 2, 3, 6]

Let's go deeper.

What do you think happens, if we run following program?

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:

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

but if you run this query in the web IDE that I mentioned earlier, you'll notice that Prolog allows you to generate more answers:

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:

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:

length([1,2,2], Len).

Len = 3

We can utilise length together with append as follows:

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:

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).

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:

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.