(Это глава 2 из книги ANSI Common Lisp, автор Пол Грэм. Copyright 1995, Prentice-Hall.)
Добро пожаловать в Lisp
Цель этой главы - как можно скорее начать программировать. К концу главы вы будете знать достаточно языка Common Lisp, чтобы начать писать программы.
2.1 Форма
Для Lisp особенно верно то, что вы изучаете его, используя его, потому что Lisp - это интерактивный язык. Любая система Lisp включает в себя интерактивный интерфейс, называемый верхним уровнем. Вы вводите выражения Lisp в toplevel, а система отображает их значения.
Обычно Lisp выводит подсказку, чтобы сообщить вам, что он ждет, пока вы что-то напечатаете. Многие реализации Common Lisp используют > в качестве подсказки уровня. Это то, что мы будем использовать здесь.
Одним из простейших видов выражений Lisp является целое число. Если мы введем 1 после подсказки,
> 1 1 >
система выведет его значение, а затем еще один запрос, чтобы сказать, что она готова к дальнейшим действиям.
В данном случае выведенное значение совпадает с тем, что мы набрали. Число, подобное 1, как говорят, оценивает само себя. Жизнь становится интереснее, когда мы вводим выражения, для оценки которых требуется определенная работа. Например, если мы хотим сложить два числа, мы вводим что-то вроде:
> (+ 2 3) 5
В выражении (+ 2 3) символ + называется оператором, а числа 2 и 3 - аргументами.
В повседневной жизни мы бы записали это выражение как 2 + 3, но в Lisp мы ставим сначала оператор +, затем аргументы, а все выражение заключаем в круглые скобки: (+ 2 3). Это называется префиксной нотацией, потому что оператор стоит первым. Поначалу это может показаться странным способом записи выражений, но на самом деле эта нотация - одна из лучших в Lisp.
Например, если мы хотим сложить три числа, то в обычной нотации нам придется дважды использовать +,
2 + 3 + 4
в то время как в Lisp мы просто добавляем еще один аргумент:
(+ 2 3 4)
Как мы обычно используем +, он должен иметь ровно два аргумента: один слева и один справа. Гибкость префиксной нотации означает, что в Lisp + может принимать любое количество аргументов, в том числе и ни одного:
> (+) 0 > (+ 2) 2 > (+ 2 3) 5 > (+ 2 3 4) 9 > (+ 2 3 4 5) 14
Поскольку операторы могут принимать различное количество аргументов, нам нужны круглые скобки, чтобы показать, где начинается и заканчивается выражение.
Выражения могут быть вложенными. То есть аргументы в выражении могут сами быть сложными выражениями:
> (/ (- 7 1) (- 4 2)) 3
В английском языке это семь минус один, деленное на четыре минус два.
Еще одна прелесть нотации Lisp: это все, что есть. Все выражения Lisp - это либо атомы, такие как 1, либо списки, состоящие из нуля или более выражений, заключенных в круглые скобки. Это допустимые выражения Lisp:
2 (+ 2 3) (+ 2 3 4) (/ (- 7 1) (- 4 2))
Как мы увидим, весь код Lisp имеет такую форму. Язык типа C имеет более сложный синтаксис: арифметические выражения используют инфиксную нотацию; вызовы функций используют своего рода префиксную нотацию, с аргументами, разделенными запятыми; выражения разделены точками с запятой; блоки кода разделены фигурными скобками. В Lisp мы используем единую нотацию для выражения всех этих идей.
2.2 Оценка
В предыдущем разделе мы вводили выражения на верхнем уровне, а Lisp отображал их значения. В этом разделе мы подробнее рассмотрим, как оцениваются выражения.
В Lisp + - это функция, а выражение типа (+ 2 3) - это вызов функции. Когда Lisp оценивает вызов функции, он делает это в два этапа:
Если какие-либо аргументы сами являются вызовами функций, то они оцениваются по тем же правилам. Поэтому, когда оценивается (/ (- 7 1) (- 4 2)), происходит следующее:
Не все операторы в Common Lisp являются функциями, но большинство из них. И вызовы функций всегда оцениваются таким образом. Аргумент оценивается слева направо, а его значения передаются в функцию, которая возвращает значение выражения в целом. Это называется правилом оценки в Common Lisp.
Один из операторов, который не соответствует правилу оценки Common Lisp, - это оператор quote. Оператор quote - это специальный оператор, то есть у него есть свое собственное правило оценки. И это правило гласит: ничего не делать. Оператор quote принимает единственный аргумент и просто возвращает его дословно:
> (quote (+ 3 5)) (+ 3 5)
Для удобства Common Lisp определяет ' как сокращение для цитаты. Вы можете получить эффект вызова quote, добавив символ ' перед любым выражением:
> '(+ 3 5) (+ 3 5)
Гораздо чаще используется сокращение, чем записывается все выражение в кавычках.
Lisp предоставляет кавычки как способ защиты выражений от оценки. В следующем разделе будет рассказано, как такая защита может быть полезна.
---------------------------------------------------------------------
Выход из затруднительного положения
Если вы введете что-то, что Lisp не сможет понять, он выдаст сообщение об ошибке и переведет вас в версию уровня toplevel, называемую циклом прерывания. Петля прерывания дает опытным программистам шанс разобраться, что вызвало ошибку, но изначально единственное, что вы захотите сделать в петле прерывания, это выйти из нее. Что нужно набрать, чтобы вернуться на верхний уровень, зависит от вашей реализации Common Lisp. В этой гипотетической реализации это делает :abort:
> (/ 1 0) Error: Division by zero. Options: :abort, :backtrace >> :abort >
В Приложении А показано, как отлаживать программы на Lisp, и приведены примеры некоторых наиболее распространенных ошибок.
---------------------------------------------------------------------
2.3 Данные
Lisp предлагает все типы данных, которые встречаются в большинстве других языков, а также несколько других, которые нам не знакомы. Одним из типов данных, который мы уже использовали, является целое число, которое записывается как ряд цифр: 256. Другой тип данных, который Lisp имеет с большинством других языков, - это строка, которая представляется в виде серии символов, окруженных двойными кавычками: "ora et labora". И целое число, и строка оцениваются сами по себе.
Два типа данных Lisp, которые мы не часто встречаем в других языках, - это символы и списки. Символы - это слова.Обычно они преобразуются в верхний регистр, независимо от того, как вы их набираете:
> 'Artichoke ARTICHOKE
Символы (обычно) не оцениваются сами по себе, поэтому, если вы хотите сослаться на символ, вы должны заключить его в кавычки, как указано выше.
Списки представляются как ноль или более элементов, заключенных в круглые скобки. Элементы могут быть любого типа, включая списки. Списки нужно заключать в кавычки, иначе Lisp примет их за вызовы функций:
> '(my 3 "Sons") (MY 3 "Sons") > '(the list (a b c) has 3 elements) (THE LIST (A B C) HAS 3 ELEMENTS)
Обратите внимание, что одна кавычка защищает все выражение, включая выражения внутри него.
Вы можете строить списки, вызывая функцию list. Поскольку list - это функция, ее аргументы оцениваются. Здесь мы видим вызов + внутри вызова list:
> (list 'my (+ 2 1) "Sons") (MY 3 "Sons")
Теперь мы можем оценить одну из самых замечательных особенностей Lisp. Программы на Lisp выражаются в виде списков. Если аргументы гибкости и элегантности не убедили вас в том, что нотация Lisp является ценным инструментом, то этот пункт должен убедить вас. Это означает, что программы на Lisp могут генерировать код на Lisp. Программисты на Lisp могут (и часто так и делают) писать программы, которые пишут за них их программы.
Такие программы не рассматриваются до главы 10, но даже на этом этапе важно понимать связь между выражением и списками, хотя бы для того, чтобы не запутаться в ней. Вот почему нам нужна кавычка. Если список заключен в кавычки, то оценка возвращает сам список; если список не заключен в кавычки, то список рассматривается как код, и оценка возвращает его значение:
> (list '(+ 2 1) (+ 2 1)) ((+ 2 1) 3)
Здесь первый аргумент заключен в кавычки, поэтому получается список. Второй аргумент не заключен в кавычки и рассматривается как вызов функции, давая число.
В Common Lisp есть два способа представления пустого списка. Вы можете представить его в виде пары круглых скобок, между которыми ничего нет, или использовать символ nil. Не имеет значения, каким способом вы запишете пустой список, но он будет отображаться как nil:
> () NIL > nil NIL
Вам не нужно заключать nil в кавычки (хотя это не помешает), потому что nil оценивает сам себя.
2.4 Операции со списками
Функция cons строит списки. Если ее второй аргумент - список, она возвращает новый список с первым аргументом, добавленным в начало:
> (cons 'a '(b c d)) (A B C D)
Мы можем строить списки, объединяя новые элементы в пустой список. Функция list, которую мы рассматривали в предыдущем разделе, - это просто более удобный способ объединения нескольких элементов в nil:
> (cons 'a (cons 'b nil)) (A B) > (list 'a 'b) (A B)
Примитивными функциями для извлечения элементов списков являются car и cdr. [1] Car списка - это первый элемент, а cdr - все, что находится после первого элемента:
> (car '(a b c)) A > (cdr '(a b c)) (B C)
Вы можете использовать комбинации car и cdr для получения любого элемента списка. Если вы хотите получить третий элемент, вы можете сказать:
> (car (cdr (cdr '(a b c d)))) C
Однако вы можете сделать то же самое более простым способом, вызвав third:
> (third '(a b c d)) C
2.5 Истина
В языке Common Lisp символ t является стандартным представлением истины. Как и nil, t оценивает сам себя. Функция listp возвращает true, если ее аргумент является списком:
> (listp '(a b c)) T
Функция, возвращаемое значение которой можно интерпретировать как истину или ложь, называется предикатом. Предикаты Common Lisp часто имеют имена, заканчивающиеся на p.
Ложность в Common Lisp представлена nil, пустым списком. Если мы дадим listp аргумент, который не является списком, он вернет nil:
> (listp 27) NIL
Поскольку nil играет две роли в Common Lisp, функция null, которая возвращает true пустого списка,
> (null nil) T
и функция not, которая возвращает true, если ее аргумент false,
> (not nil) T
делают точно то же самое.
Простейшим условным выражением в Common Lisp является if. Обычно он принимает три аргумента: тестовое выражение, выражение then и выражение else. Оценивается тестовое выражение. Если оно возвращает true, то оценивается выражение then и возвращается его значение. Если тестовое выражение возвращает false, то оценивается выражение else и возвращается его значение:
> (if (listp '(a b c)) (+ 1 2) (+ 5 6)) 3 > (if (listp 27) (+ 1 2) (+ 5 6)) 11
Как и quote, if - это специальный оператор. Он не может быть реализован как функция, потому что аргументы в вызове функции всегда оцениваются, а смысл if в том, что оценивается только один из двух последних аргументов.
Последний аргумент if является необязательным. Если вы его опустите, то по умолчанию он будет равен nil:
> (if (listp 27) (+ 2 3)) NIL
Хотя t является стандартным представлением истины, все, кроме nil, также считается истинным в логическом контексте:
> (if 27 1 2) 1
Логические операторы and и or похожи на условные обозначения. Оба принимают любое количество аргументов, но оценивают только столько, сколько нужно, чтобы решить, что вернуть. Если все его аргументы истинны (то есть не nil), то and возвращает значение последнего из них:
> (and t (+ 1 2)) 3
Но если один из аргументов окажется ложным, ни один из последующих аргументов не будет оценен. Аналогично для оператора or, который останавливается, как только находит аргумент, который является истинным.
Эти два оператора являются макросами. Как и специальные операторы, макросы могут обходить обычное правило оценки. В главе 10 объясняется, как писать собственные макросы.
2.6 Функции
Вы можете определять новые функции с помощью функции defun. Обычно она принимает три или более аргументов: имя, список параметров и одно или несколько выражений, которые будут составлять тело функции. Вот как мы можем определить третью функцию:
> (defun our-third (x) (car (cdr (cdr x)))) OUR-THIRD
Первый аргумент говорит, что имя этой функции будет our-third. Второй аргумент, список (x), говорит, что функция будет принимать ровно один аргумент: x. Символ, используемый таким образом в качестве заполнителя, называется переменной. Когда переменная представляет собой аргумент функции, как это делает x, она также называется параметром.
Остальная часть определения, (car (cdr (cdr x))), называется телом функции. Оно сообщает Lisp, что он должен сделать, чтобы вычислить возвращаемое значение функции. Таким образом, вызов функции our-third возвращает (car (cdr (cdr x))) для любого x, который мы передаем в качестве аргумента:
> (our-third '(a b c d)) C
Теперь, когда мы познакомились с переменными, легче понять, что такое символы. Это имена переменных, существующие как самостоятельные объекты. Именно поэтому символы, как и списки, должны заключаться в кавычки. Список должен быть заключен в кавычки, потому что иначе он будет рассматриваться как код; символ должен быть заключен в кавычки, потому что иначе он будет рассматриваться как переменная.
Определение функции можно рассматривать как обобщенную версию выражения Lisp. Следующее выражение проверяет, больше ли сумма 1 и 4, чем 3:
> (> (+ 1 4) 3) T
Заменив эти конкретные числа переменными, мы можем написать функцию, которая будет проверять, больше ли сумма любых двух чисел, чем третье:
> (defun sum-greater (x y z) (> (+ x y) z)) SUM-GREATER > (sum-greater 1 4 3) T
Lisp не делает различий между программой, процедурой и функцией. Функции используются для всего (и действительно, составляют большую часть самого языка). Если вы хотите считать одну из ваших функций главной, вы можете это сделать, но, как правило, вы сможете вызывать любую функцию с верхнего уровня. Помимо прочего, это означает, что вы сможете тестировать свои программы по частям по мере их написания.
2.7 Рекурсия
Функции, которые мы определили в предыдущем разделе, вызывали другие функции для выполнения за них некоторой работы. Например, sum-greater вызывала + и >. Функция может вызывать любую функцию, включая саму себя.
Функция, которая вызывает саму себя, является рекурсивной. Функция-член Common Lisp проверяет, является ли что-то элементом списка. Вот упрощенная версия, определенная как рекурсивная функция:
(defun our-member (obj lst) (if (null lst) nil (if (eql (car lst) obj) lst (our-member obj (cdr lst)))))
Предикат eql проверяет, являются ли два его аргумента одинаковыми; кроме этого, все в этом определении - это то, что мы уже видели раньше. Вот оно в действии:
> (our-member 'b '(a b c)) (B C) > (our-member 'z '(a b c)) NIL
Определение our-member соответствует следующему английскому описанию. Чтобы проверить, является ли объект obj членом списка lst, мы
Когда вы хотите понять, как работает рекурсивная функция, вам может помочь перевод ее в описание такого рода.
Многим людям поначалу трудно понять рекурсию. Во многом трудности возникают из-за использования ошибочной метафоры для функций. Существует тенденция рассматривать функцию как некую машину. Сырье поступает в качестве параметров; часть работы передается другим функциям; наконец, готовый продукт собирается и отправляется в качестве возвращаемого значения. Если мы используем эту метафору для функций, рекурсия становится парадоксом. Как машина может перепоручить работу самой себе? Она и так уже занята.
Лучшей метафорой для функции будет представление о ней как о процессе, через который человек проходит. Рекурсия естественна в процессе. Мы часто видим рекурсивные процессы в повседневной жизни. Например, предположим, что историк интересуется изменениями численности населения в истории Европы. Процесс изучения документа мог бы выглядеть следующим образом:
Этот процесс достаточно прост для понимания, однако он рекурсивен, поскольку третий шаг может повлечь за собой одно или несколько применений того же процесса.
Поэтому не думайте о our-member как о машине, которая проверяет, есть ли что-то в списке. Вместо этого думайте о нем как о правилах определения того, находится ли что-то в списке. Если мы думаем о функциях в этом свете, парадокс рекурсии исчезает. [2]
2.8 Чтение Lisp
Псевдочлен, определенный в предыдущем разделе, заканчивается пятью круглыми скобками. Более сложные определения функций могут заканчиваться семью или восемью. Людей, которые только изучают Lisp, вид такого количества скобок обескураживает. Как читать, а тем более писать такой код? Как увидеть, какая скобка соответствует какой?
Ответ заключается в том, что это и не нужно. Программисты Lisp читают и пишут код по отступам, а не по скобкам. Когда они пишут код, они позволяют текстовому редактору показать, какая скобка какой соответствует. Любой хороший редактор, особенно если он поставляется вместе с системой Lisp, должен уметь выполнять паренс-сопоставление. В таком редакторе, когда вы вводите скобку, редактор показывает, какая из них совпадает. Если в вашем редакторе нет функции сопоставления скобок, остановитесь сейчас и выясните, как ее сделать, потому что без нее практически невозможно писать код на Lisp.
[В vi вы можете включить паренс-сопоставление с помощью :set sm. В Emacs хороший способ - M-x lisp-mode].
В хорошем редакторе согласование скобок перестает быть проблемой при написании кода. А поскольку существуют универсальные соглашения для отступов в Lisp, это не является проблемой и при чтении кода. Поскольку все используют одни и те же соглашения, вы можете читать код по отступам и не обращать внимания на скобки.
Любой хакер Lisp, каким бы опытным он ни был, затруднился бы прочитать определение our-member, если бы оно выглядело следующим образом:
(defun our-member (obj lst) (if (null lst) nil (if (eql (car lst) obj) lst (our-member obj (cdr lst)))))
Но когда код правильно отделен отступом, проблем не возникает. Можно опустить большую часть скобок и все равно прочитать его:
defun our-member (obj lst) if null lst nil if eql (car lst) obj lst our-member obj (cdr lst)
Действительно, это практичный подход, когда вы пишете код на бумаге. Позже, когда вы набираете его, вы можете воспользоваться преимуществами парен-сопоставления в редакторе.
2.9 Ввод и вывод
До сих пор мы выполняли ввод/вывод неявно, используя преимущества уровня toplevel. Для реальных интерактивных программ этого, скорее всего, будет недостаточно. В этом разделе мы рассмотрим несколько функций для ввода и вывода.
Наиболее общей функцией вывода в Common Lisp является format. Она принимает два или более аргументов: первый указывает, куда должен быть выведен вывод, второй является шаблоном строки, а остальные аргументы обычно являются объектами, чьи печатные представления должны быть вставлены в шаблон. Вот типичный пример:
> (format t "~A plus ~A equals ~A.~%" 2 3 (+ 2 3)) 2 plus 3 equals 5. NIL
Обратите внимание, что здесь отображаются две вещи. Первая строка отображается форматом. Вторая строка - это значение, возвращенное вызовом format, которое отображается обычным образом на верхнем уровне. Как правило, функция типа format не вызывается непосредственно с уровня toplevel, а используется внутри программы, поэтому возвращаемое значение никогда не будет не видно.
Первый аргумент format, t, указывает, что вывод должен быть отправлен в место по умолчанию. Как правило, это будет уровень toplevel. Второй аргумент - это строка, которая служит шаблоном для вывода. В этой строке каждый ~A указывает на позицию, которая должна быть заполнена, а ~% указывает на новую строку. Позиции заполняются значениями остальных аргументов по порядку.
Стандартной функцией ввода является read. Если аргументы не заданы, она читает из места по умолчанию, которое обычно является верхним уровнем. Вот функция, которая запрашивает у пользователя ввод и возвращает все, что было введено:
(defun askem (string) (format t "~A" string) (read))
Он ведет себя следующим образом:
> (askem "How old are you? ") How old are you? 29 29
Имейте в виду, что read будет ждать бесконечно долго, пока вы не напечатаете что-нибудь и (обычно) не нажмете кнопку return. Поэтому неразумно вызывать read без явной подсказки, иначе может создаться впечатление, что ваша программа застряла, а на самом деле она просто ждет ввода.
Второе, что нужно знать о read, это то, что он очень мощный: read - это полноценный синтаксический анализатор Lisp. Он не просто считывает символы и возвращает их в виде строки. Он разбирает то, что читает, и возвращает объект Lisp, который получается в результате. В приведенном выше случае он вернул число.
Короткое определение askem показывает то, чего мы раньше не видели в функциях. Ее тело содержит более одного выражения. Тело функции может содержать любое количество выражений. Когда функция будет вызвана, они будут оценены по порядку, и функция вернет значение последнего из них.
Во всех предыдущих разделах мы придерживались так называемого "чистого" Lisp, то есть Lisp без побочных эффектов. Побочный эффект - это некоторое изменение состояния мира, которое происходит как следствие оценки выражения. Когда мы оцениваем чистое выражение Lisp, такое как (+ 1 2), никаких побочных эффектов нет; оно просто возвращает значение. Но когда мы вызываем format, он не только возвращает значение, но и что-то печатает. Это один из видов побочных эффектов.
Когда мы пишем код без побочных эффектов, нет смысла определять функции с телами, состоящими более чем из одного выражения. Значение последнего выражения возвращается как значение функции, а значения всех предыдущих выражений отбрасываются. Если бы у таких выражений не было побочных эффектов, вы бы не смогли определить, потрудился ли Lisp оценить их вообще.
2.10 Переменные
Одним из наиболее часто используемых операторов в Common Lisp является let, который позволяет вводить новые локальные переменные:
> (let ((x 1) (y 2)) (+ x y)) 3
Выражение let состоит из двух частей. Сначала идет список инструкций для создания переменных, каждая из которых имеет вид (выражение переменной). Каждая переменная изначально будет установлена в значение соответствующего выражения. Так, в приведенном выше примере мы создаем две новые переменные, x и y, которые первоначально устанавливаются в значения 1 и 2 соответственно. Эти переменные действуют в теле let.
После списка переменных и значений идет тело выражений, которые оцениваются по порядку. В данном случае только одно - вызов +. Значение последнего выражения возвращается как значение let. Вот пример более выборочной версии askem, написанной с использованием let:
(defun ask-number () (format t "Please enter a number. ") (let ((val (read))) (if (numberp val) val (ask-number))))
Эта функция создает переменную val для хранения объекта, возвращенного функцией read. Поскольку у нее есть управление этим объектом, функция может посмотреть, что вы ввели, прежде чем решить, возвращать его или нет. Как вы, наверное, догадались, numberp - это предикат, который проверяет, является ли его аргумент числом.
Если значение, введенное пользователем, не является числом, ask-number вызывает саму себя. В результате получается функция, которая настаивает на получении числа:
> (ask-number) Please enter a number. a Please enter a number. (ho hum) Please enter a number. 52 52
Переменные, подобные тем, которые мы видели до сих пор, называются локальными переменными. Они действительны только в определенном контексте. Существует другой вид переменных, называемый глобальной переменной, которая может быть видна везде.
[На самом деле здесь существует различие между лексическими и специальными переменными, но мы не будем рассматривать этот вопрос до главы 6].
Вы можете создать глобальную переменную, задав символ и значение параметру defparameter:
> (defparameter *glob* 99) *GLOB*
Такая переменная будет доступна везде, кроме выражений, создающих новую локальную переменную с тем же именем. Чтобы избежать случайного возникновения такой ситуации, принято давать глобальным переменным имена, начинающиеся и заканчивающиеся звездочками. Имя переменной, которую мы только что создали, будет звучать как "star-glob-star".
Вы также можете определить глобальные константы, вызвав команду defconstant:
(defconstant limit (+ *glob* 1))
Нет необходимости давать константам отличительные имена, поскольку это приведет к ошибке, если кто-то использует такое же имя для переменной. Если вы хотите проверить, является ли некоторый символ именем глобальной переменной или константы, используйте boundp:
> (boundp '*glob*) T
2.11 Присваивание
В Common Lisp наиболее общим оператором присваивания является setf. Мы можем использовать его для присваивания переменным любого типа:
> (setf *glob* 98) 98 > (let ((n 10)) (setf n 2) n) 2
Если первым аргументом setf является символ, который не является именем локальной переменной, он принимается за глобальную переменную:
> (setf x (list 'a 'b 'c)) (A B C)
То есть, вы можете создавать глобальные переменные неявно, просто присваивая им значения. В исходных файлах, по крайней мере, лучше использовать явные параметры defparameters.
Вы можете делать больше, чем просто присваивать значения переменным. Первым аргументом setf может быть как выражение, так и имя переменной. В таких случаях значение второго аргумента вставляется в то место, на которое ссылается первый:
> (setf (car x) 'n) N > x (N B C)
Первым аргументом оператора setf может быть практически любое выражение, которое ссылается на определенное место. Все такие операторы помечены как "устанавливаемые" в Приложении D.
Вы можете задать любое (четное) количество аргументов для setf. Выражение вида
(setf a b c d e f)
эквивалентно трем отдельным последовательным вызовам setf:
(setf a b) (setf c d) (setf e f)
2.12 Функциональное программирование
Функциональное программирование означает написание программ, которые работают путем возврата значений, а не путем изменения вещей. Это доминирующая парадигма в Lisp. Большинство встроенных функций Lisp предназначены для вызова возвращаемых ими значений, а не для побочных эффектов.
Функция remove, например, принимает объект и список и возвращает новый список, содержащий все, кроме этого объекта:
> (setf lst '(c a r a t)) (C A R A T) > (remove 'a lst) (C R T)
Почему бы просто не сказать, что remove удаляет объект из списка? Потому что это не то, что он делает. Исходный список после этого остается нетронутым:
> lst (C A R A T)
Что же делать, если вы действительно хотите удалить что-то из списка? В Lisp вы обычно делаете такие вещи, передавая список в качестве аргумента некоторой функции и используя setf с возвращаемым значением. Чтобы удалить все as из списка x, мы говорим:
(setf x (remove 'a x))
Функциональное программирование означает, по сути, отказ от setf и подобных ему вещей. На первый взгляд может быть трудно представить, как это вообще возможно, не говоря уже о желательности. Как можно строить программы, просто возвращая значения?
Было бы неудобно полностью обойтись без побочных эффектов. Однако, читая дальше, вы можете с удивлением обнаружить, как мало их на самом деле нужно. И чем больше побочных эффектов вы оставите, тем лучше вам будет.
Одним из важнейших преимуществ функционального программирования является возможность интерактивного тестирования. В чисто функциональном коде вы можете тестировать каждую функцию по мере ее написания. Если она возвращает ожидаемые значения, вы можете быть уверены в ее правильности. Эта уверенность в совокупности дает огромную разницу. Вы можете мгновенно вносить изменения в любое место программы. И это мгновенное решение позволяет создать совершенно новый стиль программирования, так же как телефон, по сравнению с письмами, позволил создать новый стиль общения.
2.13 Итерация
Когда мы хотим сделать что-то многократно, иногда естественнее использовать итерацию, чем рекурсию. Типичным случаем итерации является генерация какой-либо таблицы. Эта функция
(defun show-squares (start end) (do ((i start (+ i 1))) ((> i end) 'done) (format t "~A ~A~%" i (* i i))))
выводит квадраты целых чисел от начала до конца:
> (show-squares 2 5) 2 4 3 9 4 16 5 25 DONE
Макрос do - это фундаментальный оператор итерации в Common Lisp. Как и let, do может создавать переменные, и первым аргументом является список спецификаций переменных. Каждый элемент этого списка может иметь вид
(переменная начальная обновить)
где variable - символ, а initial и update - выражения. Изначально каждая переменная будет установлена в значение соответствующего initial; на каждой итерации она будет установлена в значение соответствующего update. Do в show-squares создает только одну переменную, i. На первой итерации i будет установлена в значение start, а на последующих итерациях ее значение будет увеличиваться на единицу.
Вторым аргументом do должен быть список, содержащий одно или несколько выражений. Первое выражение используется для проверки того, должна ли итерация остановиться. В приведенном выше случае тестовым выражением является (> i end). Остальные выражения в этом списке будут оценены по порядку, когда итерация остановится, и значение последнего будет возвращено в качестве значения do. Таким образом, show-squares всегда будет возвращать done.
Остальные аргументы do составляют тело цикла. Они будут оцениваться по порядку на каждой итерации. На каждой итерации обновляются переменные, затем оценивается тест на завершение, а затем (если тест не прошел) оценивается тело цикла.
Для сравнения, вот рекурсивная версия show-squares:
(defun show-squares (i end) (if (> i end) 'done (progn (format t "~A ~A~%" i (* i i)) (show-squares (+ i 1) end))))
Единственное, что является новым в этой функции, - это progn. Она принимает любое количество выражений, оценивает их по порядку и возвращает значение последнего.
В Common Lisp есть более простые операторы итерации для особых случаев. Например, для итерации по элементам списка вам скорее всего понадобится dolist. Вот функция, которая возвращает длину списка:
(defun our-length (lst) (let ((len 0)) (dolist (obj lst) (setf len (+ len 1))) len))
Здесь dolist принимает аргумент вида (выражение переменной), за которым следует тело выражений. Тело будет оценено с привязкой переменной к последовательным элементам списка, возвращенного выражением. Таким образом, цикл выше говорит: для каждого obj в lst увеличить len.
Очевидной рекурсивной версией этой функции будет:
(defun our-length (lst) (if (null lst) 0 (+ (our-length (cdr lst)) 1)))
Или, если список пуст, его длина равна нулю, в противном случае - это длина cdr плюс единица. Эта версия our-length чище, но поскольку она не является хвостовой рекурсивной (раздел 13.2), она не будет такой эффективной.
2.14 Функции как объекты
В Lisp функции - это обычные объекты, такие же, как символы, строки или списки. Если мы передадим имя функции в функцию function, она вернет связанный с ней объект. Как и quote, function - это специальный оператор, поэтому нам не нужно заключать аргумент в кавычки:
> (function +) #<Compiled-Function + 17BA4E>
Это странно выглядящее возвращаемое значение - способ отображения функции в типичной реализации Common Lisp.
До сих пор мы имели дело только с объектами, которые при отображении Lisp выглядят так же, как и при вводе. Это соглашение не относится к функциям. Внутри встроенной функции, такой как +, скорее всего, будет сегмент кода машинного языка. Реализация Common Lisp может выбрать любое внешнее представление.
Точно так же, как мы можем использовать ' в качестве сокращения для цитаты, мы можем использовать \#' в качестве сокращения для функции:
> #'+ #<Compiled-Function + 17BA4E>
Эта аббревиатура известна как sharp-quote.
Как и любой другой объект, мы можем передавать функции в качестве аргументов. Одной из функций, принимающих функцию в качестве аргумента, является apply. Она принимает функцию и список аргументов для нее, и возвращает результат применения функции к аргументам:
> (apply #'+ '(1 2 3)) 6 > (+ 1 2 3) 6
Ему можно передать любое количество аргументов, лишь бы последний из них был списком:
> (apply #'+ 1 2 '(3 4 5)) 15
Функция funcall делает то же самое, но не требует, чтобы аргументы были упакованы в список:
> (funcall #'+ 1 2 3) 6
Макрос defun создает функцию и дает ей имя. Но функции не обязательно должны иметь имена, и нам не нужен defun для их определения. Как и большинство других объектов Lisp, мы можем ссылаться на функции буквально.
Для буквального обозначения целого числа мы используем серию цифр; для буквального обозначения функции мы используем так называемое лямбда-выражение. Лямбда-выражение - это список, содержащий символ lambda, за которым следует список параметров, а затем тело из нуля или более выражений.
Вот выражение лямбда, представляющее функцию, которая принимает два числа и возвращает их сумму:
(lambda (x y) (+ x y))
Список (x y) - это список параметров, а после него идет тело функции.
Лямбда-выражение можно рассматривать как имя функции. Как и имя обычной функции, лямбда-выражение может быть первым элементом вызова функции,
> ((lambda (x) (+ x 100)) 1) 101
и, прикрепив к лямбда-выражению кавычки, мы получим соответствующую функцию,
> (funcall #'(lambda (x) (+ x 100)) 1) 101
Кроме всего прочего, эта нотация позволяет нам использовать функции, не называя их.
-----------------------------------------------------------------
Что такое лямбда?
Лямбда в выражении лямбда не является оператором. Это просто символ. [3] В ранних диалектах Lisp он имел определенное назначение: функции представлялись внутри как списки, и единственным способом отличить функцию от обычного списка было проверить, является ли первый элемент символом лямбды.
В Common Lisp вы можете выражать функции в виде списков, но внутри они представлены как отдельные объекты функций. Поэтому лямбда больше не нужна. Нет никакого несоответствия в требовании, чтобы функции обозначались как
((x) (+ x 100))
вместо
(lambda (x) (+ x 100))
но программисты Lisp привыкли начинать функции с символа лямбда, поэтому Common Lisp сохранил его ради традиции.
-----------------------------------------------------------------
2.15 Типы
В Lisp необычайно гибкий подход к типам. Во многих языках переменные - это то, что имеет типы, и вы не можете использовать переменную, не указав ее тип. В Common Lisp типы имеют значения, а не переменные. Можно представить, что к каждому объекту прикреплена метка, определяющая его тип. Такой подход называется явной типизацией. Вам не нужно объявлять типы переменных, потому что любая переменная может содержать объекты любого типа.
Хотя объявление типов никогда не является обязательным, вы можете захотеть сделать его из соображений эффективности. Объявление типов обсуждается в разделе 13.3.
Встроенные типы Common Lisp образуют иерархию подтипов и супертипов. Объект всегда имеет более одного типа. Например, число 27 имеет типы fixnum, integer, rational, real, number, atom и t, в порядке возрастания общности. (Числовые типы рассматриваются в главе 9.) Тип t является супертипом всех типов, поэтому все имеет тип t.
Функция typep принимает объект и спецификатор типа и возвращает true, если объект относится к данному типу:
> (typep 27 'integer) T
Мы будем упоминать различные встроенные типы по мере их появления.
2.16 Забегая вперед
В этой главе мы едва коснулись поверхности Lisp. И все же портрет очень необычного языка начинает вырисовываться. Начнем с того, что язык имеет единый синтаксис для выражения всей структуры программы. Этот синтаксис основан на списке, который является разновидностью объекта Lisp. Функции, которые сами по себе являются объектами Lisp. сами по себе, могут быть выражены в виде списков. А сам Lisp - это программа на Lisp, состоящая почти полностью из функций Lisp, ничем не отличающихся от тех, которые вы можете определить сами.
Не волнуйтесь, если связи между всеми этими идеями не совсем понятны. Lisp вводит так много новых понятий, что потребуется некоторое время, чтобы привыкнуть ко всем новым вещам, которые вы можете делать с его помощью. По крайней мере, одно должно быть ясно: здесь есть несколько поразительно элегантных идей.
Ричард Гэбриэл однажды полушутливо назвал C языком для написания Unix. [4] Точно так же мы могли бы описать Lisp как язык для написания Lisp. Но это утверждение другого рода. Язык, который может быть написан сам по себе, принципиально отличается от языка, пригодного для написания некоторого определенного класса приложений. Он открывает новый способ программирования: вы можете не только написать свою программу на языке, но и усовершенствовать язык в соответствии со своей программой. Если вы хотите понять суть программирования на Lisp, эта идея - хорошее место для начала.
Резюме
Проблемы
a. (+ (- 5 1) (+ 3 7)) b. (list 1 (+ 2 3)) c. (if (listp 1) (+ 1 2) (+ 3 4)) d. (list (and (listp 3) t) (+ 1 2))
a. (defun enigma (x) (and (not (null x)) (or (null (car x)) (enigma (cdr x))))) b. (defun mystery (x y) (if (null y) nil (if (eql (car y) x) 0 (let ((z (mystery x (cdr y)))) (and z (+ z 1))))))
a. > (car (x (cdr '(a (b c) d)))) B b. > (x 13 (/ 1 0)) 13 c. > (x #'list 1 nil) (1)
a. принимает целое положительное число и печатает столько точек. b. берет список и возвращает количество раз, когда в нем встречается символ a.
a. (defun summit (lst) (remove nil lst) (apply #'+ lst)) b. (defun summit (lst) (let ((x (car lst))) (if (null x) (summit (cdr lst)) (+ x (summit (cdr lst))))))
Примечания
[1] Имена car и cdr происходят от внутреннего представления списков в первой реализации Lisp: car означало "содержимое адресной части регистра", а cdr - "содержимое декрементной части регистра".
[2] Читатели, у которых возникли проблемы с концепцией рекурсии, могут проконсультироваться с одним из следующих авторов:
Touretzky, David S. Common Lisp: A Gentle Introduction to Symbolic Computation. Benjamin/Cummings, Redwood City (CA), 1990, глава 8.
Фридман, Дэниел П. и Матиас Феллейзен. Маленький лиспер. MIT Press, Cambridge, 1987.
[3] В Ansi Common Lisp также есть макрос лямбда, который позволяет писать (лямбда (x) x) для #'(лямбда (x) x). Поскольку использование этого макроса нарушает симметрию между лямбда-выражениями и символическими именами функций (где все равно приходится использовать sharp-quote), то в лучшем случае это дает некое подобие элегантности.
[4] Gabriel, Richard P. Lisp: Хорошие новости, плохие новости, как выиграть по-крупному. AI Expert, июнь 1991, с. 34.
-------------------------------------------------------------------
Доступно на: http://www.amazon.com/exec/obidos/ASIN/0133708756