DEV Community

Cover image for The Most Unusual Programming Language
Niklas Gruhn
Niklas Gruhn

Posted on

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:

web IDE example query

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]).
Enter fullscreen mode Exit fullscreen mode

...and then returns the result list:

[1,2,2,3,6]
Enter fullscreen mode Exit fullscreen mode

In Prolog you do it like this:

append([1,2,2], [3,6], X).
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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]).
Enter fullscreen mode Exit fullscreen mode

and Prolog outputs

X = [3,6]
Enter fullscreen mode Exit fullscreen mode

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]).
Enter fullscreen mode Exit fullscreen mode

gives

X = [1,2,2]
Enter fullscreen mode Exit fullscreen mode

We can pretty much put the X anywhere we want:

append([1,2,2], [X,6], [1,2,2,3,6]).
Enter fullscreen mode Exit fullscreen mode
X = 3
Enter fullscreen mode Exit fullscreen mode

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

append([1,2,2], [3,6], [1,2,2,3,6]).
Enter fullscreen mode Exit fullscreen mode
true
Enter fullscreen mode Exit fullscreen mode

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]).
Enter fullscreen mode Exit fullscreen mode
X = 2
Enter fullscreen mode Exit fullscreen mode

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]).
Enter fullscreen mode Exit fullscreen mode
false
Enter fullscreen mode Exit fullscreen mode

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]).
Enter fullscreen mode Exit fullscreen mode

We get an answer again:

X = 2,
Y = 3
Enter fullscreen mode Exit fullscreen mode

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]).
Enter fullscreen mode Exit fullscreen mode
Prefix = [1,2,2]
Enter fullscreen mode Exit fullscreen mode

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]).
Enter fullscreen mode Exit fullscreen mode
ToRemove = 6,
ListPopped = [1, 2, 2, 3]
Enter fullscreen mode Exit fullscreen mode

and

append([1,2,2,3], [6], ListPushed).
Enter fullscreen mode Exit fullscreen mode
ListPushed = [1, 2, 2, 3, 6]
Enter fullscreen mode Exit fullscreen mode

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]),
Enter fullscreen mode Exit fullscreen mode
ToRemove = 1,
ListShifted = [2, 2, 3, 6],
Enter fullscreen mode Exit fullscreen mode

and

append([1], [2,2,3,6], ListUnshifted).
Enter fullscreen mode Exit fullscreen mode
ListUnshifted = [1, 2, 2, 3, 6]
Enter fullscreen mode Exit fullscreen mode

Let's go deeper.

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

append(X, Y, [1,2,2,3,6]).
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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:

web IDE generate multiple 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]
Enter fullscreen mode Exit fullscreen mode

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).
Enter fullscreen mode Exit fullscreen mode
Len = 3
Enter fullscreen mode Exit fullscreen mode

We can utilise length together with append as follows:

length(X, 3), 
append(X, Y, [1,2,2,3,6]).
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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).
Enter fullscreen mode Exit fullscreen mode

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.

Top comments (0)