sicp.io
Глава 3 · Проверка

Отслеживайте ячейку памяти. Именуйте расписание. Требуйте только то, что необходимо.

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

Вопрос для размышления

Можете ли вы определить, какая ячейка памяти изменяется, какой кадр предоставляет имя, какое расписание создает наблюдение, какое отложенное вычисление было форсировано и какой интерфейс скрывает эти детали?

  • Прослеживать присваивание между вызовами одного замыкания с состоянием
  • Различать закрытые ячейки памяти, созданные отдельными замыканиями
  • Объяснять, как присваивание может скрывать инструментарий или ход эксперимента
  • Объяснять, почему присваивание вносит зависимость от истории и порядка вычислений
  • Применять явные правила поиска в окружении, создания процедур, определения и присваивания
  • Фиксировать один кадр параметров на каждое применение процедуры
  • Отличать первый вызов force от мемоизированного force
  • Запрашивать только конечный префикс бесконечного потока
  • Отслеживать мутации указателей front, rear и связей в очереди
  • Отслеживать деструктивный append, псевдонимы, циклы и уникальные идентичности пар
  • Воспроизводить те же переходы состояний из одного начального значения seed
  • Распространять недостающее значение через связанные ограничения
  • Упорядочивать события по явному модельному времени
  • Объединять провода, логические элементы, задержки и расписание в схему
  • Находить потерю обновления, вызванную чтением устаревших данных
  • Сериализовать два изменения состояния с помощью одной общей блокировки
  • Отличать взаимное исключение от предотвращения циклического ожидания
  • Разрешать взаимно рекурсивные вспомогательные процедуры внутри одного закрытого окружения вызова
  • Обновлять существующие записи таблицы и связывать новые вложенные записи
  • Представлять последовательные численные приближения в виде отложенных потоков
  • Сравнивать скрытое состояние объектов с явной повторно используемой историей потоков

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

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

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

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

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

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

