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

Смешанные вычисления

Идея смешанных вычислений с точки зрения реализации близка технике ленивых вычислений, но сложилась концептуально из несколько иных предпосылок [9]. Рассматривается пара Программа-Данные при недостаточных данных, отображаемая в так называемую остаточную программу, которая может дать нужный результат, если дать недостающие данные. Для определения такого отображения понадобилась разметка действий программы на исполнимые и задерживаемые. Если такую разметку не связывать с отсутствием данных, то получается модель, практически подобная вычислениям с задержками и возобновлением .

Не всегда неопределенность части данных мешает организовать вычисление.

Рассмотрим

(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 введено соглашение, что значение атома в списке свойств хранится упакованным в список [1].

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

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

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))

Примерно это и делает необязательный параметр вида $$\text{\}$$ optional в языке Clisp.

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

Многие выражения по смыслу используемых в них операций иногда определены при частичной определенности их операндов, что часто используется при оптимизации кода программ:

X * 0 = 0
CAR (A …) = A
X*1 = X при любом X
X-X = 0
X/X = 1 и т.п.

Представление функции в некоторых точках при отладке можно задать ассоциативной таблицей:

(SETQ f ‘((a1 . r1)(a2 . r2)(a3 . r3) …))
(DEFUN f (x) (assoc x f))

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

Итак, мы получили некоторое число схем, различных с точки зрения управления вычислениями, полезных в разных ситуациях:

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

Асинхронные процессы и параллелизм

Полное представление об асинхронных процессах, их эффективности и проблемах организации дают работы по сетям Петри.

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

Название языка расшифровывается как "Streams and Iterations in a Single Assignment Language", сам он представляет собой дальнейшее развития языка VAL, известного в середине 70-х годов. Среди целей разработки языка SISAL следует отметить наиболее характерные, связанные с функциональным стилем программирования:

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

Начнем с примера программы:

1. Вычисление числа $$\pi$$ (пи).

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. Это выражение также вычисляет число $$\pi$$ (пи).

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 язык математически правильный — функции отображают аргументы в результаты без побочных эффектов, и программа строится как выражение, вырабатывающее значение. Наиболее интересна форма параллельного цикла. Она выделяет три части: for - генератор пространства итераций, do - тело цикла и returns - формирователь возвращаемых значений.

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

function Sum (N);   % Сумма квадратов
   result (+ ( sqw (1 .. N)));

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