🌐 Read in English

04 — Talking to the world (세상과 대화하기)

현재 위치

3장은 let, 중위 연산자, 튜플, 리스트, 문자열, 모듈, do-표기법을 갖춘 언어를 남긴다 — 여기에는 Prelude.uhs, List.uhs와 함께 95ff6a34가 만든 IO 모듈, IO.uhs도 포함된다. 그 커밋 시점의 IO.uhs는 프리미티브 선언 목록에 지나지 않는다(95ff6a34:IO.uhs, 전문 인용):

module IO where

(>>=)     = primitive "IO.>>="
(>>)      = primitive "IO.>>"
return    = primitive "IO.return"
readFile  = primitive "IO.readFile"
writeFile = primitive "IO.writeFile"
putChar   = primitive "IO.putChar"
getChar   = primitive "IO.getChar"

그리고 3장의 693dc6ce가 do-표기법을 "IO 모나드"라는 내장 개념이 아니라 (>>=)/(>>)를 제공하는 모듈이 무엇이든 그것에 따라 디스패치하게 만들었기 때문에, IO.do { putChar 'h'; putChar 'i' }는 지금까지 존재하는 모든 단계를 거쳐 깔끔하게 파싱되고, 디슈가되고, 컴파일된다 — 아직 타입 검사기가 없으므로(3장의 e96d04be는 :: 시그니처가 파싱된 뒤 버려진다는 사실을 확립한다) IO가 특별하다는 것을 알아채거나 신경 쓸 대상이 없다. 하지만 컴파일된다고 실행되는 것은 아니다. 2장 이후 한 번도 바뀌지 않은 eval.c는 여전히 예전의 문자 디스패치 파서이자 축약기다: 그 프리미티브 테이블은 단일 문자('+', '-', '*', '/', '%', '=', '!', '<', '>', '?')에 대한 하드코딩된 switch이며, IO.>>=처럼 여러 문자로 된 이름을 인식할 수 있는 항목도, 그런 항목을 위한 메커니즘도 없다. 직접 검증하면: 이 범위의 첫 커밋인 834fd9ba (아직 모나딕 IO가 들어오기 전이다, 아래 참고)를 3장의 빌드 노트가 쓰는 것과 같은 한 줄짜리 ap/when 패치로 빌드하고, 다음을 실행하면

module TestIO where
import Prelude
import IO

main = IO.do
  putChar 'h'
  putChar 'i'

IO.>>=, IO.putChar 등을 접두사 없는 순수 식별자 텍스트로 그대로 담고 있는 .comb 파일로 컴파일되고(Prim은 이 시점에서 자신의 원시 문자열 그대로 출력된다 — 런타임이 프리미티브 참조임을 인식하게 해 주는 $-접두사 관례는 아직 존재하지 않는다), 그 파일을 실행하면 즉시 죽는다:

$ nix develop $MICROHS -c ./eval out.comb
ERR: parse ')'

그러므로 "현재 위치"는 정확히 이렇다: IO 구문, IO 모듈, 그리고 그것과 우연히 잘 맞아떨어지는 범용 do-표기법은 모두 이미 갖춰져 있다. 그 아래의 런타임은 허구다 — 모든 IO 프리미티브는 컴파일러 아래에 아무 의미도 없는 이름일 뿐이다. 이 장의 첫 커밋이 바로 그것에 의미를 부여하는 커밋이다.

무슨 일이 있었나

3246e2a6: 모나딕 IO, 그리고 IO 값이 실제로 무엇인가

"Implement monadic IO."(모나딕 IO 구현)는 2023-06-01 저녁, 3장을 마감한 95ff6a34 이후 약 네 시간 사십 분 뒤에 올라간다 — 빈 공백이 아니다: 같은 날 더 일찍(12:09, 12:32) 834fd9ba "Small improvements"(작은 개선들)와 e2f3cf57 "More stuff"(이것저것 더)가 올라가는데, 둘 다 설명 없는 준비 작업으로 IO.uhs를 확장한다 — 프리미티브 선언 하나(print) 추가, 그리고 기존 프리미티브 위에 지어진 파생 헬퍼(mapM, mapM_, putStr, putStrLn) 첫 묶음 — 여전히 어떤 IO.* 이름 뒤에도 런타임은 없는 채로. 같은 커밋에서 두 가지 일이 벌어지며, 이 둘을 구분해 두는 것이 좋다: eval.c는 이름 있는 프리미티브를 위한 범용 메커니즘(IO 전용이 아닌)을 얻고, 그 메커니즘 위에서 IO가 첫 실제 구현을 얻는다.

범용 메커니즘 쪽: 개별적으로 이름 붙은 전역 변수들의 목록이던 NODEPTR combS, combK, ...가 {name, tag, node} 삼중항의 배열 하나로 대체된다. 일부를 생략하며 인용한다(3246e2a6:eval.c, 168–210행):

struct {
  char *name;
  enum node_tag tag;
  NODEPTR node;
} primops[] = {
  /* combinators */
  { "S", S },
  { "K", K },
  ...
  { "O", O },
  /* primops */
  { "+", ADD },
  ...
  { "ord", ORD },
  { "IO.>>=", IO_BIND },
  { "IO.>>", IO_THEN },
  { "IO.return", IO_RETURN },
  { "IO.readFile", IO_READFILE },
  { "IO.writeFile", IO_WRITEFILE },
  { "IO.getChar", IO_GETCHAR },
  { "IO.putChar", IO_PUTCHAR },
  { "IO.print", IO_PRINT },
};

그리고 .comb 파일 파서의 '+'/'-'/'?' 등 단일 문자 case들은 임의의 이름을 읽어 들여 찾아보는 '$' case 하나로 대체된다 (3246e2a6:eval.c, 365–381행, 전문 인용):

  case '$':
    /* A primitive, keep getting char's until end */
    for (int j = 0;;) {
      c = getc(f);
      if (c == ' ' || c == ')') {
        ungetc(c, f);
        buf[j] = 0;
        break;
      }
      buf[j++] = c;
    }
    for (int j = 0; j < sizeof primops / sizeof primops[0]; j++) {
      if (strcmp(primops[j].name, buf) == 0)
        return primops[j].node;
    }
    fprintf(stderr, "bad primop %s\n", buf);
    ERR("no primop");

이제 모든 컴비네이터와 프리미티브는, IO든 아니든, 이 경로 하나를 지난다 — 이 장의 트랜스크립트 어디에서나 보이는 $-접두사 관례 ($K, $IO.>>=, $chr, ...)는 바로 이 커밋의 작품이며, IO.>>=를 애초에 파싱 가능하게 만드는 인프라 조각이다. IO.>>=가 그다음에 무엇을 하는지와는 별개로 그렇다.

그것이 하는 일은 새로운 enum node_tag 값 여덟 개다(3246e2a6:eval.c, 18–21행, 전문 인용):

