9 ms·

Nondeterministic programming

64 points by lfborjas 15y ago

yuvadam 15y ago
Nice, but I'm not sure I get it. There is no such thing as a concrete non-deterministic operation. How does the expression evaluate? If all the parameters are evaluated in order, there's nothing non-deterministic about it.
- yogsototh 15y ago
  There is no known real world non-deterministic Turing Machine. We could only simulate it using a deterministic Turing Machine (like a common computer). Using this operator make the code really clear (IMHO) and I suppose it is its purpose. Furthermore, if one day we discover an hardware able to be a non-deterministic Turing machine is discovered, the code will work. [1]: I doubt such an hardware exists. But you could look about quantum computer for something close to what is a non-deterministic Turing machine.
  - szany 15y ago
    Navia Systems is designing nondeterministic hardware. http://www.naviasystems.com/ http://www.naviasystems.com/
    - kd0amg 15y ago
      Maybe I'm missing something, but their web site appears to discuss probabilistic procedures, which is not nondeterminism in the Turing machine sense.
      - szany 15y ago
        No you're right. I missed the "preferring those choices that cause the program to converge meaningfully" part. Sorry. Disregard.
- calibraxis 15y ago
  "Non-deterministic" is a somewhat technical term... Wikipedia gives a good explanation of what aspect of this operation makes it be called nondeterministic. (http://en.wikipedia.org/wiki/Nondeterministic_algorithm http://en.wikipedia.org/wiki/Nondeterministic_algorithm)
- stiff 15y ago
  It is non-deterministic in the sense that the program itself and its inputs are not sufficient to determine the program behavior, as the amb operator creates a set of "possible worlds" in which the same expression has different values. Of course to implement it on a traditional computer, one has to simulate this behavior and decide on some order of evaluation. In SICP, where this is discussed in more depth, one of the exercises asks the reader to modify amb to return a random choice instead of just the subsequent one and this expands the range of problems one can apply this technique to: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-28.html#%_thm_4.49 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-28.html... http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-28.html#%_thm_4.50 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-28.html...
rincewind 15y ago
In arc: http://arclanguage.org/item?id=6669 http://arclanguage.org/item?id=6669
chrisjsmith 15y ago
SICP covers this too: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-28.html#%_sec_4.3 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-28.html... The references are better than the posted link. I have found a couple of uses for this in the past and deparately tried to port the examples to C# (unsuccessfully).
- shriphani 15y ago
  I agree. I had to use NDP for solving a few CSPs recently. SICP was a godsend.
motxilo 15y ago
As a practical use, a while ago I "resolved" the Einstein's Riddle using this operator: http://ticsblog.com/2010/12/07/solving-einsteins-riddle-using-nondeterministic-computing http://ticsblog.com/2010/12/07/solving-einsteins-riddle-usin...
zwischenzug 15y ago
I don't understand the point of the solutions - why is a non-deterministic output of a function better than iterating over a list? If anything, it would be worse.
caioariede 15y ago
In ruby: http://www.randomhacks.net/articles/2005/10/11/amb-operator http://www.randomhacks.net/articles/2005/10/11/amb-operator
- lfborjas 15y ago
  Cool, I was wondering if it could be implemented in ruby; it's a shame that callcc isn't present anymore in ruby 1.9
  - lfborjas 15y ago
    I was wrong, ruby 1.9 has callcc back since 2009, you have to `require 'continuation'` now, though.
gromgull 15y ago
Isn't this just the prolog-ism of backtracking imported into other languages? Especially as long you just evaluate the options in order?
- _delirium 15y ago
  The article mentions that it's related, but somewhat simpler because it's "only" backtracking, versus Prolog's full logic programming: The embedding recalls the continuation strategies used to implement Prolog-style logic programming, but is sparer because the operator provided is much like a Scheme boolean operator, does not require special contexts for its use, and does not rely on linguistic infrastructure such as logic variables and unification.

64 points by lfborjas 15y ago

Nice, but I'm not sure I get it. There is no such thing as a concrete non-deterministic operation. How does the expression evaluate? If all the parameters are evaluated in order, there's nothing non-deterministic about it.

yogsototh 15y ago
There is no known real world non-deterministic Turing Machine. We could only simulate it using a deterministic Turing Machine (like a common computer). Using this operator make the code really clear (IMHO) and I suppose it is its purpose. Furthermore, if one day we discover an hardware able to be a non-deterministic Turing machine is discovered, the code will work. [1]: I doubt such an hardware exists. But you could look about quantum computer for something close to what is a non-deterministic Turing machine.
- szany 15y ago
  Navia Systems is designing nondeterministic hardware. http://www.naviasystems.com/ http://www.naviasystems.com/
  - kd0amg 15y ago
    Maybe I'm missing something, but their web site appears to discuss probabilistic procedures, which is not nondeterminism in the Turing machine sense.
    - szany 15y ago
      No you're right. I missed the "preferring those choices that cause the program to converge meaningfully" part. Sorry. Disregard.
calibraxis 15y ago
"Non-deterministic" is a somewhat technical term... Wikipedia gives a good explanation of what aspect of this operation makes it be called nondeterministic. (http://en.wikipedia.org/wiki/Nondeterministic_algorithm http://en.wikipedia.org/wiki/Nondeterministic_algorithm)
stiff 15y ago
It is non-deterministic in the sense that the program itself and its inputs are not sufficient to determine the program behavior, as the amb operator creates a set of "possible worlds" in which the same expression has different values. Of course to implement it on a traditional computer, one has to simulate this behavior and decide on some order of evaluation. In SICP, where this is discussed in more depth, one of the exercises asks the reader to modify amb to return a random choice instead of just the subsequent one and this expands the range of problems one can apply this technique to: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-28.html#%_thm_4.49 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-28.html... http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-28.html#%_thm_4.50 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-28.html...

rincewind 15y ago

In arc: http://arclanguage.org/item?id=6669 http://arclanguage.org/item?id=6669

chrisjsmith 15y ago

SICP covers this too: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-28.html#%_sec_4.3 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-28.html... The references are better than the posted link. I have found a couple of uses for this in the past and deparately tried to port the examples to C# (unsuccessfully).

shriphani 15y ago
I agree. I had to use NDP for solving a few CSPs recently. SICP was a godsend.

motxilo 15y ago

As a practical use, a while ago I "resolved" the Einstein's Riddle using this operator: http://ticsblog.com/2010/12/07/solving-einsteins-riddle-using-nondeterministic-computing http://ticsblog.com/2010/12/07/solving-einsteins-riddle-usin...

zwischenzug 15y ago

I don't understand the point of the solutions - why is a non-deterministic output of a function better than iterating over a list? If anything, it would be worse.

caioariede 15y ago

In ruby: http://www.randomhacks.net/articles/2005/10/11/amb-operator http://www.randomhacks.net/articles/2005/10/11/amb-operator

lfborjas 15y ago
Cool, I was wondering if it could be implemented in ruby; it's a shame that callcc isn't present anymore in ruby 1.9
- lfborjas 15y ago
  I was wrong, ruby 1.9 has callcc back since 2009, you have to `require 'continuation'` now, though.

gromgull 15y ago

Isn't this just the prolog-ism of backtracking imported into other languages? Especially as long you just evaluate the options in order?

_delirium 15y ago
The article mentions that it's related, but somewhat simpler because it's "only" backtracking, versus Prolog's full logic programming: The embedding recalls the continuation strategies used to implement Prolog-style logic programming, but is sparer because the operator provided is much like a Scheme boolean operator, does not require special contexts for its use, and does not rely on linguistic infrastructure such as logic variables and unification.