Текущий раздел: Книги / ANSI Common Lisp

ANSI Common Lisp

ANSI Common LISP

Автор:	Пол Грэм
Страниц:	448
Масса:
Обложка:	мягкая
Издана:	Ноябрь2012
Купить

Оглавление

Предисловие

Предисловие к русскому изданию

Глава 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.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. Анализ

Приложение А. Отладка

Приложение В. Лисп на Лиспе

Приложение С. Изменения в Common Lisp

Приложение D. Справочник по языку

Заметки (литература)

Алфавитный указатель

Предисловие к русскому изданию

Книга, перевод которой вы держите в руках, была издана в 1996 году, а написана и того раньше. К моменту подготовки перевода прошло 15 лет. Для такой стремительно развивающейся отрасли, как программирование, это огромный срок, за который изменили облик не только парадигмы и языки программирования, но и сама вычислительная техника.

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

Автор не раз упоминает о том, что Лисп, несмотря на его долгую историю, не теряет актуальности. Теперь, когда с момента издания оригинала книги прошло 15 лет, а с момента создания языка Лисп более полувека, мы отчетливо видим подтверждение слов автора, наблюдая постоянный рост интереса к языку.

Тем не менее некоторые моменты в книге являются слегка устаревшими и требуют дополнительных комментариев.

В числе уникальных особенностей Лиспа Грэм выделяет интерактивность, автоматическое управление памятью, динамическую типизацию и замыкания. На момент написания книги Лисп конкурировал с такими языками, как С, C++, Паскаль, Фортран (на протяжении книги автор сравнивает Лисп именно с ними). Эти языки «старой закалки» действительно представляют полную противоположность Лиспу. На настоящий момент разработано множество языков, в которых в той или иной степени заимствованы преимущества Лиспа. Таким, например, является Perl, который вытесняется более продвинутым языком Python, а последний, несмотря на популярность, сам испытывает конкуренцию со стороны языка Ruby, известного как «Лисп с человеческим синтаксисом». Такие языки благодаря гибкости быстро находят свою нишу, оставаясь при этом средствами общего назначения. Так, Perl прочно занял нишу скриптового языка в Unix-подобных системах. Однако механизм макросов, лежащий в основе Лиспа, пока не был заимствован ни одним из языков, так как прочно связан с его синтаксисом. Кроме того, Лисп выгодно отличается от своих «последователей». Согласитесь, искусственное добавление возможностей в язык с уже существующей структурой и идеологией существенно отличается от случая, когда язык изначально разрабатывался с учетом данных возможностей.

Время коснулось также и ряда идей и моделей, упомянутых в данной книге. Несколько странными могут показаться восторженные упоминания об объектно-ориентированном программировании. Прошло немало времени, и сегодня ООП уже больше не вызывает подобный восторг.

Многое изменилось и в мире реализаций Common Lisp. Автор сознательно не упоминает названия реализаций, так как их жизненный срок не определен. Многих реализаций языка уже нет в живых, но на их место пришли новые. Необходимо отметить, что сейчас имеется ряд блестящих реализаций Common Lisp, как коммерческих, так и свободных. Стандарт языка дает разработчикам довольно много свободы действий, и выпускаемые ими реализации как внешне, так и внутренне могут сильно отличаться друг от друга. Детали реализаций вас могут не волновать, а вот различия в их поведении могут смущать новичков. Когда речь заходит о взаимодействии с пользователем (например, о работе в отладчике), автор использует некий упрощенный унифицированный интерфейс, который он называет «гипотетической» реализацией. На деле, вам придется поэкспериментировать с выбранной реализацией, чтобы научиться эффективно ее использовать. Кроме того, сейчас имеется отличная среда разработки Slime[1], помимо прочего скрывающая разницу в поведении между реализациями.

Всеволод Демкин

Переводчик, Иван Хохлов, выражает благодарность Ивану Струкову, Сергею Катревичу и Ивану Чернецкому за предоставление ценных замечаний по переводу отдельных глав книги.

Глава 1. Введение

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