enum node_tag { FREE, IND, AP, INT, CHAR, S, K, I, B, C, T, Y, SS, BB, CC, P, O,
                ADD, SUB, MUL, QUOT, REM, SUBR, EQ, NE, LT, LE, GT, GE, ERROR, CHR, ORD,
                IO_BIND, IO_THEN, IO_RETURN, IO_READFILE, IO_WRITEFILE, IO_GETCHAR, IO_PUTCHAR, IO_PRINT
};

IO a 값은, 이 커밋에서도, 이 장의 범위 안 그 어떤 이후 커밋에서도, 별도의 런타임 타입이 아니다 — 이 여덟 개의 새 태그 중 하나를 가진 평범한 그래프 노드일 뿐이다. 보통의 축약 루프인 eval()에게 이 태그들은 불투명하며, INT나 CHAR와 똑같이 이미-값인 태그다 — 전체 처리는 축약 규칙 없는 RET 하나뿐이다(3246e2a6:eval.c, 769–777행, 전문 인용):

    case IO_BIND:
    case IO_THEN:
    case IO_RETURN:
    case IO_READFILE:
    case IO_WRITEFILE:
    case IO_GETCHAR:
    case IO_PUTCHAR:
    case IO_PRINT:
      RET;

의미는 전적으로 두 번째 인터프리터인 evalio에 담기며, main은 예전의 evali+출력 패턴 대신 프로그램 전체에 대해 이를 한 번 호출한다. evalio는 eval과 같은 종류의 그래프를 순회하지만, 그 switch는 이 여덟 개 태그에 실제 동작을 부여한다 — 순차 실행이 C 제어 흐름으로 직접 풀려 쓰인다(3246e2a6:eval.c, 817–830행):

    case IO_BIND:
      CHECKIO(2);
      GCCHECK(1);
      x = evalio(ARG(TOP(1)));  /* first argument, unwrapped */
      f = ARG(TOP(2));          /* second argument, the continuation */
      n = new_ap(f, x);
      POP(3);
      goto top;
    case IO_THEN:
      CHECKIO(2);
      (void)evalio(ARG(TOP(1))); /* first argument, unwrapped, ignored */
      n = ARG(TOP(2));          /* second argument, the continuation */
      POP(3);
      goto top;

IO_BIND(>>=)는 왼쪽 계산을 재귀적으로 실행해 포장 풀린 결과를 얻고, 그 결과에 연속을 적용한 뒤, 그 결과가 무엇이든 그 위에서 다시 루프를 돈다(goto top) — 재귀적 하강이 아니라 진짜 트램폴린이므로, 긴 do-체인이 C 스택을 키우지 않는다. IO_THEN(>>)은 왼쪽 결과를 버린다는 점만 다를 뿐 같은 모양이다. 하스켈/컴파일러 쪽에도 "IO 타입"에 해당하는 것은 없다: EDo의 디슈가링(3장의 693dc6ce:Desugar.hs)은 어떤 M에 대해서도 M.do { x <- e; rest }를 App2 (Var "M.>>=") e (Lam x rest)로 바꾸며, 그것이 Exp.hs에 도달할 즈음에는 +나 error와 항 수준에서 구별되지 않는 평범한 Prim/Var 노드일 뿐이다. "이것은 IO다"라는 사실은 오직 evalio의 switch만 알고 있으며, 시스템 그 어디에도 없다 — nfib를 이미 돌렸던 것과 같은 아키텍처다.

같은 커밋이 한 가지를 더 추가한다: do-블록 안의 Let 문 (M.do { let x = e; rest })이다. 이는 3장의 식-수준 let이 그 시점까지 그랬던 것과 다를 바 없이, 평범하고 재귀적이지 않은 애플리케이션으로 디슈가된다(3246e2a6:Desugar.hs, 54행, 문맥을 위해 앞뒤 두 줄과 함께 인용):

dsExpr (EDo n (Bind i e : ss)) = App2 (Var (n ++ ".>>=")) (dsExpr e) (Lam i $ dsExpr (EDo n ss))
dsExpr (EDo n (Then   e : ss)) = App2 (Var (n ++ ".>>"))  (dsExpr e)         (dsExpr (EDo n ss))
dsExpr (EDo n (Let  i e : ss)) = App  (Lam i $ dsExpr (EDo n ss)) (dsExpr e)

이 줄은 이 장의 범위가 끝날 때까지 한 번도 바뀌지 않는다 — 식-수준 let을 무조건 재귀적으로 만드는 fe22efbd(아래)가 온 뒤에도. do-블록 안에 쓰인 let은 8c5fbb1a에 이르기까지 원래의 단순한, 재귀적이지 않은 람다 애플리케이션인 채로 남는다. 똑같이 쓰인 두 let이, 어느 문법적 위치에 있느냐에 따라 서로 다른 디슈가링 규칙을 갖는 것이다; 이 범위의 어떤 것도 둘을 통일하지 않는다.

그리고 정직하게 배포된 하나의 빈틈: IO_READFILE과 IO_WRITEFILE은 프리미티브 테이블에 선언되어 있고, 파싱되고, 출력도 되지만 — 그 evalio 본체는 스텁이다(3246e2a6:eval.c, 836–841행, 전문 인용):

    case IO_READFILE:
      CHECKIO(1);
      ERR("IO_READFILE");
    case IO_WRITEFILE:
      CHECKIO(2);
      ERR("IO_WRITEFILE");

콘솔 IO — getChar/putChar, stdin/stdout에 하드코딩됨 — 는 이 커밋에서 곧바로 동작한다. 파일 IO는 선언만 되어 있고, 처음 쓰이는 순간 죽도록 방치된다. 4c4229ec("Fix bugs and improve.", 버그 수정과 개선)와 7bb30b64("Minor improvements.", 소소한 개선)가 같은 날 저녁 뒤이어 올라간다 — 4c4229ec는 ELam을 다중 인자 람다로 일반화하고, 이름 붙은 Prelude 함수로 fix = primitive "Y"를 추가한다(let 자체가 하는 무언가와는 별개로, Y 태그로 가는 두 번째, 명시적인 경로다 — List.uhs의 새 map/filter/foldr가 곧바로 이를 사용하는데, 각각 fix (\ rec arg -> ...) 형태로 쓰였다. 평범한 재귀 let이 아직 언어 기능으로 존재하지 않기 때문이다) — 하지만 두 커밋 다 IO_READFILE/IO_WRITEFILE은 건드리지 않는다. 그것들은 다음 날 아침까지 고장 난 채로 남는다.

c5564e64: 파일을 지원하도록 IO를 다시 만들다

