당신이 탐정이 되어 미스터리를 해결하고 있다고 상상해 보세요. 하지만 어두운 골목에서 단서를 찾는 대신, 컴퓨터 프로그램 내부를 들여다보고 있습니다. 구체적으로는, 어떤 경로로 갈지 결정하기 위해 동전 던지기를 하는 것과 같은 무작위 선택을 하는 프로그램을 보고 있습니다. 컴퓨터 과학의 세계에서 이것은 "확률적 프로그램(probabilistic program)"이라고 불립니다. 이러한 프로그램은 마치 마법의 주사위 굴리기와 같습니다. 단순히 한 가지 일만 하는 것이 아니라, 일어날 확률에 따라 여러 가지 일을 수행합니다. 이들은 무작위적이기 때문에, 우리는 단순히 "작동했는가?"라고 물을 수 없습니다. 대신 "평균적으로 얼마나 잘 작동했는가?" 그리고 "시도하는 동안 얼마나 많은 에너지나 시간을 낭비했는가?"라고 물어야 합니다.

오랫동안 이러한 무작위 프로그램들을 검증하는 것은 맨손으로 미끄러운 물고기를 잡으려는 것과 같았습니다. 당신은 물고기(코드)를 볼 수 있고 수학(확률론)도 알고 있지만, 그 "비용"(시간이나 배터리 등)이 정확히 얼마나 들지 증명하는 것은 매우 어렵습니다. 보통, 사람들은 두 개의 별개 이야기를 써야 했습니다. 하나는 프로그램이 무엇을 하는지에 대한 이야기이고, 다른 하나는 그것이 얼마나 비용이 드는지에 대한 길고 지루한 매뉴얼입니다. 그런 다음 이 두 이야기를 한 줄 한 줄 직접 맞추어 두 이야기가 서로 일치하는지 확인해야 했습니다. 이는 매우 번거롭고 인간의 실수에 취약하며, 종종 사람들이 자신들의 무작위 알고리즘이 실제로 안전하고 효율적인지 검증하는 것을 가로막았습니다.

여기서 오스트리아와 독일의 연구진이 새로운 도구를 가지고 등장합니다. 그들은 Liquid Haskell이라는 프로그래밍 언어를 위한 특별한 "비용 인식 확률 모나드(cost-aware probability monad)"를 구축했습니다. "모나드"를 프로그램이 메고 다니는 마법의 배낭이라고 생각해 보세요. 보통 이 배낭은 무작위 선택의 결과만을 담고 있습니다. 하지만 연구진이 만든 이 배 backpack은 특별합니다. 여기에는 내장된 계산기와 GPS가 있습니다. 프로그램이 한 단계를 밟을 때마다, 배낭은 자동으로 총 비용과 그 단계가 일어날 확률을 업데이트합니다. 배낭은 단순히 데이터를 담는 것이 아니라, 수학을 '알고' 있습니다. 이 스마트한 배낭을 사용함으로써, 연구진은 컴퓨터가 무작위 프로그램을 검증하는 것이 얼마나 효율적인지를 보여주었습니다. 이는 어려운 수동 퍼즐을 거의 자동화된 과정으로 바꾸어 놓았습니다. 그들은 리스트 정렬이나 데이터 관리와 같은 고전적인 문제들에 이를 테스트하여, 그들의 새로운 방식이 정확할 뿐만 아니라 이전 방식보다 훨씬 빠르고 사용하기 쉽다는 것을 입증했습니다.

무작위 프로그램을 위한 마법의 배낭

당신이 비디오 게임을 하고 있다고 상상해 보세요. 당신의 캐릭터는 장애물을 뛰어넘어야 합니다. 컴퓨터가 가상의 주사위를 어떻게 던지느냐에 따라 게임은 쉬울 수도 있고 어려울 수도 있습니다. 컴퓨터 과학에서는 이를 "확률적 알고리즘(probabilistic algorithms)"이라고 부릅니다. 이들은 엄격하고 단계적인 지침보다 더 빠르고 똑똑할 수 있어 매우 유용합니다. 하지만 함정이 있습니다. 운에 의존하기 때문에, 이들이 얼마나 많은 "연료"(시간, 돈 또는 컴퓨팅 파워)를 태울지 정확히 예측하기 어렵다는 점입니다.

