[Javascript] - Tail Call

Tail Call (꼬리 호출)

 

- 최적화

 

보통 프로그램을 더 빠르게 만들기 위해 최적화 작업을 하는데, 최적화는 규칙을 깨는 것이지만 규칙을 깬다는 사실을 눈치 채지 못하게 합니다. 그렇다고 나쁜 프로그램이 되어서는 안되며 버그를 만들어도 안 됩니다.

 

- 꼬리 호출 최적화

 

꼬리 호출 최적화는 적절한 꼬리 호출 이라고 부르기도 합니다.

꼬리 호출은 함수가 마지막으로 하는 일이 어떤 함수를 호출해 그 결과를 바로 반환 것일 때 일어납니다.

즉 함수가 함수 호출 결과를 바로 반환하는 경우를 꼬리 호출 이라고 합니다.

 

function continuize(any) {
  return function hero(continuation, ...args) {
    return continuation(any(...args)); // <-- 꼬리 호출
  };
}

 

꼬리 호출 최적화는 아주 간단하지만 효과는 엄청납니다.

위 예시의 continuize 함수를 기계어 관점에서 봤을 때 다음과 같이 최적화가 됩니다.

 

# 기존 방식
call continuation # continuation 함수 호출
return            # hero 함수를 호출한 함수로 돌아감

# 최적화
jump continuation # continuation 함수로 점프

 

기존 방식의 경우 call 명령어는 다음 명령어의 주소를 호출 스택에 저장합니다. continuation 함수가 끝나면 스택에 저장된 주소 값을 꺼내와 실행 흐름을 변경하고 이후 실행되는 return 명령어는 다시 호출 스택에서 hero 함수 호출의 명령어 주소를 꺼내와 실행 흐름을 변경합니다.

최적화를 하면 호출 스택에 반환 주소 값을 저장하지 않습니다. continuation 함수는 hero 함수가 아니라 hero 함수를 호출한 함수로 바로 돌아갑니다.

 

기계어 관점에서 보면 명령어 한줄만 줄인 것처럼 보이므로 자바스크립트에서 함수 호출이 이루어지는 과정을 보도록 하겠습니다.

 

- 기존 함수를 호출한 경우

 

• 인자 표현식 계산
• 함수의 매개변수와 변수를 저장할 수 있는 충분한 크기의 활성 객체 생성
• 호출된 함수 객체에 대한 참조를 새로운 활성 객체에 저장
• 전달받은 인자를 새로운 활성 객체의 매개변수에 저장, 빠진 인자는 undefined 로 간주, 남은 인자는 버림
• 활성 객체의 모든 변수 값을 undefined 로 지정
• 함수 호출 명령어의 다음 명령어를 활성 객체의 다음 명령어 필드 값으로 지정
• 새로운 활성 객체의 호출자 필드 값에 현재 활성 객체를 지정
• 새로운 활성 객체를 현재 활성 객체로 지정
• 호출된 함수 실행

- 최적화를 한 경우

 

• 인자 표현식 계산
• 현재 활성 객체가 충분히 크다면
  • 현재 활성 객체를 새로운 활성 객체로 사용
• 그렇지 않다면
  • 함수 매개변수와 변수를 저장할 수 있는 충분한 크기의 활성 객체 생성
  • 새로운 활성 객체의 호출자 필드 값에 현재 활성 객체 지정
  • 새로운 활성 객체를 현재 활성 객체로 지정
• 호출된 함수 객체에 대한 참조를 새로운 활성 객체에 저장
• 전달받은 인자를 새로운 활성 객체의 매개변수에 저장 (빠진 인자는 undefined, 남은 인자는 버림)
• 활성 객체의 모든 변수 값을 undefined 로 지정
• 호출된 함수 실행

- 중요한 차이점은 활성 객체가 충분히 크다면 (일반적으로 충분히 큼) 새로운 활성 객체를 할당할 필요가 없다는 것입니다.

 

메모리 할당과 가비지 컬렉션에 드는 시간을 줄이는 것만으로도 충분히 효과적입니다.

여기에 추가로 꼬리 호출 최적화를 통해 재귀 함수 호출을 반복문만큼 빠르게 만들 수 있습니다.

반복문은 순수하지 않기에, 재귀 함수 호출을 통해 순수함을 얻는 것이라 볼 수 있습니다.

 

// 일반적인 반복문
while (true) {
  // do something
  if (done) {
    break;
  }
  // do something
}

// 꼬리 재귀 함수
(function loop() {
  // do something
  if (done) {
    return;
  }
  // do something
  return loop(); // 꼬리 호출
}());

 

이러한 점을 통해 메모리 고갈이나 스택 오버플로 에러 걱정 없이 아주 깊은 재귀 호출도 사용할 수 있습니다.

적절한 꼬리 호출은 기능이 아닌 버그 수정입니다.

 

- 꼬리 위치

 

// case 1
return (
  typeof any === 'function'
  ? any() // 꼬리 호출
  : undefined
);

// case 2
return 1 + any(); // 꼬리 호출이 아님

// case 3
any(); // 꼬리 호출이 아님
return;

// case 4
const value = any(); // 꼬리 호출이 아님
return value;

 

- 재귀는 일반적으로 꼬리 호출이 아닙니다.

 

function factorial(n) {
  if (n < 2) {
    return 1;
  }
  
  return n * factorial(n - 1); // 꼬리 호출이 아님
}

 

위에서 본 예시들처럼 factorial 에 대한 재귀 호출이 꼬리 위치에 있지 않기 때문에 매 반복 시 활성 레코드를 만듭니다.

이를 아래와 같이 최적화할 수 있습니다.

 

function factorial(n, result = 1) {
  if (n < 2) {
    return result;
  }
  
  return factorial(n - 1, n * result); // 꼬리 호출
}

 

이 재귀 함수 호출은 활성화 객체를 만들지 않고 재귀 함수 호출의 최상위로 점프합니다.

 

- 새로운 함수 객체를 반환하는 것 역시 꼬리 호출이 아니며 새로운 함수 객체를 바로 호출한다면 꼬리 호출입니다.

 

return function() {}; // 꼬리 호출이 아님

return (function() {}()); // 꼬리 호출

 

- 예외 : try 블록 내의 꼬리 호출은 최적화되지 않습니다.

 

좋은 프로그램이 이상해지는 것을 막기 위해 최적화를 하지 말아야 하는 상황입니다.

꼬리 호출 최적화는 함수 호출 시 호출 스택에 활성 객체를 연결하지 않는 방법으로 시간과 메모리를 절약합니다.

하지만 try 는 실행 흐름을 호출자의 catch 문으로 변경할 수 있어야 하는데, 이것이 가능하려면 활성 객체가 최적화되면 안 됩니다.

예외 처리를 잘못 사용해서는 안 되는 또 다른 이유이기도 합니다.

 

- 디버깅

 

프로그램의 디버깅을 위해선 함수의 호출 스택을 추적하는 것이 좋은데 꼬리 재귀를 사용할 경우 호출 스택의 활성화 객체를 없애기 때문에 디버깅이 좀 어려울 수 있습니다.

 

하지만 좋은 디버거는 활성 객체의 상태가 변할 경우 그 복사본을 만들고 가장 최신의 객체를 유지하는 방식으로 디버깅을 좀 더 쉽게 만들 수 있습니다. 이렇게 해서 최적화를 방해하지 않고 호출 스택을 검사할 수 있습니다.

 

출처 : 자바스크립트는 왜 그 모양일까?