프로그래밍

[번역] 일급(First-Class) 테스트

Clean Code 블로그의 “First-Class Tests” 라는 글을 번역했다. 글을 참 짖궂게 쓴다. 개인적으로 엉클밥을 참 좋아하는데, 요즘은 뭔가 TDD교를 신봉하는 꼰대 아저씨의 느낌이 나려고 하는 것 같다. 하지만 TDD에 대한 이론이나 경험에 있어 엉클밥만큼 신뢰할만한 사람은 몇 안되지 않는다고 생각하고, 개인적으로 이 글을 통해 테스트에 대한 개념을 정리하는 데에 많은 도움을 받았다고 생각한다.

사실 프론트엔드 개발자로서, 나는 최근에 TDD에 대해 조금 회의적인 생각이 들기 시작했다. 좀더 균형잡힌 시각을 위해서는 이 글 뿐만 아니라 이 글의 소재가 된 블로그 글, 그리고 거기에 링크되어 있는 “Why most unit testing is a waste“도 읽어보면 도움이 될 것이다.

이 주제에 대해서는 조만간 생각이 정리되면 포스팅을 하도록 하겠다.


 

부적절한 학습의 희생양이 되어 단위 테스트를 포기하게 되는 사람들의 블로그를 찾아내는 건 어쩌면 나의 숙명일지도 모르겠다. 이 블로그도 바로 그 중의 하나이다.

저자는 모든 협력 객체(collaborator)를 모킹함으로 인해 단위 테스트가 얼마나 깨지기 쉬운 상태가 되었는지를 이야기한다. (한숨). 협력 객체가 변경될 때마다 모의(mock) 개체들이 변경되어야만 한다. 그리고 당연히 그로인해 단위 테스트는 깨지기 쉬운 상태가 된다.

더 나아가서 저자는 어떻게 단위 테스트를 버리고 대신 흔히들 말하는 “시스템 테스트”를 시작했는지에 대해서 이야기한다. 그의 어휘에 따르면 “시스템 테스트”는 단순히 “단위 테스트”보다 좀더 종단간 (end-to-end) 에 가까운 테스트이다.

자 먼저, 몇가지 정의를 내려보자. 거만하게 굴어 미안하지만, “단위 테스트”, “시스템 테스트”, “인수 (acceptance) 테스트” 등에 대해서는 수많은 정의가 존재하기 때문에, 누군가가 하나의 권위있는 정의를 제공해야만 할 것 같다. 이들 정의가 정착될지는 모르겠지만, 가까운 미래에 이 중의 몇가지는 그렇게 되길 바란다.

  •  단위 테스트 : 프로덕션 코드가 프로그래머가 기대하는 대로 동작하는지를 보장하기 위해 프로그래머가 작성하는 테스트 코드이다. (단위 테스트가 디자인을 도와준다는 등의 개념은 잠시 무시하기로 하겠다)
  • 인수 테스트 : 프로덕션 코드가 사업자가 기대하는 대로 동작하는지를 보장하기 위해 사업자가 작성하는 테스트이다. 이 테스트의 작성자는 사업부 인력이거나, 혹은 사업부를 대표하는 기술 인력이다. (예: 사업 분석가, QA)
  • 통합 테스트 : 시스템 컴포넌트들의 하부 조합(sub-assembly)이 제대로 작동하는지를 보장하기 위해 아키텍트나 기술 리더가 작성하는 테스트이다. 이 테스트는 Plumbing 테스트이다. (역: 기술적인 테스트라는 의미인 듯). 사업 규칙에 대한 테스트가 아니다. 이 테스트의 목적은 하부 조합이 제대로 통합되고 설정되었는지를 확인하는 것이다.
  • 시스템 테스트 : 통합된 모든 시스템의 내부가 계획한 대로 동작하는지를 보장하기 위해 작성하는 통합 테스트이다. 이 테스트는 Plumbing 테스트이다. 사업 규칙에 대한 테스트가 아니다. 이 테스트의 목적은 시스템이 제대로 통합되고 설정되었는지를 확인하는 것이다.
  • 마이크로 테스트 : Mike Hill (@GeePawHill)에 의해 만들어진 용어이다. 아주 작은 범위에서 작성된 단위 테스트이다. 단일 함수나 작은 그룹의 함수들을 테스트하기 위해서 작성한다.
  • 기능(Functional) 테스트 : 넓은 범위에서 작성된 단위 테스트이며, 느린 컴포넌트에 대한 모의 객체를 포함한다.

