이하의 글은 2012년에 쓴 것입니다. 오래된 글인 만큼, 현재의 생각과 전혀 다른 내용도 많이 포함되어 있고, 당시와는 상황이 많이 달라진 점도 있습니다. 또한, 그 당시에 잘못 알려졌던 정보도 포함되어 있을 수 있습니다. 어찌됐든 저는 제 오래된 글이 회자되는 것을 저어합니다. 읽기에 앞서 양해를 부탁드립니다.

Purely Functional Data Structures

여기저기서 말하고 다니고 있지만, 내 이상에 가장 가까운 언어는 Clojure다. 요즘 함수형 프로그래밍이라는 말이 거의 버즈워드처럼 쓰이고 있는 가운데, 진지하게 현대적인 함수형 프로그래밍 언어를 만든다면 어떤 것들이 필요한지 몸소 보여주고 있기 때문이다.

Clojure의 훌륭한 점은 여러가지가 있지만 그 중 하나가 매우 뛰어난 자료 구조이다. 디자인과 구현 모두 좋은데, 함수형 프로그래밍을 위한 자료 구조가 어떻게 구현되어야 하는지 Clojure를 보면 알 수 있다.

예를 들어 함수형 프로그래밍 언어에서는 자료 구조가 죄다 불변(immutable)이고, 어떤 종류의 연산도 새로운 객체를 만들어내게 되어 있다. 하지만 계산 위주의 프로그램을 짜보면 보통 메모리 복사를 얼마나 적게 발생시키냐가 성능 향상의 중요한 이슈가 된다.

과학 프로그래밍에서 주로 쓰이는 다차원 배열/행렬 라이브러리들이 어떤 식으로 돌아가는지를 보면 쉽게 짐작할 수 있다. 2차원 배열이 둘 있고, 두 행렬의 합을 구한 다음, 그 결과의 첫번째 열을 가져온다고 가정해보자. 무식하게 짜면 두 행렬의 합을 구할 때 메모리 복사가 일어나게 된다. 그래서 대부분은 행렬 연산 자체는 논리적으로는 객체지만 실제로는 뷰(view)로 구현되어 있는 가상의 자료 구조를 반환하게 하고, 실제로 특정 부분을 구할 때 실체화(realization)시키도록 구현한다.

Clojure는 문자열에 대해서는 어쩔 수 없이 java.lang.String을 그대로 쓰지만, Fortress 같은 언어의 경우에는 문자열 구현이 로프(rope)로 되어 있기도 하다. (모르는 사람들도 꽤 많은데 SGI의 STL 구현에는 로프 구현체인 std::rope가 포함되어 있다. 실제로 쓰는 경우를 본 적은 없지만.)

Clojure의 다양한 자료 구조들이 이런 식으로 구현이 되어 있는데, 실제로 함수형 프로그래밍을 하려면 이런 자료 구조가 필요하고, 이런 구현이 필수적으로 된다. 물론 JavaScript나 Java에서 함수형 프로그래밍 스타일을 따를 수는 있지만 메모리 복사가 무지막지하게 일어나게 되서 결국에는 무시 못할 비용을 치루게 된다. 진지한 함수형 프로그래밍을 하려면 이를 위한 진지한 자료 구조도 뒷받침되어야 하는 것이다. (다 당연한 얘기들인데 이런 소리를 왜 하고 있지…)

이번에 올라온 PEP 416가 frozendict를 제안하고 있어서 해당 링크를 r/Python 서브레딧에 올렸더니 Clojure 자료 구조를 언급하는 댓글이 달려서, 이에 관해 LangDev에서 서상현 씨와 얘기를 하다가 서상현 씨가 Purely Functional Data Structures라는 책이 이미 있고 함수형 자료 구조를 구현하려면 이 책을 정독하면 된다고 알려주셨다. 찾아보니까 Google 검색 맨 위에 아예 PDF가 걸려 있어서 냉큼 링크.