여기서는 타임스탬프가 중요하다: 3246e2a6은 2023-06-01 16:41에 커밋되고, c5564e64는 그다음 날 2023-06-02 09:38에 커밋된다 — "이틀"이 아니라 약 열일곱 시간이며, 오래된 일로 돌아온 것이 아니라 바로 다음 작업 세션이다. "Redo IO to allow files"(파일을 지원하도록 IO를 다시 만들다)는 예전엔 동작하던 무언가를 고치는 버그 수정이 아니다 — ERR() 스텁으로 배포됐던 두 프리미티브를 실제로 구현하려는 첫 시도다.

평면적 프리미티브 설계가 부딪히는 문제는 이렇다: 선언된 그대로의 IO.readFile/IO.writeFile에는 열린 파일을 담아 둘 자리가 없다 — "아직 다 읽거나 닫히지 않은, 열려 있는 파일"을 위한 런타임 표현이 없는 것이다. c5564e64는 그런 표현 하나를 추가한다: 새 노드 태그 HDL이며, 그 페이로드는 원시 C FILE *다(c5564e64:eval.c, 유니온이 HANDLE(p)로 접근되는 FILE *file 필드를 얻는다). INT/CHAR와 나란히 또 하나의 이미-값인 태그로 합류하는 것이다. stdin/stdout을 가정하던 모든 IO 프리미티브는 이제 명시적인 핸들 인자를 받는다 — IO.getChar/IO.putChar/IO.print는 hGetChar/hPutChar/hPrint가 되고, 파일을 여는 동작은 이런 핸들 노드 중 하나를 만들며, putChar/getChar/print는 내장된 stdin/stdout 노드에 h-접두사 프리미티브를 적용하는 얇은 래퍼로 살아남는다(c5564e64:IO.uhs, 인용):

openFile :: FilePath -> IOMode -> IO Handle
openFile p m =
  let
    n = case m of
          ReadMode -> 0
          WriteMode -> 1
          AppendMode -> 2
          ReadWriteMode -> 3
  in  (primitive "IO.open") p n

putChar :: Char -> IO ()
putChar = hPutChar stdout

writeFile :: FilePath -> String -> IO ()
writeFile p s = IO.do
  h <- openFile p WriteMode
  hPutStr h s
  hClose h

writeFile은 더 이상 프리미티브가 전혀 아니다 — 모든 것을 다 하는 프리미티브 하나 대신, openFile + hPutStr(그 자체는 mapM_ (hPutChar h)) + hClose, 세 프리미티브가 Prelude에서 합성된 것이다. IO_OPEN의 C 쪽은 fopen에 넘길 C 문자열이 필요한데, 런타임에는 문자열 타입이 없다 — String은 3장의 d91b9812/ddb1bb29 메커니즘이 만든, 관례로만 의미를 갖는 Char 노드의 스콧 인코딩 콘스-리스트다. c5564e64는 그 관례를 손으로 직접 순회하는 새 헬퍼 evalstring을 추가하는데, 각 콘스 셀을 강제 평가해 그 문자를 고정 크기 10000바이트 C 버퍼에 복사한다. 타협임을 스스로 인정하는 주석과 함께 (c5564e64:eval.c, 전문 인용):

/* XXX this is cheating, should use continuations */
char *
evalstring(NODEPTR n)
{
  size_t sz = 10000;
  char *p, *name = malloc(sz);

  if (!name)
    ERR("evalstring malloc");
  for (p = name;;) {
    if (p >= name + sz)
      ERR("evalstring too long");
    n = evali(n);
    if (TAG(n) == K)
      break;
    else if (TAG(n) == AP && TAG(FUN(n)) == AP && TAG(FUN(FUN(n))) == O) {
      *p++ = evalchar(ARG(FUN(n)));
      n = ARG(n);
    } else {
      ERR("evalstring not Nil/Cons");
    }
  }
  *p = 0;
  return name;
}

10000자를 넘는 파일 경로는 우아하게 처리되지 않고 그냥 ERR이다 — 실재하는, 그대로 남겨진 한계다. 이것은 축소판 재작성-기반 설계의 한 예다: 첫 시도는 그 아래에 표현 하나 없이 파일 IO의 모양 (readFile, writeFile, 프리미티브 둘)만 선언했고, 다음 날 아침 첫 실사용에서 그 사실을 발견했으며, 낡은 모양을 억지로 고쳐 동작시키는 대신 모양 자체를 교체했다 — 일급 값이 된 핸들, 콘솔/파일 연산 하나하나가 그 위에 매개변수화된 것으로.(readFile 자체는 같은 날 나중에 나오는 a3355632("More functions.", 함수 추가)에서야 다시 등장한다. openFile + 새로운 hGetContents로 만들어지며, 이는 IO.getChar가 CHAR 노드에 담긴 -1을 반환할 때까지 읽는다 — getc의 EOF 신호값 그 자체이며, 아무런 특별한 처리도 없이 ord c == negate 1이라는 정수 동등성 비교로 저장되고 비교될 뿐이다. 이 시스템 어디에도 파일 끝을 나타내는 별도의 표현은 없다.)

fe22efbd: 재귀 let, 그리고 "재귀였는가"라는 질문이 실제로 답을 얻는 곳

3장의 5ccb1b2a는 let을 엄격하게 순차적이고 재귀적이지 않은 람다 애플리케이션으로 디슈가하면서 "For now, just sequential bindings."라는 주석을 남긴다. fe22efbd("Make let bindings recursive, and optimise the non-recursive case", let 바인딩을 재귀적으로 만들고 비재귀 경우는 최적화)는 그 "일단은"이라는 말을 지킨다 — let으로 바인딩된 모든 이름은, 예외 없이, 이제 고정점 컴비네이터를 통해 자기 자신의 우변에서 보인다 (aux/y-combinator-and-recursion.md). 디슈가링은 바인딩마다 Y 하나를 끼워 넣는 식으로 바뀐다 (fe22efbd:Desugar.hs, 41행):

      def (i, d) a = App (Lam i a) (App (Comb "Y") (Lam i d))

let i = d in a는 (\i -> a) (Y (\i -> d))가 된다 — d가 실제로 i를 언급하든 안 하든 모든 바인딩이 이렇게 된다. 이는 aux 문서의 메커니즘(Y f = f (Y f), 스스로에게 고리를 건 그래프 셀 하나, eval.c의 case Y)을 일률적으로 적용한 것이며, 그 결과 압도적으로 흔한 경우인 비재귀적 let은, 무언가가 알아채지 않는 한, 필요 없는 Y 셀 값을 치르게 된다. 같은 커밋이 컴파일 후 정리 패스인 Exp.hs의 improveT에 규칙 딱 하나를 더 추가한다(fe22efbd:Exp.hs, 159–165행, 전문 인용):

improveT :: Exp -> Exp
improveT (App f a) =
  case (improveT f, improveT a) of
    (CK,                     CI) -> CT
    (CY,               App CK e) -> e
    (e1,                     e2) -> App e1 e2
