8.27 :: Hkt 구현
26일에 수면 패턴이 완전히 깨져서 되돌릴 겸 새벽에 HKT(Higher Kinded Types) 지원 관련 구현을 했다. 사실 HKT를 잘 구현하기 위해서는 기존 타입 시스템의 상당 부분을 갈아엎을 필요가 있어서, type checker / declarer 코드를 전체적으로 건드려야 했다.
처음에는 Haskell같은 언어에서 kind를 * -> * 처럼만 표기하는 걸 보고 각 타입 부분에도 제약 조건 명시가 필요할 수도 있지 않을까 싶어서 사진처럼 구현하려고 했다.
근데 확신이 들지가 않아서 상황을 가정하고 코드를 좀 써 봤는데, 만약 HKT에 다른 제네릭같은 가변적인 타입을 전달해야 할 경우 해당 제네릭에 제약 조건을 걸면 타입 오류를 충분히 낼 수 있다는 결론을 얻었다. 물론 타입 레벨에서 flatMap같은 동작을 수행하는 타입을 정의하려면 제약 조건 명시가 필요하고, 익명 형태로 전달 가능한 HKT (<T, U> -> T | U) 같은게 필요하겠지만 그렇게 했을 때 얻는 디자인적 이득이 거의 없을 것 같아서 보류했다.
이렇게 가끔 직관적으로 근거가 떠오르지 않을 때는 확실히 그냥 직접 적어보는 것이 낫다.
첫 번째 목표는 여러 개의 제네릭을 가진 타입 생성자에 부분적으로 타입을 전달할 수 있도록 일종의 currying을 지원하는 것이었다.
런타임 레벨의 currying과는 다르게 부분 적용을 한 상태에서 타입으로 사용한다면 속성같은 값의 타입을 추론해와야 하므로 구체 타입으로 (어느정도) 결정짓는 일을 그때그때 수행해야 했다.
이 부분까지는 잠을 못 잔 상태 치고는 빠르게 구현했던 것 같다. 중간중간에 특수 문자 토큰화 관련으로 lexer가 몇 번 버그를 낸 게 오히려 시간을 더 많이 잡아먹기도 했다.
다음 목표는 :: kind 표기를 통해 HKT임이 명시된 제네릭이 타입 인자를 받아 구체화되도록 만드는 것이었다.
위 같은 상황이라면 T는 A<B> 가 쓰이는 시점에 B<U> 로 취급되어서 obj | str 를 산출해야 한다. 그런데 이를 구현할 때는 시간이 좀 더 걸렸는데,
원래 type A<T> = B<T> 같이 타입 생성자인 타입이 제네릭(T) 이나 제네릭을 포함한 계산할 수 없는 타입을 포함할 경우 (예: B<C<T>>, B<T | int>) 평가를 잠시 보류하고 모두 추론 가능한 환경이 되었을 때 평가하거나 일부만 평가하도록 (위의 currying 처럼) 했다.
문제는 type A<T:: * -> *> = T<obj> 처럼 대상 타입 생성자가 제네릭일 경우 LazyApplicationType 으로 취급해서 처리하기가 조금 난감했다. 아마 평가 부분보다 선언 부분에서 일반화가 힘들다는 걸 느꼈던 것 같은데 기억이 잘 안 난다.
그래서 선언 시에는 construction type (T<obj>) 에 관한 충분한 정보가 없으므로 이를 any 로 놓고, 실제로 T 에 타입이 전달되었을 때 바꿔치기하도록 했다. 이 과정에서 코드가 지칭하는 대상이 매우 많이 바뀌고, 컴파일러 구조 특성상 추론을 위해 비슷한 함수가 순환적으로 호출되는 경우가 많아서 헷갈리지 않으려고 주석을 매우 많이 작성해야 했다. 어떨 때는 제네릭 같은 모호한 타입이 등장했을 때 각각 어떤 동작을 취하게 해야 할 지 감이 안 오기도 했는데, 이 부분은 테스트를 통해 고쳐야 할 듯 하다.
원래 이런 구현은 TDD로 하는게 구현 과정도 더 쉽고 버그를 잡기도 쉽다는 건 알지만, 한창 머리 속 흐름을 따라 구현하는 도중에 테스트를 작성하려고 그 흐름이 깨지면 당시 사고를 떠올리기 힘들 것 같아서 가능한 만큼은 그냥 구현해 뒀다.
결과적으로는 잘 된다는 걸 확인했으니 테스트 작성을 좀 하면서 일반화가 덜 된 부분을 고치고 버그를 잡을 생각이다.