Недетерминированный язык программирования — это язык , который может указывать в определенных точках программы ( называемых «точками выбора») различные альтернативы для потока программы . В отличие от оператора if-then , метод выбора между этими альтернативами не указывается программистом напрямую; программа должна выбирать между альтернативами во время выполнения с помощью некоторого общего метода, применяемого ко всем точкам выбора. Программист указывает ограниченное количество альтернатив, но программа должна позже выбирать между ними. («Выбрать» — это, по сути, типичное название для недетерминированного оператора.) Может быть сформирована иерархия точек выбора, при этом выборы более высокого уровня ведут к ветвям, которые содержат выборы более низкого уровня внутри себя.
Один из методов выбора воплощен в системах обратного отслеживания (таких как Amb, [1] или унификация в Prolog ), в которых некоторые альтернативы могут «потерпеть неудачу», заставляя программу возвращаться и пробовать другие альтернативы. Если все альтернативы терпят неудачу в определенной точке выбора, то вся ветвь терпит неудачу, и программа возвращается дальше, к более старой точке выбора. Одной из сложностей является то, что, поскольку любой выбор является предварительным и может быть переделан, система должна иметь возможность восстанавливать старые состояния программы, отменяя побочные эффекты, вызванные частичным выполнением ветви, которая в конечном итоге дала сбой.
Другим методом выбора является обучение с подкреплением , воплощенное в таких системах, как Alisp. [2] В таких системах, вместо обратного отслеживания, система отслеживает некоторую меру успеха и узнает, какие выборы часто приводят к успеху, и в каких ситуациях (как внутреннее состояние программы, так и входные данные окружающей среды могут влиять на выбор). Эти системы подходят для приложений в робототехнике и других областях, в которых обратное отслеживание будет включать попытку отменить действия, выполненные в динамической среде, что может быть сложным или непрактичным.