книги / Функциональное программирование

Представленные ранее функционалы и функции с функциональным значением (типы 4 и 5) в отличие от обыкновенных функций (1, 2, 3), получающих в качестве аргументов и возвращающих в качестве значения данные или выражения, значением которых являются данные, называются функциями более высокого порядка (higher оrdеr). Обыкновенные функции независимо от того, рекурсивные они или нет, являются функциями первого порядка.

2.13. Применяющие функционалы

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

Применяющие функционалы родственны универсальной функции «Лиспа» EVAL. В то время как EVAL вычисляет значение произвольного выражения (формы), применяющий функционал вычисляет значение вызова некоторой функции. Интерпретатор «Лиспа» EVAL и на самом деле вызывает применяющий функционал APPLY при вычислении вызова, a APPLY, в свою очередь, вызывает EVAL при вычислении значения других форм.

Применяющие функционалы дают возможность интерпретировать и преобразовывать данные в программу и применять ее в вычислениях. Ниже мы рассмотрим применяющие функционалы интерпретатора «Лиспа» APPLY и FUNCALL.

APPLY применяет функцию к списку аргументов

APPLY является (в своей исходной форме) функцией двух аргументов, из которых первый аргумент представляет собой функцию, которая применяется к элементам списка, составляющим второй аргумент функции APPLY:

101

(APPLY fn список)  (fn 'x1’x2 … 'xN), где список = (х1 x2 … xN)

>(apply ‘+ ‘(2 3)) 5

>(apply ‘cons ‘(как (быть)))

(КАК БЫТЬ) >(setq f ‘ +)

+

>(apply ‘eval ‘(+ 2 3)) 5

>(apply ‘apply ‘(+ 2 3))

5 ; APPLY применяет себя

>(apply ‘(lambda (x y) (+ x y)) ‘(2 3)) 5

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

FUNCALL вызывает функцию с аргументами. Функционал FUNCALL по своему действию аналогичен APPLY, но аргументы для вызываемой функции он принимает не списком, а по отдельности:

(FUNCALL fn x1 x2 … xN)  (fn x1 x2 … xN).

