4.2.3 · Стратегия вычисления как данные

Thunk и запоминание отложенного значения

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

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

Какие изменения представления делают call-by-need видимым внутри вычислителя?

Представление отложенной работы в виде помеченного изменяемого вектора
Различение невычисленного thunk и вычисленного thunk
Принудительное выполнение отложенного вычисления только при запросе его значения
Мемоизация первого значения для последующих запросов

make-thunk сохраняет тег thunk, вычисление с нулевым количеством аргументов и пустой слот для результата. Создание этого вектора не вызывает вычисление, поэтому даже тело с ошибкой остается безвредным, если его никто не запрашивает.

force-it проверяет тег. При первом запросе процедура вызывает сохраненное вычисление, меняет тег на evaluated-thunk, удаляет вычисление и сохраняет значение. Последующие запросы выбирают кэшированный слот и не выполняют вычисление повторно. Это раскрывает изменение представления, которое ленивый вычислитель обычно скрывает за обработкой аргументов.

Код SICP607 из 1,048,576 байт UTF-8

(begin
  (define (make-thunk computation)
    (vector 'thunk computation #f))
  (define (force-it object)
    (if (eq? (vector-ref object 0) 'evaluated-thunk)
        (vector-ref object 2)
        (let ((value ((vector-ref object 1))))
          (vector-set! object 0 'evaluated-thunk)
          (vector-set! object 1 #f)
          (vector-set! object 2 value)
          value)))
  (define calls 0)
  (define delayed
    (make-thunk
      (lambda ()
        (set! calls (+ calls 1))
        (* calls 10))))
  (list (force-it delayed)
        (force-it delayed)
        calls
        (vector-ref delayed 0)))

Примеры

Результат—

Вывод: —
Значение: —
Диагностика: —

Трасса выполнения0 / 0 событий

Ожидаемый результат

Первая программа возвращает (10 10 1 evaluated-thunk). Вторая возвращает (thunk 0) без вычисления деления на ноль.

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

В первом запуске найдите одно применение сохраненного вычисления и изменения вектора, которые заменяют представление thunk. Второй force считывает кэшированное значение. Во втором запуске убедитесь, что не происходит ни применения деления, ни присваивания calls.

Попробуйте сами

Измените программу и сравните результат.

Выполните force для delayed в третий раз в первой программе. Предскажите три значения, количество calls и итоговый тег перед запуском.

Показать подсказку

Когда тег равен evaluated-thunk, force-it считывает слот 2 без вызова слота 1.

Завершить этот урок

В этой главе пройдено 0 из 23 урока0%