데이터 타입 제네릭 프로그래밍으로 클래스 요리하기

2016년 3월 3일 · 원문 · 한국어 번역(원문에서 변경됨)

Haskell Generics는 다소 오해받는 주제이지만, 아주 적은 노력으로 방대한 유니버스의 타입들에 걸쳐 재사용 가능하고 비교 가능한 인터페이스를 작성할 수 있게 해 주는 매우 강력한 기법입니다. 아마도 표현력 있는 타입 시스템이 우리에게 주는 이점을 보여 주는 예 중에서 제가 가장 좋아하는 예일 것입니다.

예제 코드의 소스는 여기에서 볼 수 있습니다.

Generics는 *데이터 타입 제네릭 프로그래밍(datatype-generic programming)*의 한 형태이며, 이름은 Java Generics와 다소 비슷하지만 완전히 다른 개념입니다. GHC의 Generics 구현은 Haskell의 모든 데이터 타입을 *곱의 합(sum of products)*의 조합으로 쓸 수 있다는 단순한 관찰에서 자연스럽게 도출됩니다.

**합 타입(sum type)**은 서로 다르지만 고정된 여러 타입 중 하나를 취할 수 있는 값을 담는 데 쓰이는 자료 구조입니다. 예를 들면 다음과 같습니다.

data Pastry
  = Turnover
  | Macaroon
  | Brownie
  | Cookie

**곱 타입(product type)**은 여러 타입으로 이루어진 고정된 순서 집합을 담는 데 쓰이는 자료 구조입니다. 필드 하나를 선택하는 것을 사영(projection)이라고 합니다.

data Person = Person
  { firstName       :: String
  , lastName        :: String
  , age             :: Int
  , height          :: Float
  , phoneNumber     :: String
  , flavor          :: String
  }

Haskell에서는 모든 데이터 타입을 곱의 합으로 표현할 수 있습니다.

data Expr
  = Add { l :: Expr, r :: Expr }
  | Mul { l :: Expr, r :: Expr }
  | Sub { l :: Expr, r :: Expr }
  | Div { l :: Expr, r :: Expr }
  | Number { val :: Int }

컴파일 과정에서 데이터 타입의 구조에 관한 정보는 대부분 버려지며, Haskell은 설계상 모든 타입 정보를 소거합니다. 타입 검사에 앞서 **정교화(elaboration)**라고 하는 단계에서 모든 레코드 선택자가 곱의 이름 붙은 필드를 추출하는 최상위 함수로 전개됩니다.

data Point a b = Point { x :: a, y :: b }

x :: Point a b -> a
x (Point a _) = a

y :: Point a b -> b
y (Point _ b) = b

곱에 관한 나머지 정보도 컴파일 후에는 대부분 버려지고, 곱은 그저 패턴 매칭 코드로 전개됩니다. 합 타입의 경우 남아 있는 유일한 정보는 합 타입의 각 생성자에 붙은 태그입니다. 예를 들어 Add에는 태그 1이, Mul에는 2가 할당되는 식입니다. case 문에서 런타임에 알 수 있는 유일한 정보는 우리가 어느 분기를 검사하고 있는지뿐입니다.

그렇다면 이 정보를 모두 버리지 않고 대신 프로그램에 노출하여, 데이터 타입의 “구조“를 내성(introspect)할 수 있는 제네릭 로직을 작성할 수 있게 한다면 어떨지 생각해 봅시다.

컴파일러 훅

GHC 6.10부터 타입 패밀리가 도입되었는데, 타입 패밀리를 사용하면 무엇보다도 데이터 타입을 타입 클래스에 연관시킬 수 있습니다. 따라서 Generic 클래스의 구조는 타입 클래스와 함께 정보를 전달할 수 있는 연관 타입 Rep를 가질 수 있습니다.

class Generic a where
  type Rep a :: * -> *
  from :: a -> (Rep a) x
  to :: (Rep a) x -> a

데이터 타입의 구조를 표현하려면 합, 곱, 빈 분기, 그리고 필드와 생성자의 이름 및 그 타입에 관한 다양한 메타데이터를 인코딩하는 여러 데이터 타입을 마련해야 합니다. 이들은 모두 자유 매개변수 p를 가지며, 이 매개변수는 연관 데이터 타입 Rep a에서 사용될 때 타입 클래스 인스턴스의 헤드에 바인딩됩니다.

