자바 테일 호출 최적화
이 자습서에서는 꼬리 호출 최적화(TCO라고도 함)와 Java에 존재하지 않는 이유에 대해 설명합니다. 또한 Java에서 TCO를 시뮬레이션하는 데 사용할 수 있는 몇 가지 다른 방법도 살펴보겠습니다.
테일 콜 최적화란?
꼬리 호출 최적화는 호출 함수가 호출된 함수에서 받은 값을 반환하기 때문에 함수에 대해 하나의 새 스택 프레임을 할당하지 않아도 되는 프로세스입니다.
가장 일반적인 용도 중 하나는 꼬리 재귀(함수가 끝/꼬리에서 자신을 호출하는 재귀 함수)입니다. 여기서 재귀 메서드는 꼬리 호출 최적화를 활용하고 상수 스택 공간을 사용할 수 있도록 작성되었습니다.
Scheme은 모든 구현이 이 최적화를 제공해야 함을 사양에서 보장하는 프로그래밍 언어 중 하나입니다. 따라서 다음은 Scheme 프로그래밍 언어에서 계승 방법의 두 가지 예입니다.
예제 코드 1(꼬리 재귀 없음):
(define (factorial n)
(if (= n 0) 1
(* n (factorial (- n 1)))))
예제 코드 2(꼬리 재귀 포함):
(define (factorial n)
(define (factorial-tail n accum)
(if (= n 0) accum
(factorial-tail (- n 1) (* n accum))))
(factorial-tail n 1))
예제 코드 1에서 함수는 꼬리 재귀가 아닙니다. 재귀 호출이 이루어질 때마다(계승 예제 고려) 메서드는 호출이 반환된 후 결과와 관련하여 필요한 곱셈을 추적해야 하기 때문입니다.
따라서 스택은 다음과 같습니다.
(factorial 3)
(* 3 (factorial 2))
(* 3 (* 2 (factorial 1)))
(* 3 (* 2 (* 1 (factorial 0))))
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6
반대로 tail-recursive 계승에 대한 스택 추적은 다음과 같습니다.
(factorial 3)
(factorial-tail 3 1)
(factorial-tail 2 3)
(factorial-tail 1 6)
(factorial-tail 0 6)
6
factorial-tail에 대한 각 호출에 대해 동일한 데이터만 추적하면 됩니다.
그 이유는 우리가 (factorial 1000000)을 호출하더라도 ( 계승 3).
테일이 아닌 재귀 팩토리얼을 고려하는 경우에는 그렇지 않으며 값이 크면 스택 오버플로가 발생할 수 있습니다.
Java에서 꼬리 호출 최적화가 없는 이유
현재 컴파일러 수준에서 Java 꼬리 호출 최적화는 일반 Java에서 지원되지 않습니다. 상속의 존재로 인해 호출되는 메서드를 찾는 것이 쉽지 않을 수 있습니다.
또한 현재 스택 카운팅 메커니즘은 이러한 종류의 최적화가 곧 구현되는 것을 허용하지 않습니다. 매년 언어 작동 방식의 급격한 변화를 피해야 하는 이유가 있을 수 있습니다.
첫 번째 이유는 Tail Call Optimization이 비싸기 때문입니다. 둘째, Java의 규칙에 따라 오류가 발생할 때마다 스택 추적을 얻습니다.
그리고 스택 추적은 모든 논리적 호출에 대해 하나의 스택 프레임을 거의 추적할 수 없는 잘 정의된 개념입니다. 꼬리 호출 최적화가 Java에 있는 경우에는 불가능합니다.
셋째, 모델로서의 꼬리 호출 최적화는 작업을 수행하는 방법이지만 유일한 방법은 아닙니다. 일반적으로 TCO 재귀 앱으로 작성할 수 있는 모든 것에 대해 루프 기반 비재귀 알고리즘으로 리팩터링하는 것은 그리 어렵지 않습니다.
그럼 어떻게 해야 할까요? 대신 while 또는 for 루프를 사용할 수 있습니다.
Java에서 꼬리 호출 최적화를 시뮬레이션하는 방법이 있습니까?
가상 머신인 Java에는 다른 사용자가 작업을 더 쉽게 수행할 수 있는 새로운 기능이 있지만, Java 이외의 프로그래밍 언어는 클래스 파일로 컴파일되어 꼬리 호출 최적화를 지원하기 위해 Java 런타임에서 실행됩니다.
특히 언어가 가장 인기 있는 언어 중 하나일 때 모든 기능이 항상 정당화되는 것은 아니기 때문에 큰 그림에서 사물을 이해하려면 다음 두 비디오를 시청하는 것이 좋습니다.
- 동영상 1: Brian Goetz - Stewardship: the Sobering Parts
- 동영상 2: 자바 언어와 플랫폼의 미래
따라서 Java에서 TCO를 사용하기 위해 어떤 접근 방식을 사용해야 하는지 확신할 수 없습니다. Project Loom의 제안에 잘 설명되어 있습니다.
그러나 Java에서 꼬리 호출 최적화를 시뮬레이션하는 데 사용할 수 있는 몇 가지 다른 방법이 여전히 있다고 생각합니다. 첫 번째는 Scala와 같은 다른 JVM 언어를 사용하는 것입니다.
두 번째 해결책은 lambda 표현식을 사용하는 것입니다. 또는 감히 이것과 같은 위험한 것을 시도할 수 있습니다.
