4.1.9 · Вынесение внутренних определений

Явная локальная инициализация внутренних имен

Тело процедуры сначала размещает каждое внутреннее имя, затем задает значения присваиванием, поэтому взаимно рекурсивные процедуры делят одно окружение.

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

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

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

Проход scan-out считывает тело процедуры как данные. Он берет начальные формы define, преобразует сокращенную запись определения процедуры в выражения lambda, создает одно связывание let для каждого имени с явным маркером unassigned и помещает set! для каждого определения перед исходным оставшимся телом. Таким образом, имена существуют вместе до применения любого замыкания, что дает взаимно рекурсивным вспомогательным процедурам одно общее локальное окружение.

Вторая программа выполняет обе формы. classify-original использует внутренние определения напрямую. classify-scanned явно записывает преобразованную структуру let и set!. Обе формы возвращают одинаковые результаты проверки четности для 7 и 8, и equal? возвращает true. Конечное сравнение проверяет это преобразование и делает видимой его явную промежуточную структуру.

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

(begin
  (define body
    '((define (even-step value)
        (if (= value 0)
            #t
            (odd-step (- value 1))))
      (define (odd-step value)
        (if (= value 0)
            #f
            (even-step (- value 1))))
      (list (even-step n) (odd-step n))))
  (define (definition? expression)
    (and (pair? expression)
         (eq? (car expression) 'define)))
  (define (take-definitions expressions)
    (if (and (pair? expressions)
             (definition? (car expressions)))
        (cons (car expressions)
              (take-definitions (cdr expressions)))
        '()))
  (define (drop-definitions expressions)
    (if (and (pair? expressions)
             (definition? (car expressions)))
        (drop-definitions (cdr expressions))
        expressions))
  (define (definition-name definition)
    (if (symbol? (cadr definition))
        (cadr definition)
        (car (cadr definition))))
  (define (definition-value definition)
    (if (symbol? (cadr definition))
        (caddr definition)
        (cons 'lambda
              (cons (cdr (cadr definition))
                    (cddr definition)))))
  (define (make-binding definition)
    (list (definition-name definition)
          (list 'quote '*unassigned*)))
  (define (make-assignment definition)
    (list 'set!
          (definition-name definition)
          (definition-value definition)))
  (define (scan-out-defines expressions)
    (let ((definitions (take-definitions expressions))
          (remaining (drop-definitions expressions)))
      (if (null? definitions)
          expressions
          (list
            (cons 'let
                  (cons (map make-binding definitions)
                        (append (map make-assignment definitions)
                                remaining)))))))
  (car (scan-out-defines body)))

(begin
  (define body
    '((define (even-step value)
        (if (= value 0)
            #t
            (odd-step (- value 1))))
      (define (odd-step value)
        (if (= value 0)
            #f
            (even-step (- value 1))))
      (list (even-step n) (odd-step n))))
  (define (definition? expression)
    (and (pair? expression)
         (eq? (car expression) 'define)))
  (define (take-definitions expressions)
    (if (and (pair? expressions)
             (definition? (car expressions)))
        (cons (car expressions)
              (take-definitions (cdr expressions)))
        '()))
  (define (drop-definitions expressions)
    (if (and (pair? expressions)
             (definition? (car expressions)))
        (drop-definitions (cdr expressions))
        expressions))
  (define (definition-name definition)
    (if (symbol? (cadr definition))
        (cadr definition)
        (car (cadr definition))))
  (define (definition-value definition)
    (if (symbol? (cadr definition))
        (caddr definition)
        (cons 'lambda
              (cons (cdr (cadr definition))
                    (cddr definition)))))
  (define (make-binding definition)
    (list (definition-name definition)
          (list 'quote '*unassigned*)))
  (define (make-assignment definition)
    (list 'set!
          (definition-name definition)
          (definition-value definition)))
  (define (scan-out-defines expressions)
    (let ((definitions (take-definitions expressions))
          (remaining (drop-definitions expressions)))
      (if (null? definitions)
          expressions
          (list
            (cons 'let
                  (cons (map make-binding definitions)
                        (append (map make-assignment definitions)
                                remaining)))))))
  (car (scan-out-defines body)))

Примеры

Результат—

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

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

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

Программа преобразования возвращает одно выражение let с even-step и odd-step, связанными с цитированными маркерами *unassigned*, за которыми следуют две формы set! и исходное тело списка. Программа сравнения возвращает (#t ((#f #t) (#t #f)) ((#f #t) (#t #f))).

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

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

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

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

Добавьте третью внутреннюю вспомогательную процедуру, которая распознает значения, делящиеся на три, с помощью трех взаимно рекурсивных процедур для остатка. Напишите как исходную, так и явно преобразованную версию scan-out, затем сравните их результаты для 8 и 9.

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

Разместите все три имени перед присваиваниями. Каждое замыкание вызывает следующую процедуру остатка после вычитания единицы, и только процедура нулевого остатка возвращает true при нуле.

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

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