improveT e = e

흥미로운 부분은 "d가 재귀적이었는가"가 여기서 어떻게 답을 얻는가다 — 디슈가링 전 표층 구문에 대한 자유 변수 스캔이 아니라, 브래킷 추상화 자신의 스마트 생성자들로부터 사후에, 공짜로 얻어진다. d가 i를 언급하지 않을 때 \i -> d를 브래킷 추상화하면 결국 abstract의 캐치올 케이스인 App CK d로 귀결된다 — 그리고 2장부터 있던 cS의 기존 규칙(cS (App CK e1) (App CK e2) = cK (App e1 e2))에 따르면 닫힌 부분항은 내부 모양이 무엇이든 단 하나의 최상위 K 래퍼로 무너진다. 그래서 비재귀 바인딩의 컴파일된 형태는 항상, 기계적으로, 어떤 d'에 대해 Y (K d')이 된다 — 그리고 Y (K e) = K e (Y (K e)) = e는 Y 자신의 정의식만으로, 순환 없이, 한 단계 만에 성립한다. improveT의 새 줄은 정확히 그 모양을 알아보고 곧바로 e로 바꾼다. 그래서 필요 없던 바인딩에 대해서는 런타임이 스스로에게 고리를 건 셀을 결코 만들지 않게 된다 — 재귀/비재귀의 구분이 선언되는 것이 아니라 발견되는 것이다.

967b92c0: 데이터 타입은 늘어도 컴비네이터는 그대로

967b92c0("More data types.", 데이터 타입 추가)는 Prelude.uhs에 Maybe와 Either를, String.uhs에 showMaybe/showEither/showBool을 추가한다 — 그 외에는 아무것도 건드리지 않는다(git show 967b92c0 --stat이 이를 확인해 준다: .uhs 파일 두 개뿐이고, eval.c, Desugar.hs, Exp.hs는 한 줄도 바뀌지 않았다). 그것이 가능한 이유는 data 선언이 컴파일되는 메커니즘이 2장 이후 바뀌지 않았고, 이 커밋이 그 메커니즘의 깔끔한 한 사례이기 때문이다. 이 커밋 시점에도 바뀌지 않은 Desugar.hs의 처리(967b92c0:Desugar.hs, 17–22행, 전문 인용):

dsDef (Data _ cs) = zipWith dsConstr [0..] cs
  where
    fs = [f i | (i, _) <- zip [0..] cs]
    dsConstr i (c, ts) = (c, lams xs $ lams fs $ apps (Var (f i)) (map Var xs))
      where xs = ["$x" ++ show (j::Int) | (j, _) <- zip [0..] ts]
    f i = "$f" ++ show (i::Int)

선언 순서상 인덱스 i, 필드 ts를 가진 각 생성자는, 자기 자신의 필드 값(xs)들 뒤에 그 타입의 생성자마다 하나씩인 연속(fs, cs의 각 항목에 대해 $f0, $f1, ... 하나씩) 인자를 받는 함수로 컴파일된다 — 이 모든 것이 채워지면 자기 자신의 연속인 f i를 자기 자신의 필드에 적용하고 다른 모든 연속은 그냥 무시한다. data Maybe a = Nothing | Just a는 Nothing을 \$f0 $f1 -> $f0로, Just를 \x $f0 $f1 -> $f1 x로 컴파일한다 — 그 타입의 값은 검사할 태그를 지니고 있는 것이 아니라, 그 자체가 디스패처다. 그 타입이 가진 생성자 개수만큼의 연속을 건네받기를 기다리다가 정확히 하나를 호출한다. 이것은 2장이 손으로 만든 튜플/리스트 생성자에 썼고 3장의 8939d55b/d91b9812가 튜플과 리스트 구문을 위해 재사용한 것과 같은 스콧 인코딩 트릭이다 — 967b92c0은 진짜로 새로운, 사용자가 직접 정의한 합 타입에 이를 적용하는 이 장 범위의 첫 커밋이며, Desugar.hs 아래로는 아무 비용도 들지 않는다. 그 메커니즘이 이미 완전히 범용이기 때문이다. ECase의 디슈가링은 그 쌍대다: 스크루티니를 케이스 팔의 본문들에, 연속으로서, 본문이 텍스트상 쓰인 순서대로 적용한다 — dsDef의 생성자-인덱스 번호 매김이 조용히 그 순서와 맞물릴 것을 전제하는 사실이다(맞물리지 않으면 어떻게 되는지는 "직접 해보기"의 연습 문제 1 참고).

d2956ee8: Y를 더 잘 최적화하기, 그리고 aux 문서가 남긴 약속 매듭짓기

fe22efbd의 improveT 규칙은 Y (K e)를 잡아내지만, 그 정확한 모양이 완전히 브래킷 추상화된 항의 최상위까지 구조적으로 온전히 살아남을 때에만 그렇다. improveT가 compile이 끝난 뒤 완성된 항 위에서 한 번만 실행되는 별도의 패스이기 때문이다(compileOpt = improveT . compile). 감싸는 람다 안에 놓인 let은 — 실제로는 파라미터 하나만 있는 최상위 함수도 이미 람다 하나이므로 사실상 거의 모든 let이 그렇다 — 그 모양으로 improveT에 도달하지 않는다. 바깥 람다 자신의 브래킷 추상화가 안쪽의 Y (K e)를 흡수해 cS/cB를 거쳐 바깥 함수를 만드는 과정에서 재구조화해 버리고, 그 과정이 끝날 즈음에는 그 항은 App CY (App CK e)가 아니라 B Y (B K e)가 되어 있다 — improveT의 유일한 규칙이 결코 매칭하지 못하는 모양이며, 그래서 Y 셀은 최적화되지 않은 채 런타임으로 넘어간다.

d2956ee8("Optimize Y better.", Y를 더 잘 최적화)는 이 인식을 브래킷 추상화 자신의 메커니즘 안으로 옮겨서 이 문제를 고친다. 재구조화가 일어나기 전, 컴파일 도중 아래에서 위로 발동하도록 만드는 것이다 — B 컴비네이터의 스마트 생성자인 cB에 새 줄 하나(d2956ee8:Exp.hs, 99–104행, 전문 인용):

cB :: Exp -> Exp -> Exp
cB CC          (App CC CI)    = CP -- Pair
cB (App CB CK) CP             = CO -- Cons
cB CY          (App2 CB CK e) = e  -- B Y (B K e) = e
cB CI          e              = e  -- B I e = e
cB e1          e2             = App2 CB e1 e2

직접 검증하면: 다음의 동일한 프로그램

module YOpt where
import Prelude
import IO

f :: Int -> Int
f x =
  let
    y = x + 1
   in y + y

main = print (f 10)

을 967b92c0(이 최적화 이전)과 d2956ee8(이후) 시점에서 각각 컴파일하면, f에 대해 서로 다른 두 컴파일 결과가 나온다:

