이 글은 이전 글에서 다룬 Expression Problem을 하스켈 관점에서 다시 살피며, 흔히 제시되는 타입클래스 접근의 한계를 짚고, Swierstra의 "Data types à la carte" 아이디어를 바탕으로 공용 타입(코프로덕트)과 재귀적 Expr 정의, 폴드 기반 해석으로 함수와 타입을 확장하는 방법을 설명한다. 끝으로 이 기법의 복잡성과 실전 적용에 대한 생각을 덧붙인다.
제 이전 글에서는 Expression Problem을 논하고, 여러 언어의 코드를 통해 그 문제와 몇 가지 해법을 보여주었습니다. 하스켈은 함수형 언어의 대표 격으로, Expression Problem의 한 차원(특히 새로운 함수를 추가하는 것은 쉽지만 새로운 타입을 추가하는 것은 어렵다)에서 고통받는 예로 사용했습니다.
그 글의 댓글(및 온라인의 다른 댓글)에서는 타입클래스를 사용하면 하스켈에서 이 문제를 해결하거나 완화할 수 있다고 지적했고, 이제 바로 그 접근을 따라가며 오해가 있다면 바로잡고자 합니다. 타입클래스는 Expression Problem과 관련된 일부 이슈를 우회하는 데 도움을 줄 수 있지만, 완전한 해법을 제공하지는 않습니다—적어도 온라인 튜토리얼에서 흔히 제시되는 방식으로는요. 더 완전한 해법을 위해, 조금 더 파고들겠습니다.
하스켈에서의 Expression Problem은 다음 코드로 보여줄 수 있습니다:
haskelldata Expr = Constant Double | BinaryPlus Expr Expr stringify :: Expr -> String stringify (Constant c) = show c stringify (BinaryPlus lhs rhs) = stringify lhs ++ " + " ++ stringify rhs evaluate :: Expr -> Double evaluate (Constant c) = c evaluate (BinaryPlus lhs rhs) = evaluate lhs + evaluate rhs
새로운 함수(예: typecheck)를 기존 코드를 수정하지 않고 추가하는 것은 쉽지만, 새로운 표현식 타입은 그렇지 않습니다. 새 타입—예컨대 BinaryMul—을 추가하면 기존 코드의 상당 부분, 즉 stringify와 evaluate의 정의(그리고 이미 있었다면 typecheck도)를 수정해야 합니다.
다음은 앞서 언급한 문제를 타입클래스로 “해결”하는 방법을 보여줍니다. “해결”이라는 단어를 따옴표로 감싼 데는 이유가 있습니다—곧 보겠지만, 이것은 완전한 해법이 아닙니다. 그럼에도 온라인에서 가장 흔히 볼 수 있는 해법이기에, 더 깊이 들어가기 전에 자세히 살펴보려 합니다.
먼저 서로 다른 노드에 대한 데이터 타입을 정의합니다:
haskelldata Constant = Constant Double deriving (Show) data BinaryPlus lhs rhs = BinaryPlus lhs rhs deriving (Show)
이제 이들은 서로 분리되어 있으며 같은 데이터의 변형(variant)이 아닙니다. 모든 노드를 하나의 데이터 아래에 두면, 새 타입이 추가될 때마다 모든 함수의 패턴 매칭 규칙을 갱신해야 하므로 Expression Problem이 발생합니다.
이들을 빈 타입클래스로 묶습니다 [1]:
haskellclass Expr e instance Expr Constant instance (Expr lhs, Expr rhs) => Expr (BinaryPlus lhs rhs)
이제 Constant와 BinaryPlus는 전혀 다른 데이터 타입이지만, 둘 다 Expr의 인스턴스이므로, 함수나 다른 클래스가 파라미터 등에 Expr을 구현하는 타입을 요구할 수 있게 해주는 통합 지점을 제공합니다.
이 표현식들에 대한 평가를 구현해 봅시다:
haskellclass (Expr e) => Eval e where evaluate :: e -> Double instance Eval Constant where evaluate (Constant x) = x instance (Eval lhs, Eval rhs) => Eval (BinaryPlus lhs rhs) where evaluate (BinaryPlus lhsx rhsx) = evaluate lhsx + evaluate rhsx
이제 터미널에서 이렇게 할 수 있습니다:
haskell> let e = BinaryPlus (Constant 1.1) (Constant 2.2) > evaluate e 3.3000000000000003
새 함수를 추가하는 것도 꽤 쉽습니다:
haskellclass (Expr e) => Stringify e where stringify :: e -> String instance Stringify Constant where stringify (Constant x) = show x instance (Stringify lhs, Stringify rhs) => Stringify (BinaryPlus lhs rhs) where stringify (BinaryPlus lhsx rhsx) = printf "(%s + %s)" (stringify lhsx) (stringify rhsx)
마찬가지로 기존 코드를 수정할 필요 없이 이것을 추가했습니다. 좋습니다. 그럼 새로운 타입은 어떨까요? 이번에는 더 쉬울까요? BinaryMul 노드를 추가해 보겠습니다:
haskelldata BinaryMul lhs rhs = BinaryMul lhs rhs deriving (Show) instance (Expr lhs, Expr rhs) => Expr (BinaryMul lhs rhs) instance (Eval lhs, Eval rhs) => Eval (BinaryMul lhs rhs) where evaluate (BinaryMul lhsx rhsx) = evaluate lhsx * evaluate rhsx instance (Stringify lhs, Stringify rhs) => Stringify (BinaryMul lhs rhs) where stringify (BinaryMul lhsx rhsx) = printf "(%s * %s)" (stringify lhsx) (stringify rhsx)
한 번 돌려봅시다:
haskell> let d = BinaryMul (Constant 2.0) (BinaryPlus (Constant 2.0) (Constant 0.5)) > evaluate d 5.0 > stringify d "(2.0 * (2.0 + 0.5))"
잘 됩니다! 그리고 주목할 점은, 새 타입을 추가하기 위해 기존 코드를 수정할 필요가 없다는 것입니다—인스턴스 정의는 원래 클래스 바깥에 존재하므로 기존 코드를 건드리지 않고도 새 타입에 대해 정의할 수 있습니다(이는 원글에서 논한 Clojure 멀티메서드와도 비슷합니다).
그럼 이걸로 끝! 문제가 해결된 걸까요? 글쎄요, 아닙니다. 분명 우리는 기존 코드를 수정하지 않고 새로운 함수와 새로운 타입을 모두 추가한 것처럼 보입니다. 하지만 약간만 더 깊이 생각해 보면—큰 문제가 도사리고 있습니다. 무엇인지 떠오르시나요?
좋습니다, 힌트를 드리죠. 문자열을 파싱해 표현식을 만들어내는 함수를 작성하려고 한다고 상상해 봅시다. 이 함수의 타입은 무엇일까요? 특히 반환 타입은요?
Constant와 BinaryPlus를 서로 다른 데이터 타입으로 분리하면서 Expression Problem을 비켜갈 수 있게 되었지만, 동시에 중요한 무언가를 잃었습니다—그들을 하나의 타입으로 통합하는 능력입니다. 아니요, 파싱 함수는 Expr을 반환할 수 없습니다—Expr은 타입이 아니라 타입클래스입니다. 약간 다른 데모를 보시죠:
haskell> let x = 20 > let k = if x > 4 then (Constant 2.2) else (BinaryPlus (Constant 5.5) (Constant 2.1)) <interactive>:43:44: Couldn't match expected type `Constant' with actual type `BinaryPlus Constant Constant' In the return type of a call of `BinaryPlus' In the expression: (BinaryPlus (Constant 5.5) (Constant 2.1)) In the expression: if x > 4 then (Constant 2.2) else (BinaryPlus (Constant 5.5) (Constant 2.1))
하스켈은 이를 허용하지 않습니다. k의 타입은 Constant나 BinaryPlus로 추론될 수 있지만, 이는 컴파일 타임에 결정되어야 합니다. 이 표현식은 런타임 값에 따라 타입을 바꾸려 하는데, 그건 불가능합니다 [2].
이것을 가능하게 하려면, 서로 다른 표현식을 다시 한 번 재고하여 함수가 단일 타입을 반환할 수 있도록 통합해야 합니다. 코드는 상당히 복잡해지므로, 계속 읽기 전에 심호흡을 하시죠.
주의: 아래 내용은 Wouter Swierstra의 논문 "Data types a la carte" 전반부에 대한 제 나름의 해설입니다. 또한 위에서 언급한 문제를 저와 논의해 주고 이 논문을 읽어보라고 친절히 권해주신 Bartosz Milewski께도 감사드립니다.
앞 절은 문제로 끝났습니다—서로 다른 표현식 타입을 어떻게 결합해 하나의 타입으로 참조할 수 있게 만들 것인가? 떠오를 수 있는 한 가지 아이디어는 Either 같은 것을 사용하는 것입니다. 앞서 보인 것과 비슷한 조건부 대입을 보죠:
haskell> let k = if x > 4 then Left "Foo" else Right 20 > :t k k :: Either [Char] Integer
하지만 Either를 곧바로 사용하면 즉각적인 난관이 있습니다:
따라서 Either 자체를 쓰지는 않을 것이고, 영감을 주는 존재로만 남겨두겠습니다.
실제로는, 다음과 같은 것을 정의하며 비슷하게 시작하겠습니다:
haskelldata ET f g e = El (f e) | Er (g e)
Either와 비슷하지만, 타입 생성자용입니다. 세 개의 매개변수를 받습니다: f와 g는 타입 생성자이고, e는 이 타입 생성자들에게 전달될 수 있는 타입입니다. ET는 Either와 유사하게 그들을 “통합”합니다. 논문에서 Swierstra는 ET를 f와 g의 시그니처에 대한 코프로덕트(coproduct)라고 부릅니다.
그런데 이런 타입 생성자들은 어떻게 생겼을까요? 이제 어려운 부분이 옵니다. 종이에 적어가며 생각해 보세요:
haskelldata Expr f = In (f (Expr f))
네, 이것은 재귀적 타입 선언입니다. 여기서 Expr과 f 모두 타입 생성자입니다; f는 생성자들의 서브트리로 등장하는 표현식에 해당하는 타입 매개변수를 받습니다.
좀 더 구체적인 타입으로 넘어가 보죠. 익숙한 표현식 노드 타입 몇 가지입니다:
haskelldata Constant e = Constant Double data BinaryPlus e = BinaryPlus e e data BinaryMul e = BinaryMul e e
유의할 점:
이 타입들은 Functor의 인스턴스로 만들어, 이들 위에 일관되게 map을 적용할 수 있습니다:
haskellinstance Functor Constant where fmap f (Constant x) = Constant x instance Functor BinaryPlus where fmap f (BinaryPlus e1 e2) = BinaryPlus (f e1) (f e2) instance Functor BinaryMul where fmap f (BinaryMul e1 e2) = BinaryMul (f e1) (f e2)
중요하게도, 코프로덕트 ET 역시 Functor입니다:
haskellinstance (Functor f, Functor g) => Functor (ET f g) where fmap f (El e1) = El (fmap f e1) fmap f (Er e2) = Er (fmap f e2)
퍼즐의 또 하나의 중요한 조각은 foldExpr로, 표현식에 대한 폴드를 수행할 수 있게 해줍니다:
haskellfoldExpr :: Functor f => (f a -> a) -> Expr f -> a foldExpr f (In t) = f (fmap (foldExpr f) t)
foldExpr는 펑터 내부에서 값을 꺼내는 함수와 Expr을 받습니다. fmap을 사용해 포함된 타입에서 값을 재귀적으로 추출합니다. 다소 복잡해지고 있으니—곧 예제로 명확히 해보겠습니다.
마침내, 이 표현식들 위에 몇 가지 연산을 정의할 준비가 되었습니다. evaluate부터 시작해 봅시다:
haskellclass Functor f => Eval f where evalFunctor :: f Double -> Double instance Eval Constant where evalFunctor (Constant x) = x instance Eval BinaryPlus where evalFunctor (BinaryPlus x y) = x + y instance Eval BinaryMul where evalFunctor (BinaryMul x y) = x * y instance (Eval f, Eval g) => Eval (ET f g) where evalFunctor (El x) = evalFunctor x evalFunctor (Er y) = evalFunctor y evaluate :: Eval f => Expr f -> Double evaluate expr = foldExpr evalFunctor expr
먼저, Eval은 표현식에서 Double을 만들어내는 evalFunctor 함수를 지원하는 타입클래스입니다. 우리의 데이터 타입들에 대한 인스턴스는 자명하고, ET에 대한 인스턴스는 단순히 조합자의 내용에 따라 왼쪽 또는 오른쪽으로 위임합니다.
예제를 해볼 준비가 되었습니다. 먼저 현재 존재하는 세 표현식 타입을 모두 통합하는 타입을 정의합니다:
haskelltype GeneralExpr = Expr (ET Constant (ET BinaryPlus BinaryMul))
이는 단순히 타입들의 이진 트리를 구성합니다; 다시 Either를 떠올리면—이는 타입을 위한 가변 길이 버전의 Either와 같습니다. 모양은 다음과 같습니다:
ET
/ \
/ \
/ \
Constant ET
/ \
/ \
/ BinaryMul
/
BinaryPlus
예로, 간단한 상수를 정의하고 평가하면 다음과 같습니다:
haskell> let x = In(El(Constant 7.0)) :: GeneralExpr > evaluate x 7.0
x가 왜 저렇게 정의되는지 보이시나요? 트리를 따라가기만 하면 됩니다; 한 번 왼쪽(El)으로 가면 Constant에 도달합니다; 그런 다음 In으로 감싸 Expr로 만들면 끝. 이제 evaluate x가 호출되면 무슨 일이 일어날까요? 추적해 봅시다:
-> evaluate x
... x는 GeneralExpr 타입이므로 Expr이며,
... 또한 ET에 대한 Eval 인스턴스가 있으므로 Eval 제약을 만족합니다
-> foldExpr evalFunctor x
-> evalFunctor (fmap (foldExpr evalFunctor) (El(Constant 7.0)))
... 먼저, El(Constant 7.0)에 fmap을 적용합니다; ET의 fmap 정의를 보면
... 이는 El(fmap <...> (Constant 7.0))이 됩니다
-> evalFunctor El(fmap (foldExpr evalFunctor) (Constant 7.0))
... 그런데 Constant에 무엇을 fmap하든 그대로 그 Constant가 나옵니다, 따라서:
-> evalFunctor El(Constant 7.0)
... ET에 대한 Eval 인스턴스를 보면 (El x)의 경우
... evalFunctor x를 호출합니다
-> evalFunctor(Constant 7.0)
... 마지막으로 evalFunctor (Constant x)의 결과는 x입니다
-> 7.0
이제 더 복잡한 표현식을 정의해 봅시다:
haskell> let y = In(El(Constant 2.0)) :: GeneralExpr > let mulXY = In(Er(Er(BinaryMul x y))) :: GeneralExpr > let addXmulXY = In(Er(El(BinaryPlus x mulXY))) :: GeneralExpr > evaluate addXmulXY -- 참고: 이것은 "x + xy"를 계산함 21.0
좀 더 오래 걸리겠지만, 위에서 단순한 경우를 추적했던 것처럼 이 evaluate도 충분히 따라갈 수 있을 것입니다. 연습해 보시길 권합니다! GeneralExpr에 대해 정의된 ET 트리에서 BinaryPlus와 BinaryMul 노드가 올바른 경로 선택으로 어떻게 생성되는지 특히 주목하세요.
이제 이 해법에 새 함수를 어떻게 추가하는지 볼 시간입니다. stringify를 추가해 봅시다; evaluate를 어떻게 했는지 알았으니 매우 직관적입니다:
haskellclass Functor f => Stringify f where stringifyFunctor :: f String -> String instance Stringify Constant where stringifyFunctor (Constant x) = show x instance Stringify BinaryPlus where stringifyFunctor (BinaryPlus x y) = "(" ++ x ++ " + " ++ y ++ ")" instance Stringify BinaryMul where stringifyFunctor (BinaryMul x y) = "(" ++ x ++ " * " ++ y ++ ")" instance (Stringify f, Stringify g) => Stringify (ET f g) where stringifyFunctor (El x) = stringifyFunctor x stringifyFunctor (Er y) = stringifyFunctor y stringify :: Stringify f => Expr f -> String stringify expr = foldExpr stringifyFunctor expr
완전히 같은 패턴을 따르며, 물론 기존 코드를 수정할 필요가 없습니다. 우리의 노드 타입은 단일 데이터 타입에 속해 있지 않으므로, 갱신할 패턴 매칭이 없습니다. 새 기능은 Stringify 타입클래스의 인스턴스로 제공됩니다.
haskell> stringify x "7.0" > stringify addXmulXY "(7.0 + (7.0 * 2.0))"
앞 절의 기법은 표현 문제를 해결합니다. 또한 단순 타입클래스 접근에서의 문제도 겪지 않습니다. 왜냐하면 이제 실제로 Expr이라는 통합 타입이 있으니까요. 이전 시도에서처럼 두 타입 중 하나로 조건부로 값을 정의하는 것으로 돌아가 보죠:
haskell> let k = if p > 4 then x else addXYmulX > :t k k :: GeneralExpr > evaluate k 7.0
와, 된다! 이제 런타임에 실제 노드 타입이 결정되더라도, GeneralExpr를 반환하는 파서를 실제로 작성할 수 있습니다.
하지만 모든 것이 완벽하지는 않습니다. 이 접근에는 몇 가지 문제가 있습니다. 첫째, 표현식을 만드는 작업이 정말 번거롭습니다. addXmulXY 노드를 만들기 위해 필요한 일련의 임시 let들을 떠올려 보세요. El과 Er의 중첩은 꽤 피곤합니다.
또한 표현 언어에 노드 타입을 더 추가하면, ET 트리가 더 깊어지므로 이러한 정의는 더욱 복잡해질 것입니다. 그리고 마지막이자 최악의 문제는, El / Er 경로가 바뀌기 때문에 기존에 표현식을 만드는 코드를 다시 작성해야 한다는 점입니다. 기존 노드의 정의를 수정할 필요는 없고, evaluate나 stringify 같은 기존 함수 정의도 수정할 필요는 없으며(새 타입에 대한 인스턴스만 추가하면 됩니다), 엄밀히 말해 Expression Problem을 위반하는 것은 아닙니다.
이 문제들을 해결하는 여러 가지 방법이 있으며, 모두 코드를 더 복잡하게 만듭니다(개인적으로 재귀적 Expr 정의라는 현재 접근도 이미 꽤 난해하다고 느낍니다). Swierstra의 논문을 계속 읽어보면, 4절에서 더 똑똑한 생성자를 만들어 완화하는 방법을 논합니다; 심지어 Haskell 98 표준을 벗어나 언어 확장 지원까지 요구합니다.
솔직히 말해, 이번 탐구는 이미 코드 복잡성의 나라로 너무 멀리 들어간 것 같습니다. Expression Problem이 정말 그렇게 심각할까요? 왜 기존 코드를 수정하는 것이 그런 금기일까요? 제 생각에 건강한 코드 베이스는 지속적으로 손질되고 리팩터링되어야 하며, 일반화를 위해 기존 코드를 수정하는 데 아무 문제 없습니다. 물론 Clojure처럼 해법이 사소한 경우, 이러한 불변조건을 유지하는 비용은 꽤 적습니다. 그러나 하스켈에서 여기 제시한 접근은 너무 복잡해서, 실전에서 사용할 때는 조심해야 한다고 생각합니다. 여기에는 비용-편익 분석이 필요하며, 어느 쪽으로 기울지 확신하기 어렵습니다.
[1] 이 타입클래스는 인스턴스가 구현해야 할 메서드를 선언하지 않는다는 의미에서 “빈” 타입클래스입니다. 따라서 어떤 타입이든 그저 인스턴스로 선언하기만 하면 이 클래스의 인스턴스가 될 수 있습니다.
[2] 우연히도, Clojure의 동적 특성은 바로 이것이 Clojure의 다중 디스패치 해법에서 문제가 되지 않는 이유입니다. 하스켈과 달리 Clojure는 모든 표현식에 대해 컴파일 타임 타입을 추론하려 하지 않으며, 실행 중에 값이 서로 다른 타입을 지닐 수 있습니다.
[3] 여기서 “타입 생성자(type constructor)”는 널이 아닌(non-nullary) 타입 생성자를 의미합니다.
댓글은 이메일로 보내주세요.