2.5.3 · 범용 기호 대수

다항식 패키지는 대수를 태그 데이터의 연산으로 바꾼다.

희소 항 목록은 차수와 계수를 명시적으로 보존합니다. 범용 add와 multiply 메서드는 같은 차수를 합치고 0 계수를 제거하며 다항식 변수를 유지하고 맞지 않는 변수는 거부합니다.

생각해 볼 질문

범용 산술 시스템은 항 목록의 세부 표현을 클라이언트 코드에 퍼뜨리지 않고 다항식 구조를 어떻게 다룰까요?

희소 다항식을 변수와 내림차순 항으로 표현하기
두 항 목록을 더하며 같은 차수 합치기
곱셈 중 한 항을 다른 다항식 전체에 분배하기
표현 경계에서 0 계수 항 제거하기
타입 태그 메서드로 다항식 덧셈과 곱셈 디스패치하기
변수가 다른 다항식의 연산 거부하기

첫 프로그램은 각 항을 차수와 계수로 표현하고 높은 차수부터 낮은 차수 순서로 저장합니다. add-terms는 앞에서 정렬 집합에 사용한 것과 같은 병합을 수행합니다. 더 큰 차수는 그대로 옮기고 같은 차수는 계수를 합치며 adjoin-term은 결과가 0인 항을 생략합니다. 다항식 패키지가 이 표현을 소유하고 태그가 붙은 add 메서드 하나를 노출하므로 x² + 2x + 1과 x² − 1의 합은 명시적인 0 상수항 없이 2x² + 2x가 됩니다. y 다항식은 서로 다른 미지수를 조용히 섞지 않고 different-variables를 반환합니다.

두 번째 프로그램은 한 항을 다른 다항식의 모든 항에 곱하고, 차수는 더하고 계수는 곱한 뒤, 부분 곱을 add-terms로 병합합니다. (x + 1)(x − 1)에서는 가운데 두 항이 상쇄되어 x² − 1만 남습니다. 별도 평가기는 패키지 선택자를 사용해 x = 3에서 8을 보고합니다. 이 수업은 태그 기반 덧셈과 곱셈과 정규화와 평가로 희소 단일 변수 정수 계수 다항식을 다룹니다.

SICP 코드UTF-8 2,685 / 1,048,576바이트

