SICP 연습문제 2.58 친절한 풀이

문제

+와 *같은 연산자를 인자 앞에 두지 않고 수학에서 흔히 쓰던 대로 속가지 쓰기를 할 수 있도록 미분 프로그램을 고치려 한다. 미분 프로스램을 정의할 때 대수식 데이터를 간추려 썼기 때문에 대수식의 표현을 정의하는 연산, 곧 짜맞추개, 고르개, 술어 연산만 손보아도 표현 방식이 다른 대수식을 받아들이도록 만들 수 있다.

a. (x + (3 * (x + (y + 2))))와 같이 속가지 형태로 대수식을 표현했을 때, 이를 어떻게 미분할지 밝혀라. 일을 쉽게 만들기 위해서, +와 *가 받는 인자는 두 개뿐이며 (연산자 우선순위가 헛갈리지 않도록) 모든 식에서 괄호를 빠뜨리지 않는다고 하자.

b. (x + 3 * (x + y + 2))처럼 표준 대수식 쓰기법, 다시 말해서 쓸데없는 괄호를 빼고 덧셈보다 곱셈을 먼저 계산한다는 규칙을 따르기로 하면, 문제가 훨씬 어려워진다. 이런 쓰기법을 따르더라도 미분 프로스램이 제대로 돌아가도록 그에 알맞은 술어, 고르개, 짜맞추개 연산을 설계할 수 있는가?1

문제로 부터 얻은 것

추상화 장벽을 이용해 다층 설계를 하면, 이런 것까지 할 수 있구나 하는 것을 느끼게하는 문제였습니다.

문제풀이

문제 풀이를 위한 기본 프로시저들입니다.

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

(define (same-variable? v1 v2) 
 (and (variable? v1) (variable? v2) (eq? v1 v2))) 

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

(define (make-product m1 m2) 
 (cond ((or (=number? m1 0) (=number? m2 0)) 0) 
       ((=number? m1 1) m2) 
       ((=number? m2 1) m1) 
       ((and (number? m1) (number? m2)) (* m1 m2)) 
       (else (list '* m1 m2)))) 
 
(define (=number? exp num) 
 (and (number? exp) (= exp num))) 

(define (sum? x) 
 (and (pair? x) (eq? (car x) '+))) 

(define (addend s) (cadr s)) 

(define (augend s) (caddr s)) 

(define (product? x) 
 (and (pair? x) (eq? (car x) '*))) 

(define (multiplier p) (cadr p)) 

(define (multiplicand p) (caddr p)) 

(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)))) 
        ((exponentiation? exp) 
         (let ((b (base exp)) (n (exponent exp))) 
           (make-product n
                         (make-product (make-exponentiation b (make-sum n -1))
                                       (deriv b var))))) 
        (else "unknown expression type")))

a. 속가지 형태 대수식

속가지 형태의 대수식을 프로시저로 해석하는 것은 쉬웠습니다. 평소에는 리스트의 첫번째 원소이던 연산자를 두번째 원소로 바꾼 것 뿐입니다.

(x + (3 * (x + (y + 2))))

(define (sum? x)
  (and (pair? x) (eq? (cadr x) '+))) 
  
(define (addend s) (car s)) 
  
(define (augend s) (caddr s))


(define (product? x) 
  (and (pair? x) (eq? (cadr x) '*))) 
  
(define (multiplier p) (car p)) 
  
(define (multiplicand p) (caddr p)) 

b. 표준 대수식

표준 대수식은 앞의 문제보다 훨씬 까다로웠습니다. 문제 해결을 위해 떠올린 저의 아이디어는 이렇습니다.
우선 곱셈보다 덧셈을 기준으로 식을 쪼개기로 했습니다. 사칙연산의 규칙에 의해서 곱셈이 덧셈보다 먼저 계산되므로, 식을 쪼갤 때는 덧셈을 단위로 쪼개야 합니다. 아래의 예시의 (x + y + 2)처럼 괄호 안에 있는 덧셈을 착각해서 쪼개버리면 어떡하지라는 생각을 하실 수도 있습니다. 하지만 상위 식의 입장에서는 (x + y + 2)를 하나의 인자로 인식하기 때문에 걱정할 필요가 없습니다. 곱셈보다 덧셈을 먼저 쪼개는 것은 deriv의 cond식에 product?보다 sum?이 앞에 있으므로 수정할 코드는 없었습니다.
그리고 이번 문제의 가장 까다로운 점은, +라는 기호가 식의 어디에 있는지를 탐색해야 한다는 것입니다. addend와 augend 프로시저의 내부에는 iter를 따로 정의해서 이 +라는 기호를 찾고 앞뒤에 있는 식들을 각각 반환하는 것으로 프로시저를 짰습니다. augend를 짤 때는 주의해야 할 점이 있는데, 자칫 숫자를 반환해야 하는 상황에서 숫자가 담긴 리스트를 반환할 수 있다는 것입니다. ex. (3) 때문에 +연산자의 뒤에 있는 식이 단일 숫자인지 또다른 식인지를 판단하는 기능도 추가해야 합니다.
위의 아이디어를 프로시저로 구현하면 아래와 같습니다.

(x + 3 * (x + y + 2))

(define (sum? x)
  (define (iter x)
    (cond ((null? (cdr x)) #f)
          ((eq? (cadr x) '+) #t)
          (else (iter (cddr x)))))
  (and (pair? x) (iter x))) 
  
(define (addend s)
  (define (iter s result)
    (if (eq? (cadr s) '+)
        result
        (iter (cddr s) (append result (list (cadr s) (caddr s))))))
  (iter s (car s))) 
  
(define (augend s)
  (define (iter s)
    (if (eq? (cadr s) '+)
        (if (null? (cdddr s))
            (caddr s)
            (cddr s))
        (iter (cddr s))))
  (iter s))


(define (product? x) 
  (and (pair? x) (eq? (cadr x) '*))) 
  
(define (multiplier p) (car p)) 
  
(define (multiplicand p)
  (if (null? (cdddr p))
      (caddr p)
      (cddr p)))  

읽어주셔서 감사합니다.