High tech - Paul Graham / Пол Грэм - ANSI Common Lisp [2012, PDF, RUS]

Оглавление
Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .13
Предисловие к русскому изданию . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Глава
1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .19
1.1. Новые инструменты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .19
1.2. Новые приемы. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .21
1.3. Новый подход . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .22
Глава
2. Добро пожаловать в Лисп . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25
2.1. Форма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25
2.2. Вычисление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .27
2.3. Данные . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .28
2.4. Операции со списками . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .30
2.5. Истинность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .30
2.6. Функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .32
2.7. Рекурсия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .33
2.8. Чтение Лиспа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .34
2.9. Ввод и вывод . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .35
2.10. Переменные . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .37
2.11. Присваивание . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .38
2.12. Функциональное программирование . . . . . . . . . . . . . . . . . . . . . . . .39
2.13. Итерация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .40
2.14. Функции как объекты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .42
2.15. Типы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .44
2.16. Заглядывая вперед . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .44
Итоги главы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .45
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .46
Глава
3. Списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .48
3.1. Ячейки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .48
3.2. Равенство . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .50
3.3. Почему в Лиспе нет указателей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .51
3.4. Построение списков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .53
3.5. Пример: сжатие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .53
3.6. Доступ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .55
3.7. Отображающие функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .56
Оглавление
6 Оглавление
3.8. Деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.9. Чтобы понять рекурсию, нужно понять рекурсию . . . . . . . . . . . . . .58
3.10. Множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .60
3.11. Последовательности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .61
3.12. Стопка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .63
3.13. Точечные пары . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .65
3.14. Ассоциативные списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .66
3.15. Пример: поиск кратчайшего пути . . . . . . . . . . . . . . . . . . . . . . . . . . .67
3.16. Мусор . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .69
Итоги главы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .70
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .71
Глава
4. Специализированные структуры данных . . . . . . . . . . . . . . . . . . . . .73
4.1. Массивы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .73
4.2. Пример: бинарный поиск . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .75
4.3. Строки и знаки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .77
4.4. Последовательности. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .78
4.5. Пример: разбор дат. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .81
4.6. Структуры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .83
4.7. Пример: двоичные деревья поиска . . . . . . . . . . . . . . . . . . . . . . . . . . .85
4.8. Хеш-таблицы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .90
Итоги главы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .93
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .94
Глава
5. Управление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .95
5.1. Блоки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .95
5.2. Контекст . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .97
5.3. Условные выражения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .99
5.4. Итерации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
5.5. Множественные значения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.6. Прерывание выполнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
5.7. Пример: арифметика над датами . . . . . . . . . . . . . . . . . . . . . . . . . . . .106
Итоги главы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
Глава
6. Функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
6.1. Глобальные функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
6.2. Локальные функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
6.3. Списки параметров . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
6.4. Пример: утилиты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
6.5. Замыкания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
6.6. Пример: строители функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .120
6.7. Динамический диапазон . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .123
6.8. Компиляция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
6.9. Использование рекурсии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
Итоги главы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .128
Оглавление 7
Глава
7. Ввод и вывод . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
7.1. Потоки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
7.2. Ввод . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
7.3. Вывод . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
7.4. Пример: замена строк . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
7.5. Макрознаки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
Итоги главы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
Глава
8. Символы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
8.1. Имена символов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
8.2. Списки свойств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
8.3. А символы-то не маленькие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
8.4. Создание символов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
8.5. Использование нескольких пакетов . . . . . . . . . . . . . . . . . . . . . . . . . 147
8.6. Ключевые слова . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
8.7. Символы и переменные . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
8.8. Пример: генерация случайного текста . . . . . . . . . . . . . . . . . . . . . . . 149
Итоги главы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
Глава
9. Числа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
9.1. Типы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
9.2. Преобразование и извлечение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
9.3. Сравнение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
9.4. Арифметика . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
9.5. Возведение в степень . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
9.6. Тригонометрические функции. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
9.7. Представление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
9.8. Пример: трассировка лучей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
Итоги главы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
Глава
10. Макросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
10.1. Eval . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
10.2. Макросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
10.3. Обратная кавычка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
10.4. Пример: быстрая сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
10.5. Проектирование макросов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
10.6. Обобщенные ссылки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
10.7. Пример: макросы-утилиты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
10.8. На Лиспе . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
Итоги главы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
8 Оглавление
Глава
11. CLOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
11.1. Объектно-ориентированное программирование . . . . . . . . . . . . . .185
11.2. Классы и экземпляры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
11.3. Свойства слотов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
11.4. Суперклассы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
11.5. Предшествование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .190
11.6. Обобщенные функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
11.7. Вспомогательные методы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
11.8. Комбинация методов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
11.9. Инкапсуляция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
11.10. Две модели . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
Итоги главы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .200
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
Глава
12. Структура . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .202
12.1. Разделяемая структура . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .202
12.2. Модификация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .205
12.3. Пример: очереди . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .206
12.4. Деструктивные функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .208
12.5. Пример: двоичные деревья поиска . . . . . . . . . . . . . . . . . . . . . . . . .209
12.6. Пример: двусвязные списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
12.7. Циклическая структура . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
12.8. Неизменяемая структура . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
Итоги главы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
Глава
13. Скорость . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .220
13.1. Правило бутылочного горлышка . . . . . . . . . . . . . . . . . . . . . . . . . . .220
13.2. Компиляция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
13.3. Декларации типов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .224
13.4. Обходимся без мусора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .229
13.5. Пример: заранее выделенные наборы . . . . . . . . . . . . . . . . . . . . . . .232
13.6. Быстрые операторы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .234
13.7. Две фазы разработки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .236
Итоги главы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .238
Глава
14. Более сложные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .239
14.1. Спецификаторы типов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .239
14.2. Бинарные потоки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
14.3. Макросы чтения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
14.4. Пакеты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .243
14.5. Loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .246
14.6. Особые условия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .250
Оглавление 9
Глава
15. Пример: логический вывод . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .253
15.1. Цель . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
15.2. Сопоставление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .254
15.3. Отвечая на запросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .256
15.4. Анализ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
Глава
16. Пример: генерация HTML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .263
16.1. HTML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .263
16.2. Утилиты HTML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .265
16.3. Утилита для итерации. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .268
16.4. Генерация страниц. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .269
Глава
17. Пример: объекты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
17.1. Наследование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
17.2. Множественное наследование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276
17.3. Определение объектов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
17.4. Функциональный синтаксис . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
17.5. Определение методов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .280
17.6. Экземпляры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
17.7. Новая реализация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .282
17.8. Анализ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .288
Приложение
A. Отладка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .290
Приложение
B. Лисп на Лиспе . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .299
Приложение
C. Изменения в Common Lisp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .307
Приложение
D. Справочник по языку. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
Комментарии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 421
Алфавитный указатель . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .436