🌐 Read in English

1장의 배경지식.

그래프 축약과 지연 평가

lambda-calculus-and-ski.md와 bracket-abstraction.md는 Var/Lam이 하나도 남지 않은 컴비네이터 항까지 데려다준다. 이 글은 나머지 절반을 다룬다: ccb31388:eval.c, 그 항을 실제로 실행하는 약 540행짜리 C 프로그램이다. 핵심 아이디어는, 항이 여기저기 복사되어 다니는 트리가 아니라 — 변경 가능한 셀들로 이루어진 그래프이고, 축약은 셀을 제자리에서 재작성한다는 것이다. 바로 이 설계 선택 하나에서 공유와 지연성이 모두 나온다.

1. 셀은 태그 하나에 포인터 둘(또는 값 하나)

ccb31388:eval.c (23–33행):

typedef struct node {
  enum node_mark mark;
  enum node_tag tag;
  union {
    value_t value;
    struct {
      struct node *fun;
      struct node *arg;
    } s;
  } u;
} node;

그리고 태그 enum (17행):

enum node_tag { FREE, IND, AP, INT, S, K, I, B, C, T, Y, SS, BB, CC, ADD, SUB, MUL, DIV, MOD, SUBR, EQ, NE, LT, LE, GT, GE };

힙에 있는 모든 노드는 이 중 하나다. AP 노드는 함수 적용이다: 그 fun/arg 유니온 필드(FUN/ARG 매크로로 접근)는 다른 두 셀을 가리킨다. S나 K 같은 컴비네이터는 페이로드를 전혀 갖지 않는 노드다 — 태그 자체가 곧 값이다. INT 노드는 fun/arg 대신 value 필드를 쓴다. 컴파일된 프로그램 전체는 컴비네이터/INT/프리미티브 잎을 가진 하나의 큰 AP 셀 트리다 — 그러나 3절에서 보이듯, 축약이 시작되는 순간 "트리"라는 표현은 더 이상 정확하지 않게 되는데, 셀들이 재사용되고 서로 교차 연결되기 때문이다.

2. 스파인 스택과 S 재작성

eval의 임무는 최좌측-최외곽 리덱스를 찾는 것이다. 이를 위해 적용의 왼쪽 스파인을 따라 내려가며 — FUN, FUN, FUN, ... — 지나치는 모든 노드를 명시적 스택에 쌓다가, AP가 아닌 것을 만나면 멈춘다. 스택 매크로들(ccb31388:eval.c, 99–101행):

#define PUSH(x) stack[++stack_ptr] = (x)
#define TOP(n) stack[stack_ptr - (n)]
#define POP(n) stack_ptr -= (n)

