CBV와 CBN을 모두 아우르는 Call-by-Push-Value(CBPV)를 소개하고, 값과 계산의 분리를 통해 성능 최적화부터 타입 추론, 효과 추적, 호출 규약까지 새 가능성을 여는 방식을 사례와 함께 설명한다.
갈림길에서 함수 인자 하나를 만난다. 왼쪽 길로 가면 스스로를 먼저 평가한 뒤 함수에 넘겨질 것이고, 오른쪽 길로 가면 일단 함수에 넘겨지고 나중에 어딘가에서 평가될 것이다(🥁🐍). 어느 길이 더 빠를지 내기를 해보자.
아마 꽤 시시한 내기라고 생각할 수도 있다. 그냥 각 길을 내려다보고 더 짧은 쪽을 고르면 되니 말이다. 다행인지 불행인지(이 분야 이론가들에겐 유감), 현실은 그렇지 않다. 언제나 미리 평가하는 편이 유리한 경우도, 게으르게 평가하는 편이 유리한 경우도 구성할 수 있다.
이 내기는 프로그래밍 언어 의미론의 고전적 질문, 즉 call-by-value(CBV)로 할 것인가 call-by-name/call-by-need(CBN)로 할 것인가에 닿아 있다. 둘 다 식을 어떤 순서로 평가할지를 결정하는 평가 전략이다. CBV는 함수 인자를 함수에 넘기기 전에 항상 평가한다(즉, eager 평가). CBN은 함수 본문에서 실제로 사용될 때까지 인자 평가를 미룬다(즉, lazy 평가).
언어들은 보통 하나를 택해 모든 함수 적용에 그것을 쓴다. Rust, Java, JavaScript, Python, C/C++는 CBV를 쓴다. Haskell 그리고… 어… Haskell은 CBN을 쓴다. 하지만 무엇을 택하든 옆 동네 풀이 더 푸르게 보이기 마련이다. CBV 언어들은 작게나마 게으른 평가(클로저, 이터레이터 등)를 들여오고, CBN 언어는 반대로 성급한 평가를 들여온다. Haskell도 자료형을 기본적으로 eager하게 만들도록 언어를 확장했다.
CBV와 CBN 언어가 결국 eager와 lazy 평가를 모두 원하게 된다면, 왜 우리는 하나를 고르고 다른 하나를 통째로 포기해야만 할까? 사실 그럴 필요가 없다. 다만 우리가 그 많은 언어들을 설계할 때는 아직 몰랐을 뿐이다. …이런.
Levy의 ’99년 논문 Call by Push Value: A Subsuming Paradigm은 CBV/CBN 스펙트럼에 세 번째 선택지, Call-by-Push-Value(CBPV)를 제시한다. 자바스크립트 프레임워크의 관점에선 ’99년이면 거의 백악기지만, 연구의 관점에선 꽤 최근이다. CBPV는 이제 막 대중적 담론에 스며들기 시작했고, 여러 “calling-by” 접근들 중 단연 가장 유망하다.
CBPV가 왜 멋진지 말하려면, 먼저 그것이 무엇인지부터 알아야 한다. CBPV의 핵심 아이디어는 하나의 의미 체계로 CBV와 CBN을 모두 지원하는 것이다. 이를 위해 값(value)과 계산(computation)을 구분한다. 논문은 직관을 잡아주는 멋진 슬로건을 준다: “계산은 한다(do), 값은 있다(is)”.
좋다. 그런데 그게 정확히 무슨 뜻일까? 대비를 위해 전통적인 람다 계산을 먼저 보자. 그리고 이를 바탕으로 CBPV 람다 계산을 살펴보자:
data Type
= Int
| Fun Type Type
data Term
= Var Text
| Int Int
| Fun Text Term
| App Term Term
App 항을 어떻게 실행하느냐에 따라 이 계산은 CBV가 될 수도, CBN이 될 수도 있다(하지만 둘 다는 아니다). 인자를 먼저 평가한 뒤 함수에 적용하면 CBV다. 인자를 평가하지 않은 채 함수에 적용하면 CBN이다.
하지만 우리는 둘 중 하나를 골라야만 한다. 이는 값과 계산이 하나의 항 안에서 모호하게 섞여 있기 때문이다. CBN은 App이 계산을 받길 원하고, CBV는 App이 값을 받길 원한다. 둘을 구분할 수 없으니 하나를 강제로 택해야 한다. 우리의 CBPV 람다 계산은 값과 계산을 둘로 갈라 이 문제를 고친다:
-- 값의 타입
data ValType
= Int
| Thunk CompType
-- 계산의 타입
data CompType
= Fun ValType CompType -- !!
| Return ValType
-- 값 항
data Value
= Int Int
| Var Text
| Thunk Comp
-- 계산 항
data Comp
= Fun Text Comp
| App Comp Value
| Return Value
이로써 CPBV는 고르디우스의 매듭을 잘라 모든 ‘적용’의 지배자가 되었다. 아주 마음에 든다. 다만, 그걸 위해 기물은 꽤 늘어났다(줄 수가 두 배가 됐다). 이제 무엇이 값이고 무엇이 계산인지 극명해졌다. 놀라운 점 하나는 변수(Var)가 값이라는 사실이다. 만약 변수가 계산에 바인딩되어 있다면? CBPV의 계시는 이렇다: “그건 걱정할 필요 없다”(솔직히 말하면 나는 살짝 걱정되지만).
새로운 App 노드를 보면, 이제 오직 값에만 적용할 수 있다. 다행히 여전히 변수를 함수에 넘길 수 있다는 뜻이다. 그런데 CBN은 평가되지 않은 인자를 주고받는다. 핵심은 그것들이 아직 값으로 평가되지 않은 ‘계산’이라는 점이다. 모든 변수가 값이고, 모든 함수 인자가 값이라면, 그건 어떻게 하지? 해답은 새로운 Value 노드인 Thunk에 있다.
Thunk는 계산을 값으로 포장한다. 계산을 함수에 적용하고 싶다면, 먼저 Thunk로 값을 만들어야 한다. 이 강제성 덕분에 CPBV는 아주 유용해진다. 계산을 값으로 포장하는 지점을 명시적으로 만들면, 우리가 “일(작업)”을 추론하는 능력이 커진다.
새 Comp 노드인 Fun에서도 같은 예를 볼 수 있다. Fun은 오직 Comp만을 반환할 수 있다. Fun은 계산이므로 중첩해 다중 인자 함수를 만들 수 있다. 그런데 함수에서 함수를 반환하려면 어떻게 해야 할까?
그럴 때 마지막 새 노드 Return을 쓴다. Return은 Thunk의 짝이다. Value를 Computation으로 바꾼다. Return을 이용하면 다음처럼 함수를 반환하는 함수를 만들 수 있다:
(Fun "x" (Return (Thunk (Fun "y" (Return (Var "x"))))))
겉멋처럼 보일 수도 있다. 사람이 쓰는 표면 언어라면 나도 동의한다. 하지만 컴파일러 IR에서는 이 구분이 훨씬 더 효율적인 코드를 생성하게 해준다.
이제 CBPV가 무엇인지 알았으니, 왜 CBPV가 미래인지 말해보자. 큰 장점 하나는 계산을 값으로(또 그 반대로) 바꾸는 지점을 명시적으로 만든다는 점이다. 그 맥락을 잡기 위해, 런타임에 함수에 인자를 적용하기 위해 필요한 이 괴물을 보자: Making a fast curry
함수의 arity를 조회해야 할 뿐 아니라, 우리가 호출하는 게 함수인지 클로저인지도 조회해야 한다. 더 나쁜 건 이 모든 작업이 런타임에 수행되어야 한다는 점이다. 이런 두통은 CBPV에선 사라진다. 만약 다음을 보면:
(Fun "x" (Fun "y" (Return (Var "x"))))
인자를 두 개 적용해야 함을 안다. 반면 다음을 보면:
(Fun "x" (Return (Thunk (Fun "y" (Return (Var "x"))))))
인자를 하나만 적용할 수 있고, 그다음엔 더 진행하기 전에 처리해야 할 값이 생긴다. 이 항에 인자를 두 개 적용하는 것은 애초에 유효한(term) 표현이 아니다.
값과 계산을 명시적으로 나누는 일은 단지 최적화에만 도움이 되는 게 아니다. 이전엔 못 하던 새로운 일들을 가능하게 한다. 사실 이것이 바로 내가 이 글을 쓰게 된 계기다. 서로 관계없어 보이는 논문들이 CBPV를 이용해 자신의 작업을 가능하게 만드는 것을 자주 보았기 때문이다. CPBV가 할 수 있는 서로 다른 일들을 그 논문들을 통해 보자:
대수적 효과는 부작용을 타입으로 추적하는 데 관심이 있다. 이를 시도하자마자 마주치는 문제: 효과는 어디에서 발생할 수 있는가? 함수가 효과를 일으킬 수 있다는 건 쉽다. 그럼 레코드는 어떤가, 레코드도 효과를 일으킬 수 있는가? 글쎄, 레코드는 값이니 불가능하다고 하자. 그런데 그 레코드에 효과를 일으키는 함수가 들어 있다면?
CBPV는 이런 난제를 능숙하게 처리한다. 효과는 계산 타입에만, 오직 계산 타입에만 나타날 수 있다. 함수는 계산을 반환하므로 효과를 가질 수 있다. 하지만 레코드는 값이므로 다른 값만 담을 수 있고, ‘효과’는 담을 수 없다.
레코드에 함수를 넣고 싶다면 먼저 그것을 Thunk로 감싸 값으로 만들어야 한다. 그러면 그 레코드 자체는 효과를 낼 수 없다. 레코드 안 함수의 효과를 수행하고 싶다면 먼저 Return으로 다시 계산으로 되돌려야 한다. CBPV는 프로그램에서 효과가 어디서 발생할 수 있고(또 어디서는 절대 발생할 수 없는지)을 명확하고 명시적으로 해준다.
이름은 위압적이지만 정말 멋지다. 타입 추론 얘기다(이 주제는 우리가 좀 알지). 타입 추론기의 오랜 딜레마는 제네릭 타입이다. 제네릭 타입이 다른 제네릭 타입으로 추론되도록 허용하면, 타입 추론은 결정불가능해진다. 곤란하다. 멋진 타입들 중 상당수가 이런 중첩 제네릭(랭크-2, 랭크-N, 또는 임프레디케이티브 타입)을 포함하는데, 이를 추론할 수 없으면 손으로 일일이 적어야 한다. 정말 죽기보다 싫은 일이라, 이 타입들은 심각하게 저활용된다.
이 논문은 가끔은 그런 타입들을 추론할 수 있게 하며 그 문제를 일부 덜어준다. 가끔이라니 약하다고 느낄 수도 있지만, 결코 못 하는 것보다는 무한히 낫다. 비결은, 맞다, CBPV다. 앞서 보았듯 call-by-push-value는 함수가 포화 호출(saturated)인지, 아니면 클로저를 반환하는지 명시적으로 드러낸다.
이는 타입 추론 도중 가져야 할 결정적 정보로 드러난다. 포화 호출된 함수는 모든 인자를 받았고, 그 인자들이 함수 타입을 추론하기에 충분한 정보를 제공할 수 있다. 함수 타입에 중첩 제네릭이 포함되어 있어도 말이다. 꽤 신난다! 언어 의미론에서 더 영리한 선택을 했더니 코드에 필요한 주석(어노테이션)이 줄어들었다.
Kinds Are Calling Conventions는 매혹적인 논문이다. 이 논문은 지나치게 제네릭한 언어들이 태곳적 베타 리덕션 이래로 겪어 온 문제들을 ‘kind’로 해결한다:
이 문제를 풀기 위해 타입에 더 정교한 kind를 부여한다. 예컨대 타입 Int가 kind TYPE을 갖는 대신 TYPE Ptr을 갖는다. 비슷하게 타입 Int -> Int -> Int에는 kind TYPE Call[Int, Int]를 부여한다. 이는 arity 2의 함수임을 kind 수준에서 나타낸다. 여기서 CBPV가 등장한다.
어떤 타입의 kind에 arity를 제공하려면, 먼저 함수의 arity를 알아야 한다. 함수와 클로저를 자유롭게 서로 바꾸어 쓰는 CBV나 CBN 언어에서는 이게 까다롭다. 다행히 CBPV에서는 오직 타입만으로도 어떤 함수의 arity가 무엇인지 아주 분명하다.
Kinds Are Calling Conventions는 이를 최대한 활용해 고차 함수에 대한 효율적 호출 코드를 생성한다. 또한 CBPV가 eager와 lazy 평가를 모두 허용한다는 사실을 이용해, 인자가 어떻게 평가되는지를 kind에 기록한다. 모두 더 효율적인 기계어를 생성하기 위한 일이다. 이렇게 이론적인 접근이 이렇게 현실적인 목표에 봉사할 줄이야, 누가 알았겠는가.
세상에서 CBPV를 볼 때마다 5센트씩 받는다면, 지금 내게는 3닙켈이 있을 것이다. 많진 않지만, 세 번이나 일어났다는 게 신기하다. 개인적으로, 이는 CBPV가 우주의 어떤 진리를 정확히 건드렸기 때문이라고 믿는다. 무엇이 계산이고 무엇이 값인지 명시적으로 만드는 것은 프로그램에 대한 더 많은 성질을 추론하게 해준다.
이는 프로그램을 더 잘 최적화하게 해줄 뿐 아니라, 새로운 형태의 다형성을 가능하게 하고 더 근사한 타입들도 유한 시간 안에 판정할 수 있게 해준다. 연구 역사에서 보자면 CBPV는 상당히 최근의 개념이므로, 지금 우리가 보는 것은 CBPV로 할 수 있는 일들의 시작일 뿐이고 앞으로도 더 많은 것을 발견하게 될 것이다. 나도 내 몫을 하고 있다. 믿어도 좋다, 내 언어는 반드시 call-by-push-value 위에 지어질 것이다.