Structure and Interpretation of Computer Programs 라는 졸라 긴 제목을 가지고 있는 책의 번역서가
컴퓨터 프로그램의 구조와 해석 이라는 역시 졸라 긴 제목으로 작년에 출판됐다.
사실, 이 책을 아직 끝까지 다읽지는 않았다. lazy evaluation하는 evaluator 까지 밖에 못봤으니 한 3분의 2봤나?
바쁘다는 핑계를 대지만은 워낙 게을러 놔서 언제 진도가 나갈지는 잘 모르겠다;;
또 책읽는 습관이 처음에 대충 끝까지 보구 다음에 2 ~ 3번 더 보는 스타일이라 그나마도 꼼꼼히 보진 않은것 같다. 그것도 중간에 모르겠으면 걍 뛰엄뛰엄 읽구 연습문제도 별로 안풀고 대충 보는거라서 본 느낌을 말한다는게 아직 섣부를수도있지만..
그냥, 좋은걸 보면 권하고 싶구, 나누고 싶은게 인지상정아닌가싶다.
좋은책이다. 그리고, 실습언어로 scheme을 선택한것도 탁월한 선택이라구본다.
일단, 이 책은 보통 말하는 CS 개론서랑 다루는 부분에서는 맥락을 같이한다. 난이도는 조금(?) 다를지라도..
소위 말하는 Fundamentals of the computer science 를 가르친다.
프로그래밍이란? 부터 시작해서 기본적인 abstraction을 가르치며 PL, SE, 논리회로, 자료구조, 알고리즘, OS, 컴파일러등 computer science의 주요과목들에 나오는 몇몇 중요한 내용들을 주제로, 때로는 예제로 때로는 연습문제로 광범위하게 커버를 하고있다.
다른 컴퓨터 과학 개론서랑 차별되는 점이라면 나오는 이슈들을 조금(?) 더 진지하게 다룬다.
가장 큰 차이점은 그냥 뜬구름잡는 이론들만 쭉 설명만 하지않구, 직접 뚝딱거리며 "만들어 볼수 있게" 해주는 점이다. 비록 장난감 수준일지라도 직접 뚝딱거리며 만들어 보는것만큼 명확하게 이해할수 있는 방법이 또 있겠는가;;
만약, 표현력이 떨어지거나 언어 이외의 요소를 잘 알아야 잘 다룰수 있는 언어를 실습언어로 선택했다면 힘들었을것이다. 예를 들어, 1학년때 많이들 가르치는 C는 문법은 간결하지만 How computer works를 알아야 제대로 다룰수있다. 모를땐 엄청 삽질을 해야한다. 물론, 특정 머신이 아닌 추상적인 컴퓨팅 머신의 개념이기는 하지만.. (오해는 하지 마시라 "이런 용도의 도구" 로서는 잘 안어울린다는 뜻이다. 난 커니핸, 리치 형님의 빠돌이이다. 커니핸, 파이크, 리치, 톰슨 이 4인방은 나에게는 아이돌스타다;;)
C는 하나의 예이구, 어쨌든 스킴을 사용을해서 실습도구의 tricky한 부분때문에 지쳐가지구 중요한 "내용" 을 못따라오는 것을 막았다.
난이도가 조금은 도전적이기는해도, 무엇보다 아까도 말했듯이 뭔가를 뚜드리며 만들어내는 걸 좋아하는 아이들에게 이 책은 매우 좋은 CS 개론서가 될것이다.
그리구, 좋은 코드란 어떤 것인가에 대한 방향을 잡아주기도 하구, 전산학의 영원한 과제인 abstraction에 대한 고민을해보게 하는 것또한 참 좋은 경험이되줄것이다.
또, 보통의 개론서와 다르게 학부때에 배웠던 내용이 가물가물 해져가서 쭉 훑어보고 싶은 나같은 사람에게도 좋은책이다.
80년대에 휴렛 팩커드의 시니어 엔지니어 정도 들어보이는 아저씨들이 진지하게 강의를 들으며 질문도 하고 그랬던 교재이다.
물론, 모든 사람에게 다 맞는 책은 있을수없는건 분명하다.
k&r 이나 thinking in java가 취향에 맞지 않아하는 친구들도 주위에 있었으며, 나는 많은 사람들이 좋아라들하는 스티브 맥코넬의 책을 별로 안좋아하는편이다.
어쨌든, 처음엔 좀 낯설수 있지만 내 경험으로는 참고 보다보면은 재미있는 책이다.
'sicp'에 해당되는 글 5건
- 2008/01/30 SICP를 보며....
- 2008/01/30 스킴 걸음마의 말 - sicp 연습문제 1장 (설명하는 문제들중 9문제)
- 2008/01/29 스킴 걸음마의 코드 - sicp 연습문제 1장 (코드짜는 문제중 14문제)
이번에는 코드안짜구 말로 설명하는 문제들만 따로풀어보려구한다.
ch1 에서 딴거보다 쉬워보이는
exer 1.1, 1.2,, 1.4, 1.5, 1.6, 1.9, 1.10, 1.21, 1.34 만 풀어보았다.
역시 말로 설명하는건 코드짜는거보다 괜히 조금 귀찮다-_-
따로 문제는적지않는다.
무엇보다 일단 귀찮으며--;;, 문제는 책보면은 있는 내용이라서 쓸 이유를 못 느끼겠다.
경우에 따라서는 풀이에 꼭 필요한 경우에만 적겠다.
exercise 1.1
가. 10 => 10; 나. (+ 5 3 4) => 12; 다. (- 9 1) => 8; 라. (/ 6 2) => 3
마. (+ (* 2 4) (- 4 6)) 괄호안을 계산하면 (+ 8 -2) => 6
바. (+ a b (* a b)) 괄호안의 a를 3으로 대치, b를 4로 대치하면 (+ 3 4 (* 3 4)) = (+ 7 12) => 19
사. (= a b) 는 (= 3 4) => #f
아.
괄호안의 a, b를 3, 4로 대치시키구나면
(if (and (> 4 3) (< 4 (* 4 3))) 4 3) 두 조건다 참이므로 => 4
자. (= b 4)가 참이니까 (+ 6 7 3) 하면 => 16
차. (+ 2 (if (> b a) b a)) => (> b a)가 참이므로 (+ 2 b) => 6
카.
cond부터 풀면은 (< a b)가 참이니 cond를 eval하구 난 값은 4가된다.
거기에 * (+ a 1)을 하면 (* 4 (+ 3 1)) = (* 4 4) => 16
exercise 1.2
(/ (+ 5 (+ 4 (- 2 (- 3 (+ 6 (/ 4 5)))))) (* 3 (- 6 2) (- 2 7)))
exercise 1.4
(a-plus-abs-b 3 -4)로 호출했다구 치면 ((if (> -4 0) + -) 3 -4))이다. if가 거짓이다.
그래서 (- 3 -4) 가 되서 중위표기식으로 하면은 (3 - (-4)) = 3 + 4 => 7
exercise 1.5
인자 먼저 계산하는 식으로 하면 무한루프에 빠진다 왜냐하면 y자리에 (p)가 가는데 계속 자신을 호출하니까
만약 정의한대로 계산하면 if(= 0 0)이 참이 되어서 0을 리턴을 할것임 y값을 eval하지도 않으니까
무한루프에빠질일도없음
exercise 1.6
무한 루프에 빠지는데, new-if에 매개변수로 전달된 then-clause랑 else-clause가 둘다 전달되면서 evaluate되기 때문이다.
exercise 1.9
위의것 되도는프로시져, 아래것은 반복프로시져다
왜냐하면 위의건 곧바로 계산을 하지 않구 계속 미루어 놓다가 재귀호출이 끝나면 리턴값들을
계산을 하구, 밑의것은 그때그때에 계산을 한다
exercise 1.10
(A 1 10) => 1024
(A 2 4) => 65536
(A 3 3) => 65536
n > 0 임
(f n) : 2n
(g n) : 2 ^ n
(h n) : 2 ^ h (n - 1)
h는 n에 좀만 큰 수를 넣으면은 답이 졸라 커진다.
exercise 1.21
199 => 199, 1999 => 1999, 19999 => 7
exercise 1.34
procedure application: expected procedure, given: 2; arguments were: 2
라는 에러메세지 나옴.
f는 인자로 받아온 프로시져에 2를 인자로 하여 호출하는 프로시져다.
(f f) 하면은 일단 인자로 받은 f에 2를 인자로 하여 호출하려고 한다.
그럼 (f 2)를 하려하는데 (f 2)하면 인자로 받은 2에 2를 인자로 하여 호출하는
(2 2)라는 이상한짓을 하게 된다. 2는 프로시져가 아니므로 에러가되는것임
; sicp의 ch1 중 설명하는 문제는 빼놓구 코드를 짜는 문제중에서
; exercise 1.3, 1.8, 1.11, 1.12, 1.17, 1.18, 1.23, 1.30, 1.32, 1.33,
; 1.35, 1.41, 1.42, 1.43만 품
; 쉬워보이는것만 골라서 함--;;
; 12월에 포스팅했던것을 문제 몇문제 좀 더 풀구
; 정리좀해서 다시포스팅한것
; 이제 문제더 풀면 이 글에 그냥 수정해 계속해 붙여갈계획
; (plt scheme 의 개발환경 DrScheme에서 language를 standard(R5RS)로 맞춘후 테스트)
; exercise 1.3, 1.8, 1.11, 1.12, 1.17, 1.18, 1.23, 1.30, 1.32, 1.33,
; 1.35, 1.41, 1.42, 1.43만 품
; 쉬워보이는것만 골라서 함--;;
; 12월에 포스팅했던것을 문제 몇문제 좀 더 풀구
; 정리좀해서 다시포스팅한것
; 이제 문제더 풀면 이 글에 그냥 수정해 계속해 붙여갈계획
; (plt scheme 의 개발환경 DrScheme에서 language를 standard(R5RS)로 맞춘후 테스트)
; exercise 1.3
(define (square n) (* n n))
(define (sum-of-larger-square i j k)
(let ((m (min i j k)))
(cond ((= m i) (+ (square j) (square k)))
((= m j) (+ (square i) (square k)))
(else (+ (square i) (square j))))))
(display "\nexer 1.3\n")
(sum-of-larger-square 10 30 40)
(sum-of-larger-square 10 40 30)
(sum-of-larger-square 30 10 40)
(sum-of-larger-square 30 40 10)
(sum-of-larger-square 40 10 30)
(sum-of-larger-square 40 30 10)
; exercise 1.8
(define (square n) (* n n))
(define (cube n) (* n n n))
(define (cbrt-iter guess x)
(if (good-enough? guess x) guess
(cbrt-iter (improve guess x) x)))
(define (improve guess x)
(+ (/ x (* 3 (square guess))) (/ (* 2 guess) 3)))
(define (average x y)
(/ (+ x y) 2))
(define (good-enough? guess x)
(< (abs (- (cube guess) x)) 0.001))
(define (cbrt x)
(cbrt-iter 1.0 x))
(display "\nexer 1.8\n")
(cbrt 9)
(cbrt 10)
(cbrt 125)
; exercise 1.11
(define (f n)
(if (< n 3) n
(+ (- n 1) (* 2 (f (- n 2))) (* 3 (f (- n 3))))))
(define (f-iter n)
(define (iter i j k result)
(cond ((> i n) result)
((< i 3) (iter (+ i 1) (- i 1) (- i 2) i))
(else (iter (+ i 1) result j (+ (- i 1) (* 2 j) (* 3 k))))))
(iter 1 0 0 0))
(define (test proc)
(define (iter i)
(cond ((<= i 10) (display "f(") (display i)
(display ") = ") (display (proc i)) (newline)
(iter (+ i 1)))
(else (newline))))
(iter 0))
(display "\nexer 1.11\n")
(test f)
(test f-iter)
; exercise 1.12
(define (invalid? row col)
(or (< row 0) (< col 0) (< row col)))
(define (pascal row col)
(cond ((invalid? row col) 'wrong)
((or (= col 0) (= row col))1)
(else (+ (pascal (- row 1) (- col 1)) (pascal (- row 1) col)))))
(display "\nexer 1.12\n")
(pascal 9 7)
; exercise 1.17
; 짝수면은 그 값의 두배, 홀수면 그냥 더하는 식으로 곱셈을 만드는것
(define (double n) (+ n n))
(define (halve n) (/ n 2))
(define (fast-mul a b)
(cond ((or (= a 0) (= b 0)) 0)
((= b 1) a)
((= a 1) b)
((even? b) (double (fast-mul a (halve b))))
(else (+ a (fast-mul a (- b 1))))))
(display "\nexer 1.17\n")
(fast-mul 2 3)
(fast-mul 2 4)
(fast-mul 2 5)
(fast-mul 100 20)
; exercise 1.18
; even일때 a를 double하는게 중요
(define (fast-mul-iter a b)
(define (iter a b result)
(cond ((or (= a 0) (= b 0)) 0)
((= b 1) (+ result a))
((even? b) (iter (double a) (halve b) result))
(else (iter a (- b 1) (+ result a)))))
(iter a b 0))
(display "\nexer 1.18\n")
(fast-mul-iter 2 3)
(fast-mul-iter 2 4)
(fast-mul-iter 2 5)
(fast-mul-iter 100 20)
; exercise 1-23
(define (next n)
(if (= n 2) 3
(+ n 2)))
(define (find-divisor n test-div)
(cond ((> (* test-div test-div) n) n)
((= 0 (remainder n test-div)) test-div)
(else (find-divisor n (next test-div)))))
(define (smallest-divisor n)
(find-divisor n 2))
(define (prime? n)
(if(>= 1 n) #f
(= n (smallest-divisor n))))
(display "\nexer 1.23\n")
(prime? 17)
(prime? 561)
; exercise 1.30
(define (inc n) (+ n 1))
(define (cube n) (* n n n))
(define (sum-cubes a b)
(sum cube a inc b))
(define (sum term a next b)
(define (iter a result)
(if (> a b) result
(iter (next a) (+ result (term a)))))
(iter a 0))
(display "\nexer 1.30\n")
(sum-cubes 1 10)
; exercise 1.32
(define (accumulate combiner null-value term a next b)
(if (> a b) null-value
(combiner (term a) (accumulate combiner null-value term (next a) next b))))
(define (accumulate-iter combiner null-value term a next b)
(define (iter a result)
(if (> a b) result
(iter (next a) (combiner (term a) result))))
(iter a null-value))
(define (sum term a next b)
(accumulate + 0 term a next b))
(define (product term a next b)
(accumulate * 1 term a next b))
(define (sum-iter term a next b)
(accumulate-iter + 0 term a next b))
(define (product-iter term a next b)
(accumulate-iter * 1 term a next b))
(display "\nexer 1.32\n")
(define (sum-squares a b)
(sum square a inc b))
(define (sum-squares-iter a b)
(sum-iter square a inc b))
(define (product-squares a b)
(product square a inc b))
(define (product-squares-iter a b)
(product-iter square a inc b))
(sum-squares 1 5)
(sum-squares-iter 1 5)
(product-squares 1 5)
(product-squares-iter 1 5)
; exercise 1.33
(define (filtered-accumulate predicate combiner null-value term a next b)
(cond ((> a b) null-value)
((predicate a)
(combiner (term a) (filtered-accumulate predicate combiner
null-value term (next a) next b)))
(else (filtered-accumulate
predicate combiner null-value term (next a) next b))))
(define (sum-prime-squares a b)
(filtered-accumulate prime? + 0 square a inc b))
(define (mutual-prime? a b)
(= 1 (gcd a b)))
(define (identity. x) x)
(define (product-mutual-primes n)
(filtered-accumulate (lambda (x) (mutual-prime? x n)) * 1 identity. 1 inc (- n 1)))
(display "\nexercise 1.33\n")
(sum-prime-squares 1 20)
(product-mutual-primes 10)
; exercise 1.35
(define tolerance 0.00001)
(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (try guess)
(let ((next (f guess)))
(if (close-enough? guess next) next
(try next))))
(try first-guess))
(define (golden-ratio)
(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0))
(display "\nexercise 1.35\n")
(golden-ratio)
; exercise 1.41
(define (double proc)
(lambda (x) (proc (proc x))))
(display "\nexer 1.41\n")
;((double inc) 3)
(((double (double double)) inc) 5)
; exercise 1.42
; lambda로 만드는 프로시져는
; x를 인자로 받아서 (g x)를 호출 후 리턴값으로 f를 호출
(define (compose. f g)
(lambda (x) (f (g x))))
(display "\nexer 1.42\n")
((compose. square inc) 6)
; exercise 1.43
(define (identity. x) x)
(define (repeated f n)
(if (= n 0) identity.
(compose. f (repeated f (- n 1)))))
(display "\nexer 1.43\n")
((repeated square 2) 5)
((repeated square 1) 2)
((repeated square 2) 2)
((repeated square 3) 2)
((repeated square 4) 2)
(define (square n) (* n n))
(define (sum-of-larger-square i j k)
(let ((m (min i j k)))
(cond ((= m i) (+ (square j) (square k)))
((= m j) (+ (square i) (square k)))
(else (+ (square i) (square j))))))
(display "\nexer 1.3\n")
(sum-of-larger-square 10 30 40)
(sum-of-larger-square 10 40 30)
(sum-of-larger-square 30 10 40)
(sum-of-larger-square 30 40 10)
(sum-of-larger-square 40 10 30)
(sum-of-larger-square 40 30 10)
; exercise 1.8
(define (square n) (* n n))
(define (cube n) (* n n n))
(define (cbrt-iter guess x)
(if (good-enough? guess x) guess
(cbrt-iter (improve guess x) x)))
(define (improve guess x)
(+ (/ x (* 3 (square guess))) (/ (* 2 guess) 3)))
(define (average x y)
(/ (+ x y) 2))
(define (good-enough? guess x)
(< (abs (- (cube guess) x)) 0.001))
(define (cbrt x)
(cbrt-iter 1.0 x))
(display "\nexer 1.8\n")
(cbrt 9)
(cbrt 10)
(cbrt 125)
; exercise 1.11
(define (f n)
(if (< n 3) n
(+ (- n 1) (* 2 (f (- n 2))) (* 3 (f (- n 3))))))
(define (f-iter n)
(define (iter i j k result)
(cond ((> i n) result)
((< i 3) (iter (+ i 1) (- i 1) (- i 2) i))
(else (iter (+ i 1) result j (+ (- i 1) (* 2 j) (* 3 k))))))
(iter 1 0 0 0))
(define (test proc)
(define (iter i)
(cond ((<= i 10) (display "f(") (display i)
(display ") = ") (display (proc i)) (newline)
(iter (+ i 1)))
(else (newline))))
(iter 0))
(display "\nexer 1.11\n")
(test f)
(test f-iter)
; exercise 1.12
(define (invalid? row col)
(or (< row 0) (< col 0) (< row col)))
(define (pascal row col)
(cond ((invalid? row col) 'wrong)
((or (= col 0) (= row col))1)
(else (+ (pascal (- row 1) (- col 1)) (pascal (- row 1) col)))))
(display "\nexer 1.12\n")
(pascal 9 7)
; exercise 1.17
; 짝수면은 그 값의 두배, 홀수면 그냥 더하는 식으로 곱셈을 만드는것
(define (double n) (+ n n))
(define (halve n) (/ n 2))
(define (fast-mul a b)
(cond ((or (= a 0) (= b 0)) 0)
((= b 1) a)
((= a 1) b)
((even? b) (double (fast-mul a (halve b))))
(else (+ a (fast-mul a (- b 1))))))
(display "\nexer 1.17\n")
(fast-mul 2 3)
(fast-mul 2 4)
(fast-mul 2 5)
(fast-mul 100 20)
; exercise 1.18
; even일때 a를 double하는게 중요
(define (fast-mul-iter a b)
(define (iter a b result)
(cond ((or (= a 0) (= b 0)) 0)
((= b 1) (+ result a))
((even? b) (iter (double a) (halve b) result))
(else (iter a (- b 1) (+ result a)))))
(iter a b 0))
(display "\nexer 1.18\n")
(fast-mul-iter 2 3)
(fast-mul-iter 2 4)
(fast-mul-iter 2 5)
(fast-mul-iter 100 20)
; exercise 1-23
(define (next n)
(if (= n 2) 3
(+ n 2)))
(define (find-divisor n test-div)
(cond ((> (* test-div test-div) n) n)
((= 0 (remainder n test-div)) test-div)
(else (find-divisor n (next test-div)))))
(define (smallest-divisor n)
(find-divisor n 2))
(define (prime? n)
(if(>= 1 n) #f
(= n (smallest-divisor n))))
(display "\nexer 1.23\n")
(prime? 17)
(prime? 561)
; exercise 1.30
(define (inc n) (+ n 1))
(define (cube n) (* n n n))
(define (sum-cubes a b)
(sum cube a inc b))
(define (sum term a next b)
(define (iter a result)
(if (> a b) result
(iter (next a) (+ result (term a)))))
(iter a 0))
(display "\nexer 1.30\n")
(sum-cubes 1 10)
; exercise 1.32
(define (accumulate combiner null-value term a next b)
(if (> a b) null-value
(combiner (term a) (accumulate combiner null-value term (next a) next b))))
(define (accumulate-iter combiner null-value term a next b)
(define (iter a result)
(if (> a b) result
(iter (next a) (combiner (term a) result))))
(iter a null-value))
(define (sum term a next b)
(accumulate + 0 term a next b))
(define (product term a next b)
(accumulate * 1 term a next b))
(define (sum-iter term a next b)
(accumulate-iter + 0 term a next b))
(define (product-iter term a next b)
(accumulate-iter * 1 term a next b))
(display "\nexer 1.32\n")
(define (sum-squares a b)
(sum square a inc b))
(define (sum-squares-iter a b)
(sum-iter square a inc b))
(define (product-squares a b)
(product square a inc b))
(define (product-squares-iter a b)
(product-iter square a inc b))
(sum-squares 1 5)
(sum-squares-iter 1 5)
(product-squares 1 5)
(product-squares-iter 1 5)
; exercise 1.33
(define (filtered-accumulate predicate combiner null-value term a next b)
(cond ((> a b) null-value)
((predicate a)
(combiner (term a) (filtered-accumulate predicate combiner
null-value term (next a) next b)))
(else (filtered-accumulate
predicate combiner null-value term (next a) next b))))
(define (sum-prime-squares a b)
(filtered-accumulate prime? + 0 square a inc b))
(define (mutual-prime? a b)
(= 1 (gcd a b)))
(define (identity. x) x)
(define (product-mutual-primes n)
(filtered-accumulate (lambda (x) (mutual-prime? x n)) * 1 identity. 1 inc (- n 1)))
(display "\nexercise 1.33\n")
(sum-prime-squares 1 20)
(product-mutual-primes 10)
; exercise 1.35
(define tolerance 0.00001)
(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (try guess)
(let ((next (f guess)))
(if (close-enough? guess next) next
(try next))))
(try first-guess))
(define (golden-ratio)
(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0))
(display "\nexercise 1.35\n")
(golden-ratio)
; exercise 1.41
(define (double proc)
(lambda (x) (proc (proc x))))
(display "\nexer 1.41\n")
;((double inc) 3)
(((double (double double)) inc) 5)
; exercise 1.42
; lambda로 만드는 프로시져는
; x를 인자로 받아서 (g x)를 호출 후 리턴값으로 f를 호출
(define (compose. f g)
(lambda (x) (f (g x))))
(display "\nexer 1.42\n")
((compose. square inc) 6)
; exercise 1.43
(define (identity. x) x)
(define (repeated f n)
(if (= n 0) identity.
(compose. f (repeated f (- n 1)))))
(display "\nexer 1.43\n")
((repeated square 2) 5)
((repeated square 1) 2)
((repeated square 2) 2)
((repeated square 3) 2)
((repeated square 4) 2)
