4.2.1 · 정상 순서와 적용적 순서

평가 순서는 인자가 언제 작업이 되는지 결정한다.

같은 guest 적용을 strict 평가기와 메모이즈하지 않은 정상 순서 평가기로 실행하고 사용하지 않은 인자와 두 번 참조한 인자의 probe 횟수를 셉니다.

생각해 볼 질문

평가기 두 개가 같은 값을 반환하면서도 서로 다른 인자 작업을 수행할 수 있는 이유는 무엇일까요?

strict compound 적용 전에 모든 피연산자 평가하기
평가하지 않은 피연산자 식을 정상 순서 thunk로 바인딩하기
변수 조회가 값을 필요로 할 때만 thunk 강제하기
사용하지 않은 인자를 두 전략에서 관찰하기
정상 순서 매개변수를 두 번 참조할 때 중복 작업 관찰하기
명시적인 두 guest 평가 전략 비교하기

strict-eval은 compound procedure를 적용하기 전에 피연산자를 평가합니다. 따라서 본문이 1만 반환하고 x를 쓰지 않아도 인자 probe는 한 번 호출됩니다. normal-eval은 x를 피연산자 식과 환경을 담은 thunk로 바인딩합니다. 본문이 x를 조회하지 않으므로 probe는 실행되지 않습니다.

두 번째 식은 본문에서 x를 두 번 사용합니다. strict 평가는 probe를 한 번 계산하고 결과 10을 바인딩합니다. 메모이즈하지 않은 정상 평가기는 조회마다 저장한 식을 강제하므로 probe를 두 번 실행합니다. 둘 다 20을 반환하지만 작업량은 다릅니다. 두 평가기는 명시적인 guest 모형이며 실행 중인 호스트 리스펙스의 평가 순서를 바꾸지 않습니다.

SICP 코드UTF-8 4,328 / 1,048,576바이트

(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)))를 반환합니다. 각 pair는 값과 probe 호출 수입니다.

실행 추적에서 볼 점

strict-eval에서는 compound 본문이 시작하기 전에 probe를 찾으세요. normal-eval에서는 각 매개변수 바인딩을 thunk까지 따라가고 변수 조회에서만 강제되는지 확인하세요. unused 본문은 강제하지 않고 duplicated 본문은 이 모형이 메모이즈하지 않으므로 같은 thunk 식에 두 번 도달합니다.

직접 해보기

프로그램을 수정하고 결과를 비교해 보세요.

((lambda (x) (+ x (+ x x))) (probe 4))를 추가하세요. strict와 normal의 probe 횟수를 예상한 뒤 thunk에 memo 셀을 추가했을 때 call-by-need 횟수를 예상하세요.

힌트 보기

strict는 인자를 한 번 계산합니다. 메모이즈하지 않은 normal은 x 조회마다 계산하고 memoized thunk는 최대 한 번 계산합니다.

이 수업 완료하기

이 장의 총 23개 수업 중 0개 완료0%