람다 대신 나무? 계산의 새로운 기초를 제안하는 Tree Calculus

계산이란 뭘까, 그 근본부터 다시 생각해보자

프로그래밍을 하다 보면 "람다(lambda)"라는 단어를 한 번쯤은 만나게 되죠. Python의 lambda x: x + 1처럼 익명 함수를 만들 때 쓰는 그 키워드요. 그런데 이 람다라는 개념은 사실 1930년대에 알론조 처치(Alonzo Church)가 만든 람다 대수(Lambda Calculus)에서 온 거예요. 람다 대수는 "계산이란 무엇인가"를 수학적으로 정의한 체계인데, 튜링 머신과 함께 현대 컴퓨터 과학의 이론적 토대를 이루고 있어요.

그런데 최근 이 람다 대수를 대체할 수 있는 완전히 새로운 계산 모델이 제안됐어요. 이름은 Tree Calculus, 직역하면 "나무 대수"예요. 이름 그대로, 모든 계산을 트리(나무 구조)로 표현하겠다는 아이디어인데요. 단순히 학술적 호기심에서 그치는 게 아니라, 프로그래밍 언어 설계와 소프트웨어 검증 분야에 실질적인 가능성을 열어줄 수 있는 접근이라 눈여겨볼 만해요.

핵심 아이디어: 모든 것은 트리다

람다 대수에서는 모든 것을 함수로 표현해요. 숫자도 함수, 불리언도 함수, 리스트도 함수. 예를 들어 숫자 2는 "함수를 두 번 적용하는 함수"로 인코딩하죠 (처치 인코딩이라고 불러요). 강력하지만, 직관적이진 않아요.

Tree Calculus는 접근이 달라요. 기본 빌딩 블록이 딱 하나, 트리 노드예요. 이게 뭐냐면, 잎사귀(leaf) 하나를 기본 단위로 두고, 노드들을 연결해서 트리를 만드는 거예요. 모든 프로그램, 모든 데이터, 모든 연산이 이 트리 구조 안에서 표현돼요.

구체적으로 보면, Tree Calculus에는 두 가지 구성 요소만 있어요. 첫째는 리프(leaf), 아무것도 담지 않은 빈 노드예요. 둘째는 스템(stem)과 포크(fork), 자식 노드를 가진 노드들이에요. 이 단순한 구조만으로 계산 규칙을 정의할 수 있다는 게 핵심이에요. 마치 레고 블록 하나로 모든 걸 조립하는 것처럼요.

람다 대수에서 가장 핵심적인 연산은 베타 리덕션(beta reduction)이라고 해서, 함수에 인자를 넣어서 결과를 얻는 과정이에요. Tree Calculus에서는 이에 해당하는 트리 리덕션 규칙이 있는데, 트리 노드들이 만나면 특정 패턴에 따라 다른 트리로 변환되는 방식이에요. 규칙 자체가 매우 단순하면서도, 이것만으로 튜링 완전(Turing-complete)한 계산이 가능해요. 즉, 이론적으로 어떤 프로그램이든 이 체계 안에서 표현할 수 있다는 뜻이에요.

람다 대수와 비교하면 뭐가 좋을까

람다 대수는 90년 넘게 쓰여온 검증된 체계인데, 굳이 새로운 걸 만들 이유가 있을까요? Tree Calculus가 주장하는 장점은 크게 두 가지예요.

첫 번째는 자기 자신을 분석할 수 있다는 점이에요. 람다 대수에서 함수는 기본적으로 "블랙박스"예요. 함수를 받아서 그 함수의 내부 구조를 들여다보는 건 불가능하죠. 두 함수가 같은 동작을 하는지 비교하는 것도 일반적으로는 풀 수 없는 문제(결정 불가능 문제)예요. 그런데 Tree Calculus에서는 프로그램 자체가 트리 데이터이기 때문에, 프로그램이 다른 프로그램의 구조를 직접 탐색하고 분석할 수 있어요. 이걸 내성(introspection)이라고 하는데, 이게 가능해지면 프로그램 동치성 검사나 자동 최적화 같은 작업이 훨씬 자연스러워져요.

