[C++] about 꼬리호출(꼬리재귀) 최적화

https://www.artificialworlds.net/blog/2012/04/30/tail-call-optimisation-in-cpp/

번역한 글입니다. 오역이 난무할수 있습니다.

Some programming languages make recursive programming more practical by providing the tail call optimisation.
-> 일부 프로그래밍 언어들은 보다 효율적인 재귀 표현을 위해 꼬리호출 최적화를 지원합니다.

For a tiny talk at the recent ACCU conference I looked at how we might do something similar in C++.
->저는 최근 ACCU 콘퍼런스에서 짧은 강연을 하기 위해서, C++에서는 어떻게 비슷한 걸 할수 있을지 생각해봤습니다.

Multiplying by two

Here’s a toy problem we will use as our example.
->여기 간단한 문제가 하나 있습니다.

Imagine for a second that you want to write a function that multiplies a number by two. OK, we can do that:
->한 숫자에다 2를 곱하는 함수를 만들려면 어떻게 해야할지 생각해봅시다.
대충 이런식으로 할수 있을겁니다.

long times_two_hardware( long value )
{
    return value * 2;
}

Now imagine that you don’t have the “*” operator. We’re going have to use “+”:
-> 그러면 이제 *연산자를 쓰지 않고 +를 써서 풀어봅시다.

long times_two_loop( long value )
{
     long ret = 0;
    for ( long i = 0; i < value; ++i )           
    { ret += 2; }
    return ret;
}

(Obviously, this is just a silly example designed to be easy to follow.)
->확실히, 이건 따라하기만 쉬운 단순한 예제이긴 합니다.

Now imagine that you read somewhere that state was bad, and you could always replace a loop with recursion.
->이번에는 어느 부분이 읽기에 상태가 좋지 않은지 읽어보고, 반복문을 재귀로 바꿔야 할 지에 대해서 생각해봅시다.

Then you might get something like this:
->그러면 이런식으로 짜볼 수 있습니다.

long times_two_naive_recursive( long value )
{
    if ( value == 0 )
    { return 0; }
    else
    {
        return 2 +
        times_two_naive_recursive( value - 1 );
    }
}

This is fine, but what happens when you run it for a large input?
->꽤 괜찮지만, 큰 입력을 받아서 수행한다면 무슨 일이 일어날까요?

$ ulimit -S -s 16 $ ./times_two naive_recursive 100000 Segmentation fault

Note that I set my stack size to be very small (16K) to make the point - actually, this will run successfully for very large arguments, but it will eat all your memory and take a long time to finish.

Why does this fail?
->왜 실패한 걸까요?

Because every time you call a function, the state of the current function is saved, and new information is pushed onto the stack about the new function.
->함수를 호출할때마다 현재 함수의 상태가 저장되고, 새로운 정보가 새 함수에 대한 스택 위로 저장되기 때문입니다.

When you call a function from within a function multiple times, the stack grows and grows, remembering the state all the way down to the place where you started.
->함수내에서 함수를 여러번 호출하다 보면, 스택은 점점 자라게 됩니다. 그리고 함수가 시작한 장소의 상태까지 전부 기억하게됩니다.

So is programming like this useless in practice?
->그렇다면 이런 프로그래밍 방법은 쓸모없는걸까요?

Tail call optimisation

No, because in several programming languages, the compiler or interpreter performs the "tail call optimisation".
->아니죠. 많은 프로그래밍 언어의, 컴파일러나 인터프리터들은 '꼬리호출 최적화'라는걸 지원합니다.'

When you call a function from within some other code, you normally need the state of the current code to be preserved.
->다른 코드에서 함수를 호출할 때면, 보통 현재 코드의 상태가 유지되어야 합니다.

There is a special case where you don't need it, though, and this is called a tail call.
->하지만 이게 필요없는 특수한 경우가 있으니,
이게 바로 꼬리호출을 수행하는겁니다.

A tail call is just the situation where you call a function and immediately return its return value as your return value.
->꼬리호출은 함수를 호출하고서 바로 그 리턴값을 즉시 리턴하는 것 뿐입니다.

In this case, we don't need any of the state of the current code any more - we are just about to throw it away and return.
->이 경우에는, 현재 코드의 상태가 더이상 필요하지 않습니다. 단지 그 값을 던지고 리턴할 뿐이죠.

The tail call optimisation throws away this unneeded state before calling the new function, instead of after.
->꼬리호출최적화는 새 함수를 호출하기 전에, 필요하지 않은 (현재)상태를 던져버립니다.

