The Little Schemer: чудесное функциональное программирование

Первая заповедь 
При рекурсивном обходе списка атомов lat задавайте два вопроса: (null? 
lat) и else. 
При рекурсивном обходе числа n 
задавайте два вопроса: (zero? n) и else.
При рекурсивном обходе списка 
S-выражений l задавайте три вопроса: 
(null? l), (atom? (car l))  и else.
Вторая заповедь
Используйте cons для создания списка.
Третья заповедь
Конструируя список, опишите первый 
элемент, который должен быть помещен в результат, а затем добавьте его 
с помощью cons в результат рекурсивного вызова.
Четвертая заповедь
Выполняя рекурсивный вызов, всегда 
изменяйте хотя бы один аргумент. При 
рекурсивном обходе списка атомов 
lat используйте (cdr lat). При рекурсивном обходе числа n используйте (sub1 
n). При рекурсивном обходе списка 
S-выражений l используйте (car l) и 
(cdr l), если ни (null? l), ни (atom? (car l)) 
не дали истинного значения.
Изменения 
должны 
приближать 
выполнение 
условия 
завершения. 
Изменяемый аргумент должен проверяться в условии завершения: 
• при использовании cdr проверяйте 
условие завершения с помощью 
null?;
• при 
использовании 
sub1 
проверяйте условие завершения 
с помощью zero?.
Пятая заповедь
Конструируя значение с помощью, 
всегда используйте 0 как значение, 
возвращаемое 
строкой 
проверки 
условия завершения рекурсии, потому что прибавление 0 не изменяет 
результата операции сложения.
Конструируя значение с помощью, 
всегда используйте 1 как значение, 
возвращаемое 
строкой 
проверки 
условия завершения рекурсии, потому что умножение на 1 не изменяет 
результата операции умножения.
Конструируя значение с помощью 
cons, всегда используйте () как значение, возвращаемое строкой проверки 
условия завершения рекурсии.
Шестая заповедь
Упрощайте, только добившись правильной работы функции.
Седьмая заповедь
Выполняйте 
рекурсивный 
обход 
частей, имеющих одинаковую природу:
• 
подсписков в списках;
• 
подвыражений в 
арифметических 
выражениях.
Восьмая заповедь
Используйте вспомогательные функции для абстрагирования от представлений.
Девятая заповедь
Абстрагируйте общие шаблоны, определяя новые функции.
Десятая заповедь
Создавайте 
функции 
для 
сбора 
нескольких значений за один раз.

Дэниел П. Фридман, Маттиас Феллейзен
The Little Schemer: 
чудесное функциональное 
программирование

The Little Schemer
Fourth Edition
Daniel P. Friedman
Indiana University
Bloomington, Indiana
Matthias Felleisen
Rice University
Houston, Texas
Drawings by Duane Bibby
Foreword by Gerald J. Sussman
The MIT Press
Cambridge, Massachusetts
London, England

The Little Schemer: 
чудесное функциональное 
программирование
Дэниел П. Фридман
Университет штата Индиана, 
Блумингтон, Индиана
Маттиас Феллейзен
Университет Райса
Хьюстон, Техас
Рисунки Дуэйна Бибби
Предисловие Джеральда Дж. Сассмана
Москва, 2024

УДК  004.04
ББК  32.372
         Ф82
Дэниел П. Фридман, Маттиас Феллейзен
Ф82	
The Little Schemer: чудесное функциональное программирование. – 
М.: ДМК Пресс, 2024. – 230 с.: ил.
ISBN 978-5-93700-234-1
The Little Schemer – не просто введение в функциональное программирование, это захватывающее исследование самих принципов 
вычислительного мышления. Книга проводит читателя через тонкости рекурсивного программирования, представляя материал в удобном для восприятия табличном формате («вопрос–ответ»).
Это незаменимое руководство для тех, кто стремится не только 
уметь понимать код, но и мыслить в нем и перестраивать его, выходя за рамки обыденного программирования и погружаясь в более 
абстрактный мир вычислений.
@ MIT Press. Права на русское издание получены через агентство Александра 
Корженевского. 
Все права защищены. Любая часть этой книги не может быть воспроизведена в 
какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав.
Материал, изложенный в данной книге, многократно проверен. Но поскольку вероятность технических ошибок все равно существует, издательство не может гарантировать 
абсолютную точность и правильность приводимых сведений. В связи с этим издательство 
не несет ответст-венности за возможные ошибки, связанные с использованием книги.
ISBN 978-0-26256-099-2
© Massachusetts Institute of Technology, 1996
ISBN 978-5-93700-234-1
© Оформление, перевод, издание, ДМК Пресс, 2024

Посвящается 
Марии, Хельге и нашим детям

