조건문 지옥을 피하는 법: 1994년 포스(Forth)의 유한 상태 기계 설계가 지금도 유효한 이유

파서, 프로토콜 처리기, 입력 검증 루틴처럼 '정해지지 않은 순서로 들어오는 입력'에 반응해야 하는 코드는 절차적으로 짜기가 유독 까다롭다. 예를 들어 컴파일러는 부동소수점 숫자를 나타내는 문자열과, 비슷한 문자들이 비슷한 순서로 나열된 대수식을 구분해야 한다. 숫자 문자열은 길이가 고정돼 있지도 않고 기호의 등장 순서가 정해져 있지도 않으며, 사용자 편의를 위해 같은 값을 여러 형식으로 허용해야 하기까지 한다. 1994년 포스(Forth) 커뮤니티에서 발표된 이 노트는 이런 문제를 유한 상태 기계(FSM)로 다루는 구체적인 구현 기법을 단계적으로 보여 준다. 30년도 더 지난 글이지만, '분기문 남발을 상태 표(state table)로 대체한다'는 발상 자체는 지금의 코드에도 그대로 적용된다.

중첩 IF가 만드는 문제

글이 겨냥하는 적은 명확하다. 패턴 인식은 IF, ELSE, THEN을 충분히 많이 이어 붙이면 논리적으로 구현할 수 있다. 문제는 그렇게 나온 코드가 읽기 어렵고 디버깅과 수정이 힘들며, 아무리 들여쓰기를 예쁘게 해도 본질적으로 구조화되지 않는다는 점이다. 저자는 여기에 성능 문제까지 덧붙인다. 많은 프로세서가 분기 시 파이프라인을 비우기 때문에, 논리식 위주의 프로그램은 느려질 수 있다는 것이다. 이 결함이 실제로 얼마나 컸는지는, 이를 극복하려는 상업용 도구가 즐비했다는 사실이 방증한다. 논리식을 번역·단순화하는 Logic Gem, 상태 표를 BASIC·Modula-2·Pascal·C 등으로 옮겨 주는 Matrix Layout, 비슷한 변환을 수행하는 COMPEDITOR 같은 CASE 도구들이 1993년까지도 개발자용 소프트웨어 할인점에서 팔리고 있었다.

예제로 든 것은 키보드로 숫자를 입력받는 루틴이다. 불친절한 프로그램은 사용자가 숫자를 다 입력하고 나서야 소수점을 두 번 찍었다고 알려 주지만, 친절한 프로그램은 애초에 불법 문자를 인식하지도 화면에 표시하지도 않는다. 예제는 규모를 줄이기 위해 지수부가 없는 부호 있는 고정소수점 숫자만 다룬다. 숫자, 소수점, 맨 앞의 마이너스 부호는 허용하고 공백을 포함한 다른 ASCII 문자는 거부한다. 이때 절차적 접근의 핵심 단어 LEGAL?의 문제는, 합법성이 시점에 따라 달라지는 문자마다 '이력 세마포어(history semaphore)'가 하나씩 필요하다는 데 있다. 세마포어가 늘어나면 코드만 봐서는 논리가 맞는지조차 판단하기 어려워지고, 실제로 저자는 그 논리가 틀려 있었다고 지적한다.

상태 변수 하나로 이력을 대체한다

FSM 접근의 핵심은 여러 개의 참/거짓 이력 세마포어를 상태 변수 하나로 치환하는 것이다. 규칙은 상태 표에 담기고, 표의 각 칸은 '어떤 입력에 대해 어떤 동작을 하고 어느 상태로 전이하는가'를 명시한다. 저자는 이 표를 포스로 옮기는 세 가지 구현을 순서대로 발전시킨다. 첫 번째는 Eaker CASE 문이나 HS/FORTH의 CASE: ;CASE를 쓴 '무차별' 방식이다. 상태값 0·1·2를 갖는 변수를 두고 상태마다 단어를 하나씩 정의해 처리한다. 동작은 하지만, 각 단어가 입력 검사까지 떠안아 인수 분해가 부족하고 여전히 IF...ELSE...THEN 분기를 품고 있으며, 매번 상태 기계를 손으로 짜맞춰야 한다는 한계가 있다.