(begin
  (define (attach-tag type contents) (cons type contents))
  (define (type-tag object) (car object))
  (define (contents object) (cdr object))
  (define (make-term order coefficient)
    (list order coefficient))
  (define (order term) (car term))
  (define (coefficient term) (cadr term))
  (define (adjoin-term term terms)
    (if (= (coefficient term) 0)
        terms
        (cons term terms)))
  (define (add-terms left right)
    (cond ((null? left) right)
          ((null? right) left)
          (else
           (let ((left-term (car left))
                 (right-term (car right)))
             (cond ((> (order left-term) (order right-term))
                    (adjoin-term
                      left-term
                      (add-terms (cdr left) right)))
                   ((< (order left-term) (order right-term))
                    (adjoin-term
                      right-term
                      (add-terms left (cdr right))))
                   (else
                    (adjoin-term
                      (make-term
                        (order left-term)
                        (+ (coefficient left-term)
                           (coefficient right-term)))
                      (add-terms (cdr left) (cdr right)))))))))
  (define (make-polynomial variable terms)
    (attach-tag 'polynomial (cons variable terms)))
  (define (variable polynomial-contents)
    (car polynomial-contents))
  (define (term-list polynomial-contents)
    (cdr polynomial-contents))
  (define (add-polynomial-contents left right)
    (if (eq? (variable left) (variable right))
        (make-polynomial
          (variable left)
          (add-terms (term-list left) (term-list right)))
        'different-variables))
  (define operation-table
    (list
      (cons (list 'add 'polynomial 'polynomial)
            add-polynomial-contents)))
  (define (lookup-entry key table)
    (cond ((null? table) #f)
          ((equal? key (car (car table)))
           (cdr (car table)))
          (else (lookup-entry key (cdr table)))))
  (define (apply-generic operation left right)
    (let ((method
            (lookup-entry
              (list operation (type-tag left) (type-tag right))
              operation-table)))
      (if method
          (method (contents left) (contents right))
          'no-method)))
  (define p
    (make-polynomial
      'x
      (list (make-term 2 1)
            (make-term 1 2)
            (make-term 0 1))))
  (define q
    (make-polynomial
      'x
      (list (make-term 2 1)
            (make-term 0 -1))))
  (define y
    (make-polynomial 'y (list (make-term 1 1))))
  (list (apply-generic 'add p q)
        (apply-generic 'add p y)))

(begin
  (define (attach-tag type contents) (cons type contents))
  (define (type-tag object) (car object))
  (define (contents object) (cdr object))
  (define (make-term order coefficient)
    (list order coefficient))
  (define (order term) (car term))
  (define (coefficient term) (cadr term))
  (define (adjoin-term term terms)
    (if (= (coefficient term) 0)
        terms
        (cons term terms)))
  (define (add-terms left right)
    (cond ((null? left) right)
          ((null? right) left)
          (else
           (let ((left-term (car left))
                 (right-term (car right)))
             (cond ((> (order left-term) (order right-term))
                    (adjoin-term
                      left-term
                      (add-terms (cdr left) right)))
                   ((< (order left-term) (order right-term))
                    (adjoin-term
                      right-term
                      (add-terms left (cdr right))))
                   (else
                    (adjoin-term
                      (make-term
                        (order left-term)
                        (+ (coefficient left-term)
                           (coefficient right-term)))
                      (add-terms (cdr left) (cdr right)))))))))
  (define (make-polynomial variable terms)
    (attach-tag 'polynomial (cons variable terms)))
  (define (variable polynomial-contents)
    (car polynomial-contents))
  (define (term-list polynomial-contents)
    (cdr polynomial-contents))
  (define (add-polynomial-contents left right)
    (if (eq? (variable left) (variable right))
        (make-polynomial
          (variable left)
          (add-terms (term-list left) (term-list right)))
        'different-variables))
  (define operation-table
    (list
      (cons (list 'add 'polynomial 'polynomial)
            add-polynomial-contents)))
  (define (lookup-entry key table)
    (cond ((null? table) #f)
          ((equal? key (car (car table)))
           (cdr (car table)))
          (else (lookup-entry key (cdr table)))))
  (define (apply-generic operation left right)
    (let ((method
            (lookup-entry
              (list operation (type-tag left) (type-tag right))
              operation-table)))
      (if method
          (method (contents left) (contents right))
          'no-method)))
  (define p
    (make-polynomial
      'x
      (list (make-term 2 1)
            (make-term 1 2)
            (make-term 0 1))))
  (define q
    (make-polynomial
      'x
      (list (make-term 2 1)
            (make-term 0 -1))))
  (define y
    (make-polynomial 'y (list (make-term 1 1))))
  (list (apply-generic 'add p q)
        (apply-generic 'add p y)))

예제

결과—

출력: —
값: —
진단: —

실행 추적0 / 0 개 이벤트

예상 결과

덧셈 프로그램은 ((polynomial x (2 2) (1 2)) different-variables)를 반환합니다. 곱셈 프로그램은 ((polynomial x (2 1) (0 -1)) 8)을 반환합니다.

실행 추적에서 볼 점

덧셈에서는 내림차순 차수 비교와 같은 차수 계수 합이 0 상수항을 제거하는 지점을 따라가세요. 곱셈에서는 각 차수 이동과 계수 곱, 재귀적인 부분 곱, 두 1차 항을 상쇄하는 add-terms 병합을 찾으세요. 변수 검사는 표현 연산이 시작되기 전에 일어납니다.

직접 해보기

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

x² + x + 1과 x − 1을 곱하고 희소 항 목록을 예상한 뒤 x = 2에서 값을 계산하세요.

힌트 보기

왼쪽의 각 항마다 부분 곱을 하나 만들고 같은 차수를 병합하세요. 1차항과 상수항의 상쇄는 서로 다른 단계에서 일어납니다.

이 수업 완료하기

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