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

핵심 요약

• 데이터 구조 과제에서 1+1+1을 이진 트리로 평가하는 것에서 출발했다.
• 초기에는 Add, Sub, Mul, Div 등 연산을 모두 다른 경우로 표현했지만, 모두 두 식을 받아 하나를 반환하므로 일반화된 Func 노드로 단순화했다.
• 변수를 추가하려면 해시 테이블이 필요했는데, C에 내장 해시 테이블이 없어서 직접 구현했다.
• 각 노드가 32바이트이고 malloc 메타데이터 16바이트를 더하면 노드당 48바이트인데, 3개 노드로 1+1을 평가하려면 144바이트가 필요했다.
• 메모리 효율을 위해 아레나 할당자 대신 청크 할당자를 구현했다: 메모리 블록들을 연결 리스트로 체인하여 포인터 무효화 없이 동적 확장이 가능하게 했다.
• fib(5)를 평가하니 13,000개 노드가 생성되었는데 할당자는 1,024개만 지원해서 작동했지만, fib(10)은 40MB, fib(40)은 12GB 이상을 사용했다.
• 문제는 평가 후 더 이상 필요 없는 노드들을 절대 해제하지 않았기 때문이었다.
• 마크-앤드-스윕 가비지 컬렉터를 구현했다: 평가 중 노드를 리터럴로 축약하면 자식 포인터를 null로 설정하고, GC가 도달 가능한 노드만 마크한 후 미마크 노드를 재사용 리스트에 넣는다.
• GC 적용 후 fib(40)의 메모리 사용량이 12GB에서 1.7MB로 감소했다.
• 하지만 fib(40)을 평가하는데 6분이 걸렸다: mark-and-sweep은 stop-the-world 방식이고 피보나치 평가 자체가 지수 복잡도이기 때문이다.
• 이후 TCO(꼬리 호출 최적화), 어휘 분석기/파서, FFI, REPL 구현, 람다 함수, 지역 변수, Cheney의 복사 수집기 등을 추가할 예정이다.
• 최종적으로 대수적 데이터 타입, 환경 테이블, 청크 할당자, mark-and-sweep GC를 갖춘 그래프 축약 엔진을 만들었다.