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

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 2

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.

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.