967b92c0:  YOpt.f = B (S Prelude.+ I) (B Y (B K (Prelude.+ 1)))
d2956ee8:  YOpt.f = B (S Prelude.+ I) (Prelude.+ 1)

두 번째 것에서는 Y가 완전히 사라졌다 — 줄어든 게 아니라 제거된 것이다 — 그리고 두 버전 다 여전히 같은 답인 22로 실행되지만, d2956ee8 빌드는 더 적은 축약 횟수로 그렇게 한다(같은 계산에 대해 340 대 351, 둘 다 ./eval의 축약 카운터로 측정). f의 본문 안에 있는 비재귀 let은 다른 람다 아래에 아무리 깊이 중첩되어 있어도 더 이상 런타임에 스스로에게 고리를 건 그래프 셀을 요구하지 않는다 — 이는 aux 문서가 "커밋 d2956ee8 ... 이 구현을 다시 손본다. 무엇이 바뀌는지는 여기서 다룰 범위 밖이다; 4장이 다룬다."로 마무리하며 남긴 약속 그대로다. 같은 커밋은 또한 List.uhs의 map/filter/foldr와 IO.uhs의 mapM_를 4c4229ec/c5564e64가 써 오던 명시적인 fix (\ rec arg -> ...) 관용구에서 평범한 let rec = ... in rec로 옮긴다 — 라이브러리 코드는 이 최적화가 방금 공짜로 만든 언어 기능을, 그것을 공짜로 만든 바로 그 커밋에서 곧바로 쓰기 시작한다.

b1e84cf7과 8c5fbb1a: 직렬화와 역직렬화

Main.hs의 writeFile "out.comb" $ toStringP res(2장/3장의 메커니즘, 그대로)와 eval.c의 print/pp(축약 전후로 프로그램을 그대로 찍어내는 데 쓰임) 둘 다 이미 존재한다. IO.print(나중에 IO.serialize로 이름이 바뀐다)는 바로 그 print 함수를 런타임 IO 프리미티브로 배선한 것에 지나지 않는다 — 시작 시점에 컴파일된 프로그램 전체뿐 아니라, 어떤 살아 있는 그래프 값이든 동일한 텍스트 형식($name 프리미티브 참조, :N/_N 공유 라벨)으로 파일 핸들에 덤프한다. 그 배선 자체는 이 장의 범위 이전에 이미 존재했다 (IO.print/hPrint, c5564e64); 새로운 것은 핸들을 담은 값들과 접촉해도 살아남게 만드는 것, 그리고 역방향을 추가하는 것이다.

b1e84cf7("Handle serialization of standard handles.", 표준 핸들의 직렬화 처리)는 좁은 틈 하나를 고친다: 이 이전에는 어떤 HDL 노드든 print의 switch에 다다르면 그대로 오류였다(1a2f7b7a:eval.c, 468행: case HDL: ERR("Cannot serialize handles");). b1e84cf7은 잘 알려진 세 핸들만 C 포인터 동일성으로 정확히 알아보고, 대신 이름 붙은 프리미티브로 출력한다 (b1e84cf7:eval.c, 483–492행, 전문 인용):

  case HDL:
    if (HANDLE(n) == stdin)
      fprintf(f, "$IO.stdin");
    else if (HANDLE(n) == stdout)
      fprintf(f, "$IO.stdout");
    else if (HANDLE(n) == stderr)
      fprintf(f, "$IO.stderr");
    else
      ERR("Cannot serialize handles");
    break;

새로 openFile로 연 핸들은 여전히 직렬화할 수 없다 — 커밋 제목은 "handles"가 아니라 "standard handles"라고 말하고, 코드는 정확히 그와 일치한다.

8c5fbb1a("Add deserialization.", 역직렬화 추가)는 역방향 프리미티브인 IO.deserialize를 추가하는데, 시작 시점에 컴파일된 .comb 프로그램을 읽는 바로 그 함수인 parse()를, 실행 도중 살아 있는 파일 핸들 위에서 직접 호출함으로써 그렇게 한다(8c5fbb1a:eval.c, 965–970행, 전문 인용):

    case IO_DESERIALIZE:
      CHECKIO(1);
      hdl = evalhandle(ARG(TOP(1)));
      gc();                     /* parser runs without GC */
      n = parse(hdl);
      RETIO(n);

"실행 중인 프로그램의 그래프를 직렬화한다"는 것이 구체적으로 의미하는 바는 이렇다: 프로그램을 .comb 파일로부터 부트스트랩하는 바로 그 리더가, 시작 파일이 아닌 임의의 핸들을 가리킨 채, 실행 중인 프로그램 내부에서 프리미티브로서 도달 가능하다는 것이다. IO.serialize로 쓰이고 IO.deserialize로 다시 읽힌 값은, 2장이 프로그램 전체 링킹을 위해 확립한 것과 같은 :N/_N 라벨 구문을 통해 왕복한다 — 그리고 아래 "직접 해보기"가 그대로 보여주듯, 이것이야말로 진짜로 순환하는 값이 그 여정에서 살아남는 방법이기도 하다: :N/_N은 반복되는 부분항을 위한 최적화에 그치지 않고, 이 텍스트 형식이 스스로에게 고리를 건 그래프를 표현할 수 있는 유일한 방법이다.

하지만 parse()의 :/_ case들은 모두 전역 변수 NODEPTR *shared를 통해 읽고 쓰며, 그 전역 변수는 컴파일된 프로그램을 읽는 함수에 의해 시작 시점에 딱 한 번 할당되고, 0으로 채워지고, 해제된다 (8c5fbb1a:eval.c, 447–456행, 전문 인용):

NODEPTR
parse_top(FILE *f)
{
  shared = malloc(heap_size * sizeof(NODEPTR));
  for(int i = 0; i < heap_size; i++)
    shared[i] = NIL;
  NODEPTR n = parse(f);
  free(shared);
  return n;
}

IO_DESERIALIZE는 parse_top()이 아니라 parse()를 직접 호출한다 — 그래서 shared를 결코 재할당하지 않으며, main이 evalio를 실행하기 시작하기도 전에 이미 해제된 메모리를 역참조하는 것이다. :/_ 라벨이 전혀 없는 값(공유되는 것도, 순환하는 것도 없는)을 역직렬화하는 것은 shared[]를 전혀 건드리지 않으므로 잘 동작한다; 라벨을 하나라도 실제로 쓰는 것(순환하는 값은 예외 없이 모두 포함)을 역직렬화하는 것은 해제 후 사용이다. 직접 검증하면(직접 해보기, 연습 문제 3): 매번, 일관되게, 세그폴트가 난다.

