На Lisp - Глава 3

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

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

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

3.1 Функциональное проектирование

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

Функциональное программирование означает написание программ, которые работают за счет возврата значений, а не за счет побочных действий. Побочные действия включают в себя деструктивные изменения объектов (напр. rplaca) и присвоения переменным (напр. setq). Если побочные действия немногочисленны и локализованы, то программы становится легче читать, тестировать и отлаживать. Lisp-программисты не всегда писали в таком стиле, но со временем Lisp и функциональное программирование постепенно стали неразделимы.

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

(defun bad-reverse (lst)

(let* ((len (length lst))

(ilimit (truncate (/ len 2))))

(do ((i 0 (1+ i))

(j (1- len) (1- j)))

((>= i ilimit))

(rotatef (nth i lst) (nth j lst)))))

Рис. 3.1. Функция, инвертирующая списки.

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

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

> (setq lst ’(a b c))

(A B C)

> (bad-reverse lst)

NIL

> lst

(C B A)

Ее имя подсказывает, что bad-reverse далека от хорошего Lisp-стиля. Кроме того, ее уродство заразно: так как она работает при помощи побочных действий, то также уводит в сторону от функционального идеала вызвавшие ее функции.

Хотя, выступая в роли злодея, у bad-reverse есть одно достоинство: она демонстрирует идиому Common Lisp для перестановки двух значений. Макрос rotatef переворачивает значения любого числа обобщенных переменных, то есть выражения, которые можно передать setf в качестве первого аргумента. Результатом применения непосредственно к двум аргументам будет их перестановка.

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

> (setq lst ’(a b c))

(A B C)

> (good-reverse lst)

(C B A)

> lst

(A B C)

(defun good-reverse (lst)

(labels ((rev (lst acc)

(if (null lst)

acc

(rev (cdr lst) (cons (car lst) acc)))))

(rev lst nil)))

Рисунок 3.2. Функция, возвращающая инвертированные списки.

Раньше считалось, что можно судить о чьем-то характере, глядя на форму его головы. Относится ли это в самом деле к людям или нет, но как правило, применимо к Lisp-программам. Внешний вид функциональных программ отличается от внешнего вида императивных. Структурно функциональная программа -- это всегда композия аргументов внутри выражений, а так как аргументы можно индентировать, то функциональный код оказывается более разнообразным в плане индентации. Функциональный код выглядит гибким 1), а императивный код выглядит сплошным и блочным, как Basic.

1) Типичный пример приведен на странице 242.

Мы видим, не вдаваясь в детали, исходя из внешнего вида bad- и good-reverse, какая из программ лучше. Несмотря на то, что good-reverse короче и также более эффективна: O(n) вместо O(n^2).

Мы избежали проблемы написания reverse, поскольку Common Lisp имеет встроенную. Имеет смысл ненадолго взглянуть на эту функцию, потому что она часто выявляет неправильные представления о функциональном программировании. Как и good-reverse, встроенная reverse возвращает значение, не изменяя аргументов. Но изучающие Lisp могут подумать, что она, как и bad-reverse,

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

(reverse lst)

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

(setq lst (reverse lst))

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

Сравнивая bad- и good-reverse, мы не придали значения одной из особенностей, заключающейся в том, что bad-reverse не синтезирует целое из частей. Вместо создания новой структуры списка, она работает с исходным списком. Это может быть опасно: список может потребоваться где-либо еще в программе, но иногда бывает необходимо ради производительности. Для таких случаев Common Lisp предоставляет O(n) деструктивную инвертирующую функцию, которая называется nreverse.

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

(nreverse lst)

в середине функции, полагая, что после этого lst будет инвертирован. Вот, что происходит в большинстве реализаций:

> (setq lst ’(a b c))

(A B C)

> (nreverse lst)

(C B A)

> lst

(A)

Для инвертирования lst можно было бы присвоить lst возвращаемое значение, как в случае с обычным reverse.

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

(nconc x y)

почти всегда производит те же действия, что и

(setq x (nconc x y))

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

Лишь несколько операторов Lisp предназначены для вызова с целью получения побочных действий. Вообще, встроенные операторы задумывались для вызова ради возращаемых ими значений. Такие названия, как sort, remove или substitute, не должны вводить в заблуждение. Если вам нужны побочные действия, применяйте setq к возвращаемому значению.

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

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

set setq setf psetf psetq incf decf push pop pushnew

rplaca rplacd rotatef shiftf remf remprop remhash

и также let*, в которых нередко скрываются императивные программы. Применение этих операторов, как облагаемых налогом, лишь помогает приблизиться к хорошему Lisp-стилю, а не служит для него критерием. Тем не менее, лишь одно это позволит вам удивительно далеко зайти.

В других языках одной из наиболее частых причин возникновения побочных действий является необходимость возврата функцией нескольких значений. Если функции способны вернуть лишь одно значение, то они должны <<вернуть>> оставшиеся путем изменения собственных параметров. К счастью, это не требуется в Common Lisp, так как любая функция может вернуть несколько значений.

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

> (truncate 26.21875)

26

0.21875

Когда вызывающий код требует одно значение, будет использовано первое:

> (= (truncate 26.21875) 26)

T

Вызывающий код может получить оба возвращаемых значения при помощи multiple-value-bind. Этот оператор принимает список переменных, вызов, а также программный код. Код выполняется с привязкой переменных к соответствующим возвращаемым вызовом значениям:

> (multiple-value-bind (int frac) (truncate 26.21875)

(list int frac))

(26 0.21875)

Наконец, чтобы возвращать несколько значений, мы используем оператор values:

> (defun powers (x)

(values x (sqrt x) (expt x 2)))

POWERS

> (multiple-value-bind (base root square) (powers 4)

(list base root square))

(4 2.0 16)

Вообще, функциональное программирование -- хорошая идея. И особенно хорошая в Lisp, так как Lisp развивался для того, чтобы его поддерживать. FIXME Встроенные операторы, такие как reverse и nreverse, предполагается использовать в таком ключе. Другие операторы, как values и multiple-value-bind, были разработаны как раз для того, чтобы сделать функциональное программирование легче.

Императивное программирование наизнанку

Возможно, цели функционального программирования станут более понятными в процессе сравнения с другим, более распространенным подходом -- императивным программированием. Функциональная программа говорит вам то, что она хочет; императивная же говорит вам, что делать. Функциональная программа говорит: <<Вернуть список, состоящий из a и квадрата первого элемента x>>:

(defun fun (x)

(list ’a (expt (car x) 2)))

Императивная программа говорит: <<Взять первый элемент x, затем возвести его в квадрат, затем вернуть список, состоящий из a и квадрата>>:

(defun imp (x)

(let (y sqr)

(setq y (car x))

(setq sqr (expt y 2))

(list ’a sqr)))