Оглавление
Предисловие............................................................................................ 8
Вступление............................................................................................. 10
Что нужно знать, чтобы читать эту книгу..........................................................11
Благодарности.............................................................................................................11
Примечание для читателей....................................................................................12
1. Игрушки.............................................................................................. 15
Правило Car’a..............................................................................................................19
Правило Cdr’a..............................................................................................................20
Правило Cons’a...........................................................................................................22
Правило Null?..............................................................................................................23
Правило Eq?..................................................................................................................25
2. Сделай это, сделай это снова, и снова, и снова............................ 27
Первая заповедь (предварительная версия)...................................................38
3. Cons великолепный.......................................................................... 49
Вторая заповедь..........................................................................................................54
Третья заповедь...........................................................................................................63
Четвертая заповедь (предварительная версия).............................................76
4. Игры с числами................................................................................. 77
Первая заповедь (первая редакция)....................................................................83
Четвертая заповедь (первая редакция)..............................................................84
Пятая заповедь............................................................................................................86
5. *Б_же мой*: сколько звёзд!............................................................. 99
Первая заповедь (окончательный вариант).................................................102
Четвертая заповедь (окончательный вариант)...........................................104
Шестая заповедь.......................................................................................................116
6. Тени...................................................................................................119
Седьмая заповедь.....................................................................................................126
Восьмая заповедь.....................................................................................................130
7. Друзья и отношения.......................................................................133

Оглавление
8. Lambda повсюду.............................................................................149
Девятая заповедь.....................................................................................................160
Десятая заповедь......................................................................................................167
9. ...И снова, и снова, и снова............................................................175
10. Какова ценность всего этого?....................................................203
Антракт.................................................................................................225
Алфавитный указатель.......................................................................227

Предисловие
Это предисловие появлялось во втором и третьем изданиях книги «The Little LlSPer» (предшествовавшей «The Little Schemer»). 
Мы цитируем его здесь с разрешения автора.
В 1967 году я посещал вводные занятия по фотографии. Большинство 
слушателей (включая меня) записались на этот курс в надежде 
научить-ся художественной фотографии, и делать такие же восхитительные снимки, как известный художник Эдвард Уэстон (Edward 
Weston). В первый день преподаватель терпеливо огласил длинный 
список технологических навыков, которым он собирался обучить 
нас в течение семестра. Ключевым из них была «Зонная система» 
Анселя Адамса (Ansel Adams) – методика определения оптимальной 
экспозиции в фотографии, параметров лабораторной обработки 
полученного снимка (черноты на конечном отпечатке) и их зависимости от освещенности сцены. В дополнение к этому мы должны были научиться пользоваться экспонометрами для измерения 
уровня освещенности и определять время экспозиции и обработки 
в проявителе для контроля уровня черного и контраста изображения. Для этого, в свою очередь, мы должны были научиться заряжать 
пленку, смешивать химикаты и печатать снимки. А чтобы постоянно получать стабильные результаты – изучить правила обращения 
со светочувствительными материалами. На первом лабораторном 
занятии мы выяснили, что проявитель скользкий на ощупь, а фиксаж ужасно пахнет.
А где же творчество в композиции? Чтобы начать творить, необходимо сначала освоить инструменты для съёмки. Невозможно 
создать отличную фотографию без навыков, позволяющих это сделать. В инженерном деле, как и в других областях творчества, мы 
должны научиться анализировать, чтобы начать творить. Нельзя 
построить красивый и надежный мост, не имея знаний о свойствах 
сталей и грунтов и не владея математическим аппаратом для вычисления свойств конструкций. Точно так же нельзя построить красивую компьютерную систему, порождаемую написанными процедурами, не понимая процесса «печати снимков».
Некоторые фотографы предпочитают использовать черно-белые 
пластины 8×10, другие – фотопленку шириной 35 мм. И те, и другие 
имеют свои преимущества и недостатки. Как и в фотоделе, в про

Предисловие
граммировании требуется выбрать инструменты. Многие выбирают 
язык Lisp за его свободный стиль и гибкость. Lisp изначально задумывался как теоретическое средство для развития теории рекурсии 
и символьной алгебры. В дальнейшем он превратился в уникальный, мощный и гибкий инструмент разработки программного обеспечения, позволяющий быстро создавать прототипы программных 
систем. Как и другие языки, Lisp предлагает обширную библиотеку 
готовых процедур, созданных сообществом пользователей. В Lisp 
процедуры являются обычными данными первого класса, которые 
можно передавать в виде аргументов, возвращать и хранить в структурах данных. Такая гибкость очень ценна, но самое главное – она 
обеспечивает механизмы формализации, именования и сохранения идиом – общих шаблонов использования, составляющих основу 
инженерного проектирования. Кроме того, программы на Lisp способны манипулировать представлениями программ на Lisp. Это его 
свойство способствовало развитию обширного комплекса инструментов синтеза и анализа программ, таких как источники перекрестных ссылок.
Книга «Little LISPer» – это уникальный подход к развитию навыков, лежащих в основе творческого программирования на Lisp. В ней 
просто и остроумно изложены теория и практика, необходимые для 
овладения навыками построения рекурсивных процессов и манипулирования рекурсивными структурами данных. Для изучающих 
программирование на Lisp книга «Little LISPer» может оказать такую 
же услугу, как упражнения Ханона (Hanon) для пальцев или фортепианные этюды Черни (Czerny) для обучающихся игре на фортепиано.
Джеральд Дж. Сассман (Gerald J. Sussman)
Кембридж, Массачусетс