Prolog-ic JavaScript

Firstly, a context

Recently, I've started learning programming languages present in amazing Seven Languages in Seven Weeks book by Bruce Tate.

I discovered a very special one - Prolog - as it is a declarative language.

It means, that the programmer does not provide ready implementation, but gives instructions on how to solve the problem and Prolog tries to figure it out.

How does it apply to imperative JavaScript?

• A typical Prolog use cases are things like processing the natural language, specific expert systems, and even AI.

• We use various JavaScript and TypeScript frameworks to specify how an application works and looks like.

So, what do these have in common?
We need to know, what we are trying to achieve.

Prolog is just giving us a lesson on how to ask questions efficiently, not to answer them.

A practical example

My very first thoughts of writing Prolog-based JavaScript algorithms appeared as a result of curiosity.
How do you even translate facts and rules to something that works for JS?

Let's have a look at an example - how list reverse algorithm written in Prolog is similar to a JavaScript one.

Making the question

When we are asking Prolog for a solution, we need to think about what the definition of the reversed list might look like.

One of the most used ideas when you are dealing with lists there
is to use the idea of accumulator - something, that will store the things we already know.

So, our first fact would be that reversing an empty list will result in.. empty list.

However, when we will deal with non-empty lists - we don't know their size.
In such scenarios, recursion is the way to process them.

Therefore, the refined first fact will be that reversing an empty list will result in some list and accumulator will be the same list.

list_reverse_state([], List, List).

The next step is to actually define our expectations for non-empty lists.
It's important to know here that Prolog uses tail recursion, so things can look confusing and out of order, but they actually work.
It sometimes takes a while to understand it, so I placed appropriate comments in the code.

Now we describe a rule, that the current list element needs to be placed before the accumulator (remember when I wrote - the things we already know?), as the original list is slowly going to be emptied.

list_reverse_state([Head|Tail], OutputList, ListStack) :-
  list_reverse_state(Tail, OutputList, [Head|ListStack]).

When it will become empty, the first fact will be met so the output will be the same as the accumulator.

... and that's it for Prolog!

list_reverse_state([], List, List).
list_reverse_state([Head|Tail], OutputList, ListStack) :-
  list_reverse_state(Tail, OutputList, [Head|ListStack]).

Translation to JavaScript

When we review our final question to Prolog above, the things are getting clear - we exactly know what we want to do.

It was a great experience for me, figuring out that the only work needed to be done in JS was to follow the same behavior as described in our question.

It can be actually simplified because the second argument is not needed at all, added it just to show the similarities.

const usePrologStyleList = (array) => {
  const [head, ...tail] = array;
  return [head, tail];
};

const listReverseState = (list, reversedList, acc) => {
  const [head, tail] = usePrologStyleList(list);

  // list_reverse_state([], List, List).
  if (head === undefined) {
    return reversedList = acc;
  }

  // (...) :- list_reverse_state(Tail, OutputList, [Head|ListStack])
  return listReverseState(tail, reversedList, [head].concat(acc));
};

const listReverse = (list) => listReverseState(list, [], []);

Summary

Hopefully, you will discover how appropriate problem descriptions written in declarative language can boost your imperative language skills.

Article cover photo by Michael Dziedzic

Comments

[artydev]

Nice :-)
In case you don't already know, you can look at tau-prolog.org/