lone lisp에서 제너레이터가 어떻게 도입되었는지, 구분된 연속체에서 코루틴과 세미코루틴을 거쳐 구현으로 이어지는 과정을 설명합니다.
구분된 연속체만으로는 충분하지 않았습니다. 더 있어야 합니다. 바로 제너레이터입니다.
이제 lone에는 전용 제너레이터 타입이 있습니다. 이것은 결국 lone lisp에서 반복의 기반이 될 것입니다.
(import (lone print set lambda generator yield) (math +))
(set f (lambda (x)
(yield (+ x 1))
(yield (+ x 2))
(yield (+ x 3))
x))
(set g (generator f))
(print (g 1)); 2
(print (g)); 3
(print (g)); 4
(print (g)); 1
(print (g)); error
제너레이터는 세미코루틴이라고도 알려져 있습니다. 오직 자기 자신의 호출자에게만 제어를 되돌려 주는 특수한 코루틴입니다. 왠지 지나치게 학술적인 구분처럼 들리지만, 실제로는 엄청난 단순화이며 덕분에 이해하기도 구현하기도 훨씬 쉬워집니다.
이제 구분된 연속체가 강력한 추상화라는 점에는 전혀 의심의 여지가 없습니다. 사실입니다. 제너레이터는 그 위에 구축할 수도 있었습니다. 거의 모든 종류의 효과 시스템이 그 위에 구축될 수 있다고 생각합니다.
하지만 _할 수 있다_고 해서 반드시 해야 하는 것은 아닙니다. _지나치게 강한 힘_이라는 것도 있습니다. 그리고 그 대가를 치르는 경우가 많습니다. 강력한 주문은 마나를 너무 많이 씁니다. 구분된 연속체도 예외는 아닙니다. 이 경우 그 대가는 memcpy입니다.
제너레이터의 목적은 값을 생성하는 것입니다. 즉 반복입니다. 루프입니다. 핫 패스입니다. 큰 리스트입니다. 무한한 리스트입니다. 계속 돕니다. 빙글빙글. 몇 번이고 다시. 영원히. 멈출 때까지. 아니면 멈추지 않거나요.
그러니 이 모든 한가운데에서 전체 스택을 이리저리 memcpy하는 습관을 들이지 않는 편이 좋겠다는 결론은 꽤 자명해 보입니다. lone이 속도의 전형적인 모범과는 거리가 멀다는 점은 제가 가장 먼저 인정하겠지만, 이건 제 제법 느슨한 성능 요구사항조차 충족하지 못합니다. 이걸로는 반복의 기반을 만들 수 없습니다.
구분된 연속체는 너무 강력합니다. 여기에 제약 장치를 좀 달아야 합니다. 먼저 구분된 연속체가 _멀티샷_이라는 사실부터 시작해 봅시다.
스택은 보류 중인 계산을 나타냅니다. 그 내용을 값으로 복사하면 즉시 연속체가 됩니다. 그러면 프로그램 어디에 있든, 그것들을 다시 스택 위로 복사하기만 하면 이전과 정확히 같은 상태로 모든 계산을 되돌릴 수 있습니다.
이렇게 한다고 해서 연속체가 소모되는 것은 아니라는 점에 주목하세요. 필요한 만큼 여러 번 계산을 복원할 수 있습니다. 재활성화될 때 복사되는 부분 스택 프레임입니다. 몇 번 복사할 수 있는지에는 제한이 없습니다.
연속체는 작고 재사용 가능한 계산 부분집합과 같습니다. 시간 속에 영원히 얼어붙은 스택의 한 조각입니다. 그것들은 복사하지 않는 한 아무것도 하지 않습니다. 진짜 컴퓨터 프로세서의 스택으로 복사해야만 합니다. 그것들만으로는 스스로 계산할 수 없습니다.
어쩌면 계산 능력을 높이면 이런 복사를 없앨 수 있을지도 모릅니다. 진짜 컴퓨터는 자기 자신의 스택을 가집니다. 연속체에도 자기만의 스택을 줍시다.
struct lone_lisp_generator {
struct {
struct lone_lisp_machine_stack own;
} stacks;
};
연속체가 수행하는 계산은 생성될 때 포착한 스택 부분집합에 의해 결정됩니다. 진짜 컴퓨터는 빈 상태로 시작합니다. 실행할 프로그램을 명시적으로 넣어줘야 합니다. 함수 하나면 되지 않을까요?
struct lone_lisp_generator {
struct lone_lisp_value function;
struct {
struct lone_lisp_machine_stack own;
} stacks;
};
이쯤 되면 결국 lone lisp 머신을 다시 발명하게 됩니다. 하지만 그럴 이유는 없습니다. 이 계산들은 병행적으로 실행되지만 병렬적으로 실행되지는 않습니다. 어느 시점이든 활성화된 머신은 하나뿐입니다. 서로 배타적이므로 자원을 공유할 수 있습니다. 특히 lisp 머신 자체의 자원을요. 필요할 때 스택을 교체해 넣고 빼면 됩니다. 머신 레지스터도 공유할 수 있습니다.
그리고 그렇게 코루틴이 탄생합니다. 본질적으로 마음대로 전환할 수 있는 별도의 스택입니다. 복사해서 올리는 것이 아니라 전환하는 것입니다. memcpy, 물러가라. 물러가라.
알고 보니 코루틴도 여전히 너무 강력합니다. 물론 이제는 스택을 자유롭게 전환할 수 있지만, 그건 곧 생각해야 할 완전히 새로운 종류의 문제가 생긴다는 뜻이기도 합니다. 이제 그 모든 독립적인 스택을 추적해야 합니다. 그중 어떤 것으로 전환할지 생각해야 합니다. 언제 전환할지도 생각해야 합니다. 머리가 아픕니다.
조금 더 얌전하게 만들어 봅시다. 인지 부하를 줄이기 위해, 코루틴이 어디로 전환할지를 미리 정해 두어서 프로그래머가 그 문제를 생각하지 않도록 하겠습니다.
struct lone_lisp_generator {
struct lone_lisp_value function;
struct {
struct lone_lisp_machine_stack own;
struct lone_lisp_machine_stack caller;
} stacks;
};
_세미_코루틴입니다. 자신이 어디로 제어를 되돌려 줘야 하는지 추적하는 평범한 코루틴입니다. 여기서는 자신을 호출한 코드입니다.
이것이 정확히 우리에게 필요한 것입니다. 사람들은 값을 얻기 위해 함수를 호출합니다. 호출한 쪽에게 값을 돌려주는 것은 지극히 자연스럽습니다. 세미코루틴은 값을 계속해서 반환할 수 있습니다.
이 스택들은 제너레이터 상태에 대해 알아야 할 모든 것을 드러냅니다. 스택 맨 위가 베이스와 같다면 제너레이터는 아직 실제로 실행되지 않은 것입니다. 맨 위가 null이라면 프로그램을 끝마친 것입니다. 맨 위가 베이스에서 벗어나 있다면 실행 중이거나 중단된 상태입니다. 호출자 스택이 없다면 중단된 상태입니다. 그렇지 않다면 실행 중입니다.
이 마법을 작동시키려면 약간의 손놀림이 필요합니다. 그 대부분은 제너레이터 호출을 처리하는 머신의 APPLICATION 단계에 있습니다.
먼저 몇 가지를 정리해 둡시다. 제너레이터가 유효한지 확인하는 간단한 검사를 수행하는 것부터 시작합니다.
case LONE_LISP_TYPE_GENERATOR:
generator = &lone_lisp_heap_value_of(lone, machine->applicable)->as.generator;
if (!generator->stacks.own.top) { /* generator is finished */ }
if (generator->stacks.caller.base) { /* generator is already running */ }
/* ... */
return true;
이미 끝난 제너레이터를 호출하는 것은 오류입니다. 이미 실행 중인 제너레이터를 호출하는 것도 마찬가지로, 어쩌면 그보다 더더욱 말이 되지 않습니다. 이 둘 중 하나라도 하면 프로그램은 충돌합니다.
다음 단계는 제너레이터의 스택을 머신에 교체해 넣는 것입니다. 그럼 머신의 스택은 어떻게 하느냐고요? 그냥 제너레이터 자체 안에 밀어 넣으면 됩니다. 네.
generator->stacks.caller = machine->stack;
machine->stack = generator->stacks.own;
이제 처리해야 할 경우는 두 가지입니다. 제너레이터를 시작해야 하거나, 다시 재개해야 하거나입니다.
if (generator->stacks.own.top == generator->stacks.own.base) {
/* start generator */
} else {
/* resume generator */
}
제너레이터를 시작하는 것은 충분히 쉽습니다. 머신이 제너레이터의 함수에 인자를 적용하도록 꾸미기만 하면 됩니다. 또한 별도로 처리되는 제너레이터 반환 단계도 설정합니다.
lone_lisp_machine_push_step(lone, machine, LONE_LISP_MACHINE_STEP_GENERATOR_RETURN);
machine->expression = lone_lisp_list_create(lone, generator->function, machine->list);
machine->step = LONE_LISP_MACHINE_STEP_EXPRESSION_EVALUATION;
이때 메타데이터를 설정하기에도 좋습니다. 프리미티브는 제너레이터를 찾아야 할 것입니다. 그것에 대한 참조를 담기 위해 구분자를 사용할 수 있습니다. 제너레이터 스택의 0번째 프레임으로 하나를 푸시합니다.
lone_lisp_machine_push(
lone,
machine,
(struct lone_lisp_machine_stack_frame) {
.type = LONE_LISP_MACHINE_STACK_FRAME_TYPE_GENERATOR_DELIMITER,
.as.value = machine->applicable,
});
이제 프리미티브는 그것이 어디 있는지 언제나 알 수 있습니다. 작동하는 해결책에 토를 달 수는 없지요.
제너레이터를 재개하는 쪽은 알고 보니 훨씬 더 단순합니다. 인자를 값으로 제너레이터의 스택에 흘려보내고 계속 진행하면 됩니다.
if (lone_lisp_list_has_rest(lone, machine->list)) { goto too_many_arguments; }
machine->value = lone_lisp_list_first(lone, machine->list);
machine->step = LONE_LISP_MACHINE_STEP_AFTER_APPLICATION;
제너레이터 반환은 별도의 머신 단계로 처리됩니다. 애플리케이션 단계에서 했던 일을 되돌리기만 하면 됩니다. 호출자의 스택을 복원한 다음, 그것을 가리키는 제너레이터의 모든 포인터를 null로 만듭니다. 끝났음을 표시하기 위해 맨 위 포인터를 null로 만듭니다.
case LONE_LISP_MACHINE_STEP_GENERATOR_RETURN:
/* ... */
generator->stacks.own.top = 0;
machine->stack = generator->stacks.caller;
generator->stacks.caller = (struct lone_lisp_machine_stack) { 0 };
/* ... */
머신이 제너레이터의 함수를 평가하는 동안 실행했던 애플리케이션 단계가 이미 반환값을 설정해 두었습니다.
generator 프리미티브는 꽤 지루합니다. 그저 제너레이터 값의 생성자일 뿐입니다. 존재 이유 전체가 이 한 줄을 실행하고 그 결과를 반환하는 것입니다.
generator = lone_lisp_generator_create(lone, function, 500);
이 매직 넘버는 그저 제너레이터의 스택 크기입니다. 공정한 주사위 굴림으로 골랐습니다. 무작위임이 보장됩니다. 어떤 엘리트 함수형 프로그래밍 비밀 결사에 가입한 것과는 전혀 관계없습니다. 여기엔 볼 것이 없습니다. yield 프리미티브가 훨씬 더 흥미롭습니다.
LONE_LISP_PRIMITIVE(lone_yield)
{
/* variables */
switch (step) {
case 0:
arguments = lone_lisp_machine_pop_value(lone, machine);
if (lone_lisp_list_destructure(lone, arguments, 1, &value)) {
value = arguments;
}
delimiter = &machine->stack.base[0];
if (delimiter->type != LONE_LISP_MACHINE_STACK_FRAME_TYPE_GENERATOR_DELIMITER) {
/* not inside a generator */ goto error;
}
generator = &lone_lisp_heap_value_of(lone, delimiter->as.value)->as.generator;
generator->stacks.own = machine->stack;
machine->stack = generator->stacks.caller;
generator->stacks.caller = (struct lone_lisp_machine_stack) { 0 };
lone_lisp_machine_push_function_delimiter(lone, machine);
lone_lisp_machine_push_value(lone, machine, value);
return 0;
default:
goto error;
}
error:
linux_exit(-1);
}
yield 프리미티브는 스택의 바닥에서 제너레이터 구분자를 찾습니다. 바로 그 이유 때문에 거기에 넣어 두었으니까요. 마지막 스냅샷 이후로 많은 일이 일어났으므로 제너레이터의 스택을 저장합니다. 실행이 돌아가야 할 곳이기 때문에 호출자의 스택을 복원합니다. 이미 예언된 바와 같이 말입니다. 기운을 다한 호출자의 스택은 메모리 페이지 아래로 무너져 내리며, 삭제되고 0으로 채워집니다. 그것이 바로 중단의 분명한 표식입니다. 그렇습니다. 모든 것이 제자리에 있습니다... 모든 것이 제자리에 있습니다...
이제 한 가지 임무만 남았습니다. 우리를 부른 그분, 모든 것을 소비하는 하나의 프로세스, 무한 자체를 삼키고도 더 갈망하며 헤아릴 수 없는 힘에 의해 멈춰질 때까지 영원히 루프를 도는 존재에게 성스러운 값을 의식적으로 바치는 일입니다.
자비가 우리에게 미소 지어 준다면, 데이터에 대한 그 갈증은 우리의 공물로 채워질 것이고, 우리는 평안히 몸을 눕히고 깊은 잠에 들 것입니다. 그렇지 않다면 우리는 다시 깨어나 고통받고 희생하며 또 하나의 모험, 또 하나의 성스러운 탐구에 나서 호출자를 위해 값에 비트를 불어넣게 될 것입니다. 그것이 상상의 수학마법 왕국이든, 비좁고 망가진 I/O의 터널이든, 녹이 슨 거대한 회전 자기 평원이든, 우리는 그 모든 것을 헤쳐 나갈 것입니다. 왜냐하면 _그것_이 우리의 의무이기 때문입니다.
... 흠.
그리고 바로 이렇게, lone에는 제너레이터가 생겼습니다.
반복을 위한 기반이 마련되었습니다. 이제 그 위에 쌓아 올릴 시간입니다.