본문 바로가기
documents

SCIP

snskshn 2008. 7. 31. 13:39

200710100001.gif

Harold Abelson, Gerald Jay Sussman, Julie Sussman| 김재우, 김수정, 김정민, 안윤호 역| Insight (인사이트)| 2007.10.25 | 888p | ISBN : 9788991268326

옳긴이의 글(김재우 : http://kizoo.blogspot.com/2007/03/sicp.html)

두 번째 판 머리말 : IEEE Scheme이라는 것이 있음. http://mitpress.mit.edu/sicp(sicp 홈페이지)

1. 프로시저를 써서 요약하는 방법

머릿속의 단순한 아이디어를 쓸모있는 아이디어로 만들어 내는 방법(인간 오성론(an essay concerning human understanding), 1690)

  1. 여러 단순한 아이디어를 한 아이디어로 묶어냄
  2. 단순한 아이디어와 복잡한 아이디어를 펼쳐놓음
  3. 실제 속의 복잡하게 얽힌 것에서 다른 아이디어를 분리(abstraction)

 

Lisp는 수학에서 쓰는 논리식 가운데 재귀 방정식을 컴퓨터 계산 모형으로 사용할 수 있는지 엄밀히 살펴보기 위해 1950년대에 존 매카시(John McCarthy)가 만든 언어다. 그가 쑨 논문 「Recursive Functions of Symbolic Expressions and Their computation by machine, McCarthy 1960」에 그 설계 원리가 밝혀져 있다.

 

메카시가 정리한 「Lisp - Notes On its Past and Future」(1980)

가이 L. 스틸 주니어(Guy L. Steel Jr.)와 리차드 P. 가브리엘(Richard P. Gabriel)이 정리한 『The Evolution of Lisp』

 

Common Lisp(Steele 1982, Steele 1990)는 그때까지 여러 사투리에 있던 기능을 한데 묶어서 산업 표준 Lisp를 제정하려고 Lisp 공동체가 만든 것인데, 1994년에 ANSI 표준(ANSI 1994)이 정해졌다.

Lisp(Scheme)를 바탕으로 하는 셸 언어로 scsch가 있다. 또 소프트웨어의 기능을 늘리는 언어로는 Emacs 편집기의 Elisp, AutoCAD 시스템의 AutoLisp를 들 수 있다.

 

1.1 프로그램 짤 때 바탕이 되는 것

프로시저 정의는 두 연산이 한데 어울려 만들어 내는 결과라는 점을 알아두자. 말하자면, 프로시저를 새로 만드는 연산이 그 하나요, 이어서 새 프로시저에 square라는 이름을 붙이는 연산이 다른 하나다. 다시 말해서, '이름 없는 프로시저를 만든다'라는 개념과 '만들어 놓은 프로시저에 이름을 붙인다'는 개념을 반드시 구분할 줄 알아야 한다.

프로시저 몸은(엮은식 말고도) 여러 식을 한 줄로 이어 쓴 식(squance of expression)일 수도 있다. 이런 식이 오면 실행기는 하나씩 차례대로 식을 계산하는데, 이때 맨 마지막 식의 값이 프로시저의 값이 된다.

 

  • 맞바꿈 계산법(substitution model) : 연산자와 피연산자를 먼저 계산 하고서, 연산자 프로시저를 연산할 인자에 맣춘다.

    1. (f 5)
    2. (sum-of-squares (+ a 1) (* a 2)
    3. (sum-of-squares (+ 5 1) (* 5 2)
    4. (+ (square 6) (square 10))
    5. (+ (* 6 6) (* 10 10)
    6. (+ 36 100)
    7. 136

 

맞바꿈 계산법이 겉으로는 아주 쉬워 보이나, 수학에서 그 과정을 정의하기가 엄청나게 복잡하다는 것은 오래전에 밝혀진 사실이다. 특히 어려운 문제는, 인자 값을 나타내는 식(the expression to which the procedure may be applied)에서 프로시저 몸 속에 있는 인자 이름과 같은 이름을 쓰는 경우, 이 두 이름을 다른 이름으로 보고 처리하는 것이 여긴 헛갈리는 일이 아니라는 것이다. 실제로 이런 문제 때문에 논리와 프로그래밍 언어의 뜻을 다루는 글에서 맞바꾸는 과정(substitution)을 틀리게 밝혀 놓은 겻우가 적지 않다. 맞바꿈 계산법을 더 깊이 알고 싶으면 Stoy 1977을 보라.

 

  • 인자 먼저 계산법(applicative order) : '인자 값부터 먼저 구하는' 방법. Lisp 실행기가 사용하는 방법

  • 정의대로 계산법(normal order) : '끝까지 펼친 다음에 줄이는' 계산 방법. 값이 필요할 때까지 피연산자를들 계산하지 않고 미루어 두는 방법.

    1. (f 5)
    2. (sum-of-squares (+ 5 1) (* 5 2))
    3. (+ (square (+ 5 1)) (square (* 5 2)))
    4. (+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2)))
    5. (+ (* 6 6) (* 10 10))
    6. (+ 36 100)
    7. 136
  • Lisp는 앞서 보기로 든 것과 달리 인자 먼저 계산하는 규칙을 따른다. 그 까닭은 첫째로 (+ 5 1)과 (* 5 2)처럼 같은 식을 여러 번 되푼이 계산하는 경우가 생기지 않아서 좀 더 빠르고 가볍게 계산할 수 있기 때문이고, 둘째로 맞바꿈 계산법이 통하지 안는 프로시저가 있을 때에는, 정의대로 계산하는 규칙이 더 복잡하기 때문이다.

 

'참이나 거짓이 된다'는 뜻은 이렇다. Scheme에는 참, 거짓 값을 나타내는 이름 #t와 #f가 따로 있다. 한데, 실행기가 술어의 답을 따질 때에는 #f가 나오면 거짓이라 답한 것으로 보고, 그 밖에 다른 값이 나오면 모두 참이라고 본다.( 다시 말해, 논리만 따진다면 #t라는 상수가 없어도 되지만, 있으면 편하기에 따로 만들어 놓은 것이다.) 이 책에서는 #t와 #f대신에 같은 값을 나타내는 true와 false라는 이름을 쓰기로 한다.

 

  1. (cond (<p1> <e1>)
  2. (<p2> <e2>)
  3. ...
  4. (<pn> <en>)
  5. (else <e>))

else라는 이름이 따로 없어도, 마지막 절 <p> 자리에 언제나 true라고 대답하는 식을 쓰기만 하면 else를 쓴 것이나 마찬가지다.

 

  1. (if <predicate> <consequent> <alternative>)

if와 cond 사이에는 다른 점이 또 하나 있다. cond 식에서 각 절의 <e>자리에는 잇단식(sequance of expression)이 올 수도 있다. 곧 <p>가 참일 때 <e>가 잇단식이면, 그 낱 식을 차례로 계산한 다음 마지막 식의 값을 cond값으로 돌려준다. 하지만 if 식에서는 <consequent>와 <alternative> 자리에 식 하나만 쓸 수 있다.

 

  1. (and <e1> ... <en>)

식 <e>를 왼쪽에서 오른쪽으로 계산한다. 그 가운데 거짓이라 대답하는 <e>가 나오면 and 식의 값은 거짓이 되고, 나머지 <e>의 값은 구하지 않는다. 모든 <e>가 참일 때에는 마지막 식의 값을 and식의 값으로 내놓는다.

 

  1. (or <e1> ... <en>)

식 <e>를 왼쪽에서 오른쪽으로 계산한다. 그 가운데 참이라 답하는 <e>가 나오면 or식의 값은 참이 되고, 나머지 <e>의 값은 구하지 않는다. 모든 <e>가 거짓일 때에는 마지막 식의 값을 or식의 값으로 돌려준다.

 

  1. (not <e1>)

<e>가 참이면 not식의 값으로 거짓을, 거짓이면 참을 내놓는다.

 

연습문제 1.3

세 숫자를 인자로 받아 그 가운데 큰 숫자 두 개를 제곱한 다음, 그 두 값을 덧셈하여 내놓는 프로시저를 정의하라.

해결중..

 

연습문제 1.5

인저 먼저 계산하는 실행기와 정의한 대로 계산하는 실행기에 따른 결과의 차이를 밝혀 보라.(if 식을 계산하는 규칙은 인자 먼저 하든지 정의대로 하든지 똑같다고 치자. 다시 말해서, 술어의 답, 곧 참이냐 거짓이냐에 따라 두 식 가운데 하나만 골라서 값을 구한다.)

  1. (define (p) (p))
  2. (define (test x y)
  3. (if (= x 0)
  4. 0
  5. y))
  6. (test 0 (p))

해결중..

 

함수와 프로시저의 차이는, 무엇이 어떤 성질을 지니는지 밝히는 일과, 그 무엇을 어떻게 만들지 또는 구할지 나타내는 일의 차이점과 같다. 이를 흔히 문제가 무엇인지에 관한 지식(declarative knowledge)과 문제 푸는 방법에 대한(명령하는) 지식(imperative knowledge)의 다른 점이라고 한다.

 

  • 뉴튼 법(Newton method) : x의 제곱근에 가까운 값 y가 있을 때 y와 x / y의 평균을 구하여 진짜 제곱근에 더 가까운 값을 구하는 방법이다.
    사실 이 제곱근 알고리즘은 뉴튼 법을 이 문에제 맞도록 줄인 것이고, 뉴튼 방법의 진짜 쓰임새는 방정식의 근을 챃는 것이다.
  1. (define (sqrt-iter guess x)
  2. (if (good-enough? guess x)
  3. guess
  4. (sqrt-iter (improve guess x)
  5. x)))
  6. (define (improve guess x)
  7. (average guess (/ x guess)))
  8. (define (average x y)
  9. (/ (+ x y) 2))
  10. (define (good-enough? guess x)   ;;미리 정한 폭(predetermined tolerance) = 0.001
  11. (< abs (- (square guess) x)) 0.001))
  12. (define (sqrt x)   ;; 제곱근에 가까운 값으로 언제나 1을 씀
  13. (sqrt-iter 1.0 x))

여기서 처음에 잡은 가까운 값(initial guess)이 1이 아니라 1.0임을 눈여겨보자. 대개 Lisp 시스템에서 1과 1.0은 별 차이가 없다. 그런데 MIT판 Scheme에서는 정수와 실수를 따로 보기 때문에, 정수를 나누면 실수가 아니라 유리수가 나온다. 이를테면, 10을 6으로 나눈 값은 5/3이지만, 10.0을 6.0으로 나눈 값은 1.6666666666666667이 된다. (유리수 연산을 만드는 방법은 2.1.1절에서 배운다.) 그러므로 제곱근 프로그램에서 첫 어림값을 1로 잡는다는 말은 x가 딱 떨어지는 정수라는 말이고, 이어서 제곱근 계산을 하면 실수가 안 나오고 유리수가 나온다. 하지만, 유리수와 실수를 섞어 쓰면 언제나 실수가 나오기 때문에, 첫 값으로 1.0을 잡ㅇ면 뒤이어 오는 모든 계산 결과에서 실수가 나온다.

 

연습문제 1.6

위 제곱근 프로시저에서 새로 정의한 new-if가 작동하지 않는 이유를 설명하시오.

  1. (define (new-if predicate then-clause else-cluase)
  2. (cond (predicate then-clause)
  3. (else else-clause)))

해결중..

 

연습문제 1.7

아주 작은 수나 큰 수의 제곱근까지 구할 수 있도록 good-enough?를 수정하라.

해결중..

 

연습문제 1.8

세제곱근을 구하는 뉴튼 법은, x의 세제곱근에 가까운 값을 y라고 할 때, 다음 식에 따라 y보다 더 가까운 값을 계산하는 것이다.

  1. (/ (+ x
  2. (square y)
  3. (* 2 y))
  4. 3)

제곱근 프로시저처럼, 이 식을 써서 세제곱근 프로시저를 짜보자.

해결중..

 

  • 매인 변수(bound variable) : 프로시저에 인자 이름이 매인다
  • 자유 변수(free variable) : 프로시저 정의에 매이지 않은 변수
  1. (define sqrt x)
  2. (define (good-enough? guess x)
  3. (< (abs (- (square guess) x)) 0.001))
  4. (define (improve guess x)
  5. (average guess (/ x guess)))
  6. (define (sqrt-iter guess x)
  7. (if (good-enough? guess x)
  8. guess
  9. (sqrt-iter (improve guess x) x)))
  10. (sqrt-iter 1.0 x))

