Языки функционального программирования

Идеи ФП достаточно полно поддержаны в проекте Lisp 1.5, выполненном Дж. Маккарти и его коллегами. В этом исключительно мощном языке не только реализованы основные средства, обеспечившие практичность и ре- зультативность ФП, но и впервые опробован целый ряд поразительно точных построений, ценных как концептуально, так и методически и конструктивно, понимание и осмысление которых слишком отстает от практики применения. Понятийно функциональный потенциал языка Lisp 1.5 в значительной мере унаследован стандартом Common Lisp.

Языки ФП достаточно разнообразны. Существует и активно применяется более трехсот диалектов Lisp-а и родственных ему языков: Interlisp, muLisp,

 

 

Clisp, Sсheme, ML, Cmucl, Logo, Hope, Sisal, Haskell, Miranda и др. При срав- нении языков программирования часто классифицируют функциональные языки по следующим критериям: «ленивый» или аппликативный, последова- тельный или параллельный. Например, ML является аппликативным и после- довательным, Erlang – аппликативным и параллельным, Haskell – «ленивым» и последовательным, а Clean – параллельным и «ленивым».

В рамках проекта.Net выполнено большое число реализаций различных языков программирования, в числе которых Haskell, Sml, Scheme, Mondrian, Mercury, Perl, Oberon, Component Pascal, Разработан F# – новый язык ФП. Еще большее разнообразие предлагает проект DotGNU, пытающийся отсто- ять приоритет в области разработки переносимого ПО. Развиваются линии учебного и любительского программирования и методично осваивается тех- ника выстраивания иерархии абстрактных машин при определении языков программирования.

Разработка языков функционального программирования (ЯФП) и приспо- собленность средств ФП к быстрой отладке, верификации, их лаконизм, гиб- кость, конструктивность и моделирующая сила позволяют рассматривать ФП как основу информационной среды обучения современному программирова- нию на всех уровнях проблематики от алгоритмизации до включения в соци- альный контекст приложений разрабатываемых ИС с использованием любых парадигм.

 

Отображения и функционалы

Выразительная сила ЯФП наиболее ярко проявляется в программирова- нии отображений. Отображения обычно используются при анализе и обра- ботке данных, представляющих информацию разной природы. Вычисление, кодирование, трансляция, распознавание – каждый из таких процессов ис- пользует исходное множество цифр, шаблонов, текстов, идентификаторов, по которым конкретная отображающая функция находит пронумерованный объект, строит закодированный текст, выделяет идентифицированный фраг- мент, получает зашифрованное сообщение. Так работает любое введение обозначений – от знака переход к его смыслу.

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

 

 

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

Говорят, что отображение существует, если задана пара множеств и отоб- ражающая функция, для которой первое множество – область определения, а второе – область значения. При определении отображений, прежде всего, должны быть ясны ответы на следующие вопросы:

– что представляет собой отображающая функция;

– как организовано данное, представляющее отображаемое множество;

– каким способом выделяются элементы отображаемого множества, пе- редаваемые в качестве аргументов отображающей функции;

– как организовано данное, представляющее результат отображения.

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

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

– где размещается множество полученных результатов;

– чем отличаются нужные результаты от полученных попутно;

– как строятся итоговые данные из отобранных результатов.

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

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

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

 

 

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

Отказ от барьера между представлениями функций и значений дает воз- можность использовать символьные выражения как для изображения задан- ных значений, включая любые структуры над числами и строками, так и для представления функций, обрабатывающих любые данные. (Напоминаем, что определение функции представляется как данное.) Таким образом, функцио- налы в ЯФП – это функции, которые используют в качестве аргументов или результатов представления других функций, а не собственно функции как принято говорить. При построении функционалов переменные могут играть роль имен функций, представления которых находятся во внешних форму- лах, использующих функционалы.

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

 

