Готовый перевод Let Over Lambda - 50 Years of Lisp / Let Over Lambda - 50 лет Lisp-у: Глава 1 - Введение

Let Over Lambda
50 лет Lisp-у
Даг Хойт (Doug Hoyte)

Let Over Lambda
Редакция 1.0
Авторские права принадлежат Дагу Хойту (Doug Hoyte)
Все права защищены
Авторские права на код принадлежат Дагу Хойту (Doug Hoyte)
Никакие права не зарегистрированы
ISBN: 978-1-4357-1275-1
http://letoverlambda.com
doug@hcsw.org
Производство HCSW и Hoytech
Сделано на Lisp-е

1.1 Макросы

Ядро Lisp-а занимает в некотором роде локальный оптимум в пространстве языков программирования.

—Скромные слова Джона МакКарти, создателя Lisp-а

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

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

История Lisp'а более богата и обширна, нежели история других языков программирования. Над разработкой этого языка работали одни из лучших компьютерных учёных. Благодаря их трудам возник самый мощный и универсальный язык программирования. Lisp содержит много стандартов, несколько замечательных реализаций с открытым исходным кодом и макросы, с которыми не сравнятся другие языки программирования. В этой книге используется только COMMON LISP[ANSI—CL][CLTL2], но большое количество идей можно легко портировать на такие Lisp'ы, как Scheme[R5RS]. Тем не менее, ознакомившись с этой книгой, вы увидите, что для написания макросов стоит использовать COMMON LISP. В то время, когда остальные Lisp'ы хороши для других целей, COMMON LISP - это выбор профессионала, работающего с макросами.

Архитекторы COMMON LISP-а проделали замечательную работу при проектировании языка. Учитывая качество реализации COMMON LISP, на данный момент, - это лучшая среда для разработки программ с удивительно малым количеством оговорок. Как программист вы всегда можете рассчитывать на COMMON LISP и будьте уверены что в этом языке всё сделано так, как надо. Несмотря на то, что архитекторы и авторы реализаций выполнили свою работу на отлично, есть пробелы в объяснении того, почему язык реализован таким, а не другим способом. Для многих программистов COMMON LISP - это огромное коллекция непонятных особенностей, поэтому эти программисты переходят к более привычным, для них, языкам, так и не познав истинной мощи макросов. Эта книга может быть использована в качестве путеводителя по многим замечательным особенностям удивительного языка программирования - COMMON LISP. Большинство языков спроектированы так, чтобы их можно было легко реализовать; COMMON LISP спроектирован для создания мощных программ. Я искренне надеюсь, что создатели COMMON LISP оценят эту книгу как наиболее завершённый и доступный источник сведений об особенностях макросов и что эта книга будет ощутимой каплей в океан тем о макросах.

История макросов начинается почти с историей Lisp-а. Макросы изобретены Тимоти Хартом [MACRO-DEFINITIONS] в 1963 году. Тем не менее, большинство Lisp программистов не используют всю мощь макросов, а остальные программисты вообще не используют макросы. Это всегда остаётся загадкой для продвинутых лисперов. Если макросы настолько хороши, то почему их не используют все программисты? Самые умные и наиболее решительные программисты в конечном счёте приходят к макросам Лиспа. Для того, чтобы понять возможности макросов, необходимо понять что есть в Лиспе и чего нет в других языках. А это в свою очередь требует знания других, менее мощных языков. К сожалению многие программисты теряют желание учиться после того, как они освоят несколько других языков и таким образом никогда не узнают что такое макросы и их возможности. Но, несмотря на это, некоторый процент программистов задумывается над возможностью создания программ, пишущих другие программы - то есть, они приходят к макросам. А поскольку Лисп - это лучший язык для создания макросов, самые умные, самые решительные и самые любознательные программисты всегда приходят к Лиспу.

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

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

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

Указатели являются второй натурой опытного C программиста. Многие опытные C программисты считают что полное понимание указателей необходимо для правильного использования C. Поскольку указатели являются фундаментальной идеей, многие опытные C программисты не рекомендуют ограничивать использование указателей при обучении или для стилистической красоты. Несмотря на это многие новички в C считают указатели ненужным усложнением и избегают их использования, так возникает симптом FORTRAN-а (пренебрежение полезными особенностями языка). Болезнью является игнорирование особенностей языка, а не плохой программистский стиль. Если же особенности языка освоены в полном объёме, то корректный стиль программирования становится очевидным. Не нужно стремиться выработать какой-либо стиль программирования, это касается всех языков, - вспомогательная тема этой книги. Стиль нужен только в том случае, когда отсутствует понимание (Следствие этого - эффективное использование чего-либо только одним, подсмотренным где-либо, способом при отсутствии должного понимания природы вещей).

