It looks familiar, yet is still quite alien.

Here is a simple Erlang function that removes the first occurrence of an element from a list:

1
2
3
4
5
6
7

del(X, List) ->
    del(X, List, []).

del(X, [X|Tail], Acc) ->
    lists:reverse(Acc) ++ Tail;
del(X, [Y|Tail], Acc) ->
    del(X, Tail, [Y|Acc]).

Here is something similar in Prolog:

1
2
3
4

del(X, [X|Tail], Tail).

del(X, [Y|Tail], [Y|Result]) :-
    del(X, Tail, Result).

Both snippets look quite a bit alike – and that’s because Erlang began life as Prolog. Joe Armstrong tells it like so (Seibel 2009, 221–222):

So what happened was, first of all it was just Prolog. I sort of made a little language and people started using it. And then Robert Virding came along and said, “Hey, this looks like fun.” […] We met up with them once a week for about, I can’t remember, six months, nine months. And the general idea was we would teach them how to program and they would teach us about telephony – what the problem was. […] – they measured the performance of it [proto-Erlang] and said “It’s gotta be 70 times faster.” […] So then Mike [Williams] did the virtual machine in C and I did the compiler in Prolog. Then the compiler compiled itself and produced byte-code and you put it in the machine and then we changed the grammar and the syntax and compiled the compiler in itself and came out with an image that would bootstrap and then we’re flying. We’ve lost our Prolog roots and we’re now a language.

So the delightful atoms and pattern matching of Erlang can be traced back to Prolog. The main difference between the two is that while Erlang functions always return a value and we need to specify how the Acc variable should be used, in Prolog neither of these is really happening. Instead we ask whether the rules we declared are true for certain values.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

?- del(a, [a,b,c], [b,c]).
true.

?- del(a, [b,a,c], [b,c]).
true.

?- del(a, [b,c,a], [b,c]).
true.

?- del(a, [b,c], [b,c]).
false.

Prolog will tell us that by removing a from [a, b, c] we’ll end up with [b, c]. This also holds for a couple different permutations of the list ([b, a, c], [b, c, a]). We can also see the lovely Erlang-esque pattern matching in action.

Not only can we ask Prolog to test the rule with specific values, we can also task it to figure out values that would make the rule true.

1
2

?- del(a, [a, b, c], Result).
Result = [b, c].

Obviously Prolog will suggest that Result = [b, c]. This is not unlike what our Erlang function would have done.

The Weird Stuff

Here comes the weird part:

1
2
3
4

?- del(a, List, [b, c]).
List = [a, b, c];
List = [b, a, c];
List = [b, c, a].

Instead of removing a, we want to figure out what values of List would become [b, c] by removing a from them. And Prolog will suggest that [a, b, c], [b, a, c] and [b, c, a] would all work.

Although our rule is called del/3, which suggests that it’s a function that deletes an entry from a list, that’s clearly not what’s really happening. We could even ask the following to figure out if the lists differ by one element and what that one element is:

1
2

?- del(X, [a, b, c], [b, c]).
X = a.

We can even define the opposite of del thus:

1
2

insert(X, List, Result) :-
    del(X, Result, List).

Ie. the list into which X was inserted is the list from which X was deleted in order to produce the list List. This Result could be any of the three candidates:

1
2
3
4

?- insert(a, [b, c], Result).
Result = [a, b, c];
Result = [b, a, c];
Result = [b, c, a].

Logically this makes sense. Procedurally it feels completely backwards & bizarre.

Weird stuff.

Sources

  • Bratko, I. (2012) Prolog programming for artificial intelligence. Addison-Wesley. 978-0-321-41746-6.
  • Seibel, P. (2009) Coders at work: reflections on the craft of programming. Apress. 978-1-4302-1948-4.