여기서는 함수형 프로그래밍의 특징을 알아보기 위해 프로젝트 오일러(Project Euler) 2번 문제를 푸는 과정을 이용해서 설명하려 한다. 여기서 살펴볼 함수형 프로그래밍의 특징은 크게 두가지[1].

  • 지연-시퀀스 (Lazy-sequence)
  • 함수형 프로그래밍의 데이터 흐름

이 때 사용할 함수형 언어는 Clojure(클로저)다. 가급적 Clojure라는 언어를 모른 상태에서도 글을 알 수 있도록 쓰........고 싶었으나, 그렇게 되면 너무 많은 설명이 필요하기 때문에 자세한 설명은 포기하도록 하였다. 대신, 잘 모르더라도 대략적으로 저 두 특징이 어떤 역할을 하는지에 대해 설명하는데에 초점을 맞추고, 결과적으로 이러한 특징이 프로그래밍의 흐름을 어떻게 변화시키는지 간단히 소개하는데 글의 목적을 둔다.

프로젝트 오일러 (Project Euler) 문제 2번

프로젝트 오일러는 수학과 프로그래밍 문제들을 올려놓고 사람들이 맞추는 형태의 웹사이트다[2]. 고급 수학 능력이 있다면 손으로 푸는 것도 가능한데, 보통은 컴퓨터를 이용해서 풀이한다.

그중 2번 문제는 다음과 같다.

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

피보나치 수열의 각 항 들은 2개의 이전 항들을 더함으로써 만들어진다. 첫 두항을 1, 2 로 두었을 때 처음 10개의 항들은 다음과 같다:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

피보나치 수열에서 4백만이 넘지 않은 항들 중에 짝수인 항들의 합을 찾아라.

절차형(procedural) 프로그래밍 방법으로 짜는건 별로 어렵지 않다. 루프 하나 돌려서 피보나치 수열을 구하면고 동시에 바로 비교하고 조건에 맞으면 합계에 더하면 간단하게 풀 수 있다.

함수형 프로그래밍에서는 조금 다르게 풀게 된다. 절차형 프로그래밍 방식대로도 풀 수는 있지만, 오히려 복잡하고 함수형 프로그래밍의 장점을 얻어오지 못한셈이 된다(예를 들자면 가위로 못 박는 느낌?).

절차적 프로그래밍과 함수형 프로그래밍

함수형 프로그래밍에서 위의 문제를 푸는 경우 대부분 이런식이 된다.

어떤 입력을 문제를 풀어주는 함수에 입력으로 넣고 원하는 결과를 얻는다.

-_-ㅋ 당연한 말을 했다. 그런데 절차형 프로그래밍에서는 보통 이 함수 내에서 피보나치 수열을 만들고 거기서 모든 처리를 동시에 같이 처리한다. 즉, 입력을 넣기보다는 입력 데이터를 만들면서 푼다는점이 특징이다. 반면 함수형 프로그래밍 기준으로는 위의 말을 좀 더 바꿔보면 이렇다.

함수에 피보나치 수열을 입력으로 넣고 원하는 결과를 얻는다.

이것이 함수형 프로그래밍에서는 보다 이치에 맞는 접근이다. 여기서 항의 값이 4,000,000 이하라는 조건과 짝수라는 조건이 있다. 그 조건을 넣어 위의 함수를 쪼개보자.

  1. 피보나치 수열을 생성한다.
  2. 그 중 4,000,000 이하인 항들만 남긴다.
  3. 그 중 짝 수인 항들만 남긴다.
  4. 남은 항들을 모두 더한다.

함수형 프로그래밍에서는 위의 1~4의 처리 과정 하나하나가 모두 별도의 함수 호출로 이루어진다.

반면 절차적 프로그래밍에서는 이 과정이 보통은 하나로 통합되어있어서, 이 과정을 말로 표현하면 이렇게 된다.

피보나치 수열의 값이 4,000,000 이상이 되지 않을 만큼 생성하되, 그 중 짝수인 항을 골라내서 결과에 더한다.

