globalf5-240972240972 (850810), страница 28
Текст из файла (страница 28)
Такое значение отличаетсяот NIL, что работает как истина.190Л.В. ГородняяОсновы функционального программированияАналогичная проблема возникает при построении ветвлений:(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)} )В книге Хендерсона приведено обобщение абстрактной машины,поддерживающее на базовом уровне работу с вариантами сиспользованиемдополнительногодампа,гарантирующегоидентичность состояния машины при переборе вариантов [3].Реализация недетерминированных моделейНеобходимая для такого стиля работы инструментальная поддержкаобеспечивается в GNU Clisp механизмом обработки событий throw catch, для которого следует задать примерно такое взаимодействие:(DEFUN vars (xl)(catch 'ESC; перебор вариантов до первого тупика(COND; vars not NIL((null xl)(escape))((CAR xl) (CONS (CAR xl)(vars (CDR xl)))))) )191Л.В.
ГородняяОсновы функционального программирования(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, в которыхможно в качестве условия срабатывания команды указать вероятность.В задачах искусственного интеллекта работа с семантическими сетями,используемыми в базах знаний и экспертных системах, частоформулируется в терминах фреймов-слотов (рамка-щель), что192Л.В.
ГородняяОсновы функционального программированияконструктивно очень похоже на работу со списками свойств. Каждыйобъект характеризуется набором поименованных свойств, которые, всвою очередь, могут быть любыми объектами. Анализ понятийнойсистемы, представленной таким образом, обычно описывается внедетерминированном стиле.Следует отметить неисчерпаемый ряд задач, при решении которыхудобно используются недетерминированные модели:1.
Обоснование упорядочений в традиционных алгоритмах —выделяется доалгоритмический уровень, на котором простоанализируются таблицы возможных решений и постепенновырабатываются комплекты упорядочивающих условий ипредикатов.2. Переформулировка задач и переопределение алгоритмов с цельюисключения необоснованных упорядочений — одна из типовыхзадач оптимизации, особенно при переходе от обычных программкпараллельным.Приходитсявыяснятьдопустимостьнезависимого исполнения всех ветвей и управляющих ихвыбором предикатов.3.
Обобщение идеи абстрактных машин с целью теоретическогоисследования,экспериментальногомоделированияипрогнозированиянедетерминированныхпроцессовнасуперкомпьютерахимногопроцессорныхкомплексах(многопроцессорная машина Тьюринга и т.п.).4. Конструированиеучебно-игровыхпрограммиэкспериментальных макетов, в которых скорость реализацииважнее, чем производительность.5. Описание и реализация недетерминизма в языках сверхвысокогоуровня, таких как Planner, Setl, Sisal, Id, Haskell и др.6.
Недетерминированные определения разных математическихфункций и организация их обработки с учетом традициипонимания формул математиками.7. Моделирование трудно формализуемых низкоуровневых эффектов,возникающих на стыке технических новинок и их массовогоприменения как в научных исследованиях, так и в общедоступныхприборах.8.
Обработка и исследование естественно языковых конструкций,речевого поведения, культурных и творческих стереотипов,193Л.В. ГородняяОсновы функционального программированиясоциально-психологических аспектов и т.п.9. Организация и разработка распределенных вычислений,измерений, Grid-технологий, развитие интероперабельных ителекоммуникационных систем и т.п.Используемые при исследовании и решении таких задач модели даютбогатый материал для развития нового поколения информационныхсистем, концептуальную основу которых можно изучать с помощьюнебольших функциональных программ.
Принятая при решении такихзадач техника сопоставления с образцом в значительной мере можетбыть осуществлена как работа с необязательными параметрами, чтоиллюстрирует эффективная версия определения сцепления списков [7]:(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)) ;= NILSet-difference — строит список элементов первого аргумента, невходящих во второй аргумент.
Имеет деструктивный аналог — nsetdifference .194Л.В. ГородняяОсновы функционального программирования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.195Л.В. ГородняяОсновы функционального программированияPosition — выдает номер позиции первого вхождения заданногосимвола в последовательность.Substitute — выполняет систематическую замену "старого" символа на"новый" в последовательности. Имеет деструктивный аналог —nsubstitute.Maphash — методично применяет отображающую функцию двухаргументов к каждой паре из ключа и соответствующего значения в хэштаблице.196Л.В. ГородняяОсновы функционального программированияУправление процессамиРассматривается эффективное обобщение процесса информационнойобработки, вытекающее из возможности отложенных действий (lazyevaluation),органическиприсущейфункциональномупрограммированию благодаря унификации представления данных ипрограмм.
Анализируются резервы производительности обобщенныхпроцессов и методы динамической оптимизации вычислений,приводящие к смешанным и параллельным вычислениям.Замедленные (ленивые) вычисленияСредствауправленияпроцессамивфункциональномпрограммированииизначальноопираютсянаинтуитивноепредставление о вычислении выражений, согласно которому функцияприменяется к заранее вычисленным аргументам.Ради полноты пространства вычислений, гибкости программ ирезультативности процессов такое представление пришлось расширитьи ввести категорию специальных функций, которые "знают", когда и чтоиз их аргументов следует вычислить.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
