검색결과 리스트
SICP에 해당되는 글 6건
- 2015.02.07 2.1.3 데이터란 무엇인가 ?
- 2014.10.31 1.2.3 프로세스가 자라나는 정도 (임시)
- 2014.06.13 Structure and Interprecation Of Computer Programs - Chapter 1.1
글
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.)
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).
'SICP > 2. Building Abstractions with Data' 카테고리의 다른 글
| 2.5.3 Example: Symbolic Algebra (0) | 2015.11.01 |
|---|---|
| 2.5 System with Generic Operations (0) | 2015.09.13 |
| 2.3.4 Huffman Encoding Trees (3) | 2015.08.05 |
설정
트랙백
댓글
글
1.2.3 프로세스가 자라나는 정도 (임시)
'SICP > 1. Building Abstractions with Procedures' 카테고리의 다른 글
| Structure and Interprecation Of Computer Programs - Chapter 1.1 (0) | 2014.06.13 |
|---|
설정
트랙백
댓글
글
Structure and Interprecation Of Computer Programs - Chapter 1.1
MIT 컴퓨터 공학 1학년 교재로 사용된다는 SICP. (Structure and Interprecation of Computer Programs)
번역본까지 출판되어 잘 팔리고 있는 책.
문제가 되지 않는 선에서 간략히 필자의 노트 필기 차원에서 여기에 정리함.
책에서는 Lisp 으로부터 파생된 (방언이라 표현하던데) scheme 으로 예제들이 정리가 되어있는데,
필자는 Scala 로 풀어보았음. - scala 소개는 본 블로그의 scala 문법 참고.
초반부 - Lisp 소개와, scheme 의 기본 문법소개, 그리고 전위 연산 표기 소개등.
정의대로 계산법 (normal-order evaluation), 인자 먼저 계산법 (applicative_order evaluation)
def sum_of_square(a: Int, b: Int) = {
a*a + b*b
}
sum_of_square(5+5, 2+3)
와 같이 작성했을때
정의대로 계산법은
1. (5+5)*(5+5) + (2+3)*(2+3)
2. 10*10 + 5*5
3. 100 + 25
4. 125
와 같이 좁혀지며 계산되며
인자 먼저 계산법은
1. 10*10 + 5*5
2. 100 + 25
3. 125
와 같이 계산된다.
예제 1.3
세 숫자중 2개의 큰 숫자를 제곱하여 합하라
예제 1.5
정의대로 계산법과 인자 먼저 계산법에서의 다음 연산의 차이
(define (p) (p))
(define (test x y)
(if (= x 0)
0 y))
Then he evaluates the expression
(test 0 (p))
1.1.7 - Square Roots by Newton's Method
어떤 수 x 의 제곱근을 구하는 방법으로, 뉴튼법이 있다.
일단 어떤 적당한 값으로 나눠보고 (x / guess) , 이 값을 제곱했을때 값과 x 의 차이가 오차범위 이내이면 이 값을 제곱근으로 리턴하고,
그렇지 않으면 나눈 결과 값과 추측값의 평균값을 구한다. ( (x / guess + guess) / 2 )
이 평균값을 다시 추측값으로 하여 전 과정을 오차범위 이내일때까지 반복한다.
-> 장황하지만 간단히 얘기해서, 어떤 값으로 나눠본 결과가 터무니 없으면 그 어떤값과의 평균값으로 보정하는 과정을 반복하는 것이다.
-> 정확한 값이라면 (x/guess + guess) / 2 는
와 같이 전개되어 결국 원하는 값이 된다.
스칼라로 표현하면
def newton = {
def sqrt(x: Int) = {
def iter_sqrt(guess: Float, x: Int): Float = {
def improve(guess: Float): Float = {
println("guess : " + (x / guess + guess)/2)
(x / guess + guess)/2
} // improve
def good_enough(guess: Float):Boolean = {
def pow(a: Float) = {
a*a
}
if (Math.abs(pow(guess) - x) < 0.001) true else false
}
if (good_enough(guess))
guess
else
iter_sqrt(improve(guess), x)
} //iter_sqrt
iter_sqrt(1, x)
}
sqrt(2)
} //> newton: => Float
newton //> guess : 1.5
//| guess : 1.4166667
//| guess : 1.4142157
//| res3: Float = 1.4142157
와 같이 된다.
예제 1.6 new-if 로 scheme 의 if cond 를 다음과 같이 직접 작성했다.
(define (new-if predicate then-clause else-clause)
(cond (predicate then-clause)
(else else-clause)))
만약 이 new-if 를 newton's method 에 적용한다면 ?
예제 1.7 뉴튼법은 큰 숫자나 작은 숫자엔 적용하기 어렵다. 그 예를 들어 과정을 설명하고, 개선해보라.
예제 1.8 세제곱근을 구하는 공식은 (x/y^2 + 2y)/3 과 같다. 작성해보아라.
'SICP > 1. Building Abstractions with Procedures' 카테고리의 다른 글
| 1.2.3 프로세스가 자라나는 정도 (임시) (0) | 2014.10.31 |
|---|
