Welcome to F#(7) - 클리프 행어.

F# 2009. 4. 26. 18:22 Posted by 알 수 없는 사용자

-거인의 어깨에 위태롭게 매달려서 안간힘-_-.

여전히 함수형언어를, F#을 이해하기 위해서 몸부림 치고 있습니다. 제 짧은 생각인지 모르겠으나, F#을 처음배우는 프로그래밍언어로 생각하시는 분은 없을거라고 생각합니다. 호기심이든 다른 목적이 있어서든 기존에 주력으로 쓰는 명령형 언어가 있고 추가로 공부하려고 하시는 분이 거의 대부분이 아닐까 합니다.(게다가 F#은 C#이나 VB.NET을 하시던 분이 거의 대부분이 아닐까 싶네요) 저 역시 C#을 주력으로 쓰면서 F#을 공부하고 있는거니까요.

그래서 단순히 문법적 차이를 말씀드리기 보다는 함수형언어에 깔려있는 사상&접근법&관점의 차이에 대해서 말씀드리고자 하는데, 부족한 지식으로 글이 들쭉날쭉하고 앞내용과 뒷내용이 연결이 안되는, 한글이 생긴이래 진급을 못하고 있는 불상사도 자주 보게되는거 같습니다. 

오늘도 함수형언어를 이해하기 위한 노력의 일환으로 한 논문의 내용을 바탕으로 이야기 하도록 하겠습니다. Anders hejlsberg가 언어설계에 대한 이야기를 하면서 자신은 다른 거인의 어깨위에 서있다고 말을 했었는데, 저는 거인의 어깨에 선게 아니라 위태롭게 매달려 있다는 느낌이 드는군요.-_-;  아놔, 오늘도 서론이 길군요-_-;;

 

-무슨 논문이냐.

제가 한번 
"Why Functional Programming Matters?"라는 논문에 대해서 언급한적이 있었습니다. 오늘 포스트의 바탕이 될 이 논문에서 모듈화에 대한 이야기를 하면서 다음과 같은 이야기를 합니다. 

However, there is a very important point that is often missed. When writing a modular program to solve a problem, one first divides the problem into subproblems, then solves the sub-problems and combines the solutions. The ways in which one can divide up the original problem depend directly on the ways in which one can glue solutions together. Therefore, to increase ones ability to modularise a problem conceptually, one must provide new kinds of glue in the programming language. Complicated scope rules and provision for separate compilation only help with clerical details; they offer no new conceptual tools for decomposing problems. 

하지만, 그런 이야기에서 중요한 점이 무시되곤 한다. 어떤 문제를 해결하기 위해서 모듈화된 프로그램을 작성할때, 프로그래머는 우선 문제를 작은 문제로 분리해내야 하고, 각각의 작은문제를 해결해서 하나의 솔루션으로 조합해야 한다. 문제를 어떻게 분리할지는 전적으로 해결된 문제들을 어떻게 하나의 솔루션으로 조합할지에 달려있다. 그러므로 프로그래머가 조금더 능숙하게 문제를 모듈화해서 해결하게 해주려면, 프로그래밍언어에서 문제를 붙이기 위한 새로운 접착제를 제공해줘야 한다.  복잡한 스코프룰이나 분리컴파일을 좀 더 편리하게 할 수 있게 도와주는 것들은 그저 사무적인일(문제를 해결하는일 자체보다는 코드작성을 도와주는 부차적인일)정도를 도와줄 뿐이다. 즉, 문제를 잘개 쪼개기 위해선 아무 도움도 안되는 것이다.


그러면서 저자는 함수형언어에서 문제를 붙이기 위해 쓰이는 두가지 접착제를 소개합니다. 그 중 하나가 지난포스트에서도 언급했었던 higher-order function입니다. 기억나시나요? 함수를 인자로 받고 함수를 리턴가능한 함수가 higher-order function이었죠? 이 논문은 Miranda라는 언어를 사용하면서 Haskell을 쓰지 못해서 죄송하다고 언급하고 있습니다. 하지만, 조금 된 논문이라 F#으로 못해서 죄송하다는 말은 없군요. 크하하하-_-;;

