Про Лисп - Глава 2

Функции

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

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

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

2.1 Функции в качестве данных

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

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

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

2.2 Определение функций.

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

> (defun double (x) (* x 2))
DOUBLE

Скормив это Lisp, мы можем вызывать double из других функций или из верхнего уровня:

> (double 1)
2

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

Функции – это полноправные объекты. На самом деле, defun выстраивает такой объект и сохраняет его под именем, заданным первым аргументом. Помимо вызова double, мы можем выяснить, что за функция его реализует. Обычно это делают при помощи оператора #'. Этот оператор следует понимать как отображение имен на существующие функциональные объекты. Применяя его к имени double,

> #’double
#<Interpreted-Function C66ACE>

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

> (eq #’double (car (list #’double)))
T

Нам даже не нужен defun, чтобы создавать функции. Как и на большинство объектов Лисп, мы можем прямо на них ссылаться. Когда мы хотим сослаться на целое число, мы прямо используем само целое число. Для представления строки мы используем последовательность символов, окруженных двойными кавычками. Для представления функции мы используем так называемое лямбда-выражение. Лямбда-выражение – это список, состоящий из трех частей: символа лямбда, списка параметров и тела из нуля или более выражений. Лямбда-выражение ссылается на функцию, эквивалентную double:

(lambda (x) (* x 2))

Оно описывает функцию, принимающую один аргумент x и возвращающую 2x.

Лямбда-выражение также может рассматриваться как имя функции. Если double – имя собственное, как “Микеланджело”, то (lambda (x) (* x 2)) – точное определение, как “человек, расписавший свод Сикстинской капеллы”. Помещая диез-кавычку перед лямбда-выражением, мы получим соответствующую функцию:

> #’(lambda (x) (* x 2))
#<Interpreted-Function C674CE>

Эта функция ведет себя точно так же, как и double, но это два различных объекта.

При вызове функции имя функции идет в начале, а за ним следуют аргументы:

> (double 3)
6

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

> ((lambda (x) (* x 2)) 3)
6

В Коммон Лисп у нас одновременно может быть функция с именем double и переменная с именем double.

> (setq double 2)
2
> (double double)
4

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

Именно поэтому говорят, что Коммон Лисп имеет особые пространства имен для переменных и функций. У нас может быть переменная с именем foo и функция с именем foo, и им необязательно быть одинаковыми. Ситуация может сбивать с толку и приводить к определенному уродству в коде, но это что-то, с чем программисты Common Lisp вынуждены сосуществовать.

Если необходимо, Коммон Лисп предоставляет две функции, отображающие символы в значения или функции, которые они представляют. Функция symbol-value принимает символ и возвращает значение соответствующей специальной переменной:

> (symbol-value ’double)
2

в то время как symbol-function делает то же самое для глобально определенной функции:

> (symbol-function ’double)
#<Interpreted-Function C66ACE>

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

> (setq x #’append)
#<Compiled-Function 46B4BE>
> (eq (symbol-value ’x)
(symbol-function ’append))
T

За кулисами defun устанавливает symbol-function от первого аргумента на функцию, состоящую из последующих аргументов. Следующие два выражения делают примерно то же самое:

(defun double (x) (* x 2))

(setf (symbol-function ’double)
#’(lambda (x) (* x 2)))

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

2.3 Функциональные аргументы

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

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

(+12)

(apply #’+ ’(1 2))

(apply (symbol-function ’+) ’(1 2))

(apply #’(lambda (x y) (+ x y)) ’(1 2))

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

(apply #’+ 1 ’(2))

эквивалентно четырем предыдущим. Если задавать аргументы в виде списка неудобно, то мы можем использовать funcall, который отличается от apply только в этом отношении. Это выражение

(funcall #’+ 1 2)

выполняет то же действие, что и все предыдущие.

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

> (mapcar #’(lambda (x) (+ x 10)) ’(1 2 3))

(11 12 13)

> (mapcar #’+ ’(1 2 3) ’(10 100 1000))

(11 102 1003)

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

Мы уже видим, насколько удобно иметь возможность обращаться с функциями, как с данными. Во многих языках, даже если мы могли бы передать функцию в качестве аргумента чему-то, вроде mapcar, она бы, тем не менее, была функцией, определенной заранее в каком-нибудь исходном файле. Если бы требовался именно цельный код, добавляющий 10 к к каждому элементу списка, мы бы определили функцию с именем plus ten или каким-то подобным только для этого единственного применения. С помощью лямбда выражений мы можем ссылаться на функции непосредственно.

Одно из существенных отличий между Коммон Лисп и предшествовавшими ему диалектами состоит в огромном количестве встроенных функций, принимающих функциональные аргументы. Две из наиболее используемых после вездесущего mapcar – это sort и remove-if. Первая из них является функцией сортировки общего назначения. Она принимает список аргументов и предикат, а возвращает список, отсортированный пропусканием через предикат каждой пары элементов.

> (sort ’(1 4 2 5 6 7 3) #’<)
(123456 7)

Чтобы понять, как работает sort, полезно осознать, что если вы сортируете список без повторяющихся элементов с помощью <, то < вернет true, если его применить к получившемуся списку.

Если бы remove-if не был бы включен в Коммон Лисп, то это, возможно, была бы первая утилита, которую бы вы написали. Она принимает функцию и список, а возвращает все элементы списка, для которых функция вернула false.

> (remove-if #’evenp ’(123456 7))
(1357)

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

(defun our-remove-if (fn lst)

(if (null lst)

nil

(if (funcall fn (car lst))

(our-remove-if fn (cdr lst))

(cons (car lst)
(our-remove-if fn (cdr lst))))))

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

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

2.4 Функции в качестве свойств

То обстоятельство, что функции Лисп являются объектами, также позволяет нам писать программы, которые могут быть расширены на лету для работы в изменившихся условиях. Допустим, мы хотим написать функцию, принимающую аргумент – вид животного и ведущую себя соответственно. В большинстве языков естественным средством для этого будет оператор case, и мы точно так же можем это сделать и в Lisp:

(defun behave (animal)
(case animal
(dog (wag-tail) (bark))
(rat (scurry) (squeak))
(cat (rub-legs) (scratch-carpet))))

Что, если нам потребуется добавить новый тип животного? Если бы мы хотели добавить новых животных, то было бы лучше определить behave следующим образом:

(defun behave (animal)
(funcall (get animal ’behavior)))

и определить поведение отдельного животного как функцию, сохраненную, к примеру, в списке свойств его имени:

(setf (get ’dog ’behavior)

#’(lambda ()

(wag-tail)

(bark)))

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

Другой подход, несмотря на большую гибкость кажется медленным. Так и есть. Если скорость была бы критична, то мы использовали бы структуры вместо списков свойств и, главным образом, компилированные, вместо интерпретируемых функций. (Раздел 2.9 объясняет, как это сделать). Более гибкий вид кода, со структурами и компилированными функциями , может приблизиться или обогнать по скорости версии, использующие оператор case.

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

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

2.5 Связывание переменных

Common Lisp — Лисп с лексическим связыванием. Scheme является старейшим диалектом с лексическим связыванием; до Scheme динамическое связывание считалось одним из особенностей Лиспа.

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

(let ((y 7))
(defun scope-test (x)
(list x y)))

Внутри defun x является связанной переменной а y - свободной. Интерес к свободным переменным появляется потому, что неясно, каким должно быть их значение. Нет никакой неопределенности в значении связанной переменной -- когда scope-test будет вычисляться значение x будет тем, что передадут в качестве аргумента, но каким должно быть значение y? На этот вопрос могут ответить правила связывания переменных конкретного диалекта.

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

> (let ((y 5)) (scope-test 3))

(3 5)

При динамическом связывании ничего не значит тот факт, что y было связано со значением 7 при объявлении scope-test. Имеет значение только то, что y содержало значение 5 когда scope-test была вызвана.

В лиспе с лексическим связыванием вместо просматривания всей цепочки вызовов функций мы смотрим назад, на окружение в тот момент, когда функция была объявлена. В лиспе с лексическим связыванием наш пример захватит значение y в тот момент, когда scope-test была объявлена. Так что в Common Lisp произойдет следующее:

> (let ((y 5)) (scope-test 3))