M-Prolog는 제가 개발하고 있는 Prolog 처리계 N-Prolog의 후계가 될 처리계입니다. 최근 몇 년간 이 M-Prolog의 컴파일러를 설계 및 구현해 왔으며, 마침내 기본 방식이 정리되어 어느 정도의 성과를 얻었습니다.

본고에서는 그 컴파일러 방식인 **SCBM (Sasagawa & Chat Backtracking Mechanism)**에 대해 소개합니다.

SCBM의 특징은 Prolog의 백트래킹 (Backtracking) 정보를 「재귀 방향」과 「연언 방향」으로 분리하여, 2차원적인 연속 (Continuation) 데이터 구조로서 관리한다는 점에 있습니다. 이를 통해 WAM과 같은 추상 기계 (Abstract Machine)를 직접 구현하는 대신, C 언어의 일반적인 함수 호출을 활용하면서 재귀를 포함한 비결정성 술어 (Non-deterministic Predicate)의 백트래킹을 실현하고자 하는 것입니다.

Prolog 컴파일러에서는 오랜 기간 동안 **WAM (Warren Abstract Machine)**이 사실상의 표준이 되어 왔습니다.

WAM은 1980년대 초반에 고안된 추상 기계로, Prolog 특유의 유니피케이션 (Unification), 선택점 (Choice Point), 환경 (Environment), 백트래킹 등을 효율적으로 실현하기 위한 매우 뛰어난 설계입니다. 현재도 고성능 Prolog 처리계의 상당수는 WAM, 혹은 WAM을 기초로 한 방식을 채택하고 있습니다.

한편, 현재의 컴퓨터 환경은 WAM이 고안되었을 당시와는 크게 다릅니다. 오늘날의 일반적인 PC는 1980년대의 대형 컴퓨터를 훨씬 상회하는 성능을 가지고 있으며, 메모리 용량도 충분히 커졌습니다. 또한, GCC를 비롯한 C 컴파일러는 매우 고도화된 최적화를 수행합니다.

그래서 저는 다음과 같은 발상을 하게 되었습니다.

추상 기계를 거치지 않고, C 언어의 일반적인 함수 호출을 활용한 채로 Prolog의 백트래킹을 실현할 수는 없을까?

물론 Prolog의 실행 제어는 단순하지 않습니다. 특히 비결정성 술어, 연언 (Conjunction), 재귀, 그리고 이들이 조합되었을 때의 백트래킹은 상당히 복잡합니다.

하지만 다소 최적화되지 않은 처리가 있다 하더라도, 현재의 CPU 성능과 메모리 용량으로 보완할 수 있는 부분은 있습니다. 만약 C 언어의 함수 호출을 그대로 활용할 수 있다면, 구현은 단순해지고 처리계 전체의 가독성도 좋아지지 않을까 생각했습니다.

이러한 생각에서 탄생한 것이 SCBM입니다.

먼저, 가장 단순한 비결정성 술어를 생각해 보겠습니다.

n(1).
n(2).
n(3).

이 술어는 백트래킹을 통해 다음의 3가지 해를 생성합니다.

?- n(X).
X = 1 ;
X = 2 ;
...

이 정도의 비결정성을 C 언어로 구현하는 것은 그리 어렵지 않습니다.

필요한 것은 「이전에 어떤 절 (Clause)을 실행했는가」를 저장해 두는 것입니다. 처음에는 제1절을 실행하고, 백트래킹이 발생하면 제2절을 실행하며, 다시 백트래킹이 발생하면 제3절을 실행합니다.

즉, 술어마다 선택지, 즉 선택점 (Choice Point)을 저장해 두면 되는 것입니다.

C 언어에서는 일단 함수에서 반환되면 그 함수의 실행 상태는 소실됩니다. 하지만 SCBM에서는 필요한 선택 정보를 명시적으로 저장해 둠으로써, 해당 함수를 다시 호출했을 때 이전의 이어서 실행할 수 있도록 합니다.