Подобно указателям C, макросы - это особенность Лиспа, которая часто остаётся плохо понятой, и поэтому распространены не совсем верные представления о макросах. Если при работе с макросами вы полагаетесь на такие высказывания как:

Макросы изменяют синтаксис Лисп кода.

Макросы работают в дереве разбора ваших программ.

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

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

Хорошие справочники и руководства по макросам можно пересчитать по пальцам. Одним из хороших книг по макросам является книга Пола Грэма On Lisp [On-Lisp]. Рекомендуется к прочтению от корки до корки всем, кто интересуется макросами. On Lisp и остальные труды Грэма послужили толчком к написанию книги, которую вы сейчас читаете. Благодаря Полу Грэму и остальным людям, писавшим о Лиспе, мощь макросов широко обсуждается, но, к сожалению, всё же остаётся также широко не понятой. Несмотря на то, что просто прочитав книгу On Lisp можно узнать много интересного о макросах, некоторые программисты связывают проблемы программирования с макросами. В то время, когда On Lisp показывает вам различные виды макросов, эта книга расскажет вам как использовать эти макросы.

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

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

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

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

Эта книга не только о теории. Все примеры, приведённые здесь, полностью функциональны, пригодны для использования и могут помочь вам улучшить ваше программирование здесь и сейчас. Эта книга о применении передовых программистских технологий для улучшения вашего программирования. Во многих книгах посвящённых программированию сознательно применяется простой стиль программирования в угоду доступности. В этой книге материал преподаётся с полным применением всего языка. Кроме этого приведённые примеры кода используют эзотерические особенности COMMON LISP, большинство из которых будут описываться при использовании. Если вы прочитали и поняли (Конечно, вы можете не соглашаться с этим утверждением.) всё, что описано в главе 2, Замыкания и в главе 3, Основы Макросов, то можете считать что вы прошли среднюю стадию понимания Лиспа.

Одной из частей Лиспа является самостоятельные открытия, эта книга не лишит вас удовольствия от экспериментов. Имейте в виду, что материал в этой книге подаётся очень быстро, много быстрее, чем вы сможете усвоить. Для того, чтобы понять некоторые участки кода, приведённые здесь, вам придётся обращаться к другим справочникам и руководствам по COMMON LISP'у. После изучения базовых понятий мы перейдём прямо к последним исследованиям, посвящённым макросам, большинство из которых граничат с большой неизведанной областью. Эта книга фокусируется на комбинировании макросов. Эта тема имеет пугающую репутацию, а хорошо понять эту тему способны не все программисты. Комбинирование макросов включает в себя наиболее обширные и плодородные исследования в языках программирования. Исследователями было выжато почти всё из типов, объектов и пролого-подобной логики, но программирование макросов остаётся огромной, зияющей чёрной дырой. Никто не знает до конца что лежит по ту сторону. Всё, что мы знаем на данный момент - это то, что макросы сложны, пугающи и проявляют неограниченный потенциал. В отличие от многих программистских идей макросы не являются ни академической концепцией для производства бесполезных теоретических публикаций, ни пустым модным словом относящемуся к программному обеспечению компаний. Макросы - это лучшие друзья хакеров. Макросы делают ваши программы умнее, а не труднее. Большинство программистов, начавших изучение макросов приходят к выводу что программирование без макросов - это не программирование.

Многие книги посвящённые Лиспу написаны в пропагандистском ключе, но я совершенно равнодушно отношусь к публичным призывам использовать Лисп. Лисп не собирается уходить. Я был бы счастлив если бы мог использовать Лисп в качестве секретного оружия на протяжении всей своей карьеры программиста. Эта книга имеет только одну цель - вдохновить на изучение и исследование, также, как я был вдохновлён On Lisp'ом. Я надеюсь, что смогу вдохновить читателей этой книги и смогу насладиться ещё более лучшими Лисповскими макро инструментами и ещё более интересными книгами о макросах Лиспа.

