1장의 배경지식.

Y 컴비네이터와 재귀

bracket-abstraction.md는 항 안의 모든 Lam을 제거한다. 그런데 nfib는 자기 자신을 호출한다 — compile 이후에는 이름이 아예 남아 있지 않은 언어로의 변환에서, 자기 호출은 어떻게 살아남는가?

1. 이름이 없으면 자기 참조도 없다

abstract(참고: bracket-abstraction.md 1절)는 어떤 항에 들어 있는 속박된 변수를 제거하는 방법만 알 뿐이다. nfib n = ... nfib ... 같은 재귀 정의는 이런 식으로 자연스럽게 표현되지 않는다: nfib는 무엇의 매개변수도 아니다 — 그것은 지금 정의되고 있는 이름이며, 자기 자신의 본문 안에서 자기 자신을 가리킨다. compile이 Var/Lam을 지우고 나면, 런타임에는 환경도 이름 테이블도 없어서(참고: lambda-calculus-and-ski.md 3절) 이름이 통해서 참조할 대상 자체가 없다. 컴비네이터 항은 구성상 닫혀 있으므로, 다른 무언가가 자기 참조를 공급해야 한다.

2. `Y f = f (Y f)`, 그리고 축약이 실제로 만들어내는 것

표준적인 트릭은 고정점 컴비네이터 Y다: Y f는 정확히 f (Y f)처럼 동작하도록 정의된다 — f를 "지금 만들고 있는 바로 그 재귀적인 값"에 적용하는 것이다. nfib의 본문을, 자신의 재귀적 호출 대상을 추가 인자로 받는 평범한(비재귀적인) 함수 nfibF = \nfib n -> ...로 바꾸면, Y nfibF는 nfibF (Y nfibF)와 같은 값이다 — nfibF에게 호출할 자기 자신의 사본을 먹여주는 것이다.

ccb31388:eval.c의 Y에 대한 축약 규칙 (429–437행):

    case Y:
      CHECK(1);
      f = ARG(TOP(1));
      POP(1);
      n = TOP(0);
      FUN(n) = f;
      ARG(n) = n;
      GOTO ap;
      break;

여기서 n은 TOP(0)이다 — 리덱스의 가장 바깥쪽 셀, 즉 Y f 자체에 대한 AP(Y, f) 노드다 ( graph-reduction-and-laziness.md 2절의 case S와 비교해 보라, 같은 패턴이다: 인자를 읽고, 그다음 바깥쪽 셀을 답으로 재사용한다). 이 재작성은 FUN(n) = f를 설정하고, 결정적으로 ARG(n) = n도 설정한다 — 노드 자신의 인자 필드가 자기 자신을 가리키도록 설정되는 것이다. 이는 "f (Y f)의 또 다른 사본을 얻기 위해 Y f를 다시 호출"하는 것이 아니다 — 그것은 제자리에서 변경된 셀 하나이며, 이제 말 그대로 AP(f, n)인데, 여기서 n은 바로 그 AP를 담고 있는 노드 자신이다. n에서 ARG를 따라가면 다시 n으로 돌아온다. Y f의 그래프는 진짜로 순환적이다: 한 번 만들어진 단일한 자기 참조 적용 셀이다. 펼치는 것은 그저 같은 셀에 다시 들어가는 것일 뿐이므로, 몇 번이든 "펼칠" 수 있다는 데 한계가 없다.

GOTO ap는 이제 f (Y f)가 된 n에서부터 스파인 순회를 다시 시작한다 — 정확히 고정점 방정식이지만, 반복해서 재작성해야 하는 관계가 아니라 그래프상에서 이미 성립하는 항등 관계다. f의 본문이 더 안쪽에서(재귀 호출 지점에서) 두 번째 인자를 다시 요구하면, 같은 자기 순환 셀 n을 역참조하여 찾아내는데 — 그 시점에는 — 아직 같은 AP(f, n)이거나 (재귀가 더 강제되지 않았다면), 아니면 같은 자기 연결을 따라 이미 더 축약되어 있는 상태다. 어느 쪽이든, f 자신은 한 번만 가져와졌고 결코 복사되지 않는다; 오직 자기 참조 주변의 스파인만이 축약이 진행됨에 따라 자라난다.

3. `eNfib`: 재귀 정의와 `Y`가 들어오는 지점

