SICP 연습문제 2.73 친절한 풀이

,
데이터 중심 설계 방식으로 미분 프로시저 설계하기

문제

2.3.2절에서는 글자로 이루어진 식을 다음 프로그램으로 미분하였다.

(define (deriv exp var)   
  (cond ((number? exp) 0) 
        ((variable? exp)
         (if (same-variable? exp var) 1 0)) 
        ((sum? exp)
         (make-sum (deriv (addend exp) var)   
                   (deriv (augend exp) var))) 
        ((product? exp)
         (make-sum
          (make-product (multiplier exp)
                        (deriv (multiplicand exp) var))
          (make-product (deriv (multiplier exp) var)
                        (multiplicand exp)))) 
        <추가된 규칙들은 여기에>
        (else "unknown expression type")))

이 또한 식이 어떤 타입이냐에 따라 할 일을 나누어 맡기는 프로그램이라 볼 수 있다. 이 경우에는 (+ 같은) 대수식의 연산 기호가 데이터의 '타입 흐름표’가 되고, deriv는 그 데이터를 적용할 연산이 된다. 이 프로그램을 데이터 중심 방식으로 바꾸려면 위 미분 프로시저를 다음과 같이 고쳐 쓰면 된다.

(define (deriv exp var)
   (cond ((number? exp) 0)
         ((variable? exp) (if (same-variable? exp var) 1 0))
         (else ((get 'deriv (operator exp)) (operands exp)
                                            var))))
(define (operator exp) (car exp))

(define (operands exp) (cdr exp))

a. 위에서 한 일이 무엇인지 설명해 보라. number?나 variable?같은 술어 프로시저를 모조리 데이터 중심 방식으로 다루지 못하는 이유는 무엇인가?

b. 덧셈과 곱셈식을 미분하는 프로시저를 짜라. 그런 다음, 그 프로시저들을 위 프로그램에서 쓰는 표에 집어넣는데 필요한 코드를 짜라.

c. (연습문제 2.56에서 나온 것처럼) 지수 식을 미분하는 것과 같이, 새로 보태고 싶은 규칙을 하나 골라 여기서 만든 데이터 중심 시스템에 집어넣어라.

d. 이런 단순한 대수 처리 방식에서는, 식에 붙은 연산자가 그 식의 타입을 나타낸다. 이때 '연산자와 타입’이 아니라 '타입과 연산자’로 프로시저 인덱스가 붙어 있다면, deriv 속에 알맞은 프로시저를 꺼내 쓰는 코드 dispatching code 가 다음과 같이 바뀐다.

((get (operator exp) 'deriv) (operands exp) var)

이 경우, 미분 시스템에는 어떤 변화가 필요한가?

문제로 부터 얻은 것

데이터 중심 프로그래밍 기법으로 프로시저를 짜면 확실히 몇가지 이점을 얻을 수 있다는 것을 알게 되었습니다.

  1. 패키지 내부의 프로시저를 숨길 수 있었습니다.
  2. 새로운 연산을 추가하기가 기존보다 훨씬 편했습니다. (additivity)

문제풀이

dr.racket에는 put과 get이 빌트인되어있지 않습니다. 아래의 코드를 사용하면 put과 get을 사용할 수 있습니다.

(define global-array '())

(define (make-entry k v) (list k v))
(define (key entry) (car entry))
(define (value entry) (cadr entry))

(define (put op type item)
  (define (put-helper k array)
    (cond ((null? array) (list(make-entry k item)))
          ((equal? (key (car array)) k) array)
          (else (cons (car array) (put-helper k (cdr array))))))
  (set! global-array (put-helper (list op type) global-array)))

(define (get op type)
  (define (get-helper k array)
    (cond ((null? array) #f)
          ((equal? (key (car array)) k) (value (car array)))
          (else (get-helper k (cdr array)))))
  (get-helper (list op type) global-array))

그리고 교재의 2.3.2절의 프로시저 중, 이번 문제에 필요한 프로시저는 다음과 같습니다.

(define (variable? x)
  (symbol? x))

(define (same-variable? x y)
  (eq? x y))

(define (=number? exp num)
  (and (number? exp) (= exp num)))

(define (make-sum x y)
  (cond ((=number? x 0) y)
        ((=number? y 0) x)
        ((and (number? x) (number? y)) (+ x y))
        (else (list '+ x y))))

(define (make-product x y)
  (cond ((or (=number? x 0) (=number? y 0)) 0)
        ((=number? x 1) y)
        ((=number? y 1) x)
        ((and (number? x) (number? y)) (* x y))
        (else (list '* x y))))

a. 프로시저의 원리

책의 2.4.3절에서는 데이터 중심 프로그래밍에 대해 설명하고 있습니다. 제가 이해한 데이터 중심 프로그래밍 기법은 데이터의 종류에 따라 가장 알맞은 연산을 적용하기 위한 프로그래밍 기법입니다. 위의 deriv는 연습문제 2.56에서 처음 만들었던 것 처럼, 수식에서 변수와 연산자를 뽑아내어 각각에 맞게 미분을 하는 프로시저입니다. 미분하는 대상이 변수인지 상수인지에따라 또, 연산자가 곱셈인지 덧셈인지에 따라 즉, 데이터의 타입에 따라 다른 방식으로 미분을 진행하므로, 데이터 중심 설계를 하기에 알맞다고 할 수 있습니다.

number?나 variable?같은 술어 프로시저를 모조리 데이터 중심 방식으로 다루지 못하는 이유는, 술어 프로시저가 적용될 가능성이 있는 모든 데이터를 연산표에 기록하는 것은 현실적으로 불가능하기 때문이라고 생각합니다.

b. 덧셈과 곱셈식을 미분하는 프로시저

원본 프로시저에 있던 +와 *을 데이터 중심 프로그래밍 방식으로 나타내면 됩니다. 미분 프로시저를 제대로 기억하고 있지 않거나, 교재의 put과 get의 용도를 이해하지 못했다면, 어렵게 느껴질 수도 있습니다. 여유를 가지고 페이지를 앞으로 넘겨서 제대로 복습하고 오시길 바랍니다.

기존에 만들어둔 미분 프로시저의 핵심이 되는 미분 연산을 변형하면 아래와 같습니다.

(define (derive-sum operands var)
  (make-sum (deriv (addend operands) var)
            (deriv (augend operands) var)))

(define (deriv-product operands var)
  (make-sum
   (make-product (multiplier operands)
                 (deriv (multiplicand operands) var))
   (make-product (deriv (multiplier operands) var)
                 (multiplicand operands))))

각 연산을 교재의 2.4.3절처럼 패키지 형태로 만들어 보겠습니다.

(define (install-sum-deriv)
  (define (addend operands)
    (car operands))
  (define (augend operands)
    (cadr operands))
  (define (deriv-sum operands var)
    (make-sum (deriv (addend operands) var)
              (deriv (augend operands) var)))
  
  (put 'deriv '+ deriv-sum))

(define (install-product-deriv)
  (define (multiplier operands)
    (car operands))
  (define (multiplicand operands)
    (cadr operands))
  (define (deriv-product operands var)
    (make-sum
     (make-product (multiplier operands)
                   (deriv (multiplicand operands) var))
     (make-product (deriv (multiplier operands) var)
                   (multiplicand operands))))

  (put 'deriv '* deriv-product))

c. 지수식 미분

(연습문제 2.56의 exponentiation을 그대로 따왔습니다.

(define (fast-exp b n)
  (cond ((= n 0) 1)
        ((even? n) (square (fast-exp b (/ n 2))))
        (else (* b (fast-exp b (- n 1))))))
    
(define (make-exponentiation base power)
  (cond ((=number? base 0) 0)
        ((=number? base 1) 1)
        ((=number? power 0) 1)
        ((=number? power 1) base)
        ((and (number? base) (number? power)) (fast-exp base power))
        (else (list '^ base power))))
    
(define (install-exponentiation-deriv)
  (define (base operands)
    (car operands))
  (define (power operands)
    (cadr operands))
  (define (deriv-exponentiation operands var)
    (make-product
     (deriv (base operands) var)
     (make-product (power operands)
                   (make-exponentiation (base operands)
                                        (make-sum (power operands) -1)))))
  (put 'deriv '^ deriv-exponentiation))

d. 연산자와 데이터 타입 순서 변경

문제에서 요구한대로 deriv를 바꾸면 다음과 같습니다.

(define (deriv exp var)
   (cond ((number? exp) 0)
         ((variable? exp) (if (same-variable? exp var) 1 0))
         (else ((get (operator exp) 'deriv) (operands exp)
                                            var))))

단순히 모든 put을 쓰는 프로시저들의 순서만 바꿔주면 그만입니다.

(put '+ 'deriv deriv-sum)

(put '* 'deriv deriv-product)

(put '^ 'deriv deriv-exponentiation)

읽어주셔서 감사합니다.