sqrt프로시저 수정본 1

  1. (define (sqrt x)
  2. (define (good-enough? guess)
  3. (< abs (- (square guess) x)) 0.001))
  4. (define (improve guess)
  5. (average guess (/ x guess)))
  6. (define (sqrt-iter guess)
  7. (if (good-enough? guess)
  8. guess
  9. (sqrt-iter (improve guess))))
  10. (sqrt-iter 1.0))

sqrt프로시저 수정본 2

프로시저 속에 여러 프로시저를 정의할 때에는 정의하는 차례가 틀리지 않도록 조심해야 한다. 실수로 정의하는 차례와 쓰는 차례가 뒤엉킬 때, 어떤 결과가 나올지는 오로지 프로그램 짜는 사람이 책임질 문제다.

 

2. 데이터를 요약해서 표현력을 끌어올리는 방법

2.1 데이터 요약(데이터 간추리기, 데이터 내용 감추기)

프로시저를 어떻게 짰는지 모르더라도 같은 일을 하기만 한다면, 서로 달리 만든 프로시저를 맞바꿔 뜰 수도 있다는 말이다. 다시 말해서, 요약된 프로시저(간추린 프로시저)를 쓰는 덕분에 (기본 연산으로)프로시저를 만드는 쪽과 쓰는 쪽을 둘로 나누어 생각할 수 있도록 둘 사이에 '요약의 경계'를 그을 수 있다. 묶음 데이터에서, 이에 대응하는 생각이 바로 데이터 요약(데이터의 내용 감추기, data abstraction)이다. 데이터 요약(데이터 간추리기)이란, 프로시저 요약과 마찬가지로, (기본 데이터로) 묶음 데이터를 만드는 쪽과 쓰는 쪽을 떼어낼 수 있도록 하는 방법이다.

 

