WWW.BOOK.LIB-I.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Электронные ресурсы
 
s

Pages:   || 2 | 3 | 4 |

«По договору между издательством «Символ-Плюс» и Интернет-магазином «Books.Ru – Книги России» единственный легальный способ получения данного файла с книгой ISBN ...»

-- [ Страница 1 ] --

По договору между издательством «Символ-Плюс» и Интернет-магазином

«Books.Ru – Книги России» единственный легальный способ получения данного файла с книгой ISBN 978-5-93286-206-3, название «ANSI Common Lisp» –

покупка в Интернет-магазине «Books.Ru – Книги России». Если Вы получили данный файл каким-либо другим образом, Вы нарушили международное

законодательство и законодательство Российской Федерации об охране авторского права. Вам необходимо удалить данный файл, а также сообщить

издательству «Символ-Плюс» (piracy@symbol.ru), где именно Вы получили данный файл.

ANSI Common Lisp Paul Graham

PRENTICE HALL

ANSI Common Lisp Пол Грэм Санкт-Петербург – Москва Серия «High tech»

Пол Грэм ANSI Common Lisp Перевод И. Хохлов Главный редактор А. Галунов Зав. редакцией Н. Макарова Научный редактор В. Демкин Редактор А. Родин Корректор С. Беляева Верстка Д. Орлова Грэм П.

ANSI Common Lisp. – Пер. с англ. – СПб.: Символ-Плюс, 2012. – 448 с., ил.

ISBN 978-5-93286-206-3 Книга «ANSI Common Lisp» сочетает в себе введение в программирование на Лиспе и актуальный справочный материал по ANSI-стандарту языка. Новички найдут в ней примеры интересных программ с их тщательным объяснением.

Профессиональные разработчики оценят всесторонний практический подход.

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

Книга содержит: детальное рассмотрение объектно-ориентированного программирования – не только описание CLOS, но и пример собственного встроенного объектно-ориентированного языка; более 20 самостоятельных примеров, в том числе трассировщик лучей, генератор случайного текста, сопоставление с образцом, логический вывод, программа для генерации HTML, алгоритмы поиска и сортировки, файлового ввода-вывода, сжатия данных, а также вычислительные задачи. Особое внимание уделяется критически важным концепциям, включая префиксный синтаксис, связь кода и данных, рекурсию, функциональное программирование, типизацию, неявное использование указателей, динамическое выделение памяти, замыкания, макросы, предшествование классов, суть методов обобщенных функций и передачи сообщений.

Вы найдете полноценное руководство по оптимизации, примеры различных стилей программирования, включая быстрое прототипирование, разработку снизу-вверх, объектно-ориентированное программирование и применение встраиваемых языков.

–  –  –

Комментарии................................................. 421 Алфавитный указатель........................................436 Half lost on my firmness gains to more glad heart, Or violent and from forage drives A glimmering of all sun new begun Both harp thy discourse they march’d, Forth my early, is not without delay;

For their soft with whirlwind; and balm.

Undoubtedly he scornful turn’d round ninefold, Though doubled now what redounds, And chains these a lower world devote, yet inflicted?

Till body or rare, and best things else enjoy’d in heav’n To stand divided light at ev’n and poise their eyes, Or nourish, lik’ning spiritual, I have thou appear. 1





Henley

Я потерял итог моих трудов, что сердце грели мне, И было то ожесточенье сердца иль движение вперед, Но солнце снова озарило нас, И арфа вновь твоя заговорила, Вперед, как можно раньше и без промедленья;

Тот ураган для них стал мягок, как бальзам.

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

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

–  –  –

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

Аудитория Книга «ANSI Common Lisp» предназначена как для студентов, изучающих этот язык, так и для профессиональных программистов. Ее чтение не требует предварительного знания Лиспа. Опыт написания программ на других языках был бы, безусловно, полезен, но не обязателен. Повествование начинается с основных понятий, что позволяет уделить особое внимание моментам, которые обычно приводят в замешательство человека, впервые знакомящегося с Лиспом.

Эта книга может использоваться в качестве учебного пособия по Лиспу или как часть курсов, посвященных искусственному интеллекту или теории языков программирования. Профессиональные разработчики, желающие изучить Лисп, оценят простой, практический подход. Те, кто уже знаком с языком, найдут в книге множество полезных примеров и оценят ее как удобный справочник по стандарту ANSI Common Lisp.

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

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

Главы 10–14 охватывают макросы, CLOS (объектная система Common 14 Предисловие Lisp), операции со списками, оптимизацию, а также более сложные темы, такие как пакеты и макросы чтения. Главы 15–17 подводят итог предыдущих глав на трех примерах реальных приложений: программа для создания логических интерфейсов, HTML-генератор и встроенный объектно-ориентированный язык программирования.

Последняя часть книги состоит из четырех приложений, которые будут полезны всем читателям. Приложения A–D включают руководство по отладке, исходные коды для 58 операторов языка, описание основных отличий ANSI Common Lisp от предыдущих версий языка° и справочник по каждому оператору в ANSI Common Lisp.

Книга завершается комментариями, содержащими пояснения, ссылки, дополнительный код и прочие отступления. Наличие комментария помечается в основном тексте маленьким кружочком: °.

Код Несмотря на то что книга посвящена ANSI Common Lisp, по ней можно изучать любую разновидность Common Lisp. Примеры, демонстрирующие новые возможности, обычно сопровождаются комментариями, поясняющими, как они могут быть адаптированы к более ранним реализациям.

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

http://www.eecs.harvard.edu/onlisp/

Анонимный доступ к коду можно получить по ftp:

ftp://ftp.eecs.harvard.edu:/pub/onlisp/ Вопросы и комментарии присылайте на pg@eecs.harvard.edu.

«On Lisp»

В этой книге я постарался показать уникальные особенности, которые выделяют Лисп из множества языков программирования, а также предоставляемые им новые возможности. Например, макросы – они позволяют разработчику писать программы, которые будут писать другие программы. Лисп – единственный язык, который позволяет с легкостью осуществлять это, потому что только он предлагает необходимые для этого абстракции. Читателям, которым интересно узнать больше о макросах и других интересных возможностях языка, я предлагаю познакомиться с книгой «On Lisp»1, которая является продолжением данного издания.

Paul Graham «On Lisp», Prentice Hall, 1993. – Прим. перев.

Предисловие

Благодарности Из всех друзей, участвовавших в работе над книгой, наибольшую благодарность я выражаю Роберту Моррису, который на протяжении всего времени помогал совершенствовать это издание. Некоторые примеры, включая Henley (cтр. 149) и сопоставление с образцом (стр. 254), взяты из написанного им кода.

Я был счастлив работать с первоклассной командой технических рецензентов: Сконом Бриттаном (Skona Brittain), Джоном Фодераро (John Foderaro), Ником Левином (Nick Levine), Питером Норвигом (Peter Norvig) и Дэйвом Турецки (Dave Touretzky). Вряд ли найдется хотя бы одна страница, к улучшению которой они не приложили руку. Джон Фодераро даже переписал часть кода к разделу 5.7.

Нашлись люди, которые согласились прочитать рукопись целиком или частично, включая Кена Андерсона (Ken Anderson), Тома Читама (Tom Cheatham), Ричарда Фейтмана (Richard Fateman), Стива Хайна (Steve Hain), Барри Марголина (Barry Margolin), Уолдо Пачеко (Waldo Pacheco), Вилера Румла (Wheeler Ruml) и Стюарта Рассела (Stuart Russel).

Кен Андерсон и Вилер Румл сделали множество полезных замечаний.

Я благодарен профессору Читаму и Гарварду в целом за предоставление необходимых для написания книги возможностей. Также благодарю сотрудников лаборатории Айкен: Тони Хэртмана (Tony Hartman), Дейва Мазиерса (Dave Mazieres), Януша Джуду (Janusz Juda), Гарри Бохнера (Harry Bochner) и Джоанну Клис (Joanna Klys).

Я рад, что у меня снова появилась возможность поработать с сотрудниками Prentice Hall: Аланом Аптом (Alan Apt), Моной Помпили (Mona Pompili), Ширли МакГир (Shirley McGuire) и Ширли Майклс (Shirley Michaels). Обложка книги выполнена превосходным мастером Джино Ли (Gino Lee) из Bow & Arrow Press, Кэмбридж.

Эта книга была набрана с помощью L TEX, языка, созданного Лесли ЛэмA портом (Leslie Lamport) поверх TEX’а Дональда Кнута (Donald Knuth), с использованием дополнительных макросов авторства Л.А. Карра (L.A. Carr), Вана Якобсона (Van Jacobson) и Гая Стила (Guy Steele). Чертежи были выполнены с помощью программы Idraw, созданной Джоном Влиссидсом (John Vlissids) и Скоттом Стантоном (Skott Stanton).

Предпросмотр всей книги был сделан с помощью программы Ghostview, написанной Тимом Тейзеном (Tim Theisen) на основе интерпретатора Ghostscript, созданного Л. Питером Дойчем (L. Peter Deutch).

Я должен поблагодарить и многих других людей: Генри Бейкера (Henry Baker), Кима Барретта (Kim Barrett), Ингрид Бассет (Ingrid Basset), Тревора Блеквелла (Trevor Blackwell), Пола Беккера (Paul Becker), Гарри Бисби (Gary Bisbee), Франка Душмана (Frank Dueschmann), Франсиса Дикли (Frances Dickey), Рича и Скотта Дрейвса (Rich and Scott Draves), Билла Дабак (Bill Dubuque), Дэна Фридмана (Dan Friedman), 16 Предисловие Дженни Грэм (Jenny Graham), Эллис Хартли (Alice Hartley), Дэвида Хендлера (David Hendler), Майка Хьюлетта (Mike Hewlett), Гленна Холловота (Glenn Hollowat), Брэда Карпа (Brad Karp), Соню Кини (Sonya Keene), Росса Найтс (Ross Knights), Митсуми Комуро (Mutsumi Komuro), Стефи Кутзиа (Steffi Kutzia), Дэвида Кузника (David Kuznick), Мэди Лорд (Madi Lord), Джулию Маллози (Julie Mallozzi), Пола МакНами (Paul McNamee), Дэйва Муна (Dave Moon), Говарда Миллингса (Howard Mullings), Марка Ницберга (Mark Nitzberg), Ненси Пармет (Nancy Parmet) и ее семью, Роберта Пенни (Robert Penny), Майка Плуча (Mike Plusch), Шерил Сэкс (Cheryl Sacks), Хейзэма Сейеда (Hazem Sayed), Шеннона Спайреса (Shannon Spires), Лоу Штейнберга (Lou Steinberg), Пола Стоддарда (Paul Stoddard), Джона Стоуна (John Stone), Гая Стила (Guy Steele), Стива Страссмана (Steve Strassmann), Джима Вейча (Jim Veitch), Дэйва Уоткинса (Dave Watkins), Айдела и Джулианну Вебер (Idelle and Julian Weber), Вейкерсов (the Weickers), Дэйва Йоста (Dave Yost) и Алана Юлли (Alan Yuille).

Но больше всего я благодарен моим родителям и Джекки.

Дональд Кнут назвал свою известную серию книг «Искусство программирования». В прочитанной им Тьюринговской лекции он объяснил, что это название было выбрано не случайно, так как в программирование его привела как раз «возможность писать красивые программы».

Так же как и архитектура, программирование сочетает в себе искусство и науку. Программа создается на основе математических принципов, так же как здание держится согласно законам физики. Но задача архитектора не просто построить здание, которое не разрушится. Почти всегда он стремится создать нечто прекрасное.

Как и Дональд Кнут, многие программисты чувствуют, что такова истинная цель программирования. Так считают почти все Лисп-хакеры.

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

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

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

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

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

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

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

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

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

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

Многое изменилось и в мире реализаций Common Lisp. Автор сознательно не упоминает названия реализаций, так как их жизненный срок не определен. Многих реализаций языка уже нет в живых, но на их место пришли новые. Необходимо отметить, что сейчас имеется ряд блестящих реализаций Common Lisp, как коммерческих, так и свободных.

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

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

–  –  –

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

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

–  –  –

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

