의미가 분명한 자료구조 vs 절차형 기계의 효율

언어의 구문적 분명성이야 기계어 등을 제외한 대부분의 현존 언어들이 대체로 갖추고 있지만, 의미상의 분명성이 얼마나 검증될 수 있는가 하는 문제는 아직까지는 각각의 언어들마다 적지 않은 차이가 있어 보입니다. 따라서 비슷해보이는 자료구조를 기술하는 방법 뿐만 아니라 그렇게 기술된 의미의 분명성 또한 각 언어마다 다르겠죠.

간혹 Gnu MP 라이브러리를 쓸 수 없는 특수한 상황에 처할 경우에 대비해서 (실제로 그런 경우가 있을지는 모르겠습니다만), 단순한 아류작 정도 되는 Reeseo's MP 라이브러리를 간단히 만들어봤었습니다. 의미 체계의 정형성을 포기할 생각이라면야, 설계도의 의미를 왜곡해가며 구현한다든가 아니면 아예 의미론 자체를 무시하고 설계해버리는 등 효율을 몇 배로 올릴 수 있는 여러가지 방법(혹은 꽁수)들을 쓸 수 있었겠죠. 하지만, 이 라이브러리를 딱히 효율이 절실한 중요한 일에 투입할 것도 아니고 어디까지나 비상용이자 거의 장난에 가까운지라, 그냥 밑바닥부터 하나 하나 정형적인 의미 체계를 유지하여 설계하고 그 설계도의 의미 그대로를 (전형적인 '가난한 C 프로그래머' 관점에서 보자면 단순 무식 지랄스럽게) 코드로 옮겨 구현하고자 노력했더랬습니다. C 언어의 언어적 특성 상 설계도의 의미를 모두 코드에 투영시키는 과정이 (특별히 이런 것에 유리한, 예를 들어 일부 함수형 언어들 등에 비해) 상당히 어렵고 고달픈 작업이었을 뿐더러 언어 자체가 그 과정의 옳바름을 충분히 검증해주지도 못했지만, 거의 오기로 한 번 시도해봤었죠. 게다가, 의미적 정형성을 유지하는 것이 적지 않게 고달팠음에도 불구하고 끝까지 포기하지 않았던 또 하나의 중요한 이유는, 바로 'C 언어는 오랜 세월동안 컴파일러가 잘 다음어져온 언어고, gcc 등의 현대적 컴파일러는 어차피 무척 효율적인 절차형 기계용 이진 코드를 만들어주니까 약간의 효율 손해는 큰 문제가 없으리라'는 편견(?)이 작용했다는 것입니다.

결과물은 잘 작동했습니다. 여기서 잘 작동했다는 말은 '오동작 없이 예정된 설계 대로만 동작했으며, 앞으로도 그러리라 믿어졌다'는 뜻입니다. 그런데, 한 가지 예상치 못한 일이 벌어졌습니다. 속된 말로, 효율이 정말 끝장으로 나쁘더라는 것이죠. '왜' 그렇게까지 극단적으로 효율이 떨어졌는지는 궁금하지 않았습니다. 이유야 처음부터 잘 알고 있었으니까요. 의외였던 것은 왜 '그렇게까지 극단적으로' 효율이 떨어졌는가였습니다. 그렇게 심할줄은 몰랐거든요. 팩토리얼 1000을 구하는데, P2-166 128M Win98SE 환경에서 dmc (Digital Mars C Compiler)로 컴파일된 프로그램이 약 8초~10초, P3-450 128M Linux 2.4.x 환경에서 gcc로 컴파일된 경우 약 5~7초, P3-750 384M WinXP-CygWin 환경에서 CygWin-gcc로 컴파일된 경우 약 3~5초가 걸리더군요. :cry:

그러면, 역시 폰 노이먼 절차형 기계 상에서는 결국 의미를 부여하고 검증하는 부하가 배보다 훨씬 큰 배꼽 역할을 할 수 밖에 없다는 이야기일까요? 꼭 그렇지만은 않을수도 있다는 것을 ghc (Glasgaw Haskell Compiler)로 컴파일된 간단한 factorial 프로그램을 통해 알 수 있습니다. 과연 gcc로 C 코드를 컴파일한 프로그램보다 ghc로 Haskell 코드를 컴파일한 프로그램이 반드시 느릴까요? 꼭 그렇지만도 않은 것 같거든요. 그만큼 ghc 컴파일러가 충분히 연구되고 잘 만들어진 컴파일러라는 뜻일 것이고 (아마도 함수형 선언들로부터 normalize 등을 통해 최적화된 절차형 이진 코드를 만드는 과정이 역시 엄청나게 잘 다듬어져 있는 듯합니다), 그만큼 제가 더 공부해야할 것들이 산처럼 많다는 뜻이겠죠. ^^;

물론, 제가 만든 RMP 라이브러리에서 '숫자', '수', '자리수', '연산'을 이야기하는 과정과 Haskell에서 Num, Integral 타입클래스와 Integer 타입을 이야기하는 과정에는 상당한 차이가 있긴 합니다. 예를 들어 RMP 라이브러리는 digit와 integer를 따로 말하며 integer에는 digit에 없는 cipher라는 개념이 있고 digit는 한 자리 integer와는 위상 자체가 다르게 되어있죠. 이 과정에서 기계와 C언어 자체가 불분명한 의미로 제공하는 각종 자료형들에는 거의 의존하지 않고 있습니다.

여기서 한 가지 상념이 떠오릅니다. 만일 폰 노이만 기계와는 달리 전혀 절차적이지 않고 상태 변화에 의존하지 않는 새로운 기계가 있어서, 절차적이지 않은 선언들을 특별한 절차화 기법 없이도 최적(?)으로 기계에 알려주고 결과를 평가할 수 있다면, 그래서 이 기계에 C 언어 컴파일러를 이식하려면 오히려 역사적으로 발전해온 모든 절차형 언어의 컴파일러 이론을 거의 버리고 거꾸로 절차적 대입과 참조의 명령 배열을 역으로 함수형 선언과 평가의 집합으로 바꾸는 기법과 그에 따른 비용이 필요하다면, 일반적으로 말하는 속도와 저장 공간의 효율이라는 것 역시 위와는 반대되는 상황도 벌어질 수 있지 않을까 하는 것이죠. 물론 이미 연구 중인 분야인 것은 알고 있습니다만, 이런 연구의 진행 상황이나 지금까지의 성과 등을 자세히 접하기가 그다지 쉽지는 않군요.

제가 연구하는 (정확히는, 하기 시작한) 분야도 이와 약간의 간접적 연관성이 있긴 하지만, 혹시 이 게시판에서 현재 활동하시는 분들 중에 상당히 직접적으로 이 분야를 깊게 연구하고 계신 분이 있는지 궁금합니다. 그런 분들의 이야기(어떤 것이든)를 들어보는 것도 재미있을 것 같구요.