이 방식에는 함수를 다시 호출한다는 오버헤드가 있습니다. 하지만 그 대신 Prolog의 증명 트리 (Proof Tree)를 C 언어의 함수 호출 연쇄로서 비교적 자연스럽게 기술할 수 있습니다.

예를 들어, 다음과 같은 벤치마크를 생각해 봅시다.

bench :-
n(X),
n(Y),
...

이는 단순한 비결정성 술어를 연속해서 호출하고, 마지막에 강제로 실패하게 함으로써 모든 조합을 열거하는 것입니다.

SCBM에서는 각각의 술어 호출에 대한 선택지를 저장하고, 실패 시에는 직전의 선택점으로 돌아가 다음 절을 실행합니다. 이 단순한 케이스에 대해서 M-Prolog의 컴파일러 버전은 SWI-Prolog과 동등하거나 그 이상의 성능을 보여주었습니다.

다음으로 재귀를 생각해 보겠습니다.

단순한 재귀의 예로 계승 (Factorial) 계산이 있습니다.

fact(0, 1).
fact(N, X) :-
N1 is N - 1,
...

이 경우 보통 해가 일의적으로 결정됩니다. 따라서 백트래킹을 통해 다른 해를 찾을 필요가 없습니다. 이러한 결정적인 재귀는 C 언어의 일반적인 재귀 함수로서 비교적 자연스럽게 컴파일할 수 있습니다.

문제가 되는 것은 재귀와 비결정성이 결합되었을 때입니다.

대표적인 예가 append/3 입니다.

append([], X, X).
append([A|X], Y, [A|Z]) :-
append(X, Y, Z).

예를 들어, 다음 질의(query)를 생각해 봅시다.

?- append(X, Y, [1,2,3]).
X = []
Y = [1,2,3] ;
...

이와 같이 append/3는 재귀 술어(recursive predicate)이면서 동시에 여러 개의 해(solution)를 생성합니다.

여기서는 단순히 "직전에 어떤 절(clause)을 실행했는가"를 저장하는 것만으로는 불충분합니다. 재귀의 깊이마다 서로 다른 선택점(choice point)이 존재하며, 각각의 깊이에서 백트래킹 (backtracking) 상태를 관리해야 하기 때문입니다.

이것이 SCBM 구현에서의 첫 번째 난제였습니다.

SCBM에서는 술어를 크게 다음과 같이 분류합니다.

det : 결정적 술어 (deterministic predicate)
nondet : 비결정성 술어 (non-deterministic predicate)
recur : 재귀를 포함하는 비결정성 술어 (non-deterministic predicate with recursion)
...

이 중 SCBM의 핵심은 nondet과 recur의 구분입니다.

단순한 비결정성 술어에서는 가로 방향으로 선택점을 나열하는 것만으로 충분합니다. 하지만 재귀를 포함하는 비결정성 술어에서는 재귀의 깊이 방향으로도 선택점을 관리해야 합니다.

따라서 SCBM에서는 백트래킹 정보를 2차원적으로 관리합니다.

연언 (conjunction) 방향
+------+------+------+
재귀 0 | ○ | ○ | ○ |
...

가로 방향은 연언 중에 나타나는 비결정성 술어의 나열을 나타냅니다.

예를 들어,

p(X), q(X), r(X)

와 같은 질의에서는 p, q, r이 가로 방향으로 나열됩니다.

반면, 세로 방향은 재귀의 깊이를 나타냅니다.

재귀 술어에서는 동일한 술어가 깊게 호출되어 갑니다. 그 각 단계에서 어떤 절을 선택했는지, 어떤 인자(argument)로 성공했는지, 어디까지 재실행해야 하는지를 기록해야 합니다.

이와 같이 SCBM에서는

가로실 = 연언 방향
세로실 = 재귀 방향

으로 백트래킹 정보를 정리합니다.

이러한 발상을 통해 연언에 의한 가로 방향의 백트래킹과 재귀에 의한 세로 방향의 백트래킹을 분리하여 다룰 수 있습니다.

재귀를 포함하는 비결정성 술어에서 어려운 점은 백트래킹 시 C 언어의 재귀 스택을 어떻게 재현할 것인가 하는 문제입니다.