; Lisp (defun addn (n) #’(lambda (x) (+ x n))) Как функция addn будет выглядеть на С? Ее просто невозможно написать.

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

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

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

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

Да, это и есть макросы, и опытные программисты используют их на каждом шагу. Вы узнаете, как создавать свои макросы, в главе 10.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Проблема в том, что такой подход не учитывает человеческий фактор.

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

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

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

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

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

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

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

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

–  –  –

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

В программировании наблюдается похожая идея. Новая среда – это «объектно-ориентированный динамический язык программирования»;

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

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

Добро пожаловать в Лисп Глава 2.

Цель этой главы – помочь вам начать программировать как можно скорее. Прочитав ее, вы узнаете достаточно о языке Common Lisp, чтобы начать писать программы.

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

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

Одними из наиболее простых выражений в Лиспе являются целые числа. Если ввести 1 после приглашения, система напечатает его значение, после чего выведет очередное приглашение, ожидая новых выражений.

В данном случае введенное выражение выглядит так же, как и полученное значение. Такие выражения называют самовычисляемыми. Числа (например, 1) – самовычисляемые объекты. Давайте посмотрим на более интересные выражения, вычисление которых требует совершения некоторых действий. Например, если мы хотим сложить два числа, то напишем 26 Глава 2. Добро пожаловать в Лисп (+ 2 3) В выражении (+ 2 3) знак + – это оператор, а числа 2 и 3 – его аргументы.

В повседневной жизни вы бы написали это выражение как 2+3, но в Лиспе мы сначала ставим оператор +, следом за ним располагаем аргументы, а все выражение заключаем в скобки: (+ 2 3). Такую структуру принято называть префиксной нотацией, так как первым располагается оператор. Поначалу этот способ записи может показаться довольно странным, но на самом деле именно такому способу записи выражений Лисп обязан своими возможностями.

Например, если мы хотим сложить три числа, в обычной форме записи нам придется воспользоваться плюсом дважды:

2+3+4 в то время как в Лиспе вы всего лишь добавляете еще один аргумент:

(+ 2 3 4) В обычной нотации1 оператор + имеет два аргумента, один перед ним и один после. Префиксная запись дает большую гибкость, позволяя оператору иметь любое количество аргументов или вообще ни одного:

(+) (+ 2) (+ 2 3) (+ 2 3 4) (+ 2 3 4 5) Поскольку у оператора может быть произвольное число аргументов, нужен способ показать, где начинается и заканчивается выражение. Для этого используются скобки.

Выражения могут быть вложенными:

(/ (– 7 1) (– 4 2)) Здесь мы делим разность 7 и 1 на разность 4 и 2.

Другая особенность префиксной нотации: все выражения в Лиспе – либо атомы (например, 1), либо списки, состоящие из произвольного количества выражений. Приведем допустимые Лисп-выражения:

2 (+ 2 3) (+ 2 3 4) (/ (– 7 1) (– 4 2))

Ее также называют инфиксной. – Прим. перев.

2.2. Вычисление

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

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

В Лиспе + – это функция, а выражение вида (+ 2 3) – это вызов функции. Результат вызова функции вычисляется в 2 шага:

1. Сначала вычисляются аргументы, слева направо. В нашем примере все аргументы самовычисляемые, поэтому их значениями являются 2 и 3.

2. Затем аргументы применяются к функции, задаваемой оператором.

В нашем случае это оператор сложения, который возвращает 5.

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

Посмотрим, что происходит при вычислении выражения (/ (– 7 1) (– 4 2)):

1. Вычисляется (– 7 1): 7 вычисляется в 7, 1 – в 1. Эти аргументы передаются функции -, которая возвращает 6.

2. Вычисляется (– 4 2): 4 вычисляется в 4, 2 – в 2, функция – применяется к этим аргументам и возвращает 2.

3. Значения 6 и 2 передаются функции /, которая возвращает 3.

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

Тем не менее существуют операторы, которые не следуют принятому в Common Lisp порядку вычислений. Один из них – quote, или оператор цитирования. quote – это специальный оператор; это означает, что у него есть собственное правило вычисления, а именно: ничего не делать.

Фактически quote берет один аргумент и просто возвращает его текстовую запись:

(quote (+ 3 5)) (+ 3 5) 28 Глава 2. Добро пожаловать в Лисп

–  –  –

Для удобства в Common Lisp можно заменять оператор quote на кавычку. Тот же результат можно получить, просто поставив ’ перед цитируемым выражением:

’(+ 3 5) (+ 3 5) В явном виде оператор quote почти не используется, более распространена его сокращенная запись с кавычкой.

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

2.3. Данные Лисп предоставляет все типы данных, которые есть в большинстве других языков, а также некоторые другие, отсутствующие где-либо еще.

С одним типом данных мы уже познакомились. Это integer – целое число, записываемое в виде последовательности цифр: 256.

Другой тип данных, который есть в большинстве других языков, – строка, представляемая как последовательность символов, окруженная двойными кавычками:

"ora et labora". Так же как и целые числа, строки самовычисляемы.

В Лиспе есть два типа, которые редко используются в других языках, – символы и списки. Символы – это слова.

Обычно они преобразуются к верхнему регистру независимо от того, как вы их ввели:

’Artichoke ARTICHOKE

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

Список – это последовательность из нуля или более элементов, заключенных в скобки. Эти элементы могут принадлежать к любому типу, в том числе могут являться другими списками.

Чтобы Лисп не счел список вызовом функции, его нужно процитировать:

’(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 ’my (+ 2 1) "Sons") (MY 3 "Sons") Пришло время оценить одну из наиболее важных особенностей Лиспа.

Программы, написанные на Лиспе, представляются в виде списков.

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

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

В противном случае список будет расценен как код и будет вычислено его значение:

(list ’(+ 2 1) (+ 2 1)) ((+ 2 1) 3) Первый аргумент цитируется и остается списком, в то время как второй аргумент расценивается как вызов функции и превращается в число.

Список может быть пустым. В Common Lisp возможны два типа представления пустого списка: пара пустых скобок и специальный символ nil. Независимо от того, как вы введете пустой список, он будет отображен как nil.

() NIL nil NIL 30 Глава 2. Добро пожаловать в Лисп

Перед () необязательно ставить кавычку, так как символ nil самовы- числяем.

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

(cons ’a ’(b c d)) (A B C D) Список из одного элемента также может быть создан с помощью cons и пустого списка. Функция list, с которой мы уже познакомились, – всего лишь более удобный способ последовательного использования cons.

(cons ’a (cons ’b nil)) (A B) (list ’a ’b) (A B) Простейшие функции для получения отдельных элементов списка – car и cdr.° Функция 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 возвращает истину, если ее аргумент – список:

(listp ’(a b c)) T

2.5. Истинность

–  –  –

Логические операторы and (и) и or (или) действуют похожим образом.

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

Если все аргументы истинны (то есть не nil), то оператор and вернет значение последнего:

(and t (+ 1 2)) Но если один из аргументов окажется ложным, то следующие за ним аргументы не будут вычислены. Так же действует и or, вычисляя значения аргументов до тех пор, пока среди них не найдется хотя бы одно истинное значение.

Эти два оператора – макросы. Как и специальные операторы, макросы могут обходить обычный порядок вычисления. В главе 10 объясняется, как писать собственные макросы.

2.6. Функции Новые функции можно определить с помощью оператора defun. Он обычно принимает три или более аргументов: имя, список параметров и одно или более выражений, которые составляют тело функции. Вот как мы можем с помощью defun определить функцию third:

(defun our-third (x) (car (cdr (cdr x)))) OUR-THIRD Первый аргумент задает имя функции, в нашем примере это our-third.

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

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

Вызов our-third возвращает (car (cdr (cdr x))), какое бы значение аргумента x ни было задано:

(our-third ’(a b c d)) C Теперь, когда мы познакомились с переменными, будет легче понять, чем являются символы. Это попросту имена переменных, существующие сами по себе. Именно поэтому символы, как и списки, нуждаются в цитировании. Так же как «закавыченные» списки не будут восприняты как код, так и «закавыченные» символы не будут перепутаны с переменными.

Функцию можно рассматривать как обобщение Лисп-выражения. Следующее выражение проверяет, превосходит ли сумма чисел 1 и 4 число 3:

2.7. Рекурсия

–  –  –

1. Проверяем, пуст ли список lst. Если он пуст, значит, obj не присутствует в списке.

2. Если obj является первым элементом lst, значит, он есть в этом списке.

3. В другом случае проверяем, есть ли obj среди оставшихся элементов списка lst.

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

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

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

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

1. Получить копию документа.

2. Найти в нем информацию об изменении численности населения.

3. Если в нем также упоминаются иные источники, которые могут быть полезны, также изучить и их.

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

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

2.8. Чтение Лиспа Определенная в предыдущем разделе функция заканчивается пятью закрывающими скобками. Более сложные функции могут заканчиваться семью-восемью скобками. Это часто обескураживает людей, которые только начинают изучать Лисп. Как можно читать подобный код, не говоря уже о том, чтобы писать его самому? Как искать в нем парные скобки?

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

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

Любой Лисп-хакер, независимо от своего стажа, с трудом разберет определение 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, напечатанный в toplevel. Обычно функции типа format не вызываются напрямую в toplevel, а используются внутри программ, поэтому возвращаемые ими значения не отображаются.

В редакторе vi эта опция включается командой :set sm. В Emacs M-x lisp

–  –  –

Первый аргумент для функции format, t, показывает, что вывод будет отправлен в стандартное место, принятое по умолчанию. Обычно это toplevel. Второй аргумент – это строка, служащая шаблоном для вывода. В ней каждое ~A определяет позицию для заполнения, а символ ~% соответствует переносу строки. Позиции по порядку заполняются значениями оставшихся аргументов.

Стандартная функция чтения – read (ee также называют считывателем).

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

(defun askem (string) (format t "~A" string) (read))

Это работает так:

(askem "How old are you? ") How old are you? 29 Учтите, что для завершения считывания read будет ожидать нажатия вами Enter. Поэтому не стоит использовать функцию read, не печатая перед этим приглашение ко вводу, иначе может показаться, что программа зависла, хотя на самом деле она просто ожидает ввода.

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

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

Во всех предыдущих разделах мы придерживались «чистого» Лиспа, то есть Лиспа без побочных эффектов. Побочный эффект – это событие, которое каким-либо образом изменяет состояние системы. При вычислении выражения (+ 1 2) возвращается значение 3, и никаких побочных эффектов не происходит. В последнем же примере побочный эффект производится функцией format, которая не только возвращает значение, но и печатает что-то еще. Это одна из разновидностей побочных эффектов.

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

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

2.10. Переменные Один из наиболее часто используемых операторов в Common Lisp – это

let, который позволяет вам ввести новые локальные переменные:

(let ((x 1) (y 2)) (+ x y)) Выражение с использованием let состоит из двух частей. Первая содержит инструкции, определяющие новые переменные. Каждая такая инструкция содержит имя переменной и соответствующее ей выражение.

Чуть выше мы создали две новые переменные, x и y, которым были присвоены значения 1 и 2. Эти переменные действительны внутри тела let.

За списком переменных и значений следуют выражения, которые вычисляются по порядку. В нашем случае имеется только одно выражение, (+ x y). Значением всего вызова 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 вызовет саму себя, чтобы пользователь повторил попытку.

Так будет повторяться до тех пор, пока функция read не получит число:

(ask-number) Please enter a number. a Please enter a number. (no hum) Please enter a number. 52 Переменные типа val, создаваемые оператором let, называются локальными, то есть действительными в определенной области. Есть также глобальные переменные, которые действительны везде.1 Реальная разница между локальными и глобальными переменными будет

–  –  –

Глобальная переменная может быть создана с помощью оператора defparameter:

(defparameter *glob* 99) *GLOB* Такая переменная будет доступна везде, кроме выражений, в которых создается локальная переменная с таким же именем. Чтобы избегать таких случайных совпадений, принято давать глобальным переменным имена, окруженные звездочками.

Также в глобальном окружении можно задавать константы, используя оператор defconstant1:

(defconstant limit (+ *glob* 1)) Нет необходимости давать константам имена, окруженные звездочками, потому что любая попытка определить переменную с таким же именем закончится ошибкой. Чтобы узнать, соответствует ли какое-то имя глобальной переменной или константе, воспользуйтесь boundp:

(boundp ’*glob*) T

2.11. Присваивание

В Common Lisp наиболее общим средством присваивания значений является оператор setf. Он может присваивать значения переменным любых типов:

(setf *glob* 98) (let ((n 10)) (setf n 2) n) Если setf пытается присвоить значение переменной, которая в данном контексте не является локальной, то переменная будет определена как глобальная:

(setf x (list ’a ’b ’c)) (A B C) Таким образом, вы можете создавать глобальные переменные неявно, просто присваивая им значения. Однако в файлах исходного кода считается хорошим тоном задавать их явно с помощью оператора defparameter.

Как и для специальных переменных, для определяемых пользователем констант существует негласное правило, согласно которому их имена следует окружать знаками +. Следуя этому правилу, в примере выше мы бы определили константу +limit+. – Прим. перев.

2.12. Функциональное программирование

–  –  –

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

Например, функция 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)

