함수형 프로그래밍은 최대한 순수 함수를 많이 추출할 수 있는 것이 무엇보다 중요하다

그렇기 위해서는 최대한 변수에 의존하지 않는 것이 중요하고 그를 위해서 일반적인 루프보다는

재귀호출을 이용해야 한다. 그렇다면 일반적인 자료구조는 어떻게 표현할 것인가? 값을 바꾸는 개념이

없다면 어떻게 알고리즘을 표현 할 것인가?


소팅을 예로 들어보자. 기존의 명령형 프로그래밍에서 소팅을 한다는 것은 어떤 배열같은 자료구조를

대상으로 작업을 수행하여 그 자료구조의 상태를 바꾸어 놓는 것이 일반적이다. 하지만 함수형

프로그래밍에서는 데이타의 상태를 변화시키는 것을 피한다. 그럼 어떻게 한단 말인가?


그 답은 어떤자료를 입력받아 상태를 바꾸는 함수를 만드는 대신 바뀐 새로운 자료구조를 생성해내는

함수를 만드는 것이다. 즉, 변경 대신 생성을 하는 방식으로 프로그램을 짜는 것이다! 이 시점에서

정통 C 프로그래머들은 아마 인내심이 바닥나는 느낌이 밀려올지도 모르겠다


    뭐라고? 무슨일을 하건 항상 자료구조를 생성해낸다고?
    도대체 이 바닥 인간들은 효율성에 대한 개념이 있기는 한건가?


물론 방법이 있으니 하는 것이다. 그렇지만 그 방법은 명령형 언어에서의 습관과는 많이 다르다.

그래서 함수형 프로그래밍을 배우는 것은 지속적인 생각의 관성과의 싸움이다.


기본적으로 함수형 언어에서 사용하는 자료구조는 immutable 이다. immutable 하다는 것은 일단 한번

생겨난 다음에는 그 내부를 뜯어고치는 것은 불가능하며, 대신 함수에 인자로 넣어서 새로운 자료구조를

받는 것은 가능하다. 사실 이런 개념이 명령형 프로그래밍에서 아주 드문 것은 아니다. 예를 들어 java 의

String 은 immutable 이다. 한번 string 을 정의해 놓으면 그 중간의 한글자만 바꾼다던가 하는 것은

허용되지 않는다. string 의 전체 내용을 대문자로 바꾼다던가하는 함수가 존재하지만, 새로운 string 을

리턴하는 함수지, 스트링의 레퍼런스나 포인터를 받아서 받은 스트링을 고치는 것은 안된다. 이렇게 한

이유는 효율때문이다. 심볼이라는 타입이 별도로 존재하지 않는 환경에서는 스트링을 이용해서 심볼로

사용하기 때문에 스트링 끼리의 비교를 할 일이 매우 많다. 특히 map 의 인덱스를 string 으로 한다던가

하면 많은 스트링간 비교를 해야 하는데, string 을 immutable 하다라고 하면, string 이 생성되는 시점에

hash code 나 기타 그 string 의 내용에 대한 identity 를 정해서 쭉 유지시킬 수 있으므로 스트링을 비교

하는 대신 hash code 를 비교하면 되는 것이다.


그렇다면, 데이타구조를 immutable 하게 제한함으로써 생기는 효율의 문제는 어떻게 할 것인가?

- 매번 함수를 거칠때마다 계속 새로운 데이타구조가 생겨나므로 공간이 낭비되는 문제
- 자료구조의 일부만 바뀌는 경우 매번 새로운 데이타를 만들면서 카피를 해야 하는 문제


먼저, 메모리를 계속 새로 만드는 것으로 인해 메모리 공간이 낭비되는 문제는 garbage collector 가

해결한다. 기존의 자료구조를 함수에 넘어서 새로운 자료구조를 만들고 나면 새로운 자료는 그 후의

코드가 참조하겠지만 기존의 자료구조는 더 이상 참조하는 곳이 없어지는 시점에서 자동으로 제거 된다.

사실 가베지 컬렉터는 함수형 프로그래밍과는 뗄래야 뗄 수가 없는 관계이다. 옛날에 리스프같은

환경이 만들어지면서부터 지금까지 그래왔고 아패로도 가속...


그렇다면 뭔가를 할 때마다 계속 새로운 멤버를 카피해야만 하는 오버헤드는 어떻게 처리할 것인가?

그에 대한 답은 바로 리스트, 더 정확히 표현하자면 싱글 링크드 리스트이다. 처음에 리스프같은 같은

언어를 배우게 되면 car cdr cons 같은 것부터 계속 배우게 된다 이게 다 무슨 소용이란 말인가

싶겠지만 실은 위에서 설명한 요소들을 해결할 수 있는 가장 효율적인 방법이다.


예를 들어 (1 2 3) 이라는 리스트를 만들었다고 하자. 어떤 함수가 이 리스트를 받아서 맨 앞의 원소를

1 에서 5 로 바꾸게 되었다고 해보자. 즉 (5 2 3) 이라는 결과를 리턴하는 함수가 된다.

그 과정을 lisp code 로 쓰면

(setf x (list 1 2 3))             ;; x = (1 2 3)
=> (1 2 3)
(setf y (cons 5 (cdr x)))    ;; y = (5 2 3)
=> (5 2 3)

y 의 2 3 은 x 에 있는 2 와 3 을 그대로 이용한 것이다. 즉 맨 앞의 cons cell 만 하나 만들어서 5 를 넣은

다음, 그 후는 x 에 있던 2 3 쪽으로 연결을 시킨 것이다. 이런 식으로 링크의 node 를 새로 만들어서

다른 리스트의 앞부분(car)이나 중간부분 (cdr, 혹은 cdr 의 cdr) 에 연결시키는 식으로 기존에 있는

데이타를 엎어쓰지 않으면서 copy 를 최소화시키면서 새로운 자료구조를 만들어낼 수 있다.


여기서 눈여겨봐야 할 것은 위의 코드를 멀티스레드용으로 사용하게 된다고 해도 lock 을 걸 필요가

없다는 점이다. 기존의 값을 바꿀 일이 없고 값을 새로 만들기만 하니까 당연한 일이다.

또한, 위의 코드를 보면 y 가 생성된다고 해도 x 는 여전히 유효한 값으로 남아있게 된다. 나중에 x 가

scope 바깥으로 나간다던가 해서 삭제된다고 해도 y 가 참조하고 있는 x 의 2 3 은 여전히 유효한데

그 이유는 각 cons cell 들은 garbage collector 가 알아서 처리하기 때문이다.


다음 시간에는 immutable 한 특성과 STM 간의 관계, 특히 clojure 의 identity 와 state 에 대한 접근에

대해 알아보도록 하자.

imcgames 의 김학규입니다