Nondeterministic Programming
What is it?
Nondeterministic Programming (NDP) is a method of writing a program where you explore various alternatives and only execute the ones that work. In a practical way, programs that use NDP look something like this.
- Do something.
- Branch on some kind of choice.
- Execute the following code according to that choice.
- If you encounter some kind of contradiction, then give up this branch and go back to #2 with a different choice.
- If you run out of choices, then the whole process starting at #1 is a failure.
It's kind of neat since it allows you to write programs more like the way we think. For instance, you can explore the upcoming moves in a chess game, refusing to explore further the ones that are non-sensical by putting in a condition that says as much. You also refuse to explore the ones that lead to you losing more than you gain. In the end, the branches that don't look terrible are possible results.
The point of NDP is to not write the parts that choose, but simply to write code explaining what the choices are and what is acceptable and what is not. Some other program, perhaps the program evaluator, will do all the work of choosing which branch to follow when, and perhaps even cleaning up any mess left behind.
See SICP for the chapter on Non-Deterministic Programming at http://mitpress.mit.edu/sicp/full-text/sicp/book/node88.html .
NDP in Python
I am thinking of writing a small module that will do NDP in Python. Here are my earliest thoughts.
NDP in SICP suggests using only one basic function: amb. amb takes zero or more arguments representing alternate values that could be used as the evaluation of the amb function. amb with no arguments, or amb where all values lead to failure, is considered a failure. The evaluator does all the work of choosing which values to use for each amb, remembering the choice points, and exploring alternate branches, as well as restoring program state to the way it was when amb was called.
Since I don't have the luxury of rewriting Python to support NDP, or at least I doubt the Python community would accept such a patch since NDP is so complicated, I am suggesting an alternate interface that will perhaps make NDP more accessible and easier to manage.
I propose one function, "choose". "choose" takes zero or more arguments, like "amb". However, the arguments must all be callables of some sort. "choose" will choose one of the arguments and call it. If the callable evaluates to a value, then that is the result of "choose". If it throws an exception, then that exception is thrown. If the callable throws a "NoChoicesLeft" exception, then an alternate choice is attempted until no choices are left. At that point, the "NoChoicesLeft" exception is thrown.
In code, the most naive implementation would be:
class NoChoicesLeft(Error): pass
def choose(*choices):
for choice in choices:
try:
return choice()
except NoChoicesLeft:
continue
More intelligent "choose" functions can be written, such that they can optimize choices based on a variety of parameters.
Note that in the Python version, no attempt is made at "cleaning up" after a choice is attempted. The coder will have to ensure that each of the methods called doesn't have any harmful side-effects. For instance, while they may log to files, they won't change the values of important variables. If they read through a file, they will restore the file to its state before the choice was attempted. Caches may be updated, but appropriately.
Additional supporting functions could be introduced, much like "require". Functions like "any-element-of" would take a callable and possible parameters to the callable instead of behaving like "amb".
