Реализация недетерминированных моделей
Необходимая для такого стиля работы инструментальная поддержка обеспечивается в GNU Clisp механизмом обработки событий throw-catch, для которого следует задать примерно такое взаимодействие:
(defun vars (xl)(catch 'esc ; перебор вариантов до первого тупика (cond ; vars not Nil ((null xl)(escape)) ((car xl) (cons (car xl)(vars (cdr xl)))) )))
(defun escape () (throw 'esc Nil)) ; сигнал о попадании в тупик
(print(vars ())) (print(vars '(a))) (print(vars '(a b c))) (print(vars (list 'a 'b (vars ()) 'c)))
В этой схеме THROW играет роль прерывания процесса, а CATCH — обработчика прерываний.
Их взаимодействие синхронизировано с помощью тэга, идентифицирующего уровень, на котором расположена ловушка для соответствующего прерывания. При этом есть возможность указать передаваемое "наверх" значение. Содержательно такая схема взаимодействия похожа на PROG-RETURN, с той разницей, что отсутствует зависимость от расположения в тексте программы.
Получается, что в любом выражении можно выполнить разметку ветвей на нормальные и тупиковые. Тупики можно связать с различными тэгам и выставить ловушки на заданные тэги. При попадании в тупик формируется значение всей структуры, размещенной внутри ловушки.
Используя тупики и ловушки, можно организовать перебор вариантов до первого беступикового или собрать все беступиковые варианты. Первое можно сделать, используя отображения (map), а второе — первый подходящий — слегка модифицированным evcon, можно с добавочной ловушкой на прерывание при достижении успеха.
Более сложно обеспечить равновероятность выбора
вариантов. Наиболее серьезно возможность такой реализации рассматривалась в проекте языка SETL 12. Похожие механизмы используются в языках, ориентированных на конструирование игр, таких как Grow, в которых можно в качестве условия срабатывания команды указать вероятность.
В задачах искусственного интеллекта работа с семантическими сетями, используемыми в базах знаний и экспертных системах, часто формулируется в терминах фреймов-слотов (рамка-щель), что конструктивно очень похоже на работу со списками свойств.
Каждый объект характеризуется набором поименованных свойств, которые, в свою очередь, могут быть любыми объектами. Анализ понятийной системы, представленной таким образом, обычно описывается в недетерминированном стиле.
Следует отметить неисчерпаемый ряд задач, при решении которых результативно используются недетерминированные модели:
- Обоснование упорядочений в традиционных алгоритмах — выделяется доалгоритмический уровень, на котором просто анализируются таблицы возможных решений и постепенно вырабатываются комплекты упорядочивающих условий и предикатов.
- Переформулировка задач и переопределение алгоритмов с целью исключения необоснованных упорядочений — одна из типовых задач оптимизации, особенно при переходе от обычных программ к параллельным. Приходится выяснять допустимость независимого исполнения всех ветвей и управляющих их выбором предикатов.
- Обобщение идеи абстрактных машин с целью теоретического исследования, экспериментального моделирования и прогнозирования недетерминированных процессов на суперкомпьютерах и многопроцессорных комплексах (многопроцессорная машина Тьюринга и т.п.).
- Конструирование учебно-игровых программ и экспериментальных макетов, в которых скорость реализации важнее, чем производительность.
- Описание и реализация недетерминизма в языках сверхвысокого уровня, таких как Planner, Setl, Sisal, Id, Haskell и др.
- Недетерминированные определения разных математических функций и организация их обработки с учетом традиции понимания формул математиками.
- Моделирование трудно формализуемых низкоуровневых эффектов, возникающих на стыке технических новинок и их массового применения как в научных исследованиях, так и в общедоступных приборах.
- Обработка и исследование естественно языковых конструкций, речевого поведения, культурных и творческих стереотипов, социально-психологических аспектов и т.п.
- Организация и разработка распределенных вычислений, измерений, Grid-технологий, развитие интероперабельных и телекоммуникационных систем и т.п.
Используемые при исследовании и решении таких задач модели дают богатый материал для развития нового поколения информационных систем, концептуальную основу которых можно изучать с помощью небольших функциональных программ.Принятая при решении таких задач техника сопоставления с образцом в значительной мере может быть осуществлена как работа с необязательными параметрами, что иллюстрирует эффективная версия определения сцепления списков 7:
(defun append (&optional first &rest others ) (if (null others) first (nconc (copy-list first) (apply #’append others))) )
В этой версии исключено копирование первого списка, когда других списков нет, и копии сцепляемых списков производятся лишь однократно.
