-
내 맘대로 프로그램 설계 7. - 함수형 프로그래밍.프로그래밍/설계 2019. 5. 21. 17:07
내 맘대로 하는 프로그램 설계 시리즈.
Chapter1 - 간단한 데이터 처리(4섹션)
2017/12/27 - [프로그래밍/설계] - 내 맘대로 프로그램 설계 1. - 이유와 준비.
2018/01/11 - [프로그래밍/설계] - 내 맘대로 프로그램 설계 2. - 데이터 타입.
2018/01/16 - [프로그래밍/설계] - 내 맘대로 프로그램 설계 3. - 함수와 변수.
2018/05/29 - [프로그래밍/설계] - 내 맘대로 프로그램 설계 4. - 고정 크기 데이터.
2017/06/30 - [프로그래밍/설계] - 프로그래밍과 추상화에 대하여.[부록]
Chapter2 - 임의의 데이터 처리
2018/06/10 - [프로그래밍/설계] - 내 맘대로 프로그램 설계 5. - 리스트와 재귀.
2019/05/20 - [프로그래밍/설계] - 내 맘대로 프로그램 설계 6. - 데이터구조와 알고리즘[연재예정].
Chapter3 - 추상화
2019/05/20 - [프로그래밍/설계] - 내 맘대로 프로그램 설계 7. - 함수형 프로그래밍(현재).
1. 시작하기.
우리가 사용하고 있는 Racket은 첫시간에도 언급했듯이 함수형 프로그래밍 패러다임을 따르고 있다.
각종 프로그래밍 패러다임은 프로그램을 추상화 시켜 사람들이 다루기 편하도록 만들어주는 역할을 한다.
그 첫번째로, Racket && Lisp의 대표적 패러다임인 함수형 프로그래밍을 간단히 다루어보고자 한다.
다음은 위키피디아에서 나온 함수형 패러다임의 정의다.
함수형 프로그래밍은 자료 처리를 수학적 함수의 계산으로 취급하고 상태와 가변 데이터를 멀리하는 프로그래밍 패러다임의 하나이다. 명령형 프로그래밍에서는 상태를 바꾸는 것을 강조하는 것과는 달리, 함수형 프로그래밍은 함수의 응용을 강조한다. 프로그래밍이 문이 아닌 식이나 선언으로 수행되는 선언형 프로그래밍 패러다임을 따르고 있다. 함수형 프로그래밍은 1930년대에 계산가능성, 결정문제, 함수정의, 함수응용과 재귀를 연구하기 위해 개발된 형식체계인 람다 대수에 근간을 두고 있다. 다수의 함수형 프로그래밍 언어들은 람다 연산을 발전시킨 것으로 볼 수 있다.
함수형 프로그래밍의 핵심은 '상태변화'를 억제하는 것이다.
따라서 인수에만 의존하고, 인수 $x$에 같은 값을 넣고 함수 $f$를 호출하면 항상 $f(x)$라는 결과가 나온다.
아래는 C언어 코드로 상태변화의 대표적인 예시다.
int a = 0; int b = 2; a = 1; a = b;Racket으로는 요랬던 코드..
Code 7.1
(define a 0) (define b 2) (set! a 1) (set! a b)보다시피 변수 'a'의 상태가 $0 \to 1 \to 2(b의 상태)$처럼 변화하고 있다.
이 사이에 $a+1$라는 연산이 있다면 결과가 달라지는 것이다!!
프로그램의 상태에 따라 연산의 결과가 달라진다면, 프로그램의 디버깅시 변수추적이 까다로워진다.(특히 병렬 프로그래밍)
그럼, 본격적으로 함수형 프로그래밍을 다루어보자.
2. 순수 함수(Pure Fuction).
2018/01/16 - [프로그래밍/설계] - 내 맘대로 프로그램 설계 3. - 함수와 변수.
시간에 부작용(Side Effect)에 대하여 언급한 적이 있다.
컴퓨터 과학쪽에서는 함수가 결과값말고 다른 상태를 변경시키면 부작용(Side Effect, 보통 사이드 이펙트라 부름)이 생겼다고 한다. 사이트 이펙트가 생기면, 예측되지 못한 값이 나올 확률이 올라가 버그가 나오기 쉽고, 컴파일러가 최적화를 하기 힘들어진다.
근삿값이 정확한 값과 함께 계산하면 근삿값이 나오듯이 사이드 이펙트도 사이드 이펙트가 일어난 함수가 사용되면 퍼져나간다.순수 함수는 부작용이 없는 함수를 말한다.(참조 투명성을 가진다고도 함)
즉, 상태변화가 없다는 것!!
두가지 예제를 더 보며 순수 함수를 이해해보자.
2.1 최적화와 Random.
우선 $add1$은 순수 함수이다.
들어가는 인수값과 상관없이 항상 $+ 1$을 한 결과를 돌려주기 때문이다.
순수한 형태인 함수 $add1$은 다음과 같이 최적화를 할 수 있다.
Code 7.2
;;Original Pure (define pure (* (add1 a) (add1 a))) ;;Optimize Pure (define pure-temp (add1 a)) (define pure-opti (* pure-temp pure-temp)) (= pure pure-opti)결과: #true
처음 함수인 Pure은 (add1 a)을 두번 계산했지만,
두번째 pure-opti는 (add1 a)의 값을 저장(pure-temp)하고 그 값을 곱함으로서 add1 연산을 한번 줄일 수가 있었다.
그리고, 이 값들은 항상 같습니다.
그럼 랜덤에서 성립하나 생각 해봅시다.
Code 7.3
;; original (define side (* (random) (random))) ;; optimize?? (define side-temp (random)) (define side-opti (* side-temp side-temp))random이란 함수는 난수 값을 반환해주는 함수.
따라서 실행할 때 마다 결과값이 달라지게 되고, side-opti는 원래의 의도에서 달라지게 된다.
여기에서 random은 부작용(side-effect)를 일으키는 함수고, 부작용은 최적화에 악영향을 줄 수 있다는 것을 알 수 있다.
2.2 숨겨진 상태변화.
다음 함수는 stack에 특정한 값을 집어넣는(push)하는 함수이다.
Code 7.4
(define stack (make-stack val)) (define (stack-push val) (push stack val))여기에 상태변화가 존재하는가?
그렇다.
stack에 값이 들어와 상태가 변화되었다.
stack이란 입력이 숨겨졌다고 볼 수 있다.
숨겨진 상태변화를 없에려면 명시적으로 매개변수와 출력값을 지정해주면 된다.
Code 7.5
(define (stack-push-noside stack val) (push stack val))약간 복잡해보이긴 하지만, 보편적인 함수가 되었고 명시적이라 디버깅시 값추적이 편해진다.
또 다른 숨겨진 상태변화의 예로는 키보드 입력이나 모니터 출력 같은 IO(Input/Output) 작업들을 꼽을 수 있다.
하스켈은 IO 작업에서도 함수형으로 다루기 위해 모나드를 도입했다.
하스켈 위키가 가장 좋겠지만..
그림으로 설명하는 펑터, 아플리커티브, 모나드 또는 INTRODUCTION TO FUNCTIONAL PROGRAMMING USING HASKELL (한글이에요 ㅋㅋ)의 모나드, IO Monad를 참고하기 바란다.
여담으로 Reactive 프로그래밍에서 Observable이란 것도 모나드의 형태다.
3. 람다대수(Lambda Calculus).
3.1 정의.
2018/07/22 - [수학] - 무한, 집합, 그리고 수에 대해서.
힐베르트는 수학적인 명제가 입력으로 주어질 때 참과 거짓을 알아내는 알고리즘을 연구했다. 그러나 괴델이 그런 알고리즘은 존재하지 않고, 존재할 수 없음을 불완전성 정리로 증명했다.
따라서 수학자들은 '계산 가능한 문제'에 관심을 가졌고 그 결과로 나온 것이 튜링머신(Turing Machine), $\lambda$-대수(Lambda Calculus), 포스트 시스템(Post canonical system)이며, 모두 튜링 완전하다는 것이 증명되고 역도 성립한다고 한다.
이에 대한 내용은 추후에 따로 다루어보도록 한다.
기계어-어셈블리-C언어와 같은 명령형 언어 계보는 튜링머신을, Lisp-Racket, ML-Haskell등 함수형 언어의 계보는 람다대수로부터 아이디어를 가져왔다.
장황한 설명을 보니 엄청나게 복잡한 체계인것 같은데...
람다대수의 정의는 BNF로 보면 의외로 간단하다.
< expression > := < name >|< function >|< application > < function > := λ < name > . < expression > < application > := < expression >< expression >2018/07/31 - [수학/이산수학] - 기초: 논리와 증명.
를 보면 BNF를 이해할 수 있다!!
BNF를 해석해보면 람다대수는
- 표현식은 변수, 함수, 적용
- 함수는 매개변수와 표현식
- 적용은 표현식들
로 이루어져 있다는 것을 알 수 있다.
3.2 기초 사용법.
람다 대수에서 표현식의 표기를 명확히 하기 위해 괄호를 사용하며, 함수의 적용은 왼쪽으로 결합한다.
$$E_1E_2E_3...E_n \equiv (...((E_1E_2)E_3)...E_n))$$
요거요거 어디서 많이 보던 형태 아닌가?????
그렇다!!
바로 우리가 Racket에서 지금까지 써오던 방식과 동일!! (처음 배울때 여기서 감동 먹었던)
람다 함수의 형태도 같다.
$$\lambda x.x \equiv (\lambda x.x)$$
$\lambda$다음 첫번째로 등장하는 $x$는 식별자로 불리며, 프로그래밍 함수에서는 매개변수로 생각할 수 있다.
$.$이후에 등장하는 $x$는 함수의 본문(Body)다.
즉, 위 함수는 항등함수인 $f(x)=x$와 같다.
이제 앞서 나왔던 평가방법대로 적용(Application)해보자.
평가방법 $$(\lambda x.x)y \to [y/x]x \to y$$
$x$가 $y$로 치환됨을 볼 수 있다.
코드로 나타내도 거의 똑같다.
Code 7.6
(lambda (x) x) ((lambda (x) x) 1)결과: (lambda (a1) ...), 1
Code 7.7
(define x 1) (define y (lambda (y) y)) x (y x) (y 2)결과: 1, 1, 2
단, 람다 대수에서 중요한 것이 있다.
식별자의 이름(name)은 자리표시자(place holder)일 뿐이라는 거.
따라서 아래 표현은 모두 같은 함수다.
$$(\lambda z.z) \equiv (\lambda y.y) \equiv (\lambda t.t) \equiv (\lambda u.u)$$
순수한 알파벳 치환은 $\alpha$-reduction이라 불림.
3.3 자유 변수와 종속 변수(Free Variable and Bound Variable).
앞서 나온 $\lambda x.x$의 모든 이름은 지역변수(loacal variable)이다.
따라서 $x$는 본문에 출현한 이후에 $\lambda x$가 있으므로 종속(Bound)되었다 부른다.
반대로 $\lambda$로 시작하지 않는 이름은 자유변수나 비지역 변수라 한다.
간단히 예를 들어보면
$$(\lambda x.x)(\lambda y.yx)$$
첫번째 본문의 $x$는 종속 되었지만, 두번째 함수 본문의 $x$는 자유 변수다.
축약하는 과정을 $\beta$-reduction이라 한다. Code 7.8
((lambda (x) x) ((lambda (y) (+ x y)) 1))결과: 2
$\lambda y. x+y$에서 $x$는 Code 7.7에서 정의된 자유변수이다.
이제 우리는 <name>에 대하여 자유변수와 종속변수의 정의를 알 수 있다.
- 자유변수
- <name>은 <name>의 자유 변수.[예: $a$는 $a$의 자유변수]
- <name>은 $\lambda$<name1>의 자유 변수(<name>$\neq$<name1>인 표현식이고, 표현식에서 자유변수 일 때)[예: $\lambda x.y$의 $y$]
- <name>은 $E_1E_2$의 자유 변수($E_1$ 또는 $E_2$에서 자유변수 일 때. [예: $(\lambda x.x) x$])
- 종속변수
- <name>은 $\lambda$<name1>의 종속 변수(<name>$=$<name1>인 표현식이고, 표현식에서 종속변수 일 때) [예: $( \lambda y.(\lambda x.x))$]
- <name>은 $E_1E_2$의 자유 변수($E_1$ 또는 $E_2$에서 종속변수 일 때.)[예: $(\lambda x.x) x$]
3.4 다중 적용.
$$(\lambda x.(\lambda y.xy)y)$$
는
$$(\lambda xy.xy)$$
로 줄일 수 있다.
Code 7.9
((lambda (x) ((lambda (y) (+ x y)) 2)) 1) ((lambda (x y) (+ x y)) 1 2)결과: 3, 3
4. 일급 객체, 커링, 클로저(First Class Citizen, Curring, Closure).
4.1 일급 객체.
다음은 1급 객체의 정의이다.
- 변수나 데이터 구조안에 담을 수 있다.
- 파라미터로 전달 할 수 있다.
- 반환값(return value)으로 사용할 수 있다.
- 할당에 사용된 이름과 관계없이 고유한 구별이 가능하다.
- 동적으로 프로퍼티 할당이 가능하다.
람다대수를 공부하며 코드를 봤겠지만, Racket에서 함수는 모두 가능하다!!
일급 객체에 함수가 속하는 것이다.
따라서 다음 함수는 같다.
Code 7.10
(define (func1 num) (+ num 3)) (define func2 (lambda (num) (+ num 3)))4.2 커링.
함수를 파라미터로 전달하고, 반환할 수 있다면 커링(Curring)이라는 것이 가능해진다.
다중 인수를 가진 함수를 단일 인수를 갖는 함수들의 함수열로 바꾸는 것을 말한다.
2개와 3개로 커리 함수를 만들어보자.
Code 7.11
(define (curry2 f) (lambda(x) (lambda(y) (f x y)))) (define (curry3 f) (lambda(x) (lambda(y) (lambda(z) (f x y z))))) (((curry2 +) 1) 2) ((((curry3 +) 1) 2) 3)결과: 3, 6
사용하는 방법이 괴랄해보인다 ㅋㅋㅋ
하지만
Code 7.12
(define curry-temp ((curry2 +) 1)) (curry-temp 2)결과: 3
인수를 부분적으로 받고 함수의 실행을 늦추거나, curry를 이용해 함수를 정의하여 재사용성을 늘릴 수도 있다.
4.3 클로저.
클로저를 배우기 전에 중요한 개념 두가지를 짚고 넘어가고자 한다.
- Lexical Scope
함수 본문은 함수가 불려지는 것이 아닌 정의된 범위의 모든 바인딩을 사용할 수 있다. - 닫힌(Closed) 람다식과 열린(Open) 람다식
변수들이 모두 묶인 변수일 때 닫힌 람다식.
사용하는 변수들 중 하나라도 자유 변수가 있을 때 열린 람다식.
클로저는 열린 함수를 닫힌 함수로 만들어주는 것이다.
2018/07/30 - [수학] - 집합(위상)과 극한에 대하여[일부 내용 펌].
를 보고 오면 편할 것이다.
이제 클로저 사용하는 예제를 봐보자.
단, Code 7.7이 미리 실행되어 있다고 가정한다.
Code 7.13
(define f (lambda (y) (+ x y))) (define z (let ([x 2] [y 3]) (f (+ x y)))) z결과: 6
이번에 처음보는 let 함수는 지역 변수를 만들어주는 함수다.
Code 7.14
(let ([x 1]) x)결과: 1
z가 호출될 때 내부에서[(x 2) [y 3]]때문에(f (+ x y))=>(f (+ 2 3))=>(f 5)로 계산하게 된다.이때 f가 클로저 대상이 되는 함수다.
그럼 어떻게 계산되는지 계속 살펴보자.
함수
f의 식별자를 보면x,y가 존재한다.x는 자유변수,y는 종속변수로 이루어져 있는데y는 입력받은 값 5가 된다.자유변수인
x가 어디에 정의되었나 봤더니 외부(Code 7.7)에서 정의된x값(1)이었다.따라서 함수
f의 범위가 결정되어 닫힌 상태로 전환되었다.그 후 $1+5=6$으로 결과가 완결났다는 것을 알 수 있다.
5. 고차함수(High-Order Function).
이제 고차함수를 알아보고 다루어보자.
하나 이상의 함수를 인자로 받거나, 결과로 반환하는 함수를 고차함수(High-Order Function)라고 한다.
다른 모든 함수들은 일차함수(First-Order Function)이다.
형식 람다 대수에서 모든 함수들은 고차 함수.
고차함수의 예를 들어보자.
Code 7.15
(define (add x y) (+ x y)) (define (g x) (lambda (y) (+ x y))) ((g 3) 7) (add 3 7)결과: 10, 10
함수 g는 커링이 된 형태인데 함수를 반환하므로, 고차함수라 볼 수 있다.
이제 유명한 고차함수 5가지만 알아두고, 이번 섹션을 마치도록 합시다.
아래에서 소개하는 함수만 잘 써도 인생이 풍요로워집니다.
마치 엑셀의
vlookup,index,match같은 함수들이랄까?5.1 for-each.
Code 7.16
(define (my-for-each func list) (unless (null? list) (begin (func (car list)) (my-for-each func (cdr list))))) (my-for-each print '(1 2 3 4 5))결과: 12345
리스트 값들을 하나씩 대입해주는 함수다.
5.2 map.
Code 7.17
(define (my-map func list) (if (null? list) '() (cons (func (car list)) (my-map func (cdr list))))) (my-map curry-temp '(1 2 3 4 5))결과: '(2 3 4 5 6)
리스트 값에 전달받은 함수의 계산결과 새로운 리스트를 만들어 내는 함수다.
여기에서 커링(Currying)은 인자값을 자동으로 전달 받을 수 있다는 것을 알 수 있습니다.
5.3 reduce.
Code 7.18
(define (my-reduce func list) (if (null? (cdr list)) (car list) (func (car list) (my-reduce func (cdr list))))) (my-reduce + '(1 2 3 4 5)) (my-reduce (lambda (x y) (* x y)) '(1 2 3))결과: 15, 6
전해받은 리스트 결과에 연산을 적용하여 하나의 결과로 수렴해내는 함수다.
특정 로직을 한번만 사용할 경우 람다 함수를 사용하면 된다는 것도 이 예제를 통해 알 수 있다.
5.4 filter.
Code 7.19
(define (my-filter func list) (if (null? list) '() (if (func (car list)) (cons (car list) (my-filter func (cdr list))) (my-filter func (cdr list))))) (my-filter positive? '(1 -2 3 4 -5))결과: '(1 3 4)
특정 결과에 해당하는 것만 리스트로 만들어 반환한다.
5.5 find.
Code 7.20
(define (my-find func list) (if (null? list) #false (if (func (car list)) (car list) (my-find func (cdr list))))) (my-find integer? '(1.1 2.1 3 4 5.1)결과: 3
첫번째로 조건에 만족하는 것을 찾아 반환한다.
참고: 위키백과(함수형 프로그래밍 , 일급 객체, 고차 함수), A Tutorial Introduction to the LambdaCalculus,
댓글