lone에 한정 컨티뉴에이션을 도입하기까지의 구현 여정과 설계 결정, 명시적 제어 평가기/스택 재현, 프리미티브의 상태 머신화, return·예외·제너레이터의 토대, control/transfer로 구현한 한정 컨티뉴에이션과 호출 가능한 컨티뉴에이션까지를 자세히 다룹니다.
Lone가 이제 한정 컨티뉴에이션을 지원합니다! 오래 걸렸지만 드디어 왔습니다. lone이 가장 강력한 제어 메커니즘 중 하나를 지원하게 되었어요.
(import (lone print lambda control transfer) (math +))
(print
(+ 1
(control
(+ 98 (transfer 41))
(lambda (value continuation)
(continuation 1)))))
; 100을 출력
이 기능을 구현하면 예외 처리나 제너레이터 같은 많은 기능의 길이 열립니다. 하지만 개발을 계속 진행하기 전에, 이 기능을 어떻게 구현했는지 그 여정을 기록해두는 것이 가치 있겠다고 생각했습니다. 시작하기 전에 나 자신이 읽었으면 했던 글을 쓰고 싶습니다. 최소한, 훗날 이 모든 맥락을 머릿속에서 지워버린 미래의 나에게 문서로라도 남길 수 있을 테니까요.
Lone는 점점 복잡해지고 있었습니다. 이미 각종 데이터 타입, 각종 "컬렉션"들이 있었죠. 이것들을 구현하는 일은 꽤 재미있었습니다. 정말 많이 배웠습니다. 해시 테이블? 강력하죠.
하지만 제가 은근히 피하던 것이 하나 있었습니다. 바로 반복(iteration)입니다.
완전히 피한 건 아닙니다. 문제를 아예 회피하진 않았죠. Ruby에서 영감을 받아, 내장 모듈에 몇 가지 each 프리미티브를 추가했습니다.
(import (lone lambda print) (vector each))
(each [10 20 30]
(lambda (value)
(print value)))
each 함수가 내부적으로 동작하는 방식은 간단합니다. 벡터의 원소를 순회하면서, 제공된 함수를 각 원소 하나씩 인자로 넘겨 호출합니다.
LONE_LISP_PRIMITIVE(vector_each)
{
struct lone_lisp_value vector, f, entry;
size_t i;
/* 인자 언패킹 및 검사... */
LONE_LISP_VECTOR_FOR_EACH(entry, vector, i) {
arguments = lone_lisp_list_build(lone, 1, &entry);
lone_lisp_apply(lone, module, environment, f, arguments);
}
return lone_lisp_nil();
}
여기서 약간의 꼼수를 썼습니다. 실제 반복은 C 컴파일러에게 맡겨버린 것이죠. FOR_EACH 매크로는 그냥 전통적인 for 루프로 펼쳐집니다. C 코드가 lone을 대신해 순회하면서, 현재 원소를 제공된 함수에 적용합니다.
그러면 문제가 뭘까요? 이건 잘 동작합니다. 정말로 잘 동작하거든요!
문제는, 이게 lone의 한계를 너무 적나라하게 드러낸다는 데 있습니다. lone에는 프로그램의 제어 흐름을 다룰 능력이 없었습니다. 오직 함수 호출만 할 줄 알았죠. 그래서 반복을 함수 호출로 구현해야만 했던 겁니다.
while 같은 단순한 프리미티브조차 어떻게 구현해야 할지 상상도 할 수 없었습니다. 제너레이터같이 마법 같은 기능들은 말할 것도 없고요. 분명 처음 생각보다 훨씬 더 많은 노력이 필요하다는 사실이 명백해졌습니다.
그래서 반복에 관해 닥치는 대로 읽기 시작했습니다. 반복의 인체공학, 인터페이스 설계. 처음부터 올바르게, 제대로 만들고 싶었습니다. 뭘 찾아야 할지는 잘 몰랐지만, Ruby의 반복이 좋다는 건 알고 있었고, lone도 그만큼 좋아야 한다고 생각했죠.
검색하자마자 나온 첫 결과가 Bob Nystrom의 글이었습니다. 놀랍지도 않았습니다. 당연히 그가 반복에 대해 썼겠죠. 무려 두 편이나요. 먼저 그는 내게 가비지 컬렉션을 만드는 법을 가르쳐줬고, 이제는 바르게 반복하는 법을 가르쳐줄 차례였던 겁니다.
이 멋지게 쓰인 글들은 Ruby가 왜 좋은지를 정확히 보여줍니다. Ruby는 프로그래머가 블록에 값을 넘기는, 제가 만든 each처럼 깔끔한 코드를 작성하게 해줍니다. 그 방식이 합성에 실패할 때는 동시성이 구원투수로 등장합니다. Ruby는 어떻게든 반복 도중에 코드를 중단하고 제어권을 호출자에게 돌려준 다음, 호출자가 원할 때 다시 이어서 실행할 수 있게 해줍니다. 이렇게 하면 여러 반복 프로세스를 합성하거나, 교차 실행하거나, 심지어 중단할 수도 있습니다. 좋아요.
하지만 곧 경이로움은 공포로 바뀌었습니다. 이런 멋짐을 얻으려면 무엇이 필요한지 깨닫게 되었거든요. lone에는 당시 단 한 가지 없는 것이 필요했습니다. 바로 호출 스택에 대한 제어권이었죠. lone은 재귀적 트리-워킹 인터프리터였습니다. 호출 스택 역시 C 컴파일러가 관리하고 있었어요.
저는 이를 감수해야만 했습니다. lone의 재귀 평가기를 레지스터와 스택을 갖춘 제대로 된 머신으로 바꿔야 했습니다.
가능한 선택지를 검토했습니다. 유명한 프로그래밍 언어 VM들의 코드베이스를 탐색해봤습니다. 모두 바이트코드 VM을 갖고 있었죠. 예를 들어 제너레이터는 어떻게 구현하나 보니, 코드, 스택, 명령 포인터를 힙 할당된 호출 가능한 객체에 복사하더군요. 이해는 됩니다. 다만 lone에는 명령 포인터가 없습니다. 저는 Lisp 코드를 바이트코드로 변환하고 싶지 않았습니다. 리스트를 버리면 그게 진짜 Lisp일까요? 아니라고 생각했습니다.
그렇다면 변환 없이 이걸 어떻게 할 수 있을까요? PLDI 커뮤니티에 물어보기로 했습니다. Stack Exchange에 이 질문을 올렸고, Discord 서버에도 물었습니다. continuation passing style(CPS)에 관해 들었는데, 이것도 또 하나의 코드 변환이라 피하고 싶었습니다. 저는 정말로 그 리스트들이 좋거든요!
하지만 한 참고 자료가 계속 언급되었습니다. 바로 Structure and Interpretation of Computer Programs, 줄여서 SICP. Scheme 프로그래밍 언어의 그 책. 이 분야에서 가장 고전적인 책 중 하나입니다. 과학? 아니요, 마치 마법사가 주문을 외우듯, 컴퓨터는 우리가 프로그램을 새기는 룬 문자에 불과하죠. 그렇게 멋진 책이지만, 수학이나 공학 배경이 없는 제게는 쉽지 않았습니다. 몇 번이나 읽어보려 했지만 끝까지 읽은 적이 없거든요. 그런데 부끄럽게도, 제가 찾던 정답이 그 책에 내내 있었던 겁니다!
5.4장, 거의 마지막 부분에 있는 장인데, 명시적 제어 평가기(explicit-control evaluator), 즉 Lisp 표현식을 다른 것으로 변환하지 않고 그대로 평가하는 레지스터/스택 머신을 설명합니다.
장을 여러 번 읽으며 내용을 확실히 익히고, 어느 정도 이해가 섰다고 판단되자 전부 C로 번역하면서 제 필요에 맞게 수정했습니다.
Lone의 평가기는 특별 취급이 별로 없었습니다. if 같은 것은 전통적으로 평가기에서 특수 형태로 구현하지만, lone에는 FEXPR가 있어서 그것들을 내장 lone 모듈로 빼낼 수 있었습니다. lone에서는 프로그래머가 if를 언어 코어가 아닌, 아무 함수나 가져오듯이 import합니다.
그 결과 저는 Lisp의 진정한 본질이라 믿게 된 것을 구현한 머신을 얻게 되었습니다. 자기 자신을 평가하는 값들과, 함수 적용. 말 그대로 Lisp 머신이죠.
이 머신은 임의의 Lisp 표현식으로 시작해 단일 값으로 줄이려 합니다. 표현식이 숫자 같은 것이라면 더 이상 줄일 수 없습니다. 머신은 그냥 그 값을 반환합니다. 간단합니다.
expression_evaluation:
switch (lone_lisp_type_of(machine->expression)) {
case LONE_LISP_TYPE_NIL:
case LONE_LISP_TYPE_FALSE:
case LONE_LISP_TYPE_TRUE:
case LONE_LISP_TYPE_INTEGER:
machine->value = machine->expression;
/* ... */
심볼이라면 현재 환경에서 그 심볼의 값을 조회합니다. 이것도 쉽죠.
case LONE_LISP_TYPE_SYMBOL:
machine->value = lone_lisp_table_get(lone, machine->environment, machine->expression);
/* ... */
리스트를 만나야 비로소 본격적인 처리가 시작됩니다.
리스트는 (f x y z ...) 형태의 함수 적용을 나타냅니다. 먼저 해야 할 일은 함수 자체의 평가입니다. 보통 실제 함수 값을 가리키는 변수일 겁니다. 람다 표현식일 수도 있고요. 무엇이든 간에 평가가 필요합니다. 그래서 머신은 표현식 평가 로직으로 다시 들어가는데, 이번엔 f를 표현식으로 설정합니다.
case LONE_LISP_TYPE_LIST:
/* 현재 실행 컨텍스트를 스택에 저장... */
machine->expression = lone_lisp_list_first(machine->expression);
lone_lisp_machine_push_step(lone, machine, LONE_LISP_MACHINE_STEP_EVALUATED_OPERATOR);
goto expression_evaluation;
이게 끝나면 이제 인자를 어떻게 처리할지 결정해야 합니다. 이는 함수에 따라 다릅니다.
if (should_evaluate_operands(machine->applicable, machine->unevaluated)) {
/* 약간을 스택에 푸시... */
machine->step = LONE_LISP_MACHINE_STEP_OPERAND_EVALUATION;
} else {
machine->list = machine->unevaluated;
machine->step = LONE_LISP_MACHINE_STEP_APPLICATION;
}
일반 함수는 모든 인자를 평가합니다. 이런 경우 머신은 각 인자를 평가하며 결과를 리스트로 누적합니다. 이 리스트가 결국 함수에 전달됩니다. FEXPR는 이 단계를 건너뛰어, 평가되지 않은 인자들을 그대로 받습니다.
case LONE_LISP_MACHINE_STEP_OPERAND_EVALUATION:
/* 데이터를 스택에 푸시... */
machine->expression = lone_lisp_list_first(machine->unevaluated);
if (lone_lisp_list_has_rest(machine->unevaluated)) {
/* 더 많은 데이터를 스택에 푸시... */
lone_lisp_machine_push_step(lone, machine, LONE_LISP_MACHINE_STEP_OPERAND_ACCUMULATION);
} else {
/* Evlis 꼬리 재귀, 스택에 새 데이터 없음 */
lone_lisp_machine_push_step(lone, machine, LONE_LISP_MACHINE_STEP_LAST_OPERAND_ACCUMULATION);
}
goto expression_evaluation;
case LONE_LISP_MACHINE_STEP_OPERAND_ACCUMULATION:
/* 스택에서 데이터 팝... */
lone_lisp_list_append(lone, &machine->list, &head, machine->value);
/* 데이터를 다시 스택에 푸시... */
machine->step = LONE_LISP_MACHINE_STEP_OPERAND_EVALUATION;
/* ... */
case LONE_LISP_MACHINE_STEP_LAST_OPERAND_ACCUMULATION:
/* 스택에서 데이터 팝... */
machine->applicable = lone_lisp_machine_pop_value(lone, machine);
lone_lisp_list_append(lone, &machine->list, &head, machine->value);
machine->step = LONE_LISP_MACHINE_STEP_APPLICATION;
/* ... */
다음 단계는 실제로 인자들을 함수에 적용하는 것입니다.
Lisp 함수라면, 새로운 환경을 만들어 함수의 인자 리스트에 있는 변수들을 그 값에 바인딩합니다. 그래야 함수 본문에서 참조할 수 있으니까요. 이 환경은 함수의 클로저를 상속해, 함수가 정의될 때 살아있던 변수들도 참조할 수 있게 합니다. 표준적인 내용입니다. 이제 남은 일은 함수의 본문을 평가하는 것입니다.
switch (lone_lisp_heap_value_of(machine->applicable)->type) {
case LONE_LISP_TYPE_FUNCTION:
machine->environment = bind_arguments(
lone,
machine->environment,
machine->applicable,
machine->list
);
machine->unevaluated = lone_lisp_heap_value_of(machine->applicable)->as.function.code;
machine->step = LONE_LISP_MACHINE_STEP_SEQUENCE_EVALUATION;
/* ... */
프리미티브는 그냥 C 함수와 메타데이터입니다. 머신은 그것들을 호출하기만 하면 됩니다. Lisp 값을 C 변수에 자동으로 대입할 방법이 없으므로, 인자 리스트가 통째로 프리미티브에 전달됩니다. 프리미티브는 원하는 방식으로 값을 언패킹합니다.
바로 이 지점에서 C 함수에 관한 흥미로운 상황이 전개된다는 걸 깨달았습니다. 프리미티브가 Lisp로 다시 콜백하고 싶어할 거라는 사실입니다. 예를 들어 if는 머신에게 조건과 두 표현식 중 하나를 평가해달라고 해야 합니다.
처음엔 그리 나빠 보이지 않지만, 사실은 프로그램 흐름을 제어하려는 제 궁극적인 목표에 치명적입니다.
두 번째(그리고 더 깊은) 함의는, 중간의 어떤 코드가 외부(외부 언어) 함수로 재귀 호출할 경우, 그 결과로 생긴 부분 컨티뉴에이션을 다시 복구할 수 없다는 점이다.
Lisp 스택이 C 스택과 교차(interleave)되는 상황에서, 제가 어떻게 Lisp 스택을 캡처하고 조작할 수 있겠습니까? 불가능합니다.
그러니까, 재귀 평가기를 머신으로 바꿔 Lisp 스택을 노출해 조작하려고 그 고생을 해놓고, 결국 Lisp가 C를 호출하고, C가 다시 Lisp를 호출하는 초라한 상황에 빠진 겁니다.
명백히, 프리미티브가 머신으로 재귀해 들어가도록 놔 둘 수는 없습니다. 하지만 이게 어떻게 가능하죠? 많은 프리미티브가 그럴 수 있어야 기본 동작 자체가 가능한데요!
C 스택 전체를 저장하는 방법도 잠깐 생각해봤습니다. 곧 포기했지만, 그 전에 Stack Exchange에 질문을 올려 꽤 흥미로운 답을 얻었습니다. 가능은 하더군요. 현명한 선택은 아닐 테지만요. 보통 사람이라면 완전히 미친 짓이라고 여길 일을 저 말고도 시도한 사람이 있었다는 사실은 늘 위안을 줍니다.
됐습니다. C 스택 이야기는 그만. 프리미티브가 Lisp로 재귀 호출하도록 두면 안 됩니다. 무조건 안 됩니다. 이 제약 안에서 해결책을 찾아야 합니다.
영감은 제너레이터를 조사하며 읽었던 Stack Exchange 스레드를 떠올리면서 찾아왔습니다. 제너레이터란 사실, 언어가 상태 머신으로 변형한 지극히 정상적인 함수일 뿐이더군요.
struct fibState { a, b, position } int fib(fibState state) { switch (fibState.postion) { case 0: fibState.a, fibState.b = 1,2 while (a<100) { fibState.b, fibState.a = fibState.a, fibState.a+fibState.b // 컨텍스트 전환 fibState.position = 1; return fibState.a; case 1: } fibState.position = 2; return fibState.a-1 case 2: fibState.position = -1; } }mousetail, Programming Language Design and Implementation Stack Exchange, 2023년 5월 20일 14:06
초기 상태가 있고, 코드가 진행되며 새로운 상태로 전이하고, 그 과정에서 여러 값을 반환합니다. 구성에 따라 루프가 될 수도 있죠. 생각해보니, 이게 묘하게 Lisp 머신과 비슷합니다. 두 개념이 함께 작동할 수 있을까요?
답은 분명한 예(YES)였습니다! lone의 모든 프리미티브를 저 답변의 예시처럼 상태 머신으로 다시 썼습니다. 예컨대 앞에서 언급한 each 프리미티브는, 한때 비교적 단순한 함수였지만 다음과 같은 괴물로 변했습니다.
LONE_LISP_PRIMITIVE(vector_each)
{
struct lone_lisp_value arguments, vector, function, entry, expression;
lone_lisp_integer i;
switch (step) {
case 0: /* 초기화 후 반복 시작 */
/* 인자 언패킹 및 검사... */
i = 0;
iteration:
entry = lone_lisp_vector_get_value_at(vector, i);
/* (f (v i)) 평가 요청 */
expression = lone_lisp_list_build(lone, 2, &function, &entry);
lone->machine.step = LONE_LISP_MACHINE_STEP_EXPRESSION_EVALUATION;
lone->machine.expression = expression;
/* 지역 변수를 Lisp 스택에 푸시... */
return 1;
case 1: /* 반복 진행 또는 종료 */
/* Lisp 스택에서 지역 변수 복원... */
++i;
if (i < lone_lisp_vector_count(vector)) {
goto iteration;
} else {
break;
}
}
lone_lisp_machine_push_value(lone, machine, lone_lisp_nil());
return 0;
}
이제 머신은 프리미티브에게, 그 프로그램의 현재 단계(step)를 나타내는 정수를 넘깁니다. 프리미티브는 다시 머신에게, 프로그램의 다음 단계를 정수로 반환합니다. Lisp 인자와 반환값은 이제 Lisp 스택을 통해 주고받습니다.
호출 규약을 빼면, 특별한 일을 하지 않는 단순 프리미티브는 거의 달라진 게 없습니다. 초기 단계와 최종 단계가 모두 0입니다. 0을 받고, 일을 하고, 0을 반환하면 끝입니다. 단계 같은 건 신경 쓰지도 않아도 됩니다.
반면 특수 프리미티브는 머신과 인터페이스할 수 있는 능력을 얻습니다. 프리미티브가 표현식 평가 같은 일을 머신에게 시키고 싶을 때, 머신을 적절히 구성하고 0이 아닌 정수를 반환합니다. 이는 머신에게, 나중에 정확히 그 지점에서 자신을 재개하라고 알려주는 신호입니다. 머신은 부탁받은 일을 수행하고, 지정된 단계에서 프리미티브를 다시 호출해 재개시킵니다. 이렇게 하면 Lisp와 C 스택은 결코 교차하지 않습니다. C 스택이 쌓이는 걸 허용하지 않는 것이죠. C 함수는 Lisp로 다시 호출하는 대신 곧장 반환합니다.
제어의 역전. 머신을 호출하지 마세요. 머신이 여러분을 호출할 겁니다. 무엇이 필요한지 알려주면, 끝나고 나서 다시 연락이 올 겁니다.
혹은, 오지 않을 수도! 머신이 프리미티브를 유령처럼 씹고, 영원히 돌아오지 않을 수도 있습니다. 예전에는 프리미티브가 평가기 함수를 호출했고, C 컴파일러는 그 함수들이 반드시 결과를 반환하도록 보장해줬습니다. 이제는 그렇지 않습니다. 이제는 Lisp 머신이 제어권을 쥐었습니다.
case LONE_LISP_TYPE_PRIMITIVE:
/* 프리미티브는 인자 리스트를 스택에서 팝한다 */
lone_lisp_machine_push_value(lone, machine, machine->list);
machine->primitive.step = 0;
resume_primitive:
machine->primitive.step =
lone_lisp_heap_value_of(machine->applicable)->as.primitive.function(
lone, machine, machine->primitive.step
);
if (machine->primitive.step) {
/* 나중에 재개할 수 있도록 프리미티브 컨텍스트를 저장... */
lone_lisp_machine_save_primitive_step(lone, machine);
lone_lisp_machine_push_value(lone, machine, machine->applicable);
lone_lisp_machine_push_value(lone, machine, machine->environment);
lone_lisp_machine_push_step(lone, machine, LONE_LISP_MACHINE_STEP_RESUME_PRIMITIVE);
/* 프리미티브가 구성한 일을 하러 감... */
} else {
/* 프리미티브는 반환값을 스택에 푸시한다 */
machine->value = lone_lisp_machine_pop_value(lone, machine);
/* 다른 일을 하러 감... */
}
case LONE_LISP_MACHINE_STEP_RESUME_PRIMITIVE:
/* 프리미티브 컨텍스트 복원... */
machine->environment = lone_lisp_machine_pop_value(lone, machine);
machine->applicable = lone_lisp_machine_pop_value(lone, machine);
lone_lisp_machine_restore_primitive_step(lone, machine);
goto resume_primitive;
이 방식은 잘 동작하고, 놀랍도록 깔끔합니다. 물론 모든 프리미티브가 이상한 상태 머신으로 변하긴 했지만, 큰 문제는 아닙니다. 이걸 디버깅하다 보니 이제는 오히려 좋아지기 시작했달까요.
이 모든 고생을 다시 왜 했더라요? 아, 맞다. 스택. 바로 저기 있습니다. 구체화되어서요. 구조체 한가운데에 덩그러니 있습니다. 진짜로 포인터 한 칸 옆입니다. 밤새도록 산산이 부수고 넘칠 때까지요.
이걸로 뭘 할 수 있을까요? 무엇을 해야 할까요?
함수에서 일찍 반환할 수 있을까요?
(import (lone set print lambda return))
(set f
(lambda (x)
(return 42)
x))
(print (f 100)); 42
반환하려면, 스택에서 함수가 시작하는 위치를 찾아야 합니다. 스택에 어떤 마커를 두어야 합니다. 구분자(delimiter)입니다. 함수가 호출되기 전에 스택에 푸시되고, 함수 실행이 끝나면 팝되어야 합니다.
case LONE_LISP_TYPE_FUNCTION:
/* ... */
lone_lisp_machine_push_function_delimiter(lone, machine);
/* ... */
/* 머신은 결국 AFTER_APPLICATION 단계로 전이... */
case LONE_LISP_TYPE_PRIMITIVE:
lone_lisp_machine_push_function_delimiter(lone, machine);
/* ... */
if (machine->primitive.step) {
/* ... */
} else {
/* 프리미티브는 반환값을 스택에 푸시한다 */
machine->value = lone_lisp_machine_pop_value(lone, machine);
goto after_application;
}
case LONE_LISP_MACHINE_STEP_AFTER_APPLICATION:
after_application:
lone_lisp_machine_pop_function_delimiter(lone, machine);
/* ... */
이제 return은 이 마커를 찾을 때까지 스택을 언와인드하면 됩니다. 언와인드란, 찾고자 하는 프레임에 도달할 때까지 프레임을 팝하는 것입니다. 구분자가 스택 맨 위로 올라오면, 스택 규율은 프리미티브의 그것과 같아집니다. 반환값은 그냥 스택에 푸시하면 됩니다.
LONE_LISP_PRIMITIVE(lone_return)
{
struct lone_lisp_machine_stack_frame frame;
struct lone_lisp_value return_value;
return_value = /* 인자 언패킹... */;
lone_lisp_machine_pop_function_delimiter(lone, machine); // 이 프리미티브 자체의 구분자
/* 다음 함수 구분자까지 스택 언와인드 */
while (LONE_LISP_MACHINE_STACK_FRAME_TYPE_FUNCTION_DELIMITER !=
(frame = lone_lisp_machine_pop(lone, machine)).type);
lone_lisp_machine_push(lone, machine, frame);
lone_lisp_machine_push_value(lone, machine, return_value);
return 0;
}
이게 바로 호출 스택의 힘이군요...
저는 이 어두운 힘에 취해, 소박한 return 프리미티브에서 곧장 가장 강력한 제어 메커니즘 중 하나로 뛰어들었습니다. 한정 컨티뉴에이션입니다. 이게 모든 제어의 반지라고 하죠. 모든 제어를 구현하는 하나의 제어, 모두를 불러 모아, 스택을 언와인드로 묶어버리는.
하지만 먼저 순수한 컨티뉴에이션부터 이해해야 했습니다. 이게 대체 뭔가요? Scheme 언어에 대한 얕은 지식 덕분에 존재는 알고 있었지만, 제대로 이해하진 못했습니다. 위키백과의 예시는 이렇습니다.
(define (f return)
(return 2)
3)
(f (lambda (x) x)); 3
(call-with-current-continuation f); 2
무슨 일이 벌어지는지 바로 보이진 않습니다. 한 단계씩 풀어봅시다.
f는 함수를(정확히는 적용 가능한 값) 하나 받습니다. 일반 함수를 넘기면 특별한 일은 없습니다. 호출되고, 반환하고, 프로그램은 계속 진행됩니다.
call-with-current-continuation(보통 call/cc로 줄여 씁니다)에 f를 넘기면, 이름대로 현재의 컨티뉴에이션이 인자로 호출됩니다. 이 현재 컨티뉴에이션은 아주 특별한 호출 가능한 값인데, 이를 호출하면 어떻게든 call/cc 호출 자체가, 그 인자로 넘긴 값을 결과로 반환하도록 만듭니다.
정신이 뒤집힙니다. 이걸 어떻게 써야 할지 전혀 감이 오지 않습니다. 얼핏 보기에 앞서 만든 return 프리미티브와 비슷해 보이지만, 함수가 call/cc를 통해 전달되어야만 하나요?
커뮤니티가 또다시 구원해줬습니다. Discord에서 친절한 분이 한정 컨티뉴에이션에 관한 훌륭한 발표를 알려주셨습니다. 키노트는 Alexis King이 했는데, 앞서 언급한 Stack Exchange 질문 중 하나에 답을 달아주신 그분입니다. 전적으로 볼 가치가 있는, 믿을 수 없을 만큼 통찰력 있는 발표입니다. 정말 주제를 탈신비화해줍니다.
발표에서 call/cc도 잠깐 언급되는데, 얼마나 뒤엉켜 있고 뇌를 비트는 개념인지 설명합니다. 예외와 비슷한데 거꾸로라나요, 마치 catch가 throw 옆에 있는 것처럼? 그런가? 저도 확신은 없습니다.
그냥 call/cc는 잊읍시다. 고집할 이유는 충분히 많습니다. 컨티뉴에이션은 한정되어야 합니다. 이 정도는 배웠습니다.
한정 컨티뉴에이션과 예외 처리의 연결도 핵심 포인트입니다. 이건 통찰 중의 통찰, 이 수수께끼 같은 컨티뉴에이션을 대중에게 가져오는 아이디어입니다. 한정 컨티뉴에이션은 재개 가능한 예외(resumable exceptions)일 뿐입니다.
마치 파이썬이 이렇게 할 수 있는 것처럼요:
try:
print(10 + throw("error"))
except error, continuation:
continuation(10) # throw가 10을 반환하게 만들어, 20을 출력
throw는 try 블록을 빠져나와 except 블록으로 들어갑니다. except는 두 개의 인자(던진 값, 던진 순간의 컨티뉴에이션)를 받는 함수 같은 것입니다.
예외 핸들러 코드는 컨티뉴에이션을 무시해도 됩니다. 사실 대부분의 언어에서 예외를 처리할 때는 늘 그렇게 하죠.
하지만 호출 가능한 컨티뉴에이션 값이 또 다른 가능성을 열어줍니다. 핸들러 코드가 새로운 값을 시도 중인 코드에 다시 꽂아 넣을 수 있게 해줍니다. 마치 throw 프리미티브가 그 값을 반환한 것처럼요! 그래서 이 예시에서, throw가 try를 빠져나와 except로 제어권을 넘긴 뒤에, 예외 핸들러 코드는 새로운 값을 가지고 다시 try 블록으로 "돌아가" 마치 처음부터 예외가 없었던 것처럼 마무리할 수 있습니다!
정확히 말하면, 컨티뉴에이션을 호출한다고 해서 실제로 그 안으로 돌아가는 건 아닙니다. 예외 핸들러가 제어권을 잡았을 때쯤에는 try 블록은 이미 없습니다. 스택이 언와인드되어 코드 흐름은 완전히 다른 함수에 도달했죠. 컨티뉴에이션을 호출할 때 실제로 일어나는 일은, try 블록을 호출 지점으로 "가져오는" 것입니다.
try:
# 언와인드됨
except error, continuation:
try:
print(10 + 10)
except error, continuation:
continuation(10) # (이 경우) 도달 불가 코드
마치 throw 프리미티브가 호출 지점에서 모든 대기 중인 계산(try 블록, 예외 핸들러 등)을 캡처해 호출 가능한 값으로 구체화하고, 그 값을 호출하면 정확히 그 계산들로 치환되되, throw 프리미티브만 실제 값으로 바뀌는 것과 같습니다.
Lisp 머신으로 돌아가 봅시다. 이 머신은 실행 중에 많은 데이터를 스택에 푸시합니다. 그런데 스택에 올라가는 것이 데이터만은 아닙니다. 머신의 단계(step)도 스택에 푸시됩니다. 스택에는 특정 순서로 머신이 일을 하도록 지시하는 값들이 가득합니다. 스택은 일종의 코드입니다.
이 코드가 바로 "현재 컨티뉴에이션"을 이룹니다. 이 코드가 캡처되는 것입니다.
키노트의 또 다른 핵심 통찰: 컨티뉴에이션은 결국 스택을 memcpy로 복사했다 옮겨놓는 일입니다.
스택은 그냥 메모리입니다. 버퍼가 필요하죠.
struct lone_lisp_continuation {
size_t frame_count;
struct lone_lisp_machine_stack_frame *frames;
};
구분자도 필요합니다. return 프리미티브는 Lisp 머신이 관리하는 암묵적 구분자를 사용합니다. 일반적인 control 프리미티브는 구분자를 스스로 관리합니다.
LONE_LISP_PRIMITIVE(lone_control)
{
struct lone_lisp_value arguments, body, handler;
switch (step) {
case 0: /* 초기화 후 본문 평가 */
/* 인자 언패킹... */
lone_lisp_machine_push_value(lone, machine, handler);
lone_lisp_machine_push_continuation_delimiter(lone);
machine->step = LONE_LISP_MACHINE_STEP_EXPRESSION_EVALUATION;
machine->expression = body;
return 1;
case 1: /* 본문 평가 완료 */
lone_lisp_machine_pop_continuation_delimiter(lone);
lone_lisp_machine_pop_value(lone, machine); /* 핸들러 */
lone_lisp_machine_push_value(lone, machine, machine->value); /* 반환값 */
return 0;
default:
linux_exit(-1);
}
}
이 프리미티브는 핸들러 함수와 컨티뉴에이션 구분자를 스택에 푸시합니다. 그런 다음 코드 본문을 평가합니다. 끝나면 핸들러와 구분자를 버리고 결과만 반환합니다. 그러니 이 자체로는 특별한 일을 하지 않습니다. 그럴싸한 begin 프리미티브일 뿐입니다.
여기에 transfer 프리미티브가 등장합니다.
LONE_LISP_PRIMITIVE(lone_transfer)
{
struct lone_lisp_machine_stack_frame *delimiter, *frames;
struct lone_lisp_value arguments, value, continuation, handler;
size_t frame_count;
switch (step) {
case 0: /* 초기화, 컨티뉴에이션 캡처, 스택 리셋, 핸들러 평가 */
/* 인자 언패킹... */
/* 프리미티브 함수 구분자와 한 단계 건너뛰기 */
for (frame = lone->machine.stack.top - 1 - 2,
frame_count = 1;
frame >= machine->stack.base &&
frame->type != LONE_LISP_MACHINE_STACK_FRAME_TYPE_CONTINUATION_DELIMITER;
--frame, ++frame_count);
/* 핸들러 함수 복구 */
--frame; ++frame_count;
handler = frame->as.value;
/* control 프리미티브의 함수 구분자까지의 스택 프레임 복사(구분자 포함) */
--frame; ++frame_count;
frames = lone_memory_array(lone->system, 0, frame_count, sizeof(*frames));
lone_memory_move(frame, frames, frame_count * sizeof(*frames));
/* 현재 컨티뉴에이션을 구체화 */
continuation = lone_lisp_continuation_create(lone, frame_count, frames);
/* 스택을 control 프리미티브의 함수 구분자까지 되돌리기 */
lone->machine.stack.top = frame + 1;
/* (handler value continuation) 평가 설정 */
lone->machine.expression = lone_lisp_list_build(lone, 3, &handler, &value, &continuation);
lone->machine.step = LONE_LISP_MACHINE_STEP_EXPRESSION_EVALUATION;
return 1;
case 1:
/* 핸들러 평가가 끝났으니, 그 값을 반환 */
lone_lisp_machine_push_value(lone, machine, lone->machine.value);
return 0;
default:
linux_exit(-1);
}
}
첫 번째로 하는 일은 스택 프레임을 훑어보며 컨티뉴에이션 구분자를 찾는 것입니다.
구분자 바로 아래에는 control에 전달됐던 핸들러 함수가 있음을 압니다. 곧 호출할 것이므로 이 함수를 변수에 복구해 둡니다.
그런 다음 control 프리미티브의 함수 구분자를 찾고, 그 지점부터 스택의 맨 위까지의 모든 프레임을 힙에 할당한 버퍼로 복사합니다. 그리고 이 버퍼를 담는 Lisp 값을 만듭니다. 그게 바로 컨티뉴에이션입니다.
이제 스택을 함수 구분자까지 언와인드합니다. 방금 힙으로 복사한 스택 구간 전체를 팝하는 셈이죠. 이 시점에서 스택 규율은 control 프리미티브의 초기 상태와 같습니다. 정말로 그 안으로 되돌아온 겁니다! Lisp 머신의 관점에서 우리는 지금 control 안에 있으며, 값을 반환하면 마치 control이 그 값을 반환한 것처럼 보일 겁니다.
이제 transfer는 값, 컨티뉴에이션, 핸들러 함수를 갖게 되었습니다. 남은 일은 단 하나, (handler value continuation)을 평가하는 것입니다. 그 평가 결과가 control의 결과가 됩니다.
여기서 멈추고 이걸 예외 메커니즘이라고 불러도 됩니다. 컨티뉴에이션 캡처 코드를 지워버리면, 다른 언어의 예외와 정확히 같을 테니까요!
하지만 여기서 멈추지 않겠습니다. 거의 다 왔거든요!
지금 제 컨티뉴에이션 값은 단지 스택 프레임 배열을 담은 구조체입니다. 이는 새로운 값 타입으로, 시스템의 여러 부분에서 제대로 다뤄야 합니다. 특히 가비지 컬렉터에서요. 이걸 표시(mark)하고 스윕하는 데 실패하면 메모리 누수는 그나마 작은 문제일 겁니다.
Lisp 머신도 이 객체들을 어떻게 다룰지 배워야 합니다. 특히, 값이 컨티뉴에이션에 적용될 때의 동작을 배워야 하죠.
함수와 마찬가지로, 컨티뉴에이션은 자기 자신으로 평가됩니다.
case LONE_LISP_TYPE_CONTINUATION:
machine->value = machine->expression;
/* ... */
컨티뉴에이션은 적용 가능성 검사(applicable type test)를 통과합니다.
case LONE_LISP_MACHINE_STEP_EVALUATED_OPERATOR:
/* ... */
switch (lone_lisp_type_of(machine->applicable)) {
/* ... */
case LONE_LISP_TYPE_CONTINUATION:
break;
/* ... */
if (should_evaluate_operands(machine->applicable, machine->unevaluated))
/* ... */
컨티뉴에이션은 항상 인자를 평가한 뒤 받습니다.
static bool should_evaluate_operands(/* ... */)
{
/* ... */
switch (lone_lisp_heap_value_of(applicable)->type) {
/* ... */
case LONE_LISP_TYPE_CONTINUATION:
return true;
그리고 마침내... 어떤 값이 컨티뉴에이션에 적용되면, 머신은 캡처된 스택 프레임을 스택 위로 쏟아붓고, 인자가 그 계산 안으로 흘러가도록 레지스터를 설정합니다.
case LONE_LISP_MACHINE_STEP_APPLICATION:
switch (lone_lisp_heap_value_of(machine->applicable)->type) {
/* ... */
case LONE_LISP_TYPE_CONTINUATION:
if (lone_lisp_list_has_rest(machine->list)) { goto too_many_arguments; }
lone_lisp_machine_push_frames(
lone,
lone_lisp_heap_value_of(machine->applicable)->as.continuation.frame_count,
lone_lisp_heap_value_of(machine->applicable)->as.continuation.frames
);
lone_lisp_machine_restore_step(lone, machine);
machine->value = lone_lisp_list_first(machine->list);
컨티뉴에이션은 머신의 다음 단계가 스택 맨 위에 오도록 주의 깊게 캡처됩니다. 머신은 그 값을 복원하고, 그대로 실행을 이어갑니다. 끝나면 결과는 자연스럽게 호출자에게 흘러갑니다.
이렇게 해서, lone은 네이티브 1급 한정 컨티뉴에이션을 손에 넣었습니다!