Отчасти его отличает изначально заложенная возможность развиваться. Лисп позволяет программисту определять новые операторы, и если появятся новые абстракции, которые приобретут популярность (например, объектно-ориентированное программирование), их всегда можно будет реализовать в Лиспе. Изменяясь как ДНК, такой язык никогда не выйдет из моды..

1.1. Новые инструменты

Зачем изучать Лисп? Потому что он позволяет делать то, чего не могут другие языки. Если вы захотите написать функцию, складывающую все числа, меньшие n, она будет очень похожа на аналогичную функцию в С:

; Lisp /* C */

(defun sum (n) int sum(int n){

(let ((s 0)) int i , s = 0;

(dotimes (i n s) for(i = 0; i < n; i++)

(incf s i)))) s += i;

return(s);

}

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

; Lisp

(defun addn (n)

#'(lambda (x)

(+ x n)))

Как функция addn будет выглядеть на С? Ее просто невозможно написать.

Вы, вероятно, спросите, зачем это может понадобиться? Языки программирования учат вас не хотеть того, что они не могут осуществить. Раз программисту приходится думать на том языке, который он использует, ему сложно представить то, чего он не может описать. Когда я впервые занялся программированием на Бейсике, я не огорчался отсутствием рекурсии, так как попросту не знал, что такая вещь имеет место. Я думал на Бейсике и мог представить себе только итеративные алгоритмы, так с чего бы мне было вообще задумываться о рекурсии?

Если вам не нужны лексические замыкания (а именно они были продемонстрированы в предыдущем примере), просто примите пока что на веру, что Лисп-программисты используют их постоянно. Сложно найти программу на Лиспе, написанную без использования замыканий. В разделе 6.7 вы научитесь пользоваться ими.

Замыкания - не единственные абстракции, которых нет в других языках. Другой, возможно даже более важной, особенностью Лиспа является то, что программы, написанные на нем, представляются в виде его же структур данных. Это означает, что вы можете писать программы, которые пишут программы. Действительно ли люди пользуются этим? Да, это и есть макросы, и опытные программисты используют их на каждом шагу. Вы узнаете, как создавать свои макросы, в главе 10.

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

Главы 2-13 поэтапно вводят все понятия, необходимые для понимания кода главы 17. Благодаря вашим стараниям вы будете ощущать программирование на C++ таким же удушающим, каким опытный программист C++ в свою очередь ощущает Бейсик. Сомнительная, на первый взгляд, награда. Но, быть может, вас вдохновит осознание природы этого дискомфорта. Бейсик неудобен по сравнению с C++, потому что опытный программист C++ знает приемы, которые невозможно осуществить в Бейсике. Точно так же изучение Лиспа даст вам больше, нежели добавление еще одного языка в копилку ваших знаний. Вы научитесь размышлять о программах по-новому, более эффективно.

1.2. Новые приемы

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

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

Практически любая программа будет выигрывать, если используемый язык заточен под нее, и чем сложнее программа, тем большую значимость имеет подход «снизу-вверх». В такой программе может быть несколько слоев, каждый из которых служит чем-то вроде языка для описания вышележащего слоя. Одной из первых программ, написанных таким образом, был TeX. Вы имеете возможность писать программы снизу-вверх на любом языке, но на Лиспе это делать проще всего.

Написанные снизу-вверх программы легко расширяемы. Поскольку идея расширяемости лежит в основе Лиспа, это идеальный язык для написания расширяемых программ. В качестве примера приведу три программы, написанные в 80-х годах и использовавшие возможность расширения Лиспа: GNU Emacs, Autocad и Interleaf.

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

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

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

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

1.3. Новый подход

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

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

Руководитель проекта OS/360 Фредерик Брукс был хорошо знаком с традиционным подходом, а также с его результатами:

Любой пользователь OS/360 вскоре начинал понимать, насколько лучше могла бы быть система. Более того, продукт не успевал за прогрессом, использовал памяти больше запланированного, стоимость его в несколько раз превосходила ожидаемую, и он не работал стабильно до тех пор, пока не было выпущено несколько релизов.

Так он описывал систему, ставшую тогда одной из наиболее успешных.

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

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

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

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

