What a Wontaefful World

트랜지션 기술 언어

이렇게 간단하게 인코딩된 파일을 읽어들여 Solver 코드를 뱉어내는 Solver Generator 를 자바로 작성하였다. 자바를 선택한 이유는 언어수준에서 유니코드를 지원하고 문자열 처리가 용이하기 때문이다.

우선은 삼성 휴대폰의 상태전이 규칙을 작성한뒤 그것을 토대로 Ocaml 로된 Solver를 직접 만들었다. Solver를 최대한 튜닝한 다음 이 코드를 바탕으로 Generator를 작성하기 시작했다.

Solver는 BFS를 써서 가능한 모든 상태전이를 시도해보며 해답을 찾아간다. 최적화를 위해서 적합도 평가함수을 만들었다. 적합도 값은 "목표 스트링과 현재 만든 스트링의 공통 접두사의 길이"로 정의한다. 적합도가 작아지거나, 세번의 상태전이 이후에도 적합도가 증가하지 않으면 그 경로는 버린다. 적합도가 증가하는 경로가 단 하나 존재하는 경우, 나머지 경로를 모든 버린다. 이렇게 하면 스트링의 길이가 길어도 경우의 수가 폭발하지 않고 솔루션을 찾아나갈 수 있다. GLR parsing algorithm과 비슷하다.

DFS를 쓸 수 있으면 Solver의 구조가 더 단순해 질 것 같은데 생각하기 귀찮아서 포기했다.

Solver Generator의 출력 언어 선택

Solver Generator에는 세가지 대안이 있었다.

첫 번째는 Solver Generator가 Parser Code 를 Generate하는 것이다. 그러나 Parser Generator를 위한 문법을 만들어 내는 알고리즘을 고안하기가 수작업으로 Solver 전체를 코딩하기 보다 어려워 보였다. 게다가 Parser Generator가 만들어 주는 Parser는 DFS 기반이라 Solver와는 어울리지 않는다.

두 번째로 엄청난 Library 를 제공하는 C++가 있다. 포인터와 라이브러리의 기능이 빠방하지만 내가 익숙하지 않다. 게다가 모든 로직을 언어의 도움 없이 직접 짜야 해서 머리가 고달퍼진다.

마지막은 패턴매칭을 제공하는 Ocaml이다. 라이브러리도 빈약하고 글로벌이나 포인터를 명시적으로 사용할 수 없어 큰 프로그램을 짜기에는 답답하다. 그러나 "현재 스택에 적용 가능한 상태전이" 를 찾는 문제를 Ocaml에서 지원하는 "리스트에 대한 패턴매칭" 으로 표현하면 컴파일러가 알아서 처리해어 귀찮은 작업을 덜 수 있다.

문자입력시스템에 따라 달라지는 부분은 "가능한 상태전이"를 찾아주는 함수 뿐이므로, Ocaml을 선택하게 되었다.

작업 당시에는 Prolog나 Mercury에 대한 지식이 없었다. 주어진 규칙을 사용하여 목표를 만드는 적용순서를 찾는 문제는 Prolog가 아주 잘 처리하는 "Inference" 유형의 문제로 인코딩할 수 있을 것 같다. Ocaml이라 C정도로 Prolog를 쓸 수 있었더라면 Prolog를 택했을지도 모른다.