이 경우 처리가 세분화 되어 구분되지 않고 동시에 얽혀서 이루어진다(다른 말로 하면 하나의 루프 안에서 모든게 처리 된다는 말이다). 함수형 프로그래밍에서는 좀 더 데이터에 직관적으로 함수를 쪼개서 생각 할 수 있는 것과 대조되는 부분이다.

1. 피보나치 수열 생성

피보나치 수열을 만드는 함수는 다음과 같다.


> (defn fibo []
    (map first (iterate (fn [[a b]] [b (+ a b)]) [1 2])))
 

이것은 크리스토프 그랑(Christophe Grand)이 만든 함수로 Clojure에서 피보나치 수열을 가장 간단하게 만들 수 있는 방법 중 하나이다. 좀 어려워 보일 수 있기 때문에 좀 더 쉬운 형태로 소개하겠다.


> (defn fibo
    ([]
        (concat [1 2] (fib 1 2)))
    ([a b]
        (let [n (+ a b)]
              (lazy-seq
                (cons n (fibo b n))))))
 

더 쉬운 코드를 적어둔다 말했지만, 자세한 코드 설명은 하지 않겠다(-ㅅ-;;). 위 함수를 정의해놓고(위 코드는 함수를 정의하는 코드다), 이 함수를 호출하면?


> (fibo)
 

컴퓨터는 무한 루프에 빠진다. 왜냐하면 이 함수는 모든 피보나치 함수를 구하는 코드이기 때문이다.

초반 10개의 수열만 얻으려면 다음과 같이 하면 된다 (fibo 함수는 더이상 변경하지 않는다).


> (take 10 (fibo))
(1 2 3 5 8 13 21 34 55 89)
 

이런 과정은 기존 절차형 언어만 접한 사람들에게는 매우 신기한 형태의 사용법이다. fibo 함수를 변경하지 않고(게다가 함수에 몇개의 데이터만을 얻으려 한다는 입력도 없이) 위와 같은 사용으로 10개의 데이터만 취할(take) 수 있다.

이런 특징은 지연성(laziness)이라 부르고, 여기서 (fibo) 로 만들어지는 (1 2 3 5 …. )의 시퀀스는 지연 시퀀스(lazy sequence)라고 부른다. 지연 시퀀스의 데이터는 호출 즉시 모두 만들어지는 것이 아니라 각 데이터를 필요로 할 때 만들어진다[3].

take 함수는 마찬가지로 지연 평가(lazy evaluation)의 특징을 지닌다. 두번째 인자의 데이터(fibo)를 그 즉시 평가하지 않고(그 즉시 평가를 하려 한다면 무한 루프에 빠지게 된다) 필요한 10개의 데이터만을 평가(계산)하여 시퀀스로 만들어준다.

2. 4,000,000 이하인 항들만 남김

이제 2번의 함수를 만들 차례다. 4000000 이하의 데이터만을 만들어주는 2번의 함수는 다음과 같이 만들 수 있다.


> (take-while
    (partial > 4000000)
     (fibo))
(1 2 3 5(지면상 생략)3524578)
 

코드 설명은 생략하는데, 피보나치 수열의 항이 4000000 초과가 되기 전까지의 수열을 취하는 코드다[4].

3. 짝수만 남기기

이제 짝수만을 걸러내야한다. filter 함수와 even? 함수로 간단하게 걸러 낼 수 있다.


> (filter
    even?
    (take-while (partial > 4000000) (fibo)))
(2 8 34(지면상 생략)3524578)
 

시퀀스의 각 항들을 even? 함수에 넣어보고 true이면 남기기는 것이다.

4. 남은 데이터 모두 더하기

남은 데이터를 더하는 것은 reduce 함수로 아주 간단하게 가능하다. reduce 함수는 첫번째 인자로 함수를 받고 이 함수를 두번째 받은 시퀀스의 각 항들에 적용해서 결과를 얻는 것이다.


> (reduce + ‘(1 2 3 4))
10
 

이 과정은 1 + 2 -> 3 + 3 -> 6 + 4 의 과정을 통해서 10이라는 결과를 만들어준다.