같은 날 세 커밋이 더 올라가지만 이 장이 아니라 5장의 이야기다: ef082bbe/8c66d4dd/c0fb9a91는 uhs(컴파일러)와 eval(런타임) 양쪽에 독립적인 -v 상세 출력 플래그를 추가하고, b0915dcf는 라이브러리 .uhs 모듈들을 lib/ 하위 디렉터리로 옮기고 -i<dir> 모듈 검색 경로를 추가한다 — 둘 다 아래 "직접 해보기"에서 기계적으로 드러난다(eval은 이제 축약-횟수 트레일러를 찍으려면 -v가 필요하다; uhs는 Prelude/List/IO/String을 찾으려면 -ilib가 필요하다), 다만 이 장의 주제는 아니다.

왜 중요한가

이 장의 모든 확장은 1–3장이 이미 지어 놓은 아키텍처 위에, 그 모양을 바꾸지 않은 채 내려앉는다. IO a는 새로운 종류의 런타임 값이 아니다 — 새로운 태그 여덟 개 중 하나를 가진 그래프 노드일 뿐이고, 보통의 축약기에게는 불투명하며, 같은 그래프 위에 얹힌 두 번째 작은 인터프리터(evalio)에게만 의미가 있다. Maybe/Either 값 역시 새로운 종류의 런타임 값이 아니다 — 2장이 이미 튜플과 리스트를 위해 일반화해 둔 같은 스콧 인코딩 트릭을, 합 타입 두 개 더에, eval.c는 한 줄도 바꾸지 않고 적용한 것이다(967b92c0의 diff는 Prelude.uhs와 String.uhs뿐, 그 외엔 없다). "컴비네이터를 좀 더, 그리고(IO에 한해서만) 그 컴비네이터 일부에 의미를 부여하는 작은 인터프리터 하나 더" — 이 두 문장이 1장의 ccb31388 이후 계속 돌아가고 있는 핵심 루프 eval()을 건드리지 않고도 두 기능 모두를 흡수한다.

IO를 배포한 지 열일곱 시간 만에 다시 만든 것은, 재작성-기반 설계가 의도대로 작동할 때 어떤 모습인지 보여준다: 첫 시도는 아직 실제 표현으로 뒷받침할 방법을 알아내지 못한 파일 IO를 프리미티브 두 개 (readFile, writeFile)로 선언했고, 동작하는 척하지 않고 ERR() 스텁 그대로 배포했으며, 바로 다음 세션 — 파일이 실제로 필요해지자마자 — 낡은 모양(암묵적인 stdin/stdout을 가진 평면적 프리미티브)을 억지로 동작시키는 대신, 열린 파일을 담을 자리가 있는 새 모양(HDL 노드, 모든 프리미티브가 명시적 핸들을 받음)으로 설계 자체를 교체했다. 그리고 d2956ee8의 최적화는 더 작은 규모에서 같은 교훈을 준다: fe22efbd는 좁은 범위의 정리 하나를 이미 갖춘 채로 정확하지만 순진한 재귀 let(모든 바인딩에 예외 없이 Y)을 배포했고, d2956ee8는 그 정리를 일반화한 바로 그 자리에서, 곧바로 List.uhs/IO.uhs의 fix (\ rec -> ...) 관용구를 평범한 재귀 let으로 다시 썼다 — 새로 값싸진 기능이, 그것을 값싸게 만든 바로 그 커밋에서, 수작업 대체물을 대신할 만큼 신뢰받았다는 증거다.

실험 노트 여백

• 4c4229ec("Fix bugs and improve.")와 7bb30b64("Minor improvements.")는 3246e2a6과 같은 날 저녁, 각각 약 44분과 약 한 시간 뒤에 올라간다 — ELam이 다중 인자 람다로 일반화되고, 이름 붙은 함수로 fix = primitive "Y"가 추가되고, print/pp가 printrec 헬퍼를 공유하도록 리팩터링된다. 둘 다 IO_READFILE/IO_WRITEFILE 스텁은 건드리지 않는다; 그것들은 다음 날 아침의 c5564e64까지 기다린다.
• 8b39ba55("Remove junk.", 잡동사니 제거)는 Lam.hs를 통째로 지운다 — 233줄 전부, ccb31388부터 이어져 온(그 사이 6485a341과 a9178695 두 커밋에서만 가볍게 손댄) 손으로 내장한 하스켈 프로토타입 전체다. aux/y-combinator-and-recursion.md와 1–2장이 훑었던 그 코드는, 3장의 95ff6a34/b25d9fc8가 파서로 구동되는 Main.hs에 진짜 Prelude를 붙여 대체품을 마련한 이후로는 이미 대체된 것이었다. 이것은 어떤 기능과도 묶이지 않은 독립된 커밋이다 — 정리는, 그럴 만큼 쌓인 뒤에는, 그 자체로 일급 작업이 된다.
• do-블록 let(3246e2a6)과 식 let(5ccb1b2a, fe22efbd)은 똑같이 쓰이지만 이 장의 나머지 범위 내내 다르게 디슈가된다: fe22efbd의 무조건적인 Y-감싸기를 거치는 것은 식 형태뿐이다. M.do { ... } 안에 쓰인 let은 8c5fbb1a에 이르기까지 원래의 단순한, 재귀적이지 않은 람다 애플리케이션 그대로다. 이 범위의 어떤 것도 둘을 통일하지 않는다.
• a3355632의 readFile에는 파일 끝을 나타내는 별도의 값이 없다 — hGetChar는 원시 getc()가 반환한 값을 그대로, EOF일 때의 -1도 포함해서, 평범한 CHAR 노드에 담아 돌려주고, hGetContents는 ord c == negate 1일 때 멈춘다. C의 관례가 그대로 새어 나온다.

직접 해보기

기준 커밋: 8c5fbb1a("Add deserialization."). 관례(참고: 00-overview.md):

git worktree add /tmp/mhs-8c5fbb1a 8c5fbb1a
cd /tmp/mhs-8c5fbb1a

빌드 노트: 이 커밋의 Makefile에는 마침내 Main: 타깃이 있지만 (ghc Main.hs -o Main, 3246e2a6가 추가), 여전히 맨몸의 ghc 호출이라 2장과 3장의 빌드 노트가 다룬 것과 같은 GHC-9.8/mtl 문제를 겪는다. 이전 장들과 바이너리 이름을 일관되게 유지하기 위해 -o uhs로 손수 빌드한다:

nix develop $MICROHS -c ghc Main.hs -o uhs

처음에는 ParserComb.hs의 ap-not-in-scope 오류로 실패한다(2/3장과 동일); ParserComb.hs의 기존 import Control.Monad.State.Strict 뒤에 다음을 추가한다:

import Control.Monad(ap)

그다음 Compile.hs의 when-not-in-scope 오류가 난다(3장과 동일); Compile.hs의 기존 import Control.Monad.State.Strict 뒤에 다음을 추가한다:

import Control.Monad(when)