Код SICP384 из 1,048,576 байт UTF-8
Примеры
Результат
Вывод
Значение
Диагностика
Трасса выполнения0 / 0 событий
    Запуски происходят внутри браузера с отображением результата программы и трассы выполнения.
    Ожидаемый результат

    Исходные двенадцать программ сохраняют свои задокументированные первые наблюдения. Программа преимуществ присваивания возвращает (9 16 2 reset 0), а программа цены присваивания возвращает (90 80 90 90). Вычислитель с окружением возвращает (7 13), а программа кадров применения возвращает 25 с тремя записями кадров. Деструктивный append возвращает ((a b c d) (c d) #t). Инвертор возвращает (2 1 4 0), модель порядка блокировок возвращает ((90 50) (45 95) 95 45 #f #f), числовые потоки возвращают точные частичные суммы и приближения Ньютона, а рекуррентное соотношение объектов и потоков порождает одинаковый префикс из пяти чисел в обеих моделях.

    На что обратить внимание в трассе

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

    Повторение

    Двадцать один вопрос для анализа состояния, времени, идентичности и отложенных вычислений

    Что меняется, когда ответ зависит от предшествующих ему вызовов?

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

    Почему два счетчика, созданные одной процедурой, не перезаписывают значения друг друга?

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

    Как два вызова force могут привести только к одному вычислению?

    Ответ Второй вызов force возвращает сохраненное значение без повторного выполнения тела. Конечное значение calls остается равным 1, что делает мемоизацию заметной в результате.

    Как конечный запуск может использовать последовательность без последнего элемента?

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

    Почему для локальной вставки за константное время требуется указатель rear так же, как и указатель front?

    Ответ Удаление не перезаписывает связи. Оно сдвигает front к его текущему cdr. После вставки a, b и c и одного удаления front указывает на пару b, тогда как rear по-прежнему указывает на пару c.

    Как генератор с состоянием может менять значение при каждом вызове, но при этом в точности повторять последовательность?

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

    Как одно отношение может правильно реагировать независимо от того, какие два значения поступят первыми?

    Ответ Операция forget-value! выполняется успешно только тогда, когда отзывающая сторона совпадает с сохраненным источником информации. Когда пользователь забывает значение total, сумматор отзывает значение right, поскольку сам предоставил это выведенное значение, но не может отозвать независимо переданное значение left. Передача нового значения right выводит новое значение total через то же самое отношение.

    Как моделирование может определять следующее действие, не следуя порядку планирования?

    Ответ Процедура propagate извлекает самое раннее событие, применяет его числовое изменение к сигналу signal и записывает полученное состояние рядом со временем этого события. Расписание моделирует логическое время, а не ожидает физических часов, и эти примеры не моделируют физику одновременных событий за рамками явного правила вставки.

    Что теряется, когда два обновления считывают один и тот же общий баланс до завершения любого из них?

    Ответ Второе расписание позволяет операции deposit выполнить чтение и запись до того, как операцию чтения выполнит withdrawal. В результате withdrawal видит 110 и записывает 90. Эти программы перечисляют два выбранных конечных расписания и их точные итоговые балансы.

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

    Ответ Процедура make-serializer принимает общую блокировку и возвращает обертку для процедуры. Эта обертка выполняет захват перед вызовом изменяющей состояние процедуры и сбрасывает блокировку после получения ее результата. В предоставленном конечном расписании сериализованная операция deposit завершается до того, как операция withdrawal прочитает баланс balance, поэтому оба обновления сохраняются в итоговом значении 90. Урок фиксирует именно это расписание и конечное состояние.

    Как несколько локальных процедур могут ссылаться друг на друга без утечки своих имен во внешнее окружение?

    Ответ Вторая программа рассматривает определения как цитированные данные и формирует структуру scan-out, используемую для анализа одновременной локальной области: сначала для каждого имени создается связывание с явным маркером unassigned, затем каждая процедура устанавливается через set!, после чего вычисляется оставшееся тело. Этот запуск строит преобразование в виде данных и делает явной структуру unassigned и set!.

    Какие связи должны измениться, когда таблица обновляет одну запись или создает новый вложенный путь ключей?

    Ответ Таблица с двумя ключами хранит запись первого ключа, чей cdr сам является ассоциативным списком. Вставка нового второго ключа изменяет эту подтаблицу, тогда как новый первый ключ связывает целую подтаблицу с внешней таблицей. Обновление arithmetic с 10 до 11 изменяет существующую самую глубоко вложенную запись вместо создания дубликата. В этих примерах #f используется в качестве результата отсутствия значения, поэтому сохранение #f потребовало бы более богатого протокола lookup.

    Когда скрытое состояние упрощает взаимодействие процедур, которые в остальном независимы друг от друга?

    Ответ Вторая программа отделяет контроллер Монте-Карло от объекта эксперимента с состоянием. Процедура monte-carlo знает только то, что вызов experiment возвращает следующий булев результат. Переданный конечный список делает этот запуск воспроизводимым и напрямую моделирует модульное преимущество присваивания.

    Какие рассуждения о подстановке и изменении порядка становятся неверными, когда выражение может изменять состояние?

    Ответ Зонд порядка делает зависимость от расписания явной с помощью связываний let. Сначала вызов с сообщением 0 изменяет состояние, а затем сообщение 1 считывает его. Если первым вызывается сообщение 1, оно наблюдает прежнее состояние. Ни один из выводов здесь не зависит от того, какой порядок операндов выбирает вычислитель. Обе последовательности записаны раздельно и сравниваются как данные.

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

    Ответ Вторая программа делает изменение кадров явным. Поиск находит локальный x раньше глобального x. Процедура set-variable-value! изменяет уже существующую локальную запись, тогда как define-variable! добавляет y в первый кадр. Ни одна из этих операций не изменяет глобальный x. Этот пояснительный вычислитель напрямую моделирует перечисленные формы.

    Как одинаковые имена параметров остаются различными при вложенных и повторных применениях процедур?

    Ответ Процедура make-adder записывает кадр, где x = 5, и возвращает замыкание, сохраняющее доступ к нему. Последующий вызов add-five создает кадр y = 7, связанный с этим захваченным окружением. В протоколе используются учебные имена кадров, чтобы сделать эти связи явными.

    Как изменение и идентичность меняют смысл привычных операций со списками, таких как append и обход?

    Ответ Пример с циклом изменяет последний cdr так, чтобы он указывал обратно на первую пару. Обычный рекурсивный обход списка никогда не достигнет пустого списка. Поэтому count-unique-pairs записывает идентичность каждой пары перед спуском и прибавляет ноль, когда memq находит уже просмотренную пару. Программа сообщает о цикле через eq?, не требуя от принтера бесконечного развертывания.

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

    Ответ Полусумматор строится из элементов or, and, inverter и еще одного элемента and. Конечное расписание сначала устанавливает нулевые входы, а затем изменяет a, b и снова a. Зафиксированные моменты времени представляют собой точные события симуляции, полученные из явных задержек в этой модели.

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

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

    Что меняется, когда численная итерация описывает каждое последовательное приближение вместо сокрытия всех промежуточных шагов ради итогового ответа?

    Ответ Поток sqrt-stream раскрывает каждое улучшение Ньютона для √2. Его точная рациональная последовательность начинается с 1, 3/2, 17/12, 577/408 и 665857/470832. Последующие потребители могут исследовать больше приближений без изменения производителя. Отображаемый префикс фиксирует последовательность улучшений для выбранного начального значения.

    Какие зависимости становятся видимыми, когда состояние представляется в виде потока, а не скрывается внутри объекта?

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