23

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?

Tom Zych
  • 13,329
  • 9
  • 36
  • 53
BlueRaja - Danny Pflughoeft
  • 84,206
  • 33
  • 197
  • 283
  • And yes, this is very similar to my last question: http://stackoverflow.com/questions/2174535/multithreading-in-functional-languages-prolog I am asking a new question because apparently I worded the last one very poorly; everyone began arguing about the specifics of Prolog, but I don't really about Prolog. – BlueRaja - Danny Pflughoeft Feb 02 '10 at 15:40
  • Google, helps, mostly. E.g: http://en.wikipedia.org/wiki/Nondeterministic_programming is what I found. Does that help? – dirkgently Feb 02 '10 at 15:42
  • That gives a few (3) examples, but doesn't really explain why non-determinism is not used in, for example, most functional languages – BlueRaja - Danny Pflughoeft Feb 02 '10 at 15:55
  • 1
    It might help to ask what happens when you reverse the clauses. ie what does `someFunction(List) :- doSomethingWith(X), someOtherFunction(X, List)` do? Is it different? Should it be? I would recommend The Reasoned Schemer (http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=10663) if you really want to understand Prolog actually works. – Nathan Shively-Sanders Feb 03 '10 at 14:25
  • 1
    @Nathan: ...what would it do? It would give the same results, no? Just with different performance? – BlueRaja - Danny Pflughoeft Feb 03 '10 at 15:14
  • Yes, if by 'different performance' you mean 'sometimes never finishes doSomethingWith, depending on its code'. :) It is very easy to write logic programs whose first term is constructed in such a way that it generates an infinite number of values *before* the runtime feeds them to the second term. The Reasoned Schemer is the best way to understand this that I know of. I realise that you said understanding how Prolog works is not important to the question, but I think it actually is, eg it's why Norman Ramsey points out that Prolog *is* deterministic. – Nathan Shively-Sanders Feb 03 '10 at 19:07
  • @Nathan: Interesting. It seems to me that in this case, the compiler should be able to look ahead and see that the number of valid `X` will become finite due to `someOtherFunction(X, List)`, but I imagine knowing in the general case if the number of X satisfying a function will be finite or infinite is unsolvable... or is it? How does Prolog generate these terms as it is? It can't just try every possible X, or even a function like `IsBetweenFiveAndTen` would loop indefinitely... or does it already? Ay-yah, my brain hurts. – BlueRaja - Danny Pflughoeft Feb 03 '10 at 19:33
  • Interesting new language research by IBM and Portland State U using non-deterministic languages for concurrency: http://stefan-marr.de/renaissance/ – belwood Jan 03 '15 at 06:37
  • There is also: https://en.wikipedia.org/wiki/Curry_(programming_language) – Agnishom Chattopadhyay Oct 11 '17 at 02:08
  • "with a separate execution for every possible value of X that causes someOtherFunction(X, List) to return true!" that's a usual hype-y formulation, but in reality, *all* the values of `X` that are produced by preceding stages of the computation are tried by `someOtherFunction(X, List)`, and those that cause it to fail are automatically dropped, because the computation continues only if previous stage didn't fail. So it is simple generate-and-test model. Prolog predicates can be modeled as nested loops (each inside a conditional), with the answer generated by the innermost loop. – Will Ness Jun 17 '19 at 17:42

8 Answers8

22

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
  • 198,648
  • 61
  • 360
  • 533
  • I'm sure you can *achieve* the same thing with `map`, but I'm not so sure it's as trivial as you make it sound. For instance, the code I gave has nothing to do with iterating the elements of `List` - `someOtherFunction()` could be anything at all (ex. the checksum of `List` has `X` bits set)! There is also non-determinism in functions - in Prolog, you can write several definitions of a function, and all of them will be called (if any return true, the result is true). *Why* would it be hard to execute this using separate threads? Since all variables are immutable we don't need locks, right? – BlueRaja - Danny Pflughoeft Feb 03 '10 at 14:02
  • @Transfinite Numbers, Prolog is fully deterministic. It explores all options on a rigidly prescribed order. – vonbrand Oct 03 '19 at 21:46
  • In pure Prolog, if you have a finite answer set, the order doesn't matter. The program will return the same answer set, irrespective how you order the execution. Similarly in Answer Set Programming (ASP) an extension of Prolog which allows disjunctive heads and constraints but has a further level of non-determinism. ASP can generate different answer sets. –  Oct 04 '19 at 08:36
5

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".

Thomas Pornin
  • 72,986
  • 14
  • 147
  • 189
5

One example of a non-deterministic language is Occam, based on CSP theory. The combination of the PAR and ALT constructs can give rise to non-deterministic behaviour in multiprocessor systems, implementing fine grain parallel programs.

When using soft channels, i.e. channels between processes on the same processor, the implementation of ALT will make the behaviour close to deterministic†, but as soon as you start using hard channels (physical off-processor communication links) any illusion of determinism vanishes. Different remote processors are not expected to be synchronised in any way and they may not even have the same core or clock speed.

†The ALT construct is often implemented with a PRI ALT, so you have to explicitly code in fairness if you need it to be fair.

Non-determinism is seen as a disadvantage when it comes to reasoning about and proving programs correct, but in many ways once you've accepted it, you are freed from many of the constraints that determinism forces on your reasoning.

As long as the sequencing of communication doesn't lead to deadlock, which can be done by applying CSP techniques, then the precise order in which things are done should matter much less than whether you get the results that you want in time.

It was arguably this lack of determinism which was a major factor in preventing the adoption of Occam and Transputer systems in military projects, dominated by Ada at the time, where knowing precisely what a CPU was doing at every clock cycle was considered essential to proving a system correct. Without this constraint, Occam and the Transputer systems it ran on (the only CPUs at the time with a formally proven IEEE floating point implementation) would have been a perfect fit for hard real-time military systems needing high levels of processing functionality in a small space.

Mark Booth
  • 7,605
  • 2
  • 68
  • 92
4

In Prolog you can have both non-determinism and concurrency. Non-determinism is what you described in your question concerning the example code. You can imagine that a Prolog clause is full of implicit amb statements. It is less known that concurrency is also supported by logic-programming.

History says:

The first concurrent logic programming language was the Relational Language of Clark and Gregory, which was an offshoot of IC-Prolog. Later versions of concurrent logic programming include Shapiro's Concurrent Prolog and Ueda's Guarded Horn Clause language GHC. https://en.wikipedia.org/wiki/Concurrent_logic_programming

But today we might just go with treads inside logic programming. Here is an example to implement a findall via threads. This can also be modded to perform all kinds of tasks on the collection, or maybe even produce agent networks towards distributed artificial intelligence.

2

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.

Dan Mantyla
  • 21
  • 1
1

Java 2K

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

Janus Troelsen
  • 20,267
  • 14
  • 135
  • 196
Meinersbur
  • 7,881
  • 1
  • 27
  • 29
  • When I said "non-deterministic," I meant that the program takes every path. This program is not non-deterministic in that sense, even though it is definitely not deterministic. – BlueRaja - Danny Pflughoeft Feb 02 '10 at 16:54
1

The Sly programming language under development at IBM Research is an attempt to include the non-determinism inherent in multi-threaded execution in the execution of certain types of algorithms. Looks to be very much a work in progress though.

MilesHampson
  • 2,069
  • 24
  • 43
1

There is a programming language for non-deterministic problems which is called as "control network programming". If you want more information go to http://controlnetworkprogramming.com. This site is still in progress but you can read some info about it.

cpxx
  • 11
  • 1