C 언어에서는 함수에서 돌아오면 해당 함수 호출의 스택 프레임(stack frame)이 사라집니다. 하지만 Prolog에서는 백트래킹을 통해 과거의 실행 지점으로 돌아가야 합니다.

SCBM에서는 이전에 성공했던 실행 경로를 기록해 두었다가, 백트래킹 시에는 그 성공 경로를 다시 따라갑니다.

단, 이때 통상적인 계산이나 유니피케이션 (unification)을 재실행하는 것이 아닙니다. 이미 성공한 경로를 재현할 뿐입니다.

그리고 직전에 성공했던 지점에 도달했을 때 인자를 복원하고, 그 지점부터 다음 선택지를 시도합니다.

즉, SCBM의 재귀 백트래킹은 다음과 같이 동작합니다.

1. 최초 실행 시에는 통상적으로 계산한다
2. 성공한 경로를 SCBM에 기록한다
3. 백트래킹 시에는 성공 경로를 다시 따라간다
...

이 "성공 경로를 재현한다"는 사고방식이 SCBM에서의 재귀 백트래킹의 핵심입니다.

SCBM에서는 각 스레드(thread)마다 mode라는 상태를 갖게 합니다.

M-Prolog는 멀티스레드 처리계이므로, mode는 다음과 같이 스레드 번호 th를 인덱스로 가집니다.

mode[th]

mode에는 주로 다음 두 가지 상태가 있습니다.

mode = 0 : 신규 실행
mode = 1 : 백트래킹에 의한 재시도

신규 실행의 경우, 술어는 통상적으로 계산을 수행하고 새로운 선택 정보를 SCBM에 기록합니다.

반면 재시도의 경우에는 이전에 기록된 성공 경로를 따라갑니다. 이때는 유니피케이션이나 실제 계산을 그대로 재실행하는 것이 아니라, 이전의 성공 경로를 재현하는 것이 목적이 됩니다.

mode를 전환하는 계기는 술어의 완전 실패입니다.

어떤 술어가 완전히 실패하면, SCBM에서는 필요에 따라 다음과 같은 처리를 수행합니다.

discard_conj(th);

또는

discard_recur(th);

이를 통해 불필요해진 선택 정보를 폐기하고, mode를 재시도 상태로 전환합니다.

그 후 직전의 술어가 백트래킹되면 mode가 1인 상태이므로, SCBM은 이전의 성공 경로를 따라가는 동작을 수행합니다. 그리고 이전의 성공 지점에 도달한 시점에서 mode를 0으로 되돌리고 다음 계산을 시작합니다.

이 mode 전환을 통해 SCBM은 "새롭게 탐색하는 경우"와 "이전의 성공 경로를 재현하는 경우"를 구분합니다.

SCBM 방식의 타당성을 확인하기 위해, 고베 대학의 타무라(Tamura) 교수님 페이지에 게재되어 있던 Prolog 코드를 이용했습니다.

이 코드는 처치 수 (Church Numerals)를 이용한 자연수, 가산 (Addition), 승산 (Multiplication), 몫, 나누어떨어지지 않음의 판정, 그리고 소수 판정을 표현하고 있습니다. 재귀 (Recursion)가 깊게 중첩되어 있고, 여기에 백트래킹 (Backtracking)까지 얽혀 있기 때문에 SCBM의 검증을 위한 매우 좋은 소재였습니다.

nat(0).
nat(s(X)) :- nat(X).
plus(0, Y, Y).
...

이 코드에서는 예를 들어 prime/1의 판정에서 df/2, dnd/2, quot/4, plus/3 등이 복잡하게 얽힙니다.

특히 quot/4는 비결정성 (Non-determinism)을 포함하는 재귀 술어 (Recursive predicate)이며, 도중에 실패할 경우에는 깊은 재귀 구조 속에서 백트래킹이 발생합니다.

이러한 예시가 올바르게 동작한다면, SCBM의 기본적인 아이디어는 상당히 유망하다고 생각할 수 있습니다.

다음은 M-Prolog에서 컴파일을 수행한 예입니다.