수년간 컴퓨터 과학자들은 문제를 겪어왔습니다. 무작위 프로그램이 효율적이라는 것을 증명하려면 두 가지를 따로 해야 했습니다. 먼저 프로그램이 올바르게 작동한다는 것을 증명하고, 그다음에는 평균 비용을 계산하기 위해 완전히 새로운 증명을 작성해야 했습니다. 이는 케이크를 굽고 나서, 레시피에 이미 적혀 있음에도 불구하고 설탕을 적절히 사용했음을 증명하기 위해 별도의 에세이를 써야 하는 것과 같았습니다. 이 과정은 느리고 실수가 잦았습니다.

이 논문의 저자인 Matthias Hetzenberger, Georg Moser, Florian Zuleger는 프로그램들을 위한 새로운 종류의 "배낭"을 만듦으로써 이 문제를 해결하기로 했습니다. 프로그래밍 세계에서 "모나드"는 계산을 다루기 쉽게 감싸는 방법입니다. 팀은 **비용 인식 확률 모나드(Cost-Aware Probability Monad)**를 만들었습니다. 이것을 무작위 동전 던지기의 결과만을 담는 것이 아니라, 비용과 확률의 누적 합계까지 함께 들고 다니는 마법의 배낭이라고 생각할 수 있습니다.

작동 방식은 다음과 같습니다:

1. 배낭은 수학을 압니다: 프로그램이 동전을 던질 때(무작위 선택), 배 backpack은 그 던지기의 평균 비용을 자동으로 계산합니다. 사람이 수학을 적어줄 필요 없이, 배낭이 당신을 대신해 수행합니다.
2. 모든 것을 추적합니다: 프로그램이 실행되는 동안, 배낭은 점수를 기록합니다. 만약 프로그램이 1단위의 시간이 드는 단계를 밟으면, 배낭은 총합에 1을 더합니다. 만약 프로그램이 두 갈래 길로 나뉜다면, 배 backpack은 두 경로를 결합한 평균 비용을 계산합니다.
3. 컴퓨터와 대화합니다: 연구진은 Liquid Haskell이라는 도구를 사용했는데, 이는 코드를 검사하는 매우 똑똑한 로봇과 같습니다. 이 "비용 인식 배낭"을 Liquid Haskell에 넣음으로써, 그들은 로봇이 수학을 자동으로 검사하게 했습니다. 로봇은 코드를 보고 "네, 이 무작위 정렬 알고리즘은 평균적으로 $2(n+1)$의 조화수(harmonic number)에서 $4n$을 뺀 단계만큼 걸릴 것입니다"라고 인간의 도움 없이 말할 수 있습니다.

배낭 테스트하기: 힙에서 채용까지

그들의 새로운 배낭이 정말 효과가 있는지 확인하기 위해, 팀은 몇 가지 유명한 컴퓨터 과학 문제에 이를 적용해 보았습니다. 그들은 로봇이 수학 퍼즐을 자동으로 풀 수 있는지, 아니면 여전히 도움이 필요한지 확인하고 싶었습니다.

1. 결합 가능한 힙 (Meldable Heaps - 쉬운 승리)
먼저, 그들은 "결합 가능한 힙(meldable heap)"이라는 데이터 구조를 살펴보았습니다. 두 개의 카드 더미를 하나의 큰 더미로 합치고 싶다고 상상해 보세요. 프로그램은 카드가 어디로 갈지 결정하기 위해 동전을 던져 이 작업을 수행합니다. 연구진은 이 배낭이 이 과정을 거의 완전히 자동화한다는 것을 발견했습니다. 로봇은 코드를 검사했고, 비용이 로그(logarithmic) 단위라는 것(즉, 더미가 아무리 커져도 매우 느리게 증가한다는 의미)을 즉시 확인했습니다. 인간이 준 도움은 로그가 어떻게 작동하는지에 대한 아주 작은 힌트뿐이었습니다. 이는 어떤 문제들에 대해서는 이 새로운 방식이 거의 완벽하며 수동 작업이 거의 필요 없음을 보여주었습니다.

