162:), 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.
22:
146:
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.
173:. 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
366:
272:
336:
285:
191:
435:
370:
39:
177:
and other domains in which backtracking would involve attempting to undo actions performed in a dynamic environment, which may be difficult or impractical.
265:
499:
849:
711:
855:
258:
1040:
788:
86:
58:
508:
135:
139:
105:
65:
880:
560:
504:
221:
740:
613:
544:
479:
402:
186:
72:
1106:
918:
681:
311:
43:
1101:
696:
686:
464:
138:, the method of choice between these alternatives is not directly specified by the programmer; the program must decide at
54:
1080:
1060:
990:
933:
895:
885:
845:
770:
706:
676:
592:
489:
469:
444:
407:
1035:
798:
765:
660:
636:
598:
578:
474:
383:
361:
346:
982:
968:
875:
835:
760:
666:
646:
513:
392:
326:
32:
1075:
840:
750:
730:
716:
1055:
1015:
958:
890:
628:
459:
1065:
1045:
986:
973:
953:
780:
517:
421:
379:
201:
196:
1025:
1000:
994:
938:
900:
588:
583:
535:
430:
331:
303:
294:
166:
79:
927:
923:
865:
817:
387:
1111:
1070:
1050:
1010:
812:
671:
540:
527:
281:
155:
123:
1005:
943:
755:
735:
721:
453:
321:
316:
822:
775:
745:
691:
550:
449:
341:
250:
978:
870:
725:
701:
641:
608:
570:
555:
494:
860:
792:
656:
397:
127:
170:
910:
784:
650:
351:
962:
618:
484:
1095:
948:
151:
131:
142:
between the alternatives, via some general method applied to all choice points. A
830:
21:
236:
143:
174:
159:
237:"State abstraction for programmable reinforcement learning agents"
254:
15:
241:
Eighteenth
National Conference on Artificial Intelligence
1024:
909:
811:
627:
569:
526:
429:
420:
360:
302:
293:
222:"Structure and Interpretation of Computer Programs"
130:(called "choice points"), various alternatives for
46:. Unsourced material may be challenged and removed.
192:Category: Nondeterministic programming languages
266:
8:
235:David Andre; Stuart J. Russell (July 2002).
126:which can specify, at certain points in the
426:
299:
273:
259:
251:
337:Programming in the large and in the small
106:Learn how and when to remove this message
213:
7:
150:One method of choice is embodied in
44:adding citations to reliable sources
14:
881:Partitioned global address space
20:
187:Nondeterminism (disambiguation)
31:needs additional citations for
169:, embodied in systems such as
55:"Nondeterministic programming"
1:
408:Uniform Function Call Syntax
165:Another method of choice is
120:nondeterministic programming
876:Parallel programming models
850:Concurrent constraint logic
1128:
969:Metalinguistic abstraction
836:Automatic mutual exclusion
841:Choreographic programming
891:Relativistic programming
202:demonic non-determinism
197:angelic non-determinism
901:Structured concurrency
286:Comparison by language
167:reinforcement learning
1107:Programming paradigms
866:Multitier programming
682:Interface description
282:Programming paradigms
1102:Computer programming
158:, or unification in
40:improve this article
1006:Self-modifying code
614:Probabilistic logic
545:Functional reactive
500:Expression-oriented
454:Partial application
919:Attribute-oriented
692:List comprehension
637:Algebraic modeling
450:Anonymous function
342:Design by contract
312:Jackson structures
1089:
1088:
979:Program synthesis
871:Organic computing
807:
806:
712:Non-English-based
687:Language-oriented
465:Purely functional
416:
415:
154:systems (such as
136:if-then statement
116:
115:
108:
90:
1119:
991:by demonstration
896:Service-oriented
886:Process-oriented
861:Macroprogramming
846:Concurrent logic
717:Page description
707:Natural language
677:Grammar-oriented
604:Nondeterministic
593:Constraint logic
495:Point-free style
490:Functional logic
427:
398:Immutable object
317:Block-structured
300:
275:
268:
261:
252:
245:
244:
232:
226:
225:
218:
111:
104:
100:
97:
91:
89:
48:
24:
16:
1127:
1126:
1122:
1121:
1120:
1118:
1117:
1116:
1092:
1091:
1090:
1085:
1027:
1020:
911:Metaprogramming
905:
821:
816:
803:
785:Graph rewriting
623:
599:Inductive logic
579:Abductive logic
565:
522:
485:Dependent types
433:
412:
384:Prototype-based
364:
362:Object-oriented
356:
352:Nested function
347:Invariant-based
289:
279:
249:
248:
234:
233:
229:
220:
219:
215:
210:
183:
112:
101:
95:
92:
49:
47:
37:
25:
12:
11:
5:
1125:
1123:
1115:
1114:
1109:
1104:
1094:
1093:
1087:
1086:
1084:
1083:
1078:
1073:
1068:
1063:
1058:
1053:
1048:
1043:
1038:
1032:
1030:
1022:
1021:
1019:
1018:
1013:
1008:
1003:
998:
976:
971:
966:
956:
951:
946:
941:
936:
931:
921:
915:
913:
907:
906:
904:
903:
898:
893:
888:
883:
878:
873:
868:
863:
858:
853:
843:
838:
833:
827:
825:
809:
808:
805:
804:
802:
801:
796:
781:Transformation
778:
773:
768:
763:
758:
753:
748:
743:
738:
733:
728:
719:
714:
709:
704:
699:
694:
689:
684:
679:
674:
669:
667:Differentiable
664:
654:
647:Automata-based
644:
639:
633:
631:
625:
624:
622:
621:
616:
611:
606:
601:
596:
586:
581:
575:
573:
567:
566:
564:
563:
558:
553:
548:
538:
532:
530:
524:
523:
521:
520:
514:Function-level
511:
502:
497:
492:
487:
482:
477:
472:
467:
462:
457:
447:
441:
439:
424:
418:
417:
414:
413:
411:
410:
405:
400:
395:
390:
376:
374:
358:
357:
355:
354:
349:
344:
339:
334:
329:
327:Non-structured
324:
319:
314:
308:
306:
297:
291:
290:
280:
278:
277:
270:
263:
255:
247:
246:
227:
212:
211:
209:
206:
205:
204:
199:
194:
189:
182:
179:
122:language is a
114:
113:
28:
26:
19:
13:
10:
9:
6:
4:
3:
2:
1124:
1113:
1110:
1108:
1105:
1103:
1100:
1099:
1097:
1082:
1079:
1077:
1074:
1072:
1069:
1067:
1064:
1062:
1059:
1057:
1054:
1052:
1051:Data-oriented
1049:
1047:
1044:
1042:
1039:
1037:
1034:
1033:
1031:
1029:
1023:
1017:
1014:
1012:
1009:
1007:
1004:
1002:
999:
996:
992:
988:
984:
980:
977:
975:
972:
970:
967:
964:
960:
957:
955:
952:
950:
949:Homoiconicity
947:
945:
942:
940:
937:
935:
932:
929:
925:
922:
920:
917:
916:
914:
912:
908:
902:
899:
897:
894:
892:
889:
887:
884:
882:
879:
877:
874:
872:
869:
867:
864:
862:
859:
857:
856:Concurrent OO
854:
851:
847:
844:
842:
839:
837:
834:
832:
829:
828:
826:
824:
819:
814:
810:
800:
797:
794:
790:
786:
782:
779:
777:
774:
772:
769:
767:
764:
762:
759:
757:
754:
752:
751:Set-theoretic
749:
747:
744:
742:
739:
737:
734:
732:
731:Probabilistic
729:
727:
723:
720:
718:
715:
713:
710:
708:
705:
703:
700:
698:
695:
693:
690:
688:
685:
683:
680:
678:
675:
673:
670:
668:
665:
662:
658:
655:
652:
648:
645:
643:
640:
638:
635:
634:
632:
630:
626:
620:
617:
615:
612:
610:
607:
605:
602:
600:
597:
594:
590:
587:
585:
582:
580:
577:
576:
574:
572:
568:
562:
559:
557:
554:
552:
549:
546:
542:
539:
537:
534:
533:
531:
529:
525:
519:
515:
512:
510:
509:Concatenative
506:
503:
501:
498:
496:
493:
491:
488:
486:
483:
481:
478:
476:
473:
471:
468:
466:
463:
461:
458:
455:
451:
448:
446:
443:
442:
440:
437:
432:
428:
425:
423:
419:
409:
406:
404:
401:
399:
396:
394:
391:
389:
385:
381:
378:
377:
375:
372:
368:
363:
359:
353:
350:
348:
345:
343:
340:
338:
335:
333:
330:
328:
325:
323:
320:
318:
315:
313:
310:
309:
307:
305:
301:
298:
296:
292:
287:
283:
276:
271:
269:
264:
262:
257:
256:
253:
242:
238:
231:
228:
223:
217:
214:
207:
203:
200:
198:
195:
193:
190:
188:
185:
184:
180:
178:
176:
172:
168:
163:
161:
157:
153:
148:
145:
141:
137:
133:
129:
125:
121:
110:
107:
99:
88:
85:
81:
78:
74:
71:
67:
64:
60:
57: –
56:
52:
51:Find sources:
45:
41:
35:
34:
29:This article
27:
23:
18:
17:
1056:Event-driven
603:
460:Higher-order
388:Object-based
240:
230:
216:
164:
152:backtracking
149:
134:. Unlike an
132:program flow
119:
117:
102:
93:
83:
76:
69:
62:
50:
38:Please help
33:verification
30:
1112:Determinism
1066:Intentional
1046:Data-driven
1028:of concerns
987:Inferential
974:Multi-stage
954:Interactive
831:Actor-based
818:distributed
761:Stack-based
561:Synchronous
518:Value-level
505:Applicative
422:Declarative
380:Class-based
1096:Categories
1041:Components
1026:Separation
1001:Reflective
995:by example
939:Extensible
813:Concurrent
789:Production
776:Templating
756:Simulation
741:Scientific
661:Spacecraft
589:Constraint
584:Answer set
536:Flow-based
436:comparison
431:Functional
403:Persistent
367:comparison
332:Procedural
304:Structured
295:Imperative
243:: 119–125.
208:References
144:programmer
96:April 2017
66:newspapers
928:Inductive
924:Automatic
746:Scripting
445:Recursive
1081:Subjects
1071:Literate
1061:Features
1016:Template
1011:Symbolic
983:Bayesian
963:Hygienic
823:parallel
702:Modeling
697:Low-code
672:End-user
609:Ontology
541:Reactive
528:Dataflow
181:See also
175:robotics
140:run time
124:language
1036:Aspects
944:Generic
934:Dynamic
793:Pattern
771:Tactile
736:Quantum
726:filters
657:Command
556:Streams
551:Signals
322:Modular
128:program
80:scholar
799:Visual
766:System
651:Action
475:Strict
160:Prolog
82:
75:
68:
61:
53:
1076:Roles
959:Macro
722:Pipes
642:Array
619:Query
571:Logic
480:GADTs
470:Total
393:Agent
171:Alisp
87:JSTOR
73:books
724:and
371:list
59:news
629:DSL
156:Amb
42:by
1098::
993:,
989:,
985:,
791:,
787:,
516:,
507:,
386:,
382:,
369:,
239:.
118:A
997:)
981:(
965:)
961:(
930:)
926:(
852:)
848:(
820:,
815:,
795:)
783:(
663:)
659:(
653:)
649:(
595:)
591:(
547:)
543:(
456:)
452:(
438:)
434:(
373:)
365:(
288:)
284:(
274:e
267:t
260:v
224:.
109:)
103:(
98:)
94:(
84:·
77:·
70:·
63:·
36:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.