제네릭 연산의 체계

하나의 데이터 객체를 다른 방법으로 표현하여 디자인하는 시스템을 살펴보았다. 

중요한 아이디어는, 제네릭 인터페이스 프로시저들을 통해, 데이터 연산들을 몇몇의 표현에 연결하는 것이었다. 

이제 우리는 이러한 아이디어를 다른 표현에 이용하는데 그치지 않고 다른 인자들에도 접목하도록 한다.

우린 산술 연산들의 다양한 패키지를 이미 살펴보았다: 기본 산술 연산자들, (+, -, *, /) 

유리수 산술 연산 (add-rat, sub-rat, mul-rat, div-rat), 복소수 산술 연산들이 바로 그 것.

우리는 이제 데이터기반 테크닉을 산술연산의 패키지를 생성하는데 사용할 것이다.

누군가 "숫자"를 산다는 관점에서, add 연산이 제공된다. ADD 는 제네릭인터페이스의 일부인데, 별개의 일반적인 산술, 유리수 산술, 복소수 산술 패키지들이 일관된 형태로 접근 된다. 

어떤 별개의 산술연산 패키지는 제네릭 프로시져를 통해 접근되며, 이 프로시져는 패키지를 다른 표현으로 디자인된 패키지에 결합 (retangluar / polar ) 한다. 더 나아가, 이 시스템은 추가가 간편해서, 개별의 산술 패키지를 추가하고 제네릭 산술 시스템을 생성하도록 결합하는 것이 가능하다. 

2.5.1 제네릭 산술연산 

제네릭 산술 연산을 디자인 하는것은 제네릭 복소수 연산을 만드는 것과 유사하다. 예를 들면, 제네릭 프로시저 add 는 일반적인 수에는 + 를 적용하고, 유리수에는 add-rat 을 동작케하는 것과 같다. 다른 제네릭 산술 연산을 추가하기위해 2.4.3 에서 보았던 복소수를 위한 제네릭 선택자를 구현하는 것과 같은  전략을 사용하면 된다.

tag 를 추가하고 제네릭 프로시져가 적절한 패키지를 그것의 인자에 따라 디스패치하도록 한다.

제네릭 산술 연산은 다음과 같이 정의 된다.