따라서 마지막 호출할 함수는 깊게 생각할 필요도 없이 간단하게 만들어진다.


> (reduce +
    (filter even?
             (take-while (partial > 4000000) (fibo))))
4613732
 

결론

이전에 언급하였듯이 가장 크게 확인할 수 있는 내용은 절차형 프로그래밍에서는 모든 처리가 하나의 루프 안에서 맞물려 돌아가는 반면, 함수형 프로그래밍에서는 그것을 4가지 별도의 처리로 나누어 생각할 수 있다. 그 안에 지연(lazy) 처리가 핵심적으로 중요하게 숨어있기도 하다.

당연한 말이지만, 이 때 뭐가 더 좋고 나쁜건 없다. 현재 이 문제를 푸는데 있어서 함수형 언어가 이러이러한 장점이 있긴 하지만 그만큼 단점도 존재한다.

어쨌건 장점은 이렇다. 1. 문제를 더 쪼개서 생각할 수 있다. 2. 따라서 재사용성이 더 쉬워진다(C/C++코드에서는 일반적으로 이런 코드를 부분적으로 재사용하기 쉽지 않다). 중요한건 함수형 프로그래밍의 과정이 기존 절차적 프로그래밍과 이런식으로 다르게 흘러간다는 점이다. 단순히 함수 자체를 데이터로 여긴 후 처리하는 것 이상으로 프로그래밍의 패러다임이 다르다는 것을 인지하면 좋을 것 같다.

참고 자료 & 외부 링크



  1. 여기에 더해 불변성(immutable)의 특성도 지니고 있지만, 크게 두러지지 않아서 설명은 생략한다. 말하자면, 절차형 프로그래밍에서는 처리의 초반에 int sum = 0;의 변수를 만들고 이 변수를 계속 변경하며 처리가 진행되지만, 불변성을 지닌 처리에서는 이런 변수의 사용이 없다. [본문으로]
  2. 비슷한 걸로 Programming Challenges가 있는데, 이쪽은 서비스를 종료 했는데 현재 접속이 안된다. 아무튼 여기는 소스를 올려서 수행 시간까지 체크하는 반면, 프로젝트 오일러는 정답만 입력하는 형태다. [본문으로]
  3. 이때 사용되는 시퀀스라는 용어는 간편하게 배열(array) 혹은 링크드 리스트(linked list)라고 생각하면 편하다. Clojure의 기본 데이터 구조라고 보면 된다 [본문으로]
  4. 참고로 (partial > 4000000) 는 #(> 4000000 %1)의 람다 함수로 대치 될 수 있다. C++11에도 있는 람다 함수의 특징을 이용해서 시쿼스를 만들어내는 조건을 전달한다고 보면 된다. [본문으로]
크리에이티브 커먼즈 라이센스
Creative Commons License
2012/10/18 11:26 2012/10/18 11:26

트랙백 주소 :: 이 글에는 트랙백을 보낼 수 없습니다

  1. Subject:

    Tracked from GS test dem 2013/04/02 22:22  삭제

    Hybrid :: 함수형 프로그래밍에서의 패러다임 변화

  2. Subject: billig lån - laanpengenu.info

    Tracked from billig lån - laanpengenu.info 2013/04/24 13:38  삭제

    Hybrid

  3. Subject: Casino Online Review

    Tracked from Casino Online Review 2013/04/26 19:03  삭제

    Hybrid

  4. Subject: 2013 at 5:56 am

    Tracked from 2013 at 5:56 am 2013/04/30 22:29  삭제

    Hybrid

  5. Subject: casino spil

    Tracked from casino spil 2013/05/08 15:29  삭제

    Hybrid

  6. Subject: Vind ipad 3

    Tracked from Vind ipad 3 2013/05/09 03:35  삭제

    Hybrid

  7. Subject: http://laanpengenu.info

    Tracked from http://laanpengenu.info 2013/05/09 04:08  삭제

    Hybrid

  8. Subject: casinoonlinespiele911.de

    Tracked from casinoonlinespiele911.de 2013/05/09 06:34  삭제

    Hybrid

댓글을 달아 주세요