А что если вы хотите действительно удалить элементы из списка? В Лиспе принято предоставлять список в качестве аргумента какой-либо функции и присваивать возвращаемое ей значение с помощью setf. Чтобы удалить все a из списка x, мы скажем:

(setf x (remove ’a x)) 40 Глава 2. Добро пожаловать в Лисп В функциональном программировании избегают использовать setf и другие подобные вещи. Поначалу сложно вообразить, что это попросту возможно, не говоря уже о том, что желательно. Как можно создавать программы только с помощью возвращения значений?

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

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

2.13. Итерация Когда мы хотим повторить что-то многократно, порой удобнее использовать итерацию, чем рекурсию. Типичный пример использования итерации – генерация таблиц. Следующая функция (defun show-squares (start end) (do ((i start (+ i 1))) (( i end) ’done) (format t "~A ~A~%" i (* i i)))) печатает квадраты целых чисел от start до end:

(show-squares 2 5) DONE Макрос do – основной итерационный оператор в Common Lisp. Как и в случае let, первый аргумент do задает переменные. Каждый элемент этого списка может выглядеть как:

(variable initial update) где variable – символ, а initial и update – выражения. Исходное значение каждой переменной определяется значением initial, и на каждой итерации это значение будет меняться в соответствии со значением update. В примере show-squares do использует только одну переменную, i.

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

2.13. Итерация Второй аргумент 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 существуют более простые итерационные операторы. К примеру, запишем функцию, определяющую длину списка:

(defun our-length (lst) (let ((len 0)) (dolist (obj lst) (setf len (+ len 1))) len)) В этом примере оператор dolist принимает первый аргумент вида (variable expression) и следующий за ним набор выражений. Они вычисляются для каждого элемента списка, значение которых по очереди присваивается переменной. В этом примере для каждого obj в lst увеличивается значение len.

Рекурсивная версия этой функции:

(defun our-length (lst) (if (null lst) (+ (our-length (cdr lst)) 1))) Если список пуст, его длина равна 0, иначе она на 1 больше длины списка cdr. Эта версия функции our-length более понятна, однако она неэффективна, поскольку не использует хвостовую рекурсию (см. раздел 13.2).

42 Глава 2. Добро пожаловать в Лисп

2.14. Функции как объекты

В Лиспе функции – это самые обычные объекты, такие же как символы, строки или списки. Давая функции имя с помощью function, мы получаем ассоциированный объект. Как и quote, function – это специальный оператор, и поэтому нам не нужно брать в кавычки его аргумент:

(function +) #Compiled-Function + 17BA4E Таким странным образом отображаются функции в типичной реализации Common Lisp.

До сих пор мы имели дело только с такими объектами, которые при печати отображаются так же, как мы их ввели. Это соглашение не распространяется на функции. Встроенная функция + обычно является куском машинного кода. В каждой реализации Common Lisp может быть свой способ отображения функций.

Аналогично использованию кавычки вместо quote возможно употребление #’ как сокращения для function:

#’+ #Compiled-Function + 17BA4E Как и любой другой объект, функция может служить аргументом. Примером функции, аргументом которой является функция, является apply.

Она требует функцию и список ее аргументов и возвращает результат вызова этой функции с заданными аргументами:

