Лекция 10. Декларативное программирование icon

Лекция 10. Декларативное программирование



НазваниеЛекция 10. Декларативное программирование
Дата17.10.2016
Размер
ТипЛекция

Парадигмы

Лекция 10. Декларативное программирование

Недетерминизм и границы вычислимости выражений. Варианты, последовательности, множества. Описаны приемы организации недетерминированных вычислений в рамках функционального стиля программирования, вычисления с возвратами, перебор вариантов, откат. Анализируется соответствие точности решения задач и уровня постановки задачи. Оценивается зависимость техники решения от уровня изученности задачи. Функциональный стиль решения задач искусственного интеллекта. Представление и обработка недетерминированных программ. Варианты и обеспечение надежности вычислений. Теоретико-множественная семантика. Обоснование упорядочения действий в процессах обработки данных.



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


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


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


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


Обычно понятие алгоритма и программы связывают с детерминированными процессами.

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


{ 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, что не всегда соответствует интуитивным ожиданиям.

Более надежны варианты, исключающие зависимость от порядка перебора :


(( 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, можно с добавочной ловушкой на прерывание при достижении успеха. Модификация заключается в использовании другой версии eval. Ловушка нужна для приостановки вычисления независимых вариантов, когда уже найден один подходящий, т.е. не заводящий в тупик.


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


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


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


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


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


3) Обобщение идеи абстрактных машин с целью теоретического исследования, экспериментального моделирования и прогнозирования недетерминированных процессов на суперкомпьютерах и многопроцессорных комплексах

(многопроцессорная машина Тьюринга и т.п.).


4) Конструирование учебно-игровых программ и экспериментальных макетов, в которых скорость реализации важнее, чем производительность.


5) Описание и реализация недетерминизма в языках сверхвысокого уровня, таких как Planner, Setl, Sisal, Id, Haskel и др.


6) Недетерминированные определения разных математических функций и организация их обработки с учетом традиции понимания формул математиками.


7) Моделирование трудно формализуемых низкоуровневых эффектов, возникающих на стыке технических новинок и их массового применения как в научных исследованиях, так и в общедоступных приборах.


8) Обработка и исследование естественно языковых конструкций, речевого поведения, культурных и творческих стереотипов, социально-психологических аспектов и т.п.


9) Организация и разработка распределенных вычислений, измерений, Grid-технологий, развитие интероперабельных и телекоммуникационных систем и т.п.


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


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


(defun append (&optional first &rest others )

(if (null others) first

(nconc (copy-list first)

(apply #’append others)) )

)


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


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





Похожие:

Лекция 10. Декларативное программирование iconЛекция №1 Тема: Математическое программирование
В математическом программировании выделяют линейное программирование – когда функции и линейны, квадратичное программирование, когда...
Лекция 10. Декларативное программирование iconВведение в объектно-ориентированное программирование
Исторически сложилось так, что программирование возникло и развивалось как процедурное программирование, которое предполагает, что...
Лекция 10. Декларативное программирование iconМатематическое программирование Математическое программирование
Геометрическая интерпретация задач линейного программирования и графический метод решения (при двух неизвестных)
Лекция 10. Декларативное программирование iconЛекция 1 «Программирование ввода/вывода в языке C
Организация C
Лекция 10. Декларативное программирование iconЛинейное программирование
Линейное программирование (ЛП) это наука о методах исследования и отыскания наибольших и наименьших значений линейной функции, на...
Лекция 10. Декларативное программирование iconТем Предмет, объект изучения и задачи курса
Лекция 11. Динамическое программирование в задачах распределения однородных ресурсов
Лекция 10. Декларативное программирование iconЛинейное программирование, Содержание: Производственная задача, Двойственная задача, Линейное программирование как научно-практическая дисциплина. Задача об оптимизации смеси (упрощенный вариант). Планирование номенклатуры и объемов выпуска
Содержание: Производственная задача, Двойственная задача, Линейное программирование как научно-практическая
Лекция 10. Декларативное программирование iconПрограмма элективного курса «Программирование на языке Turbo Pascal» 9 класс
Предлагаемый элективный профильный курс предназначен для тех, кто хочет освоить программирование в среде Turbo Pascal. Курс предполагает...
Лекция 10. Декларативное программирование iconЛекция Экономическая роль государства в Республике Беларусь (6 ч.)
Прогнозирование, планирование, программирование как формы государственного регулирования экономики. Важнейшие прогнозные и программные...
Лекция 10. Декларативное программирование iconЛекция 2 «Многопоточное программирование в языке C
Пространство имен System. Threading. Класс Thread. Создание потока. Использование нескольких потоков. Планирование потоков, приоритеты...
Разместите ссылку на наш сайт:
Уроки, сочинения


База данных защищена авторским правом ©izlov.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
связаться с нами