Функциональная модель взаимодействия монад

Определение Примечание   (DEFUN eval-p (e c) (COND ((ATOM e) (value e c)) ((ATOM (CAR e))(COND ((get (CAR e) 'MONAD ((get (CAR e) ' MONAD) (CDR e) c))   До применения функции выясняем ее категорию, кото- рой соответствует свое пра- вило интепретации (T (apply-p (CAR e)(evlis (CDR e) c) c)) )) (T (apply-p (CAR e)(evlis (CDR e) c) c))

Примерно то же самое обеспечивают определения EVAL-P и APPLY-P, рассчитанные на использование списков свойств атома для хранения посто- янных значений и функциональных определений. Индикатор MONAD ука- зывает в списке свойств атома на правило интерпретации функций, относя- щихся к отдельной монаде, MACRO – на частный метод построения пред- ставления функции. Функция VALUE реализует методы поиска текущего значения переменной в зависимости от контекста и свойств атомов.

 

 

))

 

 

Пример 31. Функции разных категорий, аналог был реализован в MuLisp

 

Функция GET выбирает из списка свойств атома заданное свойство.

 

Определение	Примечание
(DEFUN EVAL-P (E C)
(COND ((ATOM E) (VALUE E C))
((ATOM (CAR E))(COND ((GET (CAR E) 'MONAD)	До применения функ-
((GET (CAR E) ' MONAD) (CDR E) C))	ции выясняем ее кате-
(T (APPLY-P (CAR E)(EVLIS (CDR E) C) C))	горию
))
(T (APPLY-P (CAR E)(EVLIS (CDR E) C) C))
))

Пример 32. Функции разных категорий

Каждое имя функции сопровождается свойством MONAD, задающим правило применения фукнции.

 

Определение	Примечание
(DEFUN APPLY-P (F ARGS C)
(COND ((ATOM F)(APPLY-P (FUNCTION F C) ARGS C))
((ATOM (CAR F))(COND ((GET (CAR F) 'MACRO)	Для макрофункций
(APPLY-P ((GET (CAR F) 'MACRO)	нет необходимости
(CDR F) C) ARGS C))	в вычислении аргу-
(T (APPLY-P (EVAL F E) ARGS C))	мента
))
(T (APPLY-P (EVAL F E) ARGS C))
))

Пример 33. Специальные макрофункции поддерживают пост-вычисления параметров

Или то же самое с вынесением общих подвыражений во вспомогатель- ные параметры.

 

Определение	Примечание
(DEFUN EVAL-P (E C)
(COND ((ATOM E) (VALUE E C))
((ATOM (CAR E))
((LAMBDA (V) (COND (V (V(CDR E) C))	Однократный поиск катего-
(T (APPLY-P (CAR E)(EVLIS (CDR E) C) C	рии
)) (GET (CAR E) ' MONAD)))
(T (APPLY-P (CAR E)(EVLIS (CDR E) C) C))
))

Пример 34. Исключение лишнего поиска свойства MONAD

 

 

Выражение (GET (CAR E) ' MONAD) вычисляется и как параметр переда- ется в тело безымянной функции.

 

Определение	Примечание
(DEFUN APPLY-P (F ARGS C)
(COND ((ATOM F)(APPLY-P (FUNCTION F C) ARGS C
((ATOM (CAR F))
((LAMBDA (V) (COND (V (APPLY-P (V (CDR F)
C) ARGS C))
(T (APPLY-P (EVAL F E) ARGS C))
))(GET (CAR F) 'MACRO)))
(T (APPLY-P (EVAL F E) ARGS C))
))	Однократный поиск
	свойства

Пример 35. Исключение лишнего поиска свойства MACRO

Расширение системы программирования при таком определении интер- претации осуществляется простым введением/удалением соответствующих свойств атомов и функций.

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

Моделирующую силу языка Lisp покажем на еще одном примере: Функция REV, обращающая список и все подсписки, столь же есте-

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

 

Pascal	Примечание
function REV (x: list):list;   label A, B; var y, z: list; begin A: if null (x) then REV:= y;	Определение функции REV, вырабатывающей список. Объявлены метки и локальные переменные.   Меткой «A» помечена проверка завершения
z:= car (x); if atom (z) then goto B;	и результат. Выбор очередного элемента для реверсирования. Для атома переход на метку «В» в обход реверсирования

Пример 36 (начало). Представление программы на языке Pascal. Функция rev

обращает все уровни списка так, что rev от (A ((B C) D)) даст ((D (C B))A)

 

Pascal	Примечание
z:= REV (z); B: y:= cons (z, y); x:= cdr (x); goto A; end;	Замена элемента на его реверс. Меткой «В» помечена сборка результата.   Шаг продвижения по списку.   Переход на метку «А» для дальнейшего реверсирования

Пример 36 (окончание). Представление программы на языке Pascal. Функция rev

обращает все уровни списка так, что rev от (A ((B C) D)) даст ((D (C B))A)

 

Lisp	Примечание
(defun REV (X) (prog (Y Z)   A (cond ((null X)(return Y))) (setq Z (car X))   (cond ((atom Z)(goto B))) (setq Z (rev Z)) B (setq Y (cons Z Y)) (setq X (cdr X)) (go A) ))	Определение функции REV, реализуемая императивно с переменными.   «A» помечает завершение и дан результат. Выбор очередного элемента для реверсирования. Для атома переход на метку «В» в обход реверсирования. Замена элемента на его реверс.   «В» помечает сборка реверсируемого списка. Шаг продвижения по списку. Переход на метку «А» для дальнейшего реверсирования

Пример 37. Представление программы на языке Lisp

В принципе, SET и SETQ могут быть реализованы с помощью ассоциа- тивного списка примерно так же, как и поиск значения, только с сохранением связей, расположенных ранее изменяемой переменной:

(defun SET (X Y) (cons (cons X Y) Alist)))

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

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

 

 

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

Наиболее очевидные следствия из выбранных принципов ФП:

– раскрутка СП – процесс разработки программ разбивается на фазы: по- строение базиса и его пошаговое расширение;

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

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

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

Язык программирования Lisp и сложившееся на его основе функциональ- ное программирование реально показали свои сильные стороны как инстру- ментарий исследования и освоения новых областей применения вычисли- тельной техники. Это аргумент в пользу функционального подхода к реше- нию новых сложных задач:

– доступны преобразования программ и процессов;

– осуществима лингвистическая обработка информации;

– поддерживается гибкое управление базами данных;

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

– моделирование общения.

 

Спецификация

Таблица 30