data    V1        p                       -- Empty
data    U1        p = U1                  -- ()
data    (:+:) f g p = L1 (f p) | R1 (g p) -- Sum
data    (:*:) f g p = (f p) :*: (g p)     -- Product
newtype K1    i c p = K1 { unK1 :: c }    -- a container for a c
newtype M1  i t f p = M1 { unM1 :: f p }  -- metadata wrapper

이제 모든 데이터 타입에 대해 이 인스턴스를 손으로 작성할 수도 있으며, 단순한 열거형의 경우 다음과 같습니다.

data Ingredient
  = Flour
  | Sugar

instance Generic Ingredient where
  type Rep Ingredient = M1 D (T_Ingredient ((M1 C (C_Flour U1)) :+: (M1 C (C_Sugar U1))))

  from Flour = M1 (L1 (M1 U1))
  from Sugar = M1 (R1 (M1 U1))

  to (M1 (L1 (M1 U1))) = Flour
  to (M1 (R1 (M1 U1))) = Sugar

data T_Ingredient
data C_Flour
data C_Sugar

여기서의 인스턴스는 순전히 기계적이며, GHC가 내부적으로 표현하는 구문 트리, 즉 GHC.DataCon 타입과 GHC.TypeCon 타입으로부터 유도할 수 있습니다. -XDeriveGeneric 확장을 사용하면 GHC가 이 타입 클래스를 자동으로 찍어 내게 할 수 있습니다.

