Автор: Фридман Д.П. Феллейзен М.
Теги: ориентация процесса обработки данных радиоэлектроника программирование
ISBN: 978-5-93700-234-1
Год: 2024
Текст
Первая заповедь
Пятая заповедь
При рекурсивном обходе списка атомов lat задавайте два вопроса: (null?
lat) и else.
При рекурсивном обходе числа n
задавайте два вопроса: (zero? n) и else.
При рекурсивном обходе списка
S-выражений l задавайте три вопроса:
(null? l), (atom? (car l)) и else.
Конструируя значение с помощью,
всегда используйте 0 как значение,
возвращаемое строкой проверки
условия завершения рекурсии, потому что прибавление 0 не изменяет
результата операции сложения.
Конструируя значение с помощью,
всегда используйте 1 как значение,
возвращаемое строкой проверки
условия завершения рекурсии, потому что умножение на 1 не изменяет
результата операции умножения.
Конструируя значение с помощью
cons, всегда используйте () как значение, возвращаемое строкой проверки
условия завершения рекурсии.
Вторая заповедь
Используйте cons для создания списка.
Третья заповедь
Конструируя список, опишите первый
элемент, который должен быть помещен в результат, а затем добавьте его
с помощью cons в результат рекурсивного вызова.
Четвертая заповедь
Выполняя рекурсивный вызов, всегда
изменяйте хотя бы один аргумент. При
рекурсивном обходе списка атомов
lat используйте (cdr lat). При рекурсивном обходе числа n используйте (sub1
n). При рекурсивном обходе списка
S-выражений l используйте (car l) и
(cdr l), если ни (null? l), ни (atom? (car l))
не дали истинного значения.
Изменения
должны
приближать
выполнение условия завершения.
Изменяемый аргумент должен проверяться в условии завершения:
• при использовании cdr проверяйте
условие завершения с помощью
null?;
• при
использовании
sub1
проверяйте условие завершения
с помощью zero?.
Шестая заповедь
Упрощайте, только добившись правильной работы функции.
Седьмая заповедь
Выполняйте
рекурсивный
обход
частей, имеющих одинаковую природу:
•
•
подсписков в списках;
подвыражений в
арифметических
выражениях.
Восьмая заповедь
Используйте вспомогательные функции для абстрагирования от представлений.
Девятая заповедь
Абстрагируйте общие шаблоны, определяя новые функции.
Десятая заповедь
Создавайте функции для сбора
нескольких значений за один раз.
Дэниел П. Фридман, Маттиас Феллейзен
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
ISBN 978-5-93700-234-1
© Massachusetts Institute of Technology, 1996
© Оформление, перевод, издание, ДМК Пресс, 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
Оглавление
7
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 мм. И те, и другие
имеют свои преимущества и недостатки. Как и в фотоделе, в про-
Предисловие
9
граммировании требуется выбрать инструменты. Многие выбирают
язык Lisp за его свободный стиль и гибкость. Lisp изначально задумывался как теоретическое средство для развития теории рекурсии
и символьной алгебры. В дальнейшем он превратился в уникальный, мощный и гибкий инструмент разработки программного обеспечения, позволяющий быстро создавать прототипы программных
систем. Как и другие языки, Lisp предлагает обширную библиотеку
готовых процедур, созданных сообществом пользователей. В Lisp
процедуры являются обычными данными первого класса, которые
можно передавать в виде аргументов, возвращать и хранить в структурах данных. Такая гибкость очень ценна, но самое главное – она
обеспечивает механизмы формализации, именования и сохранения идиом – общих шаблонов использования, составляющих основу
инженерного проектирования. Кроме того, программы на Lisp способны манипулировать представлениями программ на Lisp. Это его
свойство способствовало развитию обширного комплекса инструментов синтеза и анализа программ, таких как источники перекрестных ссылок.
Книга «Little LISPer» – это уникальный подход к развитию навыков, лежащих в основе творческого программирования на Lisp. В ней
просто и остроумно изложены теория и практика, необходимые для
овладения навыками построения рекурсивных процессов и манипулирования рекурсивными структурами данных. Для изучающих
программирование на Lisp книга «Little LISPer» может оказать такую
же услугу, как упражнения Ханона (Hanon) для пальцев или фортепианные этюды Черни (Czerny) для обучающихся игре на фортепиано.
Джеральд Дж. Сассман (Gerald J. Sussman)
Кембридж, Массачусетс
Вступление
В честь двадцатой годовщины создания Scheme мы в третий раз
переработали содержимое книги «The Little LISPer», дали ей более
точное название «The Little Schemer» и написали продолжение:
«The Seasoned Schemer».
Программы принимают и генерируют данные. Разработка программы требует глубокого понимания данных; хорошая программа отражает форму данных, с которыми она работает. Большинство
коллекций данных, а значит, и большинство программ, являются
рекурсивными. Рекурсия – это способ определения объекта или
решения задачи в терминах самого себя.
Цель этой книги – научить читателя мыслить рекурсивно. Наша
первая задача – решить, какой язык использовать для передачи этой
идеи. Есть три очевидных варианта: естественный язык, например
русский, формальная математика или язык программирования.
Естественные языки неоднозначны, неточны и иногда излишне
многословны. Они отлично подходят для рассуждений на общие
темы, но не подходят для краткого описания такой точной концепции, как рекурсия. Язык математики, в противоположность естественному языку, способен выражать мощные формальные идеи всего
несколькими символами. Но, к сожалению, язык математики часто
трудно понять без специальной подготовки. Сочетание технологии
и математики дает нам третий, почти идеальный вариант: язык программирования. Мы считаем, что языки программирования лучше
всего подходят для объяснения сути рекурсии. Они, как и язык математики, способны придавать формальное значение набору символов. Но, в отличие от языка математики, языки программирования
позволяют экспериментировать – вы сможете ввести программы
из этой книги в свой компьютер и понаблюдать за их поведением,
изменить их и посмотреть, какой эффект оказывают эти изменения.
Пожалуй, лучшим языком программирования для изучения
рекурсии является Scheme. Scheme поддерживает символьные
вычисления – программисту не нужно думать о связи между символами своего языка и их представлением в компьютере. Рекурсия
является естественным вычислительным механизмом в Scheme, а
основной задачей программиста является создание (потенциально)
рекурсивных определений. Реализации Scheme преимуществен-
Благодарности
11
но интерактивны – программист может писать программы и сразу
же наблюдать за их поведением. И что особенно важно для наших
уроков в конце этой книги, существует прямое соответствие между
структурами программ на Scheme и данными, которыми эти программы манипулируют.
Язык Scheme можно описать достаточно формально, но для
его понимания не требуется особой математической подготовки. Фактически книга «The Little Schemer» основана на конспектах
лекций двухнедельного краткого введения в Scheme: для студентов
без опыта программирования и с нелюбовью ко всему математическому. Многие из этих студентов готовились к карьере на государственных должностях. Мы считаем, что написание рекурсивных
программ на языке Scheme – это, по сути, простое распознавание
закономерностей. Поскольку нас интересует только рекурсивное
программирование, мы ограничиваемся рассмотрением причинноследственного устройства всего лишь нескольких функций языка
Scheme: car, cdr, cons, eq?, null?, zero?, addl, subl, number?, and, or, quote, lambda,
define и cond. По сути наш язык – это идеализированный язык Scheme.
Книги «The Little Schemer» и «The Seasoned Schemer» не являются
введением в практику программирования, но овладение концепциями, представленными в этих книгах, дает начало к пониманию
природы вычислений.
Что нужно знать, чтобы читать эту книгу
Читатель должен уметь читать, распознавать цифры и считать.
Благодарности
Мы благодарны многим людям за их помощь, которую они оказывали в процессе работы над вторым и третьим изданиями этой
книги. Мы благодарим Брюса Дуба (Bruce Duba), Кента Дибвига (Kent
Dybvig), Криса Хейнса (Chris Haynes), Юджина Колбекера (Eugene
Kohibecker), Ричарда Салтера ( Richard Salter), Джорджа Спрингера
(George Springer), Митча Уанда (Mitch Wand) и Дэвида С. Уайза (David
S. Wise) за многочисленные пояснения, повлиявшие на наше мышление при создании нашей книги. Гассан Аббас (Ghassan Abbas),
Чарльз Бейкер (Charles Baker), Дэвид Бойер (David Boyer), Майк Данн
(Mike Dunn), Терри Фалькенберг (Terry Falkenberg), Роб Фридман
(Rob Friedman), Джон Гейтли (John Gateley), Майер Голдберг (Mayer
Goldberg), Икбал Хан (Iqbal Khan), Джулия Лоуолл (Julia Lawall),
Джон Мендельсон (Jon Mendelsohn), Джон Ниенарт (John Nienart),
Джеффри Д. Перотти (Jeffrey D. Perotti), Эд Робертсон (Ed Robertson),
12
Вступление
Энн Шпунтофф (Anne Shpuntoff), Эрих Смайт (Erich Smythe), Гай
Стил (Guy Steele), Тодд Стайн (Todd Stein) и Ларри Вайссельберг (Larry
Weisselberg) дали множество ценных замечаний к рукописи книги.
Мы выражаем особую благодарность Бобу Филману (Bob Filman)
за его бескомпромиссную критику на протяжении нескольких этапов. Наконец, мы выражаем признательность Нэнси Гарретт (Nancy
Garrett), Пег Флетчер (Peg Fletcher) и Бобу Филману (Bob Filman) за
вклад в дизайн и оформление в формате TEX.
В работе над четвертым и последним изданием нам очень помог
ла невероятно умная программа Дорай Ситарам (Dorai Sitaram) для
набора текста на языке Scheme– SLATEX. Программа Chez Scheme
Кента Дибвига (Kent Dybvig) сделала программирование на Scheme
очень приятным занятием. Мы благодарны за критику и предложения Шеласвау Бушуэллу (Shelaswau Bushnell), Ричарду Коббу
(Richard Cobbe), Дэвиду Комбсу (David Combs), Питеру Дрейку (Peter
Drake), Кенту Дибвигу (Kent Dybvig), Робу Фридману (Rob Friedman),
Стиву Ганцу (Steve Ganz), Крису Хейнсу (Chris Haynes), Эрику
Хилсдейлу (Erik Hilsdale), Юджину Кольбекеру (Eugene Kohlbecker),
Шрираму Кришнамурти (Shriram Krishnamurthi), Джулии Лоуолл
(Julia Lawall), Сюзанне Мензел (Suzanne Menzel), Коллину МакКарди
(Collin McCurdy), Джону Ниенарту (John Nienart), Джону Росси (Ion
Rossie), Джонатану Собелу (Jonathan Sobel), Джорджу Спрингеру
(George Springer), Гаю Стилу (Guy Steele), Джону Дэвиду Стоуну
(John David Stone), Викраму Субраманиаму (Vikram Subramaniam),
Митчу Ванду (Mitch Wand) и Мелиссе Вингард-Филлипс (Melissa
Wingard-Phillips).
Примечание для читателей
Не торопитесь, читайте эту книгу вдумчиво; по всему ее тексту
разбросаны ценные советы. Не стремитесь прочитать книгу в три
приема. Читайте систематически. Если вы не до конца поняли одну
главу, то следующую вы поймете еще меньше. Вопросы расположены в порядке возрастания сложности: вам будет трудно ответить на
последующие вопросы, не зная ответов на предшествующие.
Книга организована как диалог, который мы с вами могли бы
вести, обсуждая примеры программ на Scheme. Если есть возможность, поэкспериментируйте со встречающимися в процессе чтения примерами.У Scheme есть множество доступных реализаций.
Несмотря на некоторые синтаксические отличия между ними
(в основном это касается написания отдельных имен и пространств
Примечание для читателей
13
имен функций), сам язык однороден. Для работы с Scheme вам
потребуется определить функции atom?, sub1 и add1:
(define atom?
(lambda (x)
(and (not (pair? x)) (not (null? x)))))
Чтобы узнать, правильно ли в вашей реализации Scheme определена функция atom?, попробуйте выполнить выражение (atom? (quote
())) – оно должно дать результат #f. На самом деле книгу можно также использовать для знакомства с современными версиями языка
Lisp, такими как Common Lisp. При этом вам также придется добавить функцию atom?:
(defun atom? (x)
(not (listp x)))
Вам также может понадобиться вносить изменения в программы.
Обычно их совсем немного. Подсказки о том, как экспериментировать с программами, приведенные в книге, вы найдете в сносках.
Сноски, начинающиеся с «S:», относятся к Scheme, а начинающиеся
с «L:» – к Common Lisp.
В главе 4 мы разработаем базовую арифметику на основе трех
операторов: add1, sub1 и zero?. Поскольку в Scheme нет встроенных операторов add1 и sub1, вы должны определить их, используя
встроенные примитивы сложения и вычитания. А чтобы избежать
цикличности, наши базовые арифметические операции сложения и
вычитания должны быть записаны с использованием других символов: + и – соответственно.
В этой книге мы не даем никаких формальных определений, считая, что вы сможете сформулировать свои определения и тем самым
запомнить и понять их лучше, чем если бы мы написали эти определения для вас. Внимательно читайте встречающиеся Законы и
Заповеди и продолжайте чтение, только убедившись, что поняли их.
Ключом к изучению Scheme является «распознавание закономерностей». Заповеди указывают на закономерности, которые вы уже
видели. В начале книги некоторые понятия сужены для простоты,
но потом они дополняются и уточняются. Также имейте в виду, что
язык Scheme намного шире, чем описано в книге, и включает намного больше возможностей, чем можно было бы доходчиво описать во
вводной книге. В этой книге вы получите знания, которые помогут
вам прочитать и понять более продвинутые и исчерпывающие книги о Scheme.
14
Вступление
Мы используем ряд типографских соглашений для обозначения
символов различных классов. Переменные и имена примитивных
операций выделены курсивом. Простые данные, включая числа
и значения истинности/ложности, набраны шрифтом без засечек.
Ключевые слова, например define, lambda, cond, else, and, or и
quote, выделены жирным. Когда вы будете экспериментировать с
программами, то просто игнорируйте различия в оформлении, но
учитывайте замечания в сносках. Согласно тем же типографским
соглашениям, программы в сносках выделены моноширинным
шрифтом. Оформление шрифтов можно смело игнорировать до главы 10, где мы будем рассматривать программы как данные.
Наконец, словарь Вебстера определяет термин «пунктуация» как
действие по расстановке знаков препинания; в частности, действие,
практика или система использования стандартных знаков в письменной и печатной формах для разделения предложений или их
частей, чтобы сделать смысл более ясным. Мы восприняли это определение буквально и отказались от некоторых привычных способов использования знаков препинания, чтобы сделать смысл более
ясным. В частности, мы отказались от использования знаков препинания в левой колонке во всех случаях, когда элемент, предшест
вующий знаку препинания, является термином языка программирования.
Во многих наших примерах для демонстрации используются
названия продуктов питания. Тому есть две причины. Во-первых, еду
проще вообразить, в отличие от абстрактных символов. (Эту книгу
не стоит читать сидящим на диете.) Мы надеемся, что выбор продуктов поможет вам понять примеры и идеи, которые мы используем.
Во-вторых, мы хотели немного развлечь вас. Мы знаем, насколько раздражающим может быть предмет, и небольшое развлечение
поможет вам сохранить ясность мысли.
Теперь вы готовы приступить к работе. Удачи! Мы надеемся, что
вам понравятся задания, которые ждут вас на следующих страницах.
1. Игрушки
16
1. Игрушки
Верно ли, что это является атомом?
атом1
1
L, S: (quote атом) или 'атом.
Значения символов «L:» и «S:» описаны
во вступлении.
Верно ли, что это является атомом?
индейка
Верно ли, что это является атомом?
1942
Верно ли, что это является атомом?
u
Верно ли, что это является атомом?
*abc$
Верно ли, что это является спис
ком?
(атом)1
1
Да,
потому что атом – это строка
символов, начинающаяся с
буквы a.
Да,
потому что индейка – это строка символов, начинающаяся с
буквы.
Да,
потому что 1492 – это строка
цифр.
Да,
потому что u – это строка из
одного символа, который является буквой.
Да,
потому что *abc$ – это строка
символов, начинающаяся с
буквы или специального символа, отличного от открывающей «(» или закрывающей «)»
круглой скобки.
Да,
потому что (атом) – это атом,
заключенный в круглые скобки.
L, S: (quote атом) или 'атом.
Верно ли, что это является спис
ком?
(атом индейка или)
Да,
потому что это – коллекция
атомов, заключенная в круглые
скобки.
1. Игрушки
Верно ли, что это является спис
ком?
(атом индейка) или
Верно ли, что это является спис
ком?
((атом индейка) или)
Верно ли, что это является
S-выражением?
xyz
Верно ли, что это является
S-выражением?
17
Нет,
потому что на самом деле это
два S-выражения, не заключенные в круглые скобки.
Первое – список с двумя атомами, а второе – атом.
Да,
потому что теперь эти два
S-выражения заключены в
круглые скобки.
Да,
потому что все атомы являются S-выражениями.
Да,
потому что это список.
(x y z)
Верно ли, что это является
S-выражением?
((x y) z)
Да,
потому что все списки являются S-выражениями.
Верно ли, что это является спис
ком?
(как ваши дела на данный момент)
Да,
потому что это коллекция
S-выражений, заключенная в
круглые скобки.
Сколько S-выражений в следующем списке?
(как ваши дела на данный момент)
Перечислите их.
Шесть:
как, ваши, дела, на, данный,
момент.
Верно ли, что это является спис
ком?
Да,
потому что это коллекция
S-выражений, заключенная в
круглые скобки.
(((как) ваши) ((дела) (на данный))
момент)
18
1. Игрушки
Сколько S-выражений в следующем списке?
(((как) ваши) ((дела) (на данный))
момент)
Три:
((как) ваши), ((дела) (на данный)),
момент.
Перечислите их.
Верно ли, что это список?
()
Верно ли, что это атом?
()
Верно ли, что это список?
Да,
потому что это содержит ноль
S-выражений, заключенных
в круглые скобки. Это особое S-выражение называется
пустым списком, или null.
Нет,
потому что () – это список.
(() () () ())
Да,
потому что это коллекция
S-выражений, заключенная в
круглые скобки.
Что выдаст выражение car l,
где
l – это аргумент (a b c)?
a,
потому что a – это первый
атом в данном списке.
Что выдаст выражение car l,
где
l имеет значение ((a b c) x y z)?
(a b c),
потому что (a b c) – это первое
S-выражение в этом непустом
списке.
Что выдаст выражение car l,
где
l имеет значение хот-дог?
Нет ответа.
Нельзя взять car от атома.
Что выдаст выражение car l,
где
l имеет значение ()?
Нет ответа1.
Нельзя взять car от пустого
списка.
1
L: nil.
Правило Car’a
19
Правило Car’a
Примитив car определен только для непустых списков.
Что выдаст выражение car l,
где
l имеет значение
(((хот-дог)) (маринованные огурцы) (и) соус)?
((хот-дог))
читается как «список, содержащий другой список с единственным атомом хот-дог».
((хот-дог)) – первое S-выражение
в l.
Что выдаст выражение (car l),
где
l имеет значение
(((хот-дог)) (маринованные огурцы) (и) соус)?
((хот-дог)),
потому что (car l) – это прос
то другой способ взять «car от
списка l».
Что выдаст выражение (car (car l)),
где
l имеет значение
(((хот-дог)) (маринованные огурцы))?
((хот-дог)).
Что выдаст выражение cdr l,
где
l имеет значение (a b c)?
(b c),
потому что (b c) – список l без
(car l).
Примечание: «cdr» произносится как
«coulder» («кьюда»).
Что выдаст выражение cdr l,
где
l имеет значение ((a b c) x y z)?
(x y z).
Что выдаст выражение cdr l,
где
l имеет значение (гамбургер)?
().
Что выдаст выражение (cdr l),
где
l имеет значение ((x) t r)?
(t r)
потому что (cdr l) – это всего
лишь другой способ взять «cdr
от списка l».
20
1. Игрушки
Что выдаст выражение (cdr a),
где
a имеет значение хот-дог?
Нет ответа.
Нельзя взять cdr от атома.
Что выдаст выражение (cdr l),
где
l имеет значение ()?
Нет ответа1.
Нельзя взять cdr от пустого
списка.
1
L: nil.
Правило Cdr’a
Примитив cdr определен только для непустых списков.
Применение cdr к непустому списку всегда дает другой
список.
Что выдаст выражение
(car (cdr l)),
где
l имеет значение ((b) (x y) ((c)))?
(x y),
потому что (cdr l) выдаст
((x y) ((c))), соответственно,
(car (cdr l)) выдаст (x y).
Что выдаст выражение
(cdr (cdr l)),
где
l имеет значение ((b) (x y) ((c)))?
(((c))),
потому что (cdr l) выдаст
((x y) ((c))), соответственно,
(cdr (cdr l)) выдаст (((c))).
Что выдаст выражение
(cdr (car l)),
где
l имеет значение (a (b (c)) d)?
Нет ответа,
потому что (car l) – это атом, а
cdr не принимает атом в аргументе; см. «Закон cdr» выше.
Что car принимает в виде аргумента?
Любой непустой список.
Что cdr принимает в виде аргумента?
Любой непустой список.
Правило Cdr’a
21
Что выдаст cons при применении
к атому a и списку l,
где
a имеет значение арахис,
а l – (масло и желе)?
Это выражение можно записать
как (cons a l).
Читается как: «cons (вставить)
атом a в список l».
(арахис масло и желе),
потому что cons добавляет
атом в начало заданного спис
ка.
Что выдаст выражение cons s l,
где
s имеет значение (банан и),
а l – (арахис масло и желе)?
((банан и) арахис масло и желе),
потому что cons добавляет
любое S-выражение в начало
заданного списка.
Что выдаст выражение (cons s l),
где
s имеет значение ((помогите)
мне), а l – (это очень ((сложная)
тема для изучения))?
(((помогите) мне) это очень ((сложная) тема для изучения)).
Что cons принимает в виде аргументов?
cons принимает два аргумента:
первый – любое S-выражение;
второй – любой список.
Что выдаст выражение (cons s l),
где
s имеет значение (a b (c)),
а l – ()?
((a b (c))),
потому что () – это список.
Что выдаст выражение (cons s l),
где
s имеет значение a, а l – ()?
(a).
Что выдаст выражение (cons s l),
где
s имеет значение ((a b c)), а l – b?
Нет ответа1,
потому что второй аргумент l
должен быть списком.
1
На практике (cons α β) работает со всеми значениями α и β, при этом
(car (cons α β)) = α
(cdr (cons α β)) = β.
1. Игрушки
22
Что выдаст выражение
(cons s l),
где
s имеет значение a, а l – b?
Нет ответа.
Почему?
Правило Cons’a
Примитив cons принимает два аргумента. Второй аргумент должен быть списком. Результат – всегда список.
Что выдаст выражение
(cons s (car l)),
где
s имеет значение a, а l – ((b) c d)?
(a b)
Почему?
Что выдаст выражение
(cons s (cdr l)),
где
s имеет значение a, а l – ((b) c d)?
(a c d)
Почему?
Можно ли сказать, что
список l пустой,
если l имеет значение ()?
Да,
потому что этот список содержит нуль S-выражений.
Этот вопрос можно записать
так: (null& l).
Что выдаст выражение
(null?1 (quote ())?
Истинное значение,
потому что (quote ())1 – это форма записи пустого списка.
1
L: null
Что выдаст выражение (null? l),
где
l имеет значение (a b c)?
1
L: а также () и ‘().
S: а также ‘().
Ложное значение,
потому что l – непустой список.
Правило Null?
Что выдаст выражение (null? a),
где
a имеет значение спагетти?
23
Нет ответа1,
потому что a – это атом, а null?
не принимает атомы.
1
На практике (null? α) выдает ложное
значение для всего, что не является
пустым списком.
Правило Null?
Примитив null? определен только для списков.
Верно ли, что s – это атом,
если s имеет значение Гарри?
Да,
потому что Гарри – это строка символов, начинающаяся с
буквы.
Что выдаст выражение (atom?1 s),
где s имеет значение Гарри?
Истинное значение,
потому что (atom? s) – это прос
то другой способ записать
вопрос «Верно ли, что s – это
атом?».
1
L: (defun atom? (x)
(not listp x)))
S: (define atom?
(lambda (x)
(and (not (pair? x)) (not (null? x)))))
Что выдаст выражение (atom? s),
где
s имеет значение
(Гарри набрал кучу яблок)?
Ложное значение,
потому что s – это список.
Сколько аргументов принимает
atom? и что это за аргументы?
atom? принимает один
аргумент – любое S-выражение.
Что выдаст выражение (atom? (car l)), Истинное значение,
потому что (car l) выдаст значегде
ние Гарри, а Гарри – это атом.
l имеет значение
(Гарри набрал кучу яблок)?
Что выдаст выражение
(atom? (cdr l)),
где
l имеет значение
(Гарри набрал кучу яблок)?
Ложное значение.
24
1. Игрушки
Что выдаст выражение
(atom? (cdr l)),
где
l имеет значение (Гарри)?
Ложное значение,
потому что l результатом будет
() – пустой список, а не атом.
Что выдаст выражение
(atom? (car (cdr l))),
где
l имеет значение
(овсянка со сладкой черешней)?
Истинное значение,
потому что (cdr l) выдаст результат (со сладкой черешней), а (car
(cdr l)) – со, т. е. атом.
Что выдаст выражение
(atom? (car (cdr l))),
где
l имеет значение
(овсянка (со сладкой) черешней)?
Ложное значение,
потому что (cdr l) выдаст
результат ((со сладкой) черешней), а (car (cdr l)) – (со сладкой),
т. е. список.
Верно ли, что a1 и a2 – это один и
тот же атом,
если
a1 имеет значение Гарри
и a2 имеет значение Гарри
Да,
потому что (eq? a1 a2) отвечает
на вопрос «a1 и a2 – это один и
тот же нечисловой атом?».
Что выдаст выражение (eq?1 a1 a2),
где
a1 имеет значение Гарри
и a2 имеет значение Гарри
Истинное значение,
потому что (eq? a1 a2) – это
просто другой способ задать
вопрос «a1 и a2 – это один и тот
же нечисловой атом?».
1
L: eq.
Что выдаст выражение (eq? a1 a2),
где
a1 имеет значение маргарин
и a2 имеет значение масло
Ложное значение,
потому что a1 и a2 – разные
атомы.
Сколько аргументов принимает
eq? и что это за аргументы?
eq? принимает два аргумента.
Оба должны быть нечисловыми атомами.
Правило Eq?
25
Что выдаст выражение (eq? l1 l2),
где
l1 имеет значение ()
и l2 имеет значение (земляника)
Нет ответа1,
потому что () и (земляника) – это
списки.
Что выдаст выражение (eq? n1 l2),
где
n1 имеет значение 6
и n2 имеет значение 7?
Нет ответа1,
потому что 6 и 7 – это числа.
1
1
На практике eq? может принимать
списки в аргументах. Два списка считаются одинаковыми, если являются
одним и тем же списком.
На практике некоторые числа могут
быть аргументами eq?.
Правило Eq?
Примитив eq? принимает два аргумента, каждый из
которых должен быть нечисловым атомом.
Что выдаст выражение
(eq? (car l) a),
где
l имеет значение Мэри заказала
маленькую отбивную из ягненка
и a имеет значение Мэри
Истинное значение,
потому что (car l) выдает атом
Мэри и аргумент a тоже является атомом Мэри.
Что выдаст выражение
(eq? (cdr l) a),
где
l имеет значение кислое молоко
и a имеет значение молоко
Нет ответа.
См. «Правило Eq?» и «Правило
Сdr’а».
Что выдаст выражение
(eq? (car l) (car (cdr l))),
где
l имеет значение
(бобы бобы нам нужны желейные бобы)
Истинное значение,
потому что сравниваются первый и второй атомы в списке.
=> А теперь сделайте себе сэндвич
с арахисовым маслом и джемом. <=
Это место зарезервировано
ДЛЯ ПЯТЕН ОТ ДЖЕМА!
2. Сделай это, сделай это снова,
и снова, и снова...
28
2. Сделай это, сделай это снова, и снова, и снова...
Истинно или ложно выражение
(lat? l),
где
l имеет значение
(Джек Спрат не смог съесть жирного цыпленка)?
Истинное значение,
потому что все S-выражения в l
являются атомами.
Истинно или ложно выражение
(lat? l),
где
l имеет значение
((Джек) Спрат не смог съесть жирного цыпленка)?
Ложное значение,
потому что (car l) – это список.
Истинно или ложно выражение
(lat? l),
где
l имеет значение
(Джек (Спрат не смог) съесть жирного цыпленка)?
Ложное значение,
потому что одно из S-выражений в l является списком.
Истинно или ложно выражение
(lat? l),
где
l имеет значение ()?
Истинное значение,
потому что пустой список в l не
содержит списков.
Верно ли, что
lat – это список атомов?
Верно!
Всякий lat – это список атомов
(list of atoms)!
Напишите функцию lat?, используя некоторые, но не обязательно
все из нижеприведённых, функции: car, cdr, cons, null?, atom? и
eq?.
Скорее всего, вы не сможете
сделать это, потому что пока
незнакомы с некоторыми компонентами. Переходите к следующим вопросам. Удачи!
Отдохнули?
2. Сделай это, сделай это снова, и снова, и снова...
(define lat?1
(lambda (l)
(cond
((null? l) #t)
((atom? (car l)) (lat? (cdr l)))
(else #f))))
29
#t.
Выражение (lat? l),
где
l имеет значение
(яичница с беконом),
выдаст значение
#t – true (истина) – потому что
l – это lat (список атомов).
Что выдаст выражение (lat? l),
где
l имеет значение
(яичница с беконом)?
1
L: (defun lat? (1)
(coud
((null 1) t)
((atom? (oar 1)) (lat? (odi 1)))
(t nil)))
Как определяется результат #t
при применении (lat? l)?
Наверняка вы этого не знали
прежде. Результат определяется
ответами на вопросы, задаваемые в функции lat?.
Подсказка: выпишите определение
функции lat? и обращайтесь к нему,
когда будете отвечать на вопросы, следующие далее.
Какой первый вопрос задает
(lat? l)?
(null? l)
Примечание:
(cond ...) задает вопросы;
(lambda ...) создает функцию;
(define ...) дает имя функции.
30
2. Сделай это, сделай это снова, и снова, и снова...
Что выдаст выражение
((null? l) #t) в операторе cond,
где
l имеет значение
(яичница с беконом)?
(null? l) спрашивает: является ли
аргумент l пустым списком? Если
ответ положительный, то результатом становится истинное значение (#t). Иначе задается следующий вопрос. В данном случае
l – не пустой список, поэтому
задается следующий вопрос.
Какой следующий вопрос?
(atom? (car l)).
Что выдаст выражение
((atom? (car l)) (lat? (cdr l))),
где
l имеет значение
(яичница с беконом)?
(atom? (car l)) спрашивает:
является ли атомом первое
S-выражение в списке l?
Если (car l) – атом, то нужно
узнать, являются ли все остальные элементы списка l атомами.
Если (car l) – не атом, то задается
следующий вопрос.
В данном случае (car l) – атом,
поэтому значением функции
становится результат выражения
(lat? (cdr l)).
Что выдаст выражение
(lat? (cdr l))?
Выражение (lat? (cdr l)) просмат
ривает остальные элементы в
списке l и проверяет, являются
ли они атомами, применяя функцию lat? к новому аргументу.
Что на этот раз получает lat? в
аргументе l?
На этот раз в l передается результат (cdr l) – (с беконом).
Какой следующий вопрос?
(null? l).
2. Сделай это, сделай это снова, и снова, и снова...
31
Что выдаст выражение
((null? l) #t,
где
l теперь имеет значение
(с беконом)?
(null? l) спрашивает:
является ли аргумент l пустым
списком?
Если ответ положительный, то
результатом становится истинное значение (#t).
Иначе задается следующий
вопрос.
В данном случае l – не пустой
список, поэтому задается следующий вопрос.
Какой следующий вопрос?
(atom? (car l)).
Что выдаст выражение
((atom? (car l)) (lat? (cdr l))),
где
l имеет значение
(с беконом)?
(atom? (car l)) спрашивает:
является ли атомом первое
S-выражение в списке l?
Если (car l) – атом, то результатом
выражения становится результат
(lat? (cdr l)).
Иначе задается следующий
вопрос.
В данном случае (car l) – атом,
поэтому значением функции
становится результат проверки –
являются ли атомами все остальные элементы списка.
Что выдаст выражение
(lat? (cdr l))?
Выражение (lat? (cdr l)) просмат
ривает остальные элементы в
списке l и проверяет, являются ли они атомами, применяя
функцию lat? к новому аргументу – результату выражения (cdr l),
в данном случае (беконом).
Какой следующий вопрос?
(null? l).
32
2. Сделай это, сделай это снова, и снова, и снова...
Что выдаст выражение
((null? l) #t,
где
l теперь имеет значение (беконом)?
(null? l) спрашивает:
является ли аргумент l пустым
списком?
Если ответ положительный, то
результатом становится истинное значение (#t).
Иначе задается следующий
вопрос.
В данном случае l – не пустой
список, поэтому задается следующий вопрос.
Какой следующий вопрос?
(atom? (car l)).
Что выдаст выражение
((atom? (car l)) (lat? (cdr l))),
(atom? (car l)) спрашивает: является ли атомом результат применения (car l).
Если ответ положительный, то
результатом выражения становится результат (lat? (cdr l)).
Если (car l) – не атом, то задается
следующий вопрос.
В данном случае (car l) – атом,
поэтому снова выполняется
выражение (lat? (cdr l)).
где
l имеет значение (беконом)?
Что выдаст выражение
(lat? (cdr l))?
Выражение (lat? (cdr l)) просмат
ривает остальные элементы в
списке l и проверяет, являются
ли они атомами, применяя функцию lat? к новому аргументу –
результату выражения (cdr l).
Какой аргумент принимает lat?
на этот раз?
().
2. Сделай это, сделай это снова, и снова, и снова...
33
Что выдаст выражение
((null? l) #t,
где
l теперь имеет значение ()?
(null? l) спрашивает: является ли
аргумент l пустым списком?
Если ответ положительный, то
результатом становится истинное значение (#t). Иначе задается
следующий вопрос.
В данном случае l имеет значение () – пустой список. Поэтому
результатом применения (lat? l),
где
l имеет значение (яичница с беконом), является #t – true (истина).
Вы еще помните, какой вопрос
мы задавали о (lat? l)?
Скорее всего, нет.
Как (lat? l), определяющая, что
список l содержит только атомы,
дает #t для l со значением (яичница с беконом)?
Сможете описать своими
словами, что делает функция
(lat? l)?
Вот наше описание:
«lat? просматривает по очереди каждое S-выражение в
списке, спрашивая, является
ли оно атомом. Если по пути
ей не встретится список, то она
выдаст значение #t. Если обнаружится список, то выдаст значение #f – false (ложь)».
Чтобы увидеть, как достигается
значение «ложь», рассмотрим
еще несколько вопросов.
Повторим еще раз определение
функции lat?:
#f,
потому что список l содержит
S-выражение,
являющееся
списком.
(define lat?
(lambda (l)
(cond
((null? l) #t)
((atom? (car l)) (lat? (cdr l)))
(else #f))))
34
2. Сделай это, сделай это снова, и снова, и снова...
Что выдаст выражение (lat? l),
где
l имеет значение
(яичница (с беконом))?
Какой первый вопрос задает
(lat? l)?
(null? l).
Что выдаст выражение
((null? l) #t),
где
l имеет значение
(яичница (с беконом))?
(null? l) спрашивает:
является ли аргумент l пустым
списком?
Если ответ положительный, то
результатом становится истинное значение #t.
Иначе задается следующий
вопрос.
В данном случае l – не пустой
список, поэтому задается следующий вопрос.
Какой следующий вопрос?
(atom? (car l)).
Что выдаст выражение
((atom? (car l)) (lat? (cdr l))),
где
l имеет значение
(яичница (с беконом))?
(atom? (car l)) спрашивает:
является ли атомом (car l)?
Если да, то оценивается выражение (lat? (cdr l))). Если нет, то задается следующий вопрос.
В данном случае (car l) – атом,
поэтому далее проверяется,
являются ли все остальные элементы списка l атомами.
Что выдаст выражение
(lat? (cdr l))?
Выражение (lat? (cdr l)) просмат
ривает остальные элементы в
списке l и проверяет, являются
ли они атомами, применяя функцию lat? к аргументу (cdr l) вмес
то l.
2. Сделай это, сделай это снова, и снова, и снова...
35
Что выдаст выражение
((null? l) #t,
где
l теперь имеет значение
((с беконом))?
(null? l) спрашивает:
является ли аргумент l пустым
списком?
Если ответ положительный, то
результатом становится истинное значение #t. Иначе задается
следующий вопрос.
В данном случае l – не пустой
список, поэтому задается следующий вопрос.
Какой следующий вопрос?
(atom? (car l)).
Что выдаст выражение
((atom? (car l)) (lat? (cdr l))),
где
l имеет значение ((с беконом))?
(atom? (car l)) спрашивает:
является ли атомом выражение
(car l)?
Если да, то результатом выражения становится результат (lat?
(cdr l)). Если нет, то задается следующий вопрос.
В данном случае (car l) – атом,
поэтому задается следующий
вопрос.
Какой следующий вопрос?
else.
Что означает конструкция else?
else спрашивает: верно ли иное?
Истинно ли else?
Да,
потому что на вопрос else всегда
дается ответ #t (истина)!
else?
Конечно!
Почему вопрос else задается
последним?
Потому что после получения
ответа на этот вопрос больше не
о чем спрашивать.
Почему больше не о чем спрашивать?
Потому что список может быть
пустым, может содержать атом
в первом элементе или может
содержать список в первом элементе.
36
2. Сделай это, сделай это снова, и снова, и снова...
Что выдаст выражение (else #f)?
else спрашивает: верно ли иное?
Если иное верно, а это всегда так,
то возвращается ответ #f (false –
ложь).
Что означают последние три
закрывающие скобки )))?
Они соответствуют парным им
открывающим круглым скобкам в последовательности операторов (cond ..., (lambda ... и
(define ... в начале определения
функции.
Попробуйте описать своими
словами, как определяется
значение #f для (lat? l),
Вот наше описание:
«(lat? l) просматривает все элементы в своем аргументе и проверяет, являются ли они атомами. Если по пути не встретится
список, то (lat? l) выдаст значение #t. Если обнаружится список, как в примере с аргументом
(яичница (с беконом)), то (lat? l)
выдаст значение #f».
где
l имеет значение
(яичница (с беконом)).
Истинно или ложно выражение
(or (null? l1) (atom? l2)),
где
l1 имеет значение (),
а l2 – значение (d e f g)?
Истинно,
потому что (null? l1) дает истинное значение для l1 со значением ().
Истинно или ложно выражение
(or (null? l1) (null? l2)),
где
l1 имеет значение (a b c),
а l2 – значение ()?
Истинно,
потому что (null? l2) дает истинное значение для l2 со значением ().
Истинно или ложно выражение
(or (null? l1) (null? l2)),
где
l1 имеет значение (a b c),
а l2 – значение (атом)?
Ложно,
потому что ни (null? l1),
ни (null? l2) не даст истинного
значения для
l2 со значением (a b c)
и l2 со значением (атом).
2. Сделай это, сделай это снова, и снова, и снова...
37
Что делает оператор (or ...)?
(or ...) задает два вопроса подряд.
Если в ответ на первый будет
получено истинное значение, то
второй вопрос не задается и возвращается истинное значение.
Иначе задается второй вопрос,
и ответ на него становится
результатом всего выражения.
Верно ли, что a является членом lat,
где
a имеет значение чай,
а lat – значение
(кофе чай или молоко)?
Верно,
потому что один из атомов
в lat (кофе чай или молоко)
является тем же атомом,
что и a – чай.
Что выдаст выражение
(member? a lat),
где
a имеет значение пашот,
а lat – значение (глазунья и
омлет)?
Ложное значение,
потому что a не является ни
одним из атомов в lat.
Вот функция member?:
#t,
потому что атом мясо является
одним из атомов в lat,
(картофельное пюре и мясо
с подливкой).
(define member?
(lambda (a lat)
(cond
((null? lat) #f)
(else (or (eq? (car lat) a)
(member? a (cdr lat)))))))
Какое значение выдаст
(member? a lat),
где
a имеет значения мясо,
а lat – значение (картофельное
пюре и мясо с подливкой)?
38
2. Сделай это, сделай это снова, и снова, и снова...
Как предыдущее применение
функции member? определяет
значение #t?
Значение определяется как ответ
на вопрос (member? a lat).
Какой первый вопрос задает
(member? a lat)?
(null? lat).
Это также первый вопрос, который задает lat?.
Подсказка: выпишите определение
функции member? и обращайтесь к
нему, когда будете отвечать на вопросы, следующие далее.
Первая заповедь
(предварительная версия)
Всегда первым задавайте вопрос null? в определении
любой функции.
Какой первый вопрос задает
(member? a lat)?
(null? lat).
Это также первый вопрос, который задает lat?.
Что выдаст выражение
((null? lat) #f)
в операторе cond,
где
lat имеет значение
(картофельное пюре и мясо с
подливкой)?
(null? lat) спрашивает:
является ли аргумент lat пустым
списком?
Если ответ положительный, то
результатом становится значение #f, потому что атом мясо не
может присутствовать в пустом
списке. Иначе задается следующий вопрос.
В данном случае lat – не пустой
список, поэтому задается следующий вопрос.
Какой следующий вопрос?
else.
Почему следующий вопрос else?
Потому что нет необходимости
ни в каких других вопросах.
Первая заповедь (предварительная версия)
39
Действительно ли else является
вопросом?
Да,
else – это вопрос, в ответ на
который всегда дается истинное значение.
Что выдаст выражение
(else (or (eq? (car lat) a)
(member? a (cdr lat))))?
Теперь, когда известно, что lat не
null?, нужно проверить, является ли результат применения car
к lat тем же атомом, что и a, или,
может быть, искомый атом находится в остальной части lat?
Выражение
(or (eq? (car lat) a)
(member? a (cdr lat)))
отвечает на этот вопрос.
Что выдаст выражение
(or (eq? (car lat) a)
(member? a (cdr lat))),
где
a имеет значение мясо,
а
lat – значение
(картофельное пюре и мясо с
подливкой)?
Определим ответ, отвечая на
каждый вопрос по очереди.
Что выдаст выражение
(eq? (car lat) a),
где
a имеет значение мясо,
а
lat – значение
(картофельное пюре и мясо с
подливкой)?
Ложное значение,
потому что атом мясо не равен
(eq?) результату применения
car к (картофельное пюре и мясо
с подливкой).
Какой второй вопрос задает
оператор (or ...)?
(member? a (cdr lat)).
Это выражение применяет ту же
функцию member?, но заменяет
аргумент lat аргументом (cdr lat).
40
2. Сделай это, сделай это снова, и снова, и снова...
Какие аргументы на этот раз
получает member?
a – мясо,
и lat теперь получает результат
применения (cdr lat) – (пюре и
мясо с подливкой).
Какой следующий вопрос?
(null? lat).
Вспомните первую заповедь.
Какое значение выдаст выражение (null? lat),
где
lat имеет значение
(пюре и мясо с подливкой)?
#f – false (ложь).
Что мы делаем дальше?
Задаем следующий вопрос.
Какой следующий вопрос?
else.
Что выдаст выражение
(or (eq? (car lat) a)
(member? a (cdr lat)))?
(or (eq? (car lat) a)
(member? a (cdr lat)))
Оно проверит, является ли (eq?)
результат применения car к lat
тем же атомом, что и a, и если
нет, то проверит результат применения cdr к lat вызовом той же
функции member?.
Результат применения car к lat
является (eq?) тем же атомом,
что и a?
Нет,
потому что a – это мясо,
а car lat – это пюре.
Что мы делаем дальше?
Задаем вопрос
(member? a (cdr lat)).
Какие аргументы на этот раз
получает member?
a – мясо
и
lat – (и мясо с подливкой).
Какой следующий вопрос?
(null? lat).
Что мы делаем дальше?
Задаем следующий вопрос,
потому что выражение (null?
lat) дало ложное значение.
Первая заповедь (предварительная версия)
41
Какой следующий вопрос?
else.
Что выдаст выражение
(or (eq? (car lat) a)
(member? a (cdr lat)))?
Значение (member? a (cdr lat)).
Почему?
Потому что выражение
(eq? (car lat) a)
дало ложное значение.
Что мы делаем дальше?
Повторяем – вызываем функцию member? с новыми аргументами.
Какие аргументы на этот раз
получает member?
a – мясо
и
lat – (мясо с подливкой).
Какой следующий вопрос?
(null? lat).
Что мы делаем дальше?
Задаем следующий вопрос,
потому что выражение
(null? lat)
дало ложное значение.
Какой следующий вопрос?
else.
Что выдаст выражение
(or (eq? (car lat) a)
(member? a (cdr lat)))?
#t,
потому что (car lat)
и a – это один и тот же атом
мясо. Соответственно, ответом
выражения (or ...) будет значение #t.
Какой результат выдаст применение (member? a lat),
где
a имеет значение мясо,
а
lat – значение (мясо с подливкой)?
#t,
потому что мы обнаружили,
что атом мясо присутствует в
списке (мясо с подливкой).
42
2. Сделай это, сделай это снова, и снова, и снова...
Какой результат выдаст применение (member? a lat),
где
a имеет значение мясо,
а
lat – значение (и мясо с
подливкой)?
#t,
потому что атом мясо также
присутствует в списке
(и мясо с подливкой).
Какой результат выдаст применение (member? a lat),
где
a имеет значение мясо,
а
lat – значение (пюре и мясо с
подливкой)?
#t,
потому что атом мясо также
присутствует в списке
(пюре и мясо с подливкой).
Какой результат выдаст применение (member? a lat),
где
a имеет значение мясо,
а
lat – значение (картофельное
пюре и мясо с подливкой)?
#t,
потому что атом мясо также
присутствует в списке
(картофельное пюре и мясо с
подливкой).
Конечно, это наш исходный
список.
Только чтобы убедиться, что вы
все поняли правильно, кратко
повторим пройденное.
Какой результат выдаст применение (member? a lat),
где
a имеет значение мясо,
а
lat – значение (картофельное
пюре и мясо с подливкой)?
#t.
(null? lat)?
Нет.
Переходим к следующей строке.
else?
Да.
(or (eq? (car lat) a)
(member? a (cdr lat)))?
Возможно.
Подсказка: выпишите определение
функции member? и ее аргументы и
обращайтесь к ним, просматривая
вопросы, следующие далее.
Первая заповедь (предварительная версия)
43
(eq? (car lat) a)?
Нет.
Задаем следующий вопрос.
Что дальше?
Повторяем все сначала с аргументами a и (cdr lat),
где
a – мясо,
а
(cdr lat) – (пюре и мясо с подливкой).
(null? lat)?
Нет.
Переходим к следующей строке.
else?
Да.
Но (eq? (car lat) a) дает ложное
значение.
Повторяем все сначала с аргументами a и (cdr lat),
где
a – мясо,
а
(cdr lat) – (и мясо с подливкой).
(null? lat)?
Нет.
Переходим к следующей строке.
else?
Да.
Но (eq? (car lat) a) дает ложное
значение.
Повторяем все сначала с аргументами a и (cdr lat),
где
a – мясо,
а
(cdr lat) – (мясо с подливкой).
(null? lat)?
Нет.
Переходим к следующей строке.
(eq? (car lat) a)?
Да.
Выдаем значение #t.
44
2. Сделай это, сделай это снова, и снова, и снова...
(or (eq? (car lat) a)
(member? a (cdr lat)))?
#t.
Какой результат выдаст применение (member? a lat),
где
a – мясо,
а
lat – (мясо с подливкой)?
#t.
Какой результат выдаст применение (member? a lat),
где
a – мясо,
а
lat – (и мясо с подливкой)?
#t.
Какой результат выдаст применение (member? a lat),
где
a – мясо,
а
lat – (пюре и мясо с подливкой)?
#t.
Какой результат выдаст применение (member? a lat),
где
a – мясо,
а
lat – (картофельное пюре и мясо с
подливкой)?
#t.
Какой результат выдаст применение (member? a lat),
где
a – ливер,
а
lat – (бублик с лососиной)?
#f.
Первая заповедь (предварительная версия)
45
Давайте посмотрим, почему на
этот раз получилось значение #f.
Какой первый вопрос задает
member??
(null? lat).
(null? lat)?
Нет,
переходим к следующей строке.
else?
Да.
Но (eq? (car lat) a) дает ложное
значение.
Повторяем все сначала с аргументами a и (cdr lat),
где
a – ливер,
а
(cdr lat) – (с лососиной).
(null? lat)?
Нет,
переходим к следующей строке.
else?
Да.
Но (eq? (car lat) a) дает ложное
значение.
Повторяем все сначала с аргументами a и (cdr lat),
где a – ливер,
а
(cdr lat) – (с лососиной).
(null? lat)?
Нет,
переходим к следующей строке.
else?
Да.
Но (eq? (car lat) a) дает ложное
значение.
Повторяем все сначала с аргументами a и (cdr lat),
где
a – ливер,
а
(cdr lat) – ().
46
2. Сделай это, сделай это снова, и снова, и снова...
(null? lat)?
Да.
Какой результат выдаст применение (member? a lat),
где
a – ливер,
а
lat – ()?
#f.
Что выдаст выражение
(or (eq? (car lat) a)
(member? a (cdr lat))),
где
a – ливер,
а
lat – (лососиной)?
#f.
Какой результат выдаст применение (member? a lat),
где
a – ливер,
а
lat – (лососиной)?
#f.
Что выдаст выражение
(or (eq? (car lat) a)
(member? a (cdr lat))),
где
a – ливер,
а
lat – (с лососиной)?
#f.
Какой результат выдаст применение (member? a lat),
где
a – ливер,
а
lat – (с лососиной)?
#f.
Первая заповедь (предварительная версия)
Что выдаст выражение
(or (eq? (car lat) a)
(member? a (cdr lat))),
где
a – ливер,
а
lat – (бублик с лососиной)?
#f.
Какой результат выдаст применение (member? a lat),
где
a – ливер,
а
lat – (бублик с лососиной) ?
#f.
Вам все понятно?
Тогда можете отдохнуть!
47
Здесь можно что-нибудь нарисовать
или оставить заметки.
3. Cons великолепный
50
3. Cons великолепный
Что выдаст (rember a lat),
где a – мятное
и
lat – (баранья отбивная и мятное
желе)?
(баранья отбивная и желе).
Имя функции «rember» означает
«remove a member» (удалить элемент).
(rember a lat),
где a – мятное
и
lat – (баранья отбивная и мятное
ароматное мятное желе)?
(баранья отбивная и ароматное
мятное желе).
(rember a lat),
где a – тост
и
lat – (бекон салат и помидор)?
(бекон салат и помидор).
(rember a lat),
где a – чашка
и
lat – (кофейная чашка чайная чашка и деревенская чашка)?
(кофейная чайная чашка и деревенская чашка).
Что делает (rember a lat)?
Принимает аргументы с атомом
и списком атомов (list of atoms,
lat) и создает новый lat (список
атомов) – копию исходного спис
ка, из которой удалено первое
вхождение заданного атома.
Какие шаги необходимо выполнить для этого?
Сначала нужно выполнить проверку (null? lat), как того требует
первая заповедь.
А если (null? lat) вернет истинное
значение?
Выдать ().
О чем говорит ложное значение,
выданное выражением
(null? lat)?
Что в lat есть по меньшей мере
один атом.
Есть ли еще вопросы, которые мы
должны задать в отношении lat?
Нет. Список lat либо пустой, либо
содержит хотя бы один атом.
3. Cons великолепный
51
Что мы должны сделать, зная, что
lat содержит хотя бы один атом?
Спросить, равны ли a и (car lat).
Как задаются вопросы?
С помощью выражения
(cond
( ________ ________ )
( ________ ________ )).
Как спросить, равен ли атом a
атому (car lat)?
(eq? (car lat) a).
Какое значение выдаст
(rember a lat), если a и (car lat) –
один и тот же атом?
(cdr lat).
Что делать, если a и (car lat) –
разные атомы?
Сохранить (car lat) и попытаться
отыскать a в оставшейся части
lat.
Как удалить первое вхождение a
из оставшейся части lat?
(rember a (cdr lat)).
Есть ли еще вопросы, которые
мы должны задать?
Нет.
Теперь запишем, что мы выяснили к данному моменту:
(салат и помидор).
(define rember
(lambda (a lat)
(cond
((null? lat) (quote ()))
(else (cond
((eq? (car lat) a) (cdr lat))
(else (rember a
(cdr lat))))))))
Какое значение выдаст
(rember a lat),
где
a – бекон
и
lat – (бекон салат и помидор)?
Подсказка:
выпишите
определение
функции rember и ее аргументы и обращайтесь к ним, просматривая вопросы,
следующие далее.
52
3. Cons великолепный
Теперь посмотрим, правильно
ли работает эта функция. Какой
первый вопрос?
(null? lat).
Что делаем дальше?
Переходим к следующей строке и
задаем следующий вопрос.
else?
Да.
Что дальше?
Задаем следующий вопрос.
(eq? (car lat) a)?
Да,
т. е. результатом становится значение выражения
(car lat) – список (салат и помидор).
Это верный результат?
Да,
потому что результат – это копия
исходного списка без атома
бекон.
А насколько показателен пример, который мы выбрали?
Мы не знаем.
Узнать, вкусный ли пудинг, можно, только съев его, поэтому
попробуем другой пример.
Что делает rember?
Принимает аргументы с атомом
и списком атомов (list of atoms,
lat) и создает новый lat (список
атомов) – копию исходного списка, из которой удалено первое
вхождение заданного атома.
Что мы сделаем теперь?
Сравним каждый атом в lat с атомом a и, если сравнение потерпит неудачу, сконструируем список, начинающийся с атома, с
которым только что проводилось
сравнение.
Первая заповедь (предварительная версия)
53
Какое значение выдаст
(rember a lat),
где a – и
и
lat – (бекон салат и помидор)?
(бекон салат помидор).
Давайте посмотрим, правильно
ли работает эта функция. Какой
первый вопрос мы зададим
фукнции rember?
(null? lat).
Что делаем дальше?
Переходим к следующей строке и
задаем следующий вопрос.
else?
Да.
Задаем следующий вопрос.
(eq? (car lat) a)?
Нет,
поэтому переходим к следующей
строке.
Что выдаст выражение
(else (rember a (cdr lat)))?
else спрашивает: верно ли иное?
(А это всегда так.) А остальная
часть строки требует повторить
применение функции rember к
аргументам a и (cdr lat),
где a – и
и
(cdr lat) – (салат и помидор).
(null? lat)?
Нет,
поэтому переходим к следующей
строке.
else?
Да, конечно.
(eq? (car lat) a)
Да.
Что получится в результате?
(cdr lat) – (помидор).
Это верный ответ?
Нет,
потому что (помидор) не является
списком (бекон салат и помидор) с
удаленным элементом и.
54
3. Cons великолепный
Что мы сделали неправильно?
Мы удалили и, но при этом потеряли все атомы, предшествовавшие и.
Как можно избежать потери атомов бекон салат?
Использовать cons, как мы делали это в главе 1.
Вторая заповедь
Используйте cons для создания списка.
Давайте посмотрим, что получится, если использовать cons.
(define rember
(lambda (a lat)
(cond
((null? lat) (quote ()))
(else (cond
((eq? (car lat) a) (cdr lat))
(else (cons (car lat)
(rember a
(cdr lat)))))))))
(бекон салат помидор).
Подсказка: выпишите определение этой
функции с cons и ее аргументы и обращайтесь к ним, просматривая вопросы,
следующие далее.
Что выдаст (rember a lat),
где
a имеет значение и
и
lat – значение (бекон салат и
помидор)?
Какой первый вопрос?
(null? lat).
Что делаем дальше?
Задаем следующий вопрос.
else?
Да, конечно.
(eq? (car lat) a)?
Нет,
поэтому переходим к следующей
строке.
Вторая заповедь
55
Что выдаст
(cons (car lat)
(rember a
(cdr lat))),
где
a имеет значение и
и
lat – значение (бекон салат и
помидор)?
Это выражение применит cons,
чтобы скопировать результат
(car lat) – значение бекон – в значение (rember a (cdr lat)).
Но так как значение
(rember a (cdr lat)) неизвестно,
мы должны сначала найти его, а
потом добавить в него результат
(car lat).
Что выдаст
(rember a (cdr lat))?
Это выражение вызывает функцию rember, но вместо lat передает ей (cdr lat) – (салат и помидор).
(null? lat)?
Нет,
поэтому переходим к следующей строке.
else?
Да, задаем следующий вопрос.
(eq? (car lat) a)?
Нет,
переходим к следующей строке.
Что выдаст
(cons (car lat)
(rember a
(cdr lat)))?
Это выражение предлагает оператору cons скопировать car от
lat – значение салат – в значение
(rember a (cdr lat)).
Но так как значение
(rember a (cdr lat)) неизвестно, мы
должны сначала найти
(rember a (cdr lat)), а потом
cons (car lat) в него.
Что выдаст
(rember a (cdr lat))?
Это выражение вызывает функцию rember, но вместо lat передает ей (cdr lat) – (и помидор).
(null? lat)?
Нет,
поэтому переходим к следующей
строке.
else?
Да, задаем следующий вопрос.
(eq? (car lat) a)?
Да.
56
3. Cons великолепный
Какое значение даст строка
((eq? (car lat) a) (cdr lat))?
(cdr lat) – (помидор).
Мы закончили?
Конечно нет!
Мы узнали результат (rember a lat),
где
lat имеет значение (и помидор),
но мы все же не знаем результат
(rember a lat),
где
lat имеет значение (салат и
помидор)
или
(бекон салат и помидор).
Теперь у нас есть значение
(rember a (cdr lat)),
где
a имеет значение и
и
(cdr lat) – значение (и помидор).
Это значение (помидор).
Что дальше?
Напомню, что мы должны cons
салат в значение
(rember a (cdr lat)),
где
a имеет значение и
и
результат (cdr lat) имел значение (и помидор).
Теперь, когда у нас есть это значение – (помидор), – мы можем
cons салат в него.
Что получается в результате
cons салат в (помидор)?
(салат помидор).
Что представляет значение
(салат помидор)?
Это результат
(cons (car lat)
(rember a
(cdr lat))),
где
lat имеет значение (салат и
помидор)
и
(rember a (cdr lat)) – значение
(помидор).
Вторая заповедь
57
Мы закончили?
Еще нет.
К настоящему моменту мы узнали, что выдаст (rember lat), когда
lat имеет значение (салат и помидор), но пока не знаем, что выдаст
это выражение, когда lat имеет
значение (бекон салат и помидор).
Теперь у нас есть значение
(rember a (cdr lat)),
где
a имеет значение и
и
(cdr lat) – значение (салат и
помидор). Это значение (салат
помидор). Но это еще не окончательный результат.
Какой следующий шаг нужно
сделать?
Напомню, что мы должны cons
бекон в значение
(rember a (cdr lat)),
где
a имеет значение и
и
результат (cdr lat) имел значение (салат и помидор).
Теперь, когда у нас есть это значение – (салат помидор), – мы
можем cons бекон в него.
Что получается в результате cons
бекон в (салат помидор)?
(бекон салат помидор).
Что представляет значение
(бекон салат помидор)1?
Это результат
(cons (car lat)
(rember a (cdr lat))),
где
lat имеет значение (бекон салат
и помидор)
и
(rember a (cdr lat)) – значение
(салат помидор).
1
Завтрак?
Ну, теперь-то мы закончили?
Да.
58
3. Cons великолепный
Попробуйте
описать
своими словами, как определяется
конечное значение (бекон салат
помидор).
Вот наше описание:
«Функция rember проверяет
поочередно каждый атом в lat,
чтобы выяснить, является ли
он атомом и. Если результат
применения car не является
атомом и, то он сохраняется,
чтобы позже его можно было
вставить (cons) в конечное
значение. Обнаружив атом и,
функция rember удаляет его и
вставляет предыдущие атомы
в обратном порядке в остав
шуюся часть lat».
Попробуйте переписать функцию rember так, чтобы ее структура отражала описание выше.
Вот как можно упростить ее.
Такое определение
проще?
выглядит
Да. Кстати, функции, подобные
rember, всегда можно упростить
таким способом.
Почему мы не упростили ее сразу?
Потому что тогда структура
функции не совпала бы со структурой ее аргументов.
Давайте посмотрим, работает
ли новая функция rember так же,
как старая. Что даст применение
(rember a lat),
где
a имеет значение и
и
lat – значение (бекон салат и
помидор)?
(бекон салат помидор).
(define rember
(lambda (a lat)
(cond
((null? lat) (quote ()))
((eq? (car lat) a) (cdr lat))
(else (cons (car lat)
(rember a (cdr lat)))))))
Подсказка: выпишите определение этой
функции rember и ее аргументы и обращайтесь к ним, просматривая вопросы,
следующие далее.
Вторая заповедь
59
(null? lat)?
Нет.
(eq? (car lat) a)?
Нет.
else?
Да,
поэтому результат получит значение
(cons (car lat)
(rember a (cdr lat))).
Что выдаст
(cons (car lat)
(rember a (cdr lat)))?
Это выражение вызывает функцию rember, замещая аргумент
lat значением (cdr lat), и, получив результат (rember a (cdr lat)),
добавляет в него (car lat) – значение бекон.
(null? lat)?
Нет.
else?
Да,
поэтому результат получит значение
(cons (car lat)
(rember a (cdr lat))).
Что выдаст
(cons (car lat)
(rember a (cdr lat)))?
Это выражение рекурсивно вызы-
вает функцию rember, замещая
аргумент lat значением
(cdr lat), и, получив результат
(rember a (cdr lat)), добавляет в
него (car lat) – значение салат.
(null? lat)?
Нет.
(eq? (car lat) a)?
Да.
Какое значение даст строка
((eq? (car lat) a) (cdr lat))?
(cdr lat) – (помидор).
Что дальше?
Теперь cons (car lat) – добавляем
салат в (помидор).
Что дальше?
Теперь cons (car lat) – добавляем
бекон в (салат помидор).
60
3. Cons великолепный
Теперь, разобравшись с функцией rember, попробуйте другой
пример: (rember a lat),
где
a имеет значение соус
и
lat – значение (соевый соус и
томатный соус).
(rember a lat) даст в результате
(соевый и томатный соус).
Что даст (firsts l),
где
l – ((яблоко персик тыква)
(слива груша вишня)
(виноград изюм горох)
(фасоль морковь баклажан))?
(яблоко слива виноград фасоль).
Что даст (firsts l),
где
l – ((a b) (c d) (e f))?
(a c e).
Что даст (firsts l),
где
l – ()?
().
Что даст (firsts l),
где
l – ((пять слив)
(четыре)
(одиннадцать зеленых апельсинов))?
(пять четыре одиннадцать).
Что даст (firsts l),
где
l – (((пять слив) четыре)
(одиннадцать зеленых апельсинов))
((нет) больше))?
((пять слив) одиннадцать (нет)).
Вторая заповедь
61
Опишите своими словами, что
делает применение функции
(firsts l).
Вот наше описание:
«Функция firsts принимает один
аргумент, список, который может
быть пустым списком или содержит только непустые списки, и
создает другой список, составленный из первых S-выражений
внутренних списков».
Попробуйте написать определение функции firsts.
Это очень просто:
Вспомните заповеди!
(define firsts
(lambda (l)
(cond
((null? l) …)
(else (cons ... (firsts (cdr l)))))))
Для чего используются строки
(define firsts
(lambda (l)
...))?
С этих строк начинается определение любой функции. define
задает имя функции, а (lambda
перечисляет аргументы и тело
функции.
Для чего нужна строка (cond ...)?
Чтобы помочь нам задавать
вопросы о фактических аргументах.
Что делает ((null? l) …)?
Смотрите первую заповедь.
Для чего нужна строка (else ...)?
У нас есть только два вопроса,
касающихся списка l: это пустой
список или он содержит хотя бы
один непустой список?
Для чего нужна строка (else ...)?
См. выше, а также потому, что
последний вопрос – всегда else.
Что делает (cons)?
Конструирует список, как описывает вторая заповедь.
62
3. Cons великолепный
Для чего нужна строка
(firsts (cdr l))?
Чтобы просматривать S-выражения по одному. Для просмотра
оставшейся части списка требуется выполнить рекурсивный
вызов.
Для чего нужна строка )))?
Чтобы закрыть соответствующие
открывающие скобки
в (cond, (lambda и (define.
Они всегда присутствуют в конце
определений функций.
Опираясь на определение функции firsts, определите, какой
первый элемент в результирующем списке вернет (firsts l),
где
l имеет значение ((a b) (c d) (e f)).
a.
Какие другие элементы присутствуют в результате?
c и e.
Представьте себе функцию
seconds.
Какие элементы вернет
(seconds l),
где
l имеет значение ((a b) (c d) (e f))?
b, d и f.
Как бы вы описали первый элемент, возвращаемый применением функции (firsts l)?
Как car от первого элемента в
списке l – (car (car l)).
См. главу 1.
Отыскав очередной элемент
для помещения в результат, что
(firsts l) должна сделать с ним?
cons в результат рекурсивного
вызова – (firsts (cdr l)).
Третья заповедь
63
Третья заповедь
Конструируя список, опишите первый элемент, который должен быть помещен в результат, а затем добавьте
его с помощью cons в результат рекурсивного вызова.
Опираясь на третью заповедь,
мы можем дополнить определение функции firsts.
Как должна выглядеть последняя строка?
(else (cons (car (car l)) (firsts (cdr l)) )).
Что делает (firsts l):
Пока ничего.
Мы упустили один важный
ингредиент в нашем рецепте.
Первая строка ((null? l …) должна
вернуть значение в случае, когда
l – пустой список. Впрочем, пока
что мы можем обойтись без него.
(define firsts
(lambda (l)
(cond
((null? l) ...)
(else (cons (car (car l))
(firsts (cdr l))))))),
первый рекурсивный
элемент
вызов
где
l имеет значение ((a b) (c d) (e f))?
(null? l),
где
l имеет значение ((a b) (c d) (e f))?
Нет,
переходим к следующей строке.
Что делает
(cons (car (car l))
(firsts (cdr l)))?
Сохраняет значение (car (car l),
чтобы позднее с помощью cons
поместить его в (firsts (cdr l)). Чтобы найти значение (firsts (cdr l)),
мы вызываем функцию с новым
аргументом (cdr l).
(null? l),
где
l имеет значение ((c d) (e f))?
Нет,
переходим к следующей строке.
Что делает
(cons (car (car l))
(firsts (cdr l)))?
Сохраняет значение (car (car l) и
выполняет рекурсивный вызов
(firsts (cdr l)).
64
3. Cons великолепный
(null? l),
где
l имеет значение ((e f))?
Нет,
переходим к следующей строке.
Что делает
(cons (car (car l))
(firsts (cdr l)))?
Сохраняет значение (car (car l) и
выполняет рекурсивный вызов
(firsts (cdr l)).
(null? l)?
Да.
Какое значение теперь выдаст
выражение ((null? l) ...)?
Здесь не указано никакое значение. Именно это это мы упустили
из виду.
Куда функция cons должна помес
тить атом?
В список.
Вспомните закон cons.
Какое значение нужно выдать,
когда выполняется условие
(null? l), чтобы cons могла использовать его?
Конечное значение должно быть
списком, поэтому мы не можем
использовать #t или #f. Давайте
попробуем (quote ()).
После получения значения ()
выполняются три шага cons, чтобы вернуться обратно и собрать
результат:
I. либо
1. cons e в ()
2. cons c в (e)
3. cons а в (c e)
II. либо
1. cons а в (c e)
2. cons c в (e)
3. cons e в ()
III. либо
cons а в cons c в cons e в ().
Что в конечном итоге выдаст
(firsts l)?
(a c e).
Какая из трех альтернатив
кажется вам более понятной?
Теперь используйте ее в своей
практике.
Третья заповедь
65
Что выдаст (insertR new old lat),
где
new имеет значение помадкой,
old – сливочной
и
lat – (мягкое мороженое со сливочной на десерт)?
(мягкое мороженое со сливочной
помадкой на десерт).
Что выдаст (insertR new old lat),
где
new имеет значение халапеньо,
old – и
и
lat – (мексиканское тако сальса
и)?
(мексиканское тако сальса и халапеньо).
Что выдаст (insertR new old lat),
где
new имеет значение e,
old – d
и
lat – (a b c d f g h)?
(a b c d e f g h).
Опишите своими словами, что
делает применение функции
(insertR new old lat).
Вот наше описание:
«Функция insertR принимает
три аргумента: атомы new и
old и список атомов lat. Она
конструирует новый список,
вставляя в lat атом new правее
первого вхождения атома old».
Попробуйте самостоятельно
написать первые три строки
определения функции insertR.
Какой аргумент изменяется в
рекурсивных вызовах insertR?
(define insertR
(lambda (new old lat)
(cond ...)))
Список lat, потому что мы можем
просматривать содержащиеся в
нем атомы только по одному.
66
3. Cons великолепный
Сколько вопросов можно задать
о lat?
Два.
Является lat пустым или непус
тым списком атомов.
Какие конкретно вопросы нужно задать?
Первый вопрос: (null? lat).
Второй – else, потому что else –
всегда последний вопрос.
Что мы узнаем, если (null? lat)
выдаст ложное значение?
Что lat содержит по меньшей
мере один элемент.
Какие вопросы нужно задать о
первом элементе?
Первый вопрос: (eq? (car lat) old).
Второй вопрос: else, потому что
никакие другие случаи нас не
интересуют.
Теперь попробуйте написать пол
ное определение функции insertR.
Вот наша первая попытка.
(define insertR
(lambda (new old lat)
(cond
(_____ _____)
(else
(cond
(_____ _____)
(_____ _____))))))
Какое значение даст применение
только что определенной нами
функции (insertR new old lat),
где
new имеет значение помадкой,
old – сливочной
и
lat – (мягкое мороженое со сливочной на десерт)?
(define insertR
(lambda (new old lat)
(cond
((null? lat) (quote ()))
(else
(cond
((eq? (car lat) old) (cdr lat))
(else (cons (car lat)
(insertR new old
(cdr lat)))))))))
(мягкое мороженое со на десерт).
Третья заповедь
67
Эта версия действует подобно
rembrer.
Что нужно сделать в insertR, когда (eq? (car lat) old) дает истинное
значение?
Когда значения (car lat) и old совпадают, нужно справа от old вставить new.
Как это сделать?
Давайте попробуем применить
cons и добавить new в (cdr lat).
То есть мы получаем:
Да.
(define insertR
(lambda (new old lat)
(cond
((null? lat) (quote ()))
(else
(cond
((eq? (car lat) old)
(сons new (cdr lat)))
(else (cons (car lat)
(insertR new old
(cdr lat)))))))))?
Какое значение даст применение этой версии функции
(insertR new old lat),
где
new имеет значение помадкой,
old – сливочной
и
lat – (мягкое мороженое со сливочной на десерт)?
(мягкое мороженое со помадкой на
десерт).
Это верный результат?
Нет,
мы просто заменили сливочной
на помадкой.
Что еще мы должны сделать?
Мы должны включить в список
атом old перед атомом new.
Как включить в список атом old
перед атомом new?
Попробуем применить cons и
добавить old в (cons new в (cdr lat)).
68
3. Cons великолепный
Включим это изменение в определение функции insertR.
(define insertR
(lambda (new old lat)
(cond
((null? lat) (quote ()))
(else
(cond
((eq? (car lat) old)
(cons old
(сons new (cdr lat))))
(else (cons (car lat)
(insertR new old
(cdr lat)))))))))
Когда new имеет значение помадкой, old – сливочной и lat – (мягкое мороженое со сливочной на
десерт), то применение (insertR
new old lat) дает в результате
(мягкое мороженое со сливочной
помадкой на десерт). Если вы сделали все правильно, то получите
этот результат.
Теперь пробуйте написать определение функции insertL.
Подсказка: insertL вставляет атом new
слева от первого вхождения атома old в
списке lat.
Это было совсем несложно, верно?
(define insertL
(lambda (new old lat)
(cond
((null? lat) (quote ()))
(else (cond
((eq? (car lat) old)
(cons new
(cons old (cdr lat))))
(else (cons (car lat)
(insertL new old
(cdr lat )))))))))
Третья заповедь
69
Можно ли то же самое выразить
иначе?
Можно, например так:
((eq? (car lat) old)
(cons new (cons old (cdr lat))))
или так:
((eq? (car lat) old)
(cons new lat)),
потому что (cons old (cdr lat)), где
old совпадает с (car lat), – это тот
же самый lat.
Теперь пробуйте определить
функцию subst.
Очевидное решение:
Подсказка: (subst new old lat) заменяет
первое вхождение old в lat на new.
Например, если
new имеет значение помадкой,
old – сливочной
и
lat – (мягкое мороженое со сливочной на десерт),
то применение (subst new old lat)
даст значение (мягкое мороженое
со помадкой на десерт).
Смысл, думаю, вам понятен.
Теперь пробуйте определить
функцию subst2.
Подсказка: (subst2 new o1 o2 lat) заменяет
первое вхождение o1 или o2 в lat на new.
Например, если new имеет значение ванильное,
o1 – шоколадной,
o2 – банановое
и
lat – (банановое мороженое с
шоколадной крошкой), то применение (subst2 new o1 o2 lat)
даст значение (ванильное мороженое с шоколадной крошкой).
(define subst
(lambda (new old lat)
(cond
((null? lat) (quote ()))
(else (cond
((eq? (car lat) old)
(cons new (cdr lat)))
(else (cons (car lat)
(subst new old
(cdr lat)))))))))
Оно совпадает с одной из наших
неправильных попыток определить функцию insertR.
(define subst2
(lambda (new o1 o2 lat)
(cond
((null? lat) (quote ()))
(else (cond
((eq? (car lat) o1)
(cons new (cdr lat)))
((eq? (car lat) o2)
(cons new (cdr lat)))
(else (cons (car lat)
(subst2 new o1 o2
(cdr lat)))))))))
70
3. Cons великолепный
Можно ли то же самое выразить
иначе?
Можно, например заменить две
строки eq? (car lat) на
((or (eq? (car lat) o1) (eq? (car lat) o2))
(cons new (cdr lat))).
Определив последнюю функцию,
пойдите и сделайте себе бутерброд.
Вспомните, что делает функция
rember.
Напишите функцию
multirember, которая возвращает копию оригинального списка
lat, из которой удалены все
вхождения a.
(define muftirember
(lambda (a lat)
(cond
(_____ _____)
(else
(cond
(_____ _____)
(_____ _____))))))
Функция rember просматривает
каждый атом в списке lat и сравнивает его с заданным атомом a.
Если они не равны, то rember сохраняет атом и продолжает поиск.
Обнаружив первое вхождение a,
rember останавливает процесс
и выдает значение (cdr lat), т. е.
оставшуюся часть списка lat.
Таким образом, в результате возвращается копия оригинального списка lat без первого вхож
дения а.
(define mtiltirember
(lambda (a lat)
(cond
((null? lat) (quote ()))
(else
(cond
((eq? (car lat) a)
(multirember a (cdr lat)))
(else (cons (car lat)
(multirember a
(cdr lat))))))))
Третья заповедь
71
Подсказка: что нужно сделать, если
выражение (eq? (car lat) a) дает истинное
значение?
Возьмите для примера такие аргументы:
a – чашка
и
lat – (чайная чашка кофейная чашка и
деревенская чашка).
Обнаружив первое вхождение
a, мы тут же рекурсивно применяем (multirember (cdr lat)), чтобы
удалить другие вхождения.
В конечном результате получается значение (чайная кофейная и
деревенская).
Вы понимаете, как работает
multirermber?
Возможно нет,
поэтому давайте посмотрим,
какие шаги выполняются на пути
к конечному значению (чайная
кофейная и деревенская).
(null? lat)?
Нет,
поэтому переходим к следующей
строке.
else?
Да.
(eq? (car lat) a)?
Нет,
поэтому переходим к следующей
строке.
Что выдаст выражение
(cons (car lat)
(multirember a
(cdr lat)))?
Сохранит значение (car lat) –
кофейная, – чтобы позднее добавить в значение
(multirember a (cdr lat)).
Теперь определим, что выдаст
(multirember a (cdr lat)).
(null? lat)?
Нет,
поэтому переходим к следующей
строке.
else?
Естественно.
(eq? (car lat) a)?
Да,
поэтому забудьте (car lat) и определите (muitirember (cdr lat)).
72
3. Cons великолепный
(null? lat)?
Нет,
поэтому переходим к следующей
строке.
else?
Да!
(eq? (car lat) a)?
Нет,
поэтому переходим к следующей
строке.
Что выдаст выражение
(cons (car lat)
(multirember a
(cdr lat)))?
Сохранит значение
(car lat) – чайная,
– чтобы позднее добавить в значение (multirember a (cdr lat)).
Теперь определим, что выдаст
(multirember a (cdr lat)).
(null? lat)?
Нет,
поэтому переходим к следующей
строке.
else?
Да,
движемся дальше.
(eq? (car lat) a)?
Да,
поэтому забудьте (car lat) и определите (muitirember (cdr lat)).
(null? lat)?
Нет,
поэтому переходим к следующей
строке.
(eq? (car lat) a)?
Нет,
поэтому переходим к следующей
строке.
Что выдаст выражение
(cons (car lat)
(multirember a
(cdr lat)))?
Сохранит значение
(car lat) – и,
– чтобы позднее добавить в значение (multirember a (cdr lat)).
Теперь определим, что выдаст
(multirember a (cdr lat)).
Третья заповедь
73
(null? lat)?
Нет,
поэтому переходим к следующей
строке.
(eq? (car lat) a)?
Нет,
поэтому переходим к следующей
строке.
Что выдаст выражение
(cons (car lat)
(multirember a
(cdr lat)))?
Сохранит значение
(car lat) – деревенская,
– чтобы позднее добавить в значение (multirember a (cdr lat)).
Теперь определим, что выдаст
(multirember a (cdr lat)).
(null? lat)?
Нет,
поэтому переходим к следующей
строке.
(eq? (car lat) a)?
Да,
поэтому забудьте (car lat) и определите (muitirember (cdr lat)).
(null? lat)?
Да,
возвращаем результат ().
Мы закончили?
Нет,
нам осталось завершить еще
несколько вызовов cons.
Что делаем дальше?
Вставляем самый последний
результат (car lat) – деревенская –
в пустой список ().
Что дальше?
Вставляем и в список
(деревенская).
Что дальше?
Вставляем чайная в список
(и деревенская).
Что дальше?
Вставляем кофейная в список
(чайная и деревенская).
А теперь мы закончили?
Да.
74
3. Cons великолепный
Далее попробуйте определить
функцию muitiinsertR.
(define multiinsertR
(lambda (new old lat)
(cond
(_____ _____)
(else
(cond
(_____ _____)
(_____ _____))))))
(define multiinsertR
(lambda (new old lat)
(cond
((null? lat) (quote ()))
(else
(cond
((eq? (car lat) old)
(cons (car lat)
(cons new
(multiinsertR new old
(cdr lat)))))
(else (cons (car lat)
(multiinsertR new old
(cdr lat)))))))))
Также можно было бы использовать old вместо (car lat), потому
что мы знаем, что
(eq? (car lat) old).
Эта функция определена правильно?
(define multiinsertL
(lambda (new old lat)
(cond
((null? lat) (quote ()))
(else
(cond
((eq? (car lat) old)
(cons new
(cons old
(multiinsertL new old
lat))))
(else (cons (car lat)
(multiinsertL new old
(cdr lat)))))))))
Не совсем.
Чтобы узнать почему, попробуйте применить
(multiinsertL new old lat),
где
new имеет значение жаркое,
old – рыба,
lat – (картофель и рыба или рыба и
жаркое).
Третья заповедь
Достигается ли конечное условие?
Теперь пробуйте переписать определение функции
multiinsertL:
(define multiinsertR
(lambda (new old lat)
(cond
(_____ _____)
(else
(cond
(_____ _____)
(_____ _____))))))
75
Нет,
потому что функция никогда не
пройдет мимо первого вхождения old.
(define multiinsertL
(lambda (new old lat)
(cond
((null? lat) (quote ()))
(else
(cond
((eq? (car lat) old)
(cons new
(cons old
(multiinsertL new old
(cdr lat)))))
(else (cons (car lat)
(multiinsertL new old
(cdr lat)))))))))
76
3. Cons великолепный
Четвертая заповедь
(предварительная версия)
Всегда изменяйте хотя бы один аргумент в рекурсивном вызове. Аргумент должен изменяться так, чтобы
приблизиться к завершению. Изменяемый аргумент
должен проверяться в условии завершения:
используя cdr, проверяйте условие завершения с помо
щью null?.
Теперь попробуйте написать определение функции
multisubst.
(define multisubst
(lambda (new old lat)
(cond
(_____ _____)
(else
(cond
(_____ _____)
(_____ _____))))))
(define multisubst
(lambda (new old lat)
(cond
((null? lat) (quote ()))
(else (cond
((eq? (car lat) old)
(cons new
(multisubst new old
(cdr lat)))))
(else (cons (car lat)
(multisubst new old
(cdr lat)))))))))
4. Игры с числами
78
4. Игры с числами
14 – это атом?
Да,
потому что все числа – атомы.
Какое значение выдаст выражение (atom? n), истинное или ложное, если n имеет значение 14?
Истинное,
потому что 14 – это атом.
–3 – это число?
Да,
но мы не рассматриваем отрицательные числа.
3,14159 – это число?
Да,
но мы рассматриваем только
целые числа.
–3 и 3,14159 – это числа?
Да,
но мы будем использовать только неотрицательные целые числа
(т. е. 0, 1, 2, 3, 4…).
Какое значение выдаст
(add11 n),
где
n имеет значение 67?
68.
1
L: 1+.
S: (define add1
(lambda (n)
(+ 1 n))).
Какое значение выдаст
(add1 67)?
Тоже 68,
мы просто не говорим «где n
имеет значение 67», когда аргумент является числом.
Какое значение выдаст (sub11 n),
где
n имеет значение 5?
4.
1
L: 1–.
S: (define sub1
(lambda (n)
(– n 1))).
4. Игры с числами
Какое значение выдаст (sub1 0)?
Нет ответа1.
1
Какое значение выдаст выражение (zero?1 0), истинное или ложное?
1
79
(sub1 n), где n имеет значение 0, не имеет
ответа, потому что мы рассматриваем
только неотрицательные числа. Но на
практике это выражение выдаст –1.
Истинное.
L: zerop.
Какое значение выдаст выражение (zero? 1492), истинное или
ложное?
Ложное.
Какое значение выдаст выражение (+ 46 12)?
58.
Попробуйте написать функцию +.
(define +1
(lambda (n m)
(cond
((zero? m) n)
(else (add1 ( n (sub1 m)))))))
Подсказка: используйте zero? add1 и
sub11.
1
Это было несложно?
1
Не забудьте добавить наши определения add1 и sub1.
1
L, S: эта функция подобна встроенной
функции +, поэтому, определяя ее,
выберите имя +.
А мы не нарушили только что
первую заповедь?
Да,
но мы можем интерпретировать
zero? как null?, потому что zero?
спрашивает, пустое ли число, а
null? спрашивает, пустой ли список.
Если zero? можно считать аналогом null?, то можно ли считать
add1 аналогом cons?
Да!
cons конструирует списки,
а add1 – числа.
Что выдаст выражение (– 14 3)?
11.
80
4. Игры с числами
Что выдаст выражение (– 17 9)?
8.
Что выдаст выражение (– 18 25)?
Нет ответа.
Мы не рассматриваем отрицательные числа.
Попробуйте определить функцию.
Вот наш вариант:
(define –1
(lambda (n m)
(cond
((zero? m) n)
(else (sub1 (– n (sub1 m)))))))
Подсказка: используйте sub1.
1
L, S: эта функция подобна встроенной
функции -, поэтому, определяя ее,
выберите имя o-.
Попробуйте описать своими
словами, как работает (– n m).
Функция – принимает в качестве
аргументов два числа и уменьшает второе, пока оно не достигнет нуля. Она вычитает единицу
из результата столько раз, сколько потребовалось, чтобы второе
число уменьшилось до нуля.
Верно ли, что
(2 11 3 79 47 6) – это кортеж?
Да.
Верно ли, что
(8 55 5 555) – это кортеж?
Да,
конечно, а еще список чисел.
Верно ли, что
(1 2 8 apple 4 3) – это кортеж?
Нет,
это список атомов.
Верно ли, что
(3 (7 4) 13 9) – это кортеж?
Нет,
потому что это не список чисел.
(7 4) – это не число.
Верно ли, что
() – это кортеж?
Да,
это список, содержащий ноль
чисел. Это особый случай кортежа – пустой кортеж.
4. Игры с числами
81
Что выдаст выражение
(addtup tup),
где
tup имеет значение (3 5 2 8)?
18.
Что выдаст выражение
(addtup tup),
где
tup имеет значение (15 6 7 12 3)?
43.
Что делает addtup?
Конструирует число, складывая
все числа в аргументе.
Какой наиболее естественный
способ сконструировать число
из списка?
Использовать + вместо cons:
функция + конструирует числа
точно так же, как cons конструирует списки.
При конструировании списков с
помощью cons в условии завершения проверяется совпадение
со значением (). Какое значение
должно проверяться в условии
завершения в функции +?
0.
Как проверяется условие завершения при конструировании
списков?
(null? l).
Как проверяется условие завершения при конструировании
чисел из кортежей?
(null? tup).
Как должна выглядеть строка с
проверкой условия завершения
при конструировании числа из
списка чисел?
((null? tup) 0), по аналогии
с ((null? l) (quote ())) – строкой
проверки условия завершения
при конструировании списков.
Как выглядит строка проверки
условия завершения рекурсии в
addtup?
((null? tup) 0).
82
4. Игры с числами
Что такое список атомов lat?
Это или пустой список, или список, содержащий атом, (car lat) и
остальную часть (cdr lat), т. е. тоже
lat.
Что такое кортеж tup?
Это или пустой список, или список, содержащий число и остальную часть, т. е. тоже tup.
Какое выражение используется
в рекурсивном вызове при работе со списками?
(cdr lat).
Какое выражение используется
в рекурсивном вызове при работе с кортежами?
(cdr tup).
Почему?
Потому что остальная часть
непустого списка – список, а
остальная часть непустого кортежа – кортеж.
Сколько вопросов мы задаем о
списках?
Два.
Сколько вопросов мы задаем о
кортежах?
Два, потому что он может быть
пустым или содержать число и
остальную часть, которая сама
является кортежем.
Как определяется число?
Это либо ноль, либо единица,
прибавленная к остальной части,
где остальная часть – тоже число.
Как определяется условие завершения при конструировании
чисел?
((zero? n).
Как определяется рекурсивный
вызов при конструировании
чисел?
(sub1 n).
Сколько вопросов мы задаем
при конструировании чисел?
Два.
Первая заповедь (первая редакция)
83
Первая заповедь
(первая редакция)
Выполняя рекурсивный обход списка атомов, lat, задайте два вопроса: (null? lat) и else.
Выполняя рекурсивный обход чисел, для каждого чис
ла n задайте два вопроса: (zero? n) и else.
Что делает cons?
Конструирует списки.
Что делает addtup?
Конструирует числа, складывая
числа, содержащиеся в кортеже.
Как проверяется условие завершения рекурсии в addtup?
((null? tup) 0).
Как выполняется рекурсивный
вызов в addtup?
(addtup (cdr tup)).
Что использует addtup при
конструировании чисел?
Она использует +, потому что +
тоже конструирует числа!
Добавьте недостающий код в
следующем определении:
Вот наш вариант:
(+ (car tup) (addtup (cdr tup))).
(define addtup
(lambda (tup)
(cond
((null? tup) 0)
(else ……..))))
Обратите внимание, как эта строка похожа на последнюю строку в
определении функции rember:
(cons (car lat) (rember (cdr lat))).
Что выдаст выражение (× 5 3)?
15.
Что выдаст выражение (× 13 4)?
52.
Что делает (× n m)?
Конструирует число, прибавляя n
к самому себе m раз.
Как выглядит проверка условия
завершения рекурсии в ×?
((zero? m) 0), потому что n × 0 = 0.
84
4. Игры с числами
Поскольку (zero? m) является
условием завершения рекурсии,
то m в конечном итоге должно стать равным нулю. Какая
функция используется для этого
превращения?
sub1.
Четвертая заповедь
(первая редакция)
Всегда изменяйте хотя бы один аргумент в рекурсивном
вызове. Аргумент должен изменяться так, чтобы приблизиться к завершению. Изменяемый аргумент должен проверяться в условии завершения:
используя cdr, проверяйте условие завершения с
помощью null?
и
используя sub1, проверяйте условие завершения с
помощью zero?.
Что такое (× n (sub1 m)) в этом
случае?
Это рекурсивный вызов в ×.
Попробуйте определить функцию ×.
(define ×1
(lambda (n m)
(cond
((zero? m) 0)
(else (+ n (× n (sub1 m)))))))
1
L, S: подобна *.
Что выдаст выражение (× 12 3)?
36,
но давайте пройдемся по процессу выполнения функции и
посмотрим, как получается это
значение.
(zero? m)?
Нет.
Четвертая заповедь (первая редакция)
85
Что делает (+ n (× n (sub1 m)))?
Прибавляет n (где n = 12) к результату рекурсии.
Если × выполняется правильно,
то (× 12 (sub1 3)) должно дать 24.
Какие новые аргументы получает (× n m)?
n = 12 и m = 2.
(zero? m)
Нет.
Что делает (+ n (× n (sub1 m)))?
Прибавляет n (где n = 12) к результату (× n (sub1 m)).
Какие новые аргументы получает (× n m)?
n = 12 и m = 1.
(zero? m)?
Нет.
Что делает (+ n (× n (sub1 m)))?
Прибавляет n (где n = 12) к результату (× n (sub1 m)).
Какое значение выдаст выражение ((zero? m) 0)?
0, потому что (zero? m) теперь
даст истинное значение.
Мы закончили?
Нет.
Почему нет?
Потому что мы все еще должны
завершить три вызова +, чтобы
закончить сборку.
Какой результат вернет оригинальное применение функции?
Сложит 12, 12, 12 и 0 и вернет 36.
Обратите внимание, что число n
складывается m раз.
Докажите, используя уравнения, что × – обычное умножение
неотрицательных целых чисел,
(× 12 3) = 12 + (× 12 2)
= 12 + 12 + (× 12 1)
= 12 + 12 + 12 + (× 12 0)
= 12 + 12 + 12 + 0,
что является тем, чего мы ожидали. Эта методика работает
для всех рекурсивных функций,
не только для чисел. Вы можете
использовать данный подход для
определения функций и обсуж
дения их правильности.
где
n = 12 и m = 3.
86
4. Игры с числами
И снова: почему в проверке
условия завершения рекурсии
в × используется число 0?
Потому что 0 не влияет на +,
соответственно, n + 0 = n.
Пятая заповедь
Конструируя значение с помощью +, всегда используйте 0 как значение, возвращаемое строкой проверки
условия завершения рекурсии, потому что прибавление
0 не изменяет результата операции сложения.
Конструируя значение с помощью ×, всегда используйте 1 как значение, возвращаемое строкой проверки
условия завершения рекурсии, потому что умножение
на 1 не изменяет результата операции умножения.
Конструируя значение с помощью cons, всегда используйте () как значение, возвращаемое строкой проверки
условия завершения рекурсии.
Что выдаст (tup+ tup1 tup2),
где
tup1 имеет значение (3 6 9 11 4)
и
tup2 – значение (8 5 2 0 7)?
(11 11 11 11 11).
Что выдаст (tup+ tup1 tup2),
где
tup1 имеет значение (2 3)
и
tup2 – значение (4 6)?
(6 9).
Что делает (tup+ tup1 tup2)?
Складывает первое число в tup1
с первым числом в tup2, затем
складывает второе число в tup1
со вторым числом tup2 и т. д.,
конструируя кортеж ответов,
обрабатывая кортежи одинаковой длины.
Пятая заповедь
87
Что необычного в функции tup+?
Необычно то, что она просмат
ривает элементы двух кортежей
одновременно, иначе говоря,
выполняет рекурсивный обход
сразу двух кортежей.
Сколько вопросов нужно задать,
выполняя рекурсивный обход
одного кортежа?
Два: (null? tup) и else.
Сколько вопросов нужно задать,
выполняя рекурсивный обход
двух кортежей?
Четыре: пустой или непустой
первый кортеж и пустой или
непустой второй кортеж.
Имеются в виду вопросы:
(and (null? tup1) (null? tup2)),
(null? tup1),
(null? tup2)
и else?
Да.
Может ли первый кортеж быть
пустым кортежем (), а второй –
непустым?
Нет,
потому что кортежи должны
быть одинаковой длины.
Означает ли, что
(and (null? tup1) (null? tup2))
и
else
– единственные вопросы, которые мы должны задать?
Да,
потому что (null? tup1) дает истинное значение в тот же момент,
когда истинное значение дает
((null? tup2).
Напишите определение функции tup+.
(define tup+
(lambda (tup1 tup2)
(cond
((and (null? tup1) (null? tup2))
(quote ()))
(else
(cons (+ (car tup1) (car tup2))
(tup+
(cdr tup1) (cdr tup2))))))
88
4. Игры с числами
Какие аргументы получит +
в последней строке?
(car tup1) и (car tup2).
Какой аргумент получит cons
в последней строке?
(+ (car tup1) (car tup2))
и
(tup+ (cdr tup1) (cdr tup2))).
Что выдаст выражение
(tup+ tup1 tup2),
где
tup1 имеет значение (3 7)
и
tup2 – значение (4 6)?
(7 13).
Но давайте посмотрим, как оно
работает.
(null? tup1)?
Нет.
(cons
(+ (car tup1) (car tup2))
(tup+ (cdr tup1) (cdr tup2)))
cons 7 к результату рекурсии:
(tup+ (cdr tup1) (cdr tup2))).
Почему рекурсивный вызов
включает cdr обоих аргументов?
Потому, что первый элемент
конечного значения определяется как применение car к обоим
кортежам, теперь мы готовы рассмотреть остальные части обоих
кортежей.
(null? tup1),
где
tup1 имеет значение (7)
и
tup2 – значение (6)?
Нет.
(cons
(+ (car tup1) (car tup2))
(tup+ (cdr tup1) (cdr tup2)))?
cons 13 к результату рекурсии.
(null? tup1)?
Да.
Пятая заповедь
89
Какое значение должно вернуть
это выражение?
(),
потому что проверка (null? tup2)
должна дать истинный результат.
Что должно вернуть все применение функции?
(7 13).
То есть cons 7 к результату cons 13
к ().
Какая проблема возникает, если
(tup+ tup1 tup2),
где
tup1 имеет значение (3 7)
и
tup2 – значение (4 6 8 1)?
Нет ответа,
так как tup1 будет исчерпан
прежде, чем tup2.
Можно ли определить функцию
tup+ так, чтобы она объединяла
даже кортежи разной длины?
Да!
Какое новое условие завершения можно добавить, чтобы
получить правильное конечное
значение?
((null? tup1) tup2).
Что выдаст выражение (tup+ tup1
tup2),
где
tup1 имеет значение (3 7 8 1)
и
tup2 – значение (4 6)
Нет ответа, так как tup2 будет
исчерпан прежде, чем tup1.
См. первую заповедь: мы не задали всех
необходимых вопросов!
Но мы хотели бы получить конечное значение (7 13 8 1).
См. первую заповедь: мы не задали всех
необходимых вопросов!
Что нужно добавить в нашу
функцию?
Еще два вопроса:
(null? tup1) и (null? tup2).
Как должна выглядеть вторая
новая строка?
((null? tup2) tup1).
90
4. Игры с числами
Вот определение функции tup+,
способной
объединить
два
любых кортежа:
(define tup+
(lambda (tup1 tup2)
(cond
((and (null? tup1) (null? tup2))
(quote ()))
((null? tup1) tup2)
((null? tup2) tup1)
(else (cons (+ (car tup1) (car tup2))
(tup+
(cdr tup1) (cdr tup2)))))))
(define tup+
(lambda (tup1 tup2)
(cond
((null? tup1) tup2)
((null? tup2) tup1)
(else
(cons (+ (car tup1) (car tup2))
(tup+
(cdr tup1) (cdr tup2)))))))
Попробуйте упростить это определение.
Важен ли порядок проверки двух
условий завершения?
Нет.
Является ли else последним
вопросом?
Да,
потому что либо (null? tup1), либо
(null? tup2) даст истинное значение, если любой из кортежей не
содержит хотя бы одного числа.
Что выдаст выражение
(> 12 133)?
#f – false (ложь).
Что выдаст выражение
(> 120 133)?
#t – true (истина).
Для скольких чисел требуется
повторить рекурсивный вызов?
Для двух, n и m.
Как выглядят рекурсивные
вызовы?
(sub1 n) и (sub1 m).
Когда выполняется рекурсия?
Когда обнаруживается, что ни
одно из чисел не равно 0.
Сколько вопросов нужно задать
о числах n и m?
Три:
(zero? n), (zero? m) и else.
Пятая заповедь
91
Попробуйте определить >,
используя zero? и sub1.
Вот наш вариант:
Даст ли верный результат применение (> n m)?
Нет.
Попробуем, например, применить нашу функцию > к двум
одинаковым числам. Пусть m и n
имеют значение 3.
(zero? 3)?
Нет,
переходим к следующему вопросу.
(zero? 3)?
Нет,
переходим к следующему вопросу.
Что сделает выражение
(> (sub1 n) (sub1 m))?
Выполнит рекурсивные вызовы,
но с аргументами, уменьшенными на единицу.
(zero? 2)?
Нет,
переходим к следующему вопросу.
(zero? 2)?
Нет,
переходим к следующему вопросу.
Что сделает выражение
(> (sub1 n) (sub1 m))?
Выполнит рекурсивные вызовы,
но с аргументами, уменьшенными еще на одну единицу.
(zero? 1)?
Нет,
переходим к следующему вопросу.
(zero? 1)?
Нет,
переходим к следующему вопросу.
Что сделает выражение
(> (sub1 n) (sub1 m))?
Выполнит рекурсивные вызовы,
но с аргументами, уменьшенными еще на одну единицу.
(define >
(lambda (n m)
(cond
((zero? m) #t)
((zero? n) #f)
(else (> (sub1 n) (sub1 m))))))
92
4. Игры с числами
(zero? 0)?
Да,
поэтому выражение (> n m) даст
значение #t.
Это правильный результат?
Нет,
потому что 3 не больше 3.
Важен ли порядок проверки двух
условий завершения?
Подумайте над этим!
Важен ли порядок проверки двух
условий завершения?
Попробуйте!
Важен ли порядок проверки двух
предыдущих вопросов?
Да.
Сначала подумайте, а потом
попробуйте ответить.
Как можно изменить функцию >, чтобы решить эту
небольшую проблему?
Поменять местами строки с
zero?:
Что выдаст выражение (< 4 6)?
#t.
(< 8 3)?
#f.
(< 6 6)?
#f.
Попробуйте определить функцию <.
Вот наш вариант:
(define >
(lambda (n m)
(cond
((zero? n) #f)
((zero? m) #t)
(else (> (sub1 n) (sub1 m))))))
(define <
(lambda (n m)
(cond
((zero? m) #f)
((zero? n) #t)
(else (< (sub1 n) (sub1 m))))))
Пятая заповедь
Вот определение функции =:
93
Вот наш вариант:
(define =
(lambda (n m)
(cond
((zero? m) (zero? n))
((zero? n) #t)
(else (= (sub1 n) (sub1 m))))))
(define =
(lambda (n m)
(cond
((> n m) #f)
((< n m) #f)
(else #t))))
Перепишите его, используя < и >.
Означает ли это, что мы получили две разные функции для проверки равенства атомов?
Да,
так и есть: = для чисел и eq? для
остальных атомов.
(↑ 1 1)?
1.
(↑ 2 3)?
8.
(↑ 5 3)?
125.
Теперь попробуйте написать
определение функции ↑.
Вот наш вариант:
(define ↑1
(lambda (n m)
(cond
((zero? m) 1)
(else (× n (↑ n (sub1 m)))))))
Подсказка: смотрите первую и пятую
заповеди.
1
Какое имя вы дали бы следующей функции?
(define ???
(lambda (n m)
(cond
((< n m) 0)
(else (add1 (??? (– n m) m))))))
Что проверяет первый вопрос?
L, S: похоже на expt.
До сих пор нам не встречались
подобные определения; рекурсивный вызов выглядит немного
странно.
Меньше ли первый аргумент
второго.
94
4. Игры с числами
А что происходит во второй
строке?
Выполняется рекурсивный вызов
с первым аргументом, из которого вычитается второй, и к результату вызова прибавляется 1.
Что же делает эта функция?
Она подсчитывает, сколько раз
второй аргумент укладывается в
первый.
И что же что за функция?
Деление.
(define ÷
(lambda (n m)
(cond
((< n m) 0)
(else (add1 (÷ (– n m) m))))))
Что выдаст выражение (÷ 15 4)?
Число 3.
Как получается этот результат?
Простой вопрос:
(÷ 15 4) = 1 + (÷ 11 4)
= 1 + (1 + (÷ 7 4))
= 1 + (1 + (1 + (÷ 3 4)))
= 1 + (1 + (1 + 0)).
Неплохо было бы сейчас
(ветчину с сыром на ржаном хлебе)!
И не забудьте про горчицу!
Что выдаст выражение (length lat),
где
lat имеет значение
(хот-дог с горчицей капустой
и
солеными огурцами)?
7.
Пятая заповедь
Что выдаст выражение (length lat),
где
lat имеет значение
(ветчина и сыр на ржаном хлебе)?
6.
Теперь попробуйте написать
функцию length.
Вот наш вариант:
Что выдаст выражение (pick n lat),
где
n имеет значение 4
и
lat – значение (лазанья спагетти
равиоли макароны фрикадельки)?
макароны.
Что выдаст выражение
(pick 0 lat),
где
lat имеет значение (a)?
Нет ответа.
Попробуйте написать определение функции pick.
Вот наш вариант:
Что выдаст выражение
(rempick n lat),
где
n имеет значение 3
и
lat – значение (хот-дог с острой
горчицей)?
(хот-дог с горчицей).
95
(define length
(lambda (lat)
(cond
((null? lat) 0)
(else (add1 (len (cdr lat)))))))
(define pick
(lambda (n lat)
(cond
((zero? (sub1 n)) (car lat))
(else (pick (sub1 n) (cdr lat))))))
96
4. Игры с числами
Теперь попробуйте написать
определение функции rempick.
Вот наш вариант:
Что выдаст (number?1 a),
где
a имеет значение помидор?
#f.
1
(define rempick
(lambda (n lat)
(cond
((zero? (sub1 n)) (cdr lat))
(else (cons (car lat)
(rempick (sub1 n)
(cdr lat)))))))
L: numberp.
Что выдаст (number? 76)?
#t.
Сможете ли вы написать определение функции number?, которая
выдает #t, если получит числовой
атом, и #f в ином случае?
Нет:
number?, подобно add1, sub1,
zero?, car, cdr, cons, null?, eq? и
atom?, является примитивной
функцией.
Используя number?, напишите
определение функции no-nums,
которая выдает в результате
содержимое lat без чисел.
Например, для lat со значением
(5 груш 6 слив 9 фиников) выражение (no-nums lat) должно дать
(груш слив фиников).
Вот наш вариант:
(define no-nums
(lambda (lat)
(cond
((null? lat) (quote ()))
(else (cond
((number? (car lat))
(no-nums (cdr lat)))
(else (cons (car lat)
(no-nums
(cdr lat)))))))))
Пятая заповедь
97
Теперь напишите определение
функции all-nums, которая извлекает кортеж со всеми числами,
имеющимися в lat.
Вот наш вариант:
Напишите определение функции eqan?, которая дает #t, если
два ее аргумента (a1 и a2) – это
один и тот же атом. Не забывайте использовать = для чисел и eq?
для всех остальных атомов.
Вот наш вариант:
Можно ли обобщить все функции, использующие eq?, путем
замены eq? на eqan??
Да,
за исключением, конечно, самой
eqan?.
Теперь напишите определение
функции occur, которая подсчитывает, сколько раз встречается
атом a в lat.
Вот наш вариант:
(define occur
(lambda (а lat)
(cond
(_____ _____)
(else
(cond
(_____ _____)
(_____ _____))))))
(define all-nums
(lambda (lat)
(cond
((null? lat) (quote ()))
(else (cond
((number? (car lat))
(cons (car lat)
(all-nums (cdr lat))))
(else (all-nums (cdr lat))))))))
(define eqan?
(lambda (a1 a2)
(cond
((and (number? a1) (number? a2))
(= a1 a2))
((or (number? a1) (number? a2)) #f)
(else (eq? a1 a2)))))
(define occur?
(lambda (a lat)
(cond
((null? lat) 0)
(else
(cond
((eq? (car lat) a)
(add1 (occur a (cdr lat))))
(else (occur a (cdr lat))))))
98
4. Игры с числами
Напишите определение функции
one?,
где
(one? n) выдает #t,
если
n имеет значение 1,
и
#f (т. е. ложь) в противном случае.
Вот наш вариант:
Догадайтесь, как еще больше
упростить эту функцию, сделав
ее однострочной.
Удалив предложение (cond ...):
Теперь перепишите определение
функции rempick, которая удаляет n-й атом из lat.
Например, для
n со значением 3
и
lat со значением (лимон безе
соленый паштет)
Вот наш вариант:
выражение (rempick n lat) должно дать в результате (лимон безе
паштет).
Используйте функцию one? в
своем определении.
(define one?
(lambda (n)
(cond
((zero? n) #f)
(else (zero? (sub1 n))))))
или
(define one?
(lambda (n)
(cond
(else (= n 1)))))
(define one?
(lambda (n)
(= n 1)))
(define rempick
(lambda (n lat)
(cond
((one? n) (cdr lat))
(else (cons (car lat)
(rempick (sub1 n)
(cdr lat)))))))
5. *Б_же мой*: сколько звёзд!
100
5. *Б_же мой*: сколько звёзд!
Что выдаст выражение
(rember* a l),
где
a имеет значение чашка
и
l – значение ((кофейная) чашка
((чайная) чашка) (и (деревенская))
чашка)?
«rember*» читается как
«rember-звёздочка».
((кофейная)((чайная))(и (деревенс
кая))).
Что выдаст выражение
(rember* a l),
где
a имеет значение соус
и
l – значение (((томатный соус))
((фасолевый) соус) (и ((сметанный)) соус))?
(((томатный)),
((фасолевый))
(и ((сметанный)))).
Теперь попробуйте написать
определение функции rember*1.
Вот ее заготовка:
Вот наш вариант:
(define rember*
(lambda (a l)
(cond
( ________ ________ )
( ________ ________ )
( ________ ________ ))))
1
« ...*»
мой!».
заставляет нас думать «б_же
(define rember*
(lambda (a l)
(cond
((null? l) (quote ()))
((atom? (car l))
(cond
((eq? (car l) a)
(rember* a (cdr l)))
(else (cons (car l)
(rember* a (cdr l))))))
(else (cons (rember* a (car l))
(rember* a (cdr l)))))))
Примените
эту
функцию,
используя аргументы из одного из предыдущих примеров, и
посмотрите, как она работает.
Обратите внимание, что теперь
рекурсия выполняется не только
по cdr, но и по car списка.
5. *Б_же мой*: сколько звёзд!
(lat? l),
101
#f.
где
l имеет значение
(((томатный соус)), ((фасолевый)
соус) (и ((сметанный)) соус)).
Является ли значение
(car l) атомом,
Нет.
где
l имеет значение
(((томатный соус)), ((фасолевый)
соус) (и ((сметанный)) соус))?
Что выдаст выражение
(insertR* new old l),
где
new имеет значение жареный,
old имеет значение сурок
и
l – значение ((сколько (дров))
мог
((бы (напилить) сурок))
(((если)))
(бы (сурок) ((умел пилить)))
дрова)?
((сколько (дров))
мог
((бы (напилить) сурок жареный))
(((если)))
(бы (сурок жареный) ((умел пилить)))
дрова).
102
5. *Б_же мой*: сколько звёзд!
Теперь попробуйте написать
определение функции insertR*,
которая вставляет атом new правее атома old, где бы он ни встретился.
(define insertR*
(lambda (new old l)
(cond
( ________ ________ )
( ________ ________ )
( ________ ________ ))))
Чем похожи функции insertR* и
rember*?
Вот наш вариант:
(define insertR*
(lambda (new old l)
(cond
((null? l) (quote ()))
((atom? (car l))
(cond
((eq? (car l) old)
(cons old
(cons new
(insertR* new old
(cdr l)))))
(else (cons (car l)
(insertR* new old
(cdr l))))))
(else (cons (insertR* new old
(car l))
(insertR* new old
(cdr l)))))))
Обе они задают три вопроса.
Первая заповедь
(окончательный вариант)
При рекурсивном обходе списка атомов lat задавайте
два вопроса: (null? lat) и else.
При рекурсивном обходе числа n задавайте два вопроса: (zero? n) и else.
При рекурсивном обходе списка S-выражений l задавайте три вопроса: (null? l), (atom? (car l)) и else.
Чем похожи функции insertR* и
rember*?
Обе выполняют рекурсивный
вызов для car своего аргумента,
когда обнаруживается, что car
аргумента является списком.
Первая заповедь (окончательный вариант)
103
Чем
отличаются
функции
rember* и multirember?
Функция multirember не выполняет рекурсивный вызов для
car. Функция rember* выполняет рекурсивные вызовы и для
car, и для cdr. Она выполняет
рекурсивный вызов для car, когда обнаруживается, что car – это
список.
Чем похожи функции insertR* и
rember*?
Обе выполняют рекурсивный
вызов для car, когда обнаруживают, что car – это список, а также для cdr.
Чем похожи все функции со
звездочкой (*)?
Все они задают три вопроса и
выполняют рекурсивные вызовы и для car, и для cdr, когда
обнаруживают, что car – это
список.
Почему?
Потому что все функции со
звездочкой работают со списками, которые являются:
• либо пустыми;
• либо атомами, помещенными в список;
• либо списками, помещенными в список.
104
5. *Б_же мой*: сколько звёзд!
Четвертая заповедь
(окончательный вариант)
Выполняя рекурсивный вызов, всегда изменяйте хотя
бы один аргумент:
• при рекурсивном обходе списка атомов lat используйте (cdr lat);
• при рекурсивном обходе числа n используйте (sub1 n);
• при рекурсивном обходе списка S-выражений l используйте (car l) и (cdr l), если ни (null? l), ни (atom?
(car l)) не дали истинного значения.
Изменения должны приближать выполнение условия
завершения. Изменяемый аргумент должен проверяться
в условии завершения:
• при использовании cdr проверяйте условие завершения с помощью null?;
• при использовании sub1 проверяйте условие завершения с помощью zero?.
(occursomething a l),
где
a имеет значение банановый
и
l – значение
((сладкие)
(блюда ((((банановый лед)))
(банановый (крем))
банановый шербет))
(банановый)
(хлеб)
(банановый бренди))?
5.
Какое имя лучше подойдет для
функции occursomething?
occur*.
Четвертая заповедь (окончательный вариант)
Попробуйте написать определение occur*.
(define occur*
(lambda (a l)
(cond
( ________ ________ )
( ________ ________ )
( ________ ________ ))))
(subst* new old l),
где
new имеет значение апельсиновый,
old имеет значение банановый
и
l – значение
((сладкие)
(блюда ((((банановый лед)))
(банановый (крем))
банановый шербет))
(банановый)
(хлеб)
(банановый бренди))?
105
Вот наш вариант:
(define occur*
(lambda (a l)
(cond
((null? l) 0)
((atom? (car l))
(cond
((eq? (car l) a)
(add1 (occur* a (cdr l))))
(else (occur* a (cdr l)))))
(else (+ (occur* a (car l))
(occur* a (cdr l)))))))
((сладкие)
(блюда ((((апельсиновый лед)))
(апельсиновый(крем))
апельсиновый шербет))
(апельсиновый)
(хлеб)
(апельсиновый бренди))
106
5. *Б_же мой*: сколько звёзд!
Попробуйте написать определение subst*.
(define subst*
(lambda (new old l)
(cond
( ________ ________ )
( ________ ________ )
( ________ ________ ))))
Что выдаст выражение
(insertL * new old l),
где
new имеет значение дятел,
old имеет значение сурок
и
l – значение
((сколько (дров))
мог
((бы (напилить) сурок))
(((если)))
(бы (сурок) ((умел пилить)))
дрова)?
Вот наш вариант:
(define subst*
(lambda (new old l)
(cond
((null? l) (quote ()))
((atom? (car l))
(cond
((eq? (car l) old)
(cons new
(subst* new old (cdr l))))
(else (cons (car l)
(subst* new old
(cdr l))))))
(else
(cons (subst* new old (car l))
(subst* new old (cdr l)))))))
((сколько (дров))
мог
((бы (напилить) дятел сурок))
(((если)))
(бы (дятел сурок) ((умел пилить)))
дрова)
Четвертая заповедь (окончательный вариант)
Попробуйте написать определение insertL*.
(define insertL*
(lambda (new old l)
(cond
( ________ ________ )
( ________ ________ )
( ________ ________ ))))
107
Вот наш вариант:
(define insertL*
(lambda (new old l)
(cond
((null? l) (quote ()))
((atom? (car l))
(cond
((eq? (car l) old)
(cons new
(cons old
(insertL* new old
(cdr l)))))
(else (cons (car l)
(insertL* new old (cdr l))))))
(else (cons (insertL* new old
(car l))
(insertL* new old
(cdr l)))))))
(member* a l),
где
a имеет значение chips
и
l – значение ((картофельные)
(чипсы ((и) рыбные) (чипсы))))?
#t,
потому что атом чипсы присутст
вует в списке l.
Попробуйте написать определение member*.
Вот наш вариант:
(define insertL*
(lambda (new old l)
(cond
( ________ ________ )
( ________ ________ )
( ________ ________ ))))
(define member*
(lambda (a l)
(cond
((null? l) #f)
((atom? (car l))
(or (eq? (car l) a)
(member* a (cdr l))))
(else (or (member* a (car l))
(member* a (cdr l)))))))
108
5. *Б_же мой*: сколько звёзд!
Что выдаст выражение
(member* a l),
где
a имеет значение chips
и
l – значение ((картофельные)
(чипсы ((и) рыбные) (чипсы))))?
#t.
Какой атом чипсы будет найден?
((картофельные) (чипсы ((и) рыбные) (чипсы)))).
Что выдаст выражение
(leftmost l),
где
l имеет значение ((картофельные)
(чипсы ((и) рыбные) (чипсы))))?
картофельные.
Что выдаст выражение
(leftmost l),
тунец.
где
l имеет значение ((горячий)
(тунец (и))) сыр)
Что выдаст выражение
(leftmost l),
где
l имеет значение (((() четыре)) 17
(семнадцать))?
Нет ответа.
Что выдаст выражение
(leftmost (quote ())?
Нет ответа.
Опишите, что делает функция
leftmost.
Вот наше описание:
«Функция
leftmost
находит
самый левый атом в непустом
списке S-выражений, который
не содержит пустых списков».
Является ли leftmost * – функцией?
Она работает со списками
S-выражений, но выполняет
рекурсивные вызовы только для
car.
Четвертая заповедь (окончательный вариант)
109
Должна ли leftmost задавать все
три возможных вопроса?
Нет,
она должна задать всего два
вопроса. Мы согласились, что
leftmost работает только в отсутствие пустых списков в заданном
списке.
Попробуйте написать определение функции leftmost.
Вот наш вариант:
(define leftmost
(lambda (l)
(cond
( ________ ________ )
( ________ ________ ))))
(define leftmost
(lambda (l)
(cond
((atom? (car l)) (car l))
(else (leftmost (car l))))))
Помните ли вы, что делает
(or ...)?
(or ...) задает вопросы по одному,
пока не найдет тот, на который
получит истинный ответ. Затем
(or ...) останавливается и возвращает истинное значение. Если
аргумент, для которого получается истинный ответ, не будет
найден, то возвращается ложное
значение.
Что выдаст выражение
(and (atom? (car l))
(eq? (car l) x)),
где
x имеет значение пицца
и
l – значение (моцарелла пицца)?
#f.
Почему значение ложное?
Потому что (and ...) задает вопрос
(atom? (car l)), который дает
истинный ответ #t, а затем задается вопрос (eq? (car l) x), который
дает ложный ответ #f. Как результат общий ответ – #f.
110
5. *Б_же мой*: сколько звёзд!
Что выдаст выражение
(and (atom? (car l))
(eq? (car l) x)),
где
x имеет значение пицца
и
l – значение ((моцарелла грибы)
пицца)?
#f.
Почему значение ложное?
Потому что (and ...) задает вопрос
(atom? (car l)), но (car l) – не атом.
Как результат общий ответ – #f.
Приведите примеры значений x
и l, для которых
(and (atom? (car l))
(eq? (car l) x))
даст истинное значение.
Вот один пример:
x – пицца,
l – (пицца (хороша на вкус)).
Опишите своими словами, что
делает (and ...).
Вот наше описание:
«(and ...) задает вопросы по
одному, пока не найдет тот, на
который получит ложный ответ.
Затем (and ...) останавливается и возвращает ложное значение. Если аргумент, для которого получается ложный ответ, не
будет найден, то возвращается
истинное значение».
Может ли случиться так, что
операторы (and ...) и (or ...) про
анализируют не все аргументы1?
Да,
потому что (and ...) останавливается, встретив первый аргумент
со значением #f, а (or ...) останавливается, встретив первый аргумент со значением #t.
1
(cond ...) тоже может анализировать
не все свои аргументы. По этой причине ни (and ...), ни (or ...) нельзя
определить как функции в терминах
(cond ...), даже притом что (and ...)
и (or ...) можно выразить как сокращенные формы (cond ...)-выражения:
(and α β) = (cond (α β (else #f))
и
(or α β) = (cond (α #t (else β))
Четвертая заповедь (окончательный вариант)
111
(eqlist? l1 l2),
где
l1 имеет значение (клубничное
мороженое)
и
l2 – значение (клубничное мороженое)?
#t.
(eqlist? l1 l2),
где
l1 имеет значение (клубничное
мороженое)
и
l2 – значение (мороженое клубничное)?
#f.
(eqlist? l1 l2),
где
l1 имеет значение (сладкие
((блюда)))
и
l2 – значение ((сладкие) (блюда))?
#f.
(eqlist? l1 l2),
где
l1 имеет значение (говяжьи
((сосиски)) (и (газировка)))
и
l2 – значение (говяжьи ((сардельки)) (и (газировка)))?
#f, но почти #t.
(eqlist? l1 l2),
где
l1 имеет значение (говяжьи
((сосиски)) (и (газировка)))
и
l2 – значение (говяжьи ((сосис
ки)) (и (газировка)))?
#t. Так лучше.
Что такое eqlist??
Это функция, определяющая
равенство двух списков.
Какое максимальное количество
вопросов может задать eqlist?
Девять.
112
5. *Б_же мой*: сколько звёзд!
Попробуйте объяснить, почему может быть задано девять
вопросов.
Вот наше объяснение:
«Каждый аргумент может быть:
• пустым списком;
• атомом в списке;
• списком в списке.
Например, в то время как первый аргумент может быть
пустым списком, второй аргумент может быть пустым спис
ком, содержать атом или список
в позиции car».
Попробуйте определить eqlist?
через eqan?.
Вот наш вариант:
Правильно ли спрашивать (atom?
(car l2)) во втором вопросе?
Да,
потому что мы знаем, что второй
список не может быть пустым.
В противном случае первый
вопрос вернул бы истинное значение.
(define eqlist?
(lambda (l1 l2)
(cond
((and (null? l1) (null? l2)) #t)
((and (null? l1) atom? (car l2)))
#f)
((null? l1) #f)
((and (atom? (car l1)) (null? l2))
#f)
((and (atom? (car l1))
(atom? (car l2)))
(and (eqan? (car l1) (car l2))
(eqlist? (cdr l1) (cdr l2))))
((atom? (car l1)) #f)
((null? l2) #f)
((atom? (car l2)) #f)
(else
(and (eqlist? (car l1) (car l2))
(eqlist? (cdr l1) (cdr l2)))))))
Четвертая заповедь (окончательный вариант)
113
Почему третий вопрос –
(null? l1)?
К этому моменту мы знаем, что
если первый аргумент – пустой
список, то второй аргумент не
может быть пустым списком
или списком с атомом в первом
элементе. Если в этом случае
(null? l1) даст истинное значение,
то второй аргумент должен быть
списком, первый элемент которого также является списком.
Верно ли, что если первым аргументом является (), то eqlist?
выдаст #t только в одном случае.
Верно.
Чтобы выражение
(eqlist? (quote ()) l2) дало истинное
значение, аргумент l2 также должен быть пустым списком.
Означает ли это, что вопросов
Да.
Если в ответ на первый вопрос
будет дано истинное значение,
то eqlist? выдаст #t, в противном
случае она выдаст #f.
(and (null? l1) (null? l2))
и
(or (null? l1) (null? l2))
достаточно для определения
ответа в первых трех случаях?
Попробуйте определить eqlist?
иначе.
Вот наш вариант:
(define eqlist?
(lambda (l1 l2)
(cond
((and (null? l1) (null? l2)) #t)
((or (null? l1) (null? l2)) #f)
((and (atom? (car l1))
(atom? (car l2)))
(and (eqan? (car l1) (car l2))
(eqlist? (cdr l1) (cdr l2))))
((or (atom? (car l1))
(atom? (car l2)))
#f)
(else
(and (eqlist? (car l1) (car l2))
(eqlist? (cdr l1) (cdr l2)))))))
114
5. *Б_же мой*: сколько звёзд!
Что такое S-выражение?
S-выражение – это атом или (возможно, пустой) список S-выражений.
Сколько вопросов задает equal?,
чтобы определить равенство
двух S-выражений?
Четыре.
Первый аргумент может быть
атомом или списком S-выражений, и второй аргумент может
быть атомом или списком
S-выражений.
Попробуйте написать определение equal?.
Вот наш вариант:
Почему вторым задается вопрос
(atom? s1)?
Если он даст истинный ответ,
то мы будем знать, что первый
аргумент – атом, а второй – список.
Почему третьим задается вопрос
(atom? s2)?
К тому моменту, когда подходит черед задать третий вопрос,
нам известно, что первый аргумент – не атом. Поэтому, чтобы
отличить два остальных случая,
остается только выяснить, является ли второй аргумент атомом.
Первый аргумент должен быть
списком.
Можно ли объединить второй и
третий вопросы так:
(or (atom? s1) (atom? s2))?
Да, можно!
(define equal?
(lambda (s1 s2)
(cond
((and (atom? s1) (atom? s2))
(eqan? s1 s2))
((atom? s1) #f)
((atom? s2) #f)
(else (eqlist? s1 s2)))))
Четвертая заповедь (окончательный вариант)
Попробуйте упростить equal?.
115
Вот наш вариант:
(define equal?
(lambda (s1 s2)
(cond
((and (atom? s1) (atom? s2))
(eqan? s1 s2))
((or (atom? s1) (atom? s2))
#f)
(else (eqlist? s1 s2)))))
Функция equal? задает достаточно вопросов?
Да.
Попробуйте переписать определение eqlist? через equal?.
Вот наш вариант:
(define eqlist?
(lambda (l1 l2)
(cond
((and (null? l1) (null? l2)) #t)
((or (null? l1) (null? l2)) #f)
(else
(and (equal? (car l1) (car l2))
(eqlist? (cdr l1) (cdr l2)))))))
116
5. *Б_же мой*: сколько звёзд!
Шестая заповедь
Упрощайте только после того, как добились корректной
работы функции.
Вот версия rember, получив
шаяся после замены lat спис
ком l S-выражений и a – любым
S-выражением:
(define rember
(lambda (s l)
(cond
((null? l) (quote ()))
((atom? (car l))
(cond
((equal? (car l) s) (cdr l))
(else (cons (car l)
(rember s (cdr l))))))
(else (cond
((equal? (car l) s) (cdr l))
(else (cons (car l)
(rember s
(cdr l)))))))))
Очевидно же!
(define rember
(lambda (s l)
(cond
((null? l) (quote ()))
(else (cond
((equal? (car l) s) (cdr l))
(else (cons (car l)
(rember s
(cdr l)))))))))
Попробуйте упростить ее.
Чем они отличаются?
Теперь функция rember удаляет
первое соответствующее S-выражение s из l вместо первого соответствующего атома a в lat.
Является ли rember теперь
*-функцией?
Нет.
Почему?
Потому что rember передает в
рекурсивные вызовы только cdr l.
Шестая заповедь
117
Можно ли еще больше упростить
rember?
Да,
внутренний (cond ...) задает
вопросы, которые можно задать
во внешнем (cond ...)!
Попробуйте сделать это!
Вот наш вариант:
(define rember
(lambda (s l)
(cond
((null? l) (quote ()))
((equal? (car l) s) (cdr l))
(else (cons (car l)
(rember s (cdr l)))))))
Это определение проще?
Да, конечно!
И работает так же хорошо?
Да,
потому что мы знаем, что все
случаи и все рекурсивные вызовы обрабатывались и выполнялись правильно до упрощения.
Можно ли упростить insertL*
Нет, не получится.
Прежде чем задать вопрос
(eq? (car l) old), мы должны знать,
что (car l) является атомом.
Когда функции хорошо продуманы и работают правильно, мы
можем рассуждать о них спокойно.
И в этот раз это спасло нас от
ошибок.
Можно ли обобщить все функции, использующие eq? и =, заменив eq? и = функцией equal??
Не совсем. Такая замена не будет
работать в eqan?, но будет работать во всех остальных. На самом
деле, не обращая внимания на
тривиальный пример eqan?,
именно это мы и будем предполагать.
Здесь можно что-нибудь нарисовать
или оставить заметки.
6. Тени
120
6. Тени
1 – это арифметическое выражение?
Да.
3 – это арифметическое выражение?
Да, конечно.
1 + 3 – это арифметическое
выражение?
Да!
1 + 3 × 4 – это арифметическое
выражение?
Несомненно.
печенье – это арифметическое
выражение?
Да.
А вы были готовы к такому повороту?
А как насчет 3 ↑ y + 5?
Да.
Попробуйте дать определение
арифметического выражения.
Вот наше определение:
«В нашем случае арифметическое выражение – это либо атом
(включая числа), либо два арифметических выражения, объединенных знаками +, × или ↑».
Что выдаст выражение
(quote a)?
a.
Что выдаст выражение
(quote +)?
Атом +, не оператор +.
Что выдаст выражение
(quote ×)?
Атом ×, не оператор ×.
Что выдаст выражение
(eq? (quote a) y)?
#t.
Что выдаст выражение (eq? x y),
где
x имеет значение a
и
y – значение a?
Это тот же самый вопрос. И ответом на него тоже будет #t.
6. Тени
121
(n + 3) – это арифметическое
выражение?
На самом деле нет,
потому что имеются круглые
скобки, окружающие n + 3.
В нашем определении арифметического выражения круглые
скобки не упоминаются.
Можно ли рассматривать (n + 3)
как арифметическое выражение?
Да,
если помнить, что скобок на
самом деле нет.
Как бы вы назвали (n + 3)
Мы называем это представлением для n + 3.
Почему (n + 3) является хорошим
представлением?
Потому что:
1) (n + 3) является S-выражением и может служить аргументом функции;
2) структурно похоже на n + 3.
Что выдаст выражение
(numbered? x),
где
x имеет значение 1?
#t.
Как еще можно представить
3 + 4 × 5?
(3 + (4 × 5)).
Что выдаст выражение
(numbered? y),
где
y имеет значение (3 + (4 ↑ 5))?
#t.
Что выдаст выражение
(numbered? z),
где
z имеет значение (2 × сосиски)?
#f, потому что сосиски – это не
число.
Что такое numbered?
Это функция, которая определяет, содержит ли представление
арифметического
выражения
только числа, кроме знаков +, ×
и ↑.
122
6. Тени
Попробуйте написать структуру
numbered.
Вот наш вариант:
(define numbered?
(lambda (aexp)
(cond
(__________ __________)
(__________ __________)
(__________ __________)
(__________ __________))))
Это отличная догадка.
Каким будет первый вопрос?
(atom? aexp).
Что означает
(eq? (car (cdr aexp)) (quote +))?
Это второй вопрос.
Попробуйте угадать третий.
(eq? (car (cdr aexp)) (quote ×))
Угадать четвертый вы теперь
сможете без труда.
(eq? (car (cdr aexp)) (quote ↑)),
конечно.
Какие-то еще вопросы мы должны задать для aexp?
Нет!
Поэтому мы можем заменить
предыдущий вопрос на else.
Почему мы задаем четыре воп
роса, а не два?
Ведь такие арифметические
выражения, как (1 + 3), являются
списками атомов (lat)?
Потому что мы рассматриваем
(1 + 3) как представление арифметического выражения в форме
списка, а не как список.
И арифметическое выражение –
это либо число, либо два арифметических выражения, объединенных знаком +, × или ↑.
6. Тени
123
Теперь у вас есть все, чтобы
написать определение numbered.
Вот наш вариант:
Зачем задается вопрос (number?
aexp), когда выясняется, что
aexp – это атом?
Чтобы выяснить, все ли арифметические выражения, являющиеся атомами, одновременно являются числами.
Что нужно выяснить в случае,
если aexp состоит из двух арифметических выражений, объединенных знаком +?
Являются ли эти два подвыражения числами.
В какой позиции находится первое подвыражение?
car от aexp.
В какой позиции находится второе подвыражение?
car от cdr от cdr от aexp.
И что нужно спросить?
(numbered? (car aexp)) и
(numbered? (car (cdr (cdr aexp)))).
На оба вопроса ответом должно
быть значение #t.
Каким будет ответ на второй
вопрос?
(and (numbered? (car aexp))
(numbered? (car (cdr (cdr aexp)))))
(define numbered?
(lambda (aexp)
(cond
((atom? aexp) (number? aexp))
((eq? (car cdr aexp)) (quote +))
...)
((eq? (car (cdr aexp)) (quote ×))
...)
((eq? (car (cdr aexp)) (quote ↑))
...))))
124
6. Тени
Попробуйте дописать недостающие части в определении
numbered.
Вот наш вариант:
Понимая, что aexp – это арифметическое выражение, можно ли
определить numbered? проще?
Да.
Что позволяет сделать такое
упрощение?
Наличие заведомо верно работающей функции.
Что выдаст выражение (value u),
где
u имеет значение 13?
13.
(value x),
где
x имеет значение (1 + 3)?
4.
(define numbered?
(lambda (aexp)
(cond
((atom? aexp) (number? aexp))
((eq? (car (cdr aexp)) quote +)
(and (numbered? (car aexp))
(numbered?
(car (cdr (cdr aexp))))))
((eq? (car (cdr aexp)) quote ×)
(and (numbered? (car aexp))
(numbered?
(car (cdr (cdr aexp))))))
((eq? (car (cdr aexp)) quote ↑)
(and (numbered? (car aexp))
(numbered?
(car (cdr (cdr aexp)))))))))
(define numbered?
(lambda (aexp)
(cond
((atom? aexp) (number? aexp))
(else
(and (numbered? (car aexp))
(numbered?
(car (cdr (cdr aexp)))))))))
6. Тени
125
(value y),
где
y имеет значение (1 + (3 ↑ 4))?
82.
(value z),
где
z имеет значение печенье?
Нет ответа.
(value nexp) возвращает то, что
мы считаем естественным значением арифметического выражения.
Мы надеемся на это.
Сколько вопросов задает применение value nexp?
Четыре.
Попробуйте написать определение value.
Вот наш вариант:
Что такое «естественное значение» арифметического выражения, которое является числом?
Просто число.
Каково естественное значение
арифметического выражения,
состоящего из двух арифметических выражений, объединенных знаком +?
Взяв естественные значения
двух подвыражений, мы могли
бы просто сложить их.
Подумайте, как получить значения двух подвыражений
в (1 + (3 × 4)).
Поочередно применив value к 1 и
к (3 × 4).
(define value
(lambda (nexp)
(cond
((atom? nexp) ...)
((eq? (car (cdr nexp)) (quote +))
...)
((eq? (car (cdr nexp)) (quote ×))
...)
(else ...))))
126
6. Тени
Седьмая заповедь
Выполняйте рекурсивный обход частей, имеющих одинаковую природу:
• подсписков в списках;
• подвыражений в арифметических выражениях.
Попробуйте еще раз написать
определение value.
Вот наш вариант:
Можно ли придумать другое
представление арифметических
выражений?
Да, причем несколько.
Может ли (3 4 +)
представлять 3 + 4?
Да.
А (+ 3 4)?
Да.
А (plus 3 4)?
Да.
Является ли (+ (× 3 6) (↑ 8 2)) представлением арифметического
выражения?
Да.
(define value
(lambda (nexp)
(cond
((atom? nexp) nexp)
((eq? (car (cdr nexp)) (quote +))
(+ (value (car nexp))
(value (car (cdr (cdr nexp))))))
((eq? (car (cdr nexp)) (quote ×))
(× (value (car nexp))
(value (car (cdr (cdr nexp))))))
(else
(↑ (value (car nexp))
(value (car (cdr (cdr nexp)))))))))
Седьмая заповедь
Попробуйте написать определение функции value для арифметического выражения нового
вида, которое может быть:
• числом;
• списком с атомом +, за которым следуют два арифметических выражения;
• списком с атомом, за которым следуют два арифметических выражения;
• списком с атомом ↑, за которым следуют два арифметических выражения.
Вот наш вариант:
Это правильное определение?
Нет.
Попробуем его на примере.
(+ 1 3).
(atom? nexp),
где
nexp имеет значение (+ 1 3)?
Нет.
(eq? (car nexp) (quote +)),
где
nexp имеет значение (+ 1 3)?
Да.
А теперь рекурсия.
Да.
Что выдаст выражение (cdr nexp),
где
nexp имеет значение (+ 1 3)?
(1 3).
127
(define value
(lambda (nexp)
(cond
((atom? nexp) nexp)
((eq? (car nexp) (quote +))
(+ (value (cdr nexp))
(value (cdr (cdr nexp)))))
((eq? (car nexp) (quote ×))
(× (value (cdr nexp))
(value (cdr (cdr nexp)))))
(else
(↑ (value (cdr nexp))
(value (cdr (cdr nexp))))))))
128
6. Тени
(1 3) не является представлением арифметического выражения
в нашем понимании?
Нет,
нарушена седьмая заповедь.
(1 3) не является слагаемым,
представляющим арифметическое выражение! Причина в том,
что мы выполняем рекурсивный
обход по подспискам, но не все
списки являются представлениями арифметических выражений.
Мы должны выполнять рекурсивный обход по подвыражениям.
Как получить первое подвыражение из представления арифметического выражения?
Взяв car от cdr.
Является ли (cdr (cdr nexp)) арифметическим выражением,
где
nexp имеет значение (+ 1 3)?
Нет,
cdr от cdr – это (3), а (3) не является
арифметическим выражением.
Ошибка та же: мы работаем со
списком (+ 1 3), а не с представлением арифметического выражения.
Взяв car от cdr от cdr, мы вернемся на правильный путь.
Что мы получим, взяв car от cdr
от nexp?
Первое подвыражение в представлении арифметического
выражения.
Давайте напишем функцию
1st-sub-exp для арифметических
выражений.
Почему сразу же задается вопрос
else?
(define 1st-sub-exp
(lambda (aexp)
(cond
(else (car (cdraexp))))))
Потому что это первый и последний вопрос.
Седьмая заповедь
Можно ли обойтись без
(cond ...), если нет необходимости задавать вопросы?
129
Да,
вспомните одиночные функции
из главы 4.
(define 1st-sub-exp
(lambda (aexp)
(car (cdr aexp))))
Попробуйте написать определение функции 2nd-sub-exp для
арифметических выражений.
Вот наш вариант:
Наконец, давайте заменим
(car nexp) на (operator nexp).
Вот определение operator:
Теперь попробуйте обновить
определение функции value.
Вот наш вариант:
Можно ли применить эту функцию value к первому представлению арифметических выражений в этой главе?
Да,
изменив 1st-sub-exp и operator.
(define 2nd-sub-exp
(lambda (aexp)
(car (cdr (cdr aexp)))))
(define operator
(lambda (aexp)
(car aexp)))
(define value
(lambda (nexp)
(cond
((atom? nexp) nexp)
((eq? (operator nexp) (quote +))
(+ (value (1st-sub-exp nexp))
(value (2nd-sub-exp nexp))))
((eq? (operator nexp) (quote ×))
(× (value (1st-sub-exp nexp))
(value (2nd-sub-exp nexp))))
(else
(↑ (value (1st-sub-exp nexp))
(value (2nd-sub-exp nexp)))))))
130
6. Тени
Сделайте это!
(define 1st-sub-exp
(lambda (aexp)
(car aexp)))
(define operator
(lambda (aexp)
(car (cdr aexp))))
Это было просто?
Да,
потому что мы использовали
вспомогательные функции, чтобы скрыть отличительные особенности представления.
Восьмая заповедь
Используйте вспомогательные функции для абстрагирования от представлений.
Мы видели
раньше?
представления
Да,
просто не отмечали, что это
были представления.
Для каких сущностей мы
использовали представления?
Для значений истинности и
чисел!
Числа – это представления?
Да.
Например, 4 обозначает понятие «четыре». Мы выбрали этот
символ, потому что привыкли к
представлениям с применением арабских цифр.
Что еще мы могли бы использовать?
Например, (() () () ()). А как насчет
((((())))) или (IV)?
Помните, сколько примитивов
нам нужно для работы с числами?
Четыре: number?, zero?, add1 и
sub1.
Восьмая заповедь
Давайте попробуем другое
представление для чисел. Как
можно представить ноль?
Наш выбор: ().
Как можно представить единицу?
(()).
Как можно представить двойку?
(() ()).
Понятно? А тройку?
Тройка – это (() () ()).
Попробуйте написать функцию
для проверки на равенство
нулю.
Вот наш вариант:
Попробуйте написать функцию, аналогичную add1.
Вот наш вариант:
Как можно определить функцию sub1?
Вот наш вариант:
Они работают правильно?
Давайте посмотрим.
Что выдаст (zub1 n), где n имеет
значение ()?
Нет ответа, и это нормально.
Вспомните закон cdr.
Перепишем +, используя это
представление.
Изменилось ли определение
функции +?
131
(define sero?
(lambda (n)
(null? n)))
(define edd1
(lambda (n)
(cons (quote ()) n)))
(define zub1
(lambda (n)
(cdr n)))
(define +
(lambda (n m)
(cond
((sero? m) n)
(else (edd1 (+ n (zub1 m)))))))
И да, и нет.
Изменилось, но незначительно.
132
6. Тени
Помните определение lat??
Это просто:
(define lat?
(lambda (l)
(cond
((null? l) #t)
((atom? (car l)) (lat? (cdr l)))
(else #f))))
К чему этот вопрос?
Помните, какое значение дает
(lat? ls),
где
ls имеет значение (1 2 3)?
#t, конечно.
Как можно выразить (1 2 3),
используя наше новое представление чисел?
((()) (() ()) (() () ())).
Что выдаст (lat? ls),
где
ls имеет значение
((()) (() (() ()) (() ()())))?
#f, абсолютно точно.
Разве это плохо?
Остерегайтесь теней!
7. Друзья и отношения
134
7. Друзья и отношения
Является ли это множеством
(яблоко персик яблоко слива)?
Нет,
потому что яблоко встречается
более одного раза.
Что выдаст выражение (set? lat),
где
lat имеет значение (яблоки персики груши сливы)?
#t,
потому что ни один атом не
встречается более одного раза.
Что выдаст выражение (set? lat),
где
lat имеет значение ()?
#t,
потому что ни один атом не
встречается более одного раза.
Попробуйте написать определение функции set?.
Вот наш вариант:
Попробуйте упростить определение set?.
Вот как упростили мы:
Даст ли эта версия правильный
результат для примера списка
(яблоко 3 груша 4 9 яблоко 3 4)?
Да,
потому что member? теперь определена с использованием equal?
вместо eq?.
(define set?
(lambda (lat)
(cond
((null? lat) #t)
(else
(cond
((member? (car lat) (cdr lat))
#f)
(else (set? (cdr lat))))))))
(define set?
(lambda (lat)
(cond
((null? lat) #t)
((member? (car lat) (cdr lat)) #f)
(else (set? (cdr lat))))))
7. Друзья и отношения
135
Вас удивило присутствие функции member? в определении set??
Это не должно было вызвать
удивления, потому что мы уже
написали member? и теперь
можем использовать ее, когда
захотим.
Что выдаст выражение
(makeset lat),
где
lat имеет значение
(яблоко персик груша персик
слива лимон персик)?
(яблоко персик груша слива лимон).
Попробуйте написать определение функции makeset, используя
member?.
Вот наш вариант:
Вас удивило, насколько кратким
оказалось определение?
Надеемся, что нет. И да, она работает правильно.
Используя предыдущее определение, выясните, что выдаст
(makeset lat),
где
lat имеет значение
(яблоко персик груша персик
слива яблоко лимон персик).
(груша слива яблоко лимон персик).
(define makeset
(lambda (lat)
(cond
((null? lat) (quote ()))
((member? (car lat) (cdr lat))
(makeset (cdr lat)))
(else (cons (car lat)
(makeset (cdr lat)))))))
136
7. Друзья и отношения
Попробуйте написать определение функции makeset, используя
muttirember.
Вот наш вариант:
Используя это новое определение, выясните, что выдаст
(makeset lat),
где
lat имеет значение (яблоко персик груша персик слива яблоко
лимон персик).
(яблоко персик груша слива лимон).
Опишите своими словами, как
работает вторая версия makeset.
Вот наше описание:
«Функция makeset запоминает
первый атом в lat и cons его в
результат рекурсивного вызова
после удаления всех вхождений
первого атома из остальной
части lat».
Правильно ли обработает вторая
makeset в примере списка
(яблоко 3 груша 4 9 яблоко 3 4)?
Да,
потому что multirember теперь
определена с использованием
equal? вместо eq?.
Что выдаст выражение
(subset? set1 set2),
где
set1 имеет значение (5 куриные
крылышки)
и
set2 – значение (5 гамбургеры
2 жареные куриные и утиные
крылышки)?
#t,
потому что каждый атом в set1
присутствует также в set2.
(define makeset
(lambda (lat)
(cond
((null? lat) (quote ()))
(else (cons (car lat)
(makeset
(multirember (car lat)
(cdr lat))))))))
7. Друзья и отношения
Что выдаст выражение
(subset? set1 set2),
где
set1 имеет значение (4 фунта
хрена)
и
set2 – значение (четыре фунта
курицы и 5 фунтов хрена)?
#f.
Попробуйте написать определение функции subset?.
Вот наш вариант:
Попробуйте упростить subset?.
Вот наш вариант:
137
(define subset?
(lambda (set1 set2)
(cond
((null? set1) #t)
(else (cond
((member? (car set1) set2)
(subset? (cdr set1) set2))
(else #f))))))
(define subset?
(lambda (set1 set2)
(cond
((null? set1) #t)
((member? (car set1) set2)
(subset? (cdr set1) set2))
(else #f))))
Попробуйте написать определение функции subset? с использованием (and ...).
Вот наш вариант:
(define subset?
(lambda (set1 set2)
(cond
((null? set1) #t)
(else
(and (member? (car set1) set2)
(subset? (cdr set1) set2))))))
138
7. Друзья и отношения
Что выдаст выражение
(eqset? set1 set2),
где
set1 имеет значение (6 больших
цыпленков и крылышков)
и
set2 – значение (6 цыпленков и
больших крылышков)?
#t.
Попробуйте написать определение функции eqset?.
Вот наш вариант:
Попробуйте написать определение функции eqset? с одной
строкой cond.
Вот наш вариант:
Попробуйте написать
строчное определение.
Вот наш вариант:
одно-
Что выдаст выражение
(intersect? set1 set2),
где
set1 имеет значение (тушеные
помидоры и макароны)
и
set2 – значение (макароны и сыр)?
(define eqset?
(lambda (set1 set2)
(cond
((subset? set1 set2)
(subset? set2 set1)
(else #f))))
(define eqset?
(lambda (set1 set2)
(cond
(else (and (subset? set1 set2)
(subset? set2 set1))))))
(define eqset?
(lambda (set1 set2)
(and (subset? set1 set2)
(subset? set2 set1))))
#t,
потому что по крайней мере один
атом в set1 присутствует и в set2.
7. Друзья и отношения
Попробуйте написать определение функции intersect?.
Вот наш вариант:
Попробуйте упростить intersect?.
Вот наш вариант:
139
(define intersect?
(lambda (set1 set2)
(cond
((null? set1) #f)
(else
(cond
((member? (car set1) set2) #t)
(else (intersect?
(cdr set1) set2)))))))
(define intersect?
(lambda (set1 set2)
(cond
((null? set1) #f)
((member? (car set1) set2) #t)
(else (intersect? (cdr set1) set2)))))
Попробуйте написать определение функции intersect? с использованием (or ...).
Вот наш вариант:
(define intersect?
(lambda (set1 set2)
(cond
((null? set1) #f)
(else (or (member? (car set1) set2)
(intersect?
(cdr set1) set2))))))
Сравните subset? и intersect?.
Что выдаст выражение
(intersect set1 set2),
где
set1 имеет значение (тушеные
помидоры и макароны)
и
set2 – значение (макароны и сыр)?
(макароны и).
140
7. Друзья и отношения
Теперь попробуйте более короткую версию intersect.
Вот наш вариант:
Что выдаст выражение
(union set1 set2),
где
set1 имеет значение (тушеные
помидоры и макароны с запеканкой)
и
set2 – значение (макароны и сыр)?
(тушеные помидоры и макароны с
запеканкой и сыр).
Попробуйте написать определение функции union.
Вот наш вариант:
Что делает эта функция?
Вот наше описание:
«Эта функция возвращает все
атомы из set1, которых нет в
set2».
То есть xxx выдает разность множеств.
(define xxx
(lambda (set1 set2)
(cond
((null? set1) (quote ()))
((member? (car set1) set2)
(xxx (cdr set1) set2))
(else (cons (car set1)
(xxx (cdr set1) set2))))))
(define intersect
(lambda (set1 set2)
(cond
((null? set1) (quote ()))
((member? (car set1) set2)
(cons (car set1)
(intersect (cdr set1) set2)))
(else (intersect (cdr set1) set2)))))
(define union
(lambda (set1 set2)
(cond
((null? set1) set2)
((member? (car set1) set2)
(union (cdr set1) set2))
(else (cons (car set1)
(union (cdr set1) set2))))))
7. Друзья и отношения
141
Что выдаст выражение
(intersectall l-set),
где
l-set имеет значение
(((a b c) (c a d e) (e f g h a b))?
(a).
Что выдаст выражение
(intersectall l-set),
где
l-set имеет значение:
((6 груш и)
(3 персика и 6 перцев)
(8 груш и 6 персиков)
(и 6 груш с несколькими яблоками))?
(6 и).
Теперь, используя любые вспомогательные функции, напишите определение функции
intersectall, предполагая, что
список множеств не является
пустым.
Вот наш вариант:
(груша груша) – это пара1?
Да,
потому что этот список содержит
только два атома.
1
Пара (pair) в Scheme (или Lisp) – это два
разных, но связанных объекта.
(define intersectall
(lambda (l-set)
(cond
((null? (cdr l-set)) (car l-set))
(else (intersect (car l-set)
(intersectall (cdr l-set)))))))
(3 7) – это пара?
Да.
((2) (пара)) – это пара?
Да,
потому что этот список содержит
только два S-выражения.
(a-pair? l),
где
l имеет значение (полный (дом))?
#t,
потому что этот список содержит
только два S-выражения.
142
7. Друзья и отношения
Попробуйте написать определение функции a-pair?.
Вот наш вариант:
Как получить первое S-выражение из пары?
Взять car от пары.
Как получить второе S-выражение из пары?
Взять car от cdr от пары.
Как создать пару из двух атомов?
Объединить первый с объединением второго с пустым спис
ком (). То есть
(cons x1 (cons x2 (quote ())))).
Как создать пару из двух S-выражений?
Объединить первое с объединением второго с пустым спис
ком ().
То есть
(cons x1 (cons x2 (quote ())))).
Заметили ли вы различия между
двумя последними ответами?
Нет, таковых нет.
(define first
(lambda (p)
(coud
(else (car p)))))
(define second
(lambda (p)
(cond
(else (car (cdr p))))))
(define a-pair?
(lambda (x)
(cond
((atom? x) #f)
((null? x) #f)
((null? (cdr x)) #f)
((null? (cdr (cdr x))) #t)
(else #f))))
Для создания представлений пар
и для получения частей представлений пар. См. главу 6.
Они будут использоваться для
улучшения читабельности, как
вы скоро увидите.
Попробуйте переписать first,
second и build в виде однострочных версий.
7. Друзья и отношения
143
(define build
(lambda (s1 s2)
(cond
(else (cons s1
(cons s2 (quote ())))))))
Какое возможное применение
имеют эти три функции?
Попробуйте написать однострочное определение third.
Вот наш вариант:
l – это отношение (rel),
где
l имеет значение (яблоки персики тыквенный пирог)?
Нет,
потому что l не является списком
пар.
l – это отношение (rel),
где
l имеет значение
((яблоки, персики)
(тыквенный пирог)
(яблоки персики))?
Нет,
потому что l не является мно
жеством пар.
l – это отношение (rel),
где
l имеет значение
((яблоки персики)
(тыквенный пирог))?
Да.
l – это отношение (rel),
где
l имеет значение
((4 3) (4 2) (7 6) (6 2) (3 4))?
Да.
Является ли rel функцией,
где
rel имеет значение
((4 3) (4 2) (7 6) (6 2) (3 4))?
Нет.
(define third
(lambda (l)
(car (cdr (cdr l)))))
144
7. Друзья и отношения
Что выдаст выражение (fun? rel),
где
rel имеет значение
((8 3) (4 2) (7 6) (6 2) (3 4))?
#t,
потому что (firsts rel) – множество. См. главу 3.
Что выдаст выражение (fun? rel),
где
rel имеет значение
((d 4) (b 0) (b 9) (e 5) (g 4))?
#f,
потому что b повторяется.
Попробуйте написать определение функции fun?, используя set?
и firsts.
Вот наш вариант:
fun? – однострочная функция?
Да, конечно.
Как представить конечную функ
цию?
Для нас конечная функция – это
список пар, в котором нет пар с
совпадающими первыми элементами.
Что выдаст выражение (revrel rel),
где
rel имеет значение ((8 a)
(тыквенный пирог) (я заболел))?
((а 8) (пирог тыквенный) (заболел я)).
Попробуйте написать определение функции revrel.
Вот наш вариант:
(define fun?
(lambda (rel)
(set? (firsts rel))))
(define revrel
(lambda (rel)
(cond
((null? rel) (quote ()))
(else (cons (build
(second (car rel))
(first (car rel)))
(revrel (cdr rel)))))))
7. Друзья и отношения
Будет ли правильно работать
следующая функция?
(define revrel
(lambda (rel)
(cond
((null? rel) (quote ()))
(else (cons (cons
(car (cdr (car rel)))
(cons car (car rel))
(quote ())))
(revrel (cdr rel)))))))
Предположим, у нас есть функция revpair, которая меняет
местами два компонента пары
следующим образом:
(define revpair
(lambda (p)
(build (second p) (first p))))
Как можно определить функцию
revrel, используя эту вспомогательную функцию?
145
Да, но теперь можно заметить,
как представление способствует
читабельности.
Можно, и более того, новая версия читается легче:
(define revrel
(lambda (rel)
(cond
((null? rel) quote ())
(else (cons (revpair (car rel))
(revrel (cdr rel)))))))
Можете ли вы догадаться, почему fun не является fullfun,
где
fun имеет значение
((8 3) (4 2) (7 6) (6 2) (3 4))?
fun не является fullfun, так как 2
встречается более одного раза в
качестве второго элемента пары.
Почему #t является значением
(fullfun? fun),
где
fun имеет значение
((8 3) (4 8) (7 6) (6 2) (3 4))?
Потому что (3 8 6 2 4) – это множество.
146
7. Друзья и отношения
Что выдаст выражение
(fullfun? fun),
где
fun имеет значение
((виноград вяленый)
(сушеный чернослив)
(тушеный чернослив))?
#f.
Что выдаст выражение
(fullfun? fun),
где
fun имеет значение
((виноград вяленый)
(сушеный чернослив)
(тушеный виноград))?
#t,
потому что (вяленый чернослив
виноград) – это множество.
Попробуйте написать определение функции fullfun?.
Вот наш вариант:
Как можно записать определение функции seconds?
Так же, как firsts.
Какое другое имя можно дать
функции fullfun?
one-to-one?.
Как по-иному можно определить функцию one-to-one?
Вот наш вариант:
Является ли ((шоколадная крошка) (песочное печенье)) функцией
one-to-one?
Да,
и вы заслужили это сейчас!
(define fullfun?
(lambda (fun)
(set? (seconds fun))))
(define one-to-one?
(lambda (fun)
(fun? (revrel fun))))
7. Друзья и отношения
Сходите и купите себе печенья!
Или, что лучше, испеките его сами!
(define cookies
(lambda ()
(bake
(quote (350 градусов))
(quote (12 минут))
(mix
(quote (орехи 1 стакан))
(quote (шоколад 16 унций))
(mix
(mix
(quote (мука 2 стакана))
(quote (овсяная мука 2 стакана))
(quote (соль .5 чайной ложки))
(quote (разрыхлитель 1 чайная ложка))
(quote (сода 1 чайная ложка)))
(mix
(quote (2 больших яйца))
(quote (ванилин 1 чайная ложка))
(cream
(quote (масло сливочное 200 грамм))
(quote (сахар 2 стакана)))))))))
147
Здесь можно что-нибудь нарисовать
или оставить заметки.
8. Lambda повсюду
150
8. Lambda повсюду
Как мы изменили rember и insertL
в конце главы 5?
Заменили eq? на equal?.
Сможете ли вы самостоятельно
определить функцию rember-f
с использованием eq? или equal??
Нет,
потому что мы еще не рассказали
вам, как это сделать.
Как заставить rember удалить
первое значение a из (b c a)?
Передав функции rember
аргументы a и (b c a).
Как заставить rember удалить
первое значение c из (b c a)?
Передав функции rember
аргументы c и (b c a).
Как заставить функцию rember-f
использовать equal? вместо eq??
Передав equal? в виде аргумента
в применение rember-f.
Что выдаст выражение
(rember-f test? a l),
где
test? – это =1,
a имеет значение 5
и
l – значение (6 2 5 3)?
(6 2 3).
1
L: (rember-f (function =) 5 ‘(6 2 5 3)),
но это еще не все.
Что выдаст выражение
(rember-f test? a l),
где
test? – это eq?,
a имеет значение мармеладное
и
l – значение (мармеладное драже очень вкусное)?
(драже очень вкусное).
Что выдаст выражение
(rember-f test? a l),
где
test? – это equal?,
a имеет значение (поп-корн)
и
l – значение (лимонад (поп-корн)
и (торт))?
(лимонад и (торт)).
8. Lambda повсюду
Попробуйте написать определение функции rember-f.
151
Вот наш вариант:
(define rember-f
(lambda (test? a l)
(cond
((null? l) (quote ()))
(else (cond
(test? (car l) a)1 (cdr l))
(else (cons (car l)
(rember-f test? a
(cdr l)))))))))
Отлично!
1
L: (funcall test? (car 1) a). Используйте
funcall для вызова функции в аргументе
или функции, которая не была определена с помощью define.
Попробуйте написать более
короткую версию.
Вот наш вариант:
Как действует (rember-f test? a l),
где
test? – это eq??
(rember-f test? a l),
где
test? – это eq?, действует как
rember.
А как действует (rember-f test? a l),
где
test? – это equal??
Так же как rember, но использующая equal? вместо eq?.
Теперь у нас есть четыре функции, которые делают почти одно
и то же.
Да:
•
•
•
•
(define rember-f
(lambda (test? a l)
(cond
((null? l) (quote ()))
((test? (car l) a) (cdr l))
(else (cons (car l)
(rember-f test? a
(cdr l)))))))
rember с =;
rember с equal?;
rember с eq?;
rember-f.
152
8. Lambda повсюду
И rember-f может действовать
так же, как и все остальные.
Давайте сгенерируем все версии
с помощью rember-f.
Какие значения могут возвращать функции?
Списки и атомы.
А могут ли они возвращать
функции?
Да,
но вы, скорее всего, не знали об
этом.
Можете ли вы сказать, что такое
(lambda (a l) ...)?
(lambda (a l) ...) – это функция с
двумя аргументами, a и l.
А теперь скажите-ка, что такое
Это функция, которая принимает
аргумент a и возвращает функцию
(lambda (x)
(eq? x a)),
где
a – аргумент родительской функции.
(lambda (a)
(lambda (x)
(eq? x a)))?
Это называется «карринг»?
Спасибо вам, Моисей Эльевич
Шейнфинкель (1889–1942).
Это не называется «шейнфинкелинг».
Спасибо вам, Хаскелл Б. Карри
(1900–1982).
Определите предыдущую функцию, используя (define ...).
Вот наш вариант:
(define eq?-c1
(lambda (a)
(lambda (x)
(eq? x a))))
1
Что выдаст выражение (eq?-c k),
где
k имеет значение салат?
L:
(defun eq?-c (a)
(function
(lambda (y)
(eq y a))))
Это выражение выдаст функцию,
которая принимает аргумент k
и вызывает eq?, чтобы сравнить
аргумент с атомом салат.
8. Lambda повсюду
Давайте напишем для нее определение (define ...)
153
Хорошо.
(define1 eq?-salad (eq?-c k))
где
k имеет значение салат.
1
L: (setq eq?-salad (eq?-c ‘salad)).
Используйте setq для определения
функции, которую можно вызвать.
Что выдаст выражение
(eq?-salad y)1,
где
y имеет значение салат.
1
#t.
L: (funcall eq?-salad y), поскольку eq?salad не была определена с помощью
define.
Что выдаст выражение
(eq?-salad y),
где
y имеет значение рыбный?
#f.
Нужно ли давать имя функции
eq?-salad?
Нет, мы можем с тем же успехом
спросить ((eq?-c x) y)1,
где
x имеет значение салат
и
y – значение рыбный.
1
Теперь перепишите определение rember-f в виде функции
одного аргумента test?, которая
возвращает функцию, действующую подобно rember с eq?
вместо test?
L: (funcall (eq?-c x) y), потому что (eq?c x) – это функция, которая не была
определена с помощью define.
Вот наш вариант:
(define rember-f
(lambda (test?)
(lambda (a l)
(cond
((null? l) (quote ()))
((test? (car l) a) (cdr l))
(else (cons (car l) ...))))))
154
8. Lambda повсюду
Опишите
своими
словами
результат (rember-f test?),
где
test? – это eq?.
Дайте имя функции, возвращаемой вызовом (rember-f test?),
где
test? – это eq?.
Эта функция принимает два
аргумента, a и l. Сравнивает элементы списка l со значением a и
удаляет первый встретившийся
элемент, равный a.
(define rember-eq? (rember-f test?))
где
test? – это eq?.
Что выдаст выражение
(rember-eq? a l),
где
a имеет значение рыбный
и
l – значение (рыбный салат это
вкусно)?
(салат это вкусно).
Так ли необходимо давать имя
rember-eq? функции
(rember-f test?),
где
test? – это eq??
Нет,
можно просто написать
(((rember-f test?) a l),
где
test? – это eq?,
a – рыбный
и
l – (рыбный салат это вкусно).
Теперь заполните строку
(cons (car l) ...) в определении
rember-f, чтобы она заработала.
(define rember-f
(lambda (test?)
(lambda (a l)
(cond
((null? l) (quote ()))
((test? (car l) a) (cdr l))
(else (cons (car l)
((rember-f test?) a
(cdr l))))))))
8. Lambda повсюду
Что выдаст выражение
((rember-f eq?) a l),
где
a имеет значение рыбный
и
l – значение (салат с креветками
и рыбный салат).
(салат с креветками и салат).
Что выдаст выражение
((rember-f eq?) a l),
где
a имеет значение eq?
и
l – (equal? eq? eqan? eqlist?
eqpair?)1?
(equal? eqan? eqlist? eqpair?).
1
155
Заметили разницу между eq? и eq??
Первое – это атом, а второе – функция.
А теперь попробуйте преобразовать insertL в insertL-f, следуя
аналогии с rember и rember-f.
Вот наш вариант:
(define insertL-f
(lambda (test?)
(lambda (new old l)
(cond
((null? l) (quote ()))
((test? (car l) old)
(cons new (cons old (cdr l))))
(else (cons (car l)
((insertL-f test?) new old
(cdr l))))))))
156
8. Lambda повсюду
И для закрепления навыка проделайте то же самое с insertR.
Вот наш вариант:
Похожи ли insertR и insertL?
Да,
но есть небольшое отличие в
середине.
Можно ли определить функцию
insert-g, которая будет производить вставку слева или справа, в
зависимости от значения дополнительного аргумента?
Если есть возможность, купите
себе кофе и расслабьтесь! Если
нет, то не сдавайтесь. Вы увидите
такую функцию чуть ниже.
Какие части функций отличаются?
В insertL используются строки:
((eq? (car l) old)
(cons new (cons old (cdr l)))),
а в insertR:
((eq? (car l) old)
(cons old (cons new (cdr l)))).
Выразите разницу своими словами!
Функции применяют cons к old и
new в разном порядке, добавляя
их в cdr списка l.
Как можно избавиться от различий?
Вы, наверное, догадались: путем
передачи функции, выражающей
порядок применения cons.
(define insertR-f
(lambda (test?)
(lambda (new old l)
(cond
((null? l) (quote ()))
((test? (car l) old)
(cons old (cons new (cdr l))))
(else (cons (car l)
((insertR-f test?) new old
(cdr l))))))))
8. Lambda повсюду
157
Попробуйте определить функцию seqL, которая
1) принимает три аргумента;
2) применяет cons для вставки
первого аргумента в результат
применения cons для вставки
второго аргумента в третий
аргумент.
Вот наш вариант:
Что делает эта функция?
Эта функция:
1) принимает три аргумента;
2) применяет cons для вставки
второго аргумента в результат
применения cons для вставки
первого аргумента в третий
аргумент.
(define seqR
(lambda (new old l)
(cons old (cons new l))))
(define seqL
(lambda (new old l)
(cons new (cons old l))))
Знаете, зачем мы определили
эти функции?
Они выражают отличающиеся
строки в insertL и insertR.
Попробуйте написать определение функции insert-g одного
аргумента seq, которая возвращает insertL, если seq – это seqL,
и возвращает insertR, если seq –
это seqR.
Вот наш вариант:
Теперь попробуйте определить
insertL через insert-g.
Вот наш вариант:
Теперь попробуйте определить
insertR через insert-g.
Вот наш вариант:
(define insert-g
(lambda (seq)
(lambda (new old l)
(cond
((null? l) (quote ()))
((eq? (car l) old)
(seq new old (cdr l)))
(else (cons (car l)
((insert-g seq) new old
(cdr l))))))))
(define insertL (insert-g seqL))
(define insertR (insert-g seqR))
158
8. Lambda повсюду
Есть ли что-то необычное в этих
двух определениях?
Да.
Раньше мы, скорее всего, написали бы
(define insertL (insert-g seq)),
где
seq – это seqL,
и
(define insertR (insert-g seq)),
где
seq – это seqR.
Но слово «где» совсем необязательно использовать в отношении передачи функции в аргументе.
Так ли необходимо давать имена
функциям seqL и seqR?
Нет.
Мы могли бы вместо имен передавать их определения.
Попробуйте снова определить
insertL через insert-g, но на этот
раз без передачи seqL.
Вот наш вариант:
Такой способ лучше?
Да,
потому что не требует запоминать так много имен. Вы можете просто (rember func-name «из
вашей памяти»),
где
func-name – это seqL.
(define insertL
(insert-g
(lambda (new old l)
(cons new (cons old l)))))
8. Lambda повсюду
Вспомните определение subst.
159
Вот оно:
(define subst
(lambda (new old l)
(cond
((null? l) (quote ()))
((eq? (car l) old)
(cons new (cdr l)))
(else (cons (car l)
(subst new old (cdr l)))))))
Ничего не напоминает?
Да, оно похоже на определение
insertL или insertR. Отличается
только ответом во второй строке
cond.
Попробуйте определить функцию, подобную seqL или seqR для
subst.
Как вам такой вариант?
А теперь попробуйте определить
subst через insert-g.
Вот наш вариант:
Что делает функция yyy?
Сюрприз! Это наша старая знакомая rember.
(define yyy
(lambda (a l)
((insert-g seqrem) #f a l))),
где
(define seqrem
(lambda (new old l)
l))
(define seqS
(lambda (new old l)
(cons new l)))
(define subst (insert-g seqS))
Подсказка: пройдитесь через вычисления для (yyy a l),
где
a имеет значение колбасой
и
l – значение (пицца с колбасой и беконом).
Какую роль играет #f?
Вы только что воочию увидели силу абстракции.
160
8. Lambda повсюду
Девятая заповедь
Абстрагируйте общие шаблоны, определяя новые функции.
Встречались ли подобные функции нам раньше?
Да, мы даже видели функции с
похожими строками.
Помните определение value из
главы 6?
Вот оно:
Здесь есть похожие строки?
Последние три ответа одинаковые, за исключением +, × и ↑
Попробуйте написать определение функции atom-to-function,
которая:
1) принимает один аргумент x;
2) возвращает функцию +,
если (eq? x (quote +)),
возвращает функцию ×
если (eq? x (quote ×)), и
возвращает функцию ↑ в противном случае.
Вот наш вариант:
(define value
(lambda (nexp)
(cond
((atom? nexp) nexp)
((eq? (operator nexp)
(quote +))
(+ (value (1st-sub-exp nexp))
(value (2nd-sub-exp nexp))))
((eq? (operator nexp)
(quote ×))
(× (value (1st-sub-exp nexp))
(value (2nd-sub-exp nexp))))
(else
(↑ (value (1st-sub-exp nexp))
(value (2nd-sub-exp nexp)))))))
(define atom-to-function
(lambda (x)
(cond
((eq? x (quote +) +)
((eq? x (quote ×) ×)
(else ↑))))
Девятая заповедь
Что выдаст выражение
(atom-to-function (operator nexp)),
где
nexp – это (+ 5 3)?
Функцию +, а не атом +.
Можно ли через
atom-to-function определить
функцию value, используя только две строки cond?
Конечно:
161
(define value
(lambda (nexp)
(cond
((atom? nexp) nexp)
(else
((atom-to-function
(operator nexp))
(value (1st-sub-exp nexp))
(value (2nd-sub-exp nexp)))))))
Она получилась намного короче Да,
предыдущей версии?
и это нормально. Мы не изменили ее смысл.
Не пора ли отведать яблока?
Один раз в день, и вы обойдетесь без докторов.
Вспомним определение
multirember:
Нет проблем:
(define multirember
(lambda (a lat)
(cond
((null? lat) (quote ()))
((eq? (car lat) a)
(multirember a (cdr lat)))
(else (cons (car lat)
(multirember a
(cdr lat)))))))
Попробуйте написать определение multirember-f.
(define multirember-f
(lambda (test?)
(lambda (a lat)
(cond
((null? lat) (quote ()))
((test? a (car lat))
((multirember-f test?) a
(cdr lat)))
(else (cons (car lat)
((multirember-f test?) a
(cdr lat))))))))
162
8. Lambda повсюду
Что выдаст выражение
(салат с креветками салат и).
((multirember-f test?) a lat),
где
test? – это eq?,
a – рыбный
и
lat – (салат с креветками рыбный
салат и рыбный)?
Это было просто?
Да.
Попробуйте написать определение функции multirember-eq?,
использующей multirember-f.
Вот наш вариант:
(define multirember-eq?
(multirember-f test?))
где test? – это eq?.
Действительно ли нужно передавать функции multirember-f
аргумент рыбный?
Поскольку multirember-f просмат
ривает все элементы в lat, она
обязательно найдет рыбный.
Изменяется ли test? по мере
того, как multirember-f выполняет обход lat?
Нет,
test? означает eq?, так же как a
всегда означает рыбный.
Можно ли объединить a и test??
Да,
test? может быть функцией
только одного аргумента и сравнивать этот аргумент с рыбный.
Как это можно сделать?
Новая версия test? принимает
один аргумент и сравнивает его
с рыбный.
Вот одно из возможных определений этой функции:
Вот другой способ:
(define eq?-tuna
(eq?-c k)),
где k имеет значение рыбный.
Попробуйте придумать другой
способ определения этой функции.
(define eq?-tuna
(eq?-c (quote рыбный)))
Девятая заповедь
Вы когда-нибудь видели определения функций, содержащие
атомы?
163
Да,
0, (quote ×), (quote +) и многие
другие.
На самом деле это несложно:
Возможно, теперь следует
написать функцию multiremberT,
(define multiremberT
похожую на multirember-f.
(lambda (test? lat)
Вместо того чтобы принимать
(cond
test? и возвращать функцию,
((null? lat) (quote ()))
multiremberT принимает функ((test? (car lat))
цию вида eq?-tuna и lat, а затем
(multiremberT test? (cdr lat)))
выполняет свою работу.
(else (cons (car lat)
(multiremberT test?
(cdr lat)))))))
Что выдаст выражение
(multiremberT test? lat),
где test? – это eq?-tuna
и lat – (салат с креветками рыбный салат и рыбный)?
(салат с креветками салат и).
Так просто?
Почти.
А как вам такой вариант?
Он выглядит очень сложным!
(define multirember&co
(lambda (a lat col)
(cond
((null? lat)
(col (quote ()) (quote ())))
((eq? (car lat) a)
(multirember&co a
(cdr lat)
(lambda (newlat seen)
(col newlat
(cons (car lat) seen)))))
(else
(multirember&co a (cdr lat)
(lambda (newlat seen)
(col (cons (car lat) newlat)
seen)))))))
164
8. Lambda повсюду
Вот кое-что попроще:
(define a-friend
(lambda (x y)
(null? y)))
Да,
эта функция намного проще.
Она принимает два аргумента и
спрашивает, является ли второй
аргумент пустым списком, но
игнорирует первый аргумент.
Что выдаст выражение
Это непросто.
(multirember&co a lat col),
где
a имеет значение тунец,
lat – значение (клубника тунец и
рыба-меч)
и
col – это a-friend?
Поэтому попробуем привести
более простой пример.
Что выдаст выражение
(multirember&co a lat col),
где
a имеет значение тунец,
lat – значение ()
и
col – это a-friend?
#t,
потому что a-friend сразу
используется в первом ответе на двух пустых списках, а
a-friend проверяет, является ли
пустым ее второй аргумент.
А что выдаст выражение
(multirember&co a lat col),
где
a имеет значение тунец,
lat – значение (тунец)
и
col – это a-friend?
multirember&co спрашивает
(eq? (car lat) (quote тунец)),
где
lat имеет значение (тунец).
Затем выполняется рекурсивный вызов с ().
Какие другие аргументы
использует multirember&co в
рекурсии?
Первый – это, несомненно,
тунец. Третий аргумент – новая
функция.
Какое имя имеет третий аргумент?
col.
Девятая заповедь
165
Знаете ли вы, что означает col?
Имя col означает «коллектор»
(collector).
Коллектор иногда называют
«продолжением» (continuation).
Вот новый коллектор:
Означает ли это, что мы должны
ввести тунец в определение
(define new-friend
(lambda (newlat seen)
(col newlat
(cons (car lat) seen)))),
где
(car lat) выдает тунец
и
col – это a-friend.
(define new-friend
(lambda (newlat seen)
(col newlat
(cons (quote тунец) seen)))),
где
col – это a-friend?
Попробуйте записать это определение по-другому.
Можно ли также заменить col
на a-friend в таких определениях, если считать, что col для
a-friend – это то же самое, что
(car lat) для тунец?
Да, можно:
И что теперь?
multirember&co обнаруживает,
что (null? lat) является истиной,
и применяет коллектор к двум
пустым спискам.
Что это за коллектор?
new-friend.
Чем a-friend отличается
от new-friend?
new-friend применяет a-friend к
пустому списку и значению
(cons (quote тунец) (quote ())).
(define new-friend
(lambda (newlat seen)
(a-friend riewlat
(cons (quote tuna) seen))))
А что делает прежний коллектор Отвечает значением #f, потому
с такими аргументами?
что его второй аргумент (тунец)
не является пустым списком.
166
8. Lambda повсюду
Что выдаст выражение
(multirember&co a lat a-friend),
где
a имеет значение тунец
и
1at – значение (и тунец)?
На этот раз multirember&co
выполнит рекурсию с еще
одним другом.
(define latest-friend
(lambda (newlat seen)
(a-friend (cons (quote и) newlat)
seen)))
И что выдаст этот рекурсивный
вызов в multirember&co?
#f,
потому что (a-friend ls1 ls2),
где
ls1 имеет значение (и)
и
ls2 – значение (тунец).
Что делает
(multirember&co a lat f)?
Сравнивает каждый атом в lat с a.
Атомы, неравные a, собираются
в один список ls1, а остальные –
во второй список ls2. Наконец,
она определяет значение
(f ls1 ls2).
Последний вопрос:
что выдаст выражение
(multirember&co (quote тунец)
ls col),
где
ls имеет значение
(клубника тунец и рыба-меч)
и
col – это:
3,
потому что ls содержит три атома, отличных от тунец, и, соответственно, last-friend применяется к (клубника и рыба-меч) и
(тунец).
(define last-friend
(lambda (x y)
(length x)))?
Да!
Это странное блюдо, но мы уже
видели иностранные блюда
раньше.
Десятая заповедь
167
Десятая заповедь
Стройте функции для сбора нескольких значений за раз.
А вот и наш старый друг.
(define multiinsertL
(lambda (new old lat)
(cond
((null? lat) (quote ()))
((eq? (car lat) old)
(cons new
(cons old
(multiinsertL new old
(cdr lat)))))
(else (cons (car lat)
(multiinsertL new old
(cdr lat)))))))
Без проблем.
(define multiinsertR
(lambda (new old lat)
(cond
((null? lat) (quote ()))
((eq? (car lat) old)
(cons old
(cons new
(multiinsertR new old
(cdr lat)))))
(else (cons (car lat)
(multiinsertR new old
(cdr lat)))))))
Вспомните также multiinsertR.
Теперь попробуйте написать
определение функции
multiinsertLR.
Подсказка: multiinsertLR вставляет new
в lat слева от oldL и справа от oldR, если
oldL и oldR различны.
Вот как можно скомбинировать
две функции:
(define multiinsertLR
(lambda (new oldL oldR lat)
(cond
((null? lat) (quote ()))
((eq? (car lat) oldL)
(cons new
(cons oldL
(multiinsertLR new oldL oldR
(cdr lat)))))
((eq? (car lat) oldR)
(cons oldR
(cons new
(multiinsertLR new oldL oldR
(cdr lat)))))
(else
(cons (car lat)
(multiinsertLR new oldL oldR
(cdr lat)))))))
168
8. Lambda повсюду
Функция multiinsertLR&co для Означает ли это, что
multiinsertLR – это то же, что multiinsertLR&co принимает
multirember&co для multirember. на один аргумент больше, чем
multiinsertLR?
Да, но что это за аргумент?
Это функция коллектора.
В процессе выполнения
multiinsertLR&co применит col
к новым спискам атомов по
числу вставок слева и вставок
справа. Попробуйте написать
примерное определение
multiinsertLR&co.
Вот наш вариант. Он похож на
multiinsertLR.
(define multiinsertLR&co
(lambda (new oldL oldR lat col)
(cond
((null? lat)
(col (quote ()) 0 0))
((eq? (car lat) oldL)
(multiinsertLR&co new oldL oldR
(cdr lat)
(lambda (newlat L R)
...)))
((eq? (car lat) oldR)
(multiinsertLR&co new oldL oldR
(cdr lat)
(lambda (newlat L R)
. . .)))
(else
(multiinsertLR&co new oldL oldR
(cdr lat)
(lambda (newlat L R)
...))))))
Почему col применяется к Пустой список lat не содержит
(quote ()) 0 и 0, когда (null? lat) ни oldL, ни oldR. Это означает,
истинно?
что найдено 0 вхождений oldL и
0 вхождений oldR, и multiinsertLR
вернет (), когда lat – пустой список.
Десятая заповедь
169
Итак, что выдаст
(multiinsertLR&co
(quote клюква)
(quote рыба)
(quote чипсы)
(quote ())
col)?
Это будет значение
Верно ли, что multiinsertLR&co
будет применять новый коллектор к трем аргументам, когда результат (car lat) не равен
ни oldL, ни oldR?
Да,
первый аргумент – lat, который
multiinsertLR произведет для
(cdr lat), oldL и oldR.
Второй и третий – это количество
вставок слева и справа от oldL и
oldR соответственно.
Верно ли, что multiinsertLR&co
затем применяет функцию col к
(cons (car lat) newlat), чтобы скопировать список, если не обнаружится ни oldL, ни oldR?
Да, верно.
Поэтому мы знаем, что новый
коллектор для последнего случая
можно выразитьтак:
(col (quote ()) 0 0),
но мы не можем определить его,
потому что не знаем, что такое
col.
(lambda (newlat L R)
(col (cons (car lat) newlat) L R)).
Почему во втором и третьем Если (car lat) не равен ни oldL, ни
аргументах col просто прини- oldR, то не нужно вставлять никамает L и R?
ких новых элементов.
Потому L и R – верные результаты и для (cdr lat), и для всего
списка lat.
170
8. Lambda повсюду
коллектор
Вот что мы имеем на данный Незаконченный
момент. Здесь мы даже добави- похож на дополнительный колли дополнительный коллектор: лектор, но вместо прибавления единицы к L он прибавляет
(define multiinsertLR&co
единицу к R и вместо добавле(lambda (new oldL oldR lat col)
ния new в результат добавления
(cond
oldL в newlat он добавляет oldR
((null? lat)
в результат добавления new в
(col (quote ()) 0 0))
newlat.
((eq? (car lat) oldL)
(multiinsertLR&co new oldL oldR
(cdr lat)
(lambda (newlat L R)
(col (cons new
(cons oldL newlat))
(add1 L) R))))
((eq? (car lat) oldR)
(multiinsertLR&co new oldL oldR
(cdr lat)
(lambda (newlat L R)
...)))
(else
(multiinsertLR&co new oldL oldR
(cdr lat)
(lambda (newlat L R)
(col (cons (car lat) newlat)
L R)))))))
Попробуйте
самостоятельно
подставить требуемый код вмес
то многоточия.
Результат применения
Что выдаст выражение
(multiinsertLR&co new oldL oldR (col newlat 2 2),
lat col),
где
где
newlat – имеет значение (курица
new имеет значение пикантная,
пикантная и пикантная рыба или
oldL – значение рыба,
пикантная рыба и курица пикантoldR – значение курица
ная).
и
lat – значение (курица и рыба
или рыба и курица)?
Десятая заповедь
171
Это верный результат?
Как мне кажется, слишком много
острых приправ. Сладкий десерт
приятнее на вкус.
Вы еще помните *-функции?
Все *-функции работают со спис
ками, которые могут быть:
• пустыми;
• атомами, заключенными в
список;
• списками, заключенными в
список с помощью cons.
Попробуйте написать опре- Теперь, имея опыт написания
деление функции evens-only*, таких функций, мы легко опрекоторая удаляет все нечет- делим evens- only*:
ные числа из списка списков.
Используйте следующую функ- (define evens-only*
(lambda (l)
цию even?:
(cond
(define even?
((null? l) (quote ()))
(lambda (n)
((atom? (car l))
(= (x (÷ n 2) 2) n))).
(cond
((even? (car l))
(cons (car l) (evens-only* (cdr l))))
(else (evens-only* (cdr l)))))
(else (cons (evens-only* (car l))
(evens-only* (cdr l)))))))
Что выдаст выражение
(evens-only* l),
где
l имеет значение
((9 1 2 8) 3 10 ((9 9) 7 6) 2)?
((2 8) 10 (() 6) 2).
Чему равна сумма нечетных 9 + 1 + 3 + 9 + 9 + 7 = 38.
чисел в l,
где
l имеет значение
((9 1 2 8) 3 10 ((9 9) 7 6) 2)?
172
8. Lambda повсюду
Чему равно произведение чет- 2 × 8 × 10 × 6 × 2 = 1920.
ных чисел в l,
где
l имеет значение
((9 1 2 8) 3 10 ((9 9) 7 6) 2)?
Попробуйте написать опреде- Здесь полным-полно звезд!
ление функции evens-only*&co.
Она строит вложенный список
четных чисел, удаляя из аргумента нечетные числа, и одно
временно перемножает четные
и суммирует нечетные числа,
встречающиеся в аргументе.
Вот примерный шаблон. Попро- Она
просматривает
каждое
буйте объяснить, что именно число в car от l и собирает список
делает (evens-only*&co (car l) ...). без нечетных чисел, вычисляет
произведение четных и сумму
(define evens-only*&co
нечетных чисел.
(lambda (l col)
(cond
((null? l)
(col (quote ()) 1 0))
((atom? (car l))
(cond
((even? (car l))
(evens-only*&co (cdr l)
(lambda (newl p s)
(col (cons (car l) newl)
(× (car l) p) s))))
(else (evens-only*&co (cdr l)
(lambda (newl p s)
(col newl
p (+ (car l) s)))))))
(else (evens-only*&co (car l)
...)))))
Десятая заповедь
173
Что делает функция
Использует коллектор, который
evens-only*&co после просмот- мы еще не определили.
ра всех чисел в (car l)?
Что делает коллектор?
Использует evens-only*&co для
обхода cdr от l и собирает список,
подобный (cdr l), но без нечетных
чисел, а также вычисляет произведение четных и сумму нечетных чисел.
Означает ли это, что неизвест- Да.
ный коллектор выглядит примерно так:
(lambda (al ap as)
(evens-only*&co (cdr l)
...))?
Что произойдет, когда (evens- Как и раньше, будет применен
only*&co (cdr l) ...) завершится? еще не определенный коллектор.
Что делает коллектор примени- Объединяет
результаты
для
тельно к
списков в car и cdr, умножает и
(evens-only*&co (cdr l) ...)?
складывает
соответствующие
произведения и суммы. Затем
передает эти значения старому
коллектору:
(lambda (al ap as)
(evens-only*&co (cdr l)
(lambda (dl dp ds)
(col (cons al dl)
(× ap dp)
(+ as ds))))).
Теперь все понятно?
Абсолютно.
174
8. Lambda повсюду
Что выдаст выражение
(38 1920 (2 8) 10 (() 6) 2).
(evens-only*&co l the-last-friend),
где
l имеет значение
(((9 1 2 8) 3 10 ((9 9) 7 6) 2)
и
the-last-friend определяется так:
(define the-last-friend
(lambda (newl product sum)
(cons sum
(cons product
newl))))
Эй! У вас голова еще не закружилась
от всего этого?
Съешьте соленый кренделек
и не забудьте горчицу.
9. ...И снова, и снова, и снова...
176
9. ...И снова, и снова, и снова...
Вы хотели бы отведать икры?
Тогда нам следует отправиться
на ее поиски.
#t,
Что выдаст выражение
икра, как мы видим, присутству(looking a lat),
ет в списке lat.
где
a имеет значение икра
и
lat – значение (6 2 4 икра 5 7 3)?
Что выдаст выражение
(looking a lat),
где
a имеет значение икра
и
lat – значение
(6 2 крупа икра 5 7 3)?
#f.
Вы ожидали другого результа- Да, потому что икра все еще прита?
сутствует в списке lat.
Это верно, но какое первое 6.
число в lat?
А шестой элемент в lat?
7.
А седьмой элемент в lat?
3.
Получается, что looking
может найти атом икра?
не Да, потому что третий элемент –
крупа, которая совсем не похожа
на икра.
Вот определение looking:
(define looking
(lambda (a lat)
(keep-looking a (pick 1 lat) lat)))
Попробуйте написать определение функции keep-looking.
Мы не думаем, что вам это
удастся.
9. ...И снова, и снова, и снова...
177
Что выдаст выражение
(looking a lat),
где
a имеет значение икра
и
lat – значение (6 2 4 икра 5 7 3)?
#t,
потому что
(keep-looking a 6 lat)
дает тот же ответ, что и
(keep-looking a (pick 1 lat) lat).
Что выдаст выражение
(pick 6 lat),
где
lat имеет значение
(6 2 4 икра 5 7 3)?
7.
И что же делать?
(keep-looking a 7 lat),
где
a имеет значение икра
и
lat – значение (6 2 4 caviar 5 7 3).
Что выдаст выражение
(pick 7 lat),
где
lat имеет значение
(6 2 4 икра 5 7 3)?
3.
А что выдаст выражение
То же, что и
(keep-looking a 3 lat),
(keep-looking a 4 lat).
где
а имеет значение икра
и
lat – значение (6 2 4 икра 5 7 3)?
То есть?
#t.
Попробуйте написать опреде- Вот наш вариант:
ление функции keep-looking.
(define keep-looking
(lambda (a sorn lat)
(cond
((number? sorn)
(keep-looking a (pick sorn lat) lat))
(else (eq? sorn a)))))
178
9. ...И снова, и снова, и снова...
Догадыватесь,
sorn?
что
означает Символ или число.
Что необычного в keep-looking?
Она не выполняет рекурсивный
обход части lat.
Мы называем это «неестест- Она действительно неестественвенной» рекурсией, в отличие ная.
от обычной – естественной.
Приближается ли keep-looking к Да,
своей цели?
судя по имеющимся данным.
Всегда ли она приближается к Иногда список может не содерсвоей цели?
жать атомов икра и крупа.
Это верно.
Список может быть кортежем?
Да, если функция looking будет
искать в (7 2 4 7 5 6 3), то никогда
не закончит поиск.
Это странно!
Что выдаст выражение
(looking a lat),
где
a имеет значение икра
и
lat – значение (7 1 2 икра 5 6 3)?
Да, это странно. Но что прои- Функция продолжает, продолжазошло?
ет и продолжает искать.
Функции, подобные looking, Они называются полными.
называются частичными. А как,
по вашему мнению, называются функции, которые мы видели до сих пор?
Попробуйте определить самую Вот наш вариант:
короткую функцию, которая не
(define eternity
достигает своей цели для неко(lambda (x)
торых аргументов.
(eternity x)))
С какими аргументами eternity Ни с какими. Это самая неестест
достигает своей цели?
венная рекурсия.
9. ...И снова, и снова, и снова...
179
Является ли eternity частичной Она – самая частичная функция.
функцией?
Что выдаст выражение (shift x),
где
x имеет значение ((a b) c)?
(a (b c)).
Что выдаст выражение (shift x),
где
x имеет значение ((a b) (c d))?
(a (b c)).
Напишите определение функ- Это тривиально просто, она даже
ции shift.
не рекурсивная!
(define shift
(lambda (pair)
(build (first (first pair))
(build (second (first pair))
(second pair)))))
Опишите, что делает shift.
Вот наше описание:
«Функция shift принимает пару,
первый элемент которой сам
является парой, и строит выходную пару, смещая вторую часть
первого элемента во второй элемент».
Теперь взгляните на эту функцию:
(define align
(lambda (pora)
(cond
((atom? pora) pora)
((a-pair? (first pora))
(align (shift pora)))
(else (build (first pora)
(align (second pora)))))))
Обе функции изменяют свои
аргументы в процессе рекурсии,
но ни в одном из случаев изменение не гарантирует приближения к цели.
Что общего между ней и keeplooking?
180
9. ...И снова, и снова, и снова...
Почему align не гарантирует Во втором операторе cond придостижения цели?
менение shift создает аргумент
для align, который не является
частью первоначального аргумента.
Какую заповедь это нарушает?
Седьмую.
Может быть, новый аргумент Нет.
хотя бы короче исходного?
Почему?
Функция shift перестраивает
только ту пару, которую получает.
И?
И результат, и аргумент shift
содержат одинаковое количество атомов.
Попробуйте написать опреде- Вот наш вариант:
ление функции, подсчитываю(define length*
щей количество атомов в аргу(lambda (pora)
ментах align.
(cond
((atom? pora) 1)
(else
(+ (length* (first pora))
(length* (second pora)))))))
Является ли align частичной Мы пока не знаем.
функцией?
Возможно, есть аргументы,
получив которые, она будет продолжать группировать объекты
до бесконечности.
Есть ли что-то еще, что меняется в аргументах функции align
при ее рекурсивном применении?
Да.
Первый элемент пары становится проще, хотя второй становится сложнее.
В каком смысле первый эле- Он является лишь частью первомент становится проще?
го элемента исходной пары.
9. ...И снова, и снова, и снова...
181
Означает ли это, что length* Более подходящая функция
неправильно определяет длину должна уделять больше внимааргумента? Можно ли опреде- ния первому элементу.
лить более подходящую функцию?
Насколько больше?
По меньшей мере, в два раза
больше.
Возможно, имеется в виду Эта функция выглядит более
правильной.
функция weight*, такая как:
(define weight*
(lambda (pora)
(cond
((atom? pora) 1)
(else (+ (× (weight* (first pora)) 2)
(weight* (second pora)))))))
Что выдаст выражение
(weight* x),
где
x имеет значение ((a b) c)?
7.
Что выдаст выражение
(weight* x),
где
x имеет значение (a (b c)?
5.
Означает ли это, что аргументы Да,
становятся проще?
веса аргументов align последовательно уменьшаются.
Можно ли сказать, что align – Нет,
частичная функция?
она выдает значения для любых
аргументов.
182
9. ...И снова, и снова, и снова...
Вот функция shuffle, похожая на Функции shuffle и revpair меняalign, но использует revpair из ют местами элементы пар, если
главы 7 вместо shift:
первый элемент является парой.
(define shuffle
(lambda (pora)
(cond
((atom? pora) pora)
((a-pair? (first pora))
(shuffle (revpair pora)))
(else (build (first pora)
(shuffle (second pora)))))))
Означает ли это, что shuffle – Мы не знаем.
полная функция?
Давайте попробуем применить (a (b c)).
(shuffle x),
где
x имеет значение (a (b c))?
(shuffle x),
где
x имеет значение (a b)?
(a b).
Хорошо, теперь попробуем чтонибудь более интересное. Что
выдаст выражение (shuffle x),
где
x имеет значение ((a b) (c d))?
Чтобы ответить на этот вопрос,
нужно выяснить, что выдаст
(shuffle (revpair pora)),
где
pora имеет значение ((a b) (c d)).
И как это сделать?
Определить значение
(shuffle pora),
где
pora имеет значение ((c d) (a b)).
Не означает ли это, что мы Да,
должны знать значение
именно так.
(shuffle (revpair pora)),
где
(revpair pora) выдает значение
((a b) (c d))?
9. ...И снова, и снова, и снова...
183
И?
Функция shuffle не является полной, потому что теперь она снова
меняет местами элементы пары,
а это означает, что мы начинаем
все сначала.
Является ли следующая ниже
функция полной?
(define C
(lambda (n)
(cond
((one? n) 1)
(else
(cond
((even? n) (C (÷ n 2)))
(else (C (add1 (× 3 n)))))))))
Она не дает значения для аргумента 0, а в отношении других
значений ничего определеного
сказать нельзя.
Спасибо Лотару Коллатцу (Lothar
Collatz; 1910–1990).
Что выдаст выражение (A 1 0)?
2.
(A 1 1)?
3.
(A 2 2)?
7.
Вот определение функции A:
(define A
(lambda (n m)
(cond
((zero? n) (add1 m))
((zero? m) (A (sub1 n) 1))
(else (A (sub1 n)
(A n (sub1 m)))))))
Это функция Аккермана.
Спасибо Вильгельму
Аккерманну (Wilhelm
Ackermann; 1853–1946).
Что общего между А, shuffle и Аргументы A, как и аргументы
looking?
shuffle и looking, не обязательно
уменьшаются в ходе рекурсии.
А как насчет примера?
Это просто: для (A 1 2) необходимо значение (A 0 (A 1 1)). А это
значит, что нам нужно значение
(A 0 3).
Всегда ли A дает ответ?
Да, она полная.
184
9. ...И снова, и снова, и снова...
Тогда, что выдаст выражение
(A 4 3)?
Получить ответ на практике
невозможно.
Что это значит?
Страница, которую вы сейчас
читаете, истлеет задолго до того,
как мы сможем вычислить значение (A 4 3).
Но те молчали, так как их
Всех съели до одной.
– Льюис Кэрролл,
«Морж и плотник»
Наверное, было бы здорово
иметь функцию, которая могла
бы сказать нам, возвращает ли
какая-либо функция значение
для каждого аргумента?
Несомненно.
Теперь, когда мы увидели функции, которые никогда не возвращают результата или возвращают его слишком поздно,
было бы желательно иметь под
рукой инструмент, подобный
этой функции.
А давайте напишем ее.
Это сложная задача.
Проверяемая функция может
благополучно
возвращать
результат для множества разных аргументов.
Тогда давайте упростим задачу. Для разминки рассмотрим
функцию,
проверяющую,
останавливается ли некоторая функция только на пустом
списке – самом простом из всех
аргументов.
Эта задача решается намного
проще.
9. ...И снова, и снова, и снова...
Вот начало функции:
185
Что она делает?
(define will-stop?
(lambda f)
...))
Попробуйте продолжить.
Возвращает ли will-stop? значение для любого аргумента?
Это простой вопрос: мы сказали, что она возвращает либо #t,
либо #f, в зависимости от того,
будет ли функция останавливаться при применении к ().
Является ли will-stop? полной?
Да,
она всегда возвращает #t или #f.
Тогда
давайте
придумаем
несколько примеров. Вот первый. Что выдаст выражение
(will-stop? f),
где
f – это length?
Мы знаем, что (length l) выдает 0,
когда l имеет значение ().
И что?
Тогда применение функции
(will-stop? length) должно выдать
#t.
Однозначно.
А как насчет другого примера?
Например, что выдаст выражение (will-stop? eternity)?
(eternity (quote ())) не выдает
значения. Мы только что видели это.
Означает ли это, что выражение (will-stop? eternity) выдаст
#f?
Да, это так.
Нужны ли нам еще примеры?
Возможно, стоит привести еще
один пример.
186
9. ...И снова, и снова, и снова...
Хорошо, вот функция, которая
может оказаться интересным
аргументом для will-stop?.
Что она делает?
(define last-try
(lambda (x)
(and (will-stop? last-try)
(eternity x))))
Что выдаст выражение
(will-stop? last-try)?
Мы должны попробовать применить ее к ().
Чтобы узнать значение
(last-try (quote ()))), нужно определить значение
(and (will-stop? last-try)
(eternity (quote ()))))).
Что выдаст
(and (will-stop? last-try)
(eternity (quote ()))))?
Это зависит от значения
(will-stop? last-try).
Есть только два варианта.
Допустим, что
(will-stop? last-try) выдает #f.
Тогда (and #f (eternity (quote ())))
даст значение #f,
так как (and #f ...) – всегда #f.
То есть (last-try (quote ())) останавливается, верно?
Да.
Но разве will-stop? не предсказывала как раз противоположное?
Да, это так.
Мы сказали, что значение
(will-stop? last-try) равно #f, что
на самом деле означает, что
last-try не останавливается.
Мы, должно быть, ошиблись в
отношении (will-stop? last-try)?
Все правильно.
Она должна вернуть #t, потому
что will-stop? всегда дает ответ.
Мы говорим, что она полная.
9. ...И снова, и снова, и снова...
187
Прекрасно. Если
(will-stop? last-try) выдает #t,
то что выдаст (last-try (quote ())?
Теперь нам просто нужно определить значение
(and #t (eternity (quote ()))),
которое совпадает со значением (eternity (quote ())).
Что выдаст выражение
(eternity (quote ()))?
Ничего.
Мы знаем, что она не остановится.
Но это значит, что мы снова
ошиблись!
Да,
потому что на этот раз мы сказали, что
(will-stop? last-try) выдает #t.
Что, по-вашему, это означает?
Вот наш вывод:
«Мы рассмотрели два возможных случая. Если мы можем
определить will-stop?, то (willstop? last-try) должна дать либо
#t, либо #f. Но это не так в силу
определения того, что должна
делать will-stop?. Это означает,
что will-stop? нельзя определить».
Это особый случай?
Да.
Функция will-stop? – первая,
которую мы можем точно описать, но не можем определить
на нашем языке.
Есть ли какой-нибудь способ
решить эту проблему?
Нет.
Спасибо Алану М. Тьюрингу
(Alan M. Turing; 1912–1954)
и Курту Гёделю (Kurt Gödel;
1906–1978).
Что такое (define ...)?
Это интересный вопрос.
Мы только что видели, что
(define ...) не работает для willstop?
188
9. ...И снова, и снова, и снова...
Так что же такое рекурсивные
определения?
Держитесь крепче, сделайте
глубокий вдох и бросайтесь
вперед, когда будете готовы.
Вот функция length:
(define length
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
Это точно.
Что, если бы у нас больше не
было (define ...)? Сможем ли мы
определить length?
Без (define ...) ничто, и особенно
тело length, не могло бы сослаться на имя length.
Что делает эта функция?
(lambda (l)
(cond
((null? l) 0)
(else (add1 (eternity (cdr l))))))
Определяет длину пустого спис
ка и ничего больше.
Что произойдет, если применить ее к непустому списку?
Нет ответа.
Если передать eternity аргумент,
она не дает ответа.
Что делает эта функция, которая так похожа на length?
Она просто не дает никакого
ответа для непустых списков.
Допустим, что мы можем дать
имя этой новой функции. Какое
имя выбрали бы вы?
length0,
потому что функция может
определить длину только пустого списка.
Как бы вы определили функцию, вычисляющую длину
списка, содержащего один или
меньше элементов?
Например, так:
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length0 (cdr l))))))
9. ...И снова, и снова, и снова...
189
Почти то, что надо, но мы не
можем подставить (define ...) на
место ссылки на length0.
Поэтому заменим length0 ее
определением.
(lambda (l)
(cond
((null? l) 0)
(else
(add1
((lambda (l)
(cond
((null? l) 0)
(else (add1
(eternity (cdr l))))))
(cdr l))))))
И какое имя подошло бы для
этой функции?
Просто length≤1.
Верно ли, что следующая ниже
функция определяет длину
списков, содержащих два или
меньше элементов?
(lambda (l)
(cond
((null? l) 0)
(else
(add1
((lambda (l)
(cond
((null? l) 0)
(else
(add1
((lambda (l)
(cond
((null? l) 0)
(else
(add1
(eternity
(cdr l))))))
(cdr l))))))
(cdr l))))))
Да, это length≤2.
Мы просто заменили eternity
следующей версией length.
190
9. ...И снова, и снова, и снова...
Итак, что же такое рекурсия?
Что вы имеете в виду?
Мы видели, как определить
длину списка без элементов, с
не более чем одним элементом,
с не более чем двумя элементами и т. д.
Как можно было бы определить универсальную функцию
length?
Если бы мы могли написать
бесконечную функцию в стиле length0, length≤1, length≤2, ..., то
тогда могли бы написать length∞,
вычисляющую длину всех спис
ков, которые только можно
составить.
Какой длины списки можно
составить?
Ну, список либо пуст, либо
содержит один элемент, или два
элемента, или три, или четыре,
... или 1001, ....
Но мы же не можем определить
бесконечную функцию.
Нет, не можем.
А если бы и могли, то во всех
этих функциях имели бы повторяющиеся шаблоны.
Да, верно.
Как выглядят эти шаблоны?
Все эти программы содержат
функцию, похожую на length.
Возможно, нам следует абстрагироваться от этой функции:
см. девятую заповедь.
Давайте сделаем это!
Нам нужна функция, которая
выглядит как length, но начинается с (lambda (length) ...).
Вы это имеете в виду?
Да.
Это определение создаст length0.
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
eternity)
9. ...И снова, и снова, и снова...
191
Попробуйте переписать length≤1,
следуя аналогии.
((lambda (f)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (f (cdr l)))))))
((lambda (g)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (g (cdr l)))))))
eternity))
Может быть, мы должны были
использовать имя аргумента
length?
Нет.
Здесь мы использовали простые
имена f и g. Пока мы действуем
последовательно, все в порядке.
А как выглядело бы определение length≤2?
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
eternity)))
Почти то, что надо, но все же
слишком много повторяющегося кода.
Верно. Давайте избавимся от
этого.
С чего начнем?
Дадим имя функции, которая
принимает length как аргумент
и возвращает функцию, похожую на length.
192
9. ...И снова, и снова, и снова...
Как можно назвать эту функцию?
Например, mk-length, от «make
length» (создать length»).
Хорошо, покажите это на примере с length0.
Легко:
((lambda (mk-length)
(mk-length eternity))
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))))
Тогда это – length≤1.
А это – length≤2.
((lambda (mk-length)
(mk-length (mk-length eternity)))
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))))
((lambda (mk-length)
(mk-length
(mk-length
(mk-length eternity))))
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))))
Попробуйте написать length≤3
в том же стиле.
Это просто! Вот она:
((lambda (mk-length)
(mk-length
(mk-length
(mk-length
(mk-length eternity)))))
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))))
Итак, на что похожа рекурсия?
Она напоминает бесконечную
башню из применений
mk-length к произвольной
функции.
9. ...И снова, и снова, и снова...
193
А нам нужна бесконечная башня?
Конечно нет.
В каждом конкретном случае
применения length нам нужно
конечное число повторений,
которое, к сожалению, заранее
неизвестно.
Можно ли хотя бы примерно
оценить это число?
Да.
Но есть риск ошибиться в оценке, если число достаточно большое.
Когда мы обнаружим, что
выбрано недостаточно большое число?
Когда
применим
функцию
eternity, во внутреннем вызове
mk-length.
А если бы мы могли добавить
еще одно применение mk-length
к eternity в этой точке?
Это только отсрочит появление
проблемы на один шаг, и, кроме
того, как это сделать?
Ну, поскольку никого не волнует, какая функция передается
mk-length, мы могли бы сразу
передать ей mk-length.
Это правильная мысль.
А затем применить mk-length к
eternity, а полученный результат – к cdr, чтобы получить еще
один этаж башни.
Вот все та же функция length0:
((lambda (mk-length)
(mk-length mk-length))
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1
(length (cdr l))))))))
Да,
и мы можем даже использовать
mk-length вместо length.
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(lambda (l)
(cond
((null? l) 0)
(else (add1
(mk-length (cdr l))))))))
Зачем нам это?
Все имена равны, но некоторые
имена равнее, чем другие1.
1
Да простит нас Джордж Оруэлл
(George Orwell; 1903–1950).
194
9. ...И снова, и снова, и снова...
Верно: мы можем использовать
любые имена, если действуем
последовательно и непротиворечиво?
mk-length – более подходящее
имя, чем length.
Такое имя, как mk-length,
постоянно будет напоминать
о том, что первый аргумент
mk-length – это mk-length.
Теперь, когда mk-length передается в mk-length, можем ли
мы использовать этот аргумент
для создания дополнительного
рекурсивного применения?
Да.
Применяя mk-length один раз,
мы получаем length≤1.
Какое значение выдаст
(((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(lambda (l)
(cond
((null? l) 0)
(else (add1
((mk-length eternity)
(cdr l))))))))
l),
где
l имеет значение (яблоки)?
Хорошее упражнение.
Решите его, используя карандаш и бумагу.
Можем ли мы сделать то же
самое большее число раз?
Да,
просто продолжая передавать
mk-length самой себе, мы можем
сделать это столько раз, сколько
потребуется!
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(lambda (l)
(cond
((null? l) 0)
(else (add1
((mk-length eternity)
(cdr l))))))))
9. ...И снова, и снова, и снова...
Как бы вы назвали эту функцию?
195
Конечно же, length.
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(lambda (l)
(cond
((null? l) 0)
(else (add1
((mk-length mk-length)
(cdr l))))))))
Как она работает?
Она продолжает добавлять
рекурсивное применение, передавая mk-length самой себе в тот
момент, когда должна завершиться.
Осталась одна проблема: в ней
больше нет функции, которая
выглядит как length.
Да,
можно извлечь это новое применение mk-length к самой себе
и назвать его length.
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(lambda (l)
(cond
((null? l) 0)
(else (add1
((mk-length mk-length)
(cdr l))))))))
Можно ли это как-то исправить?
Почему?
Потому что в действительности
это применение создает функцию length.
196
9. ...И снова, и снова, и снова...
Например, так?
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(mk-length mk-length))))
Да,
выглядит просто замечательно.
Давайте посмотрим, работает
ли это решение.
Давайте.
Что выдаст
Результатом должно быть
число 1.
(((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(mk-length mk-length))))
l),
где
l имеет значение (яблоки)?
Для начала нам нужно определить значение
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(mk-length mk-length))))
Верно, потому что значение этого выражения является функцией, которую нужно применить
к l, где l имеет значение (яблоки).
9. ...И снова, и снова, и снова...
Поэтому в действительности
нужно определить значение
197
Верно.
((lambda (mk-length)
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(mk-length mk-length)))
(lambda (mk-length)
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(mk-length mk-length))))?
Но затем нам понадобится
узнать значение
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
((lambda (mk-length)
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(mk-length mk-length)))
(lambda (mk-length)
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(mk-length mk-length))))?
И это верно. Но где же конец?
Если следовать логике, то нам
также нужно узнать значение
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
((lambda (mk-length)
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(mk-length mk-length)))
(lambda (mk-length)
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(mk-length mk-length)))))).
198
9. ...И снова, и снова, и снова...
Да,
так можно продолжать до бесконечности. Почему?
Потому что мы просто продолжаем применять mk-length к
самой себе снова, снова и снова...
Странно ли это?
Это связано с тем, что mk-length
раньше возвращала функцию
при применении ее к аргументу. На самом деле не имело значения, к чему мы ее применяем.
Но теперь, когда мы извлекли
(mk-length mk-length) из функции, которая создает 1ength,
она больше не возвращает
функцию.
Нет, не возвращает. Так что же
делать?
Превратить
применение
mk-length к самой себе в последней правильной версии length в
функцию:
Как?
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(lambda (l)
(cond
((null? l) 0)
(else (add1
((mk-length mk-length)
(cdr l)))))))
Вот другой способ.
Если f – это функция одного аргумента, то является ли
(lambda (x) (f x)) функцией одного аргумента?
Да, является.
9. ...И снова, и снова, и снова...
Если (mk-length mk-length) возвращает
функцию
одного
аргумента, то возвращает ли
(lambda (x) ((mk-length mk-length)
x)) функцию одного аргумента?
199
На самом деле
(lambda (x)
((mk-length mk-length) x))
– это функция!
Хорошо, давайте сделаем это Давайте:
с применением mk-length к
((lambda (mk-length)
самой себе.
(mk-length mk-length))
(lambda (mk-length)
(lambda (l)
(cond
((null? l) 0)
(else (add1
((lambda (x)
((mk-length mk-length) x))
(cdr l))))))))
Переместите новую функцию Вот наш вариант:
так, чтобы получить length
((lambda (mk-length)
обратно.
(mk-length mk-length))
(lambda (mk-length)
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else
(add1 (length (cdr l)))))))
(lambda (x)
((mk-length mk-length) x)))))
Можно ли переместить функцию?
Да,
мы просто всегда поступали
наоборот, заменяя имя его значением. Здесь мы извлекаем
значение и даем ему имя.
Можно ли извлечь функцию
в рамке, которая похожа на
length, и дать ей имя?
Да,
это вообще не зависит от
mk-length!
200
9. ...И снова, и снова, и снова...
Правильная ли это функция?
((lambda (le)
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(le (lambda (x)
((mk-length mk-length) x))))))
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))))
Да.
Что мы на самом деле получили
обратно?
Мы извлекли исходную функцию mk-length.
Давайте отделим функцию, Это просто.
которая создает length, от функ(lambda (le)
ции, которая выглядит как
((lambda (mk-length)
length.
(mk-length mk-length))
(lambda (mk-length)
(le (lambda (x)
((mk-length mk-length) x))))))
Есть ли у этой функции имя?
Да,
она будет называться комбинатором Y аппликативного порядка.
(define Y
(lambda (le)
((lambda (f) (f f))
(lambda (f)
(le (lambda (x) ((f f) x)))))))
Работает ли (define ...) снова?
Конечно, теперь, когда мы знаем, что такое рекурсия.
Теперь вы знаете, почему работает Y?
Если нет, то перечитайте эту
главу еще раз и узнаете.
9. ...И снова, и снова, и снова...
201
Что такое (Y Y)?
Кто знает, но это выражение
очень хорошо работает.
Ваша голова еще не распухла?
Возможно, и распухла, после
такой-то нагрузки на разум!
Остановите этот мир – я сойду.
Лесли Брикусс (Leslie Bricusse)
и Энтони Ньюли (Anthony Newley)
Здесь можно что-нибудь нарисовать
или оставить заметки.
10. Какова ценность
всего этого?
204
10. Какова ценность всего этого?
Запись – это пара списков, первый из которых является множеством. Кроме того, оба спис
ка должны быть одинаковой
длины. Придумайте несколько
примеров записей.
Как сконструировать запись из
множества названий и списка
значений?
Вот наши примеры:
((напиток блюдо компонент)
(вино паштет говяжий))
и
((напиток блюдо компонент)
(пиво пиво пиво))
и
((блюдо десерт)
((еда это) (номер один для нас))).
(define new-entry build)
Попробуйте сконструировать
свои примеры с помощью этой
функции.
Что выдаст выражение
(lookup-in-entry name entry),
где
name имеет значение блюдо
и
entry – значение
((напиток блюдо компонент)
(еда очень вкусная))?
очень.
А если name имеет значение
десерт?
Оставим решение за пользователем lookup-in-entry.
Как этого достичь?
lookup-in-entry
принимает
дополнительный
аргументфункцию,
которая
должна
вызываться, если name не найден в первом списке в записи.
Как вы думаете, сколько аргументов должна принимать эта
дополнительная функция?
Мы считаем, что один – name.
Почему?
10. Какова ценность всего этого?
Вот наше определение
lookup-in-entry:
(define lookup-in-entry
(lambda (name entry entry-f)
(lookup-in-entry-help name
(first entry)
(second entry)
entry-f)))
Завершите функцию
lookup-in-entry-help.
205
Вот наш вариант:
(define lookup-in-entry-help
(lambda (name names values entry-f)
(cond
((null? names) (entry-f name))
((eq? (car names) name)
(car values))
(else (lookup-in-entry-help name
(cdr names)
(cdr valus)
entry-f)))))
(define lookup-in-entry-help
(lambda (name names values entry-f)
(cond
( ________ ________ )
( ________ ________ )
( ________ ________ ))))
Таблица (ее также называют
средой, или окружением) – это
список записей. Вот один пример: пустая таблица, представленная как ().
Составьте несколько примеров
таблиц.
Вот наш пример:
(((напиток блюдо компонент)
(вино паштет говяжий))
((блюдо десерт)
((еда это) (номер один для нас)))).
Попробуйте определить функцию extend-table, которая принимает запись и таблицу (возможно, пустую) и создает новую
таблицу, вставляя новую запись
в начало старой таблицы.
Вот наш вариант:
(define extend-table cons)
206
10. Какова ценность всего этого?
Что выдаст выражение
(lookup-in-table name table table-f),
где
name имеет значение блюдо,
table – значение
(((блюдо десерт)
(спагетти торт-мороженое))
((напиток блюдо компонент)
(еда очень вкусная)))
и
table-f – значение (lambda
(name) ...)
Это может быть либо спагетти,
либо очень, но lookup-in-table
просматривает список записей
по порядку. Поэтому результатом будет спагетти.
Напишите определение lookupin-table.
Вот наш вариант:
(define lookup-in-table
(lambda (name table table-f)
(cond
((null? table) (table-f name))
(else (lookup-in-entry name
(car table)
(lambda (name)
(lookup-in-table name
(cdr table)
table-f)))))))
Подсказка: не забудьте обратиться к
справке.
Попробуйте описать, что определяет следующая функция:
(lambda (name)
(lookup-in-table name
(cdr table)
table-f)).
В предисловии мы упоминали,
что шрифт без засечек будет
использоваться для представления атомов. До настоящего
момента это не имело значения. Но далее обращайте особое внимание на оформление
атомов шрифтом.
Эта функция определяет действие, которое должно выполниться, если искомое имя не
будет найдено в первой записи.
Обязательно обращайте внимание на оформление атомов
шрифтом без засечек.
10. Какова ценность всего этого?
207
Заметили, что слова «шрифт
без засечек» набраны не шрифтом без засечек?
Мы надеемся, что заметили.
Вот слова «шрифт без засечек»,
набранные шрифтом без засечек.
Мы выбрали хорошее представление для выражений?
Да.
Все они являются S-выражениями, поэтому могут служить
аргументами функций.
Каких функций?
Например, value.
Помните ли вы функцию value
из главы 6?
Напомним, что value – это функция, возвращающая собственное значение полученного ею
выражения.
Какое значение даст выражение (car (quote (a b c)))?
Мы даже не знаем, какое значение даст (quote (a b c)).
Какое значение выдаст выражение
То же, что и (a b c).
(cons rep-a
(cons rep-b
(cons rep-c
(quote ())))),
где
rep-a имеет значение a,
rep-b – значение b
и
rep-c – значение c?
208
10. Какова ценность всего этого?
Отлично!
А что выдаст
(cons rep-car
(cons (cons rep-quote
(cons
(cons rep-a
(cons rep-b
(cons rep-c
(quote ()))))
(quote ())))
(quote ()))),
Это представление выражения:
(car (quote (a b c))).
где
rep-car имеет значение car,
rep-quote – значение quote
rep-a – значение a,
rep-b – значение b
и
rep-c – значение c?
Что выдаст выражение
(car (quote (a b c)))?
a.
Что выдаст выражение (value e),
где
e имеет значение
(car (quote (a b c)))?
a.
Что выдаст выражение (value e),
где
e имеет значение
(quote (car (quote (a b c))))?
(car (quote (a b c))).
Что выдаст выражение (value e),
где
e имеет значение (add1 6)?
7.
Что выдаст выражение (value e),
где
e имеет значение 6?
6,
потому что числа – это константы.
10. Какова ценность всего этого?
209
Что выдаст выражение (value e),
где
e имеет значение
(quote nothing)?
nothing.
Что выдаст выражение (value e),
где
e имеет значение nothing?
nothing не имеет значения.
Что выдаст выражение (value e),
где
e имеет значение
((lambda (nothing)
(cons nothing (quote ())))
(quote
(from nothing comes something)))?
((from nothing comes something)).
Что выдаст выражение (value e),
где
e имеет значение
((lambda (nothing)
(cond
(nothing (quote something))
(else (quote nothing))))
#t)?
something.
Какой тип имеет e,
где
e имеет значение 6?
*const.
Какой тип имеет e,
где
e имеет значение #t?
*const.
Что выдаст выражение (value e),
где
e имеет значение #f?
#f.
Какой тип имеет e,
где
e имеет значение cons?
*const.
210
10. Какова ценность всего этого?
Что выдаст выражение (value e),
где
e имеет значение car?
(primitive car).
Какой тип имеет e,
где
e имеет значение
(quote nothing)?
*quote.
Какой тип имеет e,
где
e имеет значение nothing?
*identifier.
Какой тип имеет e,
где
e имеет значение
(lambda (x y) (cons x y))?
*lambda.
Какой тип имеет e,
где
e имеет значение
((lambda (nothing)
(cond
(nothing (quote something))
(else (quote nothing))))
#t)?
*application.
Какой тип имеет e,
где
e имеет значение
(cond
(nothing (quote something))
(else (quote nothing)))?
*cond.
Как вы думаете, сколько всего
типов существует?
Мы насчитали шесть:
• *const;
• *quote;
• *identifier;
• *lambda;
• *cond;
• *application.
10. Какова ценность всего этого?
211
Как, по-вашему, мы должны
представлять типы?
Мы выбираем функции. Мы
называем эти функции «действиями» – «actions».
Если действия – это функции,
которые делают «что-то правильное» при применении к
выражению соответствующего типа, то что должна делать
value?
Вы наверняка догадались. Она
должна выяснить тип переданного ей выражения и применить
соответствующее действие.
Помните ли вы функцию atomto-function из главы 8?
Функция atom-to-function пригодилась нам, когда переписывали значения для числовых
выражений.
Ниже показана функция, кото- Вот наш вариант:
рая производит правильное
(define atom-to-action
действие (т. е. функцию) для
(lambda (e)
каждого возможного S-выра(cond
жения:
((number? e) *const)
((eq? e #t) *const)
(define expression-to-action
((eq? e #f) *const)
(lambda (e)
((eq? e quote(cons)) *const)
(cond
((eq? e quote(car)) *const)
((atom? e) (atom-to-action e))
((eq? e quote(cdr)) *const)
(else (list-to-action e)))))
((eq? e quote(null?)) *const)
((eq? e quote(eq?)) *const)
Напишите определение функ1
((eq? e quote(atom?)) *const)
ции atom-to-action .
((eq? e quote(zero?)) *const)
1
Некорректно
сформированные
((eq? e quote(number?)) *const)
S-выражения, такие как (quote a b), (),
(else *identifier))))
(lambda (#t) #t), (lambda (5) 5), (lambda
(car) car), (lambda a), (cond (3 c) (else b)
(6 a)) и (1 2), здесь не рассматриваются. Они могут быть обнаружены
соответствующей функцией, которая
применяется к S-выражению до его
передачи в value.
212
10. Какова ценность всего этого?
Теперь определите вспомогательную функцию list-to-action.
Вот наш вариант:
Если
предположить,
что
expression-to-action
работает
правильно, мы можем использовать ее для определения value
и meaning.
Это пустая таблица.
Функция value1 вместе со всеми функциями, которые она
использует, называется интерпретатором.
(define value
(lambda (e)
(meaning e (quote ()))))
(define list-to-action
(lambda (e)
(cond
((atom? (car e))
(cond
((eq? (car e) (quote quote))
*quote)
((eq? (car e) (quote lambda))
*lambda)
((eq? (car e) (quote cond))
*cond)
(else *application)))
(else *application))))
1
Функция value аппроксимирует функцию eval, имеющуюся в Scheme (и Lisp).
(define meaning
(lambda (e table)
((expression-to-action e) e table)))
Что означает (quote ()) в определении value?
Действия говорят громче слов.
10. Какова ценность всего этого?
213
Сколько аргументов должны
принимать действия в соответствии с вышесказанным?
Два,
выражение e и таблицу.
Вот действия для констант.
(define *const
(lambda (e table)
(cond
((number? e) e)
((eq? e #t) #t)
((eq? e #f) #f)
(else (build
(quote primitive) e)))))
Да,
для чисел эта функция просто
возвращает выражение, и это
все, что нам нужно сделать для
0, 1, 2, ....
Для #t возвращается #t.
Для #f возвращается #f.
А все остальные атомы конс
тантного типа представляются
как примитивы.
Это верное определение?
Вот действие для *quote:
(define *quote
(lambda (e table)
(text-of e)))
Вот наше определение:
(define text-of second)
Определите вспомогательную
функцию text-of.
Мы уже использовали таблицу?
Нет, но сделаем это в ближайшее время.
Зачем нам нужна таблица?
Для запоминания
идентификаторов.
Учитывая, что таблица содержит значения идентификаторов, определите действие
*identifier.
Вот наше определение:
Вот определение initial-table:
Будем надеяться, что никогда.
Почему?
(define initial-table
(lambda (name)
(car (quote ()))))
Когда она используется?
значений
(define *identifier
(lambda (e table)
(lookup-in-table e table
initial-table)))
214
10. Какова ценность всего этого?
Какое значение имеет
(lambda (x) x)?
Мы пока не знаем, но знаем, что
это должно быть представлением непримитивной функции.
Чем отличаются непримитивные функции от примитивных?
Мы знаем, что делают примитивные функции; действия
непримитивных функций определяются их аргументами и
реализациями.
Поэтому, чтобы использовать
непримитивную
функцию,
нужно знать ее формальные
аргументы и реализацию.
По крайней мере. К счастью, это
просто cdr из выражения lambda.
Что еще мы должны знать?
Мы также добавим таблицу, на
случай, если она понадобится
позже.
И как мы ее представим?
Разумеется, в виде списка.
Вот действие для *lambda.
(non-primitive
( (((y z) ((8) 9)))
(define *lambda
(lambda (e table)
(build (quote non-primitive)
(cons table (cdr e)))))
таблица
(x)
(cons x y) ))
формальные
аргументы
Что выдаст (meaning e table),
где
e имеет значение
(lambda (x) (cons x y))
и
table – значение (((y z) ((8) 9))))?
Возможно, будет нелишним
определить некоторые вспомогательные функции для возврата частей из этого трехэлементного списка (т. е. таблицу, формальные аргументы и тело).
Определите table-of, formals-of
и body-of.
Вот наши варианты:
(define table-of first)
(define formals-of second)
(define body-of third)
тело
10. Какова ценность всего этого?
Опишите (cond ...) своими словами.
215
Это специальная форма, принимающая любое количество
строк cond. Она просматривает
строки по очереди.
Если вопросительная часть
слева дает #f, то рассматриваются остальные строки. Иначе
возвращается ответ из правой
части.
Если она видит строку else, то
рассматривает эту строку cond
так, как если бы ее вопросительная часть давала #t.
Вот функция evcon, которая Вот наши варианты:
делает то, что мы только что
(define else?
описали:
(lambda (x)
(define evcon
(cond
(lambda (lines table)
((atom? x) (eq? x (quote else)))
(cond
(else #f))))
((else? (question-of (car lines)))
(meaning (answer-of (car lines))
table))
((meaning (question-of (car lines))
table)
(meaning (answer-of (car lines))
table))
(else (evcon (cdr lines) table)))))
(define question-of first)
(define answer-of second)
Определите функцию else? и
вспомогательные функции
question-of и answer-of.
Разве мы не нарушили первую
заповедь?
Да,
мы не задаем вопроса (null?
lines), поэтому на один из
вопросов в каждом cond должен
даваться истинный ответ.
216
10. Какова ценность всего этого?
Теперь, используя функцию
evcon, определите действие
*cond.
Вот наш вариант:
(define *cond
(lambda (e table)
(evcon (cond-lines-of e) table)))
(define cond-lines-of cdr)
Полезны ли эти вспомогательные функции?
Да,
они делают код более читабельным. Но вы это уже знаете.
Теперь вы понимаете, как работает *cond?
Возможно, и нет.
Как можно добиться понимания?
Лучший способ – опробовать ее
на примере. Вот хороший пример:
(*cond e table),
где
e имеет значение
(cond (coffee klatsch) (else party))
и
table – значение
(((coffee) (#t))
((klatsch party) (5 (6)))).
Мы видели, как используется
таблица?
Да,
ее используют *lambda и
*identifier.
Но как идентификаторы попадают в таблицу?
В единственном действии,
которое мы еще не определили: *application.
Как представлено применение
(application)?
Применение – это список выражений, голова (car) которого
содержит выражение, значением которого является функция.
10. Какова ценность всего этого?
217
Чем применение отличается от
специальной формы, например
(and ...), (or ...) или (cond ...)?
Применение всегда должно
определять значения всех своих
аргументов.
Должны ли мы узнать значения
всех аргументов, прежде чем
применить функцию?
Да.
Напишите определение функ- Вот наш вариант:
ции evlis, которая принимает (define evlis
список (представлений) аргу(lambda (args table)
ментов и таблицу и возвращает
(cond
список, определяющий значе((null? args) (quote ()))
ние каждого аргумента.
(else
(cons (meaning (car args) table)
(evlis (cdr args) table))))))
Что еще нам нужно, чтобы
определить значение применения?
Мы должны выяснить, что означает function-of.
И что дальше?
Затем применить функцию к
значениям аргументов.
Вот определение *application:
Конечно. Мы просто должны
правильно определить apply,
function-of и arguments-of.
(define *application
(lambda (e table)
(apply
(meaning (function-of e) table)
(evlis (arguments-of e) table))))
Оно верное?
Напишите определения
function-of и arguments-of.
Вот наши варианты:
(define function-of car)
(define arguments-of cdr)
Сколько существует разных
видов функций?
Два: примитивные и непримитивные.
218
10. Какова ценность всего этого?
Как выглядят представления
этих двух видов функций?
(primitive primitive-name) и
(non-primitive (table formals body)).
Список (table formals body) называется замыкающей записью.
Напишите определения
primitive? и non-primitive?.
Вот наши варианты:
(define primitive?
(lambda (l)
(eq? (first l) (quote primitive))))
(define non-primitive?
(lambda (l)
(eq? (first l) (quote non-primitive))))
Теперь мы можем написать
функцию apply.
Вот она:
(define apply1
(lambda (fun vals)
(cond
((primitive? fun)
(apply-primitive
(second fun) vals))
((non-primitive? fun)
(apply-closure
(second fun) vals)))))
1
Если fun не вычисляется ни как примитивная, ни как непримитивная, как
в выражении (((lambda (x) (x 5)) 3), то
ответа нет. Функция apply аппроксимирует функцию apply, имеющуюся в
Scheme (и Lisp).
10. Какова ценность всего этого?
219
Вот определение apply-primitive: 5) (quote cons)
6) cdr1
(define apply-primitive
7) eq?
(lambda (name vals)
8) (second vals)
(cond
9) :atom?
((eq? name 1 )
(cons (first vals) (second vals))) (define :atom?
((eq? name (quote car))
(lambda (x)
(car (first vals)))
(cond
((eq? name (quote cdr))
((atom? x) #t)
( 2 (first vals)))
((null? x) #f)
((eq? name (quote null?))
((eq? (car x) (quote primitive))
(null? (first vals)))
#t)
((eq? name (quote eq?))
((eq?
(car x) (quote non-primitive)
( 3 (first vals) 4 ))
#t)
((eq? name (quote atom?))
(else #f))))
( 5 (first vals)))
((eq? name (quote zero?))
1
Функция apply-primitive может прове(zero? (first vals)))
рять применение из cdr к пустому списку
((eq? name (quote add1))
или sub1 к 0 и т. д.
(add1 (first vals)))
((eq? name (quote sub1))
(sub1 (first vals)))
((eq? name (quote number?))
(number? (first vals))))))
Заполните недостающие части.
Осталось определить только
функцию apply-closure?
Да, и apply-closure должна добавлять новые записи в таблицу.
Как найти результат (f a b),
где
f имеет значение
(lambda (x y) (cons x y)),
a – значение 1
и
b – значение (2)?
Это непросто. Но мы знаем, как
определить значение (cons x y),
где
table имеет значение
(((x y)
(1 (2)))).
Почему мы можем это?
Здесь нам не требуется
apply-closure.
220
10. Какова ценность всего этого?
Попробуйте обобщить последние два шага.
Применение
непримитивной функции – замыкания
(closure) – к списку значений
равносильно
нахождению
значения тела замыкания с
помощью его таблицы, дополненной записью вида
(formals values).
В этой записи formals – это
formals замыкания, а values –
результат применения evlis.
Вы следили за всем этим?
Если нет, то вот определение
apply-closure:
(define apply-closure
(lambda (closure vals)
(meaning (body-of closure)
(extend-table
(new-entry
(formals-of closure)
vals)
(table-of closure)))))
Это сложная функция, и она
заслуживает демонстрации на
примере.
Далее:
closure имеет значение
((((u v w)
(1 2 3))
((x y z)
(4 5 6)))
(x y)
(cons z x))
и
vals – значение ((a b c) (d e f)).
10. Какова ценность всего этого?
221
Какие значения получат новые
аргументы meaning?
Новый аргумент е для meaning
получит значение (cons z x), а
новый аргумент table – значение
(((x y)
((a b c) (d e f)))
((u v w)
(1 2 3))
((x y z)
(4 5 6))).
Что выдаст выражение (cons z x),
где
z имеет значение 6
и
x – значение (a b c)?
То же, что и (meaning e table),
где
e имеет значение (cons z x)
и
table – значение
(((x y)
((a b c) (d e f)))
((u v w)
(1 2 3))
((x y z)
(4 5 6))).
Что выдаст выражение
(meaning e table),
где
e имеет значение z?
6, с помощью *identifier.
Что выдаст выражение
(meaning e table),
где
e имеет значение x?
(a b c), с помощью *identifier.
Итак, что выдаст evlis?
(6 (a b c )), потому что evlis возвращает список значений.
Что выдаст выражение
(meaning e table),
где
e имеет значение cons?
(primitive
*const.
cons),
с
помощью
222
10. Какова ценность всего этого?
Теперь мы готовы применить
(apply fun vals),
где
fun имеет значение
(primitive cons)
и
vals – значение (6 (a b c )).
Какой
путь
выбрать?
мы
Путь apply-primitive.
должны
Какая строка cond выбирается
для (apply-primitive name vals),
где
name имеет значение cons
и
vals – значение (6 (a b c ))?
Третья:
((eq? name (quote cons))
(cons (first vals) (second vals))).
Мы уже закончили?
Да.
Но как быть с (define ...)?
Этот оператор не нужен, так как
рекурсию можно получить из
Y-комбинатора.
Действительно ли (define ...) не
нужен?
Да,
но смотрите книгу «Seasoned
Schemer».
Значит ли это, что мы можем
запустить
интерпретатор
на
интерпретаторе,
если
выполним преобразование с
помощью Y-комбинатора?
Да,
но пусть это вас не волнует.
В чем необычность value?
Она видит представления выражений.
Должна ли will-stop? видеть
представления выражений?
Это может здорово помочь.
10. Какова ценность всего этого?
223
Помогает ли это?
Нет,
не беспокойтесь – мы можем
снова сыграть в ту же игру. Мы
можем определить функцию
типа last-try?, которая покажет,
что нельзя определить новую и
улучшенную will-stop?.
else?
Да,
пришло время для банкета.
Здесь можно что-нибудь нарисовать
или оставить заметки.
Антракт
226
Антракт
Вы дошли до антракта. Что же делать дальше? Вы можете быстренько пробежаться в магазин и приобрести оставшуюся часть
нашего шоу – книгу «The Seasoned Schemer» – или прочитать некоторые из книг, которые перечислены ниже. Все эти книги считаются классикой, и некоторые из них довольно древние, но все же они
выдержали испытание временем и все достойны вашего внимания.
Какие-то из них вообще не имеют никакого отношения к математике или логике, другие имеют отношение к математике, но только
в виде увлекательных баек, а с третьими просто было бы полезно
ознакомиться. Чтобы не было недопонимания: эти книги не подготовят вас к чтению нашего продолжения – они просто помогут вам
развлечься. В конце книги «The Seasoned Schemer» вы найдете множество ссылок на Scheme и ссылку на Common Lisp. Не торопитесь
сразу же переходить к следующей книге. Отдохните немного и прочитайте некоторые из предложенных нами. Затем, когда вы немного отдохнете и, возможно, избавитесь от нескольких вмененных вам
калорий, приступайте к следующей части. Наслаждайтесь!
• Abbott, Edwin A. Flatland. Dover Publications, Inc., New York,
1952. (Original publication: Seeley and Co., Ltd., London, 1884.)
• Carroll, Lewis. The Annotated Alice: Alice ‘s Adventures in Wonderland and Through the Looking Glass. Clarkson M. Potter, Inc., New
York, 1960. Введение и примечания написаны Мартином Гарднером (Martin Gardner). Оригинальное издание публиковалось под разными названиями: Alice ‘s Adventures Under Ground
и Through the Looking Glass и What Alice Found There, Macmillan
and Company, London 1865 and 1872, respectively.
• Halinos, Paul R. Naive Set Theory. Litton Educational Publishers,
New York, 1960.
• Hein, Piet. Grooks. The MIT Press, Cambridge, Massachusetts, 1960.
• Hofstadter, Douglas R. Gödel. Escher, Bach: an Eternal Golden Braid.
Basic Books, Inc., New York, 1979.
• Nagel, Ernest and James R. Newman. Gödel’s Proof. New York
University Press, New York, 1958.
• Pólya, György. How to Solve It. Doubleday and Co., New York, 1957.
• Smullyan, Raymond. To Mock a Mockingbird and Other Logic Puzzles
Including an Amazing Adventure in Combinatory Logic. Alfred A.
Knopf, Inc., New York, 1985.
• Suppes, Patrick. Introduction to Logic. Van Nostrand Co., Princeton,
New Jersey, 1957.
Алфавитный указатель
228
Алфавитный указатель
Символы
^ 93
+ 79, 131
< 92
= 93
> 91, 92
1st-sub-exp 128, 130
2nd-sub-exp 129
*application 217
:atom? 219
*cond 216
*const 213
*identifier 213
*lambda 214
*quote 213
A
A 183
add1 79
addtup 81, 83
a-friend 164
align 179
all-nums 97
answer-of 215
a-pair? 142
apply 218
apply-closure 220
apply-primitive 219
arguments-of cdr 217
atom? 23
atom-to-action 211
atom-to-function 160
B
body-of 214
build 143
C
C 183
cond-lines-of cdr 216
cookies 147
E
edd1 131
else? 215
eqan? 97
eq?-c 152
eqlist? 112, 113, 115
eqset? 138
eq?-tuna 162
equal? 114
eternity 178
evcon 215
evens-only* 171
evens-only*&co 172
evlis 217
expression-to-action 211
extend-table 205
F
first 142
firsts 60, 61, 63
formals-of 214
fullfun? 146
fun? 144
function-of car 217
I
initial-table 213
insert-g 157
insertL 157
insertL* 107
insertL-f 155
insertR 65, 157
insertR* 102
insertR-f 156
intersect 140
intersect? 139
intersectall 141
K
keep-looking 177
L
last-try 186
lat? 132
latest-friend 166
leftmost 109
length 95, 188
length* 180
list-to-action 212
Алфавитный указатель
looking 176
lookup-in-entry 205
lookup-in-entry-help 205
lookup-in-table 206
M
makeset 135, 136
meaning 212
member? 37
member* 107
multiinsertL 74, 75, 167
multiinsertLR 167
multiinsertLR&co 168, 170
multiinsertR 74, 167
multirember&co 163
multirember-eq? 162
multirember-f 161
multiremberT 163
multisubst 76
N
new-entry 204
new-friend 165
non-primitive? 218
no-nums 96
number? 96
numbered? 123, 124
rempick 96
revpair 145
revrel 144, 145
S
second 142
seqS 159
sero? 131
set? 134
shift 179
shuffle 182
subset? 137
subst 69, 159
subst* 106
subst2 69
SYMBOL 184 \f "Symbol" \s 11 94
T
text-of 213
text-of second 213
the-last-friend 174
third 143
tup+ 86, 87, 90
U
union 140
V
O
value 125, 126, 127, 129, 160, 212
occur 97
occur* 105
one? 98
one-to-one? 146
operator 129, 130
W
P
Y 200
pick 95
primitive? 218
zub1 131
Q
question-of 215
R
rember 50, 51, 54, 60, 116
rember* 100
rember-f 151, 153
weight* 181
will-stop? 185
Y
Z
М
Моисей Эльевич Шейнфинкель 152
Х
Хаскелл Б. Карри 152
229
Книги издательства «ДМК ПРЕСС» можно купить оптом и в розницу
в книготорговой компании «Галактика»
(представляет интересы издательств
«ДМК ПРЕСС», «СОЛОН ПРЕСС», «КТК Галактика»).
Адрес: г. Москва, пр. Андропова, 38;
Тел.: +7(499) 782-38-89. Электронная почта: books@alians-kniga.ru.
При оформлении заказа следует указать адрес (полностью),
по которому должны быть высланы книги;
фамилию, имя и отчество получателя.
Желательно также указать свой телефон и электронный адрес.
Эти книги вы можете заказать и в интернет-магазине:
www.galaktika-dmk.com
Дэниел П. Фридман, Маттиас Феллейзен
The Little Schemer:
чудесное функциональное программирование
Главный редактор
Мовчан Д. А.
dmkpress@gmail.com
Корректор
Верстка
Дизайн обложки
Синяева Г. И.
Паранская Н. В.
Мовчан А. Г.
Формат 70×1001/16.
Печать цифровая. Усл. печ. л. 18.69 .
Тираж 100 экз.
Веб-сайт издательства: www.dmkpress.com
Закон car
Примитив car определен только для непустых списков.
Закон cdr
Примитив cdr определен только для непустых списков. Применение cdr к
непустому списку всегда дает другой список.
Закон cons
Примитив cons принимает два аргумента. Второй аргумент должен быть
списком. Результат – всегда список.
Закон null?
Примитив null? определен только для списков.
Закон eq?
Примитив eq? принимает два аргумента. Каждый должен быть нечисловым
атомом.