이들 정의를 통해 보면, 위 블로그의 저자는 잘못 작성된 마이크로 테스트를 포기하고, 대신에 잘못 작성된 기능 테스트를 작성했다. 왜 잘못 작성되었을까? 왜냐하면 저자의 설명에 비춰볼 때, 두가지 경우 모두 테스트들이 결합되어서는 안되는 것들과 결합되었기 때문이다. 그는 마이크로 테스트에서 너무 많은 모의 객체를 사용하고 있었고, 테스트 코드가 프로덕션 코드의 구현과 깊이 결합되어 있었다. 그러면 당연히 깨지기 쉬운 테스트가 될 수 밖에 없다.

기능 테스트를 살펴보면, 저자는 이들 테스트를 UI부터 데이터베이스에 이르기까지를 모두 포함하는 것처럼 설명하면서, 테스트가 느렸다는 사실을 언급했다. 그는 테스트가 가끔 15분내에 실행된다는 사실에 기뻐했다. 15분은 단위 테스트가 제공해야 하는 즉각적인 피드백을 위해서는 너무 긴 시간이다. TDD 개발자들에게 지속적 빌드 시스템이 테스트가 통과되었는지를 확인해줄 때까지 기다리는 습관같은 건 없다.

숙련된 TDD 개발자들은 마이크로 테스트이든 기능 테스트이든 (인수 테스트 또한 마찬가지로) 시스템의 구현과 결합되어서는 안된다는 것을 잘 알고 있다. 이들 테스트는 (위 블로그 저자가 강조했듯이) 시스템의 일부로써 어겨져야 하며, “일급 시민처럼 다루어야 한다 : 프로덕션 코드를 다루는 방식으로 다루어야 한다“.

위 블로그 저자는 시스템의 일급 시민은 결합되어서는 안된다는 점은 알지 못했던 것 같다. 자신의 테스트를 일급 시민처럼 다루는 사람은 이들 테스트가 프로덕션 코드와 강하게 결합되지 않도록 하기 위해 엄청난 노력을 기울인다.

마이크로 테스트와 기능 테스트를 프로덕션 코드로부터 감결합(decoupling) 시키는 것은 특별히 어려운 일이 아니다. 몇가지 소프트웨어 디자인 기술과 몇가지 감결합 기법에 대한 지식이 있으면 된다. 일반적으로 좋은 객체지향 디자인과 의존성 역전, 그리고 몇가지 디자인 패턴(파사드 혹은 전략 패턴과 같은)의 신중한 사용 정도면 대부분의 해로운 테스트들을 감결합 시키기에 충분하다.

불행하게도, 너무나 많은 프로그래머들이 단위 테스트에 적용되는 규칙은 다르며, 편한대로 급하게 만든 “쓰레기 코드”라도 상관없다고 생각한다. 또한, 너무나 많은 프로그래머들이 모의 객체에 대한 책을 읽고 모의 객체 도구들이 본질적이고 필요하며 단위 테스트의 일부라는 관념을 믿어오고 있다. 진실과는 한없이 멀게도 말이다.

내 경우에는 모의 객체 도구를 거의 사용하지 않는다. 만약 모의 객체(혹은 오히려 테스트 대역(Test Double))가 필요할 때면, 직접 작성한다. 테스트 대역을 작성하는 것은 그리 어려운 일이 아니다. IDE가 많은 도움을 준다. 게다가 테스트 대역을 스스로 작성하는 것은 정말 필요한 경우가 아니면 테스트 대역을 작성하지 않도록 도와준다. 테스트 대역을 사용하는 대신, 나는 마이크로 테스트에서 살짝 물러나서 좀더 기능 테스트에 가까운 테스트를 작성한다. 이 또한 내가 프로덕션 코드의 내부와 테스트 코드 사이의 결합을 감소시키는 것을 도와준다.

결국, 사람들이 단위 테스트를 포기하는 이유의 대부분은 위의 저자가 말한 조언을 따르지 않았기 때문이다. 그들은 테스트를 일급 시민으로 다루지 않았다. 그들은 테스트를 시스템의 일부인 것처럼 다루지 않았다. 그들은 다른 시스템에 적용하는 것과 동일한 기준을 갖고 테스트를 관리하지 않았다. 대신에, 그들은 테스트가 부패하고 결합되고 굳어가고 깨지기 쉽고 느리게 되도록 방치해왔다. 그리고 나서, 그들은 좌절하며 테스트를 포기한다.

교훈 : 테스트를 깔끔하게 유지하라. 테스트를 시스템의 일급 시민처럼 다루어라.

자바스크립트

[번역] 자바스크립트의 재귀, PTC, TCO, STC 에 대한 모든 것

