SICP.md

SICP

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

데이터 구조, 기능 관계성을 설명하는 용도로 리스프가 알맞다.

• 프로시저를 보통 데이터처럼 쓸 수 있다.
• 데이터와 프로시저를 구분하지 않는다
  • 대표 예로 표현식 = 값 인가?

리스프는 프로시저를 데이터처럼 다룬다.

(컴파일러처럼)
다른 프로그램을 데이터처럼 받아 처리하는 프로그램을 짜는 일에 아주 좋은 언어이다.

-> 메타 프로그램을 받아 실행하는 메타 프로그래밍 언어?

DSL을 이야기하는 건가? 다른 분 의견 : 데이터와 프로시져의 정의가 다르지 않다.

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

프로그래밍 언어는 프로세스에 대한 사람의 생각을 짜임세 있게 담아내는 그릇이다.

1.1.3 엮은 식을 계산하는 방법

절차대로 일하는 방법으로 짤 때 짚어 볼 문젯거리가 몇개 있다.

• 리스프는 다른 도구에 비해 문법이 거의 없다.

리스프에서 문법을 하찮게 여기는 까닭은

1. 언어 인터페이스를 쉽게 바꿔 쓰는 게 가능히다.
2. 편한 문법을 가진 언어는 규모가 어느 정도 커지면 피로함을 느낀다.

익명 함수

((lambda (a) (* a a)) 3)

묶음 프로시저 정의, 조건 식, 술어

(define (fb n)
  (if (< n 2)
    n
    (+ (fb (- n 1)) (fb (- n 2)))
  )
)

cond 식에서 각 절의 자리에는 잇단식이 올 수 있다.
하지만 if 식에는 식 하나만 쓸 수 있다.

The Substitution Model for Procedure Application

Scheme is an applicative-order language, namely, that all the arguments to Scheme procedures are evaluated when the procedure is applied. In contrast, normal-order languages delay evaluation of procedure arguments until the actual argument values are needed. - 4.2.1 Normal Order and Applicative Order

연습문제 1.1

(define a 3) ; a
(define b (+ a 1)) ; b
(+ a b (* a b))
(= a b) ; 19
; 생략

연습문제 1.2

(/
  (* 3 (-  6  2) (- 2 7))
  (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5)))))
) ; -150/37

1.3

Define a procedure that takes three numbers as arguments and returns the sum of the squares of the two larger numbers.

1.4

(define (a-plus-abs-b a b)
  ((if (> b 0) + -) a b))

함수 이름 그대로 a + abs(b)

1.5

(define (p) (p))

(define (test x y) 
  (if (= x 0) 
      0 
      y))

(test 0 p)

인자 먼저 계산법

p 무한 재귀 평가로 test 함수에서 값으로 실행을 하지 않는다.

normal-order evaluation

(test 0 (p))
	-> (if (= 0 0) 0 (p))
  -> 0

1.6

함수 호출 -> 호출 -> 호출...
정규 함수로 묶으니 스택이 계속 쌓인다. 꼬리 재귀 최적화가 없는 경우다.

1.9

Exercise 1.9 Each of the following two procedures defines a method for adding two positive integers in terms of the procedures inc, which increments its argument by 1, and dec, which decrements its argument by 1.

(define (+ a b)
  (if (= a 0)
      b
      (inc (+ (dec a) b))))

(define (+ a b)
  (if (= a 0)
      b
      (+ (dec a) (inc b))))

Using the substitution model, illustrate the process generated by each procedure in evaluating (+ 4 5). Are these processes iterative or recursive?

1. 되도는 프로시저

(+ 4 5)
(inc (+ 3 5))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9

2. 반복하는 프로시저

(+ 4 5)
(+ 3 6)
(+ 2 7)
(+ 1 8)
(+ 0 9)
9

1.11

되도는 프로시저

(define (f-recursive n)
  (if (< n 3)
      n
      (+ (f-recursive (- n 1))
         (* 2 (f-recursive (- n 2)))
         (* 3 (f-recursive (- n 3))))))

1.16

반복 프로세스를 사용하는 거듭 프로시저

• b^2 = (b^n/2) * 2

(define (expt-iter product goal count)
  (if (equal? goal count)
    product
    (expt-iter (* square product)
    goal
    (+ count 1))
  )
)

(define (expt b n)
	(expt-iter b n 1))

Error: *: number required, but got [expt, expt-iter, *]?

1.20

GCD를 유클리드 호제법으로 풀기

(define (gcd a b)
	(if (= b 0)
		a
		(gcd b (reaminer a b)))

정의대로 개산법

(gcd 206 40)

(if (= 40 0)
    206
    (gcd 40 (remainder 206 40)))

(if (= (remainder 206 40) 0)
    40
    (gcd (remainder 206 40)
			(remainer 40 (remainder 206 40))))
; a = 6
if (= (remainer 40 (remainder 206 40)) 0)
	(remainder 206 40)
	(gcd (remainer 40 (remainder 206 40))) (remainer (remainder 206 40) (remainer 40 (remainder 206 40))))

????

(if (= b 0) 는 대체 언제 계산 하나요?

SICP solution 에서는 1*remainder 주석이 달면서 풀어진다.

인자 먼저 개산법

(gcd 206 40)

(if (= 40 0)
    206
    (gcd 40 (remainder 206 40)))

(gcd 40 6)

(if (= 6 0)
    40
    (gcd 6 (remainder 40 6)))

(gcd 6 4)

(if (= 4 0)
    6
    (gcd 4 (remainder 6 4)))

(gcd 4 2)

(if (= 2 0)
    4
    (gcd 2 (remainder 4 2)))

(gcd 2 0)

(if (= 0 0)
    2
    (gcd 0 (remainder 2 0)))

2