그리고 이를 사용하는 루프 (364–377행, AP 풀어내리기 단계만):

  PUSH(n);
  for(;;) {
    num_reductions++;
    switch (TAG(n)) {
    ind:
    case IND:
      n = INDIR(n);
      TOP(0) = n;
      break;
    ap:
    case AP:
      n = FUN(n);
      PUSH(n);
      break;

TOP(0)은 방금 찾은 가장 안쪽 노드이고, TOP(1)은 한 단계 바깥, 이런 식으로 이어진다 — k번의 적용을 풀어낸 뒤에는 TOP(k)가 가장 바깥쪽 노드, 즉 리덱스의 뿌리다. 스위치문이 위에 인자가 충분히 쌓인 컴비네이터 태그에 도달하면, TOP/ARG를 통해 스택에서 인자를 읽어와 재작성한다. 다음은 case S 전문이다 (380–391행):

    case S:
      CHECK(3);
      GCCHECK(2);
      f = ARG(TOP(1));
      g = ARG(TOP(2));
      x = ARG(TOP(3));
      POP(3);
      n = TOP(0);
      FUN(n) = new_ap(f, x);
      ARG(n) = new_ap(g, x);
      GOTO ap;
      break;

CHECK(3)은 스택에 인자가 셋 미만이면 (축약하지 않고) 그냥 빠져나온다 — S는 완전히 적용됐을 때만 리덱스이기 때문이다. 그렇지 않으면 f, g, x를 스파인에서 읽어들이고, 세 개의 중간 노드를 팝한 뒤, n = TOP(0)이 리덱스의 가장 바깥쪽 노드 — 즉 원래의 ((S f) g) x 적용 셀 — 을 되찾는다. 그 셀의 FUN/ARG 필드는 그다음 new_ap(f, x)와 new_ap(g, x)로 덮어 쓰여진다: 노드가 제자리에서 f x (g x)로 바뀌는데, 이는 정확히 lambda-calculus-and-ski.md의 S 규칙이다. GOTO ap는 이 새로 재작성된 노드에서부터 풀어내리기를 다시 시작한다 — 3절에서 그다음에 무슨 일이 일어나는지 추적한다.

3. 공유: x는 한 번만 가져오지, 복사하지 않는다

case S를 다시 보자: x = ARG(TOP(3))는 포인터 하나를 읽어들이고, 바로 그 포인터 값이 new_ap(f, x)와 new_ap(g, x) 둘 다에 쓰인다. f x (g x)에 있는 두 개의 x 출현은 부분항의 두 복사본이 아니다 — 이들은 arg 필드가 우연히 동일한 힙 셀을 가리키는 두 개의 AP 셀이다. 그것이 C 코드 한 줄로 표현되는 공유의 메커니즘 전부다.

이를 발휘하는 가장 작은 항, S f g x 자체를 (((S +) I) ((+ 2) 3))로 놓아보자 — 즉 x = 2 + 3일 때의 + x (I x)다. S-축약 이전, 이 항은 잎 S 위에 세 개의 AP 셀이 쌓인 것이고(가장 바깥쪽, 즉 마지막에 적용된 것을 n_c라 하자), 거기에 ((+ 2) 3)에 대한 별도의 부분그래프 X가 딸려 있다:

n_c ──fun──▶ n_b ──fun──▶ n_a ──fun──▶ [S]
 │            │            └──arg──▶ [+]
 │            └──arg──▶ [I]
 └──arg──▶ X            where X = AP(AP(+, 2), 3)

2절에서와 정확히 같은 방식으로 이 그래프에 대해 case S를 추적해 보면: f = ARG(n_a) = +, g = ARG(n_b) = I, x = ARG(n_c) = X, 그리고 n = TOP(0) = n_c — 답으로 재사용되는 가장 바깥쪽 셀이다. 재작성 이후:

n_c ──fun──▶ n_d = AP(+, X)
 └──arg──▶ n_e = AP(I, X)
                    │
        both n_d.arg and n_e.arg point at the SAME cell X

n_c 자신은 해제되고 재할당된 적이 없다 — 그 fun/arg 필드가 덮어 쓰였을 뿐이므로, 그래프 어디서든 n_c를 가리키는 다른 포인터는 공짜로 재작성된 형태를 보게 된다. 그리고 n_d/n_e는 둘 다 하나의 X 셀을 가리키지, ((+ 2) 3)의 두 복사본을 가리키지 않는다.

이제 그 대가를 보자. 풀어내리기가 n_c에서 다시 시작되어 ADD 프리미티브에 도달하는데, 그 ARITH2 매크로(476행)는 두 피연산자를 모두 강제 평가한다: r = evalint(ARG(TOP(1))) op evalint(ARG(TOP(2))); (op = +) — 여기서 ARG(TOP(1)) = X이고 ARG(TOP(2)) = n_e = AP(I, X)다. 정직하게 짚어둘 것 하나: C는 +의 피연산자 평가 순서를 규정하지 않으므로, 두 evalint 호출 중 어느 것이 먼저 실행되는지는 컴파일러의 선택이다 — 그리고 공유에 대한 결론은 여기에 의존하지 않는다. 두 피연산자 모두 동일한 셀 X로 이어진다: 첫 번째는 직접, 두 번째는 n_e를 통해서인데, case I가 이를 X로의 간접 참조로 바꿔놓는다 (4절). 어느 쪽이 먼저 강제되든 X를 완전히 축약한다 — 안쪽 덧셈의 SETINT(n, r)(475행)가 X 자신의 태그/값 필드를 제자리에서 INT 5로 덮어쓴다. 그다음 다른 쪽이 강제되면, 그것은 같은 셀에 도달한다 — 직접이든, n_e의 간접 참조를 거치는 evali의 while (TAG(n) == IND) 루프(335–336행)를 통해서든 — 그리고 이미 거기 있는 태그 INT를 발견한다: 즉시 반환하고, 재계산은 없다. 어느 순서든 2 + 3은 정확히 한 번만 실행된다; 두 번째 소비자는 그저 누군가 이미 계산을 끝낸 셀로 이어지는 포인터를 따라갈 뿐이다.

실제 항을 실행해서 검증했다(shared2.comb, 축약 카운터에서 눈에 띄게 보일 만큼 효과를 키우기 위해 2 + 3 자리에 20단 깊이의 덧셈 사슬을 넣은 같은 아이디어, 아래에 등장). 작은 경우:

$ ./eval shared.comb        # (((S +) I) ((+ 2) 3))
(((S +) I) ((+ 2) 3))
10
node size=24, heap size=100000
16 reductions, 0 GCs
$ ./eval duplicated.comb    # ((+ ((+ 2) 3)) ((+ 2) 3)) -- two independent copies of (+ 2 3)
((+ ((+ 2) 3)) ((+ 2) 3))
10
node size=24, heap size=100000
13 reductions, 0 GCs

둘 다 마땅히 10을 낸다. 그러나 여기서는 공유 버전이 축약을 더 많이 한다 (16 대 13) — 두 단계짜리 덧셈에서는, 추가된 S와 I 재작성의 고정 오버헤드가 절약하는 덧셈 한 번보다 더 크기 때문이다. 공유는 공짜가 아니다; 간접 참조 하나와 추가 적용 노드 하나의 비용이 든다. 공유가 실제로 이기는 것을 보려면, 공유된 부분항이 S/I 오버헤드보다 재계산 비용이 더 클 만큼 비싸야 한다. 2 + 3을 20단 깊이로 중첩된 덧셈으로 바꾸면(((...((+ 1) 1)...) 1), 여전히 같은 S + I 모양을 통한 x + x다) 그 절약이 확연해진다:

$ ./eval shared2.comb
42
node size=24, heap size=100000
92 reductions, 0 GCs
$ ./eval dup2.comb          # x + x with x written out twice (no sharing)
42
node size=24, heap size=100000
165 reductions, 0 GCs

같은 답, 92 대 165 축약 — 중복된 버전은 20단 깊이의 사슬 비용을 두 번 치르고, 공유된 버전은 한 번만 치른다. 그것이 측정된 "한 번만 평가한다"이지, 그냥 주장이 아니다.

4. 간접 노드: 그렇다, 커밋 1에도 존재한다

첫 커밋의 평가기는 간접 노드를 다루기엔 너무 조악할 거라고 추측하기 쉽지만 — 그렇지 않다. IND는 1절에서 인용한 enum에서 태그 1이며, 여러 곳에서 만들어지고 따라가진다.

생성은 SETIND 매크로를 통해 이루어진다 (361행):

#define SETIND(n, x) do { TAG((n)) = IND; INDIR((n)) = (x); } while(0)

case K, case T, case I(항등 재작성들 — 각각 결과를 복사해 넣는 대신 리덱스 셀을 결과로의 포인터로 바꾼다)와, 결과 셀을 불리언 컴비네이터 T/K로 간접 참조하게 만드는 공유 매크로(496행)를 가진 비교 프리미티브들이 이를 사용한다:

#define CMP(op) do { CHECK(2); r = evalint(ARG(TOP(1))) op evalint(ARG(TOP(2))); n = TOP(2); SETIND(n, r ? combT : combK); POP(2); } while(0)

case I 자체 (421–428행):

    case I:
      CHECK(1);
      x = ARG(TOP(1));
      POP(1);
      n = TOP(0);
      SETIND(n, x);
      GOTO ind;
      break;

— I x는 x의 새 복사본을 할당하지 않는다; I x 적용 셀 자체를 x로의 간접 참조로 바꾼다. 이는 3절의 S와 같은 제자리 갱신 트릭을, "새 그래프"가 단지 기존 인자일 뿐인 경우에 특수화한 것이다.

따라가기는 세 곳에서 일어난다: eval 자신의 루프 안(2절에서 인용한 case IND, n = INDIR(n); TOP(0) = n;), evali 안(327–338행, eval이 반환한 뒤의 while (TAG(n) == IND) n = INDIR(n); — 호출자가 "진짜" 답을 얻을 때 쓰는 것으로, 결코 간접 참조 셀을 얻지 않는다), 그리고 가비지 컬렉터의 mark 안(다음 절) — 이는 부수 효과로 간접 참조 사슬을 압축하기도 하며, 뿌리 포인터를 그 사슬 너머로 재작성한다 (165–171행):

  if (TAG(n) == IND) {
    /* Skip indirections, and redirect start pointer */
    while (TAG(n) == IND) {
      n = INDIR(n);
    }
    *np = n;
  }

5. 메모리: 할당과 진짜 마크-스캔 GC

셀은 한 번 할당되는 고정 크기 배열에서 나온다 (11행, 46행):

#define HEAP_CELLS 100000

#define ALLOC_HEAP(n) do { cells = malloc(n * sizeof(node)); memset(cells, 0x55, n * sizeof(node)); } while(0)

100,000개의 셀을 미리 malloc하고 다시는 늘리지 않는다 — 이 파일 어디에도 개별 셀에 대한 free()는 없다; 셀이 다시 쓸 수 있게 되는 유일한 방법은 컬렉터를 거치는 것이다. alloc_node(108–120행)는 그저 프리 리스트의 머리를 팝할 뿐이다:

NODEPTR
alloc_node(enum node_tag t)
{
  NODEPTR n = next_free;
  if (n == NIL) {
    ERR("out of memory");
  }
  if (TAG(n) != FREE)
    abort();
  next_free = NEXT(n);
  TAG(n) = t;
  return n;
}

그리고 커밋 1은 진짜로 컬렉터를 갖고 있다 — 마크-스캔 방식으로, 할당이 많은 축약 전에 GCCHECK를 통해 호출된다 (예: case S, 2절: 두 번의 new_ap 호출 전에 GCCHECK(2)). gc_check는 프리 리스트가 짧아 보일 때만 실제로 수거한다 (212–222행); gc, mark, scan(158–210행)은 교과서적인 스톱더월드 마크/스윕이다: mark는 모든 살아 있는 뿌리 — 현재 stack[0..stack_ptr]에 있는 모든 셀 — 로부터 시작해 AP 스파인을 재귀적으로 마킹한다 (그리고 위에서 보인 것처럼 IND 사슬을 압축한다); 그다음 scan은 힙 전체를 한 번 선형으로 훑으며, 마킹되지 않은 모든 셀을 프리 리스트에 꿰어 넣고 나머지의 마크를 지운다 (198–210행, 주석 처리된 fprintf 디버그 줄 세 개는 생략했으며 ...로 표시):

void
gc(void)
{
  num_gc++;
  num_marked = 0;
  // ...
  for (int i = 0; i <= stack_ptr; i++)
    mark(&stack[i]);
  // ...
  scan();

  // ...
}

이는 원리로만 존재하는 게 아니라 실제로 실행되어 검증된다: nfib 35를 실행하면 (see y-combinator-and-recursion.md) 십억 번이 넘는 축약 동안 1944 GCs가 보고된다.

커밋 1에 없는 것: 압축이나 복사가 없고(셀은 결코 이동하지 않는다 — scan은 프리 리스트를 다시 연결할 뿐, 힙 배열을 줄이거나 조각 모음하지 않는다), 세대도, 참조 카운팅도, 늘어나는 힙도 없다 (alloc_node의 out of memory는 메모리를 더 요청하는 게 아니라 그냥 하드한 ERR/exit다). 파일 상단의 #elif 분기에 스케치된 NODE_SPLIT과 NODE_64 표현은 쓰이지 않는 대안들이다 — NODE_NAIVE (9행: #define NODE_NAIVE)가 #define되어 컴파일되는 것이며, 1절의 struct node가 그 표현이다.

6. 지연성은 이로부터 저절로 나오는 것이지, 나중에 덧붙인 게 아니다

위 내용 중 어느 것도 인자를 요청받기 전에 평가하지 않는다. case S는 new_ap(f, x)와 new_ap(g, x)를 만들고 즉시 GOTO ap로 왼쪽 스파인에 돌아간다 — x를 결코 들여다보지 않는다. x는 이후의 어떤 축약 단계가 그것을 INT로 필요로 할 때(evalint를 통해, 예를 들면 ARITH2, 476행 안에서), 또는 그 가장 바깥쪽 태그를 패턴 매칭해야 할 때에만 강제된다. 결코 요구되지 않는 인자는 그저 손대지지 않은 채 남는다 — 그것은 차지하는 메모리 외에는 아무 비용 없이 영원히 평가되지 않은 AP/컴비네이터 부분그래프로 남는다. 이를 3절의 공유와 결합하면 call-by-need를 공짜로 얻는다: 인자는 그래프이고, 무언가 그것을 강제할 때(그리고 그럴 경우에만) 정확히 한 번 평가된다.

다음: y-combinator-and-recursion.md — 같은 제자리 갱신 트릭을, 재귀를 위해 진짜로 순환하는 그래프를 만드는 데 적용한 것.