Representation 다형성

Represent 뜻 - 사전을 찾아보면 대표자, 대리인, 특정 방식으로 묘사, 표현등으로 나옵니다. 저는 이 걸 조금 풀어서 받아들이고 있습니다. 한 가지를 가리키는 여러 말이나, 표현, 명칭등이 있는데, 그 중 하나를 골랐을 때 represent란 말을 쓴다고 이해하고 있습니다. 변수를 표현하는 여러 방식 중, 혹은 변수를 구분하는(나누는) 여러 방식 중, 하나를 골랐을 때 쓰는 말입니다.

2 + 2, 1 * 4, 2 * 2, 5 - 1… 모두 4를 표현Represent하는 Representation입니다.

GHC 공식 문서 - 6.4.13. Representation polymorphism

하스켈에선 bottom이 될 수 있냐, 없냐로 lifted type, unlifted type으로 나누고, 힙에 올리고 포인터로 가리키는 간접 모양이냐, 바로 데이터(primitive value)냐에 따라 boxed, unboxed로 구분합니다. 참고 - Unboxed, Boxed, Unlifted, Lifted

어떤 타입이든 간에 런타임에는 boxed냐 unboxed냐, lifted냐 unlifted냐로 구분지을 수 있습니다. 이들 구분에 따라 메모리를 차지하는 모양, 접근하는 절차가 달라지는데, 이렇게 구분 짓는 걸 Representation에 따른 구분이라 합니다.

-- GHC.Exts에 아래와 같이 정의되어 있다.
TYPE :: RuntimeRep -> Type   -- GHC에 프리미티브로 구현되어 있다.

data Levity = Lifted    -- `Int`같은 평상시에 자주 쓰던 타입
            | Unlifted  -- `Array#` 포인터를 통하지 않고, 바로 데이터에 접근하는 타입

data RuntimeRep = BoxedRep Levity  -- GC가 관리하는 포인터로 represent되는 모든 타입
                | IntRep           -- `Int#`을 위한 represent
                | TupleRep [RuntimeRep]  -- unboxed tuples 
                | SumRep [RuntimeRep]    -- unboxed sums
                | ...

type LiftedRep = BoxedRep Lifted

type Type = TYPE LiftedRep
  -- Lifted 되어 있으니 Bottom값을 가질 수 있고,
  -- Boxed되어 있으니, 힙에 넣고 포인터를 통해 접근한다.
  -- 하스켈 입문 때부터 가장 많이 써왔던 보통의 타입으로 힙을 가리키는 포인터입니다.

Int# 는 TYPE IntRep
Bool 은 TYPE LiftedRep
-> 는 TYPE r1 -> TYPE r2 -> TYPE LiftedRep
...

조금 복잡하긴 한데, 하스켈의 타입들은 모두 위에서 얘기한 속성representation으로 구분지을 수 있습니다.

※ GHC공식 문서의 아래 문장을 잘못 해석했는데, Ailrun님이 바로 잡아 주셨습니다.
“We can thus say that -> has type TYPE r1 -> TYPE r2 -> TYPE LiftedRep. The result is always lifted because all functions are lifted in GHC.”
함수는 예외를 받으면 언제든 끝날 수 있어야 하니, GHC의 모든 함수의 결과는 항상 Lifted겠거니로 해석했는데, 그 뜻이 아닙니다. 함수의 결과값은 항상 Lifted일 필요는 없습니다. 함수의 결과값은 Unlifted로 지정할 수도 있습니다. 위 말은 ->의 결과 타입, 즉 모든 함수의 결과가 아니라, -> 함수의 결과 타입은 항상 Lifted란 얘기입니다.

함수는 람다 <thunk>를 가리키는 포인터입니다.

함수의 결과 값이 아니라, 즉 -> 함수의 결과값인 GHC의 모든 “함수 자체”는 항상 Lifted란 얘기입니다.

Levity 다형성

representation 다형성 중에 특별한 경우로 levity 다형성이 있습니다. 위 소스에서 보 듯 Lifted | Unlifted를 Levity라고 합니다. 어떤 구현이 Lifted일 때도 대응하고, Unlifted일 때도 대응하면 Levity 다형성을 갖고 있다고 말합니다.

example :: forall (l :: Levity) (a :: TYPE (BoxedRep l)). (Int -> a) -> a
example f = f 42