두 번째는 단순함이에요. 람다 대수에는 변수, 추상화(abstraction), 적용(application)이라는 세 가지 구성 요소가 있고, 변수의 바인딩과 스코프를 관리하는 게 꽤 복잡해요. 알파 변환이니 캡처 회피 치환이니 하는 개념들이 따라오죠. Tree Calculus에는 변수가 아예 없어요. 모든 게 트리 노드의 조합이니까, 변수 이름 충돌이나 스코프 문제가 원천적으로 사라지는 거예요. 이건 구현 관점에서도 상당히 매력적인 특성이에요.

업계 맥락: 대안적 계산 모델의 흐름

사실 람다 대수의 대안을 찾으려는 시도는 이번이 처음이 아니에요. 1920년대에 모세 쇤핑클(Moses Schönfinkel)과 해스켈 커리(Haskell Curry)가 만든 조합자 논리(Combinatory Logic)가 대표적이에요. S와 K라는 두 개의 기본 조합자만으로 모든 계산을 표현할 수 있다는 체계인데요, 이것도 변수가 없다는 점에서 Tree Calculus와 비슷한 철학을 공유해요. 실제로 Haskell의 초기 구현체인 Miranda는 내부적으로 SK 조합자로 컴파일하는 방식을 썼어요.

또 다른 흐름으로는 인터랙션 넷(Interaction Net)이 있어요. 이건 그래프 기반의 계산 모델인데, 최근에 HVM(Higher-order Virtual Machine)이라는 프로젝트가 이 모델을 활용해서 자동 병렬화를 달성한 것으로 주목받았죠. Tree Calculus도 트리 구조의 특성상 병렬 리덕션에 유리할 수 있다는 점에서, 이런 흐름과 맞닿아 있어요.

다만 현실적으로 보면, 람다 대수 기반의 생태계는 너무 거대해요. Haskell, ML 계열 언어들, 타입 이론, 증명 보조기(Coq, Lean 등)까지 모두 람다 대수 위에 구축되어 있거든요. Tree Calculus가 이런 거대한 생태계를 대체하려면 엄청난 시간과 노력이 필요할 거예요. 현재로서는 기존 체계를 보완하거나 특정 영역(프로그램 분석, 메타프로그래밍 등)에서 강점을 발휘하는 방향이 더 현실적으로 보여요.

한국 개발자에게 주는 시사점

솔직히 말하면, Tree Calculus가 당장 여러분의 실무 코드에 영향을 줄 가능성은 낮아요. 이건 아직 연구 단계의 이론적 제안이니까요. 하지만 몇 가지 측면에서 관심을 가질 가치가 있어요.

만약 프로그래밍 언어 이론이나 컴파일러에 관심이 있다면, Tree Calculus는 정말 흥미로운 공부 소재예요. 변수 없이 계산을 표현한다는 개념 자체가 "프로그래밍이란 무엇인가"에 대한 사고를 넓혀주거든요. 또 프로그램 검증이나 정적 분석 쪽에서 일하는 분이라면, 내성 가능한 계산 모델이라는 아이디어가 새로운 영감을 줄 수도 있어요.

그리고 이런 기초 이론의 변화가 실무에 도달하기까지는 보통 10~20년이 걸려요. 하지만 도달하면 패러다임 자체가 바뀌는 경우가 많죠. 람다 대수가 1930년대에 나왔지만 함수형 프로그래밍이 주류에 합류한 건 2010년대 이후잖아요. 지금 Tree Calculus의 아이디어를 이해해두면, 나중에 이 위에 만들어진 도구가 등장했을 때 빠르게 적응할 수 있을 거예요.