원문 : http://lucasfcosta.com/2017/05/08/All-About-Recursion-PTC-TCO-and-STC-in-JavaScript.html

요즘은 모두가 함수형 프로그래밍과 그 개념에 대해서 열광적인 것 같다. 하지만 많은 사람들이 재귀(Recursion)나, 특히 적절한 꼬리 호출(Tail Call)에 대해서는 이야기하지 않는 것 같다. 이는 스택이 넘치는 일 없이 깔끔하고 간결한 코드를 작성하기 위해 매우 중요한데도 말이다.

이 글에서는 재귀를 더 잘 시각화하고 생각할 수 있는 팁을 제공하고, 적절한 꼬리 호출, 꼬리 호출 최적화, 문법적 꼬리 호출이 무엇인지와 각각의 차이점, 작동 방식, 그리고 주요 자바스크립트 엔진에서 어떤 식으로 구현되어있는지에 대해 설명하도록 하겠다.

콜스택과 스택 트레이스에 대한 이야기도 많이 하겠지만, 너무 상세한 내용까지는 다루지 않을 예정이므로, 만약 이 주제에 대해 더 자세히 알고싶다면 내가 쓴 이 글(지금까지 이 사이트에서 가장 유명한 글이다)을 읽어보길 권한다.

재귀란 무엇일까

재귀는 특정 문제의 해결책이 해당 문제의 다른 예에 동일한 해결책을 적용하는 것에 의존하는 경우 발생한다.

예를 들어 4의 factorial 은 3의 factorial에 4를 곱하는 것으로 정의될 수 있으며, 이런 식으로 계속될 수 있다.

이것은 팩토리얼 연산이 자기 자신을 이용해서 정의될 수 있다는 것을 의미한다.

factorial(5) = factorial(4) * 5
factorial(5) = factorial(3) * 4 * 5
factorial(5) = factorial(2) * 3 * 4 * 5
factorial(5) = factorial(1) * 2 * 3 * 4 * 5
factorial(5) = factorial(0) * 1 * 2 * 3 * 4 * 5
factorial(5) = 1 * 1 * 2 * 3 * 4 * 5

간략하게 말해서, 함수가 자기 자신을 호출할 때 재귀를 갖는다고 할 수 있을 것이다.

재귀에 대해 효과적으로 생각하기

나는 재귀에 대해서 생각할 때 첫번째 실행에서 파생된 다수의 브랜치들이 실행된 다음, 초기 호출에게 결과값을 순차적으로 돌려주는 (bubbling up) 것을 상상해본다.

앞의 팩토리얼 예제에서 우리는 첫번째 호출에서 파생된 다수의 호출이, 이미 스스로 존재하는 정의(이 경우에는 0의 팩토리얼, 즉 1을 의미)에 다다를때까지 발생하는 것을 볼 수 있다. 그 후에는 이 정의의 결과값이 반환되면서 (bubbles up) 그 값으로 다른 작업을 할 수 있게 되고, 그 작업이 또다시 값을 반환하고, 이런 식의 과정이 “최초” 호출에 다다를때까지 반복된다.

만약 우리가 factorial 함수를 인수 5를 넘겨주면서 호출했을 때를 표현하려 한다면 다음과 같을 것이다.

factorial-calls

컴파일러 이론과 함께 생각해 보면, 이 과정은 문맥 자유 문법을 사용해서 최종 값에 다다를때까지 문장을 만들어내는 과정과 아주 유사하다.

처음이라 추상적으로 느껴질 수도 있겠지만, 이번에는 피보나치 수열에서 N번째 수를 계산해 내는 함수를 분석하면서 이러한 사고가 어떻게 다른 방식으로 적용되는지를 시각화해서 보여주도록 하겠다.

우리의 피보나치 함수 코드는 다음과 같다.

// N은 N번째 피보나치를 의미한다
function fibonacci(n) {
   if (n < 2) {
     return 1
   } else {
     return fibonacci(n - 2) + fibonacci(n - 1)
   }
}

기본적으로 피보나치 함수 호출 각각은 두개의 호출을 더 발생시키는데, 이들 또한 2보다 작은 수에 다다를 때까지 스스로를 호출할 수 있다. (피보나치 수열은 1, 1로 시작되며, 둘이 더해졌을 때 2가 되므로)

2보다 작은 수에 도달하면, 결과값을 반환해서 상위에 있는 호출이 사용할 수 있도록 하며, 거품이 올라가듯이 최초 호출까지 계속해서 반복된다.

