Life is wonder-ful

얼랭 스터디에서 배운 Continuation Passing Style. 재귀적으로 정의된 함수를 구현하는 여러 가지 방법이 있습니다.

첫 번째 일반적인 재귀 호출.

fac(0) -> 1;
fac(N) -> N * fac(N - 1).

위와 같은 재귀 호출은 종료 조건까지 갔다가 다시 돌아오면서 남은 계산을 수행해야 합니다. 지역 변수와 돌아갈 주소를 스택에 계속 유지해야 하기 때문에 입력 값이 커지면 Stack Overflow가 나고, 비효율적입니다. 종료 조건까지 갔다가 되돌아올 필요가 없다면 스택도 늘어 나지 않고 최초 호출 지점으로 바로 되돌아 갈 수 있기 때문에 효율적이겠죠. Tail call optimization이 될 수 있도록 Tail recursion으로 바꿔줍니다.

%% Accumulator Passing Style
fac_aps(0, Acc) -> Acc;
fac_aps(N, Acc) -> fac_aps(N - 1, Acc * N).
fac_aps(N) -> fac_aps(N, 1).

일반 재귀 호출 형식을 위와 같은 Accumulator Passing Style로 바꾸는 알고리즘이 없기 때문에 컴퓨터가 자동으로 Accumulator Passing Style로 변환 할 수 없다고 합니다. 즉 효율성을 위해서 사람이 Accumulator Passing Style로 변환을 해줘야 합니다. Continuation Passing Style은 꼬리 재귀 호출이면서도 일반 재귀 호출 형식에서 자동으로 변환할 수 있다고 합니다.

%% Continuation Passing Style
fac_cps(0, Cont) -> Cont(1);
fac_cps(N, Cont) -> fac_cps(N - 1, fun(X) -> Cont(N * X) end).
fac_cps(N) -> fac_cps(N, fun(X) -> X end).

그리고 신기한 것이 입력의 크기가 커지면 Continuation Passing Style이 Accumulator Passing Style보다 빨라졌다가, 더 커지면 다시 느려집니다.

31> c(fac), fac:benchmark(100).
fac_aps: 21us
fac_cps: 38us
ok
32> c(fac), fac:benchmark(10000).
fac_aps: 176273us
fac_cps: 167858us
ok
33> c(fac), fac:benchmark(50000).
fac_aps: 5717974us
fac_cps: 5576236us
ok
34> c(fac), fac:benchmark(100000).
fac_aps: 38130471us
fac_cps: 65731319us
ok