[In practice, in compiled code, this involves popping all the local variables off the stack, pushing the new function parameters on, and jmping to the new function, instead of calling it.
->실제로, 컴파일된 코드에서는 스택의 지역변수를 전부 해제시키고, 새로운 함수에 파라미터를 전달하고나서, 새 함수로 호출하는 대신 점핑하는 등의 행동을 포함합니다.
This means that when we hit the ret at the end of the new function, we return to the original caller, instead of the location of the tail call.]
->이건 새 함수의 끝에서 ret을 마주했을 때, 꼬리호출의 위치 대신에 원래 호출자에게로 돌아간다는 사실을 의미합니다.

Many recursive functions can be re-cast as tail-call versions (sometimes called iterative versions).
->많은 재귀함수들은 다시 꼬리호출버전으로 재구성될 수 있습니다. (때때로는 반복버전을 호출합니다.)

The one we're looking at is one of those.
->이제 우리가 볼 것은 이들 중 하나입니다.

 Here is the tail-call version:
->이게 꼬리호출버전입니다.

long times_two_recursive_impl( long total, long counter )
{
    if ( counter == 0 )
    { return total; }
    else
    {
        return times_two_recursive_impl( total + 2, counter - 1 );
    }
}
long times_two_recursive( long value )
{
    return times_two_recursive_impl(0, value );
}

It consists of an outer function times_two_recursive which just hands off control to the inner function times_two_recursive_impl.
->이 코드에서는 외부 함수인 function times_two_recursive가 내부함수인 function times_two_recursive_impl에게 제어권을 건네줍니다.

The inner function uses a counter variable and calls itself recursively, reducing that counter by one each time, until it reaches zero, when it returns the total, which is increased by 2 each time.
->내부 함수는 카운터 변수를 사용해서 재귀적으로 호출을 합니다. 그래서 카운터가 0에 도달할 때까지 카운터를 1씩 감소시킵니다.
그리고 total이 반환될 때마다 2씩 증가시키죠.

The key feature of this implementation is that the recursive function times_two_recursive_impl uses a tail call to do the recursion:
->이 구현의 가장 중요한 특징은 재귀함수 function times_two_recursive_impl이 꼬리호출로 재귀를 수행한다는 점에 있습니다.

the value of calling itself is immediately returned, without reference to anything else in the function, even temporary variables.
->호출된 함수의 값은 즉시 반환됩니다. 함수에서 선언된 지역변수가 있든지 없든지 상관없이요.

So, let's see what happens when we compile and run this:
->자. 그럼 이제 컴파일해서 실행결과를 봐봅시다.

$ ulimit -S -s 16 $ ./times_two recursive 100000 Segmentation fault

Did I mention that C++ doesn't do the tail call optimisation?*
->제가 C++이 꼬리호출최적화를 지원하지 않는다고 말했던가요?

Tail call optimisation isn't in the C++ standard.
->꼬리호출최적화는 C++의 표준 기능이 아닙니다.

Apparently, some compilers, including MS Visual Studio and GCC, do provide tail call optimisation under certain circumstances (when optimisations are enabled, obviously).
->MS의 VS나 GCC같은 일부 컴파일러에서는 특정 조건 하에서 꼬리호출 최적화를 행하도록 지원해주긴 합니다.

 It is difficult to implement for all cases, especially in C++ since destruction of objects can cause code to be executed where you might not have expected it, and it doesn't appear to be easy to tell when a compiler will or will not do it without examining the generated assembly language.
->하지만 모든 케이스에 대해 꼬리호출의 구현을 수행하는 것은 꽤나 어렵죠. 그래서 특히 C++에서 객체가 나서는 예상치 못한 곳에서 코드가 실행되는 상황을 유발할 수 있습니다.
게다가 생성된 어셈블리에 대한 검토 없이 컴파일러가 최적화를 수행할지 않을지 단정하는 것은 쉽지 않을 것입니다.

Languages which have this feature by design, like Scheme (and D?) can do it more predictably.
->스킴처럼 이러한 특징을 갖고 있는 언어들은 이 경우보단 예측하기가 쉽습니다.

So how would we write code that is tail call optimised in C++?
->그래서 C++에서 꼬리호출최적화가 적용되는 코드를 짜려면 어떻게 해야할까요?

Possibly of more interest to me personally:
->?

if we were generating C++ as the output format for some other language, what code might we generate for tail call optimised functions?
->만약 C++에서 다른 언어들처럼 출력포맷을 발생시키고자 한다면, 어떤 코드가 꼬리호출로 최적화된 함수를 만들어낼 수 있을까요?

Tail call optimised C++

Let's imagine for a second we have some classes, which I'll define later. 
->나중에 정의할 클래스 몇 개가 있다고 가정해봅시다.

