1+1이 필요했는데 함수형 프로그래밍 언어를 만들었다

산술식을 이진 트리로 변환하는 자료구조 과제에서 출발해, C로 graphLang이라는 언어와 그래프 축약 엔진을 구현함 덧셈과 뺄셈을 개별 연산으로 처리하는 대신 함수 적용으로 일반화하고, 변수와 함수 모두 이름으로 조회할 수 있는 값으로 취급함 사용자 정의 함수는 C 함수 포인터가 아니라 매개변수와 본문 트리를 가진 클로저 노드로 표현해, 다른 함수에 전달하거나 반환하고 단계적으로 평가할 수 있게 함 고정 크기 아레나의 용량 한계를 청크 할당기로 해결하고, 표시 후 쓸기(mark-and-sweep) GC를 추가해 fib(40)의 메모리 사용량을 12GB 이상에서 약 1.7MB로 줄임 메모리 문제를 해결한 뒤에도 fib(40) 계산에는 6분이 걸렸으며, 실행을 멈추는 GC와 지수 시간 피보나치 계산 때문에 성능 개선 과제가 남음 산술식 트리에서 함수 적용으로 graphLang은 산술식을 이진 트리로 변환하는 과제에서 출발했으며, 며칠 뒤에는 C로 클로저, 가비지 컬렉터, 사용자 정의 메모리 할당기, REPL, FFI까지 구현한 프로젝트가 됨 최초 과제는 1 + 1 + 1을 이진 트리로 평가해 3을 얻는 것이었음 연산자를 루트로, 두 피연산자를 자식으로 배치함 (+ (+ 1 1) 1)에서 안쪽 덧셈을 먼저 평가해 (+ 2 1)로 줄이고, 마지막으로 3을 얻음 처음에는 표현식의 합 타입(sum type) 에 Add, Sub, Mul, Div, Val을 별도 변형으로 둘 수 있다고 생각함 네 산술 연산은 모두 Expr × Expr → Expr이라는 동일한 형태를 가짐 이를 Expr ::= Func Expr Expr | Val로 일반화하면 평가기는 함수가 무엇을 하는지 대신 어떻게 적용하는지만 알면 됨 변수는 해시 테이블에서 이름을 조회해 Expr을 얻는 방식으로 추가함 C에는 내장 해시 테이블이 없어 How to implement a hash table (in C)를 참고해 직접 구현함 표현식에 Var를 추가해, 변수를 평가한 결과도 함수에 전달할 수 있게 함 C 노드 표현과 아레나 할당기 초기 Node 구조체는 left, right 포인터와 정수 리터럴 또는 변수/함수 이름을 담는 공용체, LITERAL/VAR/FUNC 타입 태그로 구성함 64비트 시스템을 가정한 노드 크기는 32바이트였음 자식 포인터 두 개가 16바이트, 데이터 공용체가 8바이트, 타입이 4바이트, 패딩이 4바이트를 차지함 1+1에는 연산자 노드...