Standalone

Development Note.

지난주 목요일(090424) Sparrow++ IL의 pretty printer를 만들던 중에 발견된 문제. Routine node의 type field를 출력하는 과정에서 out of memory 요류를 내면서 프로그램이 죽는 현상 발견. 어설프게 ocamldebug를 이용해서(그리고 감으로 찍기..) 파악한 결과 type node를 맵을 이용해서 unique id를 발급해서 사용하는 부분이 있는데, 이곳에 들어가는 type node가 순환적인 구조를 가지는 경우 프로그램이 죽게 된다는 것을 알게 됨.

Ocaml에서 cyclic data(mutable field를 이용하거나 reference를 이용해서 생성 될 수 있다)의 경우 라이브러리의 compare를 사용할 수 없다. compare는 structural equivalence를 비교하는데만 사용된다. 그러면 physical equivalence를 비교하는 compare 함수는 없는가? 그것을 이용해 맵을 만들고 그걸고 id를 발급해야 겠다 싶어서 궁리를 해보던 중, 이것도 안된다는 것을 알게 됨.

나와 같은 고민을 해보고 같은 결론에 도달하게 되었던 사람의 글이 ocaml maillist archive에 있더라. 그걸 옮겨 오면

> Is their a version of “compare” that is based on physical equality? If
> not, how can I define one? I tried:
>
> let compareq a b = if a == b then 0 else if a > b then 1 else (-1)
>
> But unfortunately, (>) is a structural comparison.
>
> I need to make a Map where the keys are distinguished by the physical
> instance.

It’s not possible.

One of the reason is that the GC might move your memory addresses around
and then break your Map constitency. You need to attribute an unique id
to each of your items and use it for comparison.
원문 주소 : http://alan.petitepomme.net/cwn/2005.11.29.html#5

결론은 Ocaml내에서는 불가능하다. physical equivalence를 체크하는 == 함수가 있긴 하지만 >, < 에 해당하는 연산이 없다. 그리고 이 연산이 없는 이유는 ocaml내에서 어떤 값은 GC에 의해 옮겨 다니게 되므로 물리적인 주소를 비교한다는 것은 비교 연산의 동작을 그때그때 다르게 만들어버린다. 따라서 불가능.

Physical compare는 불가능하지만 원래의 목적으로 돌아와 이에 대한 map을 만드는것은 가능하다. 위의 원문 링크를 따라가면 그 해결에 대한 내용도 있는데, 요약하면 맵에 들어갈 데이터 들에 대해 unique한 번호들을 부여해 놓고 이것을 비교하자는 것이다. 뭐, 말은 간단한데 사실 이 번호를 어떻게 부여하는가가 어려운 문제이다. 또 그에 대한 해법을 Jean-Christophe Filliatre라는 멋쟁이가 제안해 놓았더라. 데이터들에 대한 hash는 이미 라이브러리에서 제공하고 있고, 이것은 데이터 타입 모양이나 그 데이터가 순환구조인지 상관없이 잘 작동하고 끝나는것이 보장되는데 이 값을 unique number로 이용해서 맵을 사용하면 된다. 또 그러한 맵을 라이브러리로 만들어놓았더라.

생각해보면 당연히 이렇게 해결할 수 있는건가 싶기도 하다. 하지만 그 ‘당연한’걸 생각 해 내는 것과 못하는게 구루들과 나의 차이겠지. 별거 아닌 어려움에 끙끙 앓은것 같아서 부끄럽기도 하고, 뭔가 하나 배운거 같아서 기쁘기도 하다.