- •Оглавление
- •Предисловие
- •Предисловие к русскому изданию
- •Глава 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. Анализ
- •Комментарии
- •Алфавитный указатель
3.8. Деревья |
57 |
Из последнего примера видно, как mapcar обрабатывает случай со спи сками разной длины. Вычисление обрывается по окончании самого ко роткого списка.
Похожим образом действует maplist, однако применяет функцию после довательно не к car, а к cdr списка, начиная со всего списка целиком.
> (maplist #’(lambda (x) x) ’(a b c))
((A B C) (B C) (C))
Среди других отображающих функций можно отметить mapc, которая рассматривается на стр. 102, а также mapcan, с которой вы познакоми тесь на стр. 209.
3.8. Деревья
Cons-ячейки также можно рассматривать как двоичные деревья: car соот ветствует правому поддереву, а cdr – левому. К примеру, список (a (b c) d) представлен в виде дерева на рис. 3.8. (Если повернуть его на 45° против часовой стрелки, он будет напоминать рис. 3.3.)
В Common Lisp есть несколько встроенных функций для работы с де ревьями. Например, copy-tree принимает дерево и возвращает его ко пию. Определим аналогичную функцию самостоятельно:
(defun our-copy-tree (tr) (if (atom tr)
tr
(cons (our-copy-tree (car tr)) (our-copy-tree (cdr tr)))))
Сравните ее с функцией copy-list (стр. 53). В то время как copy-list копи рует только cdr списка, copy-tree копирует еще и car.
a
nil
b |
|
|
nil |
d |
|
|
|||
|
|
|
|
|
|
|
|
|
|
c
Рис. 3.8. Бинарное дерево
58 |
Глава 3. Списки |
Бинарные деревья без внутренних узлов вряд ли окажутся полезными. Common Lisp включает в себя функции для операций с деревьями не потому, что без деревьев нельзя обойтись, а потому что эти функции очень полезны для работы со списками и подсписками. Например, пред положим, что у нас есть список:
(and (integerp x) (zerop (mod x 2)))
И мы хотим заменить x на y. Заменить элементы в последовательности можно с помощью substitute:
> (substitute ’y ’x ’(and (integerp x) (zerop (mod x 2)))) (AND (INTEGERP X) (ZEROP (MOD X 2)))
Как видите, использование substitute не дало результатов, так как спи сок содержит три элемента, ни один из которых не является x. Здесь нам понадобится функция subst, работающая с деревьями:
> (subst ’y ’x ’(and (integerp x) (zerop (mod x 2)))) (AND (INTEGERP Y) (ZEROP (MOD Y 2)))
Наше определение subst будет очень похоже на copy-tree:
(defun our-subst (new old tree) (if (eql tree old)
new
(if (atom tree) tree
(cons (our-subst new old (car tree)) (our-subst new old (cdr tree))))))
Любые функции, оперирующие с деревьями, будут выглядеть похожим образом, рекурсивно вызывая себя с car и cdr. Такая рекурсия называ ется двойной.
3.9. Чтобы понять рекурсию, нужно понять рекурсию
Чтобы понять, как работает рекурсия, студентам часто предлагают трас сировать последовательность вызовов на бумаге. (Такая последователь ность, например, изображена на стр. 291.) Иногда выполнение такого за дания может ввести в заблуждение, так как программисту вовсе не обя зательно четко представлять себе последовательность вызовов и возвра щаемых результатов.
Если представлять рекурсию именно в таком виде, то ее применение вызовет лишь раздражение и вряд ли принесет пользу. Преимущества рекурсии открываются при более абстрактном взгляде на нее.
Чтобы убедиться, что рекурсия делает то, что мы думаем, достаточно спросить, покрывает ли она все варианты. Посмотрим, к примеру, на рекурсивную функцию для определения длины списка:
3.9. Чтобы понять рекурсию, нужно понять рекурсию |
59 |
(defun len (lst) (if (null lst)
0
(+ (len (cdr lst)) 1)))
Можно убедиться в корректности функции, проверив две вещи1:
1.Она работает со списками нулевой длины, возвращая 0.
2.Если она работает со списками, длина которых равна n, то будет справедлива также и для списков длиной n+1.
Если оба случая верны, то функция ведет себя корректно на всех воз можных списках.
Первое утверждение совершенно очевидно: если lst – это nil, то функ ция тут же возвращает 0. Теперь предположим, что она работает со спи ском длиной n. Согласно определению, для списка длиной n+1 она вернет число, на 1 большее длины cdr списка, то есть n+1.
Это все, что нам нужно знать. Представлять всю последовательность вызовов вовсе не обязательно, так же как необязательно искать парные скобки в определениях функций.
Для более сложных функций, например двойной рекурсии, случаев бу дет больше, но процедура останется прежней. К примеру, для функции our-copy-tree (стр. 41) потребуется рассмотреть три случая: атомы, про стые ячейки, деревья, содержащие n+1 ячеек.
Первый случай носит название базового (base case). Если рекурсивная функция ведет себя не так, как ожидалось, причина часто заключается в некорректной проверке базового случая или же в отсутствии провер ки, как в примере с функцией member:
(defun our-member |
(obj lst) |
; wrong2 |
(if (eql (car lst) obj) |
|
|
lst |
|
|
(our-member |
obj (cdr lst)))) |
|
В этом определении необходима проверка списка на пустоту, иначе в случае отсутствия искомого элемента в списке рекурсивный вызов бу дет выполняться бесконечно. В приложении А эта проблема рассматри вается более детально.
Способность оценить корректность рекурсивной функции – лишь пер вая часть понимания рекурсии. Вторая часть – необходимо научиться писать собственные рекурсивные функции, которые делают то, что вам требуется. Этому посвящен раздел 6.9.
1Такой метод доказательства носит название математической индукции. –
Прим. перев.
2Здесь ; wrong – это комментарий. Комментариями в Лиспе считается все от символа «;» до конца текущей строки.
60 |
Глава 3. Списки |
3.10. Множества
Списки – хороший способ представления небольших множеств. Чтобы проверить, принадлежит ли элемент множеству, задаваемому списком, можно воспользоваться функцией member:
> (member ’b ’(a b c)) (B C)
Если искомый элемент найден, member возвращает не t, а часть списка, начинающегося с найденного элемента. Конечно, непустой список логи чески соответствует истине, но такое поведение member позволяет полу чить больше информации. По умолчанию member сравнивает аргументы с помощью eql. Предикат сравнения можно задать вручную с помощью аргумента по ключу. Аргументы по ключу (keyword) – довольно распро страненный в Common Lisp способ передачи аргументов. Такие аргу менты передаются не в соответствии с их положением в списке парамет ров, а с помощью особых меток, называемых ключевыми словами. Клю чевым словом считается любой символ, начинающийся с двоеточия.
Одним из аргументов по ключу, принимаемых member, является :test. Он позволяет использовать в качестве предиката сравнения вместо eql произвольную функцию, например equal:
> (member ’(a) ’((a) (z)) :test #’equal) ((A) (Z))
Аргументы по ключу не являются обязательными и следуют последни ми в вызове функции, причем их порядок не имеет значения.
Другой аргумент по ключу функции member – :key. С его помощью можно задать функцию, применяемую к каждому элементу перед сравнением:
> (member ’a ’((a b) (c d)) :key #’car) ((A B) (C D))
В этом примере мы искали элемент, car которого равен a.
При желании использовать оба аргумента по ключу можно задавать их в произвольном порядке:
>(member 2 ’((1) (2)) :key #’car :test #’equal) ((2))
>(member 2 ’((1) (2)) :test #’equal :key #’car) ((2))
Спомощью member-if можно найти элемент, удовлетворяющий произволь ному предикату, например oddp (истинному, когда аргумент нечетен):
>(member-if #’oddp ’(2 3 4))
(3 4)
Наша собственная функция member-if могла бы выглядеть следующим образом: