1장. 함수로 추상화 쌓기
-
Building Abstractions with Procedures
- 1장은, 추상화를 쌓아 올리기 위한 함수 기법을 설명한다.
-
프로그래밍에서 추상화(abstraction)는 복잡한 것에서 불필요한 세부를 숨기고, 꼭 필요한 핵심만 간추려 내는 것을 말한다.
-
책에서는 함수(function)를 수학적인 개념이라하고, 프로씨저(procedure)를 계산 절차라 구분지었는데,
- 함수를 짠다는 말이 더 익숙하기에 그냥 이 둘을 합쳐서 함수로 퉁치자.
-
복잡한 것을 단순한 것에서부터 쌓아 올려 일반화(여러 상황에서 쓸 수 있도록)한다.
- 세부 구현을 숨기면, 복잡한 로직도 하나의 도구처럼 취급 가능
-
함수를 이름 붙여 재사용하고, 세부 구현을 감춘다.
-
동작 자체를 데이터처럼 다루는 능력
- 함수를 인자로 받아 사용하거나 함수를 반환하는 함수.
기본
문법
;; ================
;; 변수 정의
(define SIZE 2)
;; ================
;; 영역 변수
(let ((x 1)
(y 2))
(+ x y))
(let* ((x 1)
(y (+ x 2)))
(+ x y))
;; ================
;; 함수 정의
(define (Square x)
(* x x))
;; ================
;; 익명함수
((lambda (x) (+ x 4)) 5)
;; ================
;; 조건문 cond / if
(define (Abs-1 x)
(cond ((= x 0) 0)
((> x 0) x)
((< x 0) (- x))))
(define (Abs-2 x)
(cond ((< x 0) (- x))
(else x)))
(define (Abs-3 x)
(if (< x 0)
(- x)
x))
;; =============
;; 참(true , #t) / 거짓 (false , #f)
true
;;=> #t
#t
;;=> #t
false
;;=> #f
#f
;;=> #f
;; ================
;; 시퀀스의 각 요소에 함수를 적용.
(map (lambda (x) (* x x)) '(1 2 3 4))
;;=> (1 4 9 16)
기타 내장 함수
(display "Hello World") ; 출력
;;>> Hello World
(newline) ; 빈 라인 출력
;;>>
;;=>
(error "this is error!" 1 2 3) ; 에러 출력 및 중단
;;=> this is error! 1 2 3
(inc 1) ; 1 증가
;;=> 2
(dec 1) ; 1 감소
;;=> 0
Function / Procedure / Process
- 책에서는 함수와 프로시져를 구분해왔으나, 여기 개념설명 이후, 그냥 함수( function + procedure )로 퉁 치겠다.
함수(Function) = 수학적 개념
Factorial(N) = N!
프로시저(Procedure) = 프로그래머가 작성한 계산 절차(알고리즘)
(define (Factorial n)
(if (= n 1)
1
(* n (Factorial (dec n)))))
프로세스(Process) = 프로시저를 실행할 때, 전개되는 계산의 단계적 진행상황
(Factorial 3)
→ 3 * (Factorial 2)
→ 3 * (2 * (Factorial 1))
→ 3 * (2 * (1 * (Factorial 0)))
→ 3 * (2 * (1 * 1))
→ 6
일반 재귀 (non-tail recursion)와 꼬리 재귀 (tail recursion)
- procedure와 process의 차이를 보여주며, procedure가 만들어내는 process를 상상해 낼 수 있는 능력을 강조.
- procedure
- 함수 정의, 계산을 수행하기 위한 명령어 집합 혹은 알고리즘의 규칙
- process
- 메모리, 시간, 호출 스택 등과 관련된 실행의 구체적인 양상
- procedure
일반 재귀 (non-tail recursion) linear recursive process
- 내부의 곱셈을 계산하기 위해 함수의 Call 스택이 쌓인다.
- 단계가 늘어나면 스택이 넘치게 된다( Stack overflow )
(define (Factorial-recur n)
(if (= n 1)
1
(* n (Factorial-recur (dec n)))))
;; (Factorial-recur 3)
;; → 3 * (Factorial-recur 2)
;; → 3 * (2 * (Factorial-recur 1))
;; → 3 * (2 * (1 * (Factorial-recur 0)))
;; → 3 * (2 * (1 * 1))
;; → 6
꼬리 재귀 (tail recursion) linear iterative process
- 스택 프레임 생성 자체를 억제시켜 함수의 Call 스택이지 않는다.
(define (Factorial-iter n)
(if (< n 0)
(error "n must be greater than or equal to 0. n =" n ))
(define (iter acc x)
(if (= x 0)
acc
(iter (* acc x) (dec x))))
(iter 1 n))
;; (Factorial-iter 3)
;; → (iter 1 3)
;; → (iter (* 1 3) 2)
;; → (iter (* 3 2) 1)
;; → (iter (* 6 1) 0)
;; → 6
고차 함수 (higher-order function)
- 함수를 데이터처럼 사용하는 함수
- ex)
- C 에서의 함수포인터
- C# 에서의 delegate 혹은 Func/Action/Predicate타입
- ex)
(define (compose f g)
(lambda (x)
(f (g x))))
(define (square x)
(* x x))
((compose square inc) 6)
;=> (square (inc 6))
;=> (square 7)
;=> 49
평가전략(evaluation strategy)
- Applicative-Order Evaluation
- 다른 이름: Call-by-Value, Eager Evaluation
- 인자를 먼저 평가하고 그 결과 값을 프로시저에 대입
- Normal-Order Evaluation
- 다른 이름: Call-by-Name
- 인자를 평가하지 않고 그대로 본문에 대입 (문자 그대로 펼침)
- Lazy Evaluation
- 다른 이름: Call-by-Need
- Normal-Order와 비슷하지만 한 번 계산한 결과를 저장해서 다시 계산하는것을 방지(메모이제이션)
뉴턴-랩슨 방법으로 제곱근 찾기
- 뉴턴-랩슨 방법( Newton-Raphson method )
- https://en.wikipedia.org/wiki/Newton%27s_method
- 미분가능한 함수 f(a, b) → R에 대해 x에 대한 방정식 f(x)=0의 근의 근삿값을 구하는 알고리즘.
- 뉴턴: 1669년 무렵, 비선형 방정식을 푸는 반복법을 고안. 주로 기하학적 직관과 미분 개념을 활용.
- 랩슨: 1690년에 뉴턴 방법을 기하학 설명 없이 순수 대수 형태로 단순화해서 발표. 이 버전이 계산에 더 쓰기 좋아짐.
- 뉴턴-랩슨 공식
$$ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} $$
제곱근 구하기
$$ y {>=} 0; 이고; y^2=x; 일때; \sqrt{x}는; y다.$$
$$ y \ge 0, \quad y^2 = S$$
-
함수 정의 $$ f(x) = x^2 - S $$
-
미분 $$ f'(x) = 2x $$
-
공식에 대입 $$ x_{n+1} = x_n - \frac{x_n^2 - S}{2x_n} $$
$$ x_{n+1} = \frac{2x_n^2 - x_n^2 + S}{2x_n} $$
$$ x_{n+1} = \frac{x_n^2 + S}{2x_n} $$
- 최종 식 $$ x_{n+1} = \frac{1}{2} \left( x_n + \frac{S}{x_n} \right) $$
;; 1.1.7 연습: 뉴튼 법으로 제곱근 찾기
;; 연습문제: 1_06, 1_07
(define (square x)
(* x x))
(define (sqrt-iter guess x)
(if (good-enough? guess x)
guess
(sqrt-iter (improve guess x) x)))
(define (improve guess x)
(average guess (/ x guess)))
(define (average x y)
(~> (+ x y)
(/ 2)))
(define (good-enough? guess x)
(~> (square guess)
(- x)
(abs)
(< 0.001)))
(define (sqrt x)
(sqrt-iter 1.0 x))
(sqrt 9)
;;=> 3.00009155413138
TODO
ex 1.5 Applicative-Order Evaluation / lazy
1.17 뉴튼법 제곱근 ex 1.6 뉴튼 cont if 스페셜폼 ex 1.7 ** 뉴튼 cont good-enough 최적화 ex 1.8 뉴튼 cont 세제곱근(cube root) - ** 식이 나와있는데 원레 3제곱에서 유도하는법 1.3.4 - 뉴튼법 cont
1.2.1 재귀
- non-tail recursion / tail recursion
- Primitive Recursive Function / or not
ex 1.9 일반 재귀 (non-tail recursion)와 꼬리 재귀 (tail recursion) ex 1.10 에커만 함수 Primitive Recursive Function가 아닌 리커시브함수 ex 1.11 ** 꼬리 재귀 (tail recursion) 연습 심화 ex 1.12 파스칼 삼각형 recursion ex 1.13 *** 증명 ;; φ = (1+√5)/2 // Fib(n) = (φ^n)/√5 피보나치 수열. 특성방정식. 황금비. Binet 공식. 귀납법(induction)
1.2.4 거듭제곱 fast-expt ex 1.19 ** fast-fib-iter
1.2.5 최대공약수 GDC 유클리드
소수찾기 페르마 검사 연습문제 피보나치 하노이의 탑