Такой подход появился не просто так, он действительно приносит результат. Как бы странно это ни звучало, чем меньше планировать разработку, тем стройнее получится программа. Забавно, но такая тенденция наблюдается не только в программировании. В средние века, до изобретения масляных красок, художники пользовались особым материалом - темперой, которая не могла быть перекрашена или осветлена. Стоимость ошибки была настолько велика, что художники боялись экспериментировать. Изобретение масляных красок породило множество течений и стилей в живописи. Масло «позволяет думать дважды». Это дало решающее преимущество в работе со сложными сюжетами, такими как человеческая натура.

Введение в обиход масляных красок не просто облегчило жизнь художникам. Стали доступными новые, прогрессивные идеи. Янсон писал:

Без масла покорение фламандскими мастерами визуальной реальности было бы крайне затруднительным. С технической точки зрения они являются прародителями современной живописи, потому что масло стало базовым инструментом художника с тех пор.

Как материал темпера не менее красива, чем масло, но широта полета фантазии, которую обеспечивают масляные краски, является решающим фактором.

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

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

Приложение A. Отладка

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

Циклы прерывания

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

Внутри цикла прерывания вы по-прежнему можете вычислять выражения так же, как и в toplevel. Находясь внутри этого цикла, вы можете выяснить причину ошибки и даже исправить ее на лету, после чего программа продолжит выполнение. Тем не менее наиболее частое действие, которое вы захотите произвести внутри цикла прерывания, - это выбраться из него. В большинстве ошибок, как правило, виноваты опечатки или мелкие оплошности, так что обычно вы просто прервете выполнение и вернетесь в toplevel. В гипотетической реализации для этого нужно набрать :abort:

> (/ 1 0)

Error: Division by zero.

Options: :abort, :backtrace

>> :abort

Что вы будете вводить в своей реализации, зависит от нее.

Если вы находитесь в цикле прерывания и происходит еще одна ошибка, то вы попадаете в еще один цикл прерывания.[2] Большинство реализаций Лиспа показывает уровень цикла, на котором вы находитесь, с помощью нескольких приглашений или числа перед приглашением:

>> (/ 2 0)

Error: Division by zero.

Options: :abort, :backtrace, :previous

>>>

Теперь глубина вложенности отладчиков равна двум, и мы можем вернуться в предыдущий отладчик или же сразу попасть в toplevel.

Трассировка и обратная трассировка

Если ваша программа делает не то, что вы ожидали, иногда стоит прежде всего выяснить, что именно она делает. Если вы введете (trace foo), то Лисп будет выводить сообщение каждый раз, когда foo вызывается и завершается, показывая при этом переданные ей аргументы или возвращенные ею значения. Вы можете отслеживать таким образом поведение любой заданной пользователем функции.

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

(defun tree1+ (tr)

(cond ((null tr) nil)

((atom tr) (1+ tr))

(t (cons (tree1+ (car tr))

(tree1+ (cdr tr))))))

трасса будет отображать структуру, обход которой происходит:Ё007in

> (trace treel+)

(treel+)

