Rust로 구현하는 꼬리 재귀 인터프리터
이 글은 Rust를 사용하여 가상 머신(VM)의 다양한 디스패치 방식, 특히 꼬리 재귀(Tail-Call) 최적화를 활용한 인터프리터 구현 방법을 설명합니다. 꼬리 재귀를 통해 함수 호출 시 새로운 스택 프레임을 할당하지 않고 점프(Jump)하도록 만들어 성능을 높이고 스택 오버플로우를 방지하는 것이 핵심입니다. 개발자는 스칼라(Scala) 기반의 원본 모델을 참고하여 Rust에 맞는 스택 머신과 스위치 디스패치(Switch Dispatch) 구조를 실험하고 벤치마크합니다.
원문 제목: Tail-Call Interpreters in Rust – Jimmy Ostler 소스: hackernews
본문: Rust로 구현하는 꼬리 재귀 인터프리터 - Jimmy Ostler Rust로 구현하는 꼬리 재귀 인터프리터 2026년 8월 1일 Jimmy Ostler 단어 수: 1636 읽는 데 걸리는 시간: 9분
최근 제 삼항(ternary) 프로젝트를 개선할 방법을 찾던 중, 다양한 VM 디스패치 방식에 대한 글을 우연히 발견했습니다. 저는 꼬리 재귀 해석 기법에 대해 들어본 적이 있었지만, 제게 영감을 주었던 원래 자료를 다시 찾는 데는 약간의 시간이 걸렸습니다. 하지만 이 글은 Scala에서 사용되는 여러 가지 VM 디스패치 방식에 대해 훌륭하게 분석해 놓았습니다. 저는 재미있는 실험으로 스칼라의 방식을 Rust로 구현해 보기로 결심했고(제 프로젝트와 더 관련 있는 몇 가지 변형도 포함), 그 차이를 측정하기 위해 벤치마크를 진행했습니다. 여기서는 두 가지 버전을 살펴볼 것입니다. 하나는 Noel의 스칼라 코드를 모방한 것이고, 다른 하나는 더 복잡하고 전통적인 레지스터 머신을 통해 Rust의 강점을 활용하도록 고안된 것입니다.
꼬리 재귀(Tail-Calls) 꼬리 재귀 해석 기법은 컴파일 중에 일부 재귀 호출을 점프(jump)로 변환하여 새로운 스택 프레임을 할당할 필요를 없애는 기술을 의미합니다. 이는 스칼라(Scala)와 같은 함수형 언어에서 스택 크기를 줄이는 데 매우 유용하지만, 대부분의 컴파일러가 이를 사용하는 편입니다. 더 자세히 알고 싶다면 앞서 언급한 Noel의 훌륭한 글을 꼭 확인해 보시기를 추천합니다. 고수준 최적화를 사용해 컴파일할 때 Rust 역시 이 작업을 수행하며, 불안정한 기능(unstable feature)인 explicit_tail_calls를 사용하면 컴파일러에게 직접 이 최적화를 수행하거나 오류를 반환하라고 지시할 수 있습니다.
스택 머신 (Noel's Machine) 여기서 우리가 쉽게 다룰 수 있는 가장 간단한 머신은 Rust에서 다음과 같이 표현되는 5개의 명령어를 가진 스택 머신입니다: enum ByteCode { Lit ( f64 ), Add , Sub , Mul , Div } 이것은 본질적으로 Noel의 스칼라 코드와 동일합니다. 이것이 스택 머신이기 때문에 Lit(리터럴) 명령어는 스택에 값을 푸시(push)하고, 산술 명령어는 피연산자를 팝(pop)한 다음, 결과 값을 다시 스택에 푸시합니다.
디스패치(Dispatch)
비교 통제 용도(control)로 사용하기 위해 스위치 디스패치(switch dispatch)가 가장 적합합니다. 단순히 바이트코드 배열을 만들고, match 문을 사용하여 이를 반복하며 실행하면 됩니다.
주의: Scala 코드와 비교하기 위해 다소 이상한 방식의 코드를 사용하기로 결정했습니다. 여기에는 수동으로 클로저(closure)를 생성하는 대신 static mut와 unsafe를 사용하는 것이 포함되며, 어쨌든 어떤 의미에서는 제가 그렇게 했습니다. 하지만 저는 Rust를 이런 식으로 작성하는 것을 권장하지 않습니다.
스위치 디스패치(Switch Dispatch)
const STACK_SIZE : usize = 32 ; // 우리의 스택
static mut STACK : & mut [ f32 ] = & mut [ 0 . 0 ; STACK_SIZE ]; // 실행할 명령어 리스트
static mut INSTRS : & [ Instr ] = /* { [Lit(4.0), Lit(3.0)... 등등] } */ ;
// 스택 포인터와 명령어 포인터를 dispatch에 전달합니다.
pub fn dispatch ( sp : usize , ip : usize ) -> f32 {
unsafe {
if ip == INSTRS . len () {
STACK [ sp - 1 ]
} else {
match INSTRS [ ip ] {
Instr :: Lit ( value ) => {
STACK [ sp ] = value ;
become dispatch ( sp + 1 , ip + 1 )
},
Instr :: Add => {
let a = STACK [ sp - 2 ];
let b = STACK [ sp - 1 ];
STACK [ sp - 2 ] = a + b ;
become dispatch ( sp - 1 , ip + 1 )
},
Instr :: Sub => {
let a = STACK [ sp - 2 ];
let b = STACK [ sp - 1 ];
STACK [ sp - 2 ] = a - b ;
become dispatch ( sp - 1 , ip + 1 )
},
Instr :: Mul => {
let a = STACK [ sp - 2 ];
let b = STACK [ sp - 1 ];
STACK [ sp - 2 ] = a * b ;
become dispatch ( sp - 1 , ip + 1 )
},
Instr :: Div => {
let a = STACK [ sp - 2 ];
let b = STACK [ sp - 1 ];
STACK [ sp - 2 ] = a / b ;
become dispatch ( sp - 1 , ip + 1 )
},
}
}
}
}
여기서 우리는 전체 로직을 볼 수 있습니다. 즉, 모든 명령어에 대해 자신을 호출하는 거대한 재귀 함수입니다. become 키워드를 사용했기 때문에 우리의 재귀가 스택 오버플로우로 이어지지 않을 것임을 알고 있습니다. 이는 꽤 멋지고 단순한 전략입니다! 여기에는 너무 복잡한 것은 없습니다.
서브루틴 디스패치(Subroutine Dispatch)
다음으로는 match 문을 대체하는 서브루틴 스레딩(threading)을 살펴봅니다. 열거형(enum) 대신, 우리는 Fn() 트레이트(trait)를 구현하여 호출할 수 있는 구조체(struct)로 명령어를 구현해야 합니다. 이는 기저 구조체가 무엇이든 상관없이 동적인 &dyn Fn()을 호출할 수 있음을 의미합니다. 이제 우리의 바이트코드는 다음과 같이 보입니다(간결함을 위해 일부는 생략됨):
// 이제 명령어는 &dyn Fn()이므로 동적 디스패치(dynamic dispatch)를 사용하여 호출할 수 있습니다.