# Nondeterministic programming

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Nondeterministic_programming
> Markdown URL: https://mediated.wiki/source/Nondeterministic_programming.md
> Source: https://en.wikipedia.org/wiki/Nondeterministic_programming
> Source revision: 1334061725
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Programming paradigm

This article needs more citations. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Nondeterministic programming" – news · newspapers · books · scholar · JSTOR (April 2017) (Learn how and when to remove this message)

A **nondeterministic programming** language is a [language](/source/Programming_language) which can specify, at certain points in the [program](/source/Computer_program) (called "choice points"), various alternatives for [program flow](/source/Control_flow). Unlike an [if-then statement](/source/Conditional_(computer_programming)), the method of choice between these alternatives is not directly specified by the programmer; the program must decide at [run time](/source/Runtime_(program_lifecycle_phase)) between the alternatives, via some general method applied to all choice points. A [programmer](/source/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](/source/Backtracking) systems (such as [Amb](https://en.wikipedia.org/w/index.php?title=Amb_(evaluator)&action=edit&redlink=1),[1][*[circular reference](https://en.wikipedia.org/wiki/Wikipedia:Verifiability#Wikipedia_and_sources_that_mirror_or_use_it)*] or unification in [Prolog](/source/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](/source/Reinforcement_learning), embodied in systems such as [Alisp](https://en.wikipedia.org/w/index.php?title=Alisp&action=edit&redlink=1).[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](/source/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

- [Nondeterminism (disambiguation)](/source/Nondeterminism_(disambiguation))

- [Category: Nondeterministic programming languages](https://en.wikipedia.org/wiki/Category:Nondeterministic_programming_languages)

- [angelic non-determinism](/source/Angelic_non-determinism)

- [demonic non-determinism](/source/Demonic_non-determinism)

## References

1. **[^](#cite_ref-1)** ["Structure and Interpretation of Computer Programs"](https://en.wikipedia.org/wiki/Structure_and_Interpretation_of_Computer_Programs).

1. **[^](#cite_ref-2)** David Andre; Stuart J. Russell (July 2002). ["State abstraction for programmable reinforcement learning agents"](https://dl.acm.org/doi/10.5555/777092.777114). *Eighteenth National Conference on Artificial Intelligence*: 119–125. [ISBN](/source/ISBN_(identifier)) [978-0-262-51129-2](https://en.wikipedia.org/wiki/Special:BookSources/978-0-262-51129-2).

v t e Programming paradigms Imperative Structured Jackson structures Block-structured Modular Non-structured Procedural Programming in the large and in the small Design by contract Invariant-based Nested function Object-oriented Class-based, Prototype-based, Object-based Agent Immutable object Persistent Uniform function call syntax Declarative Functional Recursive Anonymous function (Partial application) Higher-order Purely functional Total Strict GADTs Dependent types Functional logic Point-free style Expression-oriented Applicative, Concatenative Function-level, Value-level Monad Dataflow Flow-based Reactive (Functional reactive) Signals Streams Synchronous Logic Abductive logic Answer set Constraint (Constraint logic) Inductive logic Nondeterministic Ontology Probabilistic logic Query Domain- specific language (DSL) Algebraic modeling Array Automata-based (Action) Command (Spacecraft) Differentiable End-user Grammar-oriented Interface description Language-oriented List comprehension Low-code Modeling Natural language Non-English-based Page description Pipes and filters Probabilistic Quantum Scientific Scripting Set-theoretic Simulation Stack-based System Tactile Templating Transformation (Graph rewriting, Production, Pattern) Visual Concurrent, parallel Actor-based Automatic mutual exclusion Choreographic programming Concurrent logic (Concurrent constraint logic) Concurrent OO Macroprogramming Multitier programming Organic computing Parallel programming models Partitioned global address space Process-oriented Relativistic programming Service-oriented Structured concurrency Metaprogramming Attribute-oriented Automatic (Inductive) Dynamic Extensible Generic Homoiconicity Interactive Macro (Hygienic) Metalinguistic abstraction Multi-stage Program synthesis (Bayesian, by demonstration, by example, vibe coding) Reflective Self-modifying code Symbolic Template Separation of concerns Aspects Components Data-driven Data-oriented Event-driven Features Literate Roles Subjects Comparisons/Lists Comparison (multi-paradigm, object-oriented, functional), List (OO, by type)

---
Adapted from the Wikipedia article [Nondeterministic programming](https://en.wikipedia.org/wiki/Nondeterministic_programming) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Nondeterministic_programming?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.