Пример: >(funcall '+ 2 3) 5

FUNCALL и APPLY позволяют задавать вычисления (функцию) произвольной формой, например как в вызове функции, или символом, значением которого является функциональный объект. В обыкновенном вызове функции можно использовать лишь символ, связанный DEFUN с лямбда-выражением. Интерпретация имени зависит от синтаксической позиции.

102

>(setq сложение '+)

+

>(funcall сложение 2 3) 5

>(funcall (car '(+ – * /)) 2 3) 5

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

>(setq cons '+)

+

>(funcall cons 2 3) 5

>(cons 2 3) (2. 3)

Поскольку первый аргумент функционала FUNCALL вычисляется по обыкновенным правилам, то на его месте должно стоять выражение, значением которого будет функциональный объект. Функциональным аргументом может быть только «настоящая» функция. Такие специальные формы, как QUOTE и SETQ, либо макросы для этого не подходят, даже если бы их значением был функциональный объект.

2.14. Отображающие функционалы

Важный класс функционалов в практическом программировании на языке «Лисп» образуют отображающие функции, или МАР-функции (mapping function). МАР-функционалы являются функциями, которые некоторым образом отображают (map) список (последовательность) в новую последовательность или порождают побочный эффект, связанный с этой последовательностью. Имена МАР-функций начинаются на MAP, и их вызов имеет вид

103

(МАРх fn l1 l2 …lN).

Здесь l1 … lN – списки, a fn – функция от N аргументов. Как правило, МАР-функция применяется к одному аргументусписку, т.е. fn является функцией от одного аргумента:

(МАРх fn список).

Существуют два основных типа МАР-функций. Одни из них применяют функциональный аргумент fn таким образом, что его аргументами будут последовательные CAR аргументасписка (иными словами, fn применяется к элементам списка). Другие применяют функциональный аргумент к последовательным CDR списка. Результатом этих повторяющихся вычислений будет список, состоящий из результатов последовательных применений функции. Кроме того, функции отличаются друг от друга способом формирования результата. Во всех случаях число аргументов-списков должно совпадать с числом аргументов применяемой для вычислений функции.

Рассмотрим основные типы МАР-функций.

MAPCAR повторяет вычисление функции на элементах списка. Значение функции MAPCAR вычисляется путем применения функции fn к последовательным элементам xi списка, являющегося вторым аргументом MAPCAR. Например, в случае одного списка получается (с небольшими ограничениями) следующее соответствие:

(MAPCAR fn '(xl x2 … xN))  (LIST (fn 'x1) (fn ‘x2) … (fn ‘xN)).

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

мента MAPCAR.

Пример: >(setq х ‘(a b c)) (A B C)

>(mapcar ‘atom x)

104

(T T T)

>(mapcar '(lambda (у) (list (print у))) х) A

В

С

((А) (В) (С))

>(defun параl (x) (list x 1))

ПАРА1 >(mapcar 'параl x) ((A 1) (B 1) (C 1))

Если бы функции MAPCAR был передан функциональный аргумент fn с большим количеством параметров, то и у МАР-функционала было бы соответствующее количество пара- метров-списков, которые обрабатываются параллельно.

В приведенном ниже вызове, например, функциональным аргументом MAPCAR является функция CONS, которая требует двух аргументов. Вызов MAP-CAR строит список пар из соответствующих элементов двух просматриваемых списков:

>(mapcar 'cons х '(1 2 3)) ((A. 1) (B. 2) (C. 3))

>(mapcar ‘(lambda (u v) (list v u)) x ‘(1 2 3)) ((1 A) (2 B) (3 C))

MAPCAR можно определить через используемый в «Лиспе» применяющий функционал. Для случая функционального аргумента с одним параметром функция MAPCAR выглядела бы следующим образом:

(defun mapcar1 (fn l) (if (null 1) nil

(cons (funcall fn (car l)) (mapcar1 fn (cdr l)))))

Далее мы увидим, что это определение эквивалентно MAPCAR не во всех случаях.

MAPLIST повторяет вычисление на хвостовых частях списка. MAPLIST действует подобно MAPCAR, но действия осуще-

105

ствляются не над элементами списка, а над последовательными CDR этого списка:

>(maplist '(lambda (у) у) '(a b c)) ((А В С) (В С) (C))

>(maplist 'reverse '(a b с)) ((С В А) (С В) (C)) >(defun входит-ли (х)

(if (member (car x) (cdr x)) 1 0))

ВХОДИТ-ЛИ

>(setq последовательность '(ВХОДИТ ЛИ ЗНАК В ХВОСТ)) (ВХОДИТ ЛИ ЗНАК В ХВОСТ)

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

MAPCAN и MAPCON объединяют результаты. Функции MAPCAN и MAPCON являются аналогами функций MAPCAR и MAPLIST. Отличие состоит в том, что MAPCAN и MAPCON не строят, используя LIST, новый список из результатов, а объединяют списки, являющиеся результатами, в один список, используя структуроразрушающую псевдофункцию NCONC. При использовании этих псевдофункций нужно соблюдать осторожность. MAPCAN (с небольшими ограничениями) можно представить в виде вызова NCONC следующим образом (сравните с представлением MAPCAR через вызов LIST):

(MAPCAN fn '(x1 x2 … xN))  (NCONC (fn ‘x1) (fn ‘x2) (fn ‘x3) … (fn 'xN)).

>(mapcan ‘list ‘(a b c)) (A B C)

>(mapcon ‘list ‘(a b c)) (A B C B C C)

>(mapcan ‘cons ‘(a b c) ‘(1 2 3)) (A B C)

>(mapcon ‘cons ‘(a b c) ‘(1 2 3)) ((A B C) 1 2 3 (B C) 2 3 (C) 3)

106

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

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

>(mapcar ‘numberp ‘(1 2 мимо 3)) (T T NIL T)

>(mapcan ‘(lambda (x)

(if (numberp x) ‘(t) nil))

‘(1 2 мимо 3)) (T T T)

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

Например, функцией ПОСЛЕДНИЙ можно отсеять из списка буквы, оставив по одной в том порядке, в котором они входили в список в последний раз:

>(defun последний (х) (if (eql (входит-ли х) 0)

(list (car x))

nil))

ПОСЛЕДНИЙ >последовательность

(В Х O Д И Т Л И З Н А К В Х В O С Т) >(mapcon 'последний последовательность) (Д Л И З Н А К Х В О С Т)

MAPCAN и MAPCON можно определить через MAPCAR и MAPLIST следующим образом:

107

(MAPCAN fn x1 х2… xN)  (APPLY 'NCONC (MAPCAR fn x1 x2… xN))

(MAPCON fn x1 x2…xN)  (APPLY 'NCONC (MAPLIST fn x1 x2…xN))

МАРС и MAPL теряют результаты. Функции МАРС и MAPL2 также аналогичны функциям MAPCAR и MAPLIST, но отличаются от них и от функций MAPCAN и MAPCON тем, что не собирают и не объединяют результаты. Возникающие результаты просто теряются. В качестве значения возвращается значение второго аргумента функции:

(МАРС fn список) (PROG2 (MAPCAR fn список) список) (MAPL fn список) (PROG2 (MAPLIST fn список) список)

Псевдофункционалы МАРС и MAPL прежде всего используют для получения побочного эффекта:

>(mapc '(lambda (u v) (set u v)) ‘(a b с) ‘(1 2 3)) (А В С)

>b

2

Композиция функционалов

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

Например, прямое произведение двух числовых множеств можно определить через два вложенных цикла, которые можно выразить с помощью композиции двух вложенных вызовов функционала MAPCAR:

(defun декартово (x y) (mapcar

'(lambda (x)

(mapcar '(lambda (y) (list x y))

y))

2 В более старых версиях языка «Лисп» функция MAPL носит имя MAP.

108

x))

> (декартово '(a b с) '(1 2 3))

((А 1) (А 2) (А 3) (В 1) (В 2) (В 3) (С 1) (С 2) (С 3))

Функционалы могут, подобно функциям, комбинироваться с использованием различных видов рекурсии. Если вызов функционала встречается в его собственном определении, то функционал будет рекурсивным. Например, приведенное нами ранее определение MAPCAR рекурсивно.

В следующем определении декартова произведения внешний цикл выражен через рекурсию, а внутренний – через функ-

ционал MAPLIST:

(defun декартово (х у) (cond

((null x) nil) (t (append

(maplist '(lambda (u) (list (car x)

(car u)))

y)

(декартово (cdr x) y)))))

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

Итоговая таблица отображающих функций

В качестве итога и с целью повторения приведем в виде таблицы МАР-функции, предназначенные для аргументов, записанных в виде списков (табл. 4).

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

109

2.15. Макросы

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

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

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

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

110