Non-deterministic programming languages

user_238419 0
Viewed 6559

I know in Prolog you can do something like

someFunction(List) :- 
    someOtherFunction(X, List)
    doSomethingWith(X)
    % and so on

This will not iterate over every element in List; instead, it will branch off into different "machines" (by using multiple threads, backtracking on a single thread, creating parallel universes or what have you), with a separate execution for every possible value of X that causes someOtherFunction(X, List) to return true!
(I have no idea how it does this, but that's not important to the question)

My question is: What other non-deterministic programming languages are out there? It seems like non-determinism is the simplest and most logical way to implement multi-threading in a language with immutable variables, but I've never seen this done before - Why isn't this technique more popular?

prolog non-deterministic multithreading functional-programming
8 Answers

Prolog is actually deterministic—the order of evaluation is prescribed, and order matters.

Why isn't nondeterminism more popular?

Nondeterminism is unpopular because it makes it harder to reason about the outcomes of your programs, and truly nondeterministic executions (as opposed to semantics) are hard to implement.

The only nondeterministic languages I'm aware of are

  • Dijkstra's calculus of guarded commands, which he wanted never to be implemented

  • Concurrent ML, in which communications may be synchronized nondeterministically

  • Gerard Holzmann's Promela language, which is the language of the model checker SPIN

SPIN does actually use the nondeterminism and explores the entire state space when it can.

And of course any multithreaded language behaves nondeterministically if the threads are not synchronized, but that's exactly the sort of thing that's difficult to reason about—and why it's so hard to implement efficient, correct lock-free data structures.

Incidentally, if you are looking to achieve parallelism, you can achieve the same thing by a simple map function in a pure functional language like Haskell. There's a reason Google MapReduce is based on functional languages.

Norman_Ramsey_416610

The Wikipedia article points to Amb which is a Scheme-derivative with capacities for non-deterministic programming.

As far as I understand, the main reason why programming languages do not do that is because running a non-deterministic program on a deterministic machine (as are all existing computers) is inherently expensive. Basically, a non-deterministic Turing machine can solve complex problems in polynomial time, for which no polynomial algorithm for a deterministic Turing machine is known. In other words, non-deterministic programming fails to capture the essence of algorithmics in the context of existing computers.

The same problem impacts Prolog. Any efficient, or at least not-awfully-inefficient Prolog application must use the "cut" operator to avoid exploring an exponential number of paths. That operator works only as long as the programmer has a good mental view of how the Prolog interpreter will explore the possible paths, in a deterministic and very procedural way. Things which are very procedural do not mix well with functional programming, since the latter is mostly an effort of not thinking procedurally at all.

As a side note, in between deterministic and non-deterministic Turing machines, there is the "quantum computing" model. A quantum computer, assuming that one exists, does not do everything that a non-deterministic Turing machine can do, but it can do more than a deterministic Turing machine. There are people who are currently designing programming languages for the quantum computer (assuming that a quantum computer will ultimately be built). Some of those new languages are functional. You may find a host of useful links on this Wikipedia page. Apparently, designing a quantum programming language, functional or not, and using it, is not easy and certainly not "simple".

user_2542790

I believe Haskell has the capability to construct and non-deterministic machine. Haskell at first may seem too difficult and abstract for practical use, but it's actually very powerful.

user_2644870

Java 2K

Note: Before you click the link and being disappointed: This is an esoteric language and has nothing to do with parallelism.

user_1024980
Related