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

Another method of choice is reinforcement learning, embodied in systems such as Alisp.[2] 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 impractical.

See also

edit

References

edit
  1. ^ "Structure and Interpretation of Computer Programs".
  2. ^ David Andre; Stuart J. Russell (July 2002). "State abstraction for programmable reinforcement learning agents". Eighteenth National Conference on Artificial Intelligence: 119–125. ISBN 978-0-262-51129-2.

📚 Artikel Terkait di Wikipedia

Nondeterministic algorithm

In computer science and computer programming, a nondeterministic algorithm is an algorithm that, even for the same input, can exhibit different behaviors

Nondeterminism

Nondeterministic programming Nondeterministic algorithm Nondeterministic model of computation Nondeterministic finite automaton Nondeterministic Turing machine

Orc (programming language)

Orc is a concurrent, nondeterministic computer programming language created by Jayadev Misra at the University of Texas at Austin. Orc provides uniform

Nondeterministic finite automaton

symbol is required for each state transition. A nondeterministic finite automaton (NFA), or nondeterministic finite-state machine, does not need to obey these

Curry (programming language)

Curry is a declarative programming language, an implementation of the functional logic programming paradigm, and based on the Haskell language. It merges

Concurrent logic programming

Concurrent Prolog. Concurrent constraint logic programming Logic programming Nondeterministic programming Clark, Keith Leonard; Gregory, Steve (1981). A

ProbLog

(2012). Constraints for probabilistic logic programming. Proceedings of the NIPS Probabilistic Programming Workshop. pp. 1–4. De Raedt, Luc; Kimmig, Angelika

Structure and Interpretation of Computer Programs

a Scheme – Lazy Evaluation Variations on a Scheme – Nondeterministic Computing Logic Programming Designing Register Machines A Register-Machine Simulator