Clojure의 영속 자료구조를 Fennel 위에 구현하기 — 함수형 프로그래밍의 핵심 개념 파헤치기

무슨 이야기인가요?

프로그래밍 언어의 세계에는 재미있는 실험들이 끊이지 않는데요, 이번에 소개할 프로젝트는 Clojure의 핵심 자료구조를 Fennel이라는 언어 위에 구현하는 시리즈의 첫 번째 글이에요. "그게 뭔 소리야?" 싶을 수 있으니 하나씩 풀어볼게요.

먼저 Clojure는 JVM(자바 가상 머신) 위에서 돌아가는 함수형 프로그래밍 언어예요. Lisp 계열 언어인데, 특히 불변(immutable) 자료구조를 기본으로 제공한다는 게 큰 특징이에요. 그리고 Fennel은 Lua 위에서 돌아가는 또 다른 Lisp 계열 언어예요. Lua의 가볍고 빠른 런타임을 그대로 쓰면서 Lisp 스타일의 문법을 사용할 수 있는 언어죠.

이 프로젝트의 저자는 Clojure의 강력한 자료구조를 Fennel(그리고 그 아래의 Lua) 환경에서도 쓸 수 있게 만들겠다는 목표를 가지고 있어요. 첫 번째 파트에서는 그중 가장 핵심인 영속 자료구조(Persistent Data Structures)를 다루고 있어요.

영속 자료구조란 뭔가요?

영속 자료구조라는 이름이 좀 어렵게 들리는데, 개념 자체는 간단해요. 보통 프로그래밍에서 배열이나 맵(딕셔너리)에 데이터를 추가하면 원본이 바뀌잖아요? 영속 자료구조는 원본을 절대 바꾸지 않고, 변경사항이 반영된 새로운 버전을 만들어내는 자료구조예요.

비유하자면 Google Docs의 버전 히스토리와 비슷해요. 문서를 수정해도 이전 버전이 사라지지 않고, 언제든 과거 버전으로 돌아갈 수 있죠. 영속 자료구조도 마찬가지로, 데이터를 "수정"하면 이전 버전과 새 버전이 동시에 존재하게 돼요.

"그럼 매번 전체를 복사하면 메모리 낭비 아니야?"라고 생각할 수 있는데, 여기서 Clojure가 사용하는 핵심 트릭이 나와요. 바로 구조적 공유(Structural Sharing)라는 기법이에요.

구조적 공유의 마법

구조적 공유를 이해하려면 트리 구조를 떠올려보면 돼요. Clojure의 벡터(Vector)는 내부적으로 넓은 트리(wide tree), 정확히는 32-way 분기 트리로 구현되어 있어요. 각 노드가 최대 32개의 자식을 가지는 트리인데요, 데이터를 하나 변경하면 그 데이터가 포함된 경로의 노드들만 새로 만들고, 나머지 노드들은 이전 버전과 공유해요.

예를 들어 100만 개의 요소가 있는 벡터에서 하나의 요소를 바꾼다고 해볼게요. 전체를 복사하면 100만 개를 다 복사해야 하지만, 구조적 공유를 사용하면 변경된 경로에 해당하는 노드 몇 개(32-way 트리에서 깊이가 약 4 정도)만 새로 만들면 돼요. 나머지 99.99%는 기존 트리를 그대로 가리키고 있으면 되는 거죠. 이 덕분에 변경 연산이 사실상 O(log₃₂ n), 즉 거의 O(1)에 가까운 성능을 보여요.

이 글의 저자는 이 구조를 Fennel(Lua) 위에 구현하면서, Clojure가 내부적으로 사용하는 HAMT(Hash Array Mapped Trie)라는 자료구조를 상세히 설명해요. HAMT는 해시맵의 영속 버전이라고 보면 되는데요, 키의 해시값을 비트 단위로 쪼개서 트리의 경로를 결정하는 방식이에요.

왜 이런 자료구조가 중요한가요?

영속 자료구조가 단순히 "멋있어서" 쓰는 게 아니에요. 실용적인 이점이 꽤 많거든요.

첫째, 동시성(concurrency) 문제가 크게 줄어들어요. 데이터가 불변이면 여러 스레드에서 동시에 읽어도 안전하거든요. 락(lock)을 걸 필요가 없어요. 멀티코어 시대에 이건 엄청난 장점이에요.

둘째, 되돌리기(undo) 기능 구현이 공짜예요. 이전 버전이 자동으로 보존되니까, 에디터의 Ctrl+Z 같은 기능을 구현하려면 그냥 이전 버전의 참조를 들고 있으면 끝이에요. React에서 상태 관리할 때 시간 여행 디버깅(time-travel debugging)이 가능한 것도 같은 원리예요.

셋째, 비교가 빠르아요. 두 버전의 자료구조가 구조적으로 공유되어 있으면, 루트 노드의 참조만 비교해도 전체가 같은지 다른지 O(1)에 알 수 있어요. React의 Virtual DOM 비교에서도 이런 아이디어가 활용돼요.

업계 맥락 — 영속 자료구조의 확산

Clojure에서 시작된 이 아이디어는 이미 다른 생태계에도 많이 퍼져 있어요. JavaScript에서는 Immutable.js(Meta에서 만든)가 대표적이었고, 지금은 Immer라는 라이브러리가 더 많이 쓰여요. Immer는 "겉보기에는 데이터를 직접 수정하는 것 같지만, 내부적으로는 영속 자료구조처럼 동작"하게 해주는 프록시 기반 라이브러리예요. Redux Toolkit에서 기본으로 사용하고 있죠.

Rust에서는 im 크레이트가 영속 자료구조를 제공하고, Scala에서는 언어 표준 라이브러리에 포함되어 있어요. 이번 프로젝트처럼 Lua 생태계에 가져오려는 시도는 이 개념이 특정 언어에 국한되지 않는 범용적인 가치를 가진다는 걸 보여줘요.

한국 개발자에게 주는 시사점

"함수형 프로그래밍은 실무에서 안 쓰잖아"라고 생각할 수 있는데, 사실 영속 자료구조의 아이디어는 이미 여러분의 코드에 들어와 있을 가능성이 높아요. React의 상태 관리에서 "상태를 직접 변경하지 마세요"라고 하는 그 규칙이 바로 불변성의 원칙이고, 이걸 효율적으로 가능하게 하는 게 영속 자료구조거든요.

이 글을 통해 "왜 불변성이 중요한지", "불변인데 어떻게 성능이 좋을 수 있는지"에 대한 근본적인 이해를 쌓아두면, React뿐 아니라 어떤 프레임워크를 쓰든 더 나은 설계 결정을 내릴 수 있을 거예요.

직접 영속 자료구조를 구현해볼 필요까지는 없겠지만, HAMT나 구조적 공유 같은 개념을 알아두면 면접에서도, 시스템 설계에서도 도움이 돼요.