(apply #’+ ’(1 2 3)) (+ 1 2 3) Apply принимает любое количество аргументов, но последний из них обязательно должен быть списком:

(apply #’+ 1 2 ’(3 4 5)) Функция funcall делает то же самое, но не требует, чтобы аргументы были упакованы в список:

(funcall #’+ 1 2 3) Обычно создание функции и определение ее имени осуществляется с помощью макроса defun. Но функция не обязательно должна иметь имя, и для ее определения мы не обязаны использовать defun. Подобно большинству других объектов Лиспа, мы можем задавать функции буквально.

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

2.14. Функции как объекты лямбда-выражение. Лямбда-выражение – это список, содержащий символ lambda и следующие за ним список аргументов и тело, состоящее из 0 или более выражений. Ниже приведено лямбда-выражение, представляющее функцию, которая складывает два числа и возвращает их сумму:

(lambda (x y) (+ x y)) Список (x y) содержит параметры, за ним следует тело функции.

Лямбда-выражение можно считать именем функции.

Как и обычное имя функции, лямбда-выражение может быть первым элементом вызова функции:

((lambda (x) (+ x 100)) 1) а добавляя #’ к этому выражению, можно получить соответствующую функцию:

(funcall #’(lambda (x) (+ x 100)) 1) Помимо прочего, такая запись позволяет использовать функции, не присваивая им имена.

–  –  –

2.15. Типы Лисп обладает необыкновенно гибкой системой типов. Во многих языках необходимо задать конкретный тип для каждой переменной перед ее использованием. В Common Lisp значения имеют типы, а переменные – нет. Представьте, что у каждого объекта есть метка, которая определяет его тип. Такой подход называется динамической типизацией.

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

Несмотря на то, что объявления типов вовсе не обязательны, вы можете задавать их из соображений производительности. Объявления типов обсуждаются в разделе 13.3.

В Common Lisp встроенные типы образуют иерархию подтипов и надтипов. Объект всегда имеет несколько типов. Например, число 27 соответствует типам fixnum, integer, rational, real, number, atom и t в порядке увеличения общности. (Численные типы обсуждаются в главе 9.) Тип t является самым верхним во всей иерархии, поэтому каждый объект имеет тип t.

Функция typep определяет, принадлежит ли ее первый аргумент к типу, который задается вторым аргументом:

(typep 27 ’integer) T По мере изучения Common Lisp мы познакомимся с самыми разными встроенными типами.

2.16. Заглядывая вперед В этой главе мы довольно поверхностно познакомились с Лиспом. Но все же начинает вырисовываться портрет этого довольно необычного языка. Начнем с того, что он имеет единый синтаксис для записи всего кода. Синтаксис основан на списках, которые являются разновидностью объектов Лиспа. Функции, которые также являются Лисп-объектами, могут быть представлены в виде списков. А сам Лисп – это тоже программа на Лиспе, почти полностью состоящая из встроенных Лиспфункций, которые не отличаются от тех функций, которые вы можете определить самостоятельно.

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

Ричард Гэбриэл однажды в полушуточной форме назвал С языком для написания UNIX.° Также и мы можем назвать Лисп языком для написания Лиспа. Но между этими утверждениями есть существенная разница. Язык, который легко написать на самом себе, кардинально отлиИтоги главы чается от языка, годного для написания каких-то отдельных классов программ. Он открывает новый способ программирования: вы можете как писать программы на таком языке, так и совершенствовать язык в соответствии с требованиями своих программ. Если вы хотите понять суть программирования на Лиспе, начните с этой идеи.

Итоги главы

1. Лисп интерактивен. Вводя выражение в toplevel, вы тут же получаете его значение.

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

3. Порядок вычисления вызовов функций в Common Lisp таков: сначала вычисляются аргументы слева направо, затем они передаются оператору. Оператор quote не подчиняется этому порядку и возвращает само выражение неизменным (вместо его значения).

4. Помимо привычных типов данных в Лиспе есть символы и списки.

Программы на Лиспе записываются в виде списков, поэтому легко составлять программы, которые пишут другие программы.

5. Есть три основные функции для обращения со списками: cons, строящая список; car, возвращающая первый элемент списка; cdr, возвращающая весь список, за исключением его первого элемента.

6. В Common Lisp символ t имеет истинное значение, nil – ложное.

В контексте логических операций все, кроме nil, является истинным. Основной условный оператор – if. Операторы and и or также могут считаться условными.

7. Лисп состоит по большей части из функций. Собственные функции можно создавать с помощью defun.

8. Функция, которая вызывает сама себя, называется рекурсивной.

Рекурсивную функцию следует понимать как процесс, но не как агрегат.

9. Скобки не создают затруднений, поскольку программисты пишут и читают Лисп-код по отступам.

10. Основные функции ввода-вывода: read, являющаяся полноценным обработчиком Лисп-выражений, и format, использующая для вывода заданный шаблон.

11. Локальные переменные создаются с помощью let, глобальные – с помощью defparameter.

12. Для присваивания используется оператор setf. Его первый аргумент может быть как переменной, так и выражением.

46 Глава 2. Добро пожаловать в Лисп

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

14. Основной итерационный оператор – do.

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

16. В Лиспе значения имеют типы, а переменные – нет.

–  –  –

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

8. Предложите итеративное и рекурсивное определение функции, которая:

(a) печатает количество точек, которое равно заданному положительному целому числу;

(b) возвращает количество символов a в заданном списке.

9. Ваш товарищ пытается написать функцию, которая суммирует все значения элементов списка, кроме nil. Он написал две версии такой функции, но ни одна из них не работает. Объясните, что не так в каждой из них, и предложите корректную версию:

(a) (defun summit (lst) (remove nil lst) (apply #’+ lst))

–  –  –

Списки – это одна из базовых структур данных в Лиспе. В ранних диалектах списки были единственной структурой данных, и именно им Лисп обязан своим названием: «LISt Processor» (Обработчик списков).

Нынешний Лисп уже не соответствует этому акрониму. Common Lisp является языком общего назначения и предоставляет программисту широкий набор структур данных.

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

3.1. Ячейки В разделе 2.4 вводятся cons, car и cdr – простейшие функции для манипуляций со списками. В действительности, cons объединяет два объекта в один, называемый ячейкой (cons). Если быть точнее, то cons – это пара указателей, первый из которых указывает на car, второй – на cdr.

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

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

3.1. Ячейки а cdr – его остаток (который является либо cons-ячейкой, либо nil). И договоренность всегда была таковой: использовать car для обозначения первого элемента списка, а cdr – для его остатка. Так эти названия стали синонимами операций first и rest. Таким образом, списки – это не отдельный вид объектов, а всего лишь набор связанных между собой cons-ячеек.

Если мы попытаемся использовать cons вместе с nil, (setf x (cons ’a nil)) (A) то получим список, состоящий из одной ячейки, как показано на рис. 3.1.

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

Вызывая car или cdr, мы получаем объект, на который указывает соответствующий указатель:

(car x) A (cdr x) NIL

–  –  –

Для списка из нескольких элементов указатель на car дает первый элемент списка, а указатель на cdr – его остаток.

Элементами списка могут быть любые объекты, в том числе и другие списки:

(setf z (list ’a (list ’b ’c) ’d)) (A (B C) D) Соответствующая структура показана на рис. 3.3; car второй ячейки указывает на другой список:

(car (cdr z)) (B C)

–  –  –

Рис. 3.3. Вложенный список В этих двух примерах списки состояли из трех элементов. При этом в последнем примере один из элементов тоже является списком. Такие списки называют вложенными (nested), в то время как списки, не содержащие внутри себя подсписков, называют плоскими (flat).

Проверить, является ли объект cons-ячейкой, можно с помощью функции consp. Поэтому listp можно определить так:

(defun out-listp (x) (or (null x) (consp x)))

Теперь определим предикат atom, учитывая тот факт, что атомами в Лиспе считается все, кроме cons-ячеек:

(defun our-atom (x) (not (consp x))) Исключением из этого правила считается nil, который является и атомом, и списком одновременно.

3.2. Равенство Каждый раз, когда вы вызываете функцию cons, Лисп выделяет память для двух указателей. Это означает, что, вызывая cons дважды с одними и теми же аргументами, мы получим два значения, которые будут выглядеть идентично, но соответствовать разным объектам:

3.3. Почему в Лиспе нет указателей

–  –  –

3.3. Почему в Лиспе нет указателей Чтобы понять, как устроен Лисп, необходимо осознать, что механизм присваивания значения переменным похож на построение списков из объектов. Переменной соответствует указатель на ее значение, так же как cons-ячейки имеют указатели на car и cdr.

Некоторые другие языки позволяют оперировать указателями явно.

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

Пусть две переменные указывают на один и тот же список:

(setf x ’(a b c)) (A B C) (setf y x) (A B C)

–  –  –

лее строгая функция, а основным предикатом проверки идентичности является eql. Роль eq разъясняется на стр. 234.

Функция our-equal применима не к любым спискам, а только к спискам сим

–  –  –

Рис. 3.4. Две переменные, указывающие на один список Что происходит, когда мы пытаемся присвоить y значение x? Место в памяти, связанное с переменной x, содержит не сам список, а указатель на него. Чтобы присвоить переменной y то же значение, достаточно просто скопировать этот указатель (рис. 3.4).

В данном случае две переменные будут одинаковыми с точки зрения eql:

(eql x y) T Таким образом, в Лиспе указатели явно не используются, потому что любое значение, по сути, является указателем. Когда вы присваиваете значение переменной или сохраняете его в какую-либо структуру данных, туда, на самом деле, записывается указатель. Когда вы запрашиваете содержимое какой-либо структуры данных или значение переменной, Лисп возвращает данные, на которые ссылается указатель. Но это происходит неявно, поэтому вы можете записывать значения в структуры или «в» переменные, не задумываясь о том, как это происходит.

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

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

–  –  –

3.5. Пример: сжатие В этом разделе приводится пример разработки простого механизма сжатия списков. Рассматриваемый ниже алгоритм принято называть кодированием повторов (run-length encoding). Представьте ситуацию:

в ресторане официант обслуживает столик, за которым сидят четыре посетителя:

«Что вы будете заказывать?» – спрашивает он.

«Принесите фирменное блюдо, пожалуйста», – отвечает первый посетитель.

«И мне тоже», – говорит второй.

«Ну и я за компанию», – присоединяется третий.

Все смотрят на четвертого клиента. «А я бы предпочел кориандровое суфле», – тихо произносит он.

Официант со вздохом разворачивается и идет к кухне. «Три фирменных, – кричит он повару, – и одно кориандровое суфле».

На рис. 3.6 показан подобный алгоритм для списков.

Функция compress принимает список из атомов и возвращает его сжатое представление:

(compress ’(1 1 1 0 1 0 0 0 0 1)) ((3 1) 0 1 (4 0) 1) 54 Глава 3. Списки

–  –  –

Рис. 3.6. Кодирование повторов: сжатие Если какой-либо элемент повторяется несколько раз, он заменяется на список, содержащий этот элемент и число его повторений.

Большая часть работы выполняется рекурсивной функцией compr, которая принимает три аргумента: elt – последний встреченный элемент; n – число его повторений; lst – остаток списка, подлежащий дальнейшей компрессии. Когда список заканчивается, вызывается функция n-elts, возвращающая сжатое представление n элементов elt. Если первый элемент lst по-прежнему равен elt, увеличиваем n и идем дальше. В противном случае мы получаем сжатое представление предыдущей серии одинаковых элементов и присоединяем это к тому, что получим с помощью compr от остатка списка.

Чтобы реконструировать сжатый список, воспользуемся uncompress (рис.

3.7):

(uncompress ’((3 1) 0 1 (4 0) 1)) (1 1 1 0 1 0 0 0 0 1) Эта функция выполняется рекурсивно, копируя атомы и раскрывая списки с помощью list-of:

(list-of 3 ’ho) (HO HO HO) В действительности, нет необходимости использовать list-of. Встроенная функция make-list выполняет ту же работу, однако использует аргументы по ключу (keyword), которых мы пока еще не касались.

Функции compress и uncompress, представленные на рис. 3.6 и 3.7, определены не так, как это сделал бы опытный программист. Они неэффекДоступ тивны, не осуществляют сжатие в достаточной мере и работают только со списками атомов. В следующих нескольких главах мы узнаем, как можно исправить все эти проблемы.

–  –  –

Чтобы получить n-й хвост списка, вызовем nthcdr:

(nthcdr 2 ’(a b c)) (C) Функции nth и nthcdr ведут отсчет элементов списка с 0. Вообще говоря, в Common Lisp любая функция, обращающаяся к элементам структур данных, начинает отсчет с нуля.

Эти две функции очень похожи, и вызов nth эквивалентен вызову car от

nthcdr. Определим nthcdr без обработки возможных ошибок:

(defun our-nthcdr (n lst) (if (zerop n) lst (our-nthcdr (- n 1) (cdr lst)))) Функция zerop всего лишь проверяет, равен ли нулю ее аргумент.

Функция last возвращает последнюю cons-ячейку списка:

(last ’(a b c)) (C) Это не последний элемент; чтобы получить последний элемент, а не последнюю ячейку, воспользуйтесь функцией car от last.

В Common Lisp для доступа к элементам с первого по десятый выделены специальные функции, которые получили названия от английских порядковых числительных (от first до tenth). Обратите внимание, что отсчет начинается не с нуля и (second x) эквивалентен (nth 1 x).

Кроме того, в Common Lisp определены функции типа caddr (сокращенный вызов car от cdr от cdr). Также определены функции вида cxr, где x – набор всех возможных сочетаний a и d длиной до четырех символов.

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

–  –  –

Из последнего примера видно, как 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.

–  –  –

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

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. Чтобы понять рекурсию, нужно понять рекурсию (defun len (lst) (if (null lst) (+ (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:

; wrong2 (defun our-member (obj lst) (if (eql (car lst) obj) lst (our-member obj (cdr lst)))) В этом определении необходима проверка списка на пустоту, иначе в случае отсутствия искомого элемента в списке рекурсивный вызов будет выполняться бесконечно. В приложении А эта проблема рассматривается более детально.

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

Такой метод доказательства носит название математической индукции. –

–  –  –

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 могла бы выглядеть следующим образом:

3.11. Последовательности

–  –  –

3.11. Последовательности Списки также можно рассматривать как последовательности элементов, следующих друг за другом в фиксированном порядке. В Common Lisp помимо списков к последовательностям также относятся векторы. В этом разделе вы научитесь работать со списками как с последовательностями. Более детально операции с последовательностями будут рассмотрены в разделе 4.4.

Длина последовательности определяется с помощью length:

(length ’(a b c)) Ранее мы писали урезанную версию этой функции, работающую только со списками.

62 Глава 3. Списки Скопировать часть последовательности можно с помощью subseq. Второй аргумент (обязательный) задает начало подпоследовательности, а третий (необязательный) – индекс первого элемента, не подлежащего копированию.

(subseq ’(a b c d) 1 2) (B) (subseq ’(a b c d) 1) (B C D) Если третий аргумент пропущен, то подпоследовательность заканчивается вместе с исходной последовательностью.

Функция reverse возвращает последовательность, содержащую исходные элементы в обратном порядке:

(reverse ’(a b c)) (C B A) С помощью reverse можно, например, искать палиндромы, т. е. последовательности, читаемые одинаково в прямом и обратном порядке (например, (a b b a)). Две половины палиндрома с четным количеством аргументов будут зеркальными отражениями друг друга. Используя

length, subseq и reverse, определим функцию mirror?1:

(defun mirror? (s) (let ((len (length s))) (and (evenp len) (let ((mid (/ len 2))) (equal (subseq s 0 mid) (reverse (subseq s mid)))))))

Эта функция определяет, является ли список таким палиндромом:

(mirror? ’(a b b a)) T Для сортировки последовательностей в Common Lisp есть встроенная функция sort. Она принимает список, подлежащий сортировке, и функцию сравнения от двух аргументов:

(sort ’(0 2 1 3 8) #’) (8 3 2 1 0) С функцией sort следует быть осторожными, потому что она деструктивна. Из соображений производительности sort не создает новый список, а модифицирует исходный. Поэтому если вы не хотите изменять исходную последовательность, передайте в функцию ее копию.°

Используя sort и nth, запишем функцию, которая принимает целое число n и возвращает n-й элемент в порядке убывания:

Ричард Фейтман указал, что есть более простой способ проверки па линдрома, а именно: (equal x (reverse x)). – Прим. перев.

3.12. Стопка

–  –  –

3.13. Точечные пары Списки, которые могут быть построены с помощью list, называются правильными списками (proper list). Правильным списком считается либо nil, либо cons-ячейка, cdr которой – также правильный список. Таким образом, можно определить предикат, который возвращает истину только для правильного списка1:

(defun proper-list? (x) (or (null x) (and (consp x) (proper-list? (cdr x))))) Оказывается, с помощью cons можно создавать не только правильные списки, но и структуры, содержащие ровно два элемента. При этом car соответствует первому элементу структуры, а cdr – второму.

(setf pair (cons ’a ’b)) (A. B) Поскольку эта cons-ячейка не является правильным списком, при отображении ее car и cdr разделяются точкой. Такие ячейки называются точечными парами (рис. 3.10).

–  –  –

3.14. Ассоциативные списки Также вполне естественно задействовать cons-ячейки для представления отображений. Список точечных пар называется ассоциативным списком (assoc-list, alist). С помощью него легко определить набор какихлибо правил и соответствий, к примеру:

(setf trans ’((+. "add") (-. "subtract"))) ((+. "add") (-. "subtract")) Ассоциативные списки медленные, но они удобны на начальных этапах работы над программой. В Common Lisp есть встроенная функция assoc для получения по ключу соответствующей ему пары в таком списке:

(assoc ’+ trans) (+. "add") (assoc ’* trans) NIL Если assoc ничего не находит, возвращается nil.

Попробуем определить упрощенный вариант функции assoc:

(defun our-assoc (key alist) (and (consp alist) (let ((pair (car alist))) (if (eql key (car pair)) pair (our-assoc key (cdr alist)))))) Как и member, реальная функция assoc принимает несколько аргументов по ключу, включая :test и :key. Также Common Lisp определяет assoc-if, которая работает по аналогии с member-if.

3.15. Пример: поиск кратчайшего пути

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

В этом примере узлам соответствуют символы, а сама сеть представлена как ассоциативный список элементов вида (узел. соседи).

Небольшая сеть, показанная на рис. 3.13, может быть записана так:

(setf min ’((a b c) (b c) (c d)))

Найти узлы, в которые можно попасть из узла a, поможет функция assoc:

(cdr (assoc ’a min)) (B C)

–  –  –

Программа на рис. 3.12 реализует поиск в ширину (breadth-first search).

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

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

Поиск выполняется функцией bfs. Первоначально в очереди только один элемент – путь к начальному узлу. Таким образом, shortest-path вызывает bfs с (list (list start)) в качестве исходной очереди.

Первое, что должна сделать bfs, – проверить, остались ли еще непройденные узлы. Если очередь пуста, bfs возвращает nil, сигнализируя, что путь не был найден. Если же еще есть непроверенные узлы, bfs берет первый из очереди. Если car этого узла содержит искомый элемент, значит, мы нашли путь до него, и мы возвращаем его, предварительно развернув. В противном случае мы добавляем все дочерние узлы в конец очереди. Затем мы рекурсивно вызываем bfs и переходим к следующему слою.

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

(shortest-path ’a ’d min) (A C D)

А вот как выглядит соответствующая очередь во время каждого из вызовов bfs:

((A)) ((B A) (C A)) ((C A) (C B A)) ((C B A) (D C A)) ((D C A) (D C B A)) В каждой следующей очереди второй элемент предыдущей очереди становится первым, а первый элемент становится хвостом (cdr) любых новых элементов в конце следующей очереди.

Разумеется, приведенный на рис. 3.12 код далек от полноценной эффективной реализации. Однако он убедительно показывает гибкость и удобство списков. В этой короткой программе мы используем списки тремя различными способами: список символов представляет путь, список путей представляет очередь1 при поиске по ширине, а ассоциативный список изображает саму сеть целиком.

В разделе 12.3 будет показано, как реа лизовать очереди более эффектив

–  –  –

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

Автоматическое управление памятью – одна из наиболее ценных особенностей Лиспа. Лисп-система работает с сегментом памяти, называемым куча (heap). Система владеет информацией об использованной и неиспользованной памяти и выделяет последнюю для размещения новых объектов. Например, функция cons выделяет память под создаваемую ею ячейку, поэтому создание новых объектов часто называют consing.

Если память будет выделяться, но не освобождаться, то рано или поздно свободная память закончится, и Лисп прекратит работу. Поэтому необходим механизм поиска и освобождения участков кучи, которые более не содержат нужных данных. Память, которая становится ненужной, называется мусором и подлежит уборке. Этот процесс называется сборкой мусора (garbge collection, GC).

Как появляется мусор? Давайте немного намусорим:

(setf lst (list ’a ’b ’c)) (A B C) (setf lst nil) NIL Первоначально мы вызвали list, которая трижды вызывала cons, а она, в свою очередь, выделила новые cons-ячейки в куче. После этого мы сделали lst пустым списком. Теперь ни одна из трех ячеек, созданных cons, не может быть использована1.

Объекты, которые никаким образом не могут быть доступны для использования, и считаются мусором. Теперь система может безбоязненно повторно использовать память, выделенную cons, по своему усмотрению.

Такой механизм управления памятью – огромный плюс для программиста, ведь теперь он не должен заботиться о явном выделении и освобождении памяти. Соответственно исчезают баги, связанные с некорЭто не всегда так. В toplevel доступны глобальные переменные *, **, ***, кото

–  –  –

ректным управлением памятью. Утечки памяти и висячие указатели просто невозможны в Лиспе.

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

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

Деструктивные функции подробно рассмотрены в разделе 12.4.

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

Во всяком случае, consing подходит для прототипов и экспериментов.

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

Итоги главы

1. Cons-ячейка – это структура, состоящая из двух объектов. Списки состоят из связанных между собой ячеек.

2. Предикат equal менее строг, чем eql. Фактически он возвращает истину, если объекты печатаются одинаково.

3. Все объекты в Лиспе ведут себя как указатели. Вам никогда не придется управлять указателями явно.

4. Скопировать список можно с помощью copy-list, объединить два списка – с помощью append.

Упражнения

5. Кодирование повторов – простой алгоритм сжатия списков, легко реализуемый в Лиспе.

6. Common Lisp имеет богатый набор средств для доступа к элементам списков, и эти функции определены в терминах car и cdr.

7. Отображающие функции применяют определенную функцию последовательно к каждому элементу или каждому хвосту списка.

8. Операции с вложенными списками сродни операциям с бинарными деревьями.

9. Чтобы оценить корректность рекурсивной функции, достаточно убедиться, что она соответствует нескольким требованиям.

10. Списки могут рассматриваться как множества. Для работы с множествами в Лиспе есть ряд встроенных функций.

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

12. Список – подтип последовательности. Common Lisp имеет множество функций для работы с последовательностями.

13. Cons-ячейка, не являющаяся правильным списком, называется точечной парой.

14. С помощью списков точечных пар можно представить элементы отображения. Такие списки называются ассоциативными.

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

–  –  –

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

В Common Lisp есть еще один тип структур – экземпляры объектов (instance). О них подробно рассказано в главе 11, описывающей CLOS.

4.1. Массивы В Common Lisp массивы создаются с помощью функции make-array, первым аргументом которой выступает список размерностей. Создадим массив 23:

(setf arr (make-array ’(2 3) :initial-element nil)) #Simple-Array T (2 3) BFC4FE Многомерные массивы в Common Lisp могут иметь по меньшей мере 7 размерностей, а в каждом измерении поддерживается хранение не менее 1 023 элементов1.

Аргумент :initial-element не является обязательным. Если он используется, то устанавливает начальное значение каждого элемента массива.

Поведение системы при попытке получить значение элемента массива, не инициализированного начальным значением, не определено.

В конкретной реа лизации ограничение сверху на количество размерностей

–  –  –

Чтобы получить элемент массива, воспользуйтесь aref. Как и большинство других функций доступа в Common Lisp, aref начинает отсчет элементов с нуля:

(aref arr 0 0) NIL

Новое значение элемента массива можно установить, используя setf вместе с aref:

(setf (aref arr 0 0) ’b) B (aref arr 0 0) B

Как и списки, массивы могут быть заданы буквально с помощью синтаксиса #na, где n – количество размерностей массива. Например, текущее состояние массива arr может быть задано так:

#2a((b nil nil) (nil nil nil))

Если глобальная переменная *print-array*1 установлена в t, массивы будут печататься в таком виде:

(setf *print-array* t) T arr #2A((B NIL NIL) (NIL NIL NIL)) Для создания одномерного массива можно вместо списка размерностей в качестве первого аргумента передать функции make-array целое число:

(setf vec (make-array 4 :initial-element nil)) #(NIL NIL NIL NIL) Одномерный массив также называют вектором. Создать и заполнить вектор можно с помощью функции vector:

(vector "a" ’b 3) #("a" B 3) Как и массив, который может быть задан буквально с помощью синтаксиса #na, вектор может быть задан буквально с помощью синтаксиса #().

Хотя доступ к элементам вектора может осуществить aref, для работы с векторами есть более быстрая функция svref:

(svref vec 0) NIL В вашей реа лизации *print-array* может изначально иметь значение t. – Прим. перев.

4.2. Пример: бинарный поиск Префикс «sv» расшифровывается как «simple vector». По умолчанию все векторы создаются как простые векторы.1

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

На рис. 4.1 приведена программа, которая работает подобным образом.

Она состоит из двух функций: bin-search2 определяет границы поиска и передает управление функции finder, которая ищет соответствующий элемент между позициями start и end вектора vec.

–  –  –

Рис. 4.1. Поиск в отсортированном векторе Простой массив не является ни расширяемым (adjustable), ни предразмещенным (displaced) и не имеет указатель заполнения (fill-pointer). По умолчанию все массивы простые. Простой вектор – это одномерный простой массив, который может содержать элементы любого типа.

Приведенная версия bin-search не работает, если ей передать объект, мень

–  –  –

Когда область поиска сокращается до одного элемента, возвращается сам элемент в случае его соответствия искомому значению obj, в противном случае – nil. Если область поиска состоит из нескольких элементов, определяется ее средний элемент – obj2 (функция round возвращает ближайшее целое число), который сравнивается с искомым элементом obj. Если obj меньше obj2, поиск продолжается рекурсивно в левой половине вектора, в противном случае – в правой половине. Остается вариант obj = obj2, но это значит, что искомый элемент найден и мы просто его возвращаем.

Если вставить следующую строку в начало определения функции finder, (format t "~A~%" (subseq vec start (+ end 1))) мы сможем наблюдать за процессом отсечения половин на каждом шаге:

(bin-search 3 #(0 1 2 3 4 5 6 7 8 9)) #(0 1 2 3 4 5 6 7 8 9) #(0 1 2 3) #(3) Договоренности о комментировании В Common Lisp все, что следует за точкой с запятой, считается комментарием. Многие программисты используют последовательно несколько знаков комментирования, разделяя комментарии по уровням: четыре точки с запятой в заглавии файла, три – в описании функции или макроса, две – для пояснения последующей строки, одну – в той же строке, что и поясняемый код. Таким образом, с использованием общепринятых норм комментирования начало кода на рис. 4.1 будет выглядеть так:

;;;; Инструменты для операций с отсортированными векторами ;;; Находит элемент в отсортированном векторе

–  –  –

4.3. Строки и знаки1 Строки – это векторы, состоящие из знаков. Строкой принято называть набор знаков, заключенный в двойные кавычки. Одиночный знак, например c, задается так: #\c.

Каждый знак соответствует определенному целому числу, как правило, (хотя и не обязательно) в соответствии с ASCII. В большинстве реализаций есть функция char-code, которая возвращает связанное со знаком число, и функция code-char, выполняющая обратное преобразование.° Для сравнения знаков используются следующие функции: char (меньше), char= (меньше или равно), char= (равно), char= (больше или равно), char (больше) и char/= (не равно). Они работают так же, как и функции сравнения чисел, которые рассматриваются на стр. 157.

(sort "elbow" #’char) "below" Поскольку строки – это массивы, то к ним применимы все операции с массивами. Например, получить знак, находящийся в конкретной позиции, можно с помощью aref:

(aref "abc" 1) #\b

Однако эта операция может быть выполнена быстрее с помощью специализированной функции char:

(char "abc" 1) #\b Функция char, как и aref, может быть использована вместе с setf для замены элементов:

(let ((str (copy-seq "Merlin"))) (setf (char str 3) #\k) str) "Merkin" Чтобы сравнить две строки, можно воспользоваться известной вам функцией equal, но есть также и специализированная string-equal, которая к тому же не учитывает регистр букв:

(equal "fred" "fred") T (equal "fred" "Fred") NIL Здесь и далее во избежание путаницы между символами в терминах Лиспа и символами-знаками, из которых состоят строки (буквами, цифрами и другими типами символов), мы будем называть последние просто «знаками».

В случае когда путаница исключена, может использоваться также более привычный термин «символ». – Прим. перев.

78 Глава 4. Специализированные структуры данных (string-equal "fred" "Fred") T В Common Lisp определен большой набор функций для сравнения и прочих манипуляций со строками. Они перечислены в приложении D, начиная со стр. 378.

Есть несколько способов создания строк. Самый общий – с помощью функции format. При использовании nil в качестве ее первого аргумента

format вернет строку, вместо того чтобы ее напечатать:

(format nil "~A or ~A" "truth" "dare") "truth or dare"

Но если вам нужно просто соединить несколько строк, можно воспользоваться concatenate, которая принимает тип результата и одну или несколько последовательностей:

(concatenate ’string "not " "to worry") "not to worry"

4.4. Последовательности Тип последовательность (sequence) в Common Lisp включает в себя списки и векторы (а значит, и строки). Многие функции из тех, которые мы ранее использовали для списков, на самом деле определены для любых последовательностей. Это, например, remove, length, subseq, reverse, sort,

every, some. Таким образом, функция, определенная нами на стр. 62, будет работать и с другими видами последовательностей:

(mirror? "abba") T Мы уже знаем некоторые функции для доступа к элементам последовательностей: nth для списков, aref и svref для векторов, char для строк.

Доступ к элементу последовательности любого типа может быть осуществлен с помощью elt:

(elt ’(a b c) 1) B Специализированные функции работают быстрее, и использовать elt рекомендуется только тогда, когда тип последовательности заранее не известен.

С помощью elt функция mirror? может быть оптимизирована для векторов:

(defun mirror? (s) (let ((len (length s))) (and (evenp len) (do ((forward 0 (+ forward 1)) (back (- len 1) (- back 1))) ((or ( forward back)

4.4. Последовательности

–  –  –

Одна из функций, которая принимает все эти аргументы, – position.

Она возвращает положение определенного элемента в последовательности или nil в случае его отсутствия.

Посмотрим на роль аргументов по ключу на примере position:

(position #\a "fantasia") (position #\a "fantasia" :start 3 :end 5) Во втором случае поиск выполняется между четвертым и шестым элементом. Аргумент :start ограничивает подпоследовательность слева, :end ограничивает справа или же не ограничивает вовсе, если этот аргумент не задан.

Задавая параметр :from-end:

(position #\a "fantasia" :from-end t) мы получаем позицию элемента, ближайшего к концу последовательности. Но позиция элемента вычисляется как обычно, то есть от начала списка (однако поиск элемента производится с конца списка).

Параметр :key определяет функцию, применяемую к каждому элементу перед сравнением его с искомым:

(position ’a ’((c d) (a b)) :key #’car) В этом примере мы поинтересовались, car какого элемента содержит a.

80 Глава 4. Специализированные структуры данных

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

(position ’(a b) ’((a b) (c d))) NIL (position ’(a b) ’((a b) (c d)) :test #’equal)

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

(position 3 ’(1 0 7 5) :test #’) С помощью subseq и position можно разделить последовательность на части. Например, функция (defun second-word (str) (let ((p1 (+ (position #\ str) 1))) (subseq str p1 (position #\ str :start p1)))) возвращает второе слово в предложении:

(second-word "Form follows function.") "follows"

Поиск элементов, удовлетворяющих заданному предикату, осуществляется с помощью position-if. Она принимает функцию и последовательность, возвращая положение первого встреченного элемента, удовлетворяющего предикату:

(position-if #’oddp ’(2 3 4 5)) Эта функция принимает все вышеперечисленные аргументы по ключу, за исключением :test.

Также для последовательностей определены функции, аналогичные member и member-if.

Это find (принимает все аргументы по ключу) и find-if (принимает все аргументы, кроме :test):

(find #\a "cat") #\a (find-if #’characterp "ham") #\h В отличие от member и member-if, они возвращают только сам найденный элемент.

Вместо find-if иногда лучше использовать find с ключом :key. Например, выражение:

(find-if #’(lambda (x) (eql (car x) ’complete)) lst)

4.5. Пример: разбор дат будет выглядеть понятнее в виде:

(find ’complete lst :key #’car) Функции remove (стр. 39) и remove-if работают с последовательностями любого типа. Разница между ними точно такая же, как между find и find-if. Связанная с ними функция remove-duplicates удаляет все повторяющиеся элементы последовательности, кроме последнего:

(remove-duplicates "abracadabra") "cdbra" Эта функция использует все аргументы по ключу, рассмотренные в таблице выше.

Функция reduce сводит последовательность в одно значение. Она принимает функцию, по крайней мере, с двумя аргументами и последовательность. Заданная функция первоначально применяется к первым двум элементам последовательности, а затем последовательно к полученному результату и следующему элементу последовательности. Последнее полученное значение будет возвращено как результат reduce.

Таким образом, вызов:

(reduce #’fn ’(a b c d)) будет эквивалентен (fn (fn (fn ’a ’b) ’c) ’d)

Хорошее применение reduce – расширение набора аргументов для функций, которые принимают только два аргумента. Например, чтобы получить пересечение трех или более списков, можно написать:

(reduce #’intersection ’((b r a d ’s) (b a d) (c a t))) (A)

4.5. Пример: разбор дат В качестве примера операций с последовательностями в этом разделе приводится программа для разбора дат. Мы напишем программу, которая превращает строку типа "16 Aug 1980" в целые числа, соответствующие дню, месяцу и году.

Программа на рис. 4.2 содержит некоторые функции, которые потребуются нам в дальнейшем. Первая, tokens, выделяет знаки из строки.

Функция tokens принимает строку и предикат, возвращая список подстрок, все знаки в которых удовлетворяют этому предикату. Приведем пример. Пусть используется функция alpha-char-p – предикат, справедливый для буквенных знаков.

Тогда получим:

(tokens "ab12 3cde.f" #’alpha-char-p 0) ("ab" "cde" "f") Все остальные знаки, не удовлетворяющие данному предикату, рассматриваются как пробельные.

82 Глава 4. Специализированные структуры данных

–  –  –

Рис. 4.2. Распознавание символов Функция constituent будет использоваться в качестве предиката для tokens. В Common Lisp к печатным знакам (graphic characters) относятся все знаки, которые видны при печати, а также пробел.

Вызов tokens с функцией constituent будет выделять подстроки, состоящие из печатных знаков:

(tokens "ab12 3cde.f gh" #’constituent 0) ("ab12" "3cde.f" "gh") На рис. 4.3 показаны функции, выполняющие разбор дат.

–  –  –

Рис. 4.3. Функции для разбора дат

4.6. Структуры Функция parse-date принимает дату, записанную в указанной форме, и возвращает список целых чисел, соответствующих ее компонентам:

(parse-date "16 Aug 1980") (16 8 1980) Эта функция делит строку на части и применяет parse-month и parseinteger к полученным частям. Функция parse-month не чувствительна к регистру, так как сравнивает строки с помощью string-equal. Для преобразования строки, содержащей число, в само число, используется встроенная функция parse-integer.

Однако если бы такой функции в Common Lisp изначально не было, нам пришлось бы определить ее самостоятельно:

(defun read-integer (str) (if (every #’digit-char-p str) (let ((accum 0)) (dotimes (pos (length str)) (setf accum (+ (* accum 10) (digit-char-p (char str pos))))) accum) nil)) Определенная нами функция read-integer показывает, как в Common Lisp преобразовать набор знаков в число. Она использует особенность функции digit-char-p, которая проверяет, является ли аргумент цифрой, и возвращает саму цифру, если это так.

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

(defun block-height (b) (svref b 0)) и так далее. Можете считать структуру таким вектором, у которого все эти функции уже заданы.

Определить структуру можно с помощью defstruct. В простейшем случае достаточно задать имена структуры и ее полей:

(defstruct point x y) Мы определили структуру point, имеющею два поля, x и y. Кроме того, неявно были заданы функции: make-point, point-p, copy-point, point-x, point-y.

84 Глава 4. Специализированные структуры данных В разделе 2.3 мы упоминали о способности Лисп-программ писать другие Лисп-программы. Это один из наглядных примеров: при вызове defstruct самостоятельно определяет все необходимые функции. Научившись работать с макросами, вы сами сможете делать похожие вещи. (Вы даже смогли бы написать свою версию defstruct, если бы в этом была необходимость.) Каждый вызов make-point возвращает вновь созданный экземпляр структуры point. Значения полей могут быть изначально заданы с помощью соответствующих аргументов по ключу:

(setf p (make-point :x 0 :y 0)) #S(POINT X 0 Y 0) Функции доступа к полям структуры определены не только для чтения полей, но и для задания значений с помощью setf:

(point-x p) (setf (point-y p) 2) p #S(POINT X 0 Y 2) Определение структуры также приводит к определению одноименного типа. Каждый экземпляр point принадлежит типу point, затем structure, затем atom и t. Таким образом, использование point-p равносильно проверке типа:

(point-p p) T (typep p ’point) T Функция typep проверяет объект на принадлежность к заданному типу.

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

(defstruct polemic (type (progn (format t "What kind of polemic was it? ") (read))) (effect nil))

Вызов make-polemic без дополнительных аргументов установит исходные значения полей:

(make-polemic) What kind of polemic was it? scathing #S(POLEMIC TYPE SCATHING EFFECT NIL)

4.7. Пример: двоичные деревья поиска Кроме того, можно управлять такими вещами, как способ отображения структуры и префикс имен функций для доступа к полям. Вот более развитый вариант определения структуры point:

(defstruct (point (:conc-name p) (:print-function print-point)) (x 0) (y 0)) (defun print-point (p stream depth) (format stream "#~A, ~A" (px p) (py p))) Аргумент :conc-name задает префикс, с которого будут начинаться имена функций для доступа к полям структуры. По умолчанию он равен point-, а в новом определении это просто p. Отход от варианта по умолчанию делает код менее читаемым, поэтому использовать более короткий префикс стоит, только если вам предстоит постоянно пользоваться функциями доступа к полям.

Параметр :print-function – это имя функции, которая будет вызываться для печати объекта, когда его нужно будет отобразить (например, в toplevel). Такая функция должна принимать три аргумента: сам объект;

поток, куда он будет напечатан; третий аргумент обычно не требуется и может быть проигнорирован1. С потоками ввода-вывода мы познакомимся подробнее в разделе 7.1. Сейчас достаточно сказать, что второй аргумент, поток, может быть передан функции format.

Функция print-point будет отображать структуру в такой сокращенной форме:

(make-point) #0,0

4.7. Пример: двоичные деревья поиска Поскольку в Common Lisp имеется встроенная функция sort, вам, скорее всего, не придется самостоятельно писать процедуры поиска. В этом разделе показано, как решить похожую задачу, для которой нет встроенной функции: поддержание набора объектов в отсортированном виде.

Мы рассмотрим метод хранения объектов в двоичном дереве поиска (BST). Сбалансированное BST позволяет искать, добавлять или удалять элементы за время, пропорциональное log n, где n – количество объектов в наборе.

BST – это бинарное дерево, в котором для каждого элемента и некоторой функции упорядочения (пусть это будет функция ) соблюдается правило: левый дочерний элемент элемента-родителя, и сам элемент В ANSI Common Lisp вы можете передавать в :print-object функцию двух па

–  –  –

правого дочернего элемента. На рис. 4.4 показан пример BST, упорядоченного с помощью функции.

Рис. 4.4. Двоичное дерево поиска Программа на рис. 4.5 содержит утилиты для вставки и поиска объектов в BST. В качестве основной структуры данных используются узлы.

Каждый узел имеет три поля: в одном хранится сам объект, в двух других – левый и правый потомки. Можно рассматривать узел как consячейку с одним car и двумя cdr.

BST может быть либо nil, либо узлом, поддеревья которого (l и r) также являются BST. Продолжим дальнейшую аналогию со списками. Как список может быть создан последовательностью вызовов cons, так и бинарное дерево может быть построено с помощью вызовов bst-insert.

Этой функции необходимо сообщить объект, дерево и функцию упорядочения.

(setf nums nil) NIL (dolist (x ’(5 8 4 2 1 9 6 7 3)) (setf nums (bst-insert x nums #’))) NIL Теперь дерево nums соответствует рис. 4.4.

Функция bst-find, которая ищет объекты в дереве, принимает те же аргументы, что и bst-insert. Аналогия со списками станет еще понятнее, если мы сравним определения bst-find и our-member (стр. 33).

Как и member, bst-find возвращает не сам элемент, а его поддерево:

(bst-find 12 nums #’) NIL (bst-find 4 nums #’) #4 Такое представление позволяет нам различать случаи, в которых искомый элемент не найден (nil) и в которых успешно найден элемент nil.

4.7. Пример: двоичные деревья поиска

–  –  –

Рис. 4.6. Двоичные деревья поиска: удаление

4.7. Пример: двоичные деревья поиска Функция bst-remove1 принимает объект, дерево и функцию упорядочения и возвращает это же дерево без заданного элемента. Как и remove,

bst-remove не модифицирует исходное дерево:

(setf nums (bst-remove 2 nums #’)) #5 (bst-find 2 nums #’) NIL Теперь дерево nums соответствует рис. 4.7. (Другой возможный случай – подстановка элемента 1 на место 2.) Рис. 4.7. Двоичное дерево поиска после удаления одного из элементов Удаление – более затратная процедура, так как под удаляемым объектом появляется незанятое место, которое должно быть заполнено одним из поддеревьев этого объекта. Этим занимается функция percolate.

Она замещает элемент дерева одним из его поддеревьев, затем замещает это поддерево одним из его поддеревьев и т. д.

Чтобы сбалансировать дерево, percolate случайным образом выбирает одно из двух поддеревьев. Выражение (random 2) вернет либо 0, либо 1, в результате (zerop (random 2)) будет истинно в половине случаев.

Теперь, когда мы преобразовали набор объектов в бинарное дерево, последовательный обход его элементов даст нам их в порядке возрастания.

Версия bst-remove, приведенная в оригинале книги, содержит баг.

Крис Стовер сообщает: «Задания (left child) node (right child) для каждого узла недостаточно. Необходимо более строгое ограничение: max(left subtree) node min(right subtree). Без него функция bst-traverse, приведенная на рис. 4.8, не обязательно перечислит элементы в порядке возрастания.

(Пример: дерево с основанием 1 имеет только правого потомка 2, а он имеет только правого потомка 0.) К счастью, функция bst-insert, представленная на рис. 4.5, корректна. С другой стороны, корректный порядок BST после применения bst-remove не гарантируется. Удаляемый внутренний узел необходимо заменять либо максимальным узлом левого поддерева, либо минимальным узлом правого поддерева, а приведенная функция этого не делает.»

В программе на рис. 4.6 данный баг уже исправлен. – Прим. перев.

90 Глава 4. Специализированные структуры данных

–  –  –

Рис. 4.8. Двоичные деревья поиска: обход Для этой цели определена функция bst-traverse (рис. 4.8), которая применяет к каждому элементу дерева функцию fn.

(bst-traverse #’princ nums) NIL (Функция princ всего лишь отображает отдельный объект.) Код, представленный в этом разделе, служит основой для реализации двоичных деревьев поиска. Вероятно, вы захотите как-то усовершенствовать его в соответствии с вашими потребностями. Например, каждый узел в текущей реализации имеет лишь одно поле elt, в то время как может оказаться полезным введение двух полей – ключ и значение.

Данная версия хотя и не поддерживает такую возможность, но позволяет ее легко реализовать.

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

Хотя вставки в очередях вполне могут быть распределены равномерно, удаления будут всегда осуществляться с конца. Это будет приводить к разбалансировке дерева, и вместо ожидаемой оценки O(log n) мы получим O(n). Кроме того, для моделирования очередей удобнее использовать обычный список просто потому, что BST будет вести себя в конечном счете так же, как и список.°

4.8. Хеш-таблицы В главе 3 было показано, что списки могут использоваться для представления множеств и отображений. Для достаточно больших массивов данных (начиная уже с 10 элементов) использование хеш-таблиц существенно увеличит производительность. Хеш-таблицу можно создать с помощью функции make-hash-table, которая не требует обязательных аргументов:

(setf ht (make-hash-table)) #Hash-Table BF0A96 Хеш-таблицы, как и функции, при печати отображаются в виде #....

4.8. Хеш-таблицы Хеш-таблица, как и ассоциативный список, – это способ ассоциирования пар объектов. Чтобы получить значение, связанное с заданным ключом, достаточно вызвать gethash с этим ключом и таблицей. По умолчанию gethash возвращает nil, если не находит искомого элемента.

(gethash ’color ht) NIL NIL

Здесь мы впервые сталкиваемся с важной особенностью Common Lisp:

выражение может возвращать несколько значений. Функция gethash возвращает два. Первое значение ассоциировано с ключом. Второе значение, если оно nil (как в нашем примере), означает, что искомый элемент не был найден. Почему мы не можем судить об этом из первого nil?

Дело в том, что элементом, связанным с ключом color, может оказаться nil, и gethash вернет его, но в этом случае в качестве второго значения – t.

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

Чтобы сопоставить новое значение какому-либо ключу, используем setf вместе с gethash:

(setf (gethash ’color ht) ’red) RED

Теперь gethash вернет вновь установленное значение:

(gethash ’color ht) RED T Второе значение подтверждает, что gethash вернул реально имеющийся в таблице объект, а не значение по умолчанию.

Объекты, хранящиеся в хеш-таблицах, могут иметь любой тип.

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

(setf bugs (make-hash-table)) #Hash-Table BF4C36 (push "Doesn’t take keyword arguments. " (gethash #’our-member bugs)) ("Doesn’t take keyword arguments. ") Так как по умолчанию gethash возвращает nil, вызов push эквивалентен setf, и мы просто кладем нашу строку на пустой список. (Определение функции our-member находится на стр. 39.) Хеш-таблицы также можно использовать вместо списков для представления множеств. Они существенно ускоряют поиск значений и их удаление в случаях больших объемов данных. Чтобы добавить элемент 92 Глава 4. Специализированные структуры данных в множество, представленное в виде хеш-таблицы, используйте setf вместе с gethash:

(setf fruit (make-hash-table)) #Hash-Table BFDE76 (setf (gethash ’apricot fruit) t) T

Проверка на принадлежность элемента множеству выполняется с помощью gethash:

(gethash ’apricot fruit) T T По умолчанию gethash возвращает nil, поэтому вновь созданная хештаблица представляет собой пустое множество.

Чтобы удалить элемент из множества, можно воспользоваться remhash:

(remhash ’apricot fruit) T Возвращая t, remhash сигнализирует, что искомый элемент был найден и успешно удален.

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

(setf (gethash ’shape ht) ’spherical (gethash ’size ht) ’giant) GIANT (maphash #’(lambda (k v) (format t "~A = ~A~%" k v)) ht) SHAPE = SPHERICAL SIZE = GIANT COLOR = RED NIL Функция maphash всегда возвращает nil, однако вы можете сохранить данные, если передадите функцию, которая, например, будет накапливать результаты в списке.

Хеш-таблицы могут накапливать любое количество вхождений, так как способны расширяться в процессе работы, когда места для хранения элементов перестанет хватать. Задать исходную емкость таблицы можно с помощью ключа :size функции make-hash-table. Используя этот параметр, вам следует помнить о двух вещах: большой размер таблицы позволит избежать ее частых расширений (это довольно затратная процедура), однако создание таблицы большого размера для малого набора данных приведет к необоснованным затратам памяти.

Важный момент:

Итоги главы параметр :size определяет не количество хранимых объектов, а количество пар ключ-значение.

Выражение:

(make-hash-table :size 5) вернет хеш-таблицу, которая сможет вместить пять вхождений до того, как ей придется расширяться.

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

По умолчанию используется eql, но также можно применить eq, equal или equalp; используемый предикат указывается с помощью ключа :test:

(setf writers (make-hash-table :test #’equal) #Hash-Table C005E6 (setf (gethash ’(ralph waldo emerson) writers) t) T Это один из компромиссов, с которым нам приходится мириться ради получения эффективных хеш-таблиц. Работая со списками, мы бы воспользовались функцией member, которой можно каждый раз сообщать различные предикаты проверки. При работе с хеш-таблицами мы должны определиться с используемым предикатом заранее, в момент ее создания.

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

Итоги главы

1. Common Lisp поддерживает массивы не менее семи размерностей.

Одномерные массивы называются векторами.

2. Строки – это векторы знаков. Знаки – это полноценные самостоятельные объекты.

3. Последовательности включают в себя списки и векторы. Большинство функций для работы с последовательностями имеют аргументы по ключу.

4. Синтаксический разбор не составляет труда в Common Lisp благодаря наличию множества полезных функций для работы со строками.

5. Вызов defstruct определяет структуру с именованными полями. Это хороший пример программы, которая пишет другие программы.

6. Двоичные деревья поиска удобны для хранения отсортированного набора объектов.

7. Хеш-таблицы – это эффективный способ представления множеств и отображений.

94 Глава 4. Специализированные структуры данных Упражнения

1. Определите функцию, поворачивающую квадратный массив (массив с размерностями (n n)) на 90 градусов по часовой стрелке:

(quarter-turn #2A((a b) (c d))) #2A((C A) (D B)) Вам потребуется array-dimensions (стр. 374).

2. Разберитесь с описанием reduce на стр. 382, затем с ее помощью определите:

(а) copy-list (b) reverse (для списков)

3. Создайте структуру для дерева, каждый узел которого помимо некоторых данных имеет трех потомков. Определите:

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

(b) функцию, принимающую объект и такое дерево и возвращающую истину, если этот объект встречается (с точки зрения eql) в поле данных хотя бы одного узла дерева.

4. Определите функцию, которая строит из BST-дерева список его объектов, отсортированный от большего к меньшему.

5. Определите bst-adjoin1. Функция работает аналогично bst-insert, однако добавляет новый объект лишь в том случае, если он отсутствует в имеющемся дереве.

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

(a) хеш-таблицу по ассоциативному списку;

(b) ассоциативный список по хеш-таблице.

В действительности, определение bst-adjoin будет эквива лентно уже имею

–  –  –

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

5.1. Блоки

В Common Lisp есть три основных оператора для создания блоков кода:

progn, block и tagbody. С первым из них мы уже знакомы. Выражения, составляющие тело оператора progn, вычисляются последовательно, при этом возвращается значение последнего:° (progn (format t "a") (format t "b") (+ 11 12)) ab Так как возвращается значение лишь последнего выражения, то использование progn (или других операторов блоков) предполагает наличие побочных эффектов.

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

return-from с соответствующим именем блока:

(block head (format t "Here we go.") 96 Глава 5. Управление (return-from head ’idea) (format t "We’ll never see this. ")) Here we go.

IDEA Вызов return-from позволяет вам внезапно, но изящно выйти из любого места в коде. Второй аргумент return-from служит в качестве возвращаемого значения из блока, имя которого передается в первом аргументе.

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

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

(block nil (return 27)) Многие операторы в Common Lisp, принимающие на вход блок кода, неявно оборачивают его в block с именем nil. В частности, так делают все итерационные конструкции:

(dolist (x ’(a b c d e)) (format t "~A " x) (if (eql x ’c) (return ’done))) ABC DONE Тело функции, создаваемой defun, является блоком с тем же именем, что и сама функция:

(defun foo () (return-from foo 27)) Вне явного или неявного block ни return, ни return-from не работают.

С помощью return-from можно написать улучшенный вариант функции

read-integer:

(defun read-integer (str) (let ((accum 0)) (dotimes (pos (length str)) (let ((i (digit-char-p (char str pos)))) (if i (setf accum (+ (* accum 10) i)) (return-from read-integer nil)))) accum)) Предыдущий вариант read-integer (стр. 83) выполнял проверку всех знаков до построения целого числа. Теперь же два шага собраны воедино, так как использование return-from позволяет прервать выполнение, когда мы встретим нечисловой знак.

Третий основной конструктор блоков, tagbody, допускает внутри себя использование оператора go. Атомы, встречающиеся внутри блока, расКонтекст цениваются как метки, по которым может выполняться переход.

Ниже приведен довольно корявый код для печати чисел от 1 до 10:

(tagbody (setf x 0) top (setf x (+ x 1)) (format t "~A " x) (if ( x 10) (go top))) NIL Оператор tagbody – один из тех, которые применяются для построения других операторов, но, как правило, не годятся для непосредственного использования. Большинство итеративных операторов построены поверх tagbody, поэтому иногда (но не всегда) есть возможноть использовать внутри них метки и переход по ним с помощью go.

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

–  –  –

(cond (99)) Если условие имеет тестовое выражение t, оно будет истинным всегда.

Этот факт удобно использовать для указания условия, которое будет выполняться в случае, когда все остальные не подошли. По умолчанию в таком случае возвращается nil, но считается плохим стилем использовать этот вариант. (Подобная проблема показана на стр. 132.)

Если вы сравниваете выражение с набором постоянных, уже вычисленных объектов, правильнее будет использовать конструкцию case. Например, мы можем воспользоваться case для преобразования имени месяца в его продолжительность в днях:

(defun month-length (mon) (case mon ((jan mar may jul aug oct dec) 31) ((apr jun sept nov) 30) (feb (if (leap-year) 29 28)) (otherwise "unknown month"))) Конструкция case начинается с выражения, значение которого будет сравниваться с предложенными вариантами. За ним следуют выражения, начинающиеся либо с ключа, либо со списка ключей, за которым следует произвольное количество выражений. Сами ключи рассматриваются как константы и не вычисляются. Значение ключа (ключей) сравнивается с оригинальным объектом с помощью eql. В случае совпадения вычисляются следующие за ключом выражения. Результатом вызова case является значение последнего вычисленного выражения.

Вариант по умолчанию может быть обозначен через t или otherwise. Если ни один из ключей не подошел или вариант, содержащий подходящий ключ, не содержит выражений, возвращается nil:

(case 99 (99)) NIL Макрос typecase похож на case, но вместо ключей использует спецификаторы типов, а искомое выражение сверяется с ними через typep вместо eql. (Пример с использованием typecase приведен на стр. 118.)

5.4. Итерации Основной итерационный оператор, do, был представлен в разделе 2.13.

Поскольку do неявным образом использует block и tagbody, внутри него можно использовать return, return-from и go.

В разделе 2.13 было указано, что первый аргумент do должен быть списком, содержащим описания переменных вида (variable initial update)

5.4. Итерации

–  –  –

Третье выражение в начальном списке будет вычислено на выходе из цикла. По умолчанию это nil.

Похожим образом действует dotimes, пробегающий для заданного числа

n значения от 0 до n–1:

(dotimes (x 5 x) (format t "~A " x)) Как и в dolist, третье выражение в начальном списке не обязательно и по умолчанию установлено как nil. Обратите внимание, что это выражение может содержать саму итерируемую переменную.

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

Она более гибка, чем dolist, потому что может выполнять итерацию параллельно сразу по нескольким спискам:

(mapc #’(lambda (x y) (format t "~A ~A " x y)) ’(hip flip slip) ’(hop flop slop))

5.5. Множественные значения

HIP HOP FLIP FLOP SLIP SLOP

(HIP FLIP SLIP) Функция mapc всегда возвращает свой второй аргумент.

5.5. Множественные значения Чтобы подчеркнуть важность функционального программирования, часто говорят, что в Лиспе каждое выражение возвращает значение. На самом деле, все несколько сложнее. В Common Lisp выражение может возвращать несколько значений или же не возвращать ни одного. Максимальное их количество может различаться в разных реализациях, но должно быть не менее 19.

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

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

Множественные значения можно возвратить с помощью функции values.

Она возвращает в точности те значения, которые были переданы ей в виде аргументов:

(values ’a nil (+ 2 4)) A NIL Если вызов values является последним в теле функции, то эта функция возвращает те же множественные значения, что и values. Множественные значения могут передаваться через несколько вызовов:

((lambda () ((lambda () (values 1 2))))) Однако если в цепочке передачи значений что-либо принимает лишь один аргумент, то все остальные будут потеряны:

(let ((x (values 1 2))) x) Используя values без аргументов, мы имеем возможность не возвращать никаких значений. Если же что-либо будет ожидать значение, будет возвращен nil.

104 Глава 5. Управление (values) (let ((x (values))) x) NIL

Чтобы получить несколько значений, можно воспользоваться multiplevalue-bind:

(multiple-value-bind (x y z) (values 1 2 3) (list x y z)) (1 2 3) (multiple-value-bind (x y z) (values 1 2) (list x y z)) (1 2 NIL) Если переменных больше, чем возвращаемых значений, лишним переменным будет присвоено значение nil. Если же значений возвращается больше, чем выделено переменных, то лишние значения будут отброшены. Таким образом, вы можете написать функцию, которая просто печатает текущее время:° (multiple-value-bind (s m h) (get-decoded-time) (format nil "~A:~A:~A" h m s)) "4:32:13"

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

(multiple-value-call #’+ (values 1 2 3))

Кроме того, есть функция multiple-value-list:

(multiple-value-list (values ’a ’b ’c)) (A B C) которая действует так же, как multiple-value-call с функцией #’list в качестве первого аргумента.

5.6. Прерывание выполнения Чтобы выйти из блока в любой момент, достаточно вызвать return. Однако иногда может потребоваться нечто более радикальное, например передача управления через несколько вызовов функций. Для этой цели существуют специальные операторы catch и throw. Конструкция catch использует метку, которой может быть любой объект. За меткой следует набор выражений.

(defun super () (catch ’abort (sub) (format t "We’ll never see this.")))

5.6. Прерывание выполнения (defun sub () (throw ’abort 99)) Выражения после метки вычисляются так же, как в progn. Вызов throw внутри любого из этих выражений приведет к немедленному выходу из

catch:

(super) Оператор throw с заданной меткой передаст управление соответствующей конструкции catch (то есть завершит ее выполнение) через любое количество catch с другими метками (соответственно «убив» их). Если нет ожидающего catch с требуемой меткой, throw вызовет ошибку.

Вызов error также прерывает выполнение, но вместо передачи управления вверх по дереву вызовов он передает его обработчику ошибок Лиспа. В результате вы, скорее всего, попадете в отладчик (break loop).

Вот что произойдет в некой абстрактной реализации Common Lisp:

(progn (error "Oops! ") (format t "After the error. ")) Error: Oops!

Options: :abort, :backtrace Более подробную информацию об ошибках и условиях можно найти в приложении A.

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

(setf x 1) (catch ’abort (unwind-protect (throw ’abort 99) (setf x 2))) x Здесь, даже несмотря на то что throw передал управление catch, второе выражение было вычислено прежде, чем был осуществлен выход из catch. В случае когда перед преждевременным завершением необходима какая-то очистка или сброс, unwind-protect может быть очень полезна. Один из таких примеров представлен на стр. 295.

106 Глава 5. Управление

5.7. Пример: арифметика над датами В некоторых приложениях полезно иметь возможность складывать и вычитать даты, например, чтобы сказать, что через 60 дней после 17 декабря 1997 года настанет 15 февраля 1998. В этом разделе мы создадим необходимые для этого инструменты. Нам потребуется конвертировать даты в целые числа, при этом за ноль будет принята дата 1 января 2000 года. Затем мы сможем работать с датами как с целыми числами, используя функции + и –. Кроме того, необходимо уметь конвертировать целое число обратно в дату.

Чтобы преобразовать дату в целое число, будем складывать количества дней, соответствующие различным компонентам даты. Например, число, соответствующее 13 ноября 2004 года, получим, складывая количество дней до 2004 года, количество дней в году до ноября и число 13.

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

(setf mon ’(31 28 31 30 31 30 31 31 30 31 30 31)) (31 28 31 30 31 30 31 31 30 31 30 31)



Pages:   || 2 | 3 | 4 |

Похожие работы:

«Руководство пользователя Приглашение на участие в конкурсе на получении стипендии ОКСФОРДСКОГО РОССИЙСКОГО ФОНДА придет на Ваш электронный адрес в виде сообщения от ***@orfdaas.ru : Здравствуйте. Вы были ус...»

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

«МУНИЦИПАЛЬНОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ДОПОЛНИТЕЛЬНОГО ОБРАЗОВАНИЯ ДЕТЕЙ "ДЕТСКАЯ ШКОЛА ИСКУССТВ" ДОПОЛНИТЕЛЬНАЯ ПРЕДПРОФЕССИОНАЛЬНАЯ ОБЩЕОБРАЗОВАТЕЛЬНАЯ ПРОГРАММА В ОБЛАСТИ М...»

«О внесении изменений и дополнений в некоторые приказы исполняющего обязанности Министра здравоохранения Республики Казахстан Приказ Министра здравоохранения и социального развития Республики Казахстан от 29 мая 2015 года № 417. Зарегистрирован в Министерстве юстиции Республики Казахстан 2 июля 2015 года № 11531 В соответствии с под...»

«Муниципальное бюджетное дошкольное образовательное учреждение 1. Настоящие Правила приёма, перевода и отчисления воспитанников МБДОУ "Детский сад общеразвивающего вида" с. Пажга (далее – Правила) разработаны в соответствии с Федеральным законом от 29 декабря 2012 года...»

«Менеджер pr должностная инструкция 25-03-2016 1 Клавиатурные словоизвержения по-фронтовому теснят ко вазочкам! Замасливший или подчеркнуто усмиренный помогает грузнеть. Розовато ожидающаяся бахнулась. раскулачивает, хотя иногда охлаждающий хирург холопско...»

«БОЖЕСТВЕННЫЕ ЛИЛЫ ДАТТАТРЕИ ИЛИ ПРАКТИКА ОСВОБОЖДЕНИЯ ДЛЯ МОНАХИНИ Начиналось все так: монахиня Наталья принесла мне сценарий для написания оперы: Сценарий спектакля "Возникновение Чистой страны Дивья Локи" ко дню рождения Дивья Локи 19 августа 2009 года Действующие лица и исполнители: Авт...»

«Департамент образования города Москвы Южное окружное управление образования Государственное образовательное учреждение СОШ№1034 Проектная деятельность Исследовательский краткосрочный проект " Огород на подоконнике" в старшей группе Подготовила и провела: воспитатель ГБОУ СО...»

«2 СОДЕРЖАНИЕ I. Общие положения..5 1. Главные события библиотечной жизни города Магнитогорска.5 II. Библиотечная сеть..6 1. Динамика библиотечной сети за три года..6 2. Реорганизация...»

«www.wipo.int/madrid/ru Сентябрь 2015 г. | No. 3/2015 СОДЕРЖАНИЕ МАДРИДСКАЯ СИСТЕМА. Знаменательное событие для международной системы регистрации товарных знаков ДОГОВАРИВАЮЩИЕСЯ СТОРОНЫ..2 Практическое значение присоединения Алж...»

«56 СУМСЬКИЙ ІСТОРИКО-АРХІВНИЙ ЖУРНАЛ. №X-ХІ. 2010 ІСТОРІОГРАФІЯ. ДЖЕРЕЛОЗНАВСТВО ДЕГТЯРЬОВ С.І. ОПИСИ СІЛ ВЕЛИКИЙ САМБІР ТА МАЛИЙ САМБІР 1760 р. У публікації подається уривок з маловідомого документа, датованого 1760 р., який містить опис сіл Великий Самбір та Малий Самбір. Зроблено короткий огляд історії цих населених пу...»

«1С-Битрикс: Управление сайтом Руководство по настройке и администрированию "1С-Битрикс: Веб-кластер" Содержание 1. Кластеризация 2. Что такое 1С-Битрикс: Веб-кластер 3. Цели и задачи, которые решает 1С-Битрикс: Веб-кластер 3.1. МАСШТАБИРОВАНИЕ ВЕБ-ПРОЕКТА, ПОВЫШЕНИЕ ПРОИЗВОДИТЕЛЬНОСТИ 3.2. Р...»

«Annotation Книга тайн Белогорья! Все секреты любимых героев раскрываются! Партия неведомых игроков в разгаре. Под сверкающим льдом Белых гор скрыты грязные секреты горных кланов. Внутри белой клетк...»

«1 Обновление ПО в OPPO Blu-ray плеере/v1.0 Обновление встроенного программного обеспечения OPPO Blu-ray плееров BDP-103D и BDP-105D. В OPPO Blu-ray плеерах BDP-103D и BDP-105D предусмотрена возможность обновления пользователем, по мере необходимости, программного обеспечения (ПО): основного ПО; загрузчика; Darbee; MCU-микроконтроллера. В OPP...»

«SDSHM136 ХАММЕРИТ СРЕДСТВО ПО БОРЬБЕ С РЖАВЧИНОЙ № 1 ПАСПОРТ БЕЗОПАСНОСТИ Пересмотрено 02/2007 1. ИДЕНТИФИКАЦИЯ ПРОДУКТА И КОМПАНИИ НАИМЕНОВАНИЕ ПРОДУКТА: Хаммерит Средство по борьбе с ржавчиной № 1...»

«ОДИННАДЦАТЫЙ АРБИТРАЖНЫЙ АПЕЛЛЯЦИОННЫЙ СУД ПОСТАНОВЛЕНИЕ от 26 января 2010 г. по делу N А72-5209/2009 Резолютивная часть постановления объявлена 19 января 2010 года. Постановление в полном объеме изготовлено 26 января 2010 года.Одиннадцатый арбитражный апелляционный суд в составе: председат...»

«Все Просто 2016 Тарифный план действует для абонентов, заключивших договор об оказании услуг связи на территории Кировской области Стоимость перехода на тарифный план в случае смены тарифного плана первый раз в месяц: 0руб. в случае смены тарифного плана во 2-й и более раз в течение месяца: 100 Минимальный авансов...»

«1 УТВЕРЖДЕН Советом директоров ОАО “Ленэнерго” Протокол от “_” _ 20 _ г. № ЕЖЕКВАРТАЛЬНЫЙ ОТЧЕТ Открытое акционерное общество энергетики и электрификации “Ленэнерго” Код эмитента: 00073А за II квартал 2004 года Место нахождения эмитента: Россия, 191186, г. Санкт-Петербург, Марсово поле, д.1 Информация, содержащаяся в настоящем ежекварталь...»

«АКАДЕМИЯ НАУК СССР И СИБИРСКОЕ ОТДЕЛЕНИЕ ТРУДЫ ИНСТИТУТА ГЕОЛОГИИ ГЕОФИЗИI-\И ВЫПУСК 604 ч. Б.' БОРУНАЕВ СТРУRТУРАДОRЕМБРИЯ И ТЕКТОНИКА ПЛИТ О'тветственнып редактор д-р геОЛ.-МШI. 'наук л. п. 30l-{еНlllайн, И 3ДАТЕЛЬСТВО НОВОСИБИРСК "Н А У К А" СИБИРСКОЕ ОТДЕЛЕНИЕ 551.21, : 551.71/.72 1-lовоспБ...»

«Электронный архив УГЛТУ У Д К 630*524.37 С. В. Соколов ОСОБЕННОСТИ ТАКСАЦИИ ЗАГАЗОВАННЫХ СОСНОВЫХ НАСАЖДЕНИЯ УРАЛА На Урале расположены крупные промышленные центры, пред­ приятия которых выбрасывают в воздух вместе с дымом большое количество токсичных соединений в виде пыли и газообразных веществ, оказывающих вредное влияние на...»

«(ГОДЪ ПЯТНАДЦАТЫЙ*) Цня годовому изданію три 5 строчки взимается за одинъ рубли съ нересмлкою и -^сзъ. ра^ъ—Д кои., за дпа раза О пересылки. Выходятъ 1 и 15 | —18 кои., за три раза—24 чиселъ каждаго мсяца. На | кон. Цна отдльныхъ ноичнечіітаніе объявленіи: за | меронъ но 15 копекъ, каждую...»

«Татьяна Николаева Проблема происхождения русского литературного языка в свете концепций европейских ученых Studia Rossica Posnaniensia 25, 207-216 STUDIA ROSSICA POSNANIENSIA, vol. XXV: 1993, pp. 207-216. ISBN 83-232-0573-6. ISSN 0081-6884. Adam Mickiewicz University Press, Pozna...»

«Мяндина Марина КИЕВСКАЯ ПРЕМЬЕРА ОПЕРЫ "РУСАЛКА" А. ДАРГОМЫЖСКОГО В КИЕВСКИХ ПЕРИОДИЧЕСКИХ ИЗДАНИЯХ (1868) Первая постановка оперы "Русалка" Даргомыжского состоялась в петербургском театре-цирке в 1856 году. Как известно, она не произвела должного впечатления на слу...»

«Общие сведения о протоколе быстрого связующего дерева (802.1w) Содержание Общие сведения Поддержка RSTP в коммутаторах Catalyst Новые состояния и функции портов Состояния портов Роли портов...»

«ЬХХХІ. Годъ ГОРІЫІ ЖУРНАЛЪ ИЗ'ДА'Ъ'АЕМ Ы Й ГОРНЫМЪ УЧЕНЫМЪ КОМИТЕТОМЪ. Т оііъ первый. М АРТЪ.СОДЕРЖАНІЕ: д у к та м и и устрой ства п ром ы ш ден ЧА СТЬ ОФ ІЩ ІАЛЬН АЯ. н ы х ъ н за в о д с к и х ъ н еф тяны хъ Узаконенія и распоряженія Правип р о д у к то въ подъ фи...»

«КОМИТЕТ ГОСУДАРСТВЕННОГО РЕГУЛИРОВАНИЯ ЦЕН И ТАРИФОВ ЧУКОТСКОГО АВТОНОМНОГО ОКРУГА ПОСТАНОВЛЕНИЕ ПРАВЛЕНИЯ от 16 мая 2017 года № 8-т/1 г. Анадырь Об установлении тарифов на услуги в морском порту, оказываемые АО "Морской ордена "...»

«International Naval Journal, 2016, Vol.(12), Is. 4 Copyright © 2016 by Academic Publishing House Researcher Published in the Russian Federation International Naval Journal Has been issued since 2013. ISSN: 2411-3204 E-ISSN: 2413-7596 Vol. 12, Is. 4, pp. 211-318, 2016 DOI: 10.13187/inj.2...»

«Спасибо, что скачали книгу в бесплатной электронной библиотеке Royallib.ru Все книги автора Эта же книга в других форматах Приятного чтения! А. К. Щербаков Wi-Fi: Все, что Вы хотели знать, н...»










 
2017 www.book.lib-i.ru - «Бесплатная электронная библиотека - электронные ресурсы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.