FnPlusArgsholds a function pointer, and some arguments to be passed to it. 
->FnPlusArgsholds가 함수포인터와 몇개의 인자들을 전달받습니다.

Answer holds on to one of 2 things:
->Answer은 둘중 하나를 hold합니다.

either a FnPlusArgs to call later, or an actual answer (return value) for our function.
->FnPlusArgs는 나중에 이 함수에서 호출할 수도 있고 실제로 답변하는 것(값의 반환)도 가능합니다.

Now we can write our function like this:
->이제 함수를 이렇게 짜볼 수 있습니다.

Answer times_two_tail_call_impl( long acc, long i )
{
    if ( i == 0 )
    {
        return Answer( true, null_fn_plus_args, acc );
    }
    else
    {
        return Answer(false, FnPlusArgs( times_two_tail_call_impl, acc + 2, i - 1 ), 0 );
    }
}
long times_two_tail_call( long n )
{
    return trampoline(Answer( false, FnPlusArgs(times_two_tail_call_impl, 0, n), 0 ) );
}

This has the same structure as times_two_recursive, if a little more verbose.
->이건 times_two_recursive와 비슷한 구조를 가집니다. 좀 더 장황하긴 하지만요.

The important point to note, though, is that times_two_tail_call_impl doesn't call itself recursively.
->하지만 진짜 중요한 점은, times_two_tail_call_impl가 재귀적으로 호출을 하지 않는다는 것입니다.

Instead, it returns an Answer object, which is a delegate saying that we have more work to do:
->대신, 이건 Answer 객체를 반환합니다. 우리가 작업할게 더 많다는 걸 뜻하죠.

calling the provided function with the supplied arguments.
->지정된 인자들로 제공된 함수를 호출해야 합니다.

The Trampoline

All we need now is some infrastructure to call this function, and deal with its return value, calling functions repeatedly until we have an answer.
->이제 이 함수를 호출하고 반환값을 처리해서 답이 나올 때까지 함수를 반복해서 호출하는 인프라만 있으면 됩니다.

This function is called a "trampoline", and you can sort of see why:
->이 함수는 "trampoline"라고 부르는데, 그 까닭을 어느정도 이해할 수 있을겁니다.

long trampoline( Answer answer )
{
    while ( !answer.finished_ )
    {
        answer = answer.tail_call_();
    }
    return answer.value_;
}

While the answer we get back tells us we have more work to do, we call functions, and when we're finished we return the answer.
->answer는 우리가 뭘 더 해야할지 말해줍니다. 함수를 호출하고, 끝날때까지 answer를 반환하죠.
우리가 돌려 받는 answer는 우리가 무엇을 더 해야할지 말해줍니다. 함수를 호출하고, 끝났으면 그 answer를 반환하죠.

Now all we need to get this working is the definition of Answer and FnPlusArgs:
->그리고 이 작업들에는 모두 Answer와 FnPlusArgs의 구현이 필요합니다.

struct Answer;
typedef Answer (*impl_fn_type)( long, long );

struct FnPlusArgs
{
    impl_fn_type fn_;
    long arg1_;
    long arg2_;
    FnPlusArgs( impl_fn_type fn, long arg1, long arg2 );
    Answer operator()();
};

FnPlusArgs::FnPlusArgs( impl_fn_type fn, long arg1, long arg2 )
: fn_( fn ) , arg1_( arg1 ) , arg2_( arg2 )
{ }

Answer FnPlusArgs::operator()()
{
ㅤreturn fn_( arg1_, arg2_ );
}

impl_fn_type null_fn = NULL;
FnPlusArgs null_fn_plus_args( null_fn, 0, 0 );

struct Answer
{
    bool finished_;
    FnPlusArgs tail_call_;
    long value_;
    Answer( bool finished, FnPlusArgs tail_call, long value );
};

Answer::Answer( bool finished, FnPlusArgs tail_call, long value )
: finished_( finished ) , tail_call_( tail_call ) , value_( value )
{ }

The only notable thing about this is that we use operator() on FnPlusArgs to call the function it holds.
->이에 관해 주목할 만한 유일한 것은 FnPlusArgs로 operator()를 사용해서 그것이 갖고 있는 기능을 호출한다는 것입니다.

Results

Now, when we run this code, we get what we wanted:
->이제 이 코드가 우리가 원하는 결과물을 뱉을지 봐봅시다.

$ ulimit -S -s 16 $ ./times_two tail_call 100000 200000

(I.e. it doesn't crash.)
->이제 충돌이 발생하지 않네요.

So, it turns out that the tail call optimisation is just a while loop.
->꼬리재귀 최적화로 while 반복문으로 변했습니다.

Sort of.
->of를 정렬해.