1+1을 계산하려다 함수형 프로그래밍 언어를 만들었습니다

AI 요약

이진 트리로 1+1+1을 계산하는 자료구조 과제를 받은 글쓴이는 식 평가기를 만들기 시작합니다. 연산마다 Add, Sub, Mul, Div를 구분하는 대신, 평가기가 함수의 내부 동작을 알 필요 없이 인자를 적용하기만 하면 된다고 보고 식을 Func Expr Expr 또는 값으로 표현합니다. 변수와 함수도 환경 테이블에서 이름을 찾아 값으로 다루도록 확장하면서, 작은 과제는 C로 함수형 언어를 구현하는 작업으로 커집니다.

식 트리에서 함수와 클로저로

초기 구현은 리터럴, 변수, 함수를 태그가 붙은 공용체(tagged union) 노드로 나타냅니다. 64비트 시스템에서 노드 하나는 포인터 두 개와 데이터, 타입 태그, 패딩을 합쳐 32바이트입니다. 글쓴이가 사용한 malloc()은 노드마다 메타데이터 16바이트를 더해, 노드 하나에 약 48바이트를 씁니다. 1+1만 계산해도 노드 세 개가 필요해 할당량은 144바이트가 됩니다. 작은 노드를 자주 할당하는 방식은 부담이 크다고 판단해 직접 메모리 할당기를 만듭니다.

변수와 함수를 같은 환경 테이블에 저장하면서, 함수도 값으로 취급합니다. C 함수 포인터만으로는 사용자가 언어 안에서 정의한 함수를 표현하기 어렵습니다. 함수가 다른 함수를 반환할 때도 실행할 코드를 평가기가 다시 따라가야 합니다. 그래서 함수 본문을 노드 트리로 담는 클로저(closure)를 도입합니다. 클로저를 그래프 안의 노드로 표현하면 사용자가 함수를 정의하고, 전달하고, 반환하는 구조를 만들 수 있습니다. 글에서는 클로저에 환경도 필요하지만 아직 지역 변수를 다루기 전이라 설명을 미뤘다고 덧붙입니다.

고정 크기 아레나에서 청크 할당기로

처음에는 고정 크기 배열을 쓰는 아레나 할당기를 구현합니다. 하지만 재귀적인 피보나치 함수 fib(5)를 실행하자 약 1만 3천 개 노드가 생겨 1,024개짜리 아레나를 넘어서 프로그램이 충돌합니다. 배열을 realloc()으로 키우면 메모리 블록이 다른 주소로 옮겨질 때 노드 사이 포인터가 깨질 수 있습니다. 글쓴이는 기존 데이터를 옮기지 않는 방식으로 방향을 바꿉니다. 노드를 담은 청크를 새로 할당하고, 청크끼리 연결하는 청크 할당기(chunk allocator)를 만듭니다.

이제 fib(5)는 정상 실행되지만 메모리 사용량은 1.32MB입니다. fib(10)은 40MB를 쓰고, fib(40)은 메모리 부족으로 종료되기 전에 12GB를 넘깁니다. 글쓴이의 설명에 따르면 fib(40)은 약 13억 개 노드를 만들며, 노드당 48바이트로 계산하면 전체 할당량은 약 62.4GB입니다. 문제는 계산이 끝난 노드도 메모리에 남아 있다는 점입니다.

마크-앤드-스윕으로 노드 재사용

그래프 평가기는 식을 계산하면서 노드를 값으로 바꾸고, 값으로 바뀐 노드의 자식은 더 이상 그 노드에서 도달할 수 없게 됩니다. 하지만 할당기에는 옛 노드가 그대로 남습니다. 글쓴이는 루트에서 도달 가능한 노드에 표시를 남긴 뒤, 청크를 훑어 표시되지 않은 노드를 자유 목록(free list)에 넣는 마크-앤드-스윕(mark-and-sweep) 가비지 컬렉터를 구현합니다. 새 노드가 필요하면 자유 목록의 노드를 재사용하고, 목록이 비었을 때만 청크에서 공간을 할당합니다.

가비지 컬렉터를 적용한 뒤 fib(40)의 메모리 사용량은 1.7MB로 줄어듭니다. 다만 실행 시간은 6분입니다. 글쓴이는 현재 수집기가 프로그램 실행을 멈추는 stop-the-world 방식이며, 재귀 피보나치 알고리즘 자체도 지수적으로 느리다고 설명합니다. 이후 글에서 꼬리 호출 최적화(TCO)와 평가 방식 개선으로 속도를 다루고, 렉서와 파서, FFI, REPL, 람다 함수, 지역 변수, Cheney 복사 수집기를 구현할 계획이라고 예고합니다.

구현하며 정리한 구조

