Nondeterministic programming: Difference between revisions

Revision as of 19:05, 21 October 2009

Latest revision as of 12:43, 25 February 2025

(38 intermediate revisions by 29 users not shown)

Line 1:

{{more citations needed|date =April 2017}}

{{Article issues|unreferenced =September 2008|context=August 2009|wikify =December 2008}}

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 (computer programming)|if-then statement]], the method of [[Nondeterministic|choice between these alternatives]] is not directly specified by the programmer; the program must decide at [[Run timeruntime (computingprogram lifecycle phase)|runtimerun 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.

{{Programming paradigms}}

One method of choice is embodied in [[backtracking]] systems (such as [http[Amb (evaluator)|Amb]],<ref>{{Cite web |last= |first= |title=Structure and Interpretation of Computer Programs |url=https://mitpressen.mitwikipedia.eduorg/sicpwiki/full-textStructure_and_Interpretation_of_Computer_Programs}}</sicp/book/node91.htmlref>{{Circular AMB],reference|date=February 2025}} 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.

A '''nondeterministic programming''' language is a [[programming language|language]] which can specify, at certain points in the program (called "choice points"), various alternatives for [[Control flow|program flow]]. Unlike an [[Conditional (programming)|if-then statement]], the method of [[Nondeterministic|choice between these alternatives]] is not directly specified by the programmer; the program must decide at [[Run time (computing)|runtime]] 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.

Another method of choice is [[reinforcement learning]], embodied in systems such as [http[Alisp]].<ref>{{cite journal|author1=David Andre |author2=Stuart J. Russell|title=State abstraction for programmable reinforcement learning agents|journal=Eighteenth National Conference on Artificial Intelligence|date=July 2002|pages=119–125|isbn=978-0-262-51129-2 |url=https://wwwdl.csacm.berkeley.eduorg/~bhaskaradoi/alisp10.5555/ Alisp]777092.777114}}</ref> In such systems, rather than backtracking, the system keeps track of some measure of success and learns which choices often lead to success, and in which situations (both internal program state and environmental input may affect the choice). These systems are suitable for applications to [[robotics]] and other domains in which backtracking would involve attempting to undo actions performed in a dynamic environment, which may be difficult or impossibleimpractical.

One method of choice is embodied in [[backtracking]] systems (such as [http://mitpress.mit.edu/sicp/full-text/sicp/book/node91.html AMB], 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.

==See also==

Another method of choice is reinforcement learning, embodied in systems such as [http://www.cs.berkeley.edu/~bhaskara/alisp/ Alisp]. In such systems, rather than backtracking, the system keeps track of some measure of success and learns which choices often lead to success, and in which situations (both internal program state and environmental input may affect the choice). These systems are suitable for applications to [[robotics]] and other domains in which backtracking would involve attempting to undo actions performed in a dynamic environment, which may be difficult or impossible.

*[[Nondeterminism (disambiguation)]]

*[[:Category:Nondeterministic programming languages|Category: Nondeterministic programming languages]]

*[[angelic non-determinism]]

*[[demonic non-determinism]]

==References==

{{Reflist}}

{{Programming paradigms navbox}}

{{DEFAULTSORT:Nondeterministic Programming}}

[[Category:Computer programming]]

[[Category:Programming paradigms]]

[[Category:Determinism]]