두 한 줄짜리 패치를 모두 적용하면 빌드가 성공한다(head/tail에 대한 무해한 -Wx-partial 경고는 생략):

nix develop $MICROHS -c ghc Main.hs -o uhs

[1 of 7] Compiling ParserComb       ( ParserComb.hs, ParserComb.o )
[2 of 7] Compiling Parse            ( Parse.hs, Parse.o )
[3 of 7] Compiling Exp              ( Exp.hs, Exp.o )
[4 of 7] Compiling Desugar          ( Desugar.hs, Desugar.o )
[5 of 7] Compiling Compile          ( Compile.hs, Compile.o )
[6 of 7] Compiling Main             ( Main.hs, Main.o )
[7 of 7] Linking uhs

런타임은 2/3장과 같은 방식으로 빌드한다:

nix develop $MICROHS -c gcc -Wall -O3 eval.c -o eval

이 커밋 범위에서 새로 생겨나 아래의 모든 명령에 영향을 주는 것이 두 가지 더 있다. b0915dcf는 Prelude.uhs/List.uhs/IO.uhs/ String.uhs를 lib/ 하위 디렉터리로 옮기고 -i<dir> 모듈 검색 경로(Compile.hs의 path 필드)를 추가했다 — 아래의 모든 ./uhs 호출은 import Prelude/import IO 등이 해석되도록 -ilib를 넘긴다. 그리고 ef082bbe/8c66d4dd/c0fb9a91은 eval 자신의 진단 트레일러(node size=..., N reductions, M GCs)를 2/3장에는 없던 -v 플래그 뒤에 가두었다 — 기본값으로는 이제 ./eval이 프로그램 자신의 출력만 찍고 그 외엔 아무것도 찍지 않는다; 축약 횟수를 보려면 -v를 넘긴다(./eval -v out.comb처럼).

연습 문제 1: 파일을 읽어 변형하고 결과를 출력하기

printf 'hello world\nfrom a file\n' > greeting.txt

cat > Shout.uhs <<'EOF'
module Shout where
import Prelude
import List
import IO

upc :: Char -> Char
upc c =
  case (ord c >= ord 'a') && (ord c <= ord 'z') of
    True  -> chr (ord c - 32)
    False -> c

main = IO.do
  s <- readFile "greeting.txt"
  putStr (map upc s)
EOF
nix develop $MICROHS -c ./uhs -ilib Shout
nix develop $MICROHS -c ./eval out.comb

hello world�from a file�

원하던 결과가 아니며, 위는 오타가 아니라 진짜 막다른 골목이다. upc의 case는 팔을 True 먼저, False 나중 순서로 쓰지만, Prelude.uhs는 data Bool = False | True를 선언하므로 False가 인덱스 0인 생성자, True가 인덱스 1인 생성자가 된다. 위 "무슨 일이 있었나"(967b92c0)에 따르면 dsExpr (ECase e as) = apps (dsExpr e) (map dsArm as)는 스크루티니를 팔들의 컴파일된 본문에 쓰인 순서 그대로, 위치에 따라 적용한다 — 쓰인 순서를 선언 순서와 맞춰 보는 검사는 어디에도 없다. True를 먼저 쓴다는 것은 처음 건네지는 연속이 True를 위한 것이라는 뜻이지만, Bool 값은 선언-인덱스 0의 연속 (False의 것)을 먼저 돌려받는다 — 그래서 upc의 조건이 실제로 무엇으로 평가되든, 모든 문자가 먼저 쓰인 팔을 실행하게 된다. 모든 공백(ord ' ' = 32)은 chr (32 - 32) = NUL 바이트를 얻고, 모든 줄바꿈(ord '\n' = 10)은 chr (10 - 32) = 바이트 0xEA를 얻는다 — 출력해 보면 눈에 띄게 잘못됐고, od로 확인된다:

$ nix develop $MICROHS -c ./eval out.comb | od -An -tx1 | head -1
 68 65 6c 6c 6f 00 77 6f 72 6c 64 ea 66 72 6f 6d

Bool의 실제 선언 순서 — False 먼저, True 나중 — 에 맞게 팔을 바꾸고 다시 빌드한다:

cat > Shout.uhs <<'EOF'
module Shout where
import Prelude
import List
import IO

upc :: Char -> Char
upc c =
  case (ord c >= ord 'a') && (ord c <= ord 'z') of
    False -> c
    True  -> chr (ord c - 32)

main = IO.do
  s <- readFile "greeting.txt"
  putStr (map upc s)
EOF
nix develop $MICROHS -c ./uhs -ilib Shout
nix develop $MICROHS -c ./eval out.comb

HELLO WORLD
FROM A FILE

연습 문제 2: out.comb에서 공유 라벨을 읽어 내기

연습 문제 1의 out.comb(고쳐진 버전)는 2792바이트, 한 줄, 81개의 최상위 정의(Prelude, List, IO, Shout가 함께 링크됨)로 되어 있다. 그 첫머리(바이트 그대로, ...는 네 번째 정의 이후 전부를 생략):

