1+1을 계산하려다 함수형 프로그래밍 언어를 만들었다
Needed 1+1, built a functional programming language
데이터 구조 과제로 1+1+1을 이진 트리로 평가하다, 평가기가 덧셈과 뺄셈을 구분할 필요가 없다는 걸 깨닫고 함수형 언어로 확장한다. C로 클로저, 가비지 컬렉터, 커스텀 메모리 할당자, REPL, FFI까지 구현한 과정을 담았다. 피보나치 fib(5)가 13,000개 노드를 생성해 크래시하고, fib(40)은 12GB 메모리를 잡아먹는 문제를 해결하며 언어의 핵심 요소를 하나씩 완성해 나간다.
fib(40)은 OOM으로 크래시하기 전까지 문자 그대로 12GB 이상을 사용했다. 왜냐하면 약 13억 개의 노드를 생성하기 때문이다. 노드당 48바이트면 약 62.4GB에 달하는 노드 할당이다.
HN 토론
75- CodesInChaos
Greenspun의 프로그래밍 제10법칙:
> 충분히 복잡한 C나 Fortran 프로그램이라면, 그 안에 Common Lisp의 절반을 임시방편으로, 비공식적으로 명세된, 버그투성이의, 느린 구현이 들어있다.
- tromp
> 전체적으로, 나는 Graph Reduction 엔진을 만들었다
나는 순수 함수형 프로그래밍 언어 BLC/BLC2의 성능 좋은 구현을 위해 똑같은 일을 했다.
그건 400줄이 조금 넘는 코드 안에 combinatory logic을 위한 graph reduction 엔진을 포함하고 있고, lambda calculus 프로그램들은 Kiselyov의 bracket abstraction 알고리즘에 의해 그쪽으로 변환된다.
- heronbank
공감된다. 아무도 읽지 않는 보고서를 위해 1년에 두 번 돌아가는 쿼리를 최적화하느라 일주일을 보냈다. 토끼굴은 진짜다.
- gnarlouse
이걸 보니 수십 년 전이 떠오른다... 잠깐, 나도 3년 전까지만 해도 코드를 쓰고 있었지.
- Joker_vD
> 문제는, 우리의 모든 노드가 이 메모리 블록 안에서 서로를 가리키고 있다는 거다. 크기를 늘려 realloc하면 새로운 메모리 주소로 옮겨질 수 있다. 그러면 우리의 모든 포인터가 완전히 깨져서 segfault가 난다! 이 문제를 어떻게 해결할까?
arena 배열에 인덱스를 저장하면? 아마 4바이트 인덱스를 써서 메모리 사용량을 줄일 수도 있을 거다...
> Fib(40)은 OOM에 걸려 크래시하기 전까지 말 그대로 12+ 기가바이트를 잡아먹었다. 왜? 약 13억 개의 노드를 생성하기 때문이다.
좋아, 그럼 8바이트 인덱스를 유지해도 되겠다.
> 우리가 방금 완성한 mark-and-sweep 가비지 컬렉터는 stop-the-world 가비지 컬렉터다. 그리고 우리가 돌리는 알고리즘은 본질적으로 지수적이다.
그럼 copying collector는 어때? 재귀적 Fibonacci는 쓰레기를 엄청 많이 만들지만, 내 기억으로는 어느 한 시점에서든 살아있는 집합은 사실 꽤 작다. 함수가 실제로 거대한 live set을 가질 때 GC 벤치마크가 필요하다면, 이런 게
def garbage(n):
if n == 0:
return None
return (garbage(n-1), garbage(n-1))
해줄 거다. 적절한 데이터 구조가 없으면 클로저로 아주 간단히 흉내 낼 수 있다.
> 그리고 fib 자체를 평가하는 방식에 대해서도 뭔가 할 수 있다
'재귀적으로 AST를 순회하는 것에서 전환하자'라는 뜻인가, 아니면 '지수적이지 않은 Fibonacci를 작성하자'라는 뜻인가?