그럼 저자가 higher-order function의 예로 언급한 reduce를 F#으로 구현해보면서 설명드리도록 하겠습니다. reduce는 MapReduce때문에 유명해지기도 했고, fold라는 이름으로도 불리는데요, 아마도 fold나 reduce나 둘다 뭔가를 하나씩 줄여나가는 이미지를 연상하면서 붙인 이름이 아닌가 싶습니다.


우선, 원문을 보실분들을 위해서 Miranda에 대해서 아주초큼 설명을 드리자면, Miranda는 ML에서 ML은 Lisp에서 출발한 언어라고 합니다. Lisp에서는 리스트를 Pair의 조합으로 표현하는데요, 여기서도 그런거 같습니다. Pair의 조합이란 cons(construct의 준말이라는 군요)라는 함수를 통해서 만들어지는데요(Lisp이나 Scheme하신분들은 많이 보셨을듯~) 인자를 두개 받아서 그 두 인자를 하나의 쌍으로 묶어서 리턴하는 함수입니다. 즉 Lisp에서 (1 2 3 4)라는 리스트는,

 

 (cons 1

(cons 2

(cons 3

(cons 4 nil)))) 


nil은 Lisp에서 빈값을 뜻합니다, (1 2)는 (cons 1 2), (1 2 3)은 (cons 1 (cons 2 3))의 결과 인거죠. F#이 OCaml에서, OCaml은 ML에서 출발했으니, F#에서도 리스트는 비슷하게 구현되지 않았을까 싶습니다.(List.hd, List.tl같은 함수를 보면 그런거 같습니다.) 그리고 두개의 값이 하나의 쌍으로 이루어 져있기 때문에, 값에서 head부분과 tail부분으로 나눠서 생각할 수 있습니다. (1 2 3)의 head는 1이고 tail은 (2 3)입니다. (4 5 6 7)의 head는 4이고 tail은 (5 6 7)인거죠

 

-그래 그래 얼른 reduce가 뭔지나 좀 보자.

일단, 숫자의 리스트를 모두더하는 sum을 생각해보도록 하죠. 빈값에 대한 sum은 0이겠죠? 그래서 아래와 같이 정의합니다. 

sum [] = 0 

그리고 리스트의 합은 head의 값과 나머지 tail의 합으로 정의할 수 있고, 그 tail의 합은 다시 head의 값과 나머지인 tail의 합으로 정의할 수 있습니다. 즉, 

sum list = List.hd(list) + sum List.tl(list) 

이렇게 정의할 수 있습니다. List.hd는 head의 약자로 List에서 head를 리턴하고, tl은 tail의 약자로 List에서 head를 제외한 나머지 부분을 리턴합니다. 이런 과정을 어떤 함수가 들어와도 가능하게 일반화 하려면, 위에서 빨간색(?)으로 음영표시한 두부분이 중요해 집니다. 즉, '리스트의 마지막에 도달했을때 어떤 값을 리턴할 것인가'와 '리스트의 head와 tail에 대해 어떤 함수를 수행할 것인가'하는 부분입니다. 예를 들면, 리스트에 대해서 곱셈을 수행하는데, 빈리스트에 대해서 0을 리턴하게 한다면 리스트의 곱셈값은 0이 되겠죠-_-;; 그래서 이럴땐 빈리스트의 값을 곱셈에 영향을 안주는 1로 설정해야 합니다. 물론, 위의 경우에서는 합에 영향을 주지 않는 0으로 선택한 것이구요. 

그럼, 각 리스트의 요소에 대해 수행할 함수를 아래와 같이 정의합니다. 

let add x y = x + y 

그리고 다음과 같이 reduce함수를 작성해줍니다. 

 let rec reduce f x list =
    if list = [] then x

    else f (List.hd list) ((reduce f x) (List.tl list)) 