데이터를 잘 요약하여(간추려) 그에 딱 맞는 낱말을 만들어 내기 위해서 Scheme에서는 쌍(pair)이라는 데이터 구조를 쓴다.

  1. (define x (cons 1 2))
  2. (car x)
1
  1. (cdr x)
2

 

  1. (define (add-rat x y)
  2. (make-rat (+ (* (numer x) (denom y))
  3. (* (numer y) (denom x)))
  4. (* (denom x) (denom y))))
  5. (define (sub-rat x y)
  6. (make-rat (- (* (numer x) (denom y))
  7. (* (numer y) (denom x)))
  8. (* (denom x) (denom y))))
  9. (define (mul-rat x y)
  10. (make-rat (* (numer x) (numer y))
  11. (* (denom x) (denom y))))
  12. (define (div-rat x y)
  13. (make-rat (* (numer x) (denom y))
  14. (* (denom x) (numer y))))
  15. (define (equal-rat? x y)
  16. (= (* (numer x) (denom y)
  17. (* (numer y) (denom x))))
  18. (define (make-rat n d) (cons n d))   ;; 짜맞추개(constructor)
  19. (define (numer x) (car x))   ;; 고르개(selector)
  20. (define (denom x) (cdr x))
  21. (define (print-rat x)

  22. (newline)

    (display 9numer x))

  23. (display "/")
  24. (display (denom x)))