(define (add x y) (apply-generic 'add x y))

(define (sub x y) (apply-generic 'sub x y))

(define (mul x y) (apply-generic 'mul x y))

(define (div x y) (apply-generic 'div x y))

일반 수에 대해서부터 시작해보자. tag 는 scheme-number

(define (install-scheme-number-package)

(define (tag x)

(attach-tag 'scheme-number x))

(put 'add '(scheme-number scheme-number)

(lambda (x y) (tag (+ x y))))

(put 'sub '(scheme-number scheme-number)

(lambda (x y) (tag (- x y))))

(put 'mul '(scheme-number scheme-number)

(lambda (x y) (tag (* x y))))

(put 'div '(scheme-number scheme-number)

(lambda (x y) (tag (/ x y))))

(put 'make 'scheme-number

(lambda (x) (tag x)))

'done)

scheme-number 패키지의 사용자는 다음 프로시져를 통해 숫자를 생성한다.

(define (make-scheme-number n)

((get 'make 'scheme-number) n))

제네릭산술체계의 틀이 잡혔으므로, 쉽게 새로운 종류의 수를 추가할 수 있다. 

추가가 손쉽다는 이점을 살려, 2.1.1 의 유리수 코드의 교체 없이 추가할수 있다.

(define (install-rational-package)

;; internal procedures

(define (numer x) (car x))

(define (denom x) (cdr x))

(define (make-rat n d)

(let ((g (gcd n d)))

(cons (/ n g) (/ d g))))

(define (add-rat x y)

(make-rat (+ (* (numer x) (denom y))

 (* (numer y) (denom x)))

   (* (denom x) (denom y))))

(define (sub-rat x y)

(make-rat (- (* (numer x) (denom y))

 (* (numer y) (denom x)))

   (* (denom x) (denom y))))

(define (mul-rat x y)

(make-rat (* (numer x) (numer y))

   (* (denom x) (denom y))))

(define (div-rat x y)

(make-rat (* (numer x) (denom y))

   (* (denom x) (numer y))))

;; interface to rest of the system

(define (tag x) (attach-tag 'rational x))

(put 'add '(rational rational)

(lambda (x y) (tag (add-rat x y))))

(put 'sub '(rational rational)

(lambda (x y) (tag (sub-rat x y))))

(put 'mul '(rational rational)

(lambda (x y) (tag (mul-rat x y))))

(put 'div '(rational rational)

(lambda (x y) (tag (div-rat x y))))

(put 'make 'rational

(lambda (n d) (tag (make-rat n d))))

'done)

(define (make-rational n d)

((get 'make 'rational) n d))

유사한 패키지를 complex 태그를 사용하여 복소수를 다루는데 추가할 수 있다. 

(define (install-complex-package)

;; imported procedures from rectangular and polar packages

(define (make-from-real-imag x y)

((get 'make-from-real-imag 'rectangular) x y))

(define (make-from-mag-ang r a)

((get 'make-from-mag-ang 'polar) r a))

;; internal procedures

(define (add-complex z1 z2)

(make-from-real-imag (+ (real-part z1) (real-part z2))

   (+ (imag-part z1) (imag-part z2))))

(define (sub-complex z1 z2)

(make-from-real-imag (- (real-part z1) (real-part z2))

   (- (imag-part z1) (imag-part z2))))

(define (mul-complex z1 z2)

(make-from-mag-ang (* (magnitude z1) (magnitude z2))

  (+ (angle z1) (angle z2))))

(define (div-complex z1 z2)

(make-from-mag-ang (/ (magnitude z1) (magnitude z2))

(- (angle z1) (angle z2))))

;; interface to rest of the system

(define (tag z) (attach-tag 'complex z))

(put 'add '(complex complex)

(lambda (z1 z2) (tag (add-complex z1 z2))))

(put 'sub '(complex complex)

(lambda (z1 z2) (tag (sub-complex z1 z2))))

(put 'mul '(complex complex)

(lambda (z1 z2) (tag (mul-complex z1 z2))))

(put 'div '(complex complex)

(lambda (z1 z2) (tag (div-complex z1 z2))))

(put 'make-from-real-imag 'complex

(lambda (x y) (tag (make-from-real-imag x y))))

(put 'make-from-mag-ang 'complex

(lambda (r a) (tag (make-from-mag-ang r a))))

'done)

이 패키지 외부의 프로그램은 복소수를 rectangluar form / ploarform 모두를 사용할 수 있다. 

바탕이 되는 프로시져가 (실제로는 어느한쪽의 패키지에 정의되어있는) 복소수 패키지 바깥으로 보여지고 있으며, 외부세계로 exported 하고 있다. 

(define (make-complex-from-real-imag x y)

((get 'make-from-real-imag 'complex) x y))

(define (make-complex-from-mag-ang r a)

((get 'make-from-mag-ang 'complex) r a))

여기서는 2단계의 태그 시스템을 가지고 있다. 어떤 표현방식 ( rec / pol ) 인지, 어떤 수인지 ( complex ) .

크고 복잡한 시스템에서는 많은 단계를 가지고 있을수 있으며, 다음을 위한 인터페이스들은 제네릭연산으로 인터페이스를 갖게 된다. 데이터 객체들이 "하위로" 전달됨에 따라, 바깥의 태그는 적절한 패키지로 방향을 잡고 contents 를 정요하여  이를 떼어내어 다음 단계의 태그가 앞으로의 dispatch 대상이 되도록 한다.

위의 패키지에서 add-rat / add-complex 를 완전히 예전에 썼던 코드를 그대로 사용하였다. 일단 각 인스톨 프로시져의 내부로 들어가게되면, 더이상 각각을 구분하기위한 이름은 필요없으므로, 단순한 이름을 사용하여도 된다. 

허프만 인코딩 트리

이 절에서는 리스트 구조와 set 과 tree 를 다루기 위한 데이터 추상화를 연습해 보았다.

컴퓨터에서는 데이터를 나타내기 위해 0, 1 의 연속된 값을 사용하는데, 

아스키코드가 각각의 문자를 7개 비트를 활용하여 표현하는 것이 그 예라 할 수 있다.

7 비트를 사용하면 2^7 개의 데이터를 구분할 수 있다, 

일반적으로 n 개를 표현하기 위해 개의 비트가 필요하다

고정길이 인코딩 방식

예를 들면 문자를 표현하기 위해

A 000 C 010 E 100 G 110

B 001 D 011 F 101 H 111

와 같이 표현할 수 있다.

이를 따를때, 

BACADAEAFABBAAAGAH

는 다음과 같이 인코딩 된다 

001000010000011000100000101000001001000000000110000111 (54비트)

이런 코드방식을 각각의 심볼이 같은 개수의 비트로 구성되어 있으므로, fixed-length (고정길이) 코드라고 부른다.

고정 길이 대신 가변 방식의 코딩도 쓸모 있을때가 있다. 

가변길이 인코딩 방식

빈도가 월등히 높은 문자에 대해 좀더 적은 비트수를 할당하여, 데이터를 좀더 효율적으로 메시지를 인코딩 할 수 있다.

위 고정길이 인코딩방식의 예를 variable-length (가변길이) 인코딩 방식으로 다음과 같이 재정의해보자.

A 0 C 1010 E 1100 G 1110

B 100 D 1011 F 1101 H 1111

이제, 같은 문자를 다음과 같이 인코딩한다.

100010100101101100011010100100000111001111 (42비트)

고정 길이 인코딩 방식과 비교했을때 20% 가량의 공간절약 효과를 얻을 수 있다.

이런 가변길이 인코딩방식에도 문제가 있는데, 바로 어떤 지점에서 하나의 심볼이 종료된 것인지 알기가 어렵다는 것이다. 

모스코드는 이런문제를 특별한 구분자(seperator code) 를 두는 것으로 해결 했다. 또 다른 해결책은, 

어떤 심볼도 다른 문자의 인코딩 값을 시작 코드값으로 가질 수 없도록 디자인 하는 것이다.

A를 0 이라고 정한 위 예의 경우, 어떤 문자도 0으로 시작할 수 없다. 

일반적으로 가변길이 prefix 인코딩 방식을 적절히 사용하면 상당한 이점을 볼수있다. 

이런 인코딩의 한 scheme 이 huffman 인코딩 방식이며, 허프만인코딩은 바이너리 트리로 표현되어 심볼을 인코드 할 수 있다.

허프만 인코딩

허프만트리에서 각 리프는 상대빈도와 나타내고자하는 문자가 함께 표시되어 있다. 

어떤 심볼이든 root 에서 시작하여 리프로 도달하여야 문자가 있음을 확인할 수 있다. 

아래로 내려갈때, 왼쪽 가지로 가는경우 0을 추가하고, 반대로 오른쪽으로 이동하면 1을 추가한다. 

D 의 경우 1011 이 된다.

비트열을 허프만 트리를 통해 decode 하고자 하면, root 에서 시작하여 비트열의 숫자를 보고 트리를 쫗아가면 된다.

리프에 도달할때마다 심볼을 알아낸 것이되고, 다시 다음 심볼을 알아내기위해 root 로 돌아가면 된다. 

허프만 트리의 생성

알파벳과 상대빈도가 주어져있으면, 어떻게 코드를 만드는게 최선일까? 

다음 예제를 살펴보자. 

알고리즘은 간단하다. 

가장 적은 상대빈도를 지닌 심볼이 가장 멀리 위치하는 것이다.

리프노드의 집합으로부터 시작하여 가장 빈도수가 낮은 두개의 노드를 찾아 이를 왼쪽노드, 오른쪽노드로 갖는 

부모노드를 만들며, 이 노드가 두 가중치의 합을 갖게끔한다.

두 노드를 set 에서 제거하고, 대신 이 새 노드로 대체한다. 이제 이 과정을 반복한다. 

노드가 단 하나만 남을때까지 이 과정을 반복한다. 

다음과 같은 과정으로 진행된다 .

Initial leaves {(A 8) (B 3) (C 1) (D 1) (E 1) (F 1) (G 1) (H 1)}

Merge {(A 8) (B 3) ({C D} 2) (E 1) (F 1) (G 1) (H 1)}

Merge {(A 8) (B 3) ({C D} 2) ({E F} 2) (G 1) (H 1)}

Merge {(A 8) (B 3) ({C D} 2) ({E F} 2) ({G H} 2)}

Merge {(A 8) (B 3) ({C D} 2) ({E F G H} 4)}

Merge {(A 8) ({B C D} 5) ({E F G H} 4)}

Merge {(A 8) ({B C D E F G H} 9)}

Final merge {({A B C D E F G H} 17)}

이 알고리즘은 항상 유일한 트리를 만드는 것이 아닌데, 여러 노드가 가장 작은 가중치를 가질 수도 있기때문에다. 또한, 어떤 두 노드가 먼저 merge 될지 결정하는 것도 임의기 때문이기도 하다. 

허프만 트리의 표현

이제 허프만트리를 메시지를 인코드/디코드하는데 사용하고, 허프만트리를 생성하는 시스템을 살펴보자.

각 리프들은 leaf 라는 심볼을 포함한 리스트로 표현한다.

(define (make-leaf symbol weight)

(list 'leaf symbol weight))

(define (leaf? object)

(eq? (car object) 'leaf))

(define (symbol-leaf x) (cadr x))

(define (weight-leaf x) (caddr x))

두 노드를 merge 하게 되면, 두 노드의 union 을 한 심볼의 집합이 된다.

우리의 심볼집합은 리스트로 표현했기 때문에, union 을 위해 append 프로시져를 사용한다.

(define (make-code-tree left right)

(list left

right

(append (symbols left) (symbols right))

(+ (weight left) (weight right))))

- (left right (symbol-l symbol-r) sum-wgt-lr) 와 같은 리스트 구조가 되겠다.

이제 selector 를 정의한다. 

(define (left-branch tree) (car tree))

(define (right-branch tree) (cadr tree))

(define (symbols tree)

(if (leaf? tree)

   (list (symbol-leaf tree))

   (caddr tree)))

(define (weight tree)

(if (leaf? tree)

(weight-leaf tree)

(cadddr tree)))

- 위에서 설명한 리스트 형태와 컬러링으로 매칭시켜보면 (left right (symbol-l symbol-r) sum-wgt-lr)

여기서보면 symbols 와 weight selector 들은 leaf 여부에 따라 그 동작이 다르다.

이를 잘 다루기 위해 친숙한 개념인 generic 을 scheme 에서도 사용할 수 있는데, 이는 2.4 절과 2.5절에서 살펴보도록 한다. 

디코딩 프로시저

(define (decode bits tree)

(define (decode-1 bits current-branch)

(if (null? bits)

   '()

   (let ((next-branch

   (choose-branch (car bits) current-branch)))

   (if (leaf? next-branch)

 (cons (symbol-leaf next-branch)

     (decode-1 (cdr bits) tree))

 (decode-1 (cdr bits) next-branch)))))

(decode-1 bits tree))

(define (choose-branch bit branch)

(cond ((= bit 0) (left-branch branch))

  ((= bit 1) (right-branch branch))

           (else (error "bad bit -- CHOOSE-BRANCH" bit))))

- leaf 까지 내려왔으면 그때의 심볼을 다음 디코딩대상 비트들의 결과에 붙인다.

각 요소에 가중치가 있는 set

방금의 트리표현에서, leaf 가 아닌 트리 노드의 경우 리스트로 표현한 심볼의 set 을 구성했었다. (symbol-l symbol-r)

하지만 요전에 알고리즘을 설명했을때 두 가장 작은 아이템을 merge 함으로써 얻어진 leaf 들과 tree 의 집합에 대해 동작할 필요가 있었다.

반복해서 set 에서 가장 작은 아이템들을 찾을 필요가 있었으므로, 순서가 있는 표현 방식을 사용하는것이 좋겠다.

가중치의 순서에 따라 정렬한 리프와 노드의 리스트의 집합을 구성할것이다. 

아래의 adjoin-set 프로시져는 예제 2.61 에 묘사된 것과 비슷하나, weight 를 통해서 비교가 되고 이미 존재하는 요소는 추가되지 않는 다는 점이 다르다.

(define (adjoin-set x set)

(cond ((null? set) (list x))

  ((< (weight x) (weight (car set))) (cons x set))

 (else (cons (car set)

  (adjoin-set x (cdr set))))))

아래의 프로시져는 심볼-빈도 페어리스트를 받아 최초의 leaf 들에 대한 ordered set 을 구성한다. 

(define (make-leaf-set pairs)

(if (null? pairs)

   '()

   (let ((pair (car pairs)))

       (adjoin-set (make-leaf (car pair) ; symbol

      (cadr pair)) ; frequency

  (make-leaf-set (cdr pairs))))))

앞선 절에서 - 데이터의 집합으로 - ( 포스트에는 현재 누락 ) 유리수를 정의해봤다. 

(간략히 소개하자면 유리수 데이터를 정의하고, 활용, 유리수 데이터로부터 분자와 분모를 확인하여 산술연산을 하는 프로시저의 집합이었다 )

 하지만 데이터란 진짜 무엇일까 ?

단순 프로시저들의 어떤 조합이 데이터라고 할 수 있을까 ?

물론 아니다. -

이 책에서는 데이터는 그 데이터의 '조건'이 검증되어야 - 데이터라고 할 수 있다 라고 이야기한다.

유리수를 예로 들자면, 지켜야하는 조건은

이 된다. 

여기서 재밌는 생각을 하나 해본다.

데이터가 필요로하는 조건을 만족하면 데이터가 될 수 있다면, 

흔히 생각하는 structure 와 같은 구조를 이용하지 않고 데이터를 구성할 수 있는가 ?

cons / car / cdr 프로시저를 생각해보자. 

이 프로시저는 각각 pair 를 생성 / 첫번째 값을 가져오기 / 두번째 값을 가져오기를 수행한다.

예를 들어, (car (cons 1 2)) 의 값은 1, (cdr (cons 1 2)) 의 값은 2가 되는 식이다.

다음과 같이 구현해 볼 수도 있다.

cons x y 는 dispatch 라는 function 을 리턴하는데, 이 function 은 1개의 인자를 받아 이 인자가 0이면 x 를 반환하고, 1이면 y 를 반환한다. ( 그리고 둘 다 아닌 값이면 에러 출력 )

car 와 cdr 은 z 함수를 받아 인자를 각각 0과 1로 전달한다.

car 의 인자로 cons 2 3 을 전달한다면, (car (cons 2 3)) 

(car (dispatch 0)) 이 호출되는 셈이 되고, 결국 2 가 리턴된다.

Exercise 2.4 

Here is an alternative procedural representation of pairs. For this representation, verify that

(car (cons x y)) yields x for any objects x and y.

(define (cons x y)

(lambda (m) (m x y)))

(define (car z)

(z (lambda (p q) p)))

What is the corresponding definition of cdr? (Hint: To verify that this works, make use of the substitution

model of section 1.1.5.)

Exercise 2.5. Show that we can represent pairs of nonnegative integers using only numbers and arithmetic

operations if we represent the pair a and b as the integer that is the product 2a 3b. Give the corresponding

definitions of the procedures cons, car, and cdr.

Exercise 2.6. In case representing pairs as procedures wasn't mind-boggling enough, consider that, in a

language that can manipulate procedures, we can get by without numbers (at least insofar as nonnegative

integers are concerned) by implementing 0 and the operation of adding 1 as

(define zero (lambda (f) (lambda (x) x)))

(define (add-1 n)

(lambda (f) (lambda (x) (f ((n f) x)))))

This representation is known as Church numerals, after its inventor, Alonzo Church, the logician who

invented the calculus.

Define one and two directly (not in terms of zero and add-1). (Hint: Use substitution to evaluate

(add-1 zero)). Give a direct definition of the addition procedure + (not in terms of repeated

application of add-1).