Недетерминированное программирование - Nondeterministic programming

Парадигмы программирования

Недетерминирован программирования язык является языком , который может указать, в определенные моменты в программе ( так называемый «выбор точек»), различные альтернативы для выполнения программы . В отличие от оператора if-then , метод выбора между этими альтернативами напрямую программистом не определяется; программа должна выбрать во время выполнения между альтернативами с помощью некоторого общего метода, применяемого ко всем точкам выбора. Программист определяет ограниченное число альтернатив, но программа должна позже выбирать между ними. («Выбрать» - это, по сути, типичное название недетерминированного оператора.) Может быть сформирована иерархия точек выбора, при этом варианты более высокого уровня ведут к ветвям, которые содержат в себе варианты выбора более низкого уровня.

Один из выбранных методов воплощен в системах с возвратом (таких как Amb или унификация в Prolog ), в которых некоторые альтернативы могут «потерпеть неудачу», заставляя программу возвращаться и пробовать другие альтернативы. Если все альтернативы терпят неудачу в определенной точке выбора, то выходит из строя вся ветвь, и программа возвращается дальше, к более старой точке выбора. Одна из сложностей состоит в том, что, поскольку любой выбор является предварительным и может быть переделан, система должна иметь возможность восстанавливать старые состояния программы, устраняя побочные эффекты, вызванные частичным выполнением ветки, которая в конечном итоге завершилась неудачно.

Другой предпочтительный метод - обучение с подкреплением, воплощенное в таких системах, как Alisp . В таких системах, а не в обратном направлении, система отслеживает определенную степень успеха и изучает, какой выбор часто приводит к успеху и в каких ситуациях (как внутреннее состояние программы, так и входные данные среды могут повлиять на выбор). Эти системы подходят для приложений к робототехнике и других областях, в которых обратное отслеживание будет включать попытки отменить действия, выполняемые в динамической среде, что может быть трудным или непрактичным.

Смотрите также

использованная литература