유리수 구현하기

 

연습문제 2.1

양수뿐 아니라 음수까지 다룰 수 있는 make-rat을 정의하라. 새 make-rat은, 유리수가 양수라면 분자와 분모 모두 양수이고, 유리수고 음수라면 분자만 음수가 되도록 처리해야 한다.

아직..

 

요약의 경계를 잘 짜 놓아서 아래와 같이 각각의 부품들만 다시 코딩할 수 있다.

  1. (define (make-rat n d)
  2. (cons n d))
  3. (define (numer x)
  4. (let ((g (gcd (car x) (cdr x))))
  5. (/ (car x) g)))
  6. (define (denom x)
  7. (let ((g (gcd (car x) (cdr x))))
  8. (/ (cdr x) g)))
  9. (define (gdc a b)
  10. (if (= b 0)
  11. a
  12. (gcd b (remainder a b))))

기약분수가 되도록 수정한 유리수 구현하기

 

연습문제 2.2

모든 점은 시작 점과 끝 점의 쌍으로 나타낼 수 있다. 두 점을 짜맞춰 선분을 만들어 내는 make-segment와 선분에서 두 끝점을 골라내는 start-segment, end-segment를 정의하라. 또한, 점도 x좌표를 나태내는 수와 y좌표를 나타내는 수를 한 쌍으로 해서 나타낼 수 있다. 그에 따라 make-point와 x-point, y-point를 만들어서 이런 표현 방법을 정의하라. 그 다음에 아래와 같이 점의 좌표를 찍어내는 프로시저를 써서 결과가 제대로 나오는지 확인해 보라.

 

  1. (define (print-point p)
  2. (newline)
  3. (display "(")
  4. (display (x-point p))
  5. (display ",")
  6. (display (y-point p))
  7. (display ")"))

 

아직..

 

연습문제 2.3

네모꼴을 나타내는 데이터를 표현해 보자. 네모꼴의 둘레와 넓이를 구하는 프로시저를 정의하라. 네모꼴의 표현 방법을 바꿔도 둘레와 넓이 구하는 프로시저가 그대로 알맞은 요약의 경계를 갖춘 시스템을 설계하라.

 