2. 무작위 퀵 정렬 (Randomised Quicksort - 더 어려운 퍼즐)
다음으로, 그들은 숫자가 담긴 리스트를 정렬하는 유명한 방법인 "무작위 퀵 정렬(Randomised Quicksort)"에 도전했습니다. 이것은 조금 더 까다롭습니다. 프로그램은 리스트를 나누기 위해 무작위 숫자를 선택한 다음, 작은 부분과 큰 부분을 각각 정렬합니다. 여기서의 수학은 합계와 패턴을 포함하며, 예측하기 더 어려운 복잡한 과정을 거칩니다.
로봇은 기본적인 부분들은 처리할 수 있었지만, 최종 답(조화수를 포함한 특정 공식)을 얻기 위해서는 인간이 개입하여 로봇이 더 어려운 수학 단계를 통과하도록 가이드해야 했습니다. 이는 로봇이 경주를 달릴 수는 있지만, 마지막 바퀴에서 전략을 설명해 줄 코치가 필요한 것과 같았습니다. 이러한 도움에도 불구하고, 팀은 그들의 방식이 동일한 것을 증명하는 다른 방법들보다 훨씬 짧고 깔고 깔끔하다는 것을 발견했습니다.

3. 스플레이 트리와 채용 (Splay Trees and Hiring - 중간 단계)
그들은 또한 "무작위 스플레이 트리(Randomised Splay Trees)"(자주 사용하는 항목을 위로 이동시켜 데이터를 정리하는 방식)와 "채용 문제(Hiring Problem)"(후보자들을 인터뷰하고 지금까지 중 최고인 사람을 채용하는 시나리오)를 테스트했습니다.

• 스플레이 트리의 경우, 배낭은 "잠재력(potential)"(남은 작업량에 대한 멋진 표현)과 회전(rotation) 비용을 추적하는 데 도움을 주었습니다. 로그에 대한 약간의 인간 힌트가 필요했지만, 로봇이 핵심적인 작업(heavy lifting)을 수행했습니다.
• 채용 문제의 경우, 그들은 후보자들을 무작위 순서로 인터뷰할 때 평균 채용 횟수가 특정 패턴을 따른다는 것을 증명하기 위해 배낭을 사용했습니다. 로봇은 문제를 작은 합계들로 분해함으로써 이를 성공적으로 증명했고, 이 방식이 다양한 유형의 무작위 알고리즘에 잘 작동함을 보여주었습니다.

이것이 미래에 갖는 의미

이 논문의 핵심 결론은 우리가 더 이상 "자동"과 "정확" 사이에서 선택할 필요가 없다는 것입니다. 이전에는 무작위 프로그램의 비용을 체크하고 싶다면 많은 수동 작업이 필요했습니다. 만약 완전히 자동화되기를 원했다면, 답이 유용하지 않을 정도로 문제를 너무 단순화해야 했습니다.

저자들은 프로그램의 구조(배낭) 안에 비용 추적 기능을 직접 구축함으로써, 두 가지 장점을 모두 얻을 수 있다는 것을 보여주었습니다. 컴퓨터는 대부분의 작업을 자동으로 수행할 수 있으며, 수학이 정말 어려워질 때 인간이 처음부터 증명을 다시 쓸 필요 없이 로봇을 안내하며 개입할 수 있습니다.

그들은 또한 자신들의 방식이 **건전하다(sound)**는 것을 증명했습니다. 이는 "수학적으로 정확하다"는 멋진 표현입니다. 그들은 단순히 추측한 것이 아니라, 로봇이 비용이 X라고 말하면 실제 비용도 정말 X라는 것을 보여주었습니다.

물론 한계도 있습니다. 논문은 그들의 배낭이 현재 유한한 시간 내에 유한한 결과로 끝나는 프로그램에만 작동한다고 명시합니다. 아직 영원히 실행되거나 무한한 가능성을 가진 프로그램은 다룰 수 없습니다. 하지만 우리가 오늘날 사용하는 대다수의 유용한 무작위 알고리즘에 대해, 이 새로운 도구는 게임 체인저입니다. 이는 지루하고 실수가 잦은 번거로운 일을 스트림라인화된, 거의 자동화된 과정으로 바꾸어 놓아, 더 빠르고 저렴하며 신뢰할 수 있는 소프트웨어를 만들기 쉽게 해줍니다.

요약하자면, 연구진은 우리의 디지털 탐험가들을 위해 더 똑똑한 배낭을 만들었습니다. 이제 우리의 프로그램이 무작위 모험을 떠날 때, 그들은 스스로 지도와 계산기를 들고 다니며, 보물을 얻기 위해 비용이 얼마나 들지 정확히 알 수 있게 되었습니다.