> (treel+ '((1 . 3) 5 . 7))

1 Enter TREE1+ ((1 . 3) 5 . 7)

2 Enter TREE1+ ( 1 . 3 )

3 Enter TREE1+ 1

3 Exit TREE1+ 2

3 Enter TREE1+ 3

3 Exit TREE1+ 4

2 Exit TREE1+ (2 . 4)

2 Enter TREE1+ (5 . 7)

3 Enter TREE1+ 5

3 Exit TREE1+ 6

3 Enter TREE1+ 7

3 Exit TREE1+ 8

2 Exit TREE1+ (6 . 8)

1 Exit TREE1+ ((2 . 4) 6 . 8)

((2 . 4) 6 . 8)

Для отключения трассировки foo введите (untrace foo); для отключения трассировки всех функций введите (untrace).

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

Обратная трасса (backtrace) - это список всех вызовов, находящихся на стеке, который создается из цикла прерывания после того, как произошла ошибка. Если при трассировке мы как бы говорим: «Покажи, что ты делаешь», то при обратной трассировке мы задаем вопрос: «Как мы сюда попали?». Эти две операции дополняют друг друга. Трассировка покажет каждый вызов заданных функций во всем дереве вызовов, а обратная трассировка - вызовы всех функций в выбранной части кода (на пути от toplevel к месту возникновения ошибки).

В типичной реализации мы получим обратную трассу, введя :backtrace в отладчике:

> (tree1+ '((1 . 3) 5 . A))

Error: A is not a valid argument to 1+.

Options: :abort, :backtrace

>> :backtrace

(1+ A)

(TREE1+ A)

(TREE1+ (5 . A))

(TREE1+ ((1 . 3) 5 . A))

С помощью обратной трассировки поймать ошибку иногда довольно легко. Для этого достаточно посмотреть на цепочку вызовов. Еще одним преимуществом функционального программирования (раздел 2.12) является то, что все баги проявятся при обратной трассировке. В полностью функциональном коде все, что могло повлиять на возникновение ошибки, при ее появлении находится на стеке вызовов функции.

Количество информации, содержащееся в обратной трассе, зависит от используемой реализации. Одна реализация может выводить полную историю всех незавершенных вызовов с их аргументами, а другая может не выводить практически ничего. Имейте в виду, что обычно трассировка (и обратная трассировка) более информативна для интерпретируемого кода, нежели для скомпилированного. Это еще одна причина отложить компиляцию вашей программы до тех пор, пока вы не будете полностью уверены, что она работает. Исторически отладку вели в режиме интерпретации и лишь затем компилировали отлаженную версию. Однако взгляды на этот вопрос постепенно меняются: по меньшей мере две реализации Common Lisp вовсе не содержат интерпретатор.

Когда ничего не происходит

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

> (defun blow-stack () (1+ (blow-stack)))

BLOW-STACK

> (blow-stack)

Error: Stack overflow.

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

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

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

В Common Lisp car и cdr возвращают nil, если их аргументом является nil:

> (car nil)

NIL

> (cdr nil)

NIL

Поэтому если мы пропустим базовое условие в определении member,

(defun our-member (obj lst) ; wrong

(if (eql (car lst) obj)

lst

(our-member obj (cdr lst))))

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

(our-member obj nil)

В корректном определении (стр. 33) базовое условие приведет к остановке рекурсии, возвращая nil. В нашем ошибочном случае функция будет покорно искать car и cdr от nil, которые также равны nil, поэтому процесс будет повторяться снова и снова.

Если причина бесконечного процесса неочевидна, как в нашем случае, вам поможет трассировка. Бесконечные циклы бывают двух видов. Вам повезло, если источником бесконечного повторения является структура программы. Например, в случае our-member трассировка тут же покажет, где проблема.

Более сложным случаем являются бесконечные циклы, причина которых - некорректно сформированные структуры данных. Например, попытка обхода циклического списка (стр. 215) приводит к бесконечному циклу. Подобные проблемы трудно обнаружить, так как они проявляют себя не сразу и возникают уже в коде, который не является их непосредственной причиной. Правильным решением является предупреждение подобных проблем (стр. 205): избегайте деструктивных операторов до тех пор, пока не убедитесь в корректности работы программы.

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

> (format t "for example ~A~% 'this)

Здесь мы пропустили закрывающую кавычку в конце строки форматирования. Нажатие на Enter не приведет к чему-либо, так как Лисп думает, что мы продолжаем набирать строку.

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

Переменные без значения/несвязанные переменные

Частой причиной жалоб со стороны Лиспа являются символы без значения или же несвязанные символы. Они могут вызвать несколько различных проблем.

Локальные переменные, подобные устанавливаемым в let или defun, действительны только внутри тела выражения, в котором они были созданы. Попытка сослаться на такие переменные откуда-либо извне приведет к ошибке:

> (progn

(let ((x 10))

(format t "Here x = ~A.~%" x))

(format t "But now it's gone...~%")

Here x = 10.

But now it's gone...

Error: X has no value.

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

Похожая проблема возникает, если мы пытаемся сослаться на функцию как на переменную:

> defun foo (x) (+ x 1))

Error: DEFUN has no value.

Поначалу это может озадачить: как это defun не имеет значения? Просто мы забыли открывающую скобку, и поэтому Лисп воспринимает символ defun (а это все, что он пока что считал) как глобальную переменную.

Иногда программисты забывают инициализировать глобальные переменные. Если вы не передаете второй аргумент defvar, глобальная переменная будет определена, но не инициализирована, и это может быть корнем проблемы.

Неожиданный nil

Ё016inЕсли функции жалуются, что получили nil в качестве аргумента, то это признак того, что на ранних этапах работы в программе что-то пошло не так. Некоторые встроенные операторы возвращают nil при неудачном завершении. Но, поскольку nil - полноценный объект, проблема может обнаружить себя существенно позже, когда какая-нибудь другая часть вашей программы попытается воспользоваться этим якобы возвращаемым значением.

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

(defun month-length (mon)

(case mon

((jan mar may jul aug dec) 31)

((apr jun sept nov) 30)

(feb (if (leap-year) 29 28))))

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

(defun month-weeks (mon) (/ (month-length mon) 7.0))

В таком случае при вызове month-weeks может произойти следующее:

> (month-weeks 'oct)

Error: NIL is not a valid argument to /.

Ни одно из заданных условий в case-выражении не было выполнено, и case вернул nil. Затем month-weeks, которая ожидает число, передает это значение функции /, но та получает nil, что и приводит к ошибке.

В нашем примере источник и место проявления бага находятся рядом. Чем дальше они друг от друга, тем сложнее найти подобные баги. Для предотвращения подобных ситуаций в некоторых диалектах Лиспа прохождение cond и case без выполнения одного из вариантов вызывает ошибку. В Common Lisp в этой ситуации следует использовать ecase (см. раздел 14.6).

Переименование

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

(defun depth (x)

(if (atom x)

(1+ (apply #'max (mapcar #'depth x)))))

При первом же тестировании мы обнаружим, что она дает значение, завышенное на 1:

> (depth '((a)))

Исходное значение должно быть равно 0, а не 1. Исправим этот недочет, а заодно дадим функции более конкретное имя:

(defun nesting-depth (x)

(if (atom x)

(1+ (apply #'max (mapcar #'depth x)))))

Теперь снова протестируем:

> (nesting-depth '((a)))

Мы получили тот же результат. В чем же дело? Да, ошибку мы исправили, но этот результат получается не из исправленного кода. Приглядитесь внимательно, ведь мы забыли поменять имя в рекурсивном вызове, и наша новая функция по-прежнему вызывает некорректную функцию depth.

Путаница аргументов по ключу и необязательных аргументов

Если функция принимает одновременно необязательные аргументы и аргументы по ключу, частой ошибкой является случайная передача ключевого слова (по невнимательности) в качестве значения необязательного аргумента. Например, функция read-from-string имеет следующий список аргументов:

(read-from-string string &optional eof-error eof-value

&key start end preserve-whitespace)

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

> (read-from-string "abcd" :start 2)

ABCD

то :start и 2 будут расценены как необязательные аргументы. Корректный вызов будет выглядеть следующим образом:

> (read-from-string "abcd" nil nil :start 2)

Некорректные декларации

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

(defun df* (a b)

(declare (double-float a b))

(* a b))

и поэтому компилятор сгенерировал код, предназначенный для умножения только чисел double-float.

Если df* вызывается с аргументами, не соответствующими задекларированному типу, то это вызовет ошибку или вовсе вернет мусор. А в одной из реализаций при передаче в эту функцию двух фиксированных целых происходит аппаратное прерывание:

> (df* 2 3)

Error: Interrupt.

Если у вас возникает подобная серьезная ошибка, с большой вероятностью ее причиной является неверная декларация типа.

Предупреждения

Иногда Лисп может жаловаться на что-либо без прерывания вычислений. Многие из этих предупреждений являются ложными тревогами. Например, часто возникают предупреждения, которыми сопровождается компиляция функций, содержащих незадекларированные или неиспользуемые переменные. Например, во втором вызове map-int (стр. 117) переменная x не используется. Если вы не хотите, чтобы компилятор каждый раз сообщал вам об этом факте, используйте декларацию ignore:

(map-int #'(lambda (x)

(declare (ignore x))

(random 100))

10)

[1] Домашняя страница проекта - http://common-lisp.net/project/slime/. - Прим. перев.

[2] Как раз поэтому отладчик в Лиспе называют break loop. - Прим. перев.