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

 

Управление процессами

Замедленные вычисления
Средства управления процессами в функциональном программировании изначально опираются на интуитивное представление о вычислении выражений, согласно которому функция применяется к заранее вычисленным аргументам.
Ради полноты пространства вычислений, гибкости программ и результативности процессов такое представление пришлось расширить и ввести категорию специальных функций, которые "знают", когда и что из их аргументов следует вычислить. Специальные функции могут анализировать и варьировать условия, при которых вычисление аргументов необходимо. Так используется возможность манипулировать данными, представляющими выражения, и явно определять в программах позиции обращения к интерпретатору. Эта возможность применялась для поддержки стандартной программотехники и традиционных форм конструирования функциональных объектов.
Свойственная функциональному программированию тенденция к полномасштабному применению всех попадающих в поле зрения средств логически требует перехода от частных случаев к поддержке универсального механизма, т.е. от набора конкретных специальных функций к более общему аппарату управления процессами вычислений.
Результат управления проявляется в изменении некоторых оценок, например можно влиять на эффективность и надежность программ, обусловленную целостностью объемных, сложных данных, избыточностью вычислений, возможно, бесполезных выражений, необоснованной синхронизацией формально упорядоченных действий. Подобные источники неэффективности могут быть устранены достаточно простыми методами организации частичных вычислений с учетом дополнительных условий для их фактического выполнения, таких как достижимость или востребованность результата вычислений.
Любое очень объемное, сложное данное можно вычислять "по частям". Вместо вычисления списка
(x1 x2 x3 ... )
можно вычислить x1 и построить структуру:
(x1 ( рецепт вычисления остальных элементов))
Получается принципиальная экономия памяти ценой незначительного перерасхода времени на вспомогательное построение. Рецепт — это ссылка на уже существующую программу, связанную с контекстом ее исполнения, т.е. с состоянием ассоциативного списка в момент построения рецепта.
(defun ряд_цел (M N) (cond ((> M N) Nil)
(T(cons M (ряд_цел (1+ M) N)))))

(defun сумма (X) (cond ((= X 0) 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 0) 0)
(T (+ (car X)( @ ( сумма (cdr X))))) ))
Чтобы исключить повторное вычисление совпадающих рецептов, в его внутреннее представление вводится флаг, имеющий значение 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)( первые ( @
(cdr Int))) )) ))
Эффект таких приостанавливаемых и возобновляемых вычислений получается путем следующей реализации операций || и @:
||e = > (lambda () e )
@e = > (e ),
что при интерпретации приводит к связыванию функционального аргумента с ассоциативным списком для операции || и к вызову функции EVAL для операции @.
Обычно в языках программирования различают вызовы по значению, по имени и по ссылке. Техника приостановки и возобновления функций может быть названа вызовом по необходимости.
В некоторых языках программирования, таких как язык SAIL и Hope, отложенные или замедленные вычисления — lazy evaluation основная модель вычислений.
Наиболее частый вариант — приостановка аргументов всех определенных пользователем функций и операции CONS. В таком случае порождаются многократные приостановки, что требует итеративного возобновления до непосредственно исполняемого рецепта.
Более подробно о тонкостях определения ленивых вычислений рассказано в книге Хендерсона