이 글에서 만든 것은 평가기가 연산자 종류를 직접 구분하는 인터프리터가 아니라, 함수 적용과 노드 그래프 축약으로 식을 계산하는 그래프 환원 엔진(graph reduction engine)입니다. 글쓴이는 대수적 자료형(Algebraic Data Type) 관점에서 식을 다시 생각하고, 변수와 함수도 환경에 저장되는 데이터로 통합합니다. 여기에 사용자 정의 클로저, 해시 테이블, 청크 할당기, 마크-앤드-스윕 수집기를 차례로 붙입니다. 시작은 1+1 계산이었고, 마지막에는 자신이 만든 언어 graphLang으로 실제 1+1이 2라고 확인합니다.

Hacker News 반응

• @gnarlouse — 수십 년 전 이야기 같네요. 잠깐, 저는 3년 전에도 이런 식으로 코드를 짜고 있었네요.
• @ancientstraits — 해시 테이블 구현 글이 정말 도움이 됐습니다. C에서 해시 테이블을 만드는 건 사실상 불가능하다고 생각했는데, 그 글을 보니 더 간단하더라고요.
  • @dprkh — 배열은 해시 테이블입니다. 아주 단순한 해시 테이블은 튜토리얼을 보고 만들 수 있죠. 하지만 정교한 해시 테이블은요? 동시성 해시 테이블은요?
  • @saghm — 대학 1학년 2학기 C 수업에서 해시 테이블을 만들었던 것 같습니다. 연결 리스트를 만들고, 그 리스트를 담는 배열과 키를 배열 인덱스로 바꾸는 함수를 만들면 해시 테이블이 됩니다. 실제 성능이 좋은지는 별개지만, 단순한 해시 테이블도 해시 테이블입니다.
  • @raddan — 해시 테이블은 단순한 자료구조이면서도 깊게 파고들 여지가 많아서 좋습니다. 복잡성은 충돌 처리에서 많이 생깁니다. 충돌을 어떻게 다루느냐에 따라 해시 테이블 종류가 달라집니다. 충돌 처리 방식은 수십 가지가 넘습니다. 학부 수업에서 구현했을 법한 가장 단순한 방식은 개방 주소법(open addressing)입니다. 충돌 처리는 점근적 비용을 줄이거나, 조회 때 메모리 지역성을 높여 캐시를 더 잘 활용하도록 설계할 수도 있습니다. 글은 대충 훑었지만, 저자가 스코프 규칙을 고려했는지는 궁금합니다. “scope”라는 단어를 찾아봤지만 나오지 않았습니다. 클로저는 언어 설계를 복잡하게 만듭니다. 어휘적 스코프(lexical scope)를 쓰지 않으면 동작이 고통스럽고 직관과 어긋나기 쉽습니다.
• @gbacon — 1999년에 나온 글도 참고하세요. “Perl에는 람다 계산법이 들어 있습니다”, “1+1을 계산하는 163줄 프로그램”, “분량: 90분, 사전 지식: 없음”이라고 소개합니다.
  • @Dylan16807 — 람다 계산법을 재미있게 소개하는 글로는 이것도 있습니다. 피즈버즈까지 구현합니다.
• @winwang — 설명 방식이 좋네요. “이것 하나만 해보자 → 아, 망했네 → 반복” 하는 흐름이요. 글에서 말한 그래프 환원은 항 재작성(term rewriting)을 통한 평가입니다.
• @Joker_vD — 아레나 배열 안에 포인터 대신 인덱스를 저장하는 방법은 어떨까요? 4바이트 인덱스도 쓸 수 있으니 메모리 사용량을 줄일 수 있을 겁니다. 12GB 이상을 쓴다는 대목에서는 8바이트 인덱스를 써도 될 것 같네요. 복사 수집기도 고려할 수 있습니다. 재귀 피보나치는 쓰레기를 많이 만들지만 특정 시점에 살아 있는 데이터는 실제로 적을 테니까요. 가비지 컬렉터가 큰 생존 집합을 다루는지 시험하려면, 재귀 호출마다 두 갈래를 만드는 garbage(n) 같은 함수를 쓰면 됩니다. 그리고 피보나치 개선이라는 말은 AST를 재귀 순회하는 방식을 바꾸겠다는 뜻인가요, 아니면 지수 시간 피보나치를 바꾸겠다는 뜻인가요?
• @tromp — 저도 순수 함수형 언어 BLC/BLC2를 빠르게 구현하면서 그래프 환원 엔진을 만들었습니다. 400줄이 넘는 코드에 조합 논리용 엔진이 들어 있고, Kiselyov의 bracket abstraction 알고리즘으로 람다 계산 프로그램을 변환합니다.

원문: 개인 블로그 / 번역·요약: Trawling