3.2.1 · Модель вычисления с окружениями

Правила вычисления в модели окружений

Лексический вычислитель и явные операции с кадрами сводят самовычисление, поиск переменных, применение, определение и присваивание в одну модель.

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

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

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

Процедура model-eval обрабатывает перечисленные формы: самовычисляемые значения, переменные, quote, lambda и применение. Вычисление lambda создает данные compound-procedure, содержащие параметры, тело и текущее окружение. Применение этого значения вычисляет тело в новом кадре параметров, связанном с захваченным окружением, поэтому внутренний вызов с y по-прежнему может найти внешний x.

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

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

(begin
  (define (make-frame variables values)
    (if (null? variables)
        '()
        (cons (cons (car variables) (car values))
              (make-frame (cdr variables) (cdr values)))))
  (define (extend-environment variables values base)
    (cons (make-frame variables values) base))
  (define (lookup-variable-value variable environment)
    (if (null? environment)
        'unbound-variable
        (let ((record (assoc variable (car environment))))
          (if record
              (cdr record)
              (lookup-variable-value variable (cdr environment))))))
  (define (sum-values values)
    (if (null? values)
        0
        (+ (car values) (sum-values (cdr values)))))
  (define (product-values values)
    (if (null? values)
        1
        (* (car values) (product-values (cdr values)))))
  (define (apply-primitive name arguments)
    (cond ((eq? name 'primitive-plus) (sum-values arguments))
          ((eq? name 'primitive-times) (product-values arguments))
          (else 'unknown-primitive)))
  (define (eval-operands expressions environment)
    (if (null? expressions)
        '()
        (cons (model-eval (car expressions) environment)
              (eval-operands (cdr expressions) environment))))
  (define (model-apply procedure arguments)
    (if (and (pair? procedure)
             (eq? (car procedure) 'compound))
        (model-eval
          (caddr procedure)
          (extend-environment
            (cadr procedure)
            arguments
            (cadddr procedure)))
        (apply-primitive procedure arguments)))
  (define (model-eval expression environment)
    (cond ((or (number? expression)
               (string? expression)
               (boolean? expression))
           expression)
          ((symbol? expression)
           (lookup-variable-value expression environment))
          ((eq? (car expression) 'quote)
           (cadr expression))
          ((eq? (car expression) 'lambda)
           (list 'compound
                 (cadr expression)
                 (caddr expression)
                 environment))
          (else
           (model-apply
             (model-eval (car expression) environment)
             (eval-operands (cdr expression) environment)))))
  (define global-environment
    (list (list (cons '+ 'primitive-plus)
                (cons '* 'primitive-times))))
  (list
    (model-eval
      '((lambda (x)
          ((lambda (y) (+ x y)) 4))
        3)
      global-environment)
    (model-eval
      '(((lambda (x)
           (lambda (y) (+ x y)))
         5)
        8)
      global-environment)))

(begin
  (define (make-frame variables values)
    (if (null? variables)
        '()
        (cons (cons (car variables) (car values))
              (make-frame (cdr variables) (cdr values)))))
  (define (extend-environment variables values base)
    (cons (make-frame variables values) base))
  (define (lookup-variable-value variable environment)
    (if (null? environment)
        'unbound-variable
        (let ((record (assoc variable (car environment))))
          (if record
              (cdr record)
              (lookup-variable-value variable (cdr environment))))))
  (define (sum-values values)
    (if (null? values)
        0
        (+ (car values) (sum-values (cdr values)))))
  (define (product-values values)
    (if (null? values)
        1
        (* (car values) (product-values (cdr values)))))
  (define (apply-primitive name arguments)
    (cond ((eq? name 'primitive-plus) (sum-values arguments))
          ((eq? name 'primitive-times) (product-values arguments))
          (else 'unknown-primitive)))
  (define (eval-operands expressions environment)
    (if (null? expressions)
        '()
        (cons (model-eval (car expressions) environment)
              (eval-operands (cdr expressions) environment))))
  (define (model-apply procedure arguments)
    (if (and (pair? procedure)
             (eq? (car procedure) 'compound))
        (model-eval
          (caddr procedure)
          (extend-environment
            (cadr procedure)
            arguments
            (cadddr procedure)))
        (apply-primitive procedure arguments)))
  (define (model-eval expression environment)
    (cond ((or (number? expression)
               (string? expression)
               (boolean? expression))
           expression)
          ((symbol? expression)
           (lookup-variable-value expression environment))
          ((eq? (car expression) 'quote)
           (cadr expression))
          ((eq? (car expression) 'lambda)
           (list 'compound
                 (cadr expression)
                 (caddr expression)
                 environment))
          (else
           (model-apply
             (model-eval (car expression) environment)
             (eval-operands (cdr expression) environment)))))
  (define global-environment
    (list (list (cons '+ 'primitive-plus)
                (cons '* 'primitive-times))))
  (list
    (model-eval
      '((lambda (x)
          ((lambda (y) (+ x y)) 4))
        3)
      global-environment)
    (model-eval
      '(((lambda (x)
           (lambda (y) (+ x y)))
         5)
        8)
      global-environment)))

Примеры

Результат—

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

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

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

Вычислитель урока возвращает (7 13). Программа изменения кадров возвращает (3 4 7 10).

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

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

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

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

Добавьте if в model-eval, затем вычислите замыкание, тело которого выбирает между локальным параметром и захваченным внешним значением. Также определите глобальный y и убедитесь, что локальное определение затеняет его, а не изменяет.

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

Вычисляйте только выбранную ветвь if. Определение всегда направлено на первый кадр переданного окружения.

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

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