- •Оглавление
- •Предисловие
- •Предисловие к русскому изданию
- •Глава 1. Введение
- •1.1. Новые инструменты
- •1.2. Новые приемы
- •1.3. Новый подход
- •Глава 2. Добро пожаловать в Лисп
- •2.1. Форма
- •2.2. Вычисление
- •2.3. Данные
- •2.4. Операции со списками
- •2.5. Истинность
- •2.6. Функции
- •2.7. Рекурсия
- •2.8. Чтение Лиспа
- •2.9. Ввод и вывод
- •2.10. Переменные
- •2.11. Присваивание
- •2.12. Функциональное программирование
- •2.13. Итерация
- •2.14. Функции как объекты
- •2.15. Типы
- •2.16. Заглядывая вперед
- •Итоги главы
- •Упражнения
- •Глава 3. Списки
- •3.1. Ячейки
- •3.2. Равенство
- •3.3. Почему в Лиспе нет указателей
- •3.4. Построение списков
- •3.5. Пример: сжатие
- •3.6. Доступ
- •3.7. Отображающие функции
- •3.8. Деревья
- •3.9. Чтобы понять рекурсию, нужно понять рекурсию
- •3.10. Множества
- •3.11. Последовательности
- •3.12. Стопка
- •3.13. Точечные пары
- •3.14. Ассоциативные списки
- •3.15. Пример: поиск кратчайшего пути
- •3.16. Мусор
- •Итоги главы
- •Упражнения
- •Глава 4. Специализированные структуры данных
- •4.1. Массивы
- •4.2. Пример: бинарный поиск
- •4.3. Строки и знаки
- •4.4. Последовательности
- •4.5. Пример: разбор дат
- •4.6. Структуры
- •4.7. Пример: двоичные деревья поиска
- •4.8. Хеш-таблицы
- •Итоги главы
- •Упражнения
- •Глава 5. Управление
- •5.1. Блоки
- •5.2. Контекст
- •5.3. Условные выражения
- •5.4. Итерации
- •5.5. Множественные значения
- •5.6. Прерывание выполнения
- •5.7. Пример: арифметика над датами
- •Итоги главы
- •Упражнения
- •Глава 6. Функции
- •6.1. Глобальные функции
- •6.2. Локальные функции
- •6.3. Списки параметров
- •6.4. Пример: утилиты
- •6.5. Замыкания
- •6.6. Пример: строители функций
- •6.7. Динамический диапазон
- •6.8. Компиляция
- •6.9. Использование рекурсии
- •Итоги главы
- •Упражнения
- •Глава 7. Ввод и вывод
- •7.1. Потоки
- •7.2. Ввод
- •7.3. Вывод
- •7.4. Пример: замена строк
- •7.5. Макрознаки
- •Итоги главы
- •Упражнения
- •Глава 8. Символы
- •8.1. Имена символов
- •8.2. Списки свойств
- •8.3. А символы-то не маленькие
- •8.4. Создание символов
- •8.5. Использование нескольких пакетов
- •8.6. Ключевые слова
- •8.7. Символы и переменные
- •8.8. Пример: генерация случайного текста
- •Итоги главы
- •Упражнения
- •Глава 9. Числа
- •9.1. Типы
- •9.2. Преобразование и извлечение
- •9.3. Сравнение
- •9.4. Арифметика
- •9.5. Возведение в степень
- •9.6. Тригонометрические функции
- •9.7. Представление
- •9.8. Пример: трассировка лучей
- •Итоги главы
- •Упражнения
- •Глава 10. Макросы
- •10.1. Eval
- •10.2. Макросы
- •10.3. Обратная кавычка
- •10.4. Пример: быстрая сортировка
- •10.5. Проектирование макросов
- •10.6. Обобщенные ссылки
- •10.7. Пример: макросы-утилиты
- •10.8. На Лиспе
- •Итоги главы
- •Упражнения
- •Глава 11. CLOS
- •11.1. Объектно-ориентированное программирование
- •11.2. Классы и экземпляры
- •11.3. Свойства слотов
- •11.4. Суперклассы
- •11.5. Предшествование
- •11.6. Обобщенные функции
- •11.7. Вспомогательные методы
- •11.8. Комбинация методов
- •11.9. Инкапсуляция
- •11.10. Две модели
- •Итоги главы
- •Упражнения
- •Глава 12. Структура
- •12.1. Разделяемая структура
- •12.2. Модификация
- •12.3. Пример: очереди
- •12.4. Деструктивные функции
- •12.5. Пример: двоичные деревья поиска
- •12.6. Пример: двусвязные списки
- •12.7. Циклическая структура
- •12.8. Неизменяемая структура
- •Итоги главы
- •Упражнения
- •Глава 13. Скорость
- •13.1. Правило бутылочного горлышка
- •13.2. Компиляция
- •13.3. Декларации типов
- •13.4. Обходимся без мусора
- •13.5. Пример: заранее выделенные наборы
- •13.6. Быстрые операторы
- •13.7. Две фазы разработки
- •Итоги главы
- •Упражнения
- •Глава 14. Более сложные вопросы
- •14.1. Спецификаторы типов
- •14.2. Бинарные потоки
- •14.3. Макросы чтения
- •14.4. Пакеты
- •14.5. Loop
- •14.6. Особые условия
- •Глава 15. Пример: логический вывод
- •15.1. Цель
- •15.2. Сопоставление
- •15.3. Отвечая на запросы
- •15.4. Анализ
- •Глава 16. Пример: генерация HTML
- •16.1. HTML
- •16.2. Утилиты HTML
- •16.3. Утилита для итерации
- •16.4. Генерация страниц
- •Глава 17. Пример: объекты
- •17.1. Наследование
- •17.2. Множественное наследование
- •17.3. Определение объектов
- •17.4. Функциональный синтаксис
- •17.5. Определение методов
- •17.6. Экземпляры
- •17.7. Новая реализация
- •17.8. Анализ
- •Комментарии
- •Алфавитный указатель
6.4. Пример: утилиты |
115 |
Ключевые слова и связанные с ними значения могут собираться с помо щью &rest и в таком виде передаваться другим функциям, ожидающим их. Например, мы могли бы определить adjoin следующим образом:
(defun our-adjoin (obj lst &rest args) (if (apply #’member obj lst args)
lst
(cons obj lst)))
Так как adjoin принимает те же параметры по ключу, что и member, дос таточно просто собрать их в список и передать member.
В разделе 5.2 был представлен макрос destructing-bind. В общем случае каждое поддерево шаблона, заданного первым аргументом, может быть устроено так же комплексно, как и список аргументов функции:
> (destructing-bind ((&key w x) &rest y) ’((:w 3) a) (list w x y))
(3 NIL (A))
6.4. Пример: утилиты
В разделе 2.6 упоминалось, что Лисп состоит по большей части из та ких же функций, как те, что вы можете определить самостоятельно. Эта особенность крайне полезна, потому что такой язык программиро вания не только не требует подгонки задачи под себя, но и сам может быть подстроен под каждую задачу. Если вы захотите видеть в Common Lisp какую-либо конкретную функцию, вы можете написать ее само стоятельно, и она станет такой же частью языка, как + или eql.
Опытные Лисп-разработчики создают программы как снизу-вверх, так и сверху-вниз. Подстраивая конкретную задачу под язык, они в то же время модифицируют язык, делая его удобнее для этой задачи. Таким образом, рано или поздно язык и задача окажутся максимально подо- гнанными друг под друга.
Функции, создаваемые для расширения возможностей Лиспа, называ ют утилитами. Создавая Лисп-программы, вы обнаружите, что неко торые функции, созданные для одной программы, могут пригодиться и для другой.
Профессиональные разработчики используют эту довольно привлека тельную идею для создания повторно используемых программ. Этот подход некоторым образом связан с объектно-ориентированным про граммированием, однако программа вовсе не обязана быть объектно- ориентированной, чтобы быть пригодной к повторному использованию. Подтверждение тому – сами языки программирования (точнее их ком пиляторы), которые являются, вероятно, наиболее приспособленными к повторному использованию.
Основной секрет в написании таких программ – подход снизу-вверх, и программы вовсе не обязаны быть объектно-ориентированными,
116 |
Глава 6. Функции |
чтобы писаться снизу-вверх. На самом деле, функциональный стиль да же лучше адаптирован для создания повторно используемых программ. Посмотрим, например, на sort. Имея в распоряжении эту функцию, вам вряд ли потребуется писать свои сортирующие процедуры на Лиспе, по тому что sort эффективна и может быть приспособлена к самым разным задачам. Именно это и называется повторным использованием.
Вы можете применять этот подход в своих программах, создавая ути литы. На рис. 6.1 представлена небольшая выборка полезных утилит. Первые две, single? и append1, приведены с целью показать, что даже очень короткие утилиты могут быть полезными. Первая из них возвра щает истину, когда ее аргумент – список из одного элемента:
> (single? ’(a)) T
(defun single? (lst)
(and (consp lst) (null (cdr lst))))
(defun append1 (lst obj) (append lst (list obj)))
(defun map-int (fn n) (let ((acc nil))
(dotimes (i n)
(push (funcall fn i) acc)) (nreverse acc)))
(defun filter (fn lst) (let ((acc nil))
(dolist (x lst)
(let ((val (funcall fn x))) (if val (push val acc))))
(nreverse acc)))
(defun most (fn lst) (if (null lst)
(values nil nil)
(let* ((wins (car lst))
(max (funcall fn wins))) (dolist (obj (cdr lst))
(let ((score (funcall fn obj))) (when (> score max)
(setf wins obj
max score)))) (values wins max))))
Рис. 6.1. Утилиты
6.4. Пример: утилиты |
117 |
Вторая утилита напоминает cons, однако, в отличие от cons, она добав ляет элемент в конец списка, а не в начало:
> (append1 ’(a b c) ’d) (A B C D)
Следующая утилита, map-int, принимает функцию и целое число n, воз вращая список, состоящий из значений этой функции для всех целых чисел от 0 до n–1.
Такая функция может пригодиться при тестировании кода. (Одно из преимуществ Лиспа заключается в интерактивности разработки, бла годаря которой вы можете создавать одни функции для тестирования других.) Если нам вдруг понадобится список чисел от 0 до 9, мы сможем написать:
>(map-int #’identity 10) (0 1 2 3 4 5 6 7 8 9)
Аесли мы хотим получить список из десяти случайных чисел между 0 и 99 (включительно), просто пропустим параметр лямбда-выражения и напишем:
>(map-int #’(lambda (x) (random 100))
10)
(85 40 73 64 28 21 67 5 32)
На примере map-int показана распространенная Лисп-идиома для по строения списков. В ней создается аккумулятор acc, который исходно содержит nil, и в него последовательно добавляются элементы с помо щью push. По завершении возвращается перевернутый список acc.1
Эту же идиому мы видим и в filter. Функция filter принимает функ цию и список и возвращает список результатов применения функции к элементам исходного списка, причем возвращаемый список состоит только из элементов, отличающихся от nil:
> (filter #’(lambda (x)
(and (evenp x) (+ x 10))) ’(1 2 3 4 5 6 7))
(12 14 16)
Функцию filter можно также рассматривать как обобщение remove-if.
Последняя функция на рис. 6.1, most, возвращает элемент списка, имею щий наивысший рейтинг с точки зрения заданной рейтинговой функ ции. Помимо этого элемента она также возвращает соответствующее ему значение.
> (most #’length ’((a b) (a b c) (a))) (A B C)
3
1В данном контексте nreverse (стр. 229) делает то же, что и reverse, однако она более эффективна.
118 |
Глава 6. Функции |
Если таких элементов несколько, most возвращает первый из них.
Обратите внимание, что последние три функции на рис. 6.1 принимают другие функции в качестве аргументов. Для Лиспа это явление совер шенно естественно и является одной из причин его приспособленности к программированию снизу-вверх.° Хорошая утилита должна быть как можно более обобщенной, а абстрагировать общее легче, когда можно передать специфическую часть в качестве аргумента-функции.
Функции, приведенные в этом разделе, являются утилитами общего на значения и могут быть использованы в самых разных программах. Одна ко вы можете написать утилиты для более конкретных задач. Более то го, далее будет показано, как создавать поверх Лиспа специализиро ванные языки для конкретных прикладных областей. Это еще один хороший подход к получению кода для повторного использования.
6.5. Замыкания
Функция, как и любой другой объект, может возвращаться как резуль тат выражения. Ниже приведен пример функции, которая возвращает функцию, применимую для сочетания объектов того же типа, что и ее аргумент:
(defun combiner (x)
(typecase |
x |
(number |
#’+) |
(list |
#’append) |
(t |
#’list))) |
С ее помощью мы сможем создать комбинирующую функцию общего вида:
(defun combine (&rest args) (apply (combiner (car args))
args))
Она принимает аргументы любого типа и объединяет их в соответствии с типом. (Для упрощения рассматривается лишь тот случай, когда все аргументы имеют один тип.)
>(combine 2 3)
5
>(combine ’(a b) ’(c d)) (A B C D)
Вразделе 2.10 объяснялось, что лексические переменные действитель ны только внутри контекста, в котором они были определены. Вместе с этим ограничением мы получаем обещание, что они будут по-прежнему действительны до тех пор, пока этот контекст где-нибудь используется.
Если функция была определена в зоне действия лексической перемен ной, то она сможет продолжать ссылаться на эту переменную, даже бу дучи возвращенной как значение, а затем использованной вне контекста
6.5. Замыкания |
119 |
этой переменной. Приведем функцию, добавляющую 3 к своему аргу менту:
> (setf fn (let ((i 3))
#’(lambda (x) (+ x i)))) #<Interpreted-Function C0A51E>
> (funcall fn 2) 5
Если функция ссылается на определенную вне нее переменную, то та кая переменная называется свободной. Функцию, ссылающуюся на сво бодную лексическую переменную, принято называть замыканием (clo sure)1. Свободная переменная будет существовать до тех пор, пока дос тупна использующая ее функция.
Замыкание – это комбинация функции и окружения. Замыкания созда ются неявно, когда функция ссылается на что-либо из лексического ок ружения, в котором она была определена. Это происходит без каких-либо внешних проявлений, как, например, в функции, приведенной ниже:
(defun add-to-list (num lst) (mapcar #’(lambda (x)
(+ x num)) lst))
Функция принимает число и список и возвращает новый список, в ко тором к каждому элементу исходного списка добавляется заданное чис ло. Переменная num в лямбда-выражении является свободной, значит, функции mapcar передается замыкание.
Более очевидным примером является функция, возвращающая само за мыкание. Следующая функция возвращает замыкание, выполняющее сложение с заданным числом:
(defun make-adder (n) #’(lambda (x)
(+ x n)))
Принимается число n и возвращается функция, которая складывает число n с ее аргументом:
>(setf add3 (make-adder 3)) #<Interpreted-Function C0EBF6>
>(funcall add3 2)
5
>(setf add27 (make-adder 27)) #<Interpreted-Function C0EE4E>
>(funcall add27 2)
29
1Название «замыкание» взято из ранних диалектов Лиспа. Оно происходит из метода, с помощью которого замыкания реализовывались в динамиче ском окружении.