즉, reduce는 자기자신의 정의속에 자신을 호출하는 부분이 있는 제귀함수이고, 인자로는 f, x, list를 받으며 list가 빈리스트라면 연산에 영향을 주지않는 값으로 x를 리턴하고, 빈 리스트가 아니라면 head와 나머지리스트에 함수를 f를 적용한 값을 가지고 f를 수행합니다. 위의 메서드를 좀 더 읽기 쉽게하기 위해서 타입을 명시해주면 아래과 같습니다.

let rec reduce (f : 'a -> 'b) (x : 'c) (list : 'd list) =
    if list = [] then x

    else f (List.hd list) ((reduce f x) (List.tl list))

즉, f는 함수이고, x는 제네릭한 값하나, list는 제네릭한 리스트인거죠. 일단, 수행결과를 보고 무슨 소리인지 더 풀어보도록 하죠. 위 두 함수의 정의를 평가해주고나서, reduce add 0 [1;2;3;4] 이렇게 실행을 하면 아래와 같은 결과가 나옵니다. 

val add : int -> int -> int

>

val reduce : ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b 

> reduce add 0 [1;2;3;4];;
val it : int = 10 

리스트의 값을 모두 더해서 10이라는 값이 나왔군요. 이 값이 어떻게 나왔는지 reduce가 정의를 확장하고 줄여나가는 모습을 자세히 적어보면 아래와 같습니다.

 

즉,
add x y = x + y이고
(reduce add 0) [1;2;3;4] 라면..
= add 1 ((reduce add 0) [2;3;4])
= add 1 (add 2 ((reduce add 0) [3;4]))
= add 1 (add 2 (add 3 ((reduce add 0) [4])))
= add 1 (add 2 (add 3 (add 4 ((reduce add 0) []))))
= add 1 (add 2 (add 3 (add 4 0)))
= add 1 (add 2 (add 3 4))
= add 1 (add 2 7)
= add 1 9
= 10

음영으로 강조한 부분이 reduce가 확장되는걸 보기 쉽게 만든 부분입니다. 자신의 정의를 이용해서 빈리스트가 나올때까지 값을 확장하고, 하나씩 줄여가면서 값을 게산해 가는거죠. 사실 add는 이미 F#에 구현되어 있습니다. 아래와 같이 쓸 수도 있습니다. 

reduce (+) 0 [1;2;3;4] 

그리고 람다를 이용해서 아래와 같이 써도 똑같은 결과를 낼 수 있습니다. 

reduce (fun x y -> x + y) 0 [1;2;3;4] 

그리고 reduce를 이용해서 아래와 같은 연산들도 가능합니다. 

reduce (&&) true [true; true; true; false; true] //전부다 true인지 검사하는 함수
let append a b = reduce (fun x y -> List.Cons(x, y)) b a //두 리스트를 붙이는 함수 

그리고 아래는 append의 실행결과입니다.

> append [1;2] [3;4];;

val it : int list = [1; 2; 3; 4] 

List.Cons는 위에서 말씀드렸던 cons의 F#의 List버전입니다. 위 메서드를 확장하고 줄여가나는 모습을 자세히 그려보면 아래와 같습니다.

List.Cons(1, reduce (fun x y -> List.Cons(x, y)) [3;4] [2])

= List.Cons(1, (List.Cons (2, reduce (fun x y -> List.Cons(x, y)) [3;4] [])))

= List.Cons(1, (List.Cons (2, [3;4])))

= List.Cons(1, [2;3;4])

= [1;2;3;4]

 

