Multithreading in… functional languages? (Prolog)

Question

When my friend started learning Prolog in school, I made fun of him for learning a useless language. However, he's showed me some stuff I never even knew possible; I want to know where this technique comes from.

The technique is this:

permutation(List) :-
    isAMember(X, List),
    deleteFirstElement(X, List, Substring),
    % and so on

In this code, isAMember(X, List) is a function that returns true if X is in List. However, up to this point X is not defined as a variable - so the program will spawn a bunch of new threads, one for each possible value of X that makes isAMember(X, List) true, and continue from there.

This allows us to create a multi-threaded algorithm in the simplest, most elegant way I could have ever imagined possible.

So my question is: Is this Prolog-specific, or a feature of all logical- and/or functional-languages? Also, where can I learn more amazing multithreading techniques like this - this is surely the future of programming.

Answer 1

The subset of Prolog known as "Datalog" is restricted to pure logical features (no "cut"), and in principle, the proof search could be done in parallel. However you'd have to be careful because the semantics of full Prolog is quite sensitive to the order in which results are produced, and some real Prolog programs depend on this.

The situation in pure functional languages like Haskell and Clean is a bit better—it is always safe to evaluate subexpressions in parallel—but there are many challenges of performance. If you do extreme parallelism (every subexpression) you don't get any performance gains because of all the overhead. The promising approaches at the moment seem to be

• Threads (Concurrent Haskell)

• Data Parallel Haskell

• "Sparks" with par and seq operators.

The parallel functional stuff has been around for almost 30 years and people are still trying to make it perform well. If you want more information, try

• Recent proceedings of the ACM Symposium on Haskell (and before that, the Haskell workshop)

• The work of Arvind at MIT, who was a great pioneer in this area (check out his book with R. Nikhil on parallel programming with pH)

Answer 2

If I remember my Prolog correctly, you aren't creating threads, but instead each possible instantiation of X is tried in turn, using backtracking and unification. It is quite serial.

EDIT: Apparently there are some experimental parallel prologs out there, for example, Reform Prolog. However, this is not the norm in Prolog implementations, as far as I can tell.

Answer 3

Honestly, what you've shown doesn't seem any different from a list comprehension, possibly combined with a foreach:

foreach {x | x in List}
    deleteFirstElement(x, List, Substring) 
    // not sure what deleteFirstElement does, so...

As you mentioned that isAMember could be anything, List Comprehension can be more complicated also

foreach {x | x in List if x % 2 == 0} // ie, even elements of List

Along the same lines, you can do the same thing without list comprehension

new_list = old_list.every { x | x % 2 == 0 }

which can be broken into threads just as easy.

Answer 4

isAMember(X, List) will not create threads, prolog logic just relies heavely on recursion and backtracking and is quite procedural unless you explicitly create threads.

In the case of isAMember(X, List), you're looking at the unification concept. that function will unify with all values that evaluates that function to true, in this case, all elements contained in the list. And proceed with the execution with X.

Once the execution has reached a leaf, it will backtrack to the earliest possible "still-unifiable" call (or cut-point, I think, can't remember the correct term), say isAMember(X, List), will unify X to the next candidate, and resume execution.

Dare I say, if you're not careful in your logic, you can easely get stack overflows.