(($T :0 (($B $K) (($B $K) $K))) (($T :1 ($K (($B $K) $K))) (($T :2 ($K ($K $K))) (($T :3 ($K ($K $T))) (($T :4 $IO.>>=) ...

:0부터 :3, 그리고 :4($IO.>>=)는 소스-모듈 링킹 순서로 매겨진 최상위 정의들이다 — 정확히 2장의 17587b2d 라벨 체계 그대로다. 같은 파일 더 뒤쪽에서 가져온 구체적인 역참조 하나:

... (($T :16 (_7 _13)) (($T :17 (_8 _12)) (($T :18 (_9 _13)) ...

:16(알고 보면 IO.putChar의 stdout에 묶인 래퍼, 즉 putChar)은 _7 _13으로 정의된다 — 정의 7(IO.putChar)에 대한 참조를 정의 13(IO.stdout)에 대한 참조에 적용한 것이며, 본문을 반복하는 대신 그 둘의 라벨을 재사용한다.

이것이 어떤 종류의 "공유"인지 정확히 짚어 둘 필요가 있다. 이 장은 또 다른 종류의 공유도 만들어 내기 때문이다. 이 :N 라벨들은 하나하나 Main.hs 자신이(def ((_, e), i) r = App2 CT (Lbl i (subst e)) r, 다른 어딘가에서 실제로 참조되든 안 되든 모든 정의에 대해 zip ds' [0..]를 순회하며) 최상위 정의마다 하나씩, 무조건적으로 붙인다 — 컴파일 시점에 소스 순서로부터 결정되는 정적이고 위치적인 체계다. 이를 런타임 자신의 IO.serialize가 만들어 내는 것과 대조해 보자. IO.serialize는 find_sharing의 이중 순회 그래프 walk(처음 방문 시 표시, 두 번째 방문 시 공유로 승격)를 써서, 값을 출력하는 동안 실제로 두 번 이상 방문된 노드에만 라벨을 붙인다 — 소스 순서와는 무관하게, 동적으로, 그래프의 실제 모양으로부터 결정된다. 반복되는 부분 구조가 없는 평범한 리스트는 라벨을 전혀 얻지 않는다:

cat > PlainSer.uhs <<'EOF'
module PlainSer where
import Prelude
import List
import IO

main = IO.do
  writeSerialized "plain.ser" [1, 2, 3]
  v <- readSerialized "plain.ser"
  print v
EOF
nix develop $MICROHS -c ./uhs -ilib PlainSer
nix develop $MICROHS -c ./eval out.comb
echo "exit: $?"
cat plain.ser

(($O 1) (($O 2) (($O 3) $K)))
exit: 0
(($O 1) (($O 2) (($O 3) $K)))

(실행은 깨끗하게 종료되고, 런타임이 출력한 결과와 파일 내용 둘 다 같은 텍스트다. $O/$K뿐, :/_는 어디에도 없다.) 같은 let-바인딩된 리스트를 두 번 재사용해서, 그것을 쓰는 순회가 실제로 한 노드를 두 번 이상 방문하게 만들면, 라벨이 생긴다:

cat > ShareDemo.uhs <<'EOF'
module ShareDemo where
import Prelude
import List
import IO

main = IO.do
  let
    xs = [1, 2, 3]
   in writeSerialized "share.ser" (xs, xs)
EOF
nix develop $MICROHS -c ./uhs -ilib ShareDemo
nix develop $MICROHS -c ./eval out.comb
cat share.ser

(($P :99474 (($O 1) (($O 2) (($O 3) $K)))) ($I _99474))

라벨 하나, :99474(힙-셀 인덱스라서 이렇게 크고 임의적인 숫자다 — Main.hs가 매기는 작고 순차적인 :0/:1/...와는 전혀 다르다)가, 쌍의 순회가 처음 도달했을 때 리스트 xs를 표시한다; _99474는 두 번째로 도달했을 때인데, (xs, xs)의 두 반쪽 모두 같은 힙 셀이기 때문이다(하나의 let-바인딩된 썽크가 두 번 쓰인 것이지, 비슷하게 생긴 복사본 두 개가 아니다).

연습 문제 3: 매듭 묶어 보기

take는 72d4d093(List.uhs)부터 존재하므로, 순환 리스트를 유한한 앞부분을 통해 관찰할 수 있다:

cat > Knot.uhs <<'EOF'
module Knot where
import Prelude
import List
import String
import IO

main = IO.do
  let
    xs = 1 : xs
   in putStrLn (showList showInt (take 5 xs))
EOF
nix develop $MICROHS -c ./uhs -ilib Knot
nix develop $MICROHS -c ./eval out.comb

[1,1,1,1,1]

fe22efbd의 무조건적인 Y-감싸기는 함수 정의뿐 아니라 어떤 let에도 적용된다 — xs = 1 : xs는 aux/y-combinator-and-recursion.md의 nfib가 Y로 하는 것과 같은 방식으로 진짜로 스스로에게 고리를 건 그래프 셀을 만들고, take 5는 그 안으로 다섯 걸음 걸어 들어간 뒤 멈추며, 그 리스트에 끝이 없다는 사실을 결코 알아채지 못한다. xs를(take를 거치지 않고, 무한 구조 전체를) 직접 직렬화하면 순환이 라벨 구문 자체에 드러난다:

cat > KnotSer.uhs <<'EOF'
module KnotSer where
import Prelude
import List
import IO

main = IO.do
  let
    xs = 1 : xs
   in writeSerialized "knot.ser" xs
EOF
nix develop $MICROHS -c ./uhs -ilib KnotSer
nix develop $MICROHS -c ./eval out.comb
cat knot.ser

:99731 (($O 1) _99731)

이것은 종료된다 — find_sharing의 표시-기반 순회는 순환 그래프를 eval.c의 가비지 컬렉터가 항상 해 온 것과 같은 방식으로 다룬다. AP 포인터를 영원히 따라가는 대신 이미 방문한 노드에서 멈춘다 — 그리고 결과는 그 그래프가 정확히 무엇인지 말해 준다: 정의 :99731은 콘스 셀 (O 1 _99731) 그 자체이고, 그 안의 _99731은 지금 정의되고 있는 바로 그 노드를 도로 가리킨다. 똑같이 생긴 콘스 셀 둘이 아니라, 자기 자신을 가리키는 셀 하나다.

다시 읽어 들이는 순간, 이 커밋 범위는 활주로가 바닥난다. 바로 이 파일을 역직렬화하면 세그폴트가 난다:

cat > KnotRead.uhs <<'EOF'
module KnotRead where
import Prelude
import List
import String
import IO

main = IO.do
  ys <- readSerialized "knot.ser"
  putStrLn (showList showInt (take 5 ys))
EOF
nix develop $MICROHS -c ./uhs -ilib KnotRead
nix develop $MICROHS -c ./eval out.comb
echo "exit: $?"

exit: 139

(139 = 128 + SIGSEGV.) 위 "무슨 일이 있었나"에 따르면 이는 순환에 국한된 문제가 아니다 — :/_ 라벨 구문을 조금이라도 쓰면 마찬가지다. IO_DESERIALIZE는 parse()를 직접 호출하고, parse()의 :/_ case들은 parse_top()이 시작 시점에 딱 한 번 할당했다가 evalio가 실행되기도 전에 이미 free()한 전역 포인터 shared를 읽고 쓴다. 연습 문제 2의 순환 없는 share.ser를 같은 방식으로 시도해 봐도 확인된다 — 공유된 노드 하나, 순환 없음, 그런데도 같은 크래시:

cat > ShareRead.uhs <<'EOF'
module ShareRead where
import Prelude
import List
import IO

main = IO.do
  v <- readSerialized "share.ser"
  print v
EOF
nix develop $MICROHS -c ./uhs -ilib ShareRead
nix develop $MICROHS -c ./eval out.comb
echo "exit: $?"

exit: 139

이는 writeSerialized가 만든 앞서의, 공유되지 않은 [1,2,3] 값(그 파일에는 :/_가 전혀 없다 — 연습 문제 2 참고)이 아무 탈 없이 역직렬화되는 것과 대비된다. 8c5fbb1a 시점에서 IO.serialize는 진짜 순환을 파일에 쓸 수 있고 IO.deserialize는 프리미티브로서 존재하지만 — 라벨 메커니즘을 실제로 필요로 하는 것을 읽어 들이면 매번, 재현 가능하게, 런타임이 죽는다. 이것이 이 커밋 시점에서 이 기능의 실제 현재 상태이지, 가상의 이야기가 아니다.

정리한다:

git worktree remove --force /tmp/mhs-8c5fbb1a