Futhark가 재귀 함수를 허용하지 않고 대신 `loop` 구문을 제공하는 이유, 그리고 꼬리 호출 제거를 일반화하기 어려운 배경을 설명한다.
URL: https://futhark-lang.org/blog/2026-01-20-why-not-tail-recursion.html
2026년 1월 20일에 게시됨 — Troels Henriksen
이 글은 /r/ProgrammingLanguages에서의 이 토론에서 영감을 받았다.
Futhark는 함수형 프로그래밍 언어들 가운데서 함수가 재귀적일 수 없다는 점에서 이례적이다. 이는 어느 정도 Futhark가 병렬 언어이며, 재귀적 루프는 본질적으로 순차적인 연산이기 때문에 덜 중요하다는 점으로 정당화될 수 있다. 하지만 대부분의 비자명한 병렬 알고리즘도 어느 정도의 순차적 루프를 포함하므로, 이 기능을 완전히 빼버릴 수는 없다. 그럼에도 Futhark가 여전히 재귀 함수를 허용하지 않는 이유는 제한된 타깃, 특히 GPU를 위한 코드를 생성하려는 목표 때문이다. GPU에서는 스택 사용에 대한 제약 때문에 재귀가 기껏해야 비효율적이고, 종종 아예 불가능하다. 이 문제에 대한 우리의 해결책은 의미론적으로는 “로컬 꼬리 재귀 함수”에 불과한 순차적 루프를 위한 전용 구문을 제공하는 것이다:
loop acc = 1 for i < n do acc * (i+1)
이 구문은 루프 매개변수 acc를 정의한다. acc는 처음에 1로 설정되고, 그 다음 n번 본문 acc * (i+1)을 평가한다. 각 반복에서 acc 매개변수는 이전 반복에서 본문이 반환한 값으로 다시 바인딩된다. 이는 다음 꼬리 재귀 함수와 동등하다:
def loop acc i = if i < n
then loop (acc * (i+1)) (i+1)
else acc
이를 처음에 loop 1 0으로 호출한 것과 같다. while 루프를 위한 변형도 존재한다. 이 설계의 장점은 스택 공간을 전혀 사용하지 않고도 루프를 명확히 허용한다는 점이다.
하지만 많은 함수형 언어에서는 재귀가 루프의 주된, 혹은 유일한 방법이다. 이런 언어들은 보통 꼬리 호출 제거(tail call elimination)를 수행하는데, 이는 호출자의 스택 공간을 피호출자가 재사용하도록 하는 기법이다. 그렇다면 Futhark에서도 그냥 그렇게 하면 되지 않을까?
한 가지 이유는 대부분의 Futhark 백엔드가 기계어를 직접 생성하지 않고, 대신 C를 생성한 다음 어떤 하류(downstream) C 컴파일러가 이를 처리하게 한다는 점이다. 이 설계 선택의 장단점은 아마 나중에 별도의 블로그 글로 다룰 만하지만, 핵심적인 단점은 우리가 C에서 쉽게(그리고 바람직하게는 이식 가능하게) 표현할 수 있는 것만 표현할 수 있다는 점이며, 꼬리 호출은 그런 종류의 것이 아니다. 트램폴리닝(trampolining) 같은 잘 알려진 구현 기법들이 있지만, GPU 드라이버가 제공하는 커널 컴파일러를 혼란스럽게 만들까 걱정된다. Futhark는 일반적으로 이런 컴파일러들이 기대하는 모양의 C 코드를 생성할 때 이득을 보고, 우리가 거기서 벗어나면 종종 고생한다. 여러 차례 언급했듯이, Futhark의 주된 목표는 단지 어떻게든 실행되는 것이 아니라 빠르게 실행되는 것이며, 빠르게 실행할 수 없는 기능에는 관심이 없다. 주된 목표가 그저 멋진 함수형 프로그램을 작성하는 것이라면 Futhark는 필요 없다.
좋다. 그러면 일반적인 꼬리 호출 제거는 제외하더라도, 꼬리 재귀 정도는 어떨까? 이는 항상 C의 for 또는 while 루프로 다시 쓸 수 있다(이것이 Futhark의 loop에 영감을 준 것이기도 하다). 여기서 문제는, Futhark에서는 이런 꼬리 호출을 최적화하는 것이 단지 “있으면 좋은 최적화”가 아니라, 철통같은 보장이어야 한다는 점이다. 재귀가 꼬리 위치(tail position)가 아닌 경우(따라서 제거할 수 없는 경우) 프로그램은 반드시 거부되어야 한다. 재귀 깊이에 비례해 스택 공간을 소비하는 것은 용납할 수 없기 때문이다.
알고 보니 대부분의 함수형 언어는 꼬리 재귀가 최적화된다고 _약속_하지는 않는다. 물론 실제로는 대체로 꽤 잘 해내는 편이지만 말이다. 이 영역에서 최초로 _약속_을 하고 그 약속의 경계를 정확히 명시한 언어 중 하나는 Scheme이라고 생각한다. 내가 이해하는 Scheme의 마지막 명세, 즉 다섯 번째 명세에서 꼬리 호출은 3.5절에 정의되어 있다. 그 규칙들은, 나머지 부분이 유명할 정도로 우아한 정의인 것과 달리, 구문에 의해 좌우되는 “어떤 적용(application)이 꼬리 위치인지”에 대한 규칙 목록에 가깝다는 점에서 일종의 우회로처럼 보인다. 이 규칙들은 매크로 확장 이후에 적용되어야 하는 것 같지만, 명시적으로 언급되어 있지는 않은 것 같다.
이 규칙들은 단순하고 예측 가능하지만, 나는 이런 규칙들이 프로그래밍 스타일의 피상적인 요소에 제약을 가한다는 점이 마음에 들지 않는다. Haskell로 작성한 꼬리 재귀 팩토리얼 함수를 보자:
fact acc i = if i == 0 then acc
else fact (acc*i) (i-1)
재귀 호출 fact를 꼬리 호출로 분류하는 어떤 구문 기반 규칙을 쉽게 상상할 수 있다. 하지만 Haskell 프로그래머들은 괄호를 몹시 싫어해서, 대신 이렇게 쓸 수도 있다:
fact acc i = if i == 0 then acc
else fact (acc*i) $ i-1
$ 연산자는 라이브러리 정의(언어 내장 기능이 아님)로, 단지 우선순위가 낮은 함수 적용일 뿐이다. 의미론적 목적은 없지만 f (g (h x)) 같은 긴 적용 사슬을 f $ g $ h x로 쓸 수 있게 해 준다. 이는 F#로 대중화된 파이프라인 연산자 |>와 같은 목적을 갖는다. 문제는 위 함수에서 꼬리 위치에 있는 함수 호출이 더 이상 fact에 대한 호출이 아니라 $에 대한 호출이라는 점이다. 따라서 이는 더 이상 명백한 꼬리 재귀 함수가 아니다. $가 무엇을 하는지 알고, 아마 인라인까지 해야만 fact가 여전히 꼬리 재귀임을 알 수 있다. 꼬리 호출 최적화가 “있으면 좋은” 최적화일 때는 괜찮지만, 비꼬리 재귀를 거부하고 싶은 Futhark에서는 받아들일 수 없다. 타입 체커를 통과한 어떤 프로그램이든 컴파일되어야 하며(우리가 완벽히 지키지는 못하지만), 잘-타입됨(well-typedness)을 지배하는 규칙은 단순하고 조합적이어야 한다. 나는 약속을 지키는 것을 좋아하고, 이해하기 쉬운 약속을 하는 것도 좋아한다.
언어 설계자는 선택을 강요받는 듯 보인다. 프로그래머의 코딩 스타일을 제약하는 다소 경직된 구문 기반 규칙 아래에서만 꼬리 재귀를 허용하든가, 혹은 타입 체커에 복잡한 규칙이나 분석을 넣어서 때때로 이해하기 어려운 이유로 프로그램을 거부하게 만들든가 말이다. (또는 세 번째 선택: $ 및 비슷한 함수들의 동작을 타입으로 표현할 수 있도록 타입 시스템을 훨씬 더 복잡하게 만들기.)
Futhark는 사막 언어(desert language)이므로, 우리는 언제나 언어에 가장 적은 복잡성을 더하는 선택, 즉 첫 번째 선택을 고른다. 하지만 우리는 여기서 더 나아가, 꼬리 재귀가 필요할 때는 전용 loop 구문을 반드시 요구한다. 특히 재귀 호출이 암시되어 있기 때문에, 그것을 비꼬리 위치에 둘 방법이 없다. 이는 곧 Futhark로 프로그래밍할 때 배워야 하고 염두에 둬야 할 규칙이 더 적다는 뜻이다. 프로그래머는 언어가 자신의 재귀적 비전을 받아들이지 않는 인위적인 무능함에 고개를 젓게 될지도 모르지만, 결국 도전은 “절대로 동작하지 않을 무언가를 몰래 끼워 넣기 위해 언어의 미세한 경계를 따져보기”가 아니라, “재귀가 필요 없도록 알고리즘을 어떻게 작성할 것인가”로 바뀐다.