아래의 이미지가 명확하게 보여주듯이, fibonacci(4) 를 호출하면 우리는 “스스로를 포함하는” 정의 (기본 케이스)에 다다를때까지 새로운 호출들을 파생시키는데, 이 경우 기본 케이스는 피보나치 수열의 처음 두 수 : 1 (0번째)과 1 (1번째)가 된다.

recursion-bubble-up

각각의 재귀 호출이 다른 두개의 재귀호출의 결과에 의존적이기 때문에 (넘겨진 값이 2보다 작은 “기본 케이스”가 아니라면), 우리는 말단 호출에서부터 값을 반환하기 시작하고, 상위 호출에서 사용할 수 있도록 이들을 더해서 넘겨준다.

위의 예제들에서 발견할 수 있듯이, 선형 재귀(팩토리얼 예제처럼, 재귀 호출이 단일 분기를 가질 때)와, 분기형 재귀(피보나치 예제처럼, 재귀 호출이 하나 이상의 분기를 가질 때) 를 만들 수 있다.

재귀를 만들 때, 생각해야 할 두 가지 사항이 있다.

  1. 탈출 조건, 즉 스스로 존재하는 원자적 정의를 만든다. (“기본 케이스” 라고 부른다)
  2. 알고리즘의 어떤 부분이 재귀적인지를 정의한다.

탈출 조건을 정의하고 나면, 함수가 언제 스스로를 다시 호출해야 하는지와 그 결과를 가지고 무엇을 해야 하는지를 결정하기가 쉽다.

만약 좀더 재귀에 대한 좀더 실용적이고 흥미로운 적용사례를 알고 싶다면, 트리나 그래프 관련 알고리즘을 들여다보길 권한다.

재귀와 콜스택

일반적으로 재귀를 사용할 때는 함수를 차례로 스택에 쌓아올리게 되는데, 이는 이들 함수가 이전 호출의 결과에 의존적이기 때문이다.

만약 콜스택이 어떻게 작동하는지 혹은 스택 트레이스를 어떻게 읽는지에 대해 제대로 이해하고 싶다면 이 글을 읽어보길 바란다.

재귀가 발생할 때의 콜스택이 어떤 상태인지를 나타내기 위해, 간단한 factorial 재귀 함수를 예제로 사용해보자.

코드는 다음과 같다.

function factorial(n) {
    if (n === 0) {
        return 1
    }
 
    return n * factorial(n - 1)
}

이제, 이 코드를 실행해서 3의 팩토리얼을 확인해보자.

앞의 예제를 기억하고 있을지도 모르겠지만, 팩토리얼 3은 factorial(2)factorial(1)factorial(0)을 가져오는 것과 이들을 곱하는 것으로 구성된다. 즉, 팩토리얼 3를 찾기위해 factorial 함수를 한번 호출하면 factorial 함수 호출은 3번 더 발생한다.

이들 호출 각각은 새로운 프레임을 콜스택에 추가하므로, 모두가 스택에 추가되고 나면 다음과 같을 것이다.

factorial(0) // 0의 팩토리얼은 1로 정의되어 있다 (기본 케이스)
factorial(1) // 이 호출은 factorial(0)에 의존적이다
factorial(2) // 이 호출은 factorial(1)에 의존적이다
factorial(3) // 이 첫번째 호출은 factorial(2)에 의존적이다

이제, 팩토리얼 함수가 호출될 때마다 스택에 있는 현재의 프레임들을 확인하기 위해 console.trace를 추가해 보자.

코드는 다음과 같을 것이다.

function factorial(n) {
    console.trace()
    if (n === 0) {
        return 1
    }
 
    return n * factorial(n - 1)
}
 
factorial(3) // 팩토리얼 함수를 실행해서 결과를 확인해보자

이제 이 코드를 실행하고, 출력된 콜스택을 분석해보자.

첫번째 출력이다.

Trace
    at factorial (repl:2:9)
    at repl:1:1 // 이 라인 아래는 세부 구현에 관한 것이므로 무시하면 된다
    at realRunInThisContextScript (vm.js:22:35)
    at sigintHandlersWrap (vm.js:98:12)
    at ContextifyScript.Script.runInThisContext (vm.js:24:12)
    at REPLServer.defaultEval (repl.js:313:29)
    at bound (domain.js:280:14)
    at REPLServer.runBound [as eval] (domain.js:293:12)
    at REPLServer.onLine (repl.js:513:10)
    at emitOne (events.js:101:20)

여기서 볼 수 있듯이, 첫번째 콜스택은 factorial 함수의 첫번째 호출, 즉 factorial(3)만을 포함하고 있다. 하지만 상황은 점점 흥미로워진다.

