표준 C99에서 대수적 효과와 핸들러를 라이브러리로 구현하는 방법을 설명하고, 실행 문맥을 스택/레지스터 캡처로 대응시키며, 꼬리 재개(tail resumption) 최적화를 위한 의미론 확장과 그 타당성을 제시한다.
Daan Leijen
Microsoft Research
daan@microsoft.com
초록. 우리는 표준적이고 이식 가능한 C99에서 대수적 효과(algebraic effects)와 핸들러(handlers)를 라이브러리로 구현하는 방법을 설명한다. 이 구현에서는 효과 연산(effect operation)을 일반적인 C 함수처럼 사용할 수 있다. 우리는 형식적 조작적 의미론(formal operational semantics)을 사용하여, 평가 문맥(evaluation context)이 특정 C 실행 문맥(C execution context)에 직접 대응하도록, 구현의 모든 단계를 안내한다. 마지막으로 꼬리 재개(tail resumption) 최적화를 위한 의미론의 새로운 확장을 제시하고 그 타당성을 증명한다. 이를 통해 꼬리 재개 연산의 성능이 두 자릿수 자수(orders of magnitude)로 향상되며(2.6GHz Core i7에서 초당 약 1억5천만 연산까지).
대수적 효과[34]와 핸들러[35,36]는 효과를 추론하기 위한 범주론(category theory)에서 비롯되었다. 효과는 인터페이스로서의 연산 집합을 가지며, 핸들러는 그 연산들의 의미를 부여한다. 어떤 자유 모나드(free monad)[2,17,38]도 대수적 효과 핸들러로 표현할 수 있다. 즉, 연산은 자유 모나드를 낳는 대수(algebra)를 기술하고, 핸들러는 그 대수에 대한 fold로서 의미를 제공한다. 이로 인해 대수적 효과는 표현력이 매우 높고 실용적이며, 보통은 언어 또는 컴파일러에 내장된 많은 제어 흐름 구성 요소를 기술할 수 있다. 예로는 예외 처리, 이터레이터, 백트래킹, async/await 스타일의 비동기 프로그래밍이 있다. 대수적 효과가 있으면 이 모든 추상화를 사용자가 라이브러리로 구현할 수 있다.
본 글에서는 C 자체에서(즉 C 라이브러리로서) 대수적 효과와 핸들러를 실용적으로 구현하는 방법을 설명한다. 특히,
표준적이고 이식 가능한 C99에서 대수적 효과와 핸들러의 전체 구현을 설명한다. 효과 연산의 사용은 일반적인 C 함수 호출과 동일하다. 스택은 항상 같은 위치에서 복원되며, C의 정상 의미가 보존된다.
대수적 효과의 의미론은 단순하지만, C에서의 구현은 직관적이지 않다. 우리는 형식적 조작적 의미론을 사용하여 C 구현을 모든 단계에서 안내한다. 특히 문맥 기반 의미론(context-based semantics)을 사용하며, 형식적 문맥이 특정 C 실행 문맥에 직접 대응한다.
최적화된 꼬리 재개를 기술하기 위한 형식 의미론의 새로운 확장을 제시하고 그 타당성을 증명한다. 이로써 꼬리 재개 연산의 성능이 두 자릿수 자수로 향상된다( Core i7에서 초당 최대 약 1억5천만 연산).
현재 시점에서 C에서 효과를 사용하는 것은 좋지만, 핸들러를 정의하는 것은 여전히 다소 번거롭다. C++ 래퍼를 제공하면 인터페이스를 개선할 수 있을 것이다. 지금은 이 라이브러리를 주로 라이브러리 작성자나 컴파일러를 위한 타깃으로 본다. 예를 들어 P 언어[11]는 검증 가능한 비동기 상태 기계를 기술하는 언어로, Microsoft Windows 8에 포함된 USB 장치 드라이버 스택의 핵심을 구현하고 검증하는 데 사용되었다. C로 컴파일할 때는 receive 문을 포함한 async/await 스타일 프로그래밍[5]을 가능하게 하기 위해 복잡한 CPS 스타일 변환[19,26]이 필요하다. 효과 라이브러리를 사용하면 이런 변환이 필요 없고 더 단순한 C 코드를 생성할 수 있다.
또한 우리는 이 라이브러리를 libuv[29](Node[41]의 기반 비동기 C 라이브러리)와 통합하고 있어, C 또는 C++에서 async/await 스타일 추상화[13,28]로 libuv를 직접 사용할 수 있도록 한다.
라이브러리는 오픈 소스 라이선스[25]로 libhandler라는 이름으로 공개되어 있다. 단순화를 위해 본 논문 설명에서는 많은 세부 사항과 오류 처리 등을 생략하지만, 나머지는 실제 구현을 매우 가깝게 따른다. 추가 상세 및 C++ 통합에 대해서는 확장 기술 보고서[27]를 참조하라.
여기서는 C에서 대수적 효과를 사용하는 방법을 짧게 개관한다. 효과를 언어가 네이티브로 지원하는 경우의 모습은 다른 연구[3,18,26,28,30]를 참조하라. 대수적 효과 이론은 모나드로 설명되기도 하지만, 본 글에서는 그에 못지않게 타당한 더 조작적인 관점을 사용하여, 효과를 **재개 가능한 예외(resumable exceptions)**로 본다. 따라서 먼저 효과 핸들러로 일반 예외를 구현하는 방법부터 설명한다.
예외를 대수적 효과로 구현하는 것은 간단하다. 먼저, 단 하나의 연산 raise를 가지는 새로운 효과 exn을 선언한다. 이 연산은 const char* 인자를 받는다.
DEFINE_EFFECT1(exn, raise)
DEFINE_VOIDOP1(exn, raise, string)
나중에 이 매크로들이 정확히 무엇으로 확장되는지 보이겠지만, 지금은 두 번째 줄이 일반 C 함수처럼 호출할 수 있는 새 연산 exn_raise를 정의한다는 것만 알면 된다. 예를 들어:
int divexn( int x, int y ) { return (y!=0 ? x / y : exn_raise("divide by zero")); }
효과 연산의 사용이 일반 C 함수 호출과 동일하므로, 사용자 입장에서 라이브러리를 쓰기 쉽다. 핸들러 정의는 조금 더 복잡하다. 다음은 raise 연산에 대한 가능한 핸들러 함수다:
value handle_exn_raise(resume* r, value local, value arg) { printf("exception raised: %s\n", string_value(arg)); return value_null; }
value 타입은 C에서 매개변수적 다형성을 흉내 내기 위해 사용되며, long long로 typedef되고 적절한 변환 매크로들과 함께 제공된다. 위 예에서 string_value는 exn_raise에 전달된 const char* 인자로 value를 되돌려 캐스팅한다.
새 연산 핸들러를 사용하는 것은 handle 라이브러리 함수를 사용한다. 약간 번거로운데, 모든 연산 핸들러의 테이블을 포함하는 핸들러 정의(handlerdef)를 구성해야 한다:
const operation _exn_ops[] = { { OP_NORESUME, OPTAG(exn,raise), &handle_exn_raise } };
const handlerdef _exn_def = { EFFECT(exn), NULL, NULL, NULL, _exn_ops };
value my_exn_handle(value(*action)(value), value arg) { return handle(&_exn_def, value_null, action, arg); }
핸들러를 사용하여 전체 예제를 실행하면:
value divide_by(value x) { return value_long(divexn(42,long_value(x))); }
int main() { my_exn_handle( divide_by, value_long(0)); return 0; }
이 프로그램을 실행하면 다음을 볼 것이다:
exception raised: divide by zero
핸들러 정의의 마지막 필드는 연산 목록이며 다음과 같이 정의된다:
typedef struct _operation {
const opkind opkind;
const optag optag;
value (opfun)(resume r, value local, value arg);
} operation;
연산 태그 optag는 연산을 유일하게 식별하며, opkind는 연산 핸들러의 종류를 기술한다:
typedef enum _opkind {
OP_NULL,
OP_NORESUME, // 절대 재개하지 않음
OP_TAIL, //resume를 꼬리 호출 위치에서만 사용
OP_SCOPED, //resume를 핸들러 내부에서만 사용
OP_GENERAL //resume가 일급 값
} opkind;
이 연산 종류는 최적화를 위해 사용되며, 연산 핸들러가 할 수 있는 일을 제한한다. 여기서는 OP_NORESUME을 사용하여 연산 핸들러가 결코 재개하지 않음을 표시했다. 다른 종류는 이후 절에서 예를 보겠다.
DEFINE_EFFECT 매크로는 새 효과를 정의한다. 예제에서 이는 대략 다음처럼 확장된다:
const char* effect_exn[3] = {"exn","exn_raise",NULL};
const optag optag_exn_raise = { effect_exn, 1 };
이제 효과는 effect_exn 배열의 주소로 유일하게 식별할 수 있고, EFFECT(exn)은 단순히 effect_exn으로 확장된다. 유사하게 OPTAG(exn,raise)는 optag_exn_raise로 확장된다. 마지막으로 예제의 DEFINE_VOIDOP1은 라이브러리 yield 함수 주변의 작은 래퍼로 확장된다:
void exn_raise( const char* s ) { yield( optag_exn_raise, value_string(s) ); }
이는 exn_raise에 대한 가장 안쪽(innermost) 핸들러로 “양보(yield)”한다.
예외 예제에서 본 것처럼, raise 연산의 핸들러는 resume* 인자를 받는다. 이는 연산이 발행된 지점에서 재개하는 데 사용된다. 이것이 대수적 효과의 진정한 힘(재개 가능한 예외로 볼 수 있는 이유)이다. 또 다른 예로, 주변 상태(ambient state)[28]를 구현해 보자.
DEFINE_EFFECT(state,put,get)
DEFINE_OP0(state,get,int)
DEFINE_VOIDOP1(state,put,int)
이는 연산 void state_put(int)와 int state_get()을 가진 새 효과 state를 정의한다. 다음처럼 다른 C 함수처럼 사용할 수 있다:
void loop() {
int i;
while((i = state_get()) > 0) {
printf("state: %i\n", i);
state_put(i-1);
}
}
이를 주변 상태라고 부르는 이유는, 전역/지역 상태가 아니라 가장 안쪽 state 핸들러에 동적으로 바인딩되기 때문이다. 이는 실제에서 흔한 패턴을 포착한다. 예를 들어 웹 서버를 작성할 때 “현재” 요청 객체는 보통 각 함수에 수동으로 전달해야 한다. 대수적 효과를 쓰면, 요청 효과(request effect)를 만들어 현재 요청에 접근하게 하고 모든 함수에 명시적으로 전달하지 않아도 된다.
state의 핸들러는 local 인자를 사용해 현재 상태를 저장한다:
value handle_state_get( resume* r, value local, value arg ) {
return tail_resume(r,local,local);
}
value handle_state_put( resume* r, value local, value arg ) {
return tail_resume(r,arg,value_null);
}
tail_resume(또는 resume) 라이브러리 함수는 yield 지점에서 연산을 재개한다. 인자는 (1) 재개 객체 r, (2) 새 로컬 상태 값 local, (3) yield 연산의 반환값이다. 여기서 handle_state_get은 현재 로컬 상태를 반환하고, handle_state_put은 null을 반환하지만 로컬 상태를 arg로 설정한 채 재개한다.
tail_resume는 꼬리 호출 위치에서만, 그리고 OP_TAIL 연산에서만 사용할 수 있지만, 일반 resume보다 훨씬 효율적이다(5절 참조).
한 번 방에 들어갈 수 있지만, 두 번 나올 수는 있다. — Peter Landin[22,23]
앞선 예제에서는 (예외처럼) 재개하지 않는 추상화와, (상태처럼) 한 번 재개하는 추상화를 보았다. 이런 추상화는 대부분의 언어에서 흔하다. 반면 한 번 이상 재개할 수 있는 추상화는 덜 흔하며, 보통 call/cc[40] 변종을 구현한 Lisp/Scheme 같은 언어에서 볼 수 있다.
여러 번 재개를 설명하는 좋은 예는 모호성(ambiguity) 효과다:
DEFINE_EFFECT1(amb,flip)
DEFINE_BOOLOP0(amb,flip,bool)
이는 bool amb_flip() 하나의 연산을 정의한다. 다음처럼 사용할 수 있다:
bool xor() {
bool p = amb_flip();
bool q = amb_flip();
return ((p || q) && !(p && q));
}
가능한 핸들러 하나는 매번 임의의 불리언을 반환한다:
value random_amb_flip( resume* r, value local, value arg ) {
return tail_resume(r, local, value_bool( rand()%2 ));
}
더 흥미로운 핸들러는 두 번 재개한다. 한 번은 true, 한 번은 false로 재개하여, 핸들러가 모든 결과의 리스트를 반환하게 할 수 있다:
value all_amb_flip( resume* r, value local, value arg ) {
value xs = resume(r,local, value_bool(true));
value ys = resume(r,local, value_bool(false)); //r에서 다시 재개!
return list_append(xs,ys);
}
resume의 결과도 리스트인데, 재개가 핸들러 아래에서 다시 실행되기 때문이다. xor를 all_amb 핸들러 아래에서 실행하면, 가능한 모든 결과 리스트를 얻으며 출력은 다음과 같다:
[false,true,true,false]
일반적으로 C에서 한 번 이상 재개하는 것은 위험할 수 있다. 가변 상태나 외부 리소스를 사용할 때 대부분의 C 코드는 최대 한 번만 실행된다고 가정한다. 예컨대 파일 핸들을 닫거나 어휘적 스코프를 벗어날 때 메모리를 해제한다. 이런 스코프 안에서 다시 재개하면 잘못된 결과가 나온다.
그럼에도 상태를 효과 핸들러로 관리하여 리소스 해제를 올바르게 처리하는 등으로 안전하게 만들 수 있다. 또한 async/await 인터리빙(interleaving) 구현에도 다중 재개가 필요하며, 이 경우 재개는 구성적으로 안전하도록 만들 수 있다.
최근 연구는 대수적 효과 위에 async/await 추상화를 구축하는 방법을 보였다[13,28]. 우리는 유사한 접근으로 C에서 libuv를 직접 프로그래밍할 수 있는 좋은 인터페이스를 구현하고 있다. 이는 아직 진행 중[25]이며, 여기서는 대수적 효과가 어떻게 이를 가능하게 하는지 보여주기 위해 기본 접근만 개략한다.
비동기 효과를 다음처럼 정의한다:
DEFINE_EFFECT1(async,await)
int await( uv_req_t* req );
void async_callback(uv_req_t* req);
async의 핸들러는 await만 구현하면 된다. 이 연산은 비동기 libuv 요청 객체 uv_req_t를 받는데, 여기에는 data 커스텀 필드에 재개를 저장하기만 한다. 하지만 스스로 재개하지는 않는다. 대신 바깥의 libuv 이벤트 루프로 직접 반환하며, 비동기 작업이 완료되면 등록된 콜백이 호출된다.
value handle_async_await( resume* r, value local, value arg ) {
uv_req_t* req = (uv_req_t*)ptr_value(arg);
req->data = r;
return value_null;
}
비동기 libuv 함수들이 모두 같은 async_callback을 콜백으로 사용하도록 한다. 이 콜백은 await가 data 필드에 저장한 재개를 호출한다:
void async_callback( uv_req_t* req ) {
resume* r = (resume*)req->data;
resume(r, req->result);
}
즉, 데이터 필드에 현재 상태를 인코딩하는 명시적 콜백 대신, 라이브러리가 제공하는 일급 재개가 현재 실행 문맥을 완전히 캡처한다.
이제 libuv 비동기 API 주위에 작은 래퍼를 써서 await를 사용할 수 있다. 예를 들어 비동기 파일 stat 래퍼는 다음과 같다:
int async_stat( const char* path, uv_stat_t* stat ) {
uv_fs_t* req = (uv_fs_t*)malloc(sizeof(uv_fs_t));
uv_stat(uv_default_loop(), req, path, async_callback); // 등록
int err = await((uv_req_t*)req); // 그리고 대기
*stat = req->statbuf;
uv_fs_req_cleanup(req);
free(req);
return content;
}
비동기 함수는 일반 함수처럼 호출할 수 있다:
uv_stat_t stat;
int err = async_stat("foo.txt", &stat); // 비동기!
printf("Last access time: %li\n", (err < 0 ? 0 : stat.st_atim.tv_sec));
이는 C에서 libuv를 훨씬 더 쾌적하게 사용하게 해 준다.
대수적 효과와 핸들러의 매력은 단순하고 잘 이해된 조작적 의미론을 가진다는 점이다. C 구현을 안내하기 위해 우리는 대수적 효과와 핸들러의 조작적 동작을 추론하기 적합한 작은 핵심 계산(core calculus)을 정의한다.
그림 1. λeff에서의 표현식 문법
표현식 e ::= ...
e(e) 적용(application)val x=e; e 바인딩(binding)handle h(e) 핸들러(handler)v 값값 v ::= x | c | op | λx.e
절(clause) h ::= return x→e | op (x)→e; h (단, op ∈/ h)
그림 2. 축약 규칙과 평가 문맥
평가 문맥:
E ::= [] | E(e) | v(E) | op (E) | val x=E; e | handle h(E)Xop ::= [] | Xop (e) | v(Xop ) | val x=Xop ;e | handle h(Xop ) if op ∈/ h축약 규칙:
c(v) −→ δ(c,v) if δ(c,v) is defined(λx.e)(v) −→ e[x↦v]val x=v; e −→ e[x↦v]handle h(v) −→ e[x↦v] with (return x→e) ∈ hhandle h(Xop [op (v)]) −→ e[x↦v, resume↦λy.handle h(Xop [y])] with (op (x)→e) ∈ h그림 1은 핵심 계산 λeff의 문법을 보인다. 이는 Leijen[26]의 정의와 동등하다. 기본 람다 계산에 핸들러 정의 h와 연산 op를 확장한 것이다. 이 계산은 정적 타이핑 규칙[18,26,37]으로 타입화할 수도 있다. 그러나 우리는 동적 비타입(untyped) 조작적 의미론도 줄 수 있는데, 이는 런타임에 명시적 타입이 없이도 대수적 효과를 구현할 수 있게 해 주므로 실무적으로 중요하다.
그림 2는 λeff의 의미론을 단 5개의 평가 규칙으로 정의한다. 잘 타입화된 프로그램은 이 의미론 아래에서 ‘잘못되지 않는다’는 것이 알려져 있다[26]. 우리는 두 평가 문맥을 사용한다. E는 호출-값(call-by-value) 람다 계산의 일반적인 문맥이다. Xop는 핸들러를 위한 문맥으로, 연산 op를 처리하지 않는 어떤 핸들러들 아래로도 평가가 내려가게 한다. 이는 특정 연산을 처리하는 ‘가장 안쪽 핸들러’가 선택됨을 간결히 표현한다.
E 문맥은 전체 평가 문맥을 간결히 캡처하며, 기본 축약 규칙들 위에 평가 함수를 정의하는 데 쓰인다: E[e] 7 −→ E[e′] iff e −→ e′. 처음 세 규칙 (δ), (β), (let)은 표준 호출-값 평가 규칙이다. 마지막 두 규칙은 핸들러를 평가한다. (return) 규칙은 인자가 완전히 평가되었을 때 핸들러의 return 절을 적용한다. (handle) 규칙은 대수적 효과 핸들러가 제한된 연속(delimited continuations)과 밀접히 관련됨을 보여 주는데, 그 이유는 handle h 아래의 제한된 ‘스택’ Xop [op(v)]를 캡처하기 때문이다.
Xop 문맥을 사용함으로써, op에 대한 절을 포함하는 가장 안쪽 핸들러만이 op(v)를 처리할 수 있음이 문법적으로 보장된다. 평가는 표현식 e로 계속되며, 매개변수 x를 v에 바인딩할 뿐 아니라 resume 변수를 연속으로 바인딩한다:
λy: handle h(Xop[y]).
resume를 적용하면 제공된 인자를 결과로 하여 Xop에서 평가가 계속된다. 또한 계속된 평가는 다시 핸들러 h 아래에서 일어난다.
C 구현은 형식 의미론을 가깝게 따른다. 우리는 문맥을 C의 현재 평가 문맥, 즉 호출 스택과 명령 포인터로 볼 수 있다. 이를 더 명시적으로 하기 위해 문맥을 호출 스택처럼 더 분명히 표현하는 점 표기를 사용한다. ·를 오른쪽 결합 연산자로 쓰고 e·e′ ≡ e(e′), E·e ≡ E[e]로 쓴다.
예를 들어 (handle) 규칙을 다음처럼 쓸 수 있다:
handle h · Xop · op(v) −→ e[x↦v; resume↦λy: handle h · Xop · y]
여기서 (op(x)→e) ∈ h.
이는 현재 “호출 스택” handle h · Xop 아래에서 op(v)를 평가함을 더 분명히 보여 준다( Xop 문법에 의해 h는 op에 대한 가장 안쪽 핸들러).
본 논문의 주요 기여는 이상화된 람다 계산의 조작적 의미론에서 C 라이브러리 구현으로 어떻게 내려오는지 보이는 것이다. 적용(application)과 let-바인딩 같은 일반 평가 규칙은 이미 C 언어의 일부다. 물론 C에는 일급 람다 표현식이 없으므로, 우리는 최상위 함수만 사용할 수 있다.
따라서 주된 과제는 (handle) 규칙을 구현하는 것이다:
handle h · Xop · op(v) −→ e[x↦v; resume↦λy: handle h · Xop · y]
여기서 (op(x)→e) ∈ h.
이를 위해 우리는 “handle h : Xop”를 현재 실행 문맥, 즉 스택과 명령 포인터로 볼 수 있다. C에서 실행 문맥은 현재 호출 스택과 현재 레지스터 문맥(명령 포인터 포함)으로 표현된다. 즉,
handle h 프레임을 푸시한다.op(v)를 만나면, E·handle h·Xop 호출 스택을 아래로 내려가면서 연산을 처리할 핸들러를 찾는다.handle h·Xop(호출 스택과 레지스터)을 resume 구조체로 캡처한다.h로 점프(그 실행 문맥 복원)하고, 연산 op, 인자 v, 캡처된 재개를 전달한다.이후 글에서는 스택이 위로 성장한다고 가정하며, 부모 프레임은 자식 프레임보다 “아래”에 있다고 가정한다. 실제로 대부분 플랫폼은 아래로 성장하는 스택을 갖지만, 라이브러리는 이를 동적으로 적응한다.
핸들러에 들어갈 때, 스택에 핸들러 프레임을 푸시해야 한다. 효과 핸들러 프레임은 다음과 같이 정의된다:
typedef struct _handler {
jmp_buf entry; // 핸들러로 돌아가기 위한 점프 지점
const handlerdef* hdef; // 연산 정의
volatile value arg; // 연산 인자가 여기로 전달됨
const operation* arg_op; // yield된 연산
resume* arg_resume; // 재개
void* stackbase; // 핸들러 함수 스택 프레임의 주소
} handler;
각 핸들러는 자신의 stackbase를 추적해야 한다. 연산이 재개를 캡처할 때는 그 핸들러의 stackbase까지의 스택만 저장하면 된다.
handle 함수는 stackbase를 기록하는 것으로 시작한다:
value handle( const handlerdef* hdef, value (action)(value), value arg ) {
void base = NULL;
return handle_upto( hdef, &base, action, arg );
}
스택 베이스는 지역 변수 base 자체의 주소를 취함으로써 얻는다. 이는 핸들러 프레임 바로 아래 주소에 대한 보수적 추정이다.
handle_upto는 noinline으로 표시하여 base 바로 위에 자신만의 스택 프레임을 갖도록 한다:
noinline value handle_upto( hdef, base, action, arg ) {
handler* h = hstack_push();
h->hdef = hdef;
h->stackbase = base;
value res;
if (setjmp(h->entry) == 0) {
// (H1): 레지스터 문맥 저장...
} else {
// (H2): 연산으로부터 longjmp로 여기 옴...
}
// (H3): 핸들러로부터 반환
return res;
}
이 함수는 먼저 그림자 핸들러 스택(shadow handler stack)에 새 핸들러를 푸시한다. 원칙적으로는 핸들러를 지역 변수로 선언하여 C 스택 자체를 “푸시”처럼 사용할 수도 있다. 그러나 나중에 보겠지만, 별도의 그림자 스택(스레드-로컬 핸들러 배열)을 유지하는 편이 더 편리하다.
그 다음 setjmp로 레지스터 문맥을 h->entry에 저장한다. 이는 나중에 연산이 longjmp로 핸들러로 돌아오는 데 사용된다. 최초 호출에서 setjmp는 항상 0을 반환하므로 (H1) 블록이 실행된다. longjmp되어 돌아오면 (H2) 블록이 실행된다.
여기서는 표준 C 준수 setjmp/longjmp 구현이 필요하다. 즉 setjmp가 필요한 레지스터와 플래그를 저장하고, longjmp가 이를 모두 복원해야 한다. 여기에는 스택 포인터와 명령 포인터가 포함되므로, longjmp는 사실상 setjmp 호출 지점으로 “점프”하게 된다.
불행히도 어떤 플랫폼에서는 자체 어셈블리 구현이 필요할 때가 있다. 예를 들어 Microsoft Visual C++(msvc) 컴파일러는 longjmp 시 C++ 코드의 소멸자/파이널라이저를 호출하기 위해 스택을 언와인드한다[33]. 또 어떤 플랫폼에서는 부동소수점 레지스터의 문맥이 올바로 저장되지 않는 경우도 있다(예: ARM Cortex-M의 라이브러리 코드). 다행히도 표준 준수 구현은 단순히 레지스터를 entry 블록으로 옮기고 다시 돌려놓으면 되므로 작성이 어렵지 않다. 32비트 x86에서의 setjmp 어셈블리 예는 [27]을 보라.
handle_upto의 (H1) 블록은 setjmp가 레지스터 문맥 저장을 마친 뒤 실행된다. 여기서는 인자를 넣어 action을 호출한다:
if (setjmp(h->entry) == 0) {
// (H1): 레지스터 문맥 저장 완료
res = action(arg);
hstack_pop(); // 핸들러 팝
res = hdef->retfun(res); // return 핸들러 호출
}
action이 정상 반환하면, 우리는 (return) 규칙에 해당한다:
handle h · v −→ e[x↦v] with (return x→e) ∈ h
핸들러 스택에 핸들러 h가 있고 결과값 v가 res에 있다. 진행하려면 return 핸들러 함수 retfun(즉 e)를 인자 res(즉 x↦v)로 호출하되, handle h 프레임을 팝한 후에 호출한다.
handle_upto의 (H2) 블록은 연산이 longjmp로 핸들러의 entry로 돌아왔을 때 실행된다:
else {
// 연산에서 longjmp로 여기 옴
value arg = h->arg;
const operation* op = h->arg_op;
resume* resume = h->arg_resume;
hstack_pop(); // 핸들러 팝
res = op->opfun(resume,arg);
}
이는 (handle) 규칙의 일부다:
handle h · Xop · op(v) −→ e[x↦v; resume↦λy: handle h · Xop · y]
이 시점에서, yield한 연산은 막 점프해 돌아왔고 longjmp에 의해 스택의 Xop 부분은 “팝”되었다. 또한 yield한 연산은 이미 재개 resume을 캡처하여 핸들러 프레임의 arg_resume 필드에 저장했고, 인자 v도 arg에 저장했다(4.2절).
우리는 이를 지역 변수로 옮기고 handle h 프레임을 팝한 뒤, 연산 핸들러 함수 e 즉 op->opfun을 호출하면서 재개와 인자를 전달한다.
연산 op(v) 호출은 yield(OPTAG(op), v) 함수 호출로 수행된다:
value yield(const optag* optag, value arg) {
const operation* op;
handler* h = hstack_find(optag,&op);
if (op->opkind==OP_NORESUME) yield_to_handler(h,op,arg,NULL);
else return capture_resume_yield(h,op,arg);
}
먼저 hstack_find(optag,&op)로 optag를 처리할 수 있는 핸들러를 핸들러 스택에서 찾는다. 이는 핸들러 프레임에 대한 포인터와 연산 설명에 대한 포인터를 &op로 돌려준다.
다음으로 첫 번째 최적화를 한다. 연산 핸들러가 재개를 필요로 하지 않는다면(즉 op->opkind==OP_NORESUME) 재개 인자로 NULL을 전달해 실행 문맥을 캡처하지 않아도 된다. 이 경우 즉시 yield_to_handler를 호출한다. 그렇지 않으면 capture_resume_yield로 먼저 재개를 캡처한다.
yield_to_handler는 핸들러로 longjmp하는 역할만 한다:
noreturn void yield_to_handler( handler* h, const operation* op, value oparg, resume* resume ) {
hstack_pop_upto(h); //h까지 핸들러 프레임 팝
h->arg = oparg;
h->arg_op = op;
h->arg_resume = resume;
longjmp(h->entry,1);
} // (H2)로 점프
여기까지로는 resume 없는 효과 핸들러를 구현했다. 진정한 힘은 (handle) 규칙이 다음을 캡처하는 일급 재개에서 나온다:
resume ↦ λy: handle h · Xop · y
즉 현재 실행 문맥 handle h · Xop를 캡처해야 나중에 결과 y로 그 문맥에서 재개할 수 있다. C에서 실행 문맥은 핸들러까지의 스택과 레지스터다. 이는 capture_resume_yield로 수행한다:
value capture_resume_yield(handler* h, const operation* op, oparg ) {
resume* r = (resume*)malloc(sizeof(resume));
r->refcount = 1;
r->arg = lh_value_null;
// 재개 지점 설정
if (setjmp(r->entry) == 0) {
// (Y1) 레지스터 문맥을r->entry에 저장
void* top = get_stack_top();
capture_cstack(&r->cstack, h->stackbase, top);
capture_hstack(&r->hstack, h);
yield_to_handler(h, op, oparg, r);
}
else {
// (Y2) (R1)에서 longjmp로 재개됨
value res = r->arg;
resume_release(r);
return res;
}
}
재개 구조체는 다음처럼 정의된다:
typedef struct _resume {
ptrdiff_t refcount; // 재개는 힙 할당
jmp_buf entry; // 재개가 캡처된 점프 지점
cstack cstack; // 캡처된 호출 스택
hstack hstack; // 캡처된 핸들러 스택
value arg; //resume인자를 전달하는 필드
} resume;
할당 후 참조 카운트를 1로 초기화하고 레지스터 문맥을 entry에 기록한다. 그 다음 (Y1)에서 C 호출 스택과 핸들러 스택을 캡처한다.
핸들러 스택 캡처는 쉽고 capture_hstack(&r->hstack,h)가 h까지(포함) 모든 핸들러를 r->hstack 필드로 복사한다(필요한 할당 포함).
C 호출 스택 캡처는 더 미묘하다. 현재 스택의 top을 구하기 위해 지역 변수 주소를 바로 쓰는 방식(예: void* top = (void*)⊤)은 일반적으로 안전하지 않다. 컴파일러가 top 위에 임시 값을 둘 수도 있고, System V amd64 ABI처럼 레드존(red zone)을 두어 스택 포인터 위 영역에 레지스터 스필을 허용하기도 한다[32, 3.2.2]. 대신 자식 함수를 호출하여 그 안에서 스택 top을 캡처하는 보수적 추정치를 얻는다:
noinline void* get_stack_top() { void* top = (void*)⊤ return top; }
그러나 위 코드는 일반적으로 틀릴 수 있다. 최적화 컴파일러는 지역 주소 반환이 C에서 정의되지 않은 동작(UB)임을 감지할 수 있어, 어떤 값이든 반환해도 된다. 실제로 clang/gcc는 최적화가 켜지면 0을 반환하기도 한다.
트릭은 지역 스택 주소를 별도 항등(identity) 함수로 “통과”시키는 것이다:
noinline void* stack_addr( void* p ) { return p; }
noinline void* get_stack_top() { void* top = NULL; return stack_addr(&top); }
이는 현재 컴파일러에서(공격적 최적화에서도) 기대대로 동작한다.
캡처해야 하는 스택 조각은 핸들러의 stackbase(하단 추정치)부터 top(상단 추정치)까지 정확히 사이 영역이다. capture_cstack(&r->cstack,h->stackbase,top)는 cstack을 할당하고 C 스택에서 그 구간을 memcpy로 복사한다.
이제 재개 구조체는 제한된 실행 문맥을 완전히 캡처했다. 우리는 앞의 yield_to_handler로 핸들러로 점프하면서 연산/인자/재개를 전달할 수 있다.
재개를 캡처했으니, 이제 재개하는 방법을 정의할 수 있다. 조작적 의미론에서 재개는 단지 람다식이다:
resume ↦ λy: handle h · Xop · y
재개는 단순 적용이며,
E·resume(v) −→ E·handle h · Xop · v
이다.
C 구현에서는 캡처된 스택을 주 스택들에 푸시하고, 재개 인자 v를 재개의 arg 필드로 전달하는 것을 의미한다.
하지만 캡처된 스택을 일반 호출 스택 위에 그냥 푸시할 수는 없다. C에서는 스택의 지역 변수가 종종 참조로 자식 함수에 전달된다. 예:
char buf[N];
snprintf(buf,N,"address of buf: %p", buf);
만약 snprintf 내부에서 연산이 호출되어 스택이 캡처되었다고 하자. 재개 시 스택을 다른 시작 위치로 복원하면 스택 상대 주소가 모두 틀려진다. 예컨대 buf는 스택 내 다른 위치에 놓이지만 snprintf에 전달된 주소는 그대로이기 때문이다.
따라서 우리는 항상 정확히 같은 위치에서 스택을 복원해야 하며, 이를 위해 C 구현에서 추가 작업이 필요하다. 특히 (H2)로 돌아온 연산 핸들러가 재개를 호출하면, 원래 캡처된 스택을 복원하기 위해 연산 핸들러의 현재 스택 일부를 덮어써야 한다.
이 상황을 그림 3이 보여준다. 재개 r은 핸들러 h까지의 스택을 캡처했다. h에서 stackbase로 가는 화살표는 현재 스택 포인터 아래를 가리킨다. r에 저장된 스택을 복원하면 줄무늬 영역이 덮어써진다. 즉,
h 바로 아래에 특별한 fragment 핸들러 프레임을 핸들러 스택에 푸시한다. h가 반환하면 fragment로부터 원래 스택 부분을 복원할 수 있다.재개 구현은 다음과 같다:
value resume(resume* r, value arg) {
fragment* f = (fragment*)malloc(sizeof(fragment));
f->refcount = 1;
f->res = value_null;
if (setjmp(f->entry) == 0) {
// (R1) 레지스터 문맥 저장
void* top = get_stack_top();
capture_cstack(&f->cstack, cstack_bottom(&r->cstack), top);
hstack_push_fragment(f);
hstack_push_frames(r->hstack);
r->arg = arg;
jumpto(r->cstack, r->entry);
}
else {
// (R2) (H3)에서 fragment로 점프되어 옴
value res = f->res;
hstack_pop(hs);
return res;
}
}
capture_cstack는 복원에 의해 덮어써질 수 있는 현재 스택 부분을 fragment에 저장한다. 이는 연산 핸들러의 스코프를 벗어난 재개(즉 비-scoped 재개)의 경우에만 “빈” 스택을 캡처할 수 있다.
jumpto는 C 스택과 레지스터 문맥을 복원하여 실행 문맥을 되살린다. 구현은 다음 절에서 논의한다.
먼저, fragment 프레임을 고려하도록 handle_upto를 보강해야 한다. 각 핸들러는 자신 아래에 fragment 프레임이 있는지 확인해야 한다. 있다면 재개의 일부였으며 fragment에 저장된 원래 C 스택 부분을 복원해야 한다. (H3)에 다음을 추가한다:
noinline value handle_upto( hdef, base, action, arg ) {
...
// (H3): 핸들러로부터 반환
fragment* f = hstack_try_pop_fragment();
if (f != NULL) {
f->res = res;
jumpto(f->cstack,f->entry);
}
return res;
}
여기서도 같은 jumpto로 실행 문맥을 복원한다. fragment를 통한 언와인딩은 스택을 올바로 복원하기 위해 주의가 필요하다. 자세한 내용은 [27]을 보라.
jumpto는 C 스택과 레지스터 문맥을 받아, 원래 위치에 C 스택을 복원하고 longjmp한다. 다음처럼 직접 구현할 수는 없다:
noreturn void jumpto( cstack* c, jmp_buf* entry ) { // 잘못된 구현!
memcpy(c->base,c->frames,c->size);
longjmp(*entry,1);
}
memcpy가 jumpto의 현재 스택 프레임(예: entry 변수)을 덮어쓸 수 있기 때문이다. 또한 일부 플랫폼은 스택 “위쪽”으로 점프하려 하면 중단(abort)하는 longjmp 구현을 사용한다[15].
해결은 jumpto를 두 부분으로 나누는 것이다. 먼저 jumpto에서 복원할 스택과 여분을 담을 만큼 충분한 스택 공간을 예약한다. 그 다음 실제 복원을 수행하는 헬퍼 함수 _jumpto를 호출한다. 이 함수는 이제 덮어써지지 않을 안정적인 스택 프레임을 갖는다:
noreturn noinline void _jumpto( byte* space, cstack* c, jmp_buf* entry ) {
space[0] = 0;
memcpy(c->base,c->frames,c->size);
longjmp(entry,1);
}
noreturn void jumpto(cstack cstack, jmp_buf* entry ) {
void* top = get_stack_top();
ptrdiff_t extra = top - cstack_top(cstack);
extra += 128;
byte* space = alloca(extra);
_jumpto(space,cstack,entry);
}
앞과 마찬가지로 명확성을 위해 오류 처리를 생략하고 스택이 위로 성장하며 extra가 항상 양수라고 가정했다. alloca로 충분한 스택 공간을 예약하며, space에 실제로 기록하여 최적화 컴파일러가 사용되지 않는 변수로 제거하지 못하게 한다.
연산 비용을 고립시켜 측정하기 위해, work 함수를 호출하는 단순 루프를 사용한다. 네이티브 C 버전은:
int counter_native(int i) {
int sum = 0;
while (i > 0) { sum += work(i); i--; }
return sum;
}
효과 버전은 상태 효과로 카운터를 구현하며, 루프 반복마다 두 번의 효과 연산을 수행한다:
int counter() {
int i; int sum = 0;
while ((i = state_get()) > 0) {
sum += work(i);
state_put(i - 1);
}
return sum;
}
work 함수는 상대적 성능을 측정하기 위한 기준을 제공한다. 네이티브 루프는 현대 CPU에서 거의 “공짜”에 가깝다(레지스터의 루프 변수를 거의 다루지 않으므로). work는 제곱근을 수행한다:
noinline int work(int i) { return (int)(sqrt((double)i)); }
이는 효과 연산이 제곱근 명령에 비해 얼마나 비싼지 비교할 기준이다. 그림 4는 64비트 플랫폼에서 100,000 반복 실행 결과를 보여 준다. 효과 버전은 약 300배 느리고 초당 약 130만 개 효과 연산을 수행한다. 느린 이유는 많은 재개와 fragment를 캡처해 메모리를 많이 옮기고 할당자에 압력을 주기 때문이다.
여러 최적화가 가능하다. 우선 OP_NORESUME처럼 재개가 필요 없는 연산은 상태를 캡처할 필요가 없어 longjmp 수준으로 싸질 수 있다.
또 하나의 매우 중요한 최적화 기회는 꼬리 재개다. 벤치마크에서 각 재개는 fragment에 continuation을 저장해 다시 돌아온 뒤, 아무 일도 하지 않고 즉시 반환한다. 이로 인해 fragment 프레임이 핸들러 스택에 계속 쌓인다.
실제로 대부분의 연산 구현은 resume을 꼬리 호출 위치에서 사용한다. 그리고 다행히도 이 경우는 매우 잘 최적화할 수 있어 두 자릿수 자수의 성능 향상을 얻는다.
이 절에서는 꼬리 재개를 더 효율적으로 구현할 수 있다는 관찰을 확장한다. 특히 (op (x) → resume (e)) ∈ h 꼴의 연산 핸들러를 고려하자. 여기서 resume ∈/ fv(e)이다. 그러면:
handle h · Xop · op(v) −→
resume(e)[x↦v; resume↦λy: handle h · Xop · y]
−→ (resume가 e 안에 없으므로)
(λy: handle h · Xop · y)(e[x↦v])
−→* (e[x↦v]가 v′로 계산될 때)
(λy: handle h · Xop · y)(v′) −→ handle h · Xop · v′
결국 같은 스택 handle h · Xop로 끝나므로, 문맥 handle op · Xop를 캡처/복원할 필요가 없고, 연산 표현식 e를 일반 함수 호출처럼 직접 평가할 수 있다.
그러나 스택을 그대로 두면 e[x↦v] 평가 중에 yield되는 연산이 handle h · Xop 내의 어떤 핸들러에 의해 처리되지 않도록 특별한 주의가 필요하다.
이런 꼬리 재개 표현식을 handle op · Xop 스택 아래에서 평가하되, 그 스택의 핸들러들이 연산을 처리하지 못하도록 하기 위해 새로운 yield 프레임 yield op(e)를 도입한다.
직관적으로 handle op · Xop · yield op 형태의 스택 조각은 무시될 수 있다. yield op는 연산 핸들러를 찾을 때 op ∈ h인 핸들러 h까지는 건너뛰어야 함을 지정한다.
그림 5에 이를 형식화했다. yield 표현 아래에서 평가하는 새로운 평가 문맥 F를 도입하고, Xop와 유사하지만 yield 프레임이 지정한 핸들러들을 건너뛰는 새로운 핸들러 문맥 Yop를 정의한다. 그림 5의 축약 규칙은 이 축약이 yield 프레임을 포함할 수 있음을 표시하기 위해 새로운 화살표 ¯−→를 사용한다.
처음 다섯 규칙은 기존 규칙과 동등하지만, (handle) 규칙은 이제 Xop 대신 Yop를 사용하여 handle h · Yop · yield op 시퀀스(그리고 op ∈ h)에 포함된 핸들러들을 건너뛰면서 op에 대한 가장 안쪽 핸들러를 선택한다.
최적화의 핵심은 (thandle) 규칙이다. resume가 꼬리 위치에서만 쓰일 때,
yield op 프레임만 푸시하면 되고,resume ∈/ fv(e)이므로 재개 캡처 및 resume 바인딩을 생략할 수 있다.이제 “바인딩되지 않은” 꼬리 재개는 (tail) 규칙에서 명시적으로 처리된다. yield op 프레임을 팝하고 원래 스택 아래에서 평가를 계속하면 된다.
그림 5. yield 프레임을 포함하는 최적화 축약 규칙
평가 문맥:
F ::= [] | F(e) | v(F) | op(F) | val x=F; e | handle h(F) | yield op(F)
Yop ::= [] | Yop(e) | v(Yop) | op(Yop) | val x=Yop; e | handle h(Yop) if op ∈/ h | handle h(Yop′[yield op′(Yop)]) if op′ ∈ h
새 축약 규칙:
(handle) handle h · Yop · op(v) ¯−→ e[x↦v, resume↦λy.handle h · Yop · y] with (op(x)→e) ∈ h
(thandle) handle h · Yop · op(v) ¯−→ handle h · Yop · yield op · resume(e)[x↦v] with (op(x)→resume(e)) ∈ h and resume ∈/ fv(e)
(tail) handle h · Yop · yield op · resume(v) ¯−→ handle h · Yop · v with (op ∈ h)
(δ), (β), (let), (return) 규칙은 그림 2와 동일하다.
새 최적화 규칙이 원래 의미론을 보존하길 원한다. 즉 ¯−→로 축약했을 때, 원래의 −→로 축약해도 같은 결과가 나와야 한다.
이를 위해 표현식 e와 문맥 F, Y에 대한 ignore 함수를 정의한다. 이 함수는 op ∈ h인 모든 handle h · Yop · yield op 부분식을 제거하여, 확장된 표현식을 원래 표현식으로 바꾸고 F를 E로, Yop를 Xop로 바꾼다.
이를 통해 타당성을 다음처럼 정의할 수 있다:
정리 1 (타당성). F·e ¯−→ F·e′이면 F·e −→ F·e′이다.
증명은 [27]에 있다.
꼬리 재개 구현에는 연산 yield 부분만 수정하면 된다:
value yield(const optag* optag, value arg) {
const operation* op;
handler* h = hstack_find(optag,&op);
if (op->opkind==OP_NORESUME) yield_to_handler(h,op,arg,NULL);
else if (op->opkind==OP_TAIL) {
hstack_push_yield(h); // yield 프레임 푸시
value res = op->opfun(NULL,op,arg); // 연산을 직접 호출
hstack_pop_yield(); // yield 팝
return res;
}
else return capture_resume_yield(h,op,arg);
}
꼬리 재개(tail_resume로 꼬리 호출로 끝남)를 약속하는 새 연산 종류 OP_TAIL을 추가한다. 그런 다음 yield 프레임을 푸시하고 연산을 직접 호출한다. 연산은 최종 결과를(꼬리 재개로) 반환하고, 우리는 yield 프레임을 팝한 뒤 계속 실행한다. 스택 캡처나 메모리 할당을 완전히 피한다.
이 경우 tail_resume는 단순 항등 함수다:
value tail_resume(const resume* r, value arg) { return arg; }
실제 구현에서는 더 많은 오류 검사와, OP_TAIL 연산이 아예 재개하지 않는 경우(OP_NORESUME처럼 동작)도 허용한다. 또한 hstack_find와 hstack_pop_upto가 yield 프레임이 지정한 핸들러 건너뛰기를 수행하도록 조정해야 한다.
새 꼬리 호출 재개 최적화 구현으로 4.4절의 카운터 벤치마크를 다시 실행하자. 그림 6은 새 결과를 보여준다. 세 자릿수 자수의 개선을 보이며, clang에서 초당 최대 1억5천만(!) 꼬리 재개 연산을 수행할 수 있다. 이는 2.6GHz 프로세서에서 약 18 사이클 정도로 꽤 좋은 수치다.
C에서 코루틴/스레딩 라이브러리는 흔히 C의 관용구를 깨뜨리는 것으로 악명이 높다. 우리는 대수적 효과의 구조화되고 스코프가 있는 형태가 많은 잠재적 문제를 방지한다고 믿는다. 그럼에도 스택을 복사하므로 런타임에 대해 몇 가지 가정을 한다:
C 스택이 연속(contiguous)이며 이동하지 않는다고 가정한다. 이는 주요 플랫폼 모두에서 성립한다. “연결(linked)” 스택을 지원하는 플랫폼에서는 스택을 복사 대신 참조로 캡처하여 더 최적화할 수도 있다. 하지만 “이동하지 않음” 가정은 캡처된 재개를 다른 스레드에서 재개할 수 없음을 의미한다.
yield와 (tail_)resume 호출 시에는 스택 참조로 매개변수를 전달할 수 없고 힙에 할당해야 한다. 이는 대수적 효과를 위해 특별히 작성된 새 코드에만 적용되는 합리적인 제약이라고 본다. 디버그 모드에서는 라이브러리가 이를 검사한다.
핸들러 스코프 안의 재개에 대해서는, 항상 핸들러 스택 베이스와 정확히 같은 위치에 스택과 fragment를 복원한다. 이렇게 하면 스택은 항상 유효하며 디버거 같은 도구가 언와인드할 수 있다. 일급 재개가 핸들러 스코프를 탈출하면 항상 그런 것은 아니다. 이 경우 재개 스택이 임의의 C 스택으로 복원될 수 있으며, 새 C 스택은 (일시적으로) resume 베이스 위에서만 유효하다. 그럼에도 gdb나 Microsoft 디버거/프로파일러에서 실무적으로 문제를 본 적은 없다.
실제로 거의 모든 효과는 꼬리 재개 또는 핸들러 스코프에 머무는 재개만 사용한다. 예외는 async 효과지만, 이 경우에도 우리는 항상 같은 이벤트 루프에서 재개하므로 우연히도 올바른 위치에서 재개된다.
이는 C 언어에서 대수적 효과와 핸들러를 구현한 첫 라이브러리지만, 유사한 기법은 코루틴[21, 1.4.2]과 협력적 스레딩[1,4,6,7,12] 구현에 많이 사용되었다. 특히 스택 복사/스위칭과 setjmp/longjmp의 신중한 사용[15]이다.
하지만 많은 라이브러리는 단점이 있으며 다양한 C 관용구를 제한한다. 예를 들어 대부분의 코루틴 라이브러리는 고정된 C 스택을 요구하거나[9,10,16,24,39], 재개 시 스택 위치를 이동시키거나[31], 원샷(one-shot) 연속으로 제한한다[8]. 우리는 이것이 일반 코루틴과 일급 연속(call/cc)이 너무 일반적이기 때문이라고 본다. 대수적 효과의 단순한 타입 시스템과 추가 구조는 구성적으로 더 안전하게 만든다.
Eff[3] 언어의 공동 창시자인 Andrej Bauer가 말하듯, 효과+핸들러는 제한된 연속에 대해 while이 goto에 대해 갖는 관계와 같다[20].
최근에는 Haskell에 임베디드[20,42]되거나, Eff[3], Links[18], Frank[30], Koka[26]처럼 언어에 내장된 다양한 대수적 효과 구현이 있다. 본 글과 가장 가까운 것은 Multi-core OCaml[13,14]이며, 이는 OCaml 런타임에 대수적 효과를 네이티브로 구현한다.
Multi-core OCaml은 스택 복사를 피하기 위해 여러 스택을 사용하고, 한 번 이상 재개할 때 명시적 복사를 한다. 또한 바깥쪽(최상위)에 정의된 기본 핸들러(default handler)[13]를 지원하는데, 이는 결과에 대해 암묵적 재개를 가진 핸들러다. 매우 효율적이며 함수 호출처럼 구현된다.
이는 5.1절의 꼬리 재개 최적화의 특수한 경우로 볼 수 있다. 암묵적 재개가 재개가 꼬리 호출 위치임을 보장하고, 최상위 수준은 핸들러 스택이 항상 비어 있음을 보장하므로 yield op 프레임이 따로 필요 없고, 다른 연산 처리만 막는 간단한 플래그로 충분하다.
우리는 C에서 강력한 제어 추상화를 제공하는 라이브러리를 설명했다. 가까운 미래에는 이를 P 언어[11]의 컴파일러 백엔드에 통합하고, libuv를 위한 좋은 래퍼를 만들 계획이다.
P 백엔드의 일부로, 소멸자를 올바르게 실행하기 위해 특별한 주의가 필요한 C++ 인터페이스도 작업 중이다(자세한 내용은 [27] 참조).
- [1] Martín Abadi, Gordon D. Plotkin. “A Model of Cooperative Threads.” Logical Methods in Computer Science 6 (4:2): 1–39. 2010. doi:10.2168/LMCS-6(4:2)2010.
- [2] Steve Awodey. Category Theory. Oxford Logic Guides 46. Oxford Univ. Press. 2006.
- [3] Andrej Bauer, Matija Pretnar. “Programming with Algebraic Effects and Handlers.” Journal of Logical and Algebraic Methods in Programming 84 (1): 108–123. 2015. doi:10.1016/j.jlamp.2014.02.001.
- [4] Dave Berry, Robin Milner, David N. Turner. “A Semantics for ML Concurrency Primitives.” In POPL’92, 119–129. 1992. doi:10.1145/143165.143191.
- [5] Gavin Bierman et al. “Pause ‘n’ Play: Formalizing Asynchronous C#.” In ECOOP’12, 233–257. 2012. doi:10.1007/978-3-642-31057-7_12.
- [6] Gérard Boudol. “Fair Cooperative Multithreading.” In CONCUR’07, 272–286. 2007. doi:10.1007/978-3-540-74407-8_19.
- [7] Frédéric Boussinot. “FairThreads: Mixing Cooperative and Preemptive Threads in C.” Concurrent Computation: Practice and Experience 18 (5): 445–469. 2006. doi:10.1002/cpe.v18:5.
- [8] Carl Bruggeman, Oscar Waddell, R. Kent Dybvig. “Representing Control in the Presence of One-Shot Continuations.” In PLDI’96, 99–107. 1996. doi:10.1145/231379.231395.
- [9] Peter A. Buhr, Richard A. Stroobosscher. “The uSystem: Providing Light-Weight Concurrency...” Software—Practice and Experience 20 (9): 929–963. 1990.
- [10] Russ Cox. “Libtask.” 2005. https://swtch.com/libtask .
- [11] Ankush Desai et al. “P: Safe Asynchronous Event-Driven Programming.” In PLDI ’13, 321–332. 2013. doi:10.1145/2491956.2462184.
- [12] Edsger W. Dijkstra. “Cooperating Sequential Processes.” In The Origin of Concurrent Programming, 65–138. 2002.
- [13] Stephen Dolan et al. “Concurrent System Programming with Effect Handlers.” In TFP’17. 2017.
- [14] Stephen Dolan et al. “Effective Concurrency through Algebraic Effects.” In OCaml Workshop. 2015.
- [15] Ralf S. Engelschall. “Portable Multithreading...” In ATEC’00, 20–31. 2000.
- [16] Tony Finch. “Coroutines in Less than 20 Lines of Standard C.” http://fanf.livejournal.com/105413.html .
- [17] Yannick Forster et al. “On the Expressive Power of User-Defined Effects...” In ICFP’17. 2017. arXiv:1610.09161.
- [18] Daniel Hillerström, Sam Lindley. “Liberating Effects with Rows and Handlers.” In TyDe 2016, 15–27. 2016. doi:10.1145/2976022.2976033.
- [19] Daniel Hillerström et al. “Continuation Passing Style for Effect Handlers.” In FSCD’17, vol. 84. 2017. doi:10.4230/LIPIcs.FSCD.2017.18.
- [20] Ohad Kammar, Sam Lindley, Nicolas Oury. “Handlers in Action.” In ICFP ’13, 145–158. 2013. doi:10.1145/2500365.2500590.
- [21] Donald Knuth. The Art of Computer Programming. Vol. 1. Addison-Wesley.
- [22] Peter J. Landin. A Generalization of Jumps and Labels. 1965.
- [23] Peter J. Landin. “A Generalization of Jumps and Labels.” Higher-Order and Symbolic Computation 11 (2): 125–143. 1998. doi:10.1023/A:1010068630801.
- [24] Mark Lehmann. “Libcoro.” 2006. http://software.schmorp.de/pkg/libcoro.html .
- [25] Daan Leijen. “Libhandler.” 2017. https://github.com/koka-lang/libhandler .
- [26] Daan Leijen. “Type Directed Compilation of Row-Typed Algebraic Effects.” In POPL’17, 486–499. 2017. doi:10.1145/3009837.3009872.
- [27] Daan Leijen. Implementing Algebraic Effects in C. MSR-TR-2017-23. 2017.
- [28] Daan Leijen. “Structured Asynchrony Using Algebraic Effects.” In TyDe’17. 2017. doi:10.1145/3122975.3122977.
- [29] “Libuv.” https://github.com/libuv/libuv .
- [30] Sam Lindley et al. “Do Be Do Be Do.” In POPL’17, 500–514. 2017. doi:10.1145/3009837.3009897.
- [31] Sandro Magi. “Libconcurrency.” 2008. https://code.google.com/archive/p/libconcurrency .
- [32] Michael Matz et al. “System V ABI: AMD64 Architecture Processor Supplement.” 2017. http://chamilo2.grenet.fr/inp/courses/ENSIMAG3MM1LDB/document/doc_abi_ia64.pdf .
- [33] MSDN. “Using Setjmp and Longjmp.” 2017. https://docs.microsoft.com/en-us/cpp/cpp/using-setjmp-longjmp .
- [34] Gordon D. Plotkin, John Power. “Algebraic Operations and Generic Effects.” Applied Categorical Structures 11 (1): 69–94. 2003. doi:10.1023/A:1023064908962.
- [35] Gordon D. Plotkin, Matija Pretnar. “Handlers of Algebraic Effects.” In ESOP’09, 80–94. 2009. doi:10.1007/978-3-642-00590-9_7.
- [36] Gordon D. Plotkin, Matija Pretnar. “Handling Algebraic Effects.” Logical Methods in Computer Science 9 (4). 2013. doi:10.2168/LMCS-9(4:23)2013.
- [37] Matija Pretnar. “Inferring Algebraic Effects.” Logical Methods in Computer Science 10 (3). 2014. doi:10.2168/LMCS-10(3:21)2014.
- [38] Wouter Swierstra. “Data Types à La Carte.” Journal of Functional Programming 18 (4): 423–436. 2008. doi:10.1017/S0956796808006758.
- [39] Simon Tatham. “Coroutines in C.” 2000. https://www.chiark.greenend.org.uk/~sgtatham/coroutines.html .
- [40] Hayo Thielecke. “Using a Continuation Twice...” Higher Order Symbolic Computation 12 (1): 47–73. 1999. doi:10.1023/A:1010068800499.
- [41] Stefan Tilkov, Steve Vinoski. “NodeJS...” IEEE Internet Computing. 2010.
- [42] Nicolas Wu, Tom Schrijvers, Ralf Hinze. “Effect Handlers in Scope.” In Haskell ’14, 1–12. 2014. doi:10.1145/2633357.2633358.