ccb31388:Lam.hs (193–194행):

fix :: Exp -> Exp
fix e = App CY e

fix는 그저 "Y로 감싸기"일 뿐이다 — CY는 Comb "Y" 패턴 동의어이고(ccb31388:Lam.hs, 72행: pattern CY = Comb "Y"), App CY e는 항 Y e다. eNfib(225행):

eNfib = fix $ comp $ \ nfib n -> iF (n .< 2) 1 (nfib $$ (n-1) + nfib $$ (n-2) + 1)

\nfib n -> ...는 2절의 비재귀적인 nfibF를, 하스켈 자체의 람다 문법으로 쓰고 ToLam 장치를 통해 Exp로 바꾼 것이다 (comp = improve . compile . toLam, 219행 — compile/improve는 bracket-abstraction.md 참고). nfib $$ (n-1)과 nfib $$ (n-2)는 두 번의 재귀 호출인데, 둘 다 이름으로 자기를 참조하는 게 아니라 매개변수 nfib에 대한 것이다. fix는 컴파일된 함수 전체에 Y를 적용하므로 eNfib = Y nfibF가 되고 — 본문 안에서 nfib이 나타나는 모든 자리는, compile 이후, 요구될 때 Y의 자기 순환 셀(2절)이 무엇으로 풀리든 그것을 가리키게 된다. ./eval nfib.comb가 축약 전에 출력하는 그 컴파일된 항은, 유도 과정이 예측하는 바로 그 자리에 Y를 갖고 있다 — 전체 재귀 함수를 감싸고, 35에 적용된 채로:

((Y (((C' C) ((B (S (> 2))) (((C' (C' +)) (((S' (S' +)) ((C B) (-' 1))) ((C B) (-' 2)))) 1))) 1)) 35)

(이것은 bracket-abstraction.md 4절이 이미 improve 출력의 실행 예시로 인용한 것과 같은 출력된 항이다; 맨 앞의 Y가 이 글이 다루는 부분이다.)

4. 공유로서의 재귀

2절의 자기 순환 셀은 graph-reduction-and-laziness.md가 평범한 컴비네이터(S, K, I)에 대해 설명하는 것과 똑같은 제자리 갱신 메커니즘이다 — Y의 축약은 그저 이를 이용해 셀이 다른 기존 노드가 아니라 자기 자신을 가리키게 할 뿐이다. 실행 중인 nfib의 모든 재귀 호출은 case Y가 처음에 가져온 그 f 포인터 하나를 재사용한다; f의 코드(컴파일된 컴비네이터 그래프)는 호출마다 결코 중복되지 않는다. 오직 인자 스파인 — n-1/n-2 적용이 대기 중인 사슬 — 만이 재귀가 내려갈수록 자라나며, 그 각각은 그래프의 나머지 부분과 정확히 마찬가지로 평범한 AP 축약에 의해 만들어지고 해체된다.

5. 검증: `./eval nfib.comb`는 `29860703`을 출력한다

$ cd /tmp/mhs-ccb31388 && nix develop $MICROHS -c make test
./eval nfib.comb
((Y (((C' C) ((B (S (> 2))) (((C' (C' +)) (((S' (S' +)) ((C B) (-' 1))) ((C B) (-' 2)))) 1))) 1)) 35)
29860703
node size=24, heap size=100000
1045124618 reductions, 1944 GCs

29860703은 nfib 35다 — 이 커밋에 대한 이전 모든 과제의 검증된 결과와 일치한다. 이 실행은 또한 graph-reduction-and-laziness.md의 주장, 즉 GC가 소스에 그냥 존재하기만 하는 게 아니라 실제로 실행된다는 주장도 확인해 준다: 이 한 번의 계산이 진행되는 동안 1944 GCs가 실제로 발동했다.

6. 나중에 바뀌는 것

이 Y — 위에서 보인 그대로 case Y에 의해 축약되는 자기 순환 셀 하나 — 은 첫 커밋이 하는 일이다. 이것이 마지막 말은 아니다: 커밋 d2956ee8, "Optimize Y better."(Y를 더 잘 최적화하기, 2023-06-02)가 이 구현을 다시 살펴본다. 무엇이 바뀌는지는 여기서 다룰 범위 밖이다; 4장에서 다룬다.

MicroHs에서 배우기 (Learning from MicroHs)