정수 n과 d의 쌍으로 유리수 x를 만들었다면, x의 numer를 denom으로 나눈 값이 n을 d로 나눈 값과 같다는 조건을 만족해야 한다. 달리 말해서, 어떤 정수 n과 0이 아닌 정수 d를 가지고 (make-rat n d)를 계산한 결과가 x이면 make-rat, numer, denom은 아래 조건을 만족해야 한다.

  1. (= (/ (numer x) (denom x)) (/ n d))

유리수라는 데이터를 만드는 데 바탕이 되는 연산, 곧 make-rat, numer, denom이 만족해야할 조건은 이것뿐이다. 흔히 데이터란, 짜맞추개나 고르개, 이런 프로시저가 알맞은 데이터 표현을 만들어 내는지 따져볼 수 있는 조건까지 함께 정의해 놓은 것을 말한다.

 

  1. (define (cons x y)
  2. (define (dispatch m)
  3. (cond ((=m 0) x)
  4. ((=m 1) y)
  5. (else (error "Argument not 0 or 1 -- CONS" m))))
  6. dispatch)
  7. (define (car z) (z 0))
  8. (define (cdr z) (z 1))

어떤 데이터 구조고 쓰지 않고 cons, car, cdr를 프로시저로 정의하기

이렇게 데이터를 프로시저로 나타내면 이를 곧바로 데이터라고 생각하기 어렵다. 그럼에도, 이 프로시저 셋이 위에서 밝힌 데이터의 조건을 만족하는지 증명하기만 하면 아무런 문제가 없다.

 

연습문제 2.4

cdr을 정의하시오.

  1. (define (cons x y)
  2. (lambda (m) (m x y)))
  3. (define (car z)
  4. (z (lambda (p q) p)))

이렇게 정의한 쌍이 올바로 돌아간다는 것을 따져보기 위해서 맞바꿈 계산법을 써 보라

아직...

 

연습문제 2.5

오로지 수와 산술 연산믄으로 양의 정수 쌍도 표현해 보자. 정수 a, b의 쌍을 2a3b 로 나타낼 때, 이에 알맞을 cons, car, cdr프로시저를 정의해 보라.

아직....

 

연습문제 2.6

람다 계산법을 처음 만들어 낸 논리학자 앨런조 처치(Alonzo church)의 처치의 수(Church numeral)를 이용해 one과 two를 zero와 add-1을 쓰지 않고 곧바로 정의해 보라.(맞바꿈 계산법으로 (add-1 zero)를 풀어 보라.) 덧셈 프로시저 +를 (add-1을 여러번 되풀이하지 말고) 곧바로 정의하라.

  1. (define zero (lambda (f) (lambda (x) x)))
  2. (define (add-1 n)
  3. (lambda (f) (lambda (x) (f ((n f) x)))))

 

min과 max는 여러 인자 가운데 가장 작은 값과 가장 큰 값을 구하는 기본 프로시저다.

  1. (define (add-interval x y)
  2. (make-interval (+ (lower-bound x) (lower-bound y))
  3. (+ (upper-bound x) (upper-bound y))))
  4. (define (mul-interval x y)
  5. (let ((p1 (* (lower-bound x) (lower-bound y)))
  6. (p2 (* (lower-bound x) (upper-bound y)))
  7. (p3 (* (upper-bound x) (lower-bound y)))
  8. (p4 (* (upper-bound x) (upper-bound y))))
  9. (make-interval (min p1 p2 p3 p4)
  10. (max p1 p2 p3 p4))))
  11. (define (div-interval x y)
  12. (mul-interval x
  13. (make-interval (/ 1.0 (upper-bound y))
  14. (/1.0 (lower-bound y)))))
  15. (define (make-interval a b) (cons a b))   ;; 연습문제 2.7
  16. (define (upper-bound x) (cdr x))   ;; 연습문제 2.7
  17. (define (lower-bound x) (car x))   ;; 연습문제 2.7
  18. (define (sub-interval x y)   ;; 연습문제 2.8
  19. (make-interval (- (lower-bound x) (upper-bound y))
  20. (- (upper-bound x) (lower-bound y))))

 

아직미완성....

 

2.2 계층 구조 데이터와 닫힘 성질

 

 

 

 

이 글은 스프링노트에서 작성되었습니다.

'documents' Related Articles

티스토리툴바