프로그래밍에서 Recursive Call을 설명할 때 당골로 언급되는 것이 factorial 예제를 통해 값을 구하는 것일 것이다.

int factorial(int n) {
  if (n <= 1) // Base case
    return 1; 
  return n * factorial(n - 1); // Recursive case
}

그냥 겉으로 보기에는 코드의 길이가 짧고 깔금해 보이지만 내부적으로 보면 Stack을 과도하게 사용할 수 있고 이로 인해 Stack Overflow가 발생할 가능성이 있어 되도록이면 Recursion보다 Loop을 사용하도록 가이드 하고 있다.

Tail Call이란

Java는 단지 언어(language)를 넘어 하나의 플랫폼 역할을 한다. 즉, JVM은 단지 Java 언어 뿐만 아니라 Groovy, Scala같이 다른 언어들도 지원한다는 것을 알고나면 플랫폼이란 말이 이해가 될 것이다.

많은 functional language interpreter들은 recursion 동작을 optimize함으로써 tail call에서 발생하는 stack space을 많이 줄여 준다. Tail Call이란 어떤 method call 또는 function call이 다른 method 또는 function 내에서 실행될 때 제일 마지막에 실행되는 명령어일 때를 말한다. 아래 정의된 foo()를 보면

int foo(int a) {
  a = a + 1;
  return func(a);
}

func() 호출은 foo() function에서 제일 마지막에 호출되는 구문이 되므로 Tail Call이 된다. 다음은 C언어로 작성된 Recursive function에서 Tail Call이 되는 다른 형태의 예제이다.

int fact(int i, int acc) {
  if ( i == 0 ) 
    return acc;
  else
    return fact( i – 1, acc * i);
}

int factorial(int n) {
  if ( n == 0 )
    return 1;
  else
    return fact( n – 1, 1 );
}

이 코드를 컴파일한 후 디버깅을 해보면 아래 그림과 같이 실행되는 어셈블리 코드를 볼 수 있다. 여기서 빨간색 화살표는 fact() function의 마지막 두 문장을 가리킨다. fact() 재귀 호출 함수와 return문인 retq이며 이 부분이 tail call에 해당한다.

자 그럼 이들 function을 optimize하면 어떤 장점들이 있는지 알아보자.

Tail-Call Optimization

Tail-Call Optimization(TCO)는 recursive call과 관련이 깊으며 functional programming에서의 중요한 토픽중 하나다. 재귀함수는 goto문을 활용해서 optimize할 수 있다. 이런 optimization을 이용하면 function call 이전(prolog)과 stack에서 복원된 이후(epilog)에서 했던 작업들을 더이상 수행하지 않아도 된다.

아래의 코드를 살펴보면

int func_a(int data) {
  data = do_this(data);
  return do_that(data);
}

function do_that()은 tail call이 되며 optimize하기 이전의 어셈블리 코드는 아래와 같다.

... ! executing inside func_a()
push EIP ! push current instruction pointer on stack
push data ! push variable 'data' on the stack
jmp do_this ! call do_this() by jumping to its address
... ! executing inside do_this()
push EIP ! push current instruction pointer on stack
push data ! push variable 'data' on the stack
jmp do_that ! call do_that() by jumping to its address
... ! executing inside do_that()
pop data ! prepare to return value of 'data'
pop EIP ! return to do_this()
pop data ! prepare to return value of 'data'
pop EIP ! return to func_a()
pop data ! prepare to return value of 'data'
pop EIP ! return to func_a() caller
...

data와 EIP(extended instruction pointer) 두 레지스터에 대한 pop명령어가 연속해서 여러 번 실행된다는 것에 주목할 필요가 있다. EIP 레지스터 data의 값을 반환하고 instruction pointer를 이전 상태로 원복시킨다. 어셈블리 명령어인 jump(JUMP) 하나로 이들 epilog와 prolog 한 세트를 생략할 수 있다. 이렇게 하면 function do_that()이 function_a()의 epilog 코드를 실행하기 때문에 이 optimization이 가능해 진다.

또한 function_a()가 do_that()의 리턴문이 실행된 이후에 더이상 아무런 의미있는 동작을 하지 않기 때문에 이 optimization은 안전하다라고 볼 수 있다(tail call이기 때문).

다음은 TCO의 결과를 보여준다. strike줄을 친 구문은 더이상 실행할 필요가 없는 명령어를 나타낸다.

좀 다르게 표현해서 아래의 코드가 TCO이전의 코드이며

아래는 TCO 이후의 코드이다.

음영으로 처리된 코드를 비교해 보면 optimize된 버전에서 얼마나 많은 machine code가 줄어 들었는지 확인할 수 있다.

코드의 양을 줄이는 것은 좋긴 하지만 이것이 optimize된 버전을 선호하는 가장 큰 이유는 아니다. 실질적인 장점은 TCO를 Recursion과 비교할 때 비로소 드러난다.

앞에서 본 recursive factorial 예제에 이 optimization을 적용해보면 반복해서 필요로 했던 prolog와 epilog 어셈플리 코드가 모두 사라진 것을 확인할 수 있다. 이런 optimization을 적용하면 아래의 recursive pseudocode를

call factorial(3)
  call fact(3,1)
    call fact(2,3)
      call fact(1,6)
        call fact(0,6)
        return 6
      return 6
    return 6
  return 6
return 6

iterative(순차적인) pseudocode로 바꿔준다.

call factorial(3)
  call fact(3,1)
  update variables with (2,3)
  update variables with (1,6)
  update variables with (0,6)
  return 6
return 6

달리 말하면 TCO는 recursive code를 loop code로 대체시켜 준다. 이 optimization은 계속되는 recursive call동안 prolog와 epilog 어셈플리 코드에 대한 function call을 줄여주며 이로 인해 stack사용 또한 경감시켜 준다.

이런 optimization이 없이 아주 큰 수의 factorial을 연산하면 Stack Overflow가 발생할 수 있지만 Compile과정에서 loop문을 사용하도록 변환시켜 준다면 이런 위험성을 제거할 수 있다. 이것이 대부분의 functional programming language interpreter가 이면에서 TCO를 수행하는 이유이기도 하다.

Java와 TCO

2014년부터 Java Language Architect그룹 내에서는 TCO에 대해 논의를 해오고 있지만 아직 JVM에 반영되지 않고 있다. 향후 언젠가 반영은 되겠지만 아래와 같은 security이슈로 TCO가 완벽하게 구현되지 않은 상태라고 한다.

Oracle Java Platform Group의 Mark Reinhold chief architect는 한 블로그에서 아래와 같이 언급했다.

It’s not clear to me that we would ever want to expose tail calls and continuations in the platform for general use but there may be ways we could use them inside the platform, in some fairly interesting ways.

Java언어를 사용하는 개발자들에게는 JVM에 TCO를 지원하지 않는다는 것이 여전히 아쉬운 부분이지만 아래와 같이 Recursive코드를 loop문을 이용하여 회피할 수 있다.

int factorial(int n) {
  int result = 1;
  for (int t=n; t > 1; t--)
      result *= t;
  return result;
}

하지만 JVM 기반에서 동작하는 다른 functional language(Groovy, Scala)를 사용할 때는 이슈가 된다. 이 경우 언어 자체적으로 TCO를 적용하여 recursive가 잘 동작했지만 Java 언어에 동일하게 적용한다면 Stack Overflow를 마주하게 될 것이기 때문이다.