Nondeterministic programming: Difference between revisions

Revision as of 04:14, 12 August 2021

Revision as of 04:21, 6 September 2021

Line 2:

{{Programming paradigms}}

A '''nondeterministic programming''' language is a [[programming language|language]] which can specify, at certain points in the [[Computer program|program]] (called "choice points"), various alternatives for [[Control flow|program flow]]. Unlike an [[Conditional (programming)|if-then statement]], the method of choice between these alternatives is not directly specified by the programmer; the program must decide at [[run timeruntime (program lifecycle phase)|run time]] between the alternatives, via some general method applied to all choice points. A [[programmer]] specifies a limited number of alternatives, but the program must later choose between them. ("Choose" is, in fact, a typical name for the nondeterministic operator.) A hierarchy of choice points may be formed, with higher-level choices leading to branches that contain lower-level choices within them.

One method of choice is embodied in [[backtracking]] systems (such as [[Amb (evaluator)|Amb]],<ref>https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-28.html#%_sec_4.3.3</ref> or unification in [[Prolog]]), in which some alternatives may "fail," causing the program to backtrack and try other alternatives. If all alternatives fail at a particular choice point, then an entire branch fails, and the program will backtrack further, to an older choice point. One complication is that, because any choice is tentative and may be remade, the system must be able to restore old program states by undoing side-effects caused by partially executing a branch that eventually failed.