즉, 리스트에 대해서 특정함수의 수행을 누적시켜서 결과를 얻는(Aggregate) 과정을 쪼개고 그 쪼갠 부분을 붙이는 방법으로 higher-order function을 사용해서 만든 reduce로 이렇게 다양한 연산이 가능한 것입니다. 물론 논문의 저자는 여기서 더 나아가고 있습니다만, 제 실력부족으로 더 이상 나가지 못하는 점 양해바랍니다.-_-;;; 아, 그리고 추가로 말씀드리자면 reduce는 F#에 이미 구현되어 있습니다. reduce가 fold라고 불리기도 한다고 위에서 말씀드렸었죠? 아래와 같이 하면 reduce add 0 [1;2;3;4]와 같은 결과를 낼 수 있습니다. 

List.fold_right (+) [1;2;3;4] 0

List.fold_left (+) 0 [1;2;3;4] 

둘의 차이점은 아래와 같습니다. 

(출처 : http://en.wikipedia.org/wiki/Fold_(higher-order_function))


아래그림은 fold_left이고, 윗그림이 fold_right입니다. 그리고
각각 그림의 왼쪽은 리스트이고, 오른쪽은 어떻게 펼치느냐에 대한 도식입니다. 즉, 왼쪽으로 펼쳐서 접느냐, 오른쪽으로 펼쳐서 접느냐에 따라 틀린거지요. 위에서 구현된 reduce는 fold_right라고 보시면 됩니다.

 

- 마치면서

사실, 진정한 함수형언어의 강점과 F#의 강점은 아직 맛도 못봤습니다. 이거 빨리 제가 맛을 보고 잘 전해드려야 할텐데;; 개인적인 사정이 점점 안좋아지는군요-_-. Anders hejlsberg의 인터뷰에서 발췌한 글을 끝으로 남기면서 글을 마치겠습니다.(왜 Anders hejlsberg이야기가 많이 나오냐면, 전  Anders hejlsberg빠돌이거든요-_-;) 이 글을 읽다보니, 왜 함수형언어의 힘을 빌린 LINQ를 추가해서 데이터를 다루는 부분을 추상화 했는지 확 다가오는 군요. 그리고 앤더스가 선언형 언어와 함수형언어의 장점을 점점 더 중요하게 생각하고 있다는 생각이 듭니다.(물론, 원문을 읽어보시면 더 자세한 내용을 보실수 있겠져~.) 그리고 언제나 그렇듯이 제 맘대로 번역-_-.

 

I think one of the things that are true of most programming languages today is that they force you to overspecify the solution to your problem. You're down there writing nested for loops and if statements and whatever, and really all you wanted to do was a join between two pieces of data. But there's nothing that allows you to say that. You have to get down and dirty and do hash tables and dictionaries, blah, blah, blah.

난 요즘 대부분의 프로그래밍언어가 프로그래머에게 문제를 해결하기 위한 솔루션을 너무 필요이상으로 서술하게 만든다고 생각합니다. 물론 사실이구요. 프로그래머는 그저 두 데이터집합을 조인하고 싶을 뿐인데, for루프랑 if문을 여러개 중첩시키고 어쩌고 저쩌고 해야만 하는거죠. 즉, 그냥 조인하게 해달라고만 말할 수 있는게 없다는 겁니다. 진흙탕으로 내려가서 해시테이블이랑 딕셔너리랑 기타등등, 뭐 그런것들이랑 열심히 뒹굴어야 하는거죠.



-참고자료

1. Expert F#, Don Syme, Adam Granicz, Antonio Cisternino, APRESS
2. Programming Language Pragmatics 2nd Edition, Michael L. Scott, Morgan Kaufmann Publishers
3. Structure and Interpretation of Computer Programs, 2nd Edition, Harold Abelson, Gerald Jay Sussman, Julie Sussman, The MIT Press
4. 구글을 지탱하는 기술, 니시다 케이스케, 멘토르
5. http://en.wikipedia.org/wiki/Fold_(higher-order_function)
6. http://broadcast.oreilly.com/2009/04/an-interview-with-anders-hejls-1.html
7. http://en.wikipedia.org/wiki/Miranda_(programming_language
8. http://www.math.chalmers.se/~rjmh/Papers/whyfp.pdf