{-# LANGUAGE DeriveGeneric #-}

data Ingredient
  = Flour
  | Sugar
  deriving (Generic)

GHC가 하는 작업을 대충 얼버무리고 넘어가지 않도록, 모듈의 데이터 정의로부터 Generic 클래스를 인스턴스화할 때 GHC가 사용하는 내성 로직을 실제로 재현해 봅시다. 모듈을 동적으로 로드하고 컴파일을 가로채 그 데이터 타입들의 내부 구조를 덤프하여, 이것이 어떻게 기계적으로 타입 클래스 인스턴스로 변환되는지 살펴봅시다.

import GHC
import GHC.Paths as Paths

import Name
import TyCon
import TypeRep
import DataCon
import HscTypes

import Text.Show.Pretty

main :: IO ()
main = do

  -- Inside the GHC Monad
  rep <- runGhc (Just Paths.libdir) $ do

    -- Spin up a GHC compiler environment
    dflags <- getSessionDynFlags
    setSessionDynFlags dflags

    -- Make a dummy module to inject
    let mn = mkModuleName "Test"

    -- Make a dummy target
    addTarget Target {
      targetId = TargetModule mn
    , targetAllowObjCode = True
    , targetContents = Nothing
    }

    -- Run the GHC pipeline
    load LoadAllTargets
    modSum <- getModSummary mn
    p <- parseModule modSum
    t <- typecheckModule p

    -- Pluck out the module tycons after we're done type-checking
    DesugaredModule tcmod modguts <- desugarModule t
    let tycons = mg_tcs modguts

    -- Deconstruct all datatypes into their sums-of-products.
    return (deconstruct tycons)

  putStrLn (ppShow rep)

이제 GHC가 내부적으로 표현하는 “모듈 내장(module guts)“에 접근할 수 있으므로 분해 로직을 작성할 수 있습니다. 이 로직은 대부분 ADT를 주무르는 코드로 이루어진 고작 수백 줄 정도의 분량입니다.

deconstruct :: [TyCon] -> [Data]
deconstruct = fmap go
  where
    go x
      | isProduct x = M1 $ D Datatype
        { dataTypeName = getOccString (tyConName x)
        , modName      = modString x
        , isNewtype    = isNewTyCon x
        , datatype     = Product (mkProduct x)
        , recursive    = isRecursiveTyCon x
        }

      | isVoid x = M1 $ D Datatype
        { dataTypeName = getOccString (tyConName x)
        , modName      = modString x
        , isNewtype    = isNewTyCon x
        , datatype     = V1
        , recursive    = isRecursiveTyCon x
        }

      | otherwise = M1 $ D Datatype
        { dataTypeName = getOccString (tyConName x)
        , modName      = modString x
        , isNewtype    = isNewTyCon x
        , datatype     = Sum (mkProduct x)
        , recursive    = isRecursiveTyCon x
        }

mkRecord :: TyCon -> [Data]
mkRecord x = concatMap mkRProduct (tyConDataCons x)

mkProduct :: TyCon -> [Data]
mkProduct x = fmap go (tyConDataCons x)
  where
    go :: DataCon -> Data
    go x | isRecord x   = Product (mkRProduct x)
    go x | isDProduct x = Product (mkDProduct x)
    go x                = M1 (C (Constructor (conNames x)))

mkDProduct :: DataCon -> [Data]
mkDProduct xs = [K1 (showType x) | x <- dataConOrigArgTys xs]

mkRProduct :: DataCon -> [Data]
mkRProduct x = [M1 (S (Selector (getOccString fld)) ty) | (fld, ty) <- zip (fieldNames x) (mkDProduct x)]

디컴파일 스크립트를 실행하기 위해 더미 모듈 Test.hs를 다음과 같이 준비합니다.

data PlatonicSolid
  = Tetrahedron
  | Cube
  | Octahedron
  | Dodecahedron
  | Icosahedron

data Person = Person
  { firstName       :: String
  , lastName        :: String
  , age             :: Int
  , height          :: Float
  , phoneNumber     :: String
  , flavor          :: String
  } deriving (Show)

data T
  = T1 { a :: Int, b :: Float }
  | T2 { c :: Int, d :: Double }

PlatonicSolid에 대해서는 다음과 같은 표현을 얻습니다.

M1
   (D Datatype
        { dataTypeName = "PlatonicSolid"
        , modName = "Test"
        , isNewtype = False
        , datatype =
            Sum
              [ M1 (C Constructor { conName = "Tetrahedron" })
              , M1 (C Constructor { conName = "Cube" })
              , M1 (C Constructor { conName = "Octahedron" })
              , M1 (C Constructor { conName = "Dodecahedron" })
              , M1 (C Constructor { conName = "Icosahedron" })
              ]
        , recursive = False
        })

Person에 대해서는 다음과 같은 표현을 얻습니다.

M1
    (D Datatype
         { dataTypeName = "Person"
         , modName = "Test"
         , isNewtype = False
         , datatype =
             Product
               [ M1 (S Selector { selName = "firstName" } (K1 "String"))
               , M1 (S Selector { selName = "lastName" } (K1 "String"))
               , M1 (S Selector { selName = "age" } (K1 "Int"))
               , M1 (S Selector { selName = "height" } (K1 "Float"))
               , M1 (S Selector { selName = "phoneNumber" } (K1 "String"))
               , M1 (S Selector { selName = "flavor" } (K1 "String"))
               ]
         , recursive = False
       })

곱의 합인 T에 대해서는 다음과 같은 표현을 얻습니다:

M1
  (D Datatype
       { dataTypeName = "T"
       , modName = "Test"
       , isNewtype = False
       , datatype =
           Sum
             [ Product
                 [ M1 (S Selector { selName = "a" } (K1 "Int"))
                 , M1 (S Selector { selName = "b" } (K1 "Float"))
                 ]
             , Product
                 [ M1 (S Selector { selName = "c" } (K1 "Int"))
                 , M1 (S Selector { selName = "d" } (K1 "Double"))
                 ]
             ]
       , recursive = False
       })

이 데이터는 이후 파생된 Generic 인스턴스에서 Rep 인스턴스를 생성하는 데 사용됩니다. 이것이 -XDeriveGeneric이 내부에서 동작하는 방식을 대략적으로 설명한 것입니다. 아주 복잡한 것은 없고 단지 정보를 기록하고 관리하는 일일 뿐입니다.

GHC.Generics

내부 표현으로부터 여러 생성자에 대한 메타데이터를 저장하는 타입 클래스 인스턴스 몇 개를 찍어 냅니다.

class Datatype d where
  datatypeName :: t d f a -> String
  moduleName   :: t d f a -> String
  isNewtype    :: t d f a -> Bool
  isNewtype _ = False

class Selector s where
  selName :: t s f a -> String

class Constructor c where
  conName :: t c f a -> String

  conFixity :: t c f a -> Fixity
  conFixity _ = Prefix

  conIsRecord :: t c f a -> Bool
  conIsRecord _ = False

예를 들어 앞서 본 Ingredient 예제에서는 생성자 인스턴스 몇 개가 자동으로 생성되며, 이를 통해 AST에서 이름을 조회할 수 있습니다.

type Rep Ingredient = M1 D (T_Ingredient ((M1 C (C_Flour U1)) :+: (M1 C (C_Sugar U1))))

data T_Ingredient
data C_Flour
data C_Sugar

instance Datatype T_Ingredient where
  datatypeName _ = "Ingredient"
  moduleName _ = "Main"

instance Constructor C_Flour where
  conName _ = "Flour"

instance Constructor C_Sugar where
  conName _ = "Sugar"

Java 같은 언어의 리플렉션과 달리 제네릭은 타입 정보를 런타임으로 밀어 넣지 않습니다. 딕셔너리 조회를 제외하면 제네릭은 오버헤드가 없는, 사실상 공짜인 추상화입니다. 우리는 단지 타입 검사 단계에서 컴파일러가 가진 더 많은 정보를 타입에 드러나게 할 뿐이며, 이 정보는 모두 컴파일 과정에서 소거됩니다.

예제

제네릭의 유용성을 보여 줄 억지스럽지 않은 예제를 생각해 보려 했는데, 웹의 다른 곳에 이미 잘 문서화된 예제(JSON 직렬화기, Protocol Buffers, SQL 생성, 순회, 명령줄 파서 등)가 많이 있습니다. 그러니 이 글의 제목에 담긴 실없는 말장난, 즉 타입 클래스 요리하기에 기반한 예제를 살펴봅시다.

그러니 당연히 Pie 타입이 있습니다.

data Pie = Pie
  { filling :: Filling
  , topping :: Maybe Topping
  } deriving (Show, Generic)

data Filling = Apple | Cherry | Pumpkin
  deriving (Show, Generic)

data Topping = IceCream | WhipCream
  deriving (Show, Generic)

제네릭을 사용하여 Haskell 타입의 구조로부터 메뉴에 올릴 수 있는 파이 종류의 목록을 생성하려고 합니다. 레코드는 메뉴 항목의 이름 붙은 변형(“filling” 대 “topping”)을 나타내고, 합 타입은 각 변형 안의 여러 선택지(“cherry filling” 대 “apple filling”)를 나타냅니다.

data Item
  = Item Text [Item]
  | Variant Text [Item]
  | Choice Text
  deriving (Show, Generic)

**기본 시그니처(default signature)**를 가진 타입 클래스를 구현합니다. 이를 통해 타입이 메뉴 항목으로 변환되는 방식을 직접 지정하거나, 제네릭 표현을 사용해 자동으로 생성하는 방식으로 돌아갈 수 있습니다.

class Menu a where
  menu :: a -> [Item]
  default menu :: (Generic a, GMenu (Rep a)) => a -> [Item]
  menu _ = gmenu (Proxy :: Proxy a)

gmenu :: forall a. (Generic a, GMenu (Rep a)) => Proxy a -> [Item]
gmenu _ = gopts (Proxy :: Proxy (Rep a))

제네릭 메뉴는 여러 GHC.Generics 타입 위에서 동작하며 합과 곱을 메뉴에 대응하는 Item 범주로 펼칩니다. GMenu (K1 R f)에 대한 인스턴스에는 Menu 제약이 있어 특정 데이터 타입에 대해 직접 재정의할 수 있습니다. 프록시를 전달하고 있으므로, 때로는 해결해야 하는 인스턴스의 타입으로 캐스트한 undefined를 넘겨 딕셔너리를 직접 전달해야 합니다.

-- Generic Menu
class GMenu a where
  gopts :: Proxy a -> [Item]

-- Datatype
instance GMenu f => GMenu (M1 D x f) where
  gopts _ = gopts (Proxy :: Proxy f)

-- Constructor Metadata
instance (GMenu f, Constructor c) => GMenu (M1 C c f) where
  gopts x
    | conIsRecord (undefined :: t c f a) =
      [Item (pack (conName m)) (gopts (Proxy :: Proxy f))]

    | otherwise = [Choice (pack (conName m))]
    where m = (undefined :: t c f a)

-- Selector Metadata
instance (GMenu f, Selector c) => GMenu (M1 S c f) where
  gopts _ = [Variant (pack (selName m)) (gopts (Proxy :: Proxy f))]
    where m = (undefined :: t c f a)

-- Constructor Paramater
instance (GMenu (Rep f), Menu f) => GMenu (K1 R f) where
  gopts _ = menu (undefined :: f)

-- Sum branch
instance (GMenu a, GMenu b) => GMenu (a :+: b) where
  gopts _ = gopts (Proxy :: Proxy a) ++ gopts (Proxy :: Proxy b)

-- Product branch
instance (GMenu a, GMenu b) => GMenu (a :*: b) where
  gopts _ = gopts (Proxy :: Proxy a) ++ gopts (Proxy :: Proxy b)

-- Void branch
instance GMenu U1 where
  gopts _ = []

구체적으로는 Maybe 타입을 재정의하여, 변형의 “AsIs“를 선택하거나 내부 매개변수가 부여하는 선택지 목록 중 하나를 고르도록 단순히 펼쳐지게 합니다.

instance Menu a => Menu (Maybe a) where
  menu _ = [Choice (pack "AsIs")] ++ (menu (undefined :: a))

예를 들어 Maybe Topping은 세 가지 선택지로 펼쳐집니다.

menu (a :: Maybe Topping) ~ [Choice "AsIs", Choice "IceCream", Choice "whipCream"]

GHC 7.10의 새로운 -XDeriveAnyClass 확장을 사용하면 실제로 다시 돌아가 deriving 절 안에서 Menu를 자동으로 파생할 수 있습니다.

data Pie = Pie
  { filling :: Filling
  , topping :: Maybe Topping
  } deriving (Show, Generic, Menu)

이제 Pie에 대한 딕셔너리를 합성하면 메뉴를 얻을 수 있습니다

menu (undefined :: Pie)

짜잔:

[ Item
    "Pie"
    [ Variant
        "filling" [ Choice "Apple" , Choice "Cherry" , Choice "Pumpkin" ]
    , Variant
        "topping"
        [ Choice "AsIs" , Choice "IceCream" , Choice "WhipCream" ]
    ]
]

우리의 로직은 데이터 타입 제네릭이므로, 작성할 수 있는 어떤 Haskell 타입이든 deriving Menu만으로 Menu로 자동 변환될 수 있습니다. 그러니 이제 새로운 Crisp 디저트(제가 가장 좋아하는 것입니다!)를 추가할 수 있으며, 모든 것을 공짜로 얻습니다!

data Crisp = Crisp
  { contents :: Filling
  , temperature :: Temperature
  } deriving (Show, Generic, Menu)

data Temperature = Warm | Cold
  deriving (Show, Generic, Menu)

-- Add an instance for a pair of menu items. That expands into multiple items.
instance (Menu a, Menu b) => Menu (a,b) where
  menu _ = menu (undefined :: a) ++ menu (undefined :: b)

그리고 두 디저트를 합친 메뉴를 생성할 수 있습니다:

menu (undefined :: (Pie, Crisp))

[ Item
    "Pie"
    [ Variant
        "filling" [ Choice "Apple" , Choice "Cherry" , Choice "Pumpkin" ]
    , Variant
        "topping"
        [ Choice "AsIs" , Choice "IceCream" , Choice "WhipCream" ]
    ]
, Item
    "Crisp"
    [ Variant
        "contents" [ Choice "Apple" , Choice "Cherry" , Choice "Pumpkin" ]
    , Variant "temperature" [ Choice "Warm" , Choice "Cold" ]
    ]
]

이것이 제네릭입니다. 표현력 있는 타입 시스템과 몇 가지 영리한 컴파일러 훅이 보일러플레이트를 대신 요리해 주고 더 맛있고 더 올바른 코드를 내어 줌으로써 프로그래머의 삶을 얼마나 편하게 만들 수 있는지 보여 주는 가장 좋은 대표 사례 중 하나입니다.