учебники, программирование, основы, введение в,

 

Варианты, последовательности, множества

Недетерминированные процессы
Есть мнение, что однозначное решение задачи в виде четкого алгоритма над хорошо организованными структурами и упорядоченными данными — результат аккуратной, тщательной работы, пытливого и вдумчивого изучения класса задач и требований к их решению.
Эффективные и надежные программы в таких случаях — естественное вознаграждение.
Но в ряде случаев природа задач требует свободного выбора одного из вариантоввыбор произвольного элемента множества, вероятности события при отсутствии известных закономерностей, псевдо-случайные изменения в игровых обстановках и сценариях, поиск первого подходящего адреса для размещения блока данных в памяти, лингвистический анализ при переводе документации и художественных текстов и т.д. При отсутствии предпочтений все допустимые варианты равноправны, и технология их отладки и обработки должна обеспечивать формально равные шансы вычисления таких вариантов. (Похожая проблема характерна для организации обслуживания в сетях и выполнения заданий операционными системами. Все узлы и задания сети должны быть потенциально достижимы, если нет формального запрета на оперирование ими.)
Представление вариантов в чем-то подобно определению ветвлений, но без предикатов, управляющих выбором ветви. В некоторых языках, например, учебно-игрового характера, можно указать вероятность выбора варианта. В языках логического и генетического программирования считают возможным прямой перебор вариантов, сопоставляемых с образцами, и организацию возвратов при неудачном варианте.
В отличие от множества элементов, набор вариантов не требует одновременного существования всех составляющих. Поэтому и программирование вариантов можно освободить от необходимости формулировать все варианты сразу. В логическом программировании можно продумывать варианты отношений между образцами формул постепенно, накапливая реально встречающиеся сочетания, как и методы обработки классов объектов в ООП. Содержательно такой процесс похож и на уточнение набора обработчиков прерываний на уровне оборудования. Кроме основной программы, выполняющей целевую обработку данных, отлаживается коллекция диагностических реакций и процедур продолжения счета для разного рода неожиданных событий, препятствующих получению результата программы.
Обычно понятие алгоритма и программы связывают с детерминированными процессами.
Но эти понятия не очень усложняются, если допустить недетерминизм, ограниченый конечным числом вариантов , так что в каждый момент времени из них существует только один вариант.
По смыслу выбор варианта похож на выбор произвольного элемента множества.
{ a | b | c } = э { a, b, c }
Чтобы такое понятие промоделировать обычными функциональными средствами, нужны дополнительные примитивы. Например, чтобы определить выбор произвольного элемента из списка L, можно представить рекурсивное выражение вида:
(любой L) = {( car L)
| (любой (cdr L)) }  
Если варианты в таком выражении рассматривать как равноправные компоненты, то не ясно, как предотвратить преждевременный выбор пустого списка при непустом перечне вариантов.
Чтобы решить эту задачу, вводится специальная форма ESC (ТУПИК), действие которой заключается в том, что она как бы "старается" по возможности не исполняться. Иными словами, при выборе вариантов предпочитаются варианты, не приводящие к исполнению формы ESC. (Такая же проблема возникает при обработке пустых цепочек в грамматиках. Аналогичным образом эта проблема решена при моделировании процессов интерпретированными сетями Петри — соглашением о приоритете раскрашенных переходов в сравнении с пустыми.)
Уточненное таким образом определение выбора произвольного элемента списка можно представить формулой вида:
(любой 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) )
Логические связки
Логика McCarthy (компьютерная)
a & b

(if (not a) Nil b)
b вычисляется лишь при истинном a, что результативно, но не всегда соответствует интуитивным ожиданиям (логика, предложенная в свое время McCarthy, позволяет добиться высокой эффективности). Математически более надежны варианты, исключающие зависимость от порядка перебора:
Более надежны варианты, исключающие зависимость от порядка перебора:
(( 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)})
В книге Хендерсона приведено обобщение абстрактной машины, поддерживающее на базовом уровне работу с вариантами с использованием дополнительного дампа, гарантирующего идентичность состояния машины при переборе вариантов .

Реализация недетерминированных моделей
Необходимая для такого стиля работы инструментальная поддержка обеспечивается в 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, в которых можно в качестве условия срабатывания команды указать вероятность.
В задачах искусственного интеллекта работа с семантическими сетями, используемыми в базах знаний и экспертных системах, часто формулируется в терминах фреймов-слотов (рамка-щель), что конструктивно очень похоже на работу со списками свойств. Каждый объект характеризуется набором поименованных свойств, которые, в свою очередь, могут быть любыми объектами. Анализ понятийной системы, представленной таким образом, обычно описывается в недетерминированном стиле.
Следует отметить неисчерпаемый ряд задач, при решении которых результативно используются недетерминированные модели:

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

 
На главную | Содержание | < Назад....Вперёд >
С вопросами и предложениями можно обращаться по nicivas@bk.ru. 2013 г.Яндекс.Метрика