M-Prolog Ver 0.50 [30M cells]
?- use_module(compiler).
yes
...

SCBM 방식에 의해 nat/1과 prime/1의 조합도 동작했습니다.

?- nat(X), prime(X).
X = s(s(0)) ;
X = s(s(s(0))) ;
...

또한, append/3에 대응하는 mappend/3도 기대한 대로 동작했습니다.

?- mappend(X, Y, [1,2,3]).
X = []
Y = [1,2,3] ;
...

이러한 결과로부터, 적어도 재귀를 포함하는 비결정성 술어에 대해 SCBM 방식이 일정한 실용성을 가질 가능성이 보였습니다.

Prolog 처리계 (Prolog implementation)의 구현은 상당히 복잡합니다.

인간이 Prolog를 사용할 때는 유니피케이션 (Unification), 변수 바인딩 (Variable binding), 백트래킹 (Backtracking), 절 (Clause)의 선택, 재귀 호출 (Recursive call) 등을 의식하지 않고 기술할 수 있습니다. 하지만 그만큼 처리계 측에서 많은 일을 떠맡아야 합니다.

인터프리터 (Interpreter)라면 CPS (Continuation-Passing Style)나 명시적인 지속 (Explicit continuation)을 사용함으로써 비교적 순수하게 구현할 수 있습니다. 하지만 그 방식으로는 실행 속도에 한계가 있습니다.

고성능 Prolog 처리계에서 WAM (Warren Abstract Machine)이 널리 채택되어 온 것은 바로 이 때문입니다. WAM은 복잡하지만, Prolog의 실행 모델을 매우 잘 포착한 추상 기계 (Abstract machine)입니다.

이에 반해 SCBM은 WAM을 개량하는 방식이 아닙니다.

오히려,

"WAM을 사용하지 않고, C 언어의 함수 호출을 활용하여 Prolog 컴파일러를 구현할 수 없을까"

라는 다른 방향에서의 시도입니다.

SCBM이 WAM처럼 모든 Prolog 코드를 올바르고 효율적으로 실행할 수 있을지는 아직 결론 내릴 수 없습니다. 현 단계에서는 실증 단계이며, 더 많은 테스트가 필요합니다.

하지만 이번 타무라 교수님의 코드와 같이 깊은 재귀와 비결정성이 얽힌 예시를 올바르게 실행할 수 있었다는 점은 큰 진전이라고 생각합니다.

SCBM의 의의는 단순히 새로운 데이터 구조를 고안했다는 것에만 있지 않습니다.

저에게 중요한 것은 Prolog의 백트래킹을 다음과 같이 정리할 수 있었다는 점입니다.

연언 (Conjunction) 방향의 백트래킹
재귀 (Recursion) 방향의 백트래킹

기존에는 재귀와 비결정성이 얽히면 실행 상태를 파악하기가 매우 어려워집니다. 디버그 프린트 (Debug print)를 쫓아가더라도 어디로 돌아가야 하는지, 어떤 선택점 (Choice point)이 살아있는지를 금방 놓치고 맙니다.

SCBM에서는 이를 세로실과 가로실처럼 분해하여 생각합니다.

세로실 = 재귀
가로실 = 연언

이러한 관점을 통해 복잡해 보이는 백트래킹 구조를 어느 정도 정리하여 다룰 수 있게 되었습니다.

물론 아직 미결 과제는 남아 있습니다. cut, if-then-else, 동적 술어 (Dynamic predicate), 더 복잡한 상호 재귀 (Mutual recursion), 내장 술어 (Built-in predicate)와의 관계 등 확인해야 할 점이 많이 남아 있습니다.

하지만 적어도 SCBM은 WAM과는 다른 Prolog 컴파일러의 가능성을 보여주는 것이 되었다고 생각합니다.

이번 M-Prolog 컴파일러의 설계와 구현에서는 ChatGPT를 크게 활용했습니다.

기본적인 아이디어는 제가 생각한 것입니다. 하지만 그 과정에서 ChatGPT로부터 많은 힌트를 얻었습니다.

