Недетерминированные процессы
Есть мнение, что однозначное решение задачи в виде четкого алгоритма над хорошо организованными структурами и упорядоченными данными — результат аккуратной, тщательной работы, пытливого и вдумчивого изучения класса задач и требований к их решению.
Эффективные и надежные программы в таких случаях — естественное вознаграждение.
Но в ряде случаев природа задач требует свободного выбора одного из вариантов — выбор произвольного элемента множества, вероятности события при отсутствии известных закономерностей, псевдо-случайные изменения в игровых обстановках и сценариях, поиск первого подходящего адреса для размещения блока данных в памяти, лингвистический анализ при переводе документации и художественных текстов и т.д. При отсутствии предпочтений все допустимые варианты равноправны, и технология их отладки и обработки должна обеспечивать формально равные шансы вычисления таких вариантов. (Похожая проблема характерна для организации обслуживания в сетях и выполнения заданий операционными системами. Все узлы и задания сети должны быть потенциально достижимы, если нет формального запрета на оперирование ими.)
Представление вариантов в чем-то подобно определению ветвлений, но без предикатов, управляющих выбором ветви. В некоторых языках, например, учебно-игрового характера, можно указать вероятность выбора варианта. В языках логического и генетического программирования считают возможным прямой перебор вариантов, сопоставляемых с образцами, и организацию возвратов при неудачном выборе.
В отличие от множества элементов, набор вариантов не требует одновременного существования всех составляющих, что по реализации напоминает вариантные записи или объединения. Поэтому и программирование вариантов можно освободить от необходимости формулировать все варианты сразу. В логическом программировании можно продумывать варианты отношений между образцами формул постепенно, накапливая реально встречающиеся сочетания, как и методы обработки классов объектов в ООП. Содержательно такой процесс похож и на уточнение набора обработчиков прерываний на уровне оборудования. Кроме основной программы, выполняющей целевую обработку данных, отлаживается коллекция диагностических реакций и процедур продолжения счета для разного рода неожиданных событий, препятствующих получению результата программы.
Обычно понятие алгоритма и программы связывают с детерминированными процессами.
Но эти понятия не очень усложняются, если допустить недетерминизм, ограниченый конечным числом вариантов, так что в каждый момент времени из них существует только один вариант.
По смыслу выбор варианта похож на выбор произвольного элемента множества.
{ a | b | c } = э { a, b, c }
Чтобы такое понятие промоделировать обычными функциональными средствами, нужны дополнительные примитивы. Например, чтобы определить выбор произвольного элемента из списка L, можно представить рекурсивное выражение вида:
(любой L) = { ( CAR L)
| (любой (CDR L)) }
Если варианты в таком выражении рассматривать как равноправные компоненты, то не ясно, как предотвратить преждевременный выбор пустого списка при непустом перечне вариантов.
Чтобы решить эту задачу, вводится специальная форма — соглашением о приоритете раскрашенных переходов в сравнении с пустыми.)
Уточненное таким образом определение выбора произвольного элемента списка можно представить формулой вида:
(любой L) = { (CAR L)
| (любой (CDR L))
| (if (nl L) ESC) }
В какой-то момент L становится пустым списком, и его разбор оказывается невозможным. Тогда действует ESC.
Следует иметь в виду, что варианты не образуют иерархии. Их аксиоматика подобна так называемой упрощенной теории множеств. Принципиальная особенность — совпадение предикатов принадлежности и включения.
Другие построения, характерные для теории множеств: { x | P(X) } — множество элементов, обладающих свойством P.
Определение вида
(F L) = {(if (P ( CAR L ))
(CONS ( CAR L) (F ( CDR L))) )
| (if (nl L) ESC) }
недостаточно, т.к. порождаемые варианты элементов, удовлетворяющих заданому свойству, существуют в разные моменты времени и могут не существовать одновременно. Чтобы иметь все варианты одновременно, требуется еще один примитив ALL, обеспечивающий накопление всех реально осуществимых вариантов.
(F L) = (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) )
Логические связки
Логика McCarthy (компьютерная)
a b
(if (not a) NIL b)
b вычисляется лишь при истинном a, что результативно, но не всегда соответствует интуитивным ожиданиям (логика, предложенная в свое время McCarthy, позволяет добиться высокой эффективности). Математически более надежны варианты, исключающие зависимость от порядка перебора:
Более надежны варианты, исключающие зависимость от порядка перебора:
(( ALL( LAMBDA x { (if (not x) NIL )
| ESC })
{a | b} )
Если a и b оба истины, то получается ESC. Такое значение отличается от NIL, что работает как истина.
Аналогичная проблема возникает при построении ветвлений:
(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)} )
В книге Хендерсона приведено обобщение абстрактной машины, поддерживающее на базовом уровне работу с вариантами с использованием дополнительного дампа, гарантирующего идентичность состояния машины при переборе вариантов
.
Реализация недетерминированных моделей
Необходимая для такого стиля работы инструментальная поддержка обеспечивается в 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
. Похожие механизмы используются в языках, ориентированных на конструирование игр, таких как Grow, в которых можно в качестве условия срабатывания команды указать вероятность.
В задачах искусственного интеллекта работа с семантическими сетями, используемыми в базах знаний и экспертных системах, часто формулируется в терминах фреймов-слотов (рамка-щель), что конструктивно очень похоже на работу со списками свойств. Каждый объект характеризуется набором поименованных свойств, которые, в свою очередь, могут быть любыми объектами. Анализ понятийной системы, представленной таким образом, обычно описывается в недетерминированном стиле.
Следует отметить неисчерпаемый ряд задач, при решении которых удобно используются недетерминированные модели:
Обоснование упорядочений в традиционных алгоритмах — выделяется доалгоритмический уровень, на котором просто анализируются таблицы возможных решений и постепенно вырабатываются комплекты упорядочивающих условий и предикатов.
Переформулировка задач и переопределение алгоритмов с целью исключения необоснованных упорядочений — одна из типовых задач оптимизации, особенно при переходе от обычных программ к параллельным. Приходится выяснять допустимость независимого исполнения всех ветвей и управляющих их выбором предикатов.
Обобщение идеи абстрактных машин с целью теоретического исследования, экспериментального моделирования и прогнозирования недетерминированных процессов на суперкомпьютерах и многопроцессорных комплексах (многопроцессорная машина Тьюринга и т.п.).
Конструирование учебно-игровых программ и экспериментальных макетов, в которых скорость реализации важнее, чем производительность.
Описание и реализация недетерминизма в языках сверхвысокого уровня, таких как Planner, Setl, Sisal, Id, Haskell и др.
Недетерминированные определения разных математических функций и организация их обработки с учетом традиции понимания формул математиками.
Моделирование трудно формализуемых низкоуровневых эффектов, возникающих на стыке технических новинок и их массового применения как в научных исследованиях, так и в общедоступных приборах.
Обработка и исследование естественно языковых конструкций, речевого поведения, культурных и творческих стереотипов, социально-психологических аспектов и т.п.
Организация и разработка распределенных вычислений, измерений, Grid-технологий, развитие интероперабельных и телекоммуникационных систем и т.п.
Используемые при исследовании и решении таких задач модели дают богатый материал для развития нового поколения информационных систем, концептуальную основу которых можно изучать с помощью небольших функциональных программ. Принятая при решении таких задач техника сопоставления с образцом в значительной мере может быть осуществлена как работа с необязательными параметрами, что иллюстрирует эффективная версия определения сцепления списков :
(DEFUN append (optional first rest others )
(if (null others) first
(nconc (copy-list first)
(APPLY #’append others)))
)
В этой версии исключено копирование первого списка, когда других списков нет, и копии сцепляемых списков производятся лишь однократно.
Обработка множеств и последовательностей
При реализации недетерминированных моделей обычно используются средства обработки множеств и последовательностей. В современных системах функционального программирования такие средства достаточно разнообразны. Здесь приведены лишь наиболее очевидные:
Member — выделяет часть списка, начиная с заданного объекта, NIL — если такого объекта в списке нет.
(member 'a (b a c)) ;= (a c)
(member 'd (b a c)) ;= NIL
Set-difference — строит список элементов первого аргумента, не входящих во второй аргумент. Имеет деструктивный аналог — nset-difference .
Set-exlusive-or — строит список элементов первого или второго аргумента, но не входящих в оба сразу. Имеет деструктивный аналог — nset-exlusive-or .
Union — объединение множеств — строит список элементов первого или второго аргумента. Имеет деструктивный аналог — nunion .
Intersection — пересечение множеств — строит список элементов первого, входящих во второй аргумент. Имеет деструктивный аналог — nintersection .
Delete — строит последовательность из элементов второго аргумента за исключением совпадающих с первым аргументом. Имеет деструктивный аналог — remove .
(delete 1 '(1 2 1 3 1 4)) ;= (2 3 4)
Concatenate — строит новую последовательность заданного типа из своих аргументов, начиная со второго, при этом копирует их, кроме последнего. Для списков имеет деструктивный аналог — nconc .
Elt — выдает элемент последовательности по заданному номеру.
Find — отыскивает заданный символ в последовательности, можно управлять направлением поиска.
Sort — упорядочивает последовательность по заданному предикату.
(sort '(1 2 1 3 1 4) #’<) ;= (1 1 1 2 3 4)
Map — отображает с помощью данной функции ряд последовательностей в новую последовательность типа, заданного первым аргументом. Отображающая функция — второй аргумент. Кратность применения отображающей функции определяется длиной кратчайшего аргумента, начиная с третьего. Имеет деструктивный аналог map-into, строящий результат из первого аргумента.
Reverse — обращает последовательность. Имеет деструктивный аналог nreverse.
Position — выдает номер позиции первого вхождения заданного символа в последовательность.
Substitute — выполняет систематическую замену "старого" символа на "новый" в последовательности. Имеет деструктивный аналог — nsubstitute.
Maphash — методично применяет отображающую функцию двух аргументов к каждой паре из ключа и соответствующего значения в хэш-таблице.
Недетерминированные процессы
Есть мнение, что однозначное решение задачи в виде четкого алгоритма над хорошо организованными структурами и упорядоченными данными — результат аккуратной, тщательной работы, пытливого и вдумчивого изучения класса задач и требований к их решению.
Эффективные и надежные программы в таких случаях — естественное вознаграждение.
Но в ряде случаев природа задач требует свободного выбора одного из вариантов — выбор произвольного элемента множества, вероятности события при отсутствии известных закономерностей, псевдо-случайные изменения в игровых обстановках и сценариях, поиск первого подходящего адреса для размещения блока данных в памяти, лингвистический анализ при переводе документации и художественных текстов и т.д. При отсутствии предпочтений все допустимые варианты равноправны, и технология их отладки и обработки должна обеспечивать формально равные шансы вычисления таких вариантов. (Похожая проблема характерна для организации обслуживания в сетях и выполнения заданий операционными системами. Все узлы и задания сети должны быть потенциально достижимы, если нет формального запрета на оперирование ими.)
Представление вариантов в чем-то подобно определению ветвлений, но без предикатов, управляющих выбором ветви. В некоторых языках, например, учебно-игрового характера, можно указать вероятность выбора варианта. В языках логического и генетического программирования считают возможным прямой перебор вариантов, сопоставляемых с образцами, и организацию возвратов при неудачном выборе.
В отличие от множества элементов, набор вариантов не требует одновременного существования всех составляющих, что по реализации напоминает вариантные записи или объединения. Поэтому и программирование вариантов можно освободить от необходимости формулировать все варианты сразу. В логическом программировании можно продумывать варианты отношений между образцами формул постепенно, накапливая реально встречающиеся сочетания, как и методы обработки классов объектов в ООП. Содержательно такой процесс похож и на уточнение набора обработчиков прерываний на уровне оборудования. Кроме основной программы, выполняющей целевую обработку данных, отлаживается коллекция диагностических реакций и процедур продолжения счета для разного рода неожиданных событий, препятствующих получению результата программы.
Обычно понятие алгоритма и программы связывают с детерминированными процессами.
Но эти понятия не очень усложняются, если допустить недетерминизм, ограниченый конечным числом вариантов, так что в каждый момент времени из них существует только один вариант.
По смыслу выбор варианта похож на выбор произвольного элемента множества.
{ a | b | c } = э { a, b, c }
Чтобы такое понятие промоделировать обычными функциональными средствами, нужны дополнительные примитивы. Например, чтобы определить выбор произвольного элемента из списка L, можно представить рекурсивное выражение вида:
(любой L) = { ( CAR L)
| (любой (CDR L)) }
Если варианты в таком выражении рассматривать как равноправные компоненты, то не ясно, как предотвратить преждевременный выбор пустого списка при непустом перечне вариантов.
Чтобы решить эту задачу, вводится специальная форма — соглашением о приоритете раскрашенных переходов в сравнении с пустыми.)
Уточненное таким образом определение выбора произвольного элемента списка можно представить формулой вида:
(любой L) = { (CAR L)
| (любой (CDR L))
| (if (nl L) ESC) }
В какой-то момент L становится пустым списком, и его разбор оказывается невозможным. Тогда действует ESC.
Следует иметь в виду, что варианты не образуют иерархии. Их аксиоматика подобна так называемой упрощенной теории множеств. Принципиальная особенность — совпадение предикатов принадлежности и включения.
Другие построения, характерные для теории множеств: { x | P(X) } — множество элементов, обладающих свойством P.
Определение вида
(F L) = {(if (P ( CAR L ))
(CONS ( CAR L) (F ( CDR L))) )
| (if (nl L) ESC) }
недостаточно, т.к. порождаемые варианты элементов, удовлетворяющих заданому свойству, существуют в разные моменты времени и могут не существовать одновременно. Чтобы иметь все варианты одновременно, требуется еще один примитив ALL, обеспечивающий накопление всех реально осуществимых вариантов.
(F L) = (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) )
Логические связки
Логика McCarthy (компьютерная)
a b
(if (not a) NIL b)
b вычисляется лишь при истинном a, что результативно, но не всегда соответствует интуитивным ожиданиям (логика, предложенная в свое время McCarthy, позволяет добиться высокой эффективности). Математически более надежны варианты, исключающие зависимость от порядка перебора:
Более надежны варианты, исключающие зависимость от порядка перебора:
(( ALL( LAMBDA x { (if (not x) NIL )
| ESC })
{a | b} )
Если a и b оба истины, то получается ESC. Такое значение отличается от NIL, что работает как истина.
Аналогичная проблема возникает при построении ветвлений:
(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)} )
В книге Хендерсона приведено обобщение абстрактной машины, поддерживающее на базовом уровне работу с вариантами с использованием дополнительного дампа, гарантирующего идентичность состояния машины при переборе вариантов
.
Реализация недетерминированных моделей
Необходимая для такого стиля работы инструментальная поддержка обеспечивается в 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
. Похожие механизмы используются в языках, ориентированных на конструирование игр, таких как Grow, в которых можно в качестве условия срабатывания команды указать вероятность.
В задачах искусственного интеллекта работа с семантическими сетями, используемыми в базах знаний и экспертных системах, часто формулируется в терминах фреймов-слотов (рамка-щель), что конструктивно очень похоже на работу со списками свойств. Каждый объект характеризуется набором поименованных свойств, которые, в свою очередь, могут быть любыми объектами. Анализ понятийной системы, представленной таким образом, обычно описывается в недетерминированном стиле.
Следует отметить неисчерпаемый ряд задач, при решении которых удобно используются недетерминированные модели:
Обоснование упорядочений в традиционных алгоритмах — выделяется доалгоритмический уровень, на котором просто анализируются таблицы возможных решений и постепенно вырабатываются комплекты упорядочивающих условий и предикатов.
Переформулировка задач и переопределение алгоритмов с целью исключения необоснованных упорядочений — одна из типовых задач оптимизации, особенно при переходе от обычных программ к параллельным. Приходится выяснять допустимость независимого исполнения всех ветвей и управляющих их выбором предикатов.
Обобщение идеи абстрактных машин с целью теоретического исследования, экспериментального моделирования и прогнозирования недетерминированных процессов на суперкомпьютерах и многопроцессорных комплексах (многопроцессорная машина Тьюринга и т.п.).
Конструирование учебно-игровых программ и экспериментальных макетов, в которых скорость реализации важнее, чем производительность.
Описание и реализация недетерминизма в языках сверхвысокого уровня, таких как Planner, Setl, Sisal, Id, Haskell и др.
Недетерминированные определения разных математических функций и организация их обработки с учетом традиции понимания формул математиками.
Моделирование трудно формализуемых низкоуровневых эффектов, возникающих на стыке технических новинок и их массового применения как в научных исследованиях, так и в общедоступных приборах.
Обработка и исследование естественно языковых конструкций, речевого поведения, культурных и творческих стереотипов, социально-психологических аспектов и т.п.
Организация и разработка распределенных вычислений, измерений, Grid-технологий, развитие интероперабельных и телекоммуникационных систем и т.п.
Используемые при исследовании и решении таких задач модели дают богатый материал для развития нового поколения информационных систем, концептуальную основу которых можно изучать с помощью небольших функциональных программ. Принятая при решении таких задач техника сопоставления с образцом в значительной мере может быть осуществлена как работа с необязательными параметрами, что иллюстрирует эффективная версия определения сцепления списков :
(DEFUN append (optional first rest others )
(if (null others) first
(nconc (copy-list first)
(APPLY #’append others)))
)
В этой версии исключено копирование первого списка, когда других списков нет, и копии сцепляемых списков производятся лишь однократно.
Обработка множеств и последовательностей
При реализации недетерминированных моделей обычно используются средства обработки множеств и последовательностей. В современных системах функционального программирования такие средства достаточно разнообразны. Здесь приведены лишь наиболее очевидные:
Member — выделяет часть списка, начиная с заданного объекта, NIL — если такого объекта в списке нет.
(member 'a (b a c)) ;= (a c)
(member 'd (b a c)) ;= NIL
Set-difference — строит список элементов первого аргумента, не входящих во второй аргумент. Имеет деструктивный аналог — nset-difference .
Set-exlusive-or — строит список элементов первого или второго аргумента, но не входящих в оба сразу. Имеет деструктивный аналог — nset-exlusive-or .
Union — объединение множеств — строит список элементов первого или второго аргумента. Имеет деструктивный аналог — nunion .
Intersection — пересечение множеств — строит список элементов первого, входящих во второй аргумент. Имеет деструктивный аналог — nintersection .
Delete — строит последовательность из элементов второго аргумента за исключением совпадающих с первым аргументом. Имеет деструктивный аналог — remove .
(delete 1 '(1 2 1 3 1 4)) ;= (2 3 4)
Concatenate — строит новую последовательность заданного типа из своих аргументов, начиная со второго, при этом копирует их, кроме последнего. Для списков имеет деструктивный аналог — nconc .
Elt — выдает элемент последовательности по заданному номеру.
Find — отыскивает заданный символ в последовательности, можно управлять направлением поиска.
Sort — упорядочивает последовательность по заданному предикату.
(sort '(1 2 1 3 1 4) #’<) ;= (1 1 1 2 3 4)
Map — отображает с помощью данной функции ряд последовательностей в новую последовательность типа, заданного первым аргументом. Отображающая функция — второй аргумент. Кратность применения отображающей функции определяется длиной кратчайшего аргумента, начиная с третьего. Имеет деструктивный аналог map-into, строящий результат из первого аргумента.
Reverse — обращает последовательность. Имеет деструктивный аналог nreverse.
Position — выдает номер позиции первого вхождения заданного символа в последовательность.
Substitute — выполняет систематическую замену "старого" символа на "новый" в последовательности. Имеет деструктивный аналог — nsubstitute.
Maphash — методично применяет отображающую функцию двух аргументов к каждой паре из ключа и соответствующего значения в хэш-таблице.
