globalf5-240972240972 (850810), страница 30
Текст из файла (страница 30)
ГородняяОсновы функционального программированияX/X = 1 и т.п.Пример 12.2.Представление функции в некоторых точках при отладке можно задатьассоциативной таблицей:(SETQ f ‘((a1 . r1)(a2 . r2)(a3 . r3) …))(DEFUN f (x) (assoc x f))В такое точечное определение легко добавлять недостающие пары,соответствующиенужнымдемонстрационнымтестампримакетировании программ для согласования их функций на начальныхэтапах разработки, о чем еще будет речь в лекции 14.Итак, мы получили некоторое число схем, различных с точки зренияуправления вычислениями, полезных в разных ситуациях:частичные;интервальные;многовариантные;предопределения;точечные;проекции.Возможны и другие, обеспечивающие оптимизацию, компиляцию,предвычисления, макрогенерацию текста программы, что вперспективе может покрыть полное пространство обработки программв рамках единой методики.
Например, основой единого подхода можетбыть так называемый трансформационный подход, заключающийся всведении смешанных вычислений к преобразованию программпосредством набора базовых трансформаций.Асинхронные процессы и параллелизмПолное представление об асинхронных процессах, их эффективности ипроблемах организации дают работы по сетям Петри.Заметное место среди языков функционального программирования204Л.В. ГородняяОсновы функционального программированиязанимают языки организации распределенных и параллельныхвычислений.
Практики с большой похвалой отзываются о языкефункционального программирования Erlang фирмы Ericsson. Здесь мырассмотрим один из довольно известных — язык функциональногопрограммирования SISAL [11].создание универсального функционального языка;разработка техники оптимизации для высокоэффективныхпараллельных программ;достижениеэффективностиисполнения,сравнимойсимперативными языками типа Fortran и C;внедрение функционального стиля программирования длябольших научных программ.Название языка расшифровывается как "Streams and Iterations in a SingleAssignment Language", сам он представляет собой дальнейшее развитияязыка VAL, известного в середине 70-х годов.
Среди целей разработкиязыка SISAL следует отметить наиболее характерные, связанные сфункциональным стилем программирования:создание универсального функционального языка;разработка техники оптимизации для высокоэффективныхпараллельных программ;достижениеэффективностиисполнения,сравнимойсимперативными языками типа Fortran и C;внедрение функционального стиля программирования длябольших научных программ.Эти цели создателей языка SISAL подтверждают, что функциональныеязыки способствуют разработке корректных параллельных программ.Одна из причин заключается в том, что функциональные программысвободны от побочных эффектов и ошибок, зависящих от реальноговремени.
Это существенно снижает сложность отладки. Результатыпереносимы на разные архитектуры, операционные системы илиинструментальное окружение. В отличие от императивных языков,функциональные языки уменьшают нагрузку на кодирование, в нихпроще анализировать информационные потоки и схемы управления.Легко создать функциональную программу, которая является безусловно205Л.В.
ГородняяОсновы функционального программированияпараллельной, если ее можно писать, освободившись от большинствасложностейпараллельногопрограммирования,связанныхсвыражением частичных отношений порядка между отдельнымиоперациями уровня аппаратуры. Пользователь языка SISAL -а получаетвозможность сконцентрироваться на конструировании алгоритмов и разработке программ в терминах крупноблочных и регулярноорганизованных построений, опираясь на естественный параллелизмуровня постановки задачи.Начнем с примера программы:1. Вычисление числа(пи).For % инициирование циклаApprox := 1.0;Sign := 1.0;Denom := 1.0;i := 1while i <= Cycles do % предусловие завершения циклаSign := -Sign;% однократныеDenom := Denom + 2.0;% присваиванияApprox := Approx + Sign / Denom;% образуютi := i + 1% тело циклаreturns Approx * 4.0% выбор и вычисление результата циклаend for2.
Это выражение также вычисляет число(пи).for i in [1..Cycles/2] do% пространство параллельно% исполнимых итерацийval := 1.0/real(4*i-3) — 1.0/real(4*i-1);% тело цикла, для каждого i% исполняемое независимоreturns sum( val ) % выбор и свертка результатов206Л.В. ГородняяОсновы функционального программирования% всех итераций цикла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 % = 24for i in [1..2] cross j in [3..4] do% для пар [1,3], [1,4], [2,3]% и [2,4]returns product (i+j)% произведение суммend for % = 6005.
Итеративное for-выражение с обменом данными между итерациями:forI := 1while I < S doK := I;I := old I + 2;% значение из предыдущей итерацииJ := K + I;returns product(I+J)end forКак это свойственно языкам функнционального программирования,Sisal язык математически правильный — функции отображаютаргументы в результаты без побочных эффектов, и программа строитсякак выражение, вырабатывающее значение.
Наиболее интересна форма207Л.В. ГородняяОсновы функционального программированияпараллельного цикла. Она выделяет три части: for - генераторпространства итераций, do - тело цикла и returns - формировательвозвращаемых значений.SISAL -программа представляет собой набор функций, допускающихчастичное применение, т.е. вычисление при неполном набореаргументов. В таком случае по исходному определению функциистроятся его проекции, зависящие от остальных аргументов, чтопозволяет оперативно использовать эффекты смешанных вычислений иопределять специальные оптимизации программ, связанные сразнообразием используемых конструкций и реализационныхвариантов параллельных вычислений.function Sum (N); % Сумма квадратовresult (+ ( sqw (1 ..
N)));Обычно рассматривают оптимизации, обеспечивающие устранениенеиспользуемого кода, чистку циклов, слияние общих подвыражений,перенос участков повторяемости для обеспечения однородностираспараллеливаемых ветвей, раскрутку или разбиение цикла,втягивание константных вычислений, уменьшение силы операций,удаление копий агрегатных конструкций и др.208Л.В. ГородняяОсновы функционального программированияФункции высших порядковРассматривается аппарат функций высших порядков при организациивысококвалифицированных процессов информационной обработки,использующей формализацию и спецификацию данных, таких каксинтаксическийанализ,кодогенерация,конструированиеинтерпретаторов и компиляторов по формальному определениюреализуемого языка — так называемые синтаксически управлямыеметоды информационной обработки.Ранжирование функцийПрименение функций высших порядков естественным образомзавершает освоение функционального программирования каклогической системы, допускающей конструирование функциональныхобъектов при решении задач регулярной обработки формализованнойинформации.
Подобные задачи возникают при реализации и настройкесложных информационных систем, таких как операционные системы,системы программирования, текстовые и графические процессоры,системы управления базами данных, поддержки проектов и т.п.Функции высших порядков используют другие функции в качествеаргументов или вырабатывают их как результат.(DEFUN mul-N (N) #'(LAMBDA (x) (* x N))); конструктор семейства функций, множащих; аргумент на N(funcall (mul-N 25) 7); применение частной функции, умножающей на 25Правильность выражений с такими функциями требует корректнойподстановки параметров и учета ранга функции, определяющеговозможность манипулирования функциональнымизначениями.Функции можно ранжировать на основе так называемых типовыхвыражений, представляющих области определения и значенияфункций.
Например,x+1 : Number -> Number209Л.В. ГородняяОсновы функционального программированияx+y : (Number Number) -> NumberОтсутствие таких средств в языкесоответствующими комментариями [3].Суперпозицию функцийтиповыми выражениями:можноможнокомпенсироватьхарактеризоватьследующимиS(h,g) = { при h: X -> Y, g: Y -> Z строит f=g(h) — суперпозиция }: (X->Y Y->Z)->(X->Z)(defun super (f g)#'(LAMBDA (x) (funcall f (funcall g x)) )); конструктор суперпозиции функций(funcall (super #'CAR #'CDR) '(1 2 3)); применение суперпозиции CAR и CDRДвойное применение функции можно определить независимо иличерез суперпозицию — типовое выражение от этого не зависит, но онопредставляет собой параметризованное выражение.W f = ((LAMBDA (x)(f (f x))) = S (f,f){ дважды применяется функция }: (Number->Number) -> (Number->Number)или более точно:: (X->X) -> (X->X),где X — произвольный тип значения.
Типовое выражение представляетзависимость от этого типа — параметризованный тип значения .(DEFUN duble (f)#'(LAMBDA (x) (funcall f(funcall f x)) )); конструктор двойного применения функции(funcall (duble #'CAR) '(((1) 2) 3)) ;= (1)(defun duble (f) (funcall #'super f f))210Л.В. ГородняяОсновы функционального программирования; двойное применение функции через суперпозицию(funcall (duble #'CAR) '(((A B) B) C)); = (A B)Можно ввести обозначения:Atom — атомы,Number — число,List (X) — NIL или списки из элементов типа X,Bool — NIL или T,Some — любой объект,(X . Y) – консолидация X и Y,Y != X – элементы типа Y кроме элементов типа X.Соответственно пишутся типовые выражения для элементарныхфункций:conscarcdreqatomnull: (X List (X)) -> List (X): List (X) -> X: List (X) -> List (X): (Atom Atom) -> Bool: Some -> Bool: (Atom -> T) | (List (X) -> NIL): Some -> Bool: (NIL -> T) | (Some != NIL -> NIL)& (List(X)\=NIL -> NIL)Таким же образом можно специфицировать и универсальную функцию:EVAL [e, al]:(Some List( (Atom .
Some ) )) -> Some| || List( (Atom . Some) )Some{ могут попасть и неправильные выражения }APPLY [fn, (a1 a2 …), al] : (List( Some ) -> Some| || List( Some )| || List((Atom . Some) )| ||) -> Some| ||211Л.В. ГородняяОсновы функционального программирования| || List((Atom . Some))| List(Some)(List(Some) -> SomeОтображающий функционал также может характеризоваться типовымвыражением:map [x, f]:( List(X) (X -> Y) ) -> List(Y)(DEFUN map (x f)(COND (x (CONS (funcall f (CAR x))(map (CDR x) f )))))(map '((1) (2) (3)) #'CAR ) ;= (1 2 3)Можно специфицировать функцию, непосредственно преобразующуюсвой функциональный аргумент в новую функцию, отображающуюсписок.mapf [f]: List(X -> Y) -> ( List(X) -> List(Y))(DEFUN mapf (f) #'(LAMBDA (x)(COND (x (CONS (funcall f (CAR x))(funcall (mapf f ) (CDR x)) ))) ))(funcall (mapf #'CAR ) ;=(1 2 3)Аргумент может быть списком функций, результаты которых следуетсобрать в общий список.manyfun [lf] : List(X->Y) -> (X -> List(Y))|||_____список результатов функций||||_____тип аргумента отдельной функции||____________________список функций(DEFUN manyfun (lf) #'(LAMBDA (x)(COND (lf (CONS (funcall (CAR lf) x)(funcall (manyfun (CDR lf)) x) ))) ))212Л.В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