Да пребудет с вами сила Лиспа,

ваш покорный автор,

Даг Хойт.

1.2 U-Язык

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

Никто не понимает этого лучше, чем Хаскелл Карри, автор Основ Математической Логики [FOUNDATIONS]. Карри, который пытался не просто формализовать идеи, а формализовать ещё и само выражение идей, посчитал необходимым абстрагировать эту концепцию в коммуникативный язык между писателем и читателем. Он назвал его U-Язык (U-Language).

Листинг 1.1: ПРИМЕР-ЛИСТИНГА-ПРОГРАММЫ
(defun example-program-listing ()
’(this is
(a (program
(listing)))))

Каждое исследование, включая эту книгу, должны передаваться от одного человека к другому через язык. Целесообразно начать наше обучение обратив внимание на тот очевидный факт, что нужно дать некоторое имя нашему языку и явно обозначить его функции. Мы будем называть наш используемый язык U-Языком. Если бы язык не был так тесно связан с нашей работой, то можно было бы не уделять ему такого внимания.

На протяжении всей книги мы будем вводить новые ключевые концепции или будем обращать внимание на какой-либо момент вот таким шрифтом. При цитировании специальных форм, функций, макросов и других идентификаторов присутствующих в уже встреченных или ещё не описанных программах, мы будем использовать этот специальный шрифт (учтите что некоторые слова имеют множественные значения, например макрос lambda в COMMON LISP и концепция лямбда; специальная форма let и список форм).

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

(this is
(demonstration code))

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

Поскольку Лисп имеет интерактивную природу, результат вычисления простого выражения часто передаёт больше чем соответствующее количество информации в U-Языке. В этих случаях мы будем применять вывод из COMMON LISP'овского Прочитать Вычислить Напечатать Повторить (Read Evaluate Print Loop - сокращается до REPL):

* (это
(выражение
(для вычисления)))
ЭТО-РЕЗУЛЬТАТ

Обратите внимание: текст кода введён в нижнем регистре, а текст возвращённый Лиспом в верхнем регистре. Эта особенность COMMON LISP, что позволяет нам легко вычленять вывод REPL от введённых выражений. Точнее, эта особенность позволит нам быстро просматривать Лисп формы, содержащие символы - в каком-либо файле или экране - и сразу узнать во что они были вычислены Лисп считывателем. Кроме того, заметьте, что в приглашении присутствует символ астериска (*). Этот символ идеален, поскольку его нельзя перепутать со сбалансированным символом и его начертание позволяет быстро определить его в сессии REPL.

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

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

Язык без Лисп макросов называется Блаб.

Слово Блаб в U-Язык пришло из эссе Пола Грэма, Побеждая Посредственность [BEATING-AVGS], где Блаб - это гипотетический язык, используемый для выделения того факта, что Лисп отличается от других языков: Лисп - другой. Блаб характеризуется инфиксным синтаксисом, раздражающей системой типов, увечной объектной системой, но самая главная черта, объединяющая Блаб языки - это отсутствие Лисп макросов. Ещё одна полезная сторона Блаба - в том, что простейший способ изучения продвинутой технологии макросов - это рассмотрение причин по которой макросы невозможно использовать в Блабе. Цель Блаб терминологии не в издевательствах над не Лисп языками (Хотя в этом есть доля юмора).

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

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

Листинг 1.2: ПРИМЕР-ИТЕРАТИВНОГО-ПРОЦЕССА
(defun example-function% () ; первая версия
t)
(defun example-function%% () ; вторая версия
t)
(defun example-function () ; финальная версия!
1:)

Мы можем продолжить формировать иерархию языков с любым числом уровней. Однако, вне зависимости от количества уровней U-Язык будет находиться на самом высоком уровне: если есть два уровня, то это будет мета-язык; если есть три уровня, то будет мета-мета-язык; и т.д. Таким образом термины U-Языка и мета-языка должны различаться.

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

1.3 Утилита Lisp

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

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

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

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

