globalf5-240972240972 (850810), страница 29
Текст из файла (страница 29)
Специальные функции могутанализировать и варьировать условия, при которых вычислениеаргументов необходимо. Так используется возможность манипулироватьданными, представляющими выражения, и явно определять впрограммах позиции обращения к интерпретатору. Эта возможностьприменялась для поддержки стандартной программотехники итрадиционных форм конструирования функциональных объектов.Свойственная функциональному программированию тенденция кполномасштабному применению всех попадающих в поле зрениясредств логически требует перехода от частных случаев к поддержкеуниверсального механизма, т.е. от набора конкретных специальныхфункций к более общему аппарату управления процессами вычислений.Результат управления проявляется в изменении некоторых оценок,например можно влиять на эффективность и надежность программ,обусловленнуюцелостностьюобъемных,сложныхданных,избыточностью вычислений, возможно, бесполезных выражений,необоснованной синхронизацией формально упорядоченных действий.197Л.В.
ГородняяОсновы функционального программированияПодобные источники неэффективности могут быть устраненыдостаточно простыми методами организации частичных вычислений сучетом дополнительных условий для их фактического выполнения,таких как достижимость или востребованность результата вычислений.Любое очень объемное, сложное данное можно вычислять "по частям".Вместо вычисления списка(x1 x2 x3 ... )можно вычислить x1 и построить структуру:(x1 ( рецепт вычисления остальных элементов))Получается принципиальная экономия памяти ценой незначительногоперерасхода времени на вспомогательное построение. Рецепт — этоссылка на уже существующую программу, связанную с контекстом ееисполнения, т.е.
с состоянием ассоциативного списка в моментпостроения рецепта.(DEFUN ряд_цел (M N) (COND ((> M N) NIL)(T (CONS M (ряд_цел (1+ M) N)))))(DEFUN сумма (X) (COND ((= X NIL) 0)(T (+ (CAR X)( сумма (CDR X))))) )Пример 12.1. Построение ряда целых от M до N с последующимих суммированием.Введем специальные операции || — приостановка вычислений и @ —возобновление ранее отложенных вычислений. Избежать целостногопредставления ряда целых можно, изменив формулу:(DEFUN ряд_цел (M N) (COND ((> M N) NIL)(T(CONS M ( || (ряд_цел (1+ M) N))))))(DEFUN сумма (X) (COND ((= X NIL) 0)(T (+ (CAR X) ( сумма (@ (cdr X))))) ))Чтобы исключить повторное вычисление совпадающих рецептов, в его198Л.В.
ГородняяОсновы функционального программированиявнутреннее представление вводится флаг, имеющий значение T —истина для уже выполненых рецептов, F — ложь для невыполненных.Тогда в выражении (ALL (CONS { 1 | 2 } (|| (цел 3 100)))) второй аргумент cons выполнится только для одного варианта, адля второго подставится готовый результат. Таким образом, рецептимеет вид:{ ( F e AL )| ( T x ) },где x = ( EVAL e AL ).Это позволяет распространить понятие данных на бесконечные,рекурсивно-вычислимые множества.
Например, можно работать срядом целых, больших чем N.(DEFUN цел (M) (CONS M ( || (цел (1+ M) ))))Можно из организованного таким образом списка выбирать нужноеколичество элементов, например первые K элементов можно получитьпо формуле:(DEFUN первые (K Int)(COND ((= Int Nil) NIL)((= K 0) NIL)(T (CONS (CAR Int)( первые (1- K) @ (CDR Int))) )) ))Эффект таких приостанавливаемых и возобновляемых вычисленийполучается путем следующей реализации операций || и @:||e = > (LAMBDA () e )@e = > (e ),что при интерпретации приводит к связыванию функциональногоаргумента с ассоциативным списком для операции || и к вызовуфункции EVAL для операции @.Обычно в языках программирования различают вызовы по значению,по имени и по ссылке.
Техника приостановки и возобновления функций199Л.В. ГородняяОсновы функционального программированияможет быть названа вызовом по необходимости .В некоторых языках программирования, таких как язык SAIL, Hope иHaskell, отложенные или замедленные вычисления — lazy evaluationосновная модель вычислений.Наиболее частый вариант — приостановка аргументов всехопределенных пользователем функций и операции CONS. В такомслучае порождаются многократные приостановки, что требуетитеративного возобновления до непосредственно исполняемогорецепта.Более подробно о тонкостях определения ленивых вычисленийрассказано в книге Хендерсона [3].Смешанные вычисленияИдея смешанных вычислений с точки зрения реализации близкатехнике ленивых вычислений, но сложилась концептуально изнесколько иных предпосылок [9]. Рассматривается пара ПрограммаДанные при недостаточных данных, отображаемая в так называемуюостаточную программу, которая может дать нужный результат, если датьнедостающие данные.
Для определения такого отображенияпонадобилась разметка действий программы на исполнимые изадерживаемые. Если такую разметку не связывать с отсутствиемданных, то получается модель, практически подобная вычислениям сзадержками и возобновлением .Не всегда неопределенность части данных мешает организоватьвычисление.Рассмотрим(if (< X Y) Z T)или эквивалентif X < Y then Z else TЕсли X и Y не определены, но известно, что X лежит в интервале [1, 4],200Л.В. ГородняяОсновы функционального программированияа Y в интервале [5, 6], то логическое выражение X<Y определено, иможно сделать вывод относительно выбора ветви условноговыражения и, возможно, получить его значение.Изучение смешанных вычислений может исходить из разныхтолкований понятия частичности, т.е.
функций, определенных не навсей области их существования.Первые работы Lombardi в этой области посвящены частичнымвычислениям, т.е. обработке частично определенных выражений надчислами. Реализация такой обработки на Лиспе осуществлялавыполнимые операции и строила из полученных частичныхрезультатов и невыполнимых операций некоторый промежуточныйрезультат — выражение, доопределив которое, можно получить полныйрезультат.В.Э. Иткин оценивал частичность какэффективности организации деятельности.практичныйкритерийПри подготовке программ на Лиспе неопределенность частопредставляют пустым списком, предполагая, что в него просто неуспели что-то записать. Такое представление не всегда достаточнокорректно и может потребовать дополнительных соглашений приобработке данных, по смыслу допускающих NIL в качествеопределенного значения.
Так, при реализации Lisp 1.5 введеносоглашение, что значение атома в списке свойств хранитсяупакованным в список [1].В работах по формальной семантике стандартных языковпрограммирования принято сведение к неопределенности значенийлюбых операций, зависящих от неопределенных данных.На практике это приводит к необоснованным потерям частиопределенной информации и результатов.A_1+...+A_100_000_000+неопределенность-> неопределенностьМожно обратить внимание, что невелика практическая разница вуровне определенности данных вида (A …) и (A F), где F — рецепт201Л.В.
ГородняяОсновы функционального программированиявычисления, про который не всегда известно, приведет ли он кполучению результата. Поэтомупрактичнее неопределенные данные"накрывать" рецептами, использующими специальные функции,нацеленные на раскрытие неопределенностей.Например, роль такой функции может сыграть запрос у пользователядополнительной информации:(A …) => (A . ( ||(READ)) )В определении интерпретаторасосредоточена в функции ERROR.обработканеопределенностей(DEFUN EVAL (e AL)…((assoc e AL)(cdr (assoc e AL)))(T(ERROR '"неопределенная переменная"))…)В определение функции ERROR можно включить обращение к READ,обрамленное сообщением о ситуации с информацией о контексте.(DEFUN APPLY (f args AL)…((assoc f AL)(apply (cdr (assoc f AL))(evlis args AL)AL))(T (ERROR ‘"неопределенная функция"))…)При отладке сложных комплексов часто неразработанные определениязамещают временными "заглушками", которые помогают разобраться вбудущей программе по частям.
Такую работу можно стандартизироватьзаданием предварительных определений функций в виде отображениятипа аргументов в тип результата. Соответственно, исполнениепредопределенной таким образом функции можно интерпретироватькак проверку аргументов на соответствие типу аргументов и выдачу вкачестве результата вариантов значения, принадлежащего типурезультата.202Л.В.
ГородняяОсновы функционального программированияПри небольшом числе значений заданного типа, например,истинностные значения, может быть целесообразным полный перебортаких значений с последующим выбором реальной альтернативыпользователем.(COND (e r)(T g))=> (assoc e (list (CONS T (EVAL r AL))(CONS NIL (EVAL g AL))) )Таким образом выполнятся обе ветви, их результаты ассоциируются сразличными значениями заданного типа, что позволяет получитьнужный результат, как только доопределится ранее не определенноезначение. Это позволяет избежать повторного выполненияпредшествующих вычислений, если их объем достаточно велик.Применение библиотечных процедур, зависящих от слишком большогочисла параметров, можно упростить для пользователя построениемпроекций на типовые комплекты трудно задаваемых параметров,понимаемых как определение режима работы процедуры.(DEFUN f (x y z a b c … v t u) (g …))(DEFUN Fi (x y z ) (f x y z ai bi ci … vi ti ui))Примерно это и делает необязательный параметр видаязыке Clisp.optional вТакое построение можно рассматривать как декомпозицию, разделение,сортировку на выполнимые и невыполнимые действия, при которойвыполнимые действия в тексте определения замещаются ихрезультатом, а невыполнимые преобразуются в остаточные, что всевместе образует проекцию процедуры на заданную часть ее параметров.Многие выражения по смыслу используемых в них операций иногдаопределены при частичной определенности их операндов, что частоиспользуется при оптимизации кода программ:X*0=0CAR (A …) = AX*1 = X при любом XX-X = 0203Л.В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