forall l, 즉 Lifted이든, Unlifted이든 상관없는 구현이란 뜻입니다.

※ 타입 다형성Polymorphic Type을 가진 함수를 떠올려 보면,
length :: forall a. [a] -> Int는 a가 무슨 타입이든 상관없이 대응할 수 있는 구현이란 뜻입니다. 참고 - forall - 아무거나 모든 것의 차이

UnliftedDatatypes 확장을 켜고, levity 다형성을 가진 데이터 타입을 선언할 수도 있습니다.

type PEither :: Type -> Type -> TYPE (BoxedRep l)
data PEither l r = PLeft l | PRight r

※ UnliftedDatatypes 확장: unlifted 또는 levity 다형성을 가진 result를 갖는 타입을 정의할 수 있습니다.

No representation-polymorphic 변수나 인자

GHC가 real world에서 돌아가게 컴파일할 필요가 없다면 모르지만, real world용으로 컴파일 할 때, representation_polymorphism이 까다로운 요소라 합니다.

bad :: forall (r1 :: RuntimeRep) (r2 :: RuntimeRep)
              (a :: TYPE r1) (b :: TYPE r2).
       (a -> b) -> a -> b
bad f x = f x

a와 b는 RuntimeRep에 폴리모픽한 변수들입니다. 어떤 Representation이 들어와도 문제 없는 구현이어야 합니다. 그냥 $ 함수를 general하게 표현한 것으로 보이지만, 이 걸 컴파일한다고 가정하면 문제가 있습니다. bad를 부를 때, 어떤 x를 넘기게 될텐데, x는 몇 bit 크기의 데이터가 들어 올까요? 아님 포인터가 들어 올까요? 어떤 종류의 레지스터(floating-point 또는 integral)를 준비해야 할까요? 그 걸 알아야 메모리를 준비할텐데, representation-polymorphic이라 뭐가 들어올지 알 수가 없습니다.

결론은, 현실적으론 변수는(혹은 인자는) representation-polymorphic 타입일 수 없습니다.

하지만, 다음은 가능합니다.

($) :: forall r (a :: Type) (b :: TYPE r).
       (a -> b) -> a -> b
f $ x = f x

a는 Type으로 고정이고, b만 representation-polymorphic합니다. ($)가 받는 첫 번째 인자는 함수를 가리키는 포인터, 두 번째 인자 a는 lifted representation이니 힙에 있는 값을 가리키는 포인터, 이렇게 두 개의 포인터만 들어옵니다. 그래서 문제가 없습니다.

Representation-polymorphic bottoms

undefined :: forall (r :: RuntimeRep) (a :: TYPE r).
             HasCallStack => a
error :: forall (r :: RuntimeRep) (a :: TYPE r).
         HasCallStack => String -> a

이들 함수들은 representation-polymorphic 변수를 바인딩하지 않습니다. 결과값이 representation-polymorphic입니다. 그래서 문제가 없습니다. 위 함수들이 반환하는 결과값인 bottom이 representation-polymorphic하니 어떤 함수에서든 이들을 사용할 수 있다는 얘기입니다. 이 걸 문서에서는 이렇게 얘기합니다.

“사용자는 이 함수들의 다형성을 이용해서, 어떤 함수가 unboxed 타입을 반환하는 걸 못하게 할 때 통상 사용한다.”

unboxed라고 찝어서 얘기했지만, 그렇다고 다른 타입은 반환할 수 있다는 얘기는 아닙니다. 어떤 타입도 반환할 수 없는 undefined와 error 함수를 이용해, unboxed를 반환하는 보통의 함수들의 실행을 끊을 때 쓴다는 얘기입니다.

Representation-polymorphic 타입 출력하기

-fprint-explicit-runtime-reps 옵션을 주고 GHCi를 실행하면, RuntimeRep과 Levity를 출력해 줍니다.

ghci> :t ($)
($) :: (a -> b) -> a -> b
ghci> :set -fprint-explicit-runtime-reps
ghci> :t ($)
($)
  :: forall (r :: GHC.Types.RuntimeRep) a (b :: TYPE r).
     (a -> b) -> a -> b

Generics를 보기 위해 살펴 봤는데, 문서에도 말하듯이, 다행히 일반 하스켈 사용자들은 Representation들을 굳이 따지며 쓰지 않아도 된다고 합니다. 다행입니다. 알아야 될 것도 많은데…