4.2.1 · Нормальный порядок и аппликативный порядок

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

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

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

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

Вычисление каждого операнда перед строгим составным применением
Связывание невычисленных выражений операндов как thunk нормального порядка
Форсирование thunk только тогда, когда поиск переменной требует ее значение
Наблюдение неиспользуемого аргумента при обеих стратегиях
Наблюдение дублирования работы при двукратном обращении к параметру нормального порядка
Сравнение двух явных стратегий вычисления guest

Процедура strict-eval вычисляет операнд перед применением составной процедуры. Поэтому игнорируемый аргумент x вызывает probe один раз, даже если тело возвращает 1. Процедура normal-eval вместо этого связывает x с thunk, содержащим выражение операнда и его окружение. Поскольку тело никогда не выполняет поиск x, процедура probe не запускается.

Во втором выражении тело использует x дважды. Строгое вычисление выполняет probe один раз и связывает полученное значение 10. Немемоизированный вычислитель нормального порядка форсирует сохраненное выражение при каждом поиске, поэтому probe запускается дважды. Оба возвращают 20, но объем работы различается. Эти два вычислителя представляют собой явные модели guest, и они не меняют порядок вычислений выполняющей их программы хоста Lispex.

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

(begin
  (define probes 0)
  (define (probe value)
    (set! probes (+ probes 1))
    value)
  (define (lookup name environment)
    (let ((record (assoc name environment)))
      (if record (cdr record) 'unbound)))
  (define (extend names values environment)
    (if (null? names)
        environment
        (cons (cons (car names) (car values))
              (extend (cdr names) (cdr values) environment))))
  (define (make-procedure parameters body environment)
    (list 'compound parameters body environment))
  (define (compound? value)
    (and (pair? value) (eq? (car value) 'compound)))
  (define (strict-eval expression environment)
    (cond ((number? expression) expression)
          ((symbol? expression) (lookup expression environment))
          ((and (pair? expression)
                (eq? (car expression) 'lambda))
           (make-procedure
             (cadr expression)
             (caddr expression)
             environment))
          ((pair? expression)
           (let ((procedure
                  (strict-eval (car expression) environment))
                 (arguments
                  (map (lambda (operand)
                         (strict-eval operand environment))
                       (cdr expression))))
             (cond ((procedure? procedure)
                    (apply procedure arguments))
                   ((compound? procedure)
                    (strict-eval
                      (caddr procedure)
                      (extend (cadr procedure)
                              arguments
                              (cadddr procedure))))
                   (else 'not-a-procedure))))
          (else 'unknown-expression)))
  (define (make-thunk expression environment)
    (list 'thunk expression environment))
  (define (thunk? value)
    (and (pair? value) (eq? (car value) 'thunk)))
  (define (force-normal value)
    (if (thunk? value)
        (normal-eval (cadr value) (caddr value))
        value))
  (define (normal-lookup name environment)
    (force-normal (lookup name environment)))
  (define (delay-operands operands environment)
    (map (lambda (operand)
           (make-thunk operand environment))
         operands))
  (define (actual-operands operands environment)
    (map (lambda (operand)
           (normal-eval operand environment))
         operands))
  (define (normal-eval expression environment)
    (cond ((number? expression) expression)
          ((symbol? expression)
           (normal-lookup expression environment))
          ((and (pair? expression)
                (eq? (car expression) 'lambda))
           (make-procedure
             (cadr expression)
             (caddr expression)
             environment))
          ((pair? expression)
           (let ((procedure
                  (normal-eval (car expression) environment)))
             (cond ((procedure? procedure)
                    (apply procedure
                           (actual-operands
                             (cdr expression)
                             environment)))
                   ((compound? procedure)
                    (normal-eval
                      (caddr procedure)
                      (extend
                        (cadr procedure)
                        (delay-operands
                          (cdr expression)
                          environment)
                        (cadddr procedure))))
                   (else 'not-a-procedure))))
          (else 'unknown-expression)))
  (define primitive-environment
    (list (cons '+ +)
          (cons 'probe probe)))
  (define unused-expression
    '((lambda (x) 1) (probe 10)))
  (define duplicated-expression
    '((lambda (x) (+ x x)) (probe 10)))
  (set! probes 0)
  (define strict-unused
    (list (strict-eval unused-expression primitive-environment)
          probes))
  (set! probes 0)
  (define normal-unused
    (list (normal-eval unused-expression primitive-environment)
          probes))
  (set! probes 0)
  (define strict-duplicated
    (list (strict-eval duplicated-expression primitive-environment)
          probes))
  (set! probes 0)
  (define normal-duplicated
    (list (normal-eval duplicated-expression primitive-environment)
          probes))
  (list (list 'unused strict-unused normal-unused)
        (list 'duplicated strict-duplicated normal-duplicated)))

(begin
  (define probes 0)
  (define (probe value)
    (set! probes (+ probes 1))
    value)
  (define (lookup name environment)
    (let ((record (assoc name environment)))
      (if record (cdr record) 'unbound)))
  (define (extend names values environment)
    (if (null? names)
        environment
        (cons (cons (car names) (car values))
              (extend (cdr names) (cdr values) environment))))
  (define (make-procedure parameters body environment)
    (list 'compound parameters body environment))
  (define (compound? value)
    (and (pair? value) (eq? (car value) 'compound)))
  (define (strict-eval expression environment)
    (cond ((number? expression) expression)
          ((symbol? expression) (lookup expression environment))
          ((and (pair? expression)
                (eq? (car expression) 'lambda))
           (make-procedure
             (cadr expression)
             (caddr expression)
             environment))
          ((pair? expression)
           (let ((procedure
                  (strict-eval (car expression) environment))
                 (arguments
                  (map (lambda (operand)
                         (strict-eval operand environment))
                       (cdr expression))))
             (cond ((procedure? procedure)
                    (apply procedure arguments))
                   ((compound? procedure)
                    (strict-eval
                      (caddr procedure)
                      (extend (cadr procedure)
                              arguments
                              (cadddr procedure))))
                   (else 'not-a-procedure))))
          (else 'unknown-expression)))
  (define (make-thunk expression environment)
    (list 'thunk expression environment))
  (define (thunk? value)
    (and (pair? value) (eq? (car value) 'thunk)))
  (define (force-normal value)
    (if (thunk? value)
        (normal-eval (cadr value) (caddr value))
        value))
  (define (normal-lookup name environment)
    (force-normal (lookup name environment)))
  (define (delay-operands operands environment)
    (map (lambda (operand)
           (make-thunk operand environment))
         operands))
  (define (actual-operands operands environment)
    (map (lambda (operand)
           (normal-eval operand environment))
         operands))
  (define (normal-eval expression environment)
    (cond ((number? expression) expression)
          ((symbol? expression)
           (normal-lookup expression environment))
          ((and (pair? expression)
                (eq? (car expression) 'lambda))
           (make-procedure
             (cadr expression)
             (caddr expression)
             environment))
          ((pair? expression)
           (let ((procedure
                  (normal-eval (car expression) environment)))
             (cond ((procedure? procedure)
                    (apply procedure
                           (actual-operands
                             (cdr expression)
                             environment)))
                   ((compound? procedure)
                    (normal-eval
                      (caddr procedure)
                      (extend
                        (cadr procedure)
                        (delay-operands
                          (cdr expression)
                          environment)
                        (cadddr procedure))))
                   (else 'not-a-procedure))))
          (else 'unknown-expression)))
  (define primitive-environment
    (list (cons '+ +)
          (cons 'probe probe)))
  (define unused-expression
    '((lambda (x) 1) (probe 10)))
  (define duplicated-expression
    '((lambda (x) (+ x x)) (probe 10)))
  (set! probes 0)
  (define strict-unused
    (list (strict-eval unused-expression primitive-environment)
          probes))
  (set! probes 0)
  (define normal-unused
    (list (normal-eval unused-expression primitive-environment)
          probes))
  (set! probes 0)
  (define strict-duplicated
    (list (strict-eval duplicated-expression primitive-environment)
          probes))
  (set! probes 0)
  (define normal-duplicated
    (list (normal-eval duplicated-expression primitive-environment)
          probes))
  (list (list 'unused strict-unused normal-unused)
        (list 'duplicated strict-duplicated normal-duplicated)))

Примеры

Результат—

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

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

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

Программа возвращает ((unused (1 1) (1 0)) (duplicated (20 1) (20 2))). Каждая пара содержит значение, за которым следует количество вызовов probe.

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

В strict-eval найдите вызов probe до начала выполнения составного тела. В normal-eval проследите за каждым связыванием параметра с thunk и убедитесь, что оно форсируется только при поиске переменной. Неиспользуемое тело не выполняет форсирование, а тело с дублированием обращается к одному и тому же выражению thunk дважды, поскольку эта модель намеренно не выполняет мемоизацию.

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

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

Добавьте ((lambda (x) (+ x (+ x x))) (probe 4)). Спрогнозируйте количество вызовов probe для строгого вычисления и нормального порядка, а затем добавьте ячейку мемоизации в thunk и спрогнозируйте количество вызовов при вызове по необходимости.

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

Строгое вычисление вычисляет аргумент один раз. Немемоизированный нормальный порядок выполняет вычисление один раз на каждый поиск x. Мемоизированный thunk вычисляет значение не более одного раза.

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

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