Trace
    at factorial (repl:2:9)
    at factorial (repl:7:12)
    at repl:1:1 // 이 라인 아래는 세부 구현에 관한 것이므로 무시하면 된다
    at realRunInThisContextScript (vm.js:22:35)
    at sigintHandlersWrap (vm.js:98:12)
    at ContextifyScript.Script.runInThisContext (vm.js:24:12)
    at REPLServer.defaultEval (repl.js:313:29)
    at bound (domain.js:280:14)
    at REPLServer.runBound [as eval] (domain.js:293:12)
    at REPLServer.onLine (repl.js:513:10)

이제 factorial 함수의 마지막 호출 바로 위에 또다른 호출이 보이는데, 이 호출이 factorial(2) 이다.

그리고 factorial(1) 을 호출하면 스택은 다음과 같다.

Trace
    at factorial (repl:2:9)
    at factorial (repl:7:12)
    at factorial (repl:7:12)
    at repl:1:1
    at realRunInThisContextScript (vm.js:22:35)
    at sigintHandlersWrap (vm.js:98:12)
    at ContextifyScript.Script.runInThisContext (vm.js:24:12)
    at REPLServer.defaultEval (repl.js:313:29)
    at bound (domain.js:280:14)
    at REPLServer.runBound [as eval] (domain.js:293:12

여기서 볼 수 있듯이, 이전 호출 위에 또다른 호출이 추가되었다.

그리고, 마지막으로 factorial(0) 에 도달하면 콜스택은 다음과 같다.

Trace
    at factorial (repl:2:9)
    at factorial (repl:7:12)
    at factorial (repl:7:12)
    at factorial (repl:7:12)
    at repl:1:1
    at realRunInThisContextScript (vm.js:22:35)
    at sigintHandlersWrap (vm.js:98:12)
    at ContextifyScript.Script.runInThisContext (vm.js:24:12)
    at REPLServer.defaultEval (repl.js:313:29)
    at bound (domain.js:280:14)

이 절의 도입부에서 언급했듯이, factorial(3) 의 첫번째 호출은 factorial(2)factorial(1) 그리고 factorial(0) 호출을 필요로 한다. 그것이 콜스택에 factorial 함수의 엔트리가 4개 존재하는 이유이다.

이제, 너무 많은 재귀가 발생했을 경우 발생할 문제가 무엇인지 알 수 있을 것이다. 콜스택이 너무 커지게 되면 결국 스택 버퍼 오버플로우를 맞이하게 되는데, 이는 우리가 콜스택이 한계치에 달했을 때 또다른 엔트리를 추가하려고 할 때 발생한다.

만약 어떤 환경에서 자바스크립트 코드를 실행하는지에 따라 얼마나 많은 프레임을 가질 수 있는지를 알고싶다면, Dr. Axel Rauschmayer의 끝내주는 글을 읽어보길 권한다. (나는 이친구의 왕팬이다).

적절한 꼬리 호출 (PTC: Proper Tail Calls)

적절한 꼬리 호출은 ES6가 나왔을 때 구현되었어야 하지만, 나중에 설명할 이유들로 인해 여전히 주요 브라우저들에서 사용이 불가능하다.

적절한 꼬리 호출은 재귀 호출을 할 때 스택이 넘치는 것을 피할 수 있게 해 준다. 하지만 적절한 꼬리 호출을 실행하기 위해서는, 먼저 꼬리 호출을 해야 한다.

근데, 꼬리 호출이 뭐지?

꼬리 호출은 스택을 증가시키지 않고 실행될 수 있는 함수이다. 이들은 항상 마지막에 실행되는데, return문 직전에 평가되고, 호출된 함수의 결과값이 호출하는 함수의 결과값으로 반환된다. 호출하는 함수는 또한 제너레이터 함수가 될 수 없다.

만약 컴파일러 이론이나 이런 종류의 하드코어한 내용을 좋아한다면, ECMA 스펙의 공식 정의를 읽어보면 된다.

적절한 꼬리 호출이 어떻게 작동하는지를 나타내려면, 기존의 factorial 함수를 수정해서 꼬리 재귀 형태로 만들어야 한다.

// total이 제공되지 않으면 기본값으로 1을 할당한다
function factorial(n, total = 1) {
    if (n === 0) {
        return total
    }
 
    return factorial(n - 1, n * total)
}

이제 이 함수가 마지막에 하는 일은 자기 자신을 호출해서 그 결과를 반환하는 것 외에는 없으므로, 꼬리 재귀가 되었다.

눈치챘을 수도 있겠지만, 우리는 이제 2개의 인자를 전달하고 있다. 다음 팩토리얼을 계산하기 위한 수인 (n - 1), 그리고 누적된 총합 n * total 이다.

이제, 우리는 더이상 파생된 함수들의 마지막까지 찾아갈 필요가 없는데 (이전 예제에서 우리가 했던것 처럼), 왜냐하면 이제 우리는 현재 상태를 실행하기 위한 모든 값 (누적된 값과 다음 팩토리얼 값)을 다 갖고 있기 때문이다.

이제, 이 함수가 어떻게 다수의 재귀 호출을 스택에 쌓지 않고 이 작업을 할 수 있는지 분석해 보자.

  1. factorial 호출이 스택의 최상단에 추가된다.
  2. 4가 0 (기본 케이스)가 아니기 때문에 우리는 다음으로 계산할 값 (3)과 현재까지 누적된 값 (4 * total (기본값 1))을 지정한다.
  3. 이제 factorial 함수가 다시 호출되면, 이 함수는 연산에 필요한 모든 데이터 : 다음에 계산할 팩토리얼과 누적된 총합 모두를 넘겨받게 된다. 이 덕분에 우리는 이전 스택 프레임이 더이상 필요없게 되며, 해당 프레임을 스택에서 제거한 후에 새로운 factorial(3, 4) 호출을 스택에 추가할 수 있게 된다.
  4. 이 호출도 여전히 0보다 크기 때문에, 다음 팩토리얼을 구하면서 기존의 누적된 총합(4)과 현재 값 (3)을 곱한다.
  5. 이전 호출이 (또다시) 더이상 필요없기 때문에, 기존 프레임을 스택에서 제거한 후에 또다시 factorial 함수를 호출하면서 2와 12를 넘겨준다. 한번더 총합을 갱신하여 24가 되고, 1의 팩토리얼을 구한다.
  6. 이전 프레임이 스택에서 제거되고 24(총합)과 1을 곱하면서 0의 팩토리얼을 구한다.
  7. 드디어 0의 팩토리얼은 누적된 총합인 24를 반환한다. (이 값이 4의 팩토리얼이다)

간략히 정리해보면 결국 다음과 같은 과정이 발생한다.

factorial(4, 1) // 1 은 아무값도 넘겨지지 않았을 때의 기본값이다.
factorial(3, 4) // 이 호출은 이전 호출이 필요없으며 모든 필요한 데이터를 갖고 있다.
factorial(2, 12) // 이 호출은 이전 호출이 필요없으며 모든 필요한 데이터를 갖고 있다.
factorial(1, 24) // 이 호출은 이전 호출이 필요없으며 모든 필요한 데이터를 갖고 있다.
factorial(0, 24) // -> 총합인 24를 반환하며, 이 또한 이전 호출은 필요없다.

이제, n 개의 프레임을 스택에 쌓아올리는 대신, 하나의 스택만 있으면 되는데, 이는 다음 호출이 더이상 이전 호출에 의존적이지 않기 때문이며, 이로 인해 새로운 factorial 함수는 O(N)대신 O(1)의 메모리 복잡도를 갖게 된다.

Node 에서 적절한 꼬리 호출 사용하기

만약 위의 함수에서 스택의 상태를 보기 위해 다음과 같이  console.trace 를 추가한 후에 factorial(3)를 호출한다면 :

function factorial(n, total = 1) {
    console.trace()
    if (n === 0) {
        return total
    }
 
    return factorial(n - 1, n * total)
}
 
factorial(3)

꼬리 재귀임에도 불구하고 여전히 factorial 함수가 스택에 쌓이는 모습을 볼 수 있을 것이다 :

// ...
// 다음은 마지막 2개의 factorial 함수 호출이다
Trace
    at factorial (repl:2:9) // 스택에 호출 3개가 쌓여있다
    at factorial (repl:7:8)
    at factorial (repl:7:8)
    at repl:1:1 // 아래부터는 세부 구현이다
    at realRunInThisContextScript (vm.js:22:35)
    at sigintHandlersWrap (vm.js:98:12)
    at ContextifyScript.Script.runInThisContext (vm.js:24:12)
    at REPLServer.defaultEval (repl.js:313:29)
    at bound (domain.js:280:14)
    at REPLServer.runBound [as eval] (domain.js:293:12)
Trace
    at factorial (repl:2:9) // 마지막 호출이 스택에 프레임 하나를 추가했다
    at factorial (repl:7:8)
    at factorial (repl:7:8)
    at factorial (repl:7:8)
    at repl:1:1 // 아래부터는 세부 구현이다
    at realRunInThisContextScript (vm.js:22:35)
    at sigintHandlersWrap (vm.js:98:12)
    at ContextifyScript.Script.runInThisContext (vm.js:24:12)
    at REPLServer.defaultEval (repl.js:313:29)
    at bound (domain.js:280:14)

Node 에서 적절한 꼬리 호출을 사용하기 위해서는 반드시 use strict를 .js 파일의 최상단에 추가해서 strict mode 를 활성화시키고, --harmony_tailcalls 플래그와 함께 실행시켜야 한다.

이 플래그가 우리의 factorial 함수를 개선시키도록 하기 위해서는, 스크립트 파일이 다음과 같아야 한다.

'use strict'
 
function factorial(n, total = 1) {
    console.trace()
    if (n === 0) {
        return total
    }
 
    return factorial(n - 1, n * total)
}
 
factorial(3)

이제 플래그와 함께 실행해보자.

$ node --harmony_tailcalls factorial.js

실행 결과, 스택 트레이스는 다음과 같다.

Trace
    at factorial (/Users/lucasfcosta/factorial.js:4:13)
    at Object. (/Users/lucasfcosta/factorial.js:12:1)
    at Module._compile (module.js:571:32)
    at Object.Module._extensions..js (module.js:580:10)
    at Module.load (module.js:488:32)
    at tryModuleLoad (module.js:447:12)
    at Function.Module._load (module.js:439:3)
    at Module.runMain (module.js:605:10)
    at run (bootstrap_node.js:420:7)
    at startup (bootstrap_node.js:139:9)
Trace
    at factorial (/Users/lucasfcosta/factorial.js:4:13)
    at Object. (/Users/lucasfcosta/factorial.js:12:1)
    at Module._compile (module.js:571:32)
    at Object.Module._extensions..js (module.js:580:10)
    at Module.load (module.js:488:32)
    at tryModuleLoad (module.js:447:12)
    at Function.Module._load (module.js:439:3)
    at Module.runMain (module.js:605:10)
    at run (bootstrap_node.js:420:7)
    at startup (bootstrap_node.js:139:9)
Trace
    at factorial (/Users/lucasfcosta/factorial.js:4:13)
    at Object. (/Users/lucasfcosta/factorial.js:12:1)
    at Module._compile (module.js:571:32)
    at Object.Module._extensions..js (module.js:580:10)
    at Module.load (module.js:488:32)
    at tryModuleLoad (module.js:447:12)
    at Function.Module._load (module.js:439:3)
    at Module.runMain (module.js:605:10)
    at run (bootstrap_node.js:420:7)
    at startup (bootstrap_node.js:139:9)
Trace
    at factorial (/Users/lucasfcosta/factorial.js:4:13)
    at Object. (/Users/lucasfcosta/factorial.js:12:1)
    at Module._compile (module.js:571:32)
    at Object.Module._extensions..js (module.js:580:10)
    at Module.load (module.js:488:32)
    at tryModuleLoad (module.js:447:12)
    at Function.Module._load (module.js:439:3)
    at Module.runMain (module.js:605:10)
    at run (bootstrap_node.js:420:7)
    at startup (bootstrap_node.js:139:9)

여기서 볼 수 있듯이, 더이상 factorial 호출이 동시에 하나 이상 스택에 쌓이지 않는데, 왜냐하면 매번 호출할 때마다 이전 프레임이 더이상 필요없기 때문이다.

꼬리 재귀 함수를 만들기 위한 팁은 이전 프레임을 제거할 수 있도록 다음 호출을 할 때 필요한 모든 “상태”를 넘겨주는 것이다. 단일 함수만을 가지고 항상 가능하지는 않으므로, 꼬리 재귀가 가능한 중첩 함수를 만들 수 있는지도 고려해볼 수 있을 것이다.

또하나 명심해야 할 것은, 적절한 꼬리 호출이 코드 실행을 반드시 빠르게 해 주는 것은 아니라는 것이다. 사실은, 오히려 느리게 만드는 경우가 대부분이다.

하지만, 꼬리 함수를 사용하게 되면 스택을 위한 메모리를 더 적게 사용할 수 있을 뿐만 아니라 국지적으로(locally) 할당된 객체들을 갖게됨으로써, 적은 메모리만 갖고도 재귀 함수를 실행할 수 있게 된다. 왜냐하면 현재 프레임 내부에 다음 재귀 호출을 위한 변수들이 필요없기 때문에, 가비지 컬렉터로 하여금 현재 프레임에 할당된 모든 객체를 수집해 가도록 할 수 있기 때문이다. 반면에, 꼬리 재귀가 아닌 함수들은 마지막 재귀함수 (기본 케이스)가 반환할 때까지 모든 호출들이 스택에 유지되어야 하기 때문에 매번 메모리 할당이 일어날 수 밖에 없다.

꼬리 호출 최적화 (TCO : Tail Call Optimization)

적절한 꼬리 호출때 발생하는 일들과 다르게, 꼬리 호출 최적화는 꼬리 재귀 함수들의 성능을 향상시켜서 빠르게 실행될 수 있도록 한다.

꼬리 호출 최적화는 컴파일러가 재귀 호출을  jumps 를 이용한 루프 형태로 변경시키는 기법이다.

이미 우리는 꼬리 재귀 함수가 어떻게 작동하는지 알고 있기 때문에, 꼬리 최적화에 대해 설명하기가 아주 쉬워졌다.

앞서 사용했던 factorial 함수를 이용해서, 꼬리 호출 최적화가 활성화된 자바스크립트 엔진에서 어떤 일이 발생하는지를 살펴보자.

다음 코드로 시작하자.

function factorial(n, total = 1) {
    if (n === 0) {
        return total
    }

    return factorial(n - 1, n * total)
}

탈출 조건(“기본 케이스”)이 만족될때까지 반복되는 코드라는 것을 생각한다면, 함수를 다시 호출하는 대신에 코드 안에 레이블을 넣어서 해당 위치로 바로 점프할 수 있을 것이다. 그러면 다음과 같은 코드가 될 것이다.

function factorial(n, total = 1) {
    LABEL:
        if (n === 0) {
            return total
        }
        total = n * total
        n = n - 1
        goto LABEL
}

즉, 꼬리 호출 최적화는 적절한 꼬리 호출과는 별개의 개념이다!

적절한 꼬리 호출과 꼬리 호출 최적화의 단점

이전 예제에서 보았듯이, 적절한 꼬리 호출은 모든 함수 호출의 이력을 “저장”하지 않는다는 의미가 될 수 있다. 즉, 현재 상황을 만들어낸 모든 호출들의 정보를 갖고있지 않게 되는데, 이로 인해 스택 트레이스를 읽어서 버그를 발견해내기가 어려워질 수도 있다.

이는 console.trace 구문뿐 아니라  Error.stack 프라퍼티에도 영향을 미치는데, 여기에 관해서는 아까 언급했던 글에서 다루고 있다.

한가지 가능한 해결책은 개발 환경에서 “가상 스택(Shadow Stack)”을 만드는 것이다.

가상 스택은 “제2의 스택” 처럼 작동한다. 일반 스택이 적절한 꼬리 재귀 호출이 만들어졌을 때 프레임들을 보존하지 않기 때문에, 이 호출들을 “가상 스택”에 쌓으면 디버깅 목적으로 활용할 수 있으면서도 실행 스택에는 추가되지 않도록 할 수 있다.

하지만 이를 쉽게 사용할 수 있도록 잘 만들어진 도구가 부족하며, 이 방식 또한 모든 프레임들을 다른 장소에 저장하기 위해서 추가적인 메모리가 필요하게 된다. (이는 개발 환경에서는 문제가 아닐 수도 있다)

마지막으로, 가상 스택을 사용한다고 해도 꼬리 호출 최적화를 사용한다면 Error.stack 프라퍼티 관련 문제를 해결해주지는 못하는데, 이 경우 goto 구문을 이용해서 더이상 스택 트레이스에 프레임을 추가하지 않게 되기 때문이다. 즉, 에러가 발생했을 때 스택안에 해당 함수가 없을 수도 있는데, 왜냐하면 그 구문에 도달하기 위해 함수 호출을 한 것이 아니라 레이블 위치로 점프했기 때문이다.

만약 더 관심이 있다면, Webkit이 어떻게 꼬리 호출을 다루는지에 대해 Michael Saboff가 쓴 훌륭한 글을 읽어보길 권한다.

문법적 꼬리 호출 (STC: Syntactic Tail Calls)

문법적 꼬리 호출은 컴파일러에게 언제 적절한 꼬리 호출이나 꼬리 호출 최적화를 원하는지 알려주는 방법이다.

이 방식으로 개발자들은 해당 기능을 사용할지 말지를 선택할 수 있다. 이는 기본적으로 정말 단순히 명시적인 방식이다.

이는 생략된 스택 프레임들의 복잡도를 관리할 수 있도록 해 주며, 또한 “덜 간섭적인 해결책 (혹은 전혀 해결책이 아닌)” (제안서에 따르면) 에 대한 새로운 가능성을 열어준다.

문법에 대해서는 몇가지 대안들이 논의되고 있는데, 여기에서 바로 확인할 수 있다.

지금 현재 이 제안은 스테이지 0 상태이다.

관련 문서