4.1.5 · Структуры данных вычислителя

Кадры, процедуры и списки аргументов вычислителя

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

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

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

Представление одного кадра как записей переменных и значений за закрытым маркером
Поиск в упорядоченной цепочке окружений от ближайшего кадра наружу
Сохранение параметров, тела и окружения создания в записи составной процедуры
Тегирование реализаций примитивов хоста отдельно от составных процедур
Рассмотрение только #f как лжи в предикате истинности guest
Сохранение порядка операндов при построении списка значений аргументов

Первая программа строит глобальный кадр, содержащий x = 10, и локальный кадр, содержащий x = 3 и y = 4. Поиск находит ближайший x, не изменяя глобальную запись. Запись compound-procedure затем сохраняет один параметр z, одно выражение тела и полную цепочку локального окружения, чтобы последующее применение могло расширить тот же лексический контекст.

Вторая программа помечает процедуру хоста + тегом данных primitive и применяет ее после извлечения реализации. Процедура list-of-values фиксирует вычисление операндов слева направо с помощью явных зондов. Предикат истинности guest возвращает ложь только для #f, поэтому ноль и цитированный символ считаются истиной. Вместе эти записи определяют протокол учебного вычислителя для кадров, процедур, аргументов и проверок истинности.

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

(begin
  (define (pair-bindings variables values)
    (if (null? variables)
        '()
        (cons (cons (car variables) (car values))
              (pair-bindings (cdr variables) (cdr values)))))
  (define (make-frame variables values)
    (cons '*frame* (pair-bindings variables values)))
  (define (extend-environment variables values base)
    (cons (make-frame variables values) base))
  (define (lookup variable environment)
    (if (null? environment)
        'unbound
        (let ((record (assoc variable (cdr (car environment)))))
          (if record
              (cdr record)
              (lookup variable (cdr environment))))))
  (define (make-procedure parameters body environment)
    (list 'compound parameters body environment))
  (define global-environment
    (list (make-frame '(x) '(10))))
  (define local-environment
    (extend-environment '(x y) '(3 4) global-environment))
  (define procedure
    (make-procedure '(z) '((+ x y z)) local-environment))
  (list (lookup 'x local-environment)
        (lookup 'x global-environment)
        (lookup 'y local-environment)
        (car procedure)
        (cadr procedure)
        (length (caddr procedure))
        (length (cadddr procedure))))

(begin
  (define (pair-bindings variables values)
    (if (null? variables)
        '()
        (cons (cons (car variables) (car values))
              (pair-bindings (cdr variables) (cdr values)))))
  (define (make-frame variables values)
    (cons '*frame* (pair-bindings variables values)))
  (define (extend-environment variables values base)
    (cons (make-frame variables values) base))
  (define (lookup variable environment)
    (if (null? environment)
        'unbound
        (let ((record (assoc variable (cdr (car environment)))))
          (if record
              (cdr record)
              (lookup variable (cdr environment))))))
  (define (make-procedure parameters body environment)
    (list 'compound parameters body environment))
  (define global-environment
    (list (make-frame '(x) '(10))))
  (define local-environment
    (extend-environment '(x y) '(3 4) global-environment))
  (define procedure
    (make-procedure '(z) '((+ x y z)) local-environment))
  (list (lookup 'x local-environment)
        (lookup 'x global-environment)
        (lookup 'y local-environment)
        (car procedure)
        (cadr procedure)
        (length (caddr procedure))
        (length (cadddr procedure))))

Примеры

Результат—

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

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

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

Программа окружения возвращает (3 10 4 compound (z) 1 2). Программа протокола возвращает (primitive + 12 (first second third) #f #t #t).

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

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

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

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

Добавьте define-variable! и set-variable-value! в модель кадров. Определите локальную переменную w, присвойте значение ближайшей переменной x и верните значения локальной и глобальной переменных x вместе с длиной захваченного окружения процедуры.

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

Определение направлено на первый кадр. Присваивание ищет наружу и изменяет первую существующую подходящую запись.

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

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