2.1.3 데이터란 무엇인가 ?

본문의 예제코드들과 다르게, exercise 코드들은 모두 functional programming language 인 haskell 로 구현되어 있습니다.

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

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

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

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

물론 아니다. -

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

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

* 데이터 - 유리수의 조건

유리수 X 가 n 과 d 를 통해 얻어졌다면, x 의 분자 ( numor ) 를 x 의 분모 ( denom ) 으로 나눈 값은 

n을 d 로 나눈 값과 동일해야한다. 

이 된다. 

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

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

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

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

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

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

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

* structure 없는 데이터의 필요조건만으로 구성한 cons 데이터 (pair)

(define (cons x y)

(define (dispatch m)

(cond 

((= m 0) x)

((= m 1) y)

(else (error "Argument not 0 or 1 -- CONS" m))))

dispatch)

(define (car z) (z 0))

(define (cdr z) (z 1))

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.)

위와 같이 정의했을때 cdr 은 뭘까 ? 가 문제.

사실 위 람다를 제대로 이해하지 못해도, 통빡으로 답은 맞출수 있다. ( car 이 p 를 리턴하는 함수였으니, cdr 은 q 겠지... ) 

https://github.com/nolleh/SICP/blob/master/src/2.4.prove_cons_car.hs

--exercise 2.4
	-- 인자로 받은 함수를 x 와 y 를 인자로하여 실행하는 함수 리턴
	--cons :: Int -> Int -> (Int -> Int -> Int) -> Int
	cons x y = (\m-> m x y)
	-- z 에 p 와 q 를 받아 p 를 리턴하는 함수를 인자로 하여 z 함수 실행
	--car :: ((Int -> Int -> Int) -> Int) -> Int
	car z = z (\p q-> p)
	cdr z = z (\p q-> q)
	main = do
	print $ car (cons 2 3)
	print $ cdr (cons 2 3)

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.

2^a*3^b 로 쌍을 나타낸다면, 각각 어떻게 정의할 수 있을까? 가 문제.

아래 해결은 사실 car 의 값을 a 가 아니라 2^a 를 리턴하는 형태로 구성되어있는데, 

a 를 리턴하고자 한다면 log 를 취하면 간단 해결. 

https://github.com/nolleh/SICP/blob/master/src/2.5.number_cons.hs

-- exercise 2.5
	-- a 와 b 의 쌍을 2^a*3^b 로 표현한다면, cons / car / cdr ?
	cons x y = 2^x*3^y
	car z
	| rem z 3 /= 0 = z
	| otherwise = car (div z 3)
	cdr z
	| rem z 2 /= 0 = z
	| otherwise = cdr (div z 2)
	main = do
	print $ car (cons 4 5)
	print $ cdr (cons 4 5)

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).

숫자를 쓰지않고. 프로시저만으로 수를 구성하겠다고 한다.. ( 이런생각을 하다니... )

잘 뜯어보면, 

0 은 어떤 연산(f)과 이 연산의 인자, 피연산자 x 가 있을때 연산을 한번도 적용하지 않고 x 를 그대로 리턴하는 형태로 구성되어 있고,

add-1 n 은 어떤 연산(f)과 이 연산의 인자, 피연산자 x가 있을때 x 에 f 를 n 번 ((n f) x) 적용하고 여기에 f 를 한번 더 적용한 형태로 구성되어 있다.

이때 one 과 two, 그리고 + 를 구성해보라는 문제. 

one 과 two 는 f 를 각각 한번, 두번 더 감싸면 되며, 

add n m 은 합성 함수로 n 번 적용한 함수에 m 번 적용한 function 에 피연산자 x 를 전달하는 형태로 구성한다.

바로는 잘 이해가 안가겠지만, 주석을 잘 달아 놓았으니 찬찬히 생각해보면 이해가 갈 것이다.

 

https://github.com/nolleh/SICP/blob/master/src/2.6.one_two_procedure.hs

 

--exercise 2.6
	zero = (\f -> (\x->x))
	add_1 n = (\f -> (\x-> f ((n f) x)))
	one = (\f -> (\x-> f x))
	two = (\f -> (\x-> f(f x)))
	add n m = (\f -> (\x-> ((m f).(n f)) x ))
	main = do
	-- + 1 function 을 0 이라는 x 에 0번
	print $ zero (+ 1) 0 -- 0
	-- + 2 function 을 3 이라는 x 에 2번
	print $ two (+ 2) 3 -- 7
	-- + 1 function 을 0 이라는 x 에 1 번 한 후 + 1 을 한번 더
	print $ add_1 one (+ 1) 0 -- 2
	-- + 1 function 을 0 이라는 x 에 1 번 적용하고 다시 2 번 적용한다.
	print $ add one two (+ 1) 0 -- 3