18c0693f

Реализация недетерминированных моделей


Необходимая для такого стиля работы инструментальная поддержка обеспечивается в 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, в которых можно в качестве условия срабатывания команды указать вероятность.

В задачах искусственного интеллекта работа с семантическими сетями, используемыми в базах знаний и экспертных системах, часто формулируется в терминах фреймов-слотов (рамка-щель), что конструктивно очень похоже на работу со списками свойств.
Каждый объект характеризуется набором поименованных свойств, которые, в свою очередь, могут быть любыми объектами. Анализ понятийной системы, представленной таким образом, обычно описывается в недетерминированном стиле.

Следует отметить неисчерпаемый ряд задач, при решении которых результативно используются недетерминированные модели:

  1. Обоснование упорядочений в традиционных алгоритмах — выделяется доалгоритмический уровень, на котором просто анализируются таблицы возможных решений и постепенно вырабатываются комплекты упорядочивающих условий и предикатов.
  2. Переформулировка задач и переопределение алгоритмов с целью исключения необоснованных упорядочений — одна из типовых задач оптимизации, особенно при переходе от обычных программ к параллельным. Приходится выяснять допустимость независимого исполнения всех ветвей и управляющих их выбором предикатов.
  3. Обобщение идеи абстрактных машин с целью теоретического исследования, экспериментального моделирования и прогнозирования недетерминированных процессов на суперкомпьютерах и многопроцессорных комплексах (многопроцессорная машина Тьюринга и т.п.).
  4. Конструирование учебно-игровых программ и экспериментальных макетов, в которых скорость реализации важнее, чем производительность.
  5. Описание и реализация недетерминизма в языках сверхвысокого уровня, таких как Planner, Setl, Sisal, Id, Haskell и др.
  6. Недетерминированные определения разных математических функций и организация их обработки с учетом традиции понимания формул математиками.
  7. Моделирование трудно формализуемых низкоуровневых эффектов, возникающих на стыке технических новинок и их массового применения как в научных исследованиях, так и в общедоступных приборах.
  8. Обработка и исследование естественно языковых конструкций, речевого поведения, культурных и творческих стереотипов, социально-психологических аспектов и т.п.
  9. Организация и разработка распределенных вычислений, измерений, Grid-технологий, развитие интероперабельных и телекоммуникационных систем и т.п.


Используемые при исследовании и решении таких задач модели дают богатый материал для развития нового поколения информационных систем, концептуальную основу которых можно изучать с помощью небольших функциональных программ.Принятая при решении таких задач техника сопоставления с образцом в значительной мере может быть осуществлена как работа с необязательными параметрами, что иллюстрирует эффективная версия определения сцепления списков 7:

(defun append (&optional first &rest others ) (if (null others) first (nconc (copy-list first) (apply #’append others))) )

В этой версии исключено копирование первого списка, когда других списков нет, и копии сцепляемых списков производятся лишь однократно.