두 번째 구현이 이 글의 백미다. 상태 표를 행이 상태, 열이 입력 범주, 각 칸이 실행 토큰(주소)인 행렬로 바라보는 것이다. 입력 문자를 먼저 '열 번호'로 변환해 두면, 현재 상태(행)와 열이 유일한 칸 주소를 결정하고, 그 칸의 내용을 꺼내 실행하기만 하면 된다. 입력을 열 번호로 바꾸는 작업이 모든 검사를 문자당 한 번 실행되는 단어 하나로 묶어 주고, 어느 칸을 실행할지는 '판단'이 아니라 '계산'으로 결정되므로 시간을 잡아먹는 분기 명령을 피할 수 있다. 저자는 FSM:이라는 정의 단어를 만들어 컴파일 시점에 실행 주소 배열과 열 수를 함께 저장하고, 실행 시점에는 자식 단어가 열 번호와 상태에서 칸 주소를 계산해 해당 동작을 EXECUTE하게 한다. 다만 이 우아한 구현은 간접 스레드(indirect-threaded) 포스에서만 동작하며, ANS 표준용 대안은 부록에 따로 실려 있다.

세 번째 개선은 상태 전이를 동작 단어 속에 숨기지 않고 표처럼 겉으로 드러내는 것이다. >0, >1 같은 CONSTANT로 전이를 표현하면 각 FSM 정의가 상태 표를 그대로 옮겨 놓은 모양이 되어 읽기 쉬워진다. 흥미로운 세부 사항은 실행 코드에서 상태 변경을 동작보다 먼저 수행한다는 점이다. 어떤 칸의 동작이 ABORT와 오류 메시지일 때, 상태를 먼저 갱신해 두면 칸마다 별도의 오류 처리기를 쓰지 않고도 어디서 중단됐는지 알 수 있기 때문이다. 나아가 저자는 전역 변수 mystate가 FSM의 중첩이나 재귀를 막는다는 점을 지적하며, 상태 변수를 각 FSM의 자료 구조 안(폭 정보 옆)에 넣어 셀 하나를 더 쓰는 대신 상태를 사고로부터 보호한다. 동작이 스택에 값을 남기고 전이를 나중에 처리해야 하는 경우에는 리턴 스택을 임시 저장소로 활용해 충돌을 피한다.

숫자 대신 이름, 그리고 비결정성으로

전이를 숫자 리터럴이 아니라 CONSTANT로 구현하는 이유도 설득력이 있다. 상태에 번호 대신 이름을 붙일 수 있고, 이름이 번호보다 명확한 경우가 많기 때문이다. 저자는 포스의 외부 인터프리터 자체가 COMPILE과 INTERPRET이라는 두 상태를 가진 상태 기계라는 점을 예로 든다. 더 나아가 전이를 단어로 표현하면 하나의 동작 뒤에 여러 다음 상태로 분기하는 비결정적(nondeterministic) FSM으로 확장할 수 있다. 이름과 달리 여기에 무작위나 '추측' 같은 요소는 없으며, 여러 가능성을 여는 것은 현재 상태와 현재 입력 바깥에 있는 추가 정보라는 점을 저자는 분명히 한다.

실무적으로 이 글이 남기는 교훈은 언어를 가리지 않는다. 시점 의존적인 조건이 늘어날수록 불리언 플래그를 하나씩 추가하는 방식은 필연적으로 검증 불가능한 코드로 향하며, 이를 상태 변수 하나와 표로 바꾸면 로직이 데이터가 되어 검토·수정·확장이 쉬워진다. 다만 한계도 분명하다. 예제는 지수 표기가 없는 고정소수점 숫자라는 축소된 문제이고, 가장 우아한 행렬 구현은 특정 포스 구현에 의존하며, 표기법도 ASCII를 CHAR로, DDUP를 2DUP로 바꾸는 등 ANS 표준과 어긋나는 부분이 있어 그대로 옮겨 쓸 수는 없다. 그럼에도 '분기 트리를 상태 표로 대체하고, 표를 코드가 아니라 자료로 다룬다'는 발상은 오늘날 프로토콜 파서나 UI 상태 관리에서 흔히 쓰는 상태 기계 패턴의 원형으로서 여전히 읽을 가치가 있다.