Декларативное программирование

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

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

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

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

{ a | b | c } = э{ a, b, c }

Чтобы такое понятие промоделировать, нужны дополнительные примитивы. Например, чтобы определить обычными функциональными средствами выбор произвольного элемента из списка L, можно представить рекурсивное выражение вида:

(любой L) = {( car L) | (любой (cdr L)) }

Если варианты в таком выражении рассматривать как равноправные компоненты, то не ясно, как предотвратить преждевременный выбор пустого списка при непустом перечне вариантов.

Чтобы решить эту задачу, вводится специальная форма ESC (ТУПИК), действие которой заключается в том, что она как бы "старается" по возможности не исполняться. Иными словами, при выборе вариантов предпочитаются варианты, не приводящие к исполнению формы ESC. (Такая же проблема возникает при обработке пустых цепочек в грамматиках. Аналогичная проблема решена при моделировании процессов интерпретированными сетями Петри [[15]] - соглашением о приоритете раскрашенных переходов в сравнении с пустыми.)

Уточненное таким образом определение выбора произвольного элемента списка можно представить формулой вида:

(любой L) = { (car L) | (любой (cdr L)) | (if (nl L) ESC) }

В какой-то момент L становится пустым списком, и его разбор оказывается невозможным. Тогда действует ESC.

Следует иметь в виду, что варианты не образуют иерархии. Их аксиоматика подобна так называемой упрощенной теории множеств. Принципиальная особенность - совпадение предикатов принадлежности и включения.

Другие построения, характерные для теории множеств:

{ x | P(X) } - множество элементов, обладающих свойством P.

Определение вида

(F x) = {(if (P ( car L )) (cons ( car L) (F ( cdr L))) ) | (if (nl L) esc) }

недостаточно, т.к. порождаемые варианты элементов, удовлетворяющих заданому свойству, существуют в разные моменты времени и могут не существовать одновременно. Чтобы получить все варианты одновременно, требуется еще один примитив ALL, обеспечивающий накопление всех реально осуществимых вариантов.

(F x) = (ALL {(if (P ( car L )) (cons ( car L) (F ( cdr L))) ) | (if (nl L) esc) } )

Пересечение множеств A и B:

( all ( lambda (x y) {(if (= x y) x) | esc }) (любой A) (любой B) )

Логические связки:

Логическую связку "a & b" часто реализуют как "(if (not a) Nil b)", так что "b" вычисляется лишь при истинном "a", что не всегда соответствует интуитивным ожиданиям. Более надежны варианты, исключающие зависимость от порядка вычислений параметров:

(( lambda x { (if (not x) Nil ) | esc }) {a | b} )

Аналогичная проблема возникает при реализации ветвлений.

(cond (p1 e1) (p2 e2 ) …)

( ( lambda L {(cond (( eval ( caar L) AL) ( eval ( cadr L) AL ) )) | ESC }) ( любой ((p1 e1) (p2 e2) ...)))

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

a+b+c = (a+b)+c = a+(b+c) = (a+c)+b

((lambda (x y z) {(if (< (+ x y) K) (+(+ x y) z)) | esc}) {(a b c) | (b c a) | (c a b)})

В книге Хендерсона приведено обобщение абстрактной машины, поддерживающее на базовом уровне работу с вариантами с использованием дополнительного дампа, гарантирующего идентичность состояния машины при переборе вариантов [[23]].

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

В этой схеме THROW играет роль прерывания процесса, а CATCH - обработчика прерываний. Их взаимодействие синхронизировано с помощью тега, идентифицирующего уровень, на котором расположена ловушка для соответствующего прерывания. При этом есть возможность указать передаваемое "наверх" значение. Содержательно такая схема взаимодействия похожа на PROG-RETURN, с той разницей, что отсутствует зависимость от расположения в тексте программы.

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

Используя тупики и ловушки, можно собрать все беступиковые варианты или организовать перебор вариантов до первого беступикового. Первое можно сделать с помощью отображений (map), а второе - первый подходящий - слегка модифицированным evcon с добавочной ловушкой на прерывание при достижении успеха. Модификация заключается в использовании другой версии eval. Ловушка нужна для приостановки вычисления независимых вариантов, когда уже найден один подходящий, т.е. не заводящий в тупик.

Более сложно обеспечить равновероятность выбора вариантов. Наиболее серьезно возможность такой реализации рассматривалась Дж. Шварцем в проекте языка SETL. Похожие механизмы используются в языках, ориентированных на конструирование игр, таких как Grow, в которых можно в качестве условия срабатывания команды указать вероятность.

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

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

Обоснование упорядочений в традиционных алгоритмах - выделяется доалгоритмический уровень, на котором просто анализируются таблицы возможных решений и постепенно вырабатываются комплекты упорядочивающих условий и предикатов.
Переформулировка задач и переопределение алгоритмов с целью исключения необоснованных упорядочений - одна из типовых задач оптимизации, особенно при переходе от обычных программ к параллельным. Приходится выяснять допустимость независимого исполнения всех ветвей и управляющих их выбором предикатов.
Обобщение идеи абстрактных машин с целью теоретического исследования, экспериментального моделирования и прогнозирования недетерминированных процессов на суперкомпьютерах и многопроцессорных комплексах (многопроцессорная машина Тьюринга и т.п.).
Конструирование учебно-игровых программ и экспериментальных макетов, в которых скорость реализации важнее, чем производительность.
Описание и реализация недетерминизма в языках сверхвысокого уровня, таких как Planner, Setl, Sisal, Id, Haskel и др.
Недетерминированные определения разных математических функций и организация их обработки с учетом традиции понимания формул математиками.
Моделирование трудно формализуемых низкоуровневых эффектов, возникающих на стыке технических новинок и их массового применения как в научных исследованиях, так и в общедоступных приборах.
Обработка и исследование естественно языковых конструкций, речевого поведения, культурных и творческих стереотипов, социально-психологических аспектов и т.п.
Организация и разработка распределенных вычислений, измерений, Grid-технологий, развитие интероперабельных и телекоммуникационных систем и т.п.

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

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

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

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

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

Более подробно с идеями декларативного программирования можно ознакомиться на примере языка логического программирования Пролог [[52]].

Содержание раздела