Определение	Примечание
(DEFUN map-el(fn xl)   (COND(xl (CONS (FUNCALL fn (CAR xl) (map-el fn (CDR xl)) ))))	Поэлементное преобразование XL с помощью функции FN. Пока XL не пуст, присоединяем результат FN от головы XL к списку преобразованных остальных элементов
(map-el #'1+xl)16	Следующие числа
(map-el #'CAR xl)	«головы» элементов = CAR
(map-el #'length xl)	Длины элементов

Пример 20. Отображение элементов списка с помощью заданной функции

 

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

Можно определить функцию покомпонентной обработки двух списков с помощью заданной функции FN.

 

 

Определение	Примечание
(DEFUN map-comp (fn al vl) (COND (al (CONS (FUNCALL fn (CAR al) (CAR vl)) (map-comp (CDR al) (CDR vl)) ))))	fn покомпонентно применить к соответственным элементам al и vl Пока AL не пуст   Присоединяем результат FN от голов AL и VL к списку преобразованных остальных элементов
(map-comp #'+   '(1 2 3) '(4 6 9))	= (5 8 12) Суммы
(map-comp #'*  '(1 2 3) '(4 6 9))	= (4 12 27) Произведения
(map-comp #'CONS'(1 2 3) '(4 6 9))	= ((1. 4) (2. 6) (3. 9)) Пары
(map-comp #'EQ'(4 2 3) '(4 6 9))	= (T NIL NIL) Сравнения

Пример 21. Покомпонентные действия над векторами, представленными с помощью списков

#’x – эквивалент (FUNCTION x), что в Clisp является представлением функции в качестве аргумента.

Можно задать поток функций, применяемых к общему аргументу.

 

Определение	Примечание
(DEFUN mapf (fl ex) (COND (fl (CONS (FUNCALL (CAR fl) ex)   (mapf (CDR fl) ex) ))))	Пока FL не пуст, присоединяем результат очередной   функции от EX к списку результатов остальных функций
(mapf '(length CAR CDR) '(a b c d))	= (4 a (b c d))

Пример 22. Применение списка функций к общему аргументу

 

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

 

 

Определение	Примечание
(DEFUN map-f-e (fl el) (COND (fl (CONS (FUNCALL (CAR fl) (CAR el))   (map-f-e (CDR fl) (CDR el)) ))))	Пока FL не пуст, присоединяем результат очередной функции от очередного элемента EL   к списку результатов остальных Функций от остальных элементов
(mapf '(length CAR CDR) '((a b c d) (c d) (3 4 5)))	= (4 c (4 5))

Пример 23. Применение списка функций к списку аргументов

 

Композициями таких функционалов можно применять серии функций к списку общих аргументов или к параллельно заданной последовательности списков их аргументов. Естественно, и серии, и последовательности пред- ставляются списками.

Немногим сложнее и определение фильтра-свертки.

 

Определение	Примечание
(DEFUN map-r (fl ex) (COND (fl (APPEND (FUNCALL fl ex)   (map-r (CDR fl) ex) ))))	Пока FL не пуст, присоединяем результат очередной функции от EX к списку результатов остальных функций
(map-r ' CDR '((a b c d) (d) (e f))	= (b c d f)

Пример 24. Фильтрация результатов отображения – APPEND исключает пустые списки

 

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

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

– отображающие функционалы позволяют строить программы из круп- ных действий;

– функционалы обеспечивают гибкость отображений;

 

 

– определение функции может совсем не зависеть от конкретных имен;

– с помощью функционалов можно управлять выбором формы результа- тов;

– параметром функционала может быть представление любой функции, преобразующей элементы структуры;

– функционалы позволяют формировать серии функций от общих дан- ных;

– встроенные в Clisp функционалы приспособлены к покомпонентной об- работке произвольного числа параметров;

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

Отложенные действия

Императивная организация вычислений по принципу немедленного и обязательного выполнения каждой очередной команды не всегда результа- тивна. Существует много неимперативных моделей управления процессами, позволяющих прерывать и откладывать процессы, а потом восстанавливать их и запускать или отменять. Организация такого управления, достаточного для оптимизации и программирования параллельных процессов, реализуется с помощью так называемых «замедленных» или «ленивых» вычислений (lazy evaluation). Основная идея таких вычислений заключается в сведении вызо- вов функций к представлению рецептов их вычисления, содержащих замы- кания функций в определенном контексте:

(λ () fn) – заблокировать вычисление «fn», превратив его в тело функции без аргументов;

(fn) – разблокировать выражение «fn» в форме вызова функции без пара- метров.

Непосредственное применение таких формул влечет многократное вы- числение «fn», поэтому в инструментальном ядре обычно используется реа- лизационная структура данных, названная «рецепт», хранящая варианты представления выражения:

{    [F  (fn.  e)] | [T x]}²¹

Сначала рецепт представлен как «(F (fn. e))», где «(fn. e)» – это замыка- ние выражения «fn» в пределах контекста «e», задающего значения свобод- ных переменных. Попытка вычисления рецепта приводит к замене его ре- зультатом. По прежнему адресу размещается структура «(T x)», в которой «x» равен результату вычисления «fn» в контексте «e».

21 { } – аналог вариантных записей в языке Паскаль или Union в языке Си.

 

 

Таблица 28