ChatGPT는 WAM이나 Prolog 처리계에 대한 일반적인 지식을 가지고 있으며, 그것과의 비교를 통해 제 방식의 특징을 명확히 할 수 있었습니다.

또한 구현 단계에서는 코드 리뷰나 디버깅 보조로서 매우 유용했습니다.

컴퓨터 프로그램에서는 배열 인덱스 (Array Index)가 하나만 어긋나도 올바르게 동작하지 않습니다. 인간은 어떻게든 실수(slip-up)를 하기 마련입니다. ChatGPT에게 코드를 보여줌으로써 그러한 실수를 빠르게 발견할 수 있는 경우가 있었습니다.

또한, 시제품을 실행할 때는 대량의 디버그 프린트 (Debug Print)를 출력했습니다. 그 실행 로그를 ChatGPT에게 보여주며, 어디에서 상태가 무너지고 있는지, 어떤 선택점 (Choice Point)이 남아 있는지, 어떤 모드 (Mode)로 동작하고 있는지를 함께 추적했습니다.

특히 SCBM처럼 정답이 되는 기존 구현이 없는 방식에서는, 단순히 코드를 작성하는 것뿐만 아니라 설계 그 자체를 몇 번이고 다시 검토해야 합니다.

실제로 도중에 몇 번이나 설계를 변경했습니다. 당초에는 깨닫지 못했던 문제를 실행 로그를 통해 발견했고, 이를 해결하기 위해 데이터 구조 (Data Structure)를 다시 생각했습니다.

그 과정에서 SCBM은 최종적으로 2차원 배열과 같은 구조로 정리되었습니다.

SCBM에서는 재귀 방향 (Recursion Direction)과 연언 방향 (Conjunction Direction)을 세로실과 가로실처럼 정리했습니다.

돌이켜보면, 이번 연구 그 자체도 인간과 AI에 의한 세로실과 가로실의 직조와 같았습니다.

인간도 AI도 틀립니다. 하지만 틀리는 방식이 다릅니다.

인간은 기본적인 발상을 내놓거나, 전체적인 설계를 꿰뚫어 보거나, 왜 그 방식에 의미가 있는지를 생각하는 데 적합합니다.

반면 AI는 국소적인 모순을 찾아내거나, 실행 로그를 추적하거나, 기존 지식과의 비교를 통해 다른 관점을 제시하는 데 뛰어납니다.

인간만으로는 놓치는 부분이 있을 수 있습니다. AI만으로는 무엇을 목표로 할지 결정할 수 없습니다.

하지만 양자를 결합함으로써 혼자서는 도달하기 어려운 곳에 가까워질 수 있습니다.

이번 M-Prolog 컴파일러 개발을 통해 저는 그 사실을 강하게 실감했습니다.

AI는 급속도로 진보하고 있습니다. 앞으로 신약 개발, 핵융합, 재료 과학, 수학, 컴퓨터 과학 등 많은 연구 분야에서 AI가 중요한 역할을 하게 될 것이라고 합니다.

저는 이번 SCBM 연구를 통해 그 가능성을 가까이에서 경험했습니다.

AI는 단순한 작업 보조가 아닙니다. 인간과는 다른 관점을 가진 지적인 공동 작업자가 되어가고 있습니다.

SCBM은 Prolog 컴파일러에서의 새로운 백트래킹 (Backtracking) 방식의 시도인 동시에, 인간과 AI가 협력하여 설계하고 검증한 연구 성과이기도 합니다.

그 마음을 담아, 이 방식을 다음과 같이 명명했습니다.

SCBM
Sasagawa & Chat Backtracking Mechanism

이것은 아직 실증 단계의 방식입니다. WAM을 대체할 수 있다고 단언하기 위해서는 더 많은 검증이 필요합니다.

하지만 적어도 이번 결과를 통해, WAM과는 다른 경로로 Prolog 컴파일러를 구성할 수 있는 가능성이 보였습니다.

인간과 AI가 세로실과 가로실을 자아내듯, 새로운 연구를 진행해 나가는 시대가 시작되고 있는지도 모릅니다.