CPS로 스택오버플로 회피하기

이전 글에서 재귀함수 때문에 발생하는 스택오버플로 문제를 회피할 목적으로 제너레이터 코루틴을 사용했다. 이때 스택오버플로를 회피하는 또다른 방법으로 트램폴리닝을 언급했는데, 트램폴리닝의 경우 꼬리재귀 문제는 해결 가능하지만 RD파서 처럼 꼬리재귀 형태가 아닌 경우는 적용하기 어렵다고 했다.

트램폴리닝은 사실 non-local jump에 해당하며 그 점프를 함수 호출로 하는 대신 트램폴린 함수가 대신 해주는 것이다. 그런데 꼬리 재귀가 아닌 경우 jump 후 본래의 실행 흐름으로 return 할 방법이 없으니 적용할 수 없었던 것.

// parens <- paren*
function parens() {
  let result = [];
  while (true) {
    const r = paren();   // paren 호출 후 할 일이 많다.
    if (r === FAIL) break;
    result.push(r);
  }
  return result;
}

그러니 jump할 대상지점과 return할 지점을 함께 반환한다면 트램폴린 함수에서 이를 처리해줄 수 있고, 이 방법으로 꼬리재귀 트램폴리닝 처럼 스택오버플로를 회피할 수 있다.

이건 이미 JavaScript에서 너무나 익숙한 콜백 전달, 혹은 Continuation Passing Style 일 뿐이다. 아래처럼 CPS로 바꾸면 된다.

function parens() {
  let result = [];
  return call(paren, [], function loop(r) {
    if (r === FAIL) return result;
    result.push(r);
    return call(paren, [], loop);
  });
}

사실 제너레이터를 사용한 것과 흐름은 동일하다. 다만 제너레이터 코루틴을 사용하느냐, CPS를 사용하느냐, 스타일의 차이일 뿐이다. (코드)