Смешанные вычисления
Идея смешанных вычислений с точки зрения реализации близка технике ленивых вычислений, но сложилась концептуально из несколько иных предпосылок. Рассматривается пара Программа-Данные при недостаточных данных, отображаемая в так называемую остаточную программу, которая может дать нужный результат, если дать недостающие данные. Для определения такого отображения понадобилась разметка действий программы на исполнимые и задерживаемые. Если такую разметку не связывать с отсутствием данных, то получается модель, практически подобная вычислениям с задержками и возобновлением.
Не всегда неопределенность части данных мешает организовать вычисление.
Рассмотрим
(if (< X Y) Z T)
или эквивалент
if X < Y then Z else T
Если X и Y не определены, но известно, что X лежит в интервале [1, 4], а Y в интервале [5, 6], то логическое выражение X<Y определено, и можно сделать вывод относительно выбора ветви условного выражения и, возможно, получить его значение.
Изучение смешанных вычислений может исходить из разных толкований понятия частичности, т.е. функций, определенных не на всей области их существования.
Первые работы Lombardi в этой области посвящены частичным вычислениям, т.е. обработке частично определенных выражений над числами. Реализация такой обработки на Лиспе осуществляла выполнимые операции и строила из полученных частичных результатов и невыполнимых операций некоторый промежуточный результат — выражение, доопределив которое, можно получить полный результат.
В.Э. Иткин оценивал частичность как практичный критерий эффективности организации деятельности.
При подготовке программ на Лиспе неопределенность часто представляют пустым списком, предполагая, что в него просто не успели что-то записать. Такое представление не всегда достаточно корректно и может потребовать дополнительных соглашений при обработке данных, по смыслу допускающих NIL в качестве определенного значения. Так, при реализации Lisp 1.5 введено соглашение, что значение атома в списке свойств хранится упакованым в список.
В работах по семантике стандартных языков программирования принято сведение к неопределенности значений любых операций, зависящих от неопределенных данных.
Это приводит на практике к необоснованным потерям части определенной информации и результатов.
A_1+...+A_100_000_000+неопределенность
-> неопределенность
Можно обратить внимание, что невелика практическая разница в уровне определенности данных вида (A …) и (A F), где F — рецепт вычисления, про который не всегда известно, приведет ли он к получению результата. Поэтому лучше было бы неопределенные данные "накрывать" рецептами, использующими специальные функции, нацеленные на раскрытие неопределенностей.
Например, роль такой функции может сыграть запрос у пользователя дополнительной информации:
(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 ‘"неопределенная функция"))

)
При отладке сложных комплексов часто неразработанные определения замещают временными "заглушками", которые помогают разобраться в будущей программе по частям. Такую работу можно стандартизировать заданием предварительных определений функций в виде отображения типа аргументов в тип результата. Соответственно, исполнение предопределенной таким образом функции можно интерпретировать как проверку аргументов на соответствие типу аргументов и выдачу в качестве результата вариантов значения, принадлежащего типу результата.
При небольшом числе значений заданного типа, например истинностные значения, может быть целесообразным полный перебор таких значений с последующим выбором реальной альтернативы пользователем.
(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))
Примерно это и делает необязательный параметр вида &optional.
Такое построение можно рассматривать как декомпозицию, разделение, сортировку на выполнимые и невыполнимые действия, при которой выполнимые действия в тексте определения замещаются их результатом, а невыполнимые преобразуются в остаточные, что все вместе образует проекцию процедуры на заданную часть ее параметров.
Многие выражения по смыслу используемых в них операций иногда определены при частичной определенности их операндов, что часто используется при оптимизаци кода программ:
X * 0 = 0
car (A …) = A
X*1 = X при любом X
X-X = 0
X/X = 1 и т.п.
Пример 12.2.
Представление функции в некоторых точках при отладке можно задать ассоциативной таблицей:
(setq f ‘((a1 . r1)(a2 . r2)(a3 . r3) …))
(defun f (x) (assoc x f))
В такое точечное определение легко добавлять недостающие пары, соответствующие нужным демонстрационным тестам при макетировании программ для согласования их функций на начальных этапах разработки, о чем еще будет речь в лекции 14.
Итак, мы получили некоторое число схем, различных с точки зрения управления вычислениями, полезных в разных ситуациях:

  • частичные;
  • интервальные;
  • многовариантные;
  • предопределения;
  • точечные;
  • проекции.

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

Асинхронные процессы и параллелизм
Полное представление об асинхронных процессах, их эффективности и проблемах организации дают работы по сетям Петри.
Заметное место среди языков функционального программирования занимают языки организации распределенных и параллельных вычислений. Практики с большой похвалой отзываются о языке функционального программирования Erlang фирмы Ericsson. Здесь мы рассмотрим один из довольно известных — язык функционального программирования SISAL.

  • создание универсального функционального языка;
  • разработка техники оптимизации для высокоэффективных параллельных программ;
  • достижение эффективности исполнения, сравнимой с императивными языками типа Fortran и C;
  • внедрение функционального стиля программирования для больших научных программ.