Листинг 1.3: MKSTR-SYMB
(defun mkstr (&rest args)
(with-output-to-string (s)
(dolist (a args) (princ a s))))
(defun symb (&rest args)
(values (intern (apply #’mkstr args))))

По совету из книги On Lisp, книга, которую вы сейчас читаете спроектирована как ещё один слой луковицы. Так же, как одни программы представляют слой над другими программами, эта книга базируется на On Lisp. Это центральная тема книги Грэма: при сочетании хорошо спроектированных утилит общая производительность может быть больше суммы производительностей каждой утилиты. Этот раздел описывает коллекцию полезных утилит. Кроме утилит из On Lisp в этот раздел вошли ещё и сторонние утилиты.

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

Group - это другая утилита, постоянно всплывающая при написании макросов. Отчасти это связано с необходимостью в таких отражающих операторах как COMMON LISP'овские setf и psetf, группирующими аргументы, а отчасти и с тем, что часто группировка - это наилучший путь структурирования связанных данных. Поскольку мы будем очень часто использовать эту функциональность, то эту абстракцию нужно сделать как можно более универсальной. Group Грэма группирует все предоставленное количество групп, определённое в параметре n. В отличие от setf, где аргументы группируются в пары, а n равно 2.

Flatten - одна из наиболее важных утилит в On Lisp. Получает вложенную списковую структуру и возвращает новый список, содержащий списковую структуру всех атомов из начального списка. Если же мы будем думать о списковой структуре как о дереве, то flatten будет возвращать список всех листьев дерева. Если дерево представляет Лисп код, то выполняя некоторую проверку присутствующих объектов в выражении, flatten будет представлять из себя некоторую разновидность прохода-по-коду (code-walking) - тема рекурсии, проходящая через всю книгу.

Листинг 1.4: GROUP
(defun group (source n)
(if (zerop n) (error "zero length"))
(labels ((rec (source acc)
(let ((rest (nthcdr n source)))
(if (consp rest)
(rec rest (cons
(subseq source 0 n)
acc))
(nreverse
(cons source acc))))))
(if source (rec source nil) nil)))

Листинг 1.5: FLATTEN
(defun flatten (x)
(labels ((rec (x acc)
(cond ((null x) acc)
((atom x) (cons x acc))
(t (rec
(car x)
(rec (cdr x) acc))))))
(rec x nil)))

Листинг 1.6: FACT-AND-CHOOSE
(defun fact (x)
(if (= x 0)
1
(* x (fact (- x 1)))))

(defun choose (n r)
(/ (fact n)
(fact (- n r))
(fact r)))

Fact и choose - это очевидные реализации функций факториала и биномиального коэффициента.

1.4 Лицензия

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

;; Это исходный код для книги
;; _Let_Over_Lambda_ за авторством Дага Хойта.
;; Правообладателем кода является Даг Хойт. 2002-2008 годы.
;;

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

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

Текст этой книги принадлежит Дагу Хойту. 2008 год. Все права защищены.

1.5 Благодарности

Брайан Хойт (Brian Hoyte), Нэнси Холмс (Nancy Holmes), Розали Холмс (Rosalie Holmes), Ян (Ian), Алекс (Alex) и вся остальная моя семья; syke, madness, fyodor, cyb0rg/asm, theclone, blackheart, d00tz, rt, magma, nummish, zhivago, defrost; Майк Конрой (Mike Conroy), Сильвия Рассел (Sylvia Russell), Алан Пэт (Alan Paeth), Роб МакАртур (Rob McArthur), Сильви Десярдинс (Sylvie Desjardins), Джон МакКарти (John McCarthy), Пол Грэм (Paul Graham), Дональд Кнут (Donald Knuth), Лео Броди (Leo Brodie), Брюс Шнайер (Bruce Schneier), Ричард Столлман (Richard Stallman), Эди Вейтз (Edi Weitz), Питер Норвиг (Peter Norvig), Питер Сибель (Peter Seibel), Кристиан Куиннек (Christian Queinnec), Кейт Бостик (Keith Bostic), Джон Гэмбл (John Gamble); проектировщики и создатели COMMON LISP, особенно Гай Стил (Guy Steele), Ричард Гэбриел (Richard Gabriel) и Кент Питман (Kent Pitman), разработчики и сопроводители CMUCL/SBCL, CLISP, OpenBSD, GNU/ Linux.

Отдельная благодарность Яну Хойту (Ian Hoyte) за дизайн обложки и Лео Броди (Leo Brodie) за картинку на обороте обложки.

Эта книга предназначена всем, кто любит программирование.

Переведено на Нотабеноиде
http://notabenoid.org/book/40014/148998

Переводчики: Charlz_Klug