Название языка расшифровывется как "Streams and Iterations in a Single Assignment Language", сам он представляет собой дальнейшее развития языка VAL, известного в середине 70-х годов. Среди целей разработки языка SISAL следует отметить наиболее характерные, связанные с функциональным стилем программирования:
Эти цели содателей языка SISAL подтверждают, что функциональные языки способствуют разработке корректных параллельных программ. Одна из причин заключается в том, что функциональные программы свободны от побочних эффектов и ошибок, зависящих от реального времени. Это существенно снижает сложность отладки. Результаты переносимы на разные архитектуры, операционные системы или инструментальное окружение. В отличие от императивных языков, функциональные языки уменьшают нагрузку на кодирование, в них проще анализировать информационные потоки и схемы управления. Легко создать функциональную программу, которая является безусловно параллельной, если ее можно писать, освободившись от большинства сложностей параллельного программирования, связанных с выражением частичных отношений порядка между отдельными операциями уровня аппаратуры. Пользователь Sisal-а получает возможность сконцентрироваться на конструировании алгоритмов и раз работке программ в терминах крупноблочных и регулярно организованных построений, опираясь на естественный параллелизм уровня постановки задачи.
Начнем с примера программы:
1. Вычисление числа π (пи).
For     % инициирование цикла
Approx := 1.0;
Sign := 1.0;
Denom := 1.0;
i := 1 

while i <= Cycles do % предусловие завершения цикла
Sign := -Sign;                         % однократные
Denom := Denom + 2.0;          % присваивания
Approx := Approx + Sign / Denom;      % образуют
i := i + 1                                % тело цикла

returns Approx * 4.0
% выбор и вычисление результата цикла
end for
2. Это выражение также вычисляет число π (пи).
for i in [1..Cycles/2] do
% пространство параллельно
% исполнимых итераций

val := 1.0/real(4*i-3) — 1.0/real(4*i-1);
% тело цикла, для каждого i
% исполняемое независимо

returns sum( val )   % выбор и свертка результатов
% всех итераций цикла

end for * 4.0   % вычисление результата
% выражения
Это выражение вычисляет сумму всех вычисленных значений val и умножает результат на 4.0.
3, 4. В for-выражениях операции dot и cross могут порождать пары индексов при формировании пространства итерирования:
for i in [1..2] dot j in [3..4] do
% для пар индексов [1,3] и
% [2,4]
returns product (i+j)
% произведение сумм
end for      % = 24
for i in [1..2] cross j in [3..4] do
% для пар [1,3], [1,4], [2,3]
% и [2,4]
returns product (i+j)
% произведение сумм
end for      % = 600
5. Итеративное for-выражение с обменом данными между итерациями:
for
I := 1
while I < S do
K := I;
I := old I + 2;
% значение из предыдущей итерации
J := K + I;
returns product(I+J)
end for
Как это свойственно языкам фукнционального программирования, Sisal язык математически правильный — функции отображают аргументы в результаты без побочных эффектов, и программа строится как выражение, вырабатывающее значение. Наиболее интересна форма параллельного цикла. Она включает в себя три части: генератор пространства итераций, тело цикла и формирователь возвращаемых значений.
SISAL-программа представляет собой набор функций, допускающих частичное применение, т.е. вычисление при неполном наборе аргументов. В таком случае по исходному определению функции строятся его проекции, зависящие от остальных аргументов, что позволяет оперативно использовать эффекты смешанных вычислений и определять специальные оптимизации программ, связанные с разнообразием используемых конструкций и реализационных вариантов параллельных вычислений.
function Sum (N);   % Сумма квадратов
result (+ ( sqw (1 .. N)));
Обычно рассматривают оптимизации, обеспечивающие устранение неиспользуемого кода, чистку циклов, слияние общих подвыражений, перенос участков повторяемости для обеспечения однородности распараллеливаемых ветвей, раскрутку или разбиение цикла, втягивание константных вычислений, уменьшение силы операций, удаление копий агрегатных конструкций и др.

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