Haskell에서 재귀를 분리한 AST를 Fix와 recursion-schemes의 cata, 그리고 Free 모나드를 활용해 표현하고 해석하는 방법을 예제로 설명합니다.
최근에 장난감 컴파일러를 만들어 보면서 AST에 대해 생각해 왔습니다! 저에겐 새로운 주제였고, 트리 자체의 표현과 그것을 해석하는 코드 둘 다를 단순화하는 아이디어에 약간 집착하게 되었죠.
AST는 (보통) 재귀적인 데이터 타입입니다. 즉, 그 데이터 타입 안에 동일한 타입의 값이 다시 들어가 있다는 뜻이죠! 재귀 트리의 가장 단순한 버전은 사실 리스트입니다! 리스트는 각 노드가 0개 또는 1개의 가지를 갖는 재귀(퇴화) 트리라고 볼 수 있어요. Haskell에서 간단한 List AST의 정의는 다음과 같을 수 있습니다:
data List a = Cons a (List a) | End
유치원에서 “정의에 그 단어를 쓰면 안 돼요!”라고 배웠을지 몰라도, 여기서는 예외입니다!
장난감 계산기 프로그램을 위한 조금 더 복잡한 AST는 다음처럼 생겼을 수 있어요:
data Op = Add | Mult
data AST =
BinOp Op AST AST
| Num Int
이 경우 덧셈과 곱셈으로 숫자를 조합할 수 있는 재귀 트리를 정의했습니다. 간단한 수식 (1 + 2) * 3을 이렇게 표현할 수 있죠:
simpleExpr :: AST
simpleExpr = BinOp Mult (BinOp Add (Num 1) (Num 2)) (Num 3)
사람이 읽기엔 썩 편하진 않지만, 컴퓨터가 이해하기엔 아주 쉽습니다! 이 글에서는 파서를 쓰는 대신, 이런 AST를 다루기 좋은 다른 자료구조적 표현을 살펴보겠습니다.
재귀 스킴은 zygohistomorphic prepromorphisms 같은 어려운 말들이 난무하는 상당히 복잡한 주제입니다. 하지만 겁먹지 마세요. 깊게 들어가진 않을 거고, 대신 일반적인 재귀 폴드 함수인 cata를 써서 범용 AST를 아주 깔끔하게 해석하는 방법만 살짝 맛보겠습니다!
recursion-schemes 라이브러리의 핵심 개념은 데이터 타입에서 재귀 부분을 분리해 내는 것입니다. 이렇게 하면 라이브러리가 복잡한 재귀 처리를 대신 해 주고, 우리는 재귀가 어떻게 동작해야 하는지만 쉽게 기술하면 됩니다.
하지만 공짜는 아닙니다. 먼저 우리 데이터 타입을 리팩터링해서 재귀를 “분리”해야 하죠. 그게 무슨 뜻일까요? 기본적으로는 우리의 “구체적인” 데이터 타입을 재귀 위치에 대해 Functor가 되도록 만들어야 한다는 뜻입니다. 예제를 보면 더 쉽습니다. 아까 보았던 List 예제부터 시작해 볼게요:
- data List a = Cons a (List a) | End
+ data ListF a r = Cons a r | End
차이가 보이나요? 타입이 “재귀”하던 자리에 새 타입 매개변수 r(recrusion의 r)을 넣었습니다. 그리고 관례에 따라 새 타입을 ListF로 이름 붙였어요. F는 Functor를 뜻하고, 재귀 부분 위에 Functor 구조가 얹힌 버전이라는 의미입니다.
AST에도 똑같이 적용하면 어떻게 될까요? 봅시다:
data Op = Add | Mult
- data AST =
- BinOp Op AST AST
- | Num Int
+ data ASTF r =
+ BinOpF Op r r
+ | NumF Int
deriving (Show, Functor)
전체적으로 꽤 비슷하죠! 이제 새 타입으로 계산을 표현해 봅시다.
열성적인 분이라면 이미 새 AST 타입으로 앞서의 수식을 다시 써 보다가 문제를 겪었을지도 모르겠네요! 똑같이 (1 + 2) * 3을 시도해 봅시다:
simpleExpr :: ?
simpleExpr = BinOpF Mult (BinOpF Add (Num 1) (Num 2)) (Num 3)
표현 자체는 어렵지 않은데, 타입은 뭘까요?
가장 바깥층의 타입은 재귀 부분을 _로 적으면 ASTF r입니다. 한 층 채워 넣으면 ASTF (ASTF r)가 되죠. 그런데 r도 역시 ASTF r을 나타냅니다. 계속 쓰다 보면 ASTF (ASTF (ASTF (ASTF (ASTF (ASTF ...))))) 꼴로 끝없이 이어집니다.
타입 매개변수가 “무한 재귀”를 의미한다고 GHC에 알려줄 방법이 필요합니다! 다행히 Fix라는 newtype이 그 역할을 해 줍니다.
먼저 recursion-schemes 라이브러리에서 그대로 가져온 짧지만 혼란스러운 Fix 정의부터 볼게요:
newtype Fix f = Fix (f (Fix f))
짧고 달지만, 엄청 헷갈리죠. 무슨 일이냐면, 타입 시그니처의 정의를 지연시킨 재귀 타입으로 미뤄 놓아 타입 시스템을 살짝 ‘속이는’ 겁니다. 재귀의 각 층 사이에 Fix라는 새 레이어를 하나씩 끼워 넣어 타입체커를 만족시키고, 우리가 무한 타입을 손으로 적지 않아도 되게 해 줍니다. Fix에 대한 더 나은 설명도 많으니, 제대로 이해하고 싶다면 찾아보길 권해요! 다만 여기서는 Fix가 어떻게 작동하는지 완전히 이해하지 않아도 쓸 수 있으니, 재미있는 부분으로 넘어가죠.
아래는 Fix를 사용해 표현한 수식입니다. 재귀 타입의 각 층 사이에 Fix 래퍼가 들어가 있는 걸 보세요:
simpleExprFix :: Fix ASTF
simpleExprFix = Fix (BinOpF Mult (Fix (BinOpF Add (Fix (Num 1)) (Fix (Num 2)))) (Fix (Num 3)))
지금 보면 더 복잡해진 것 같을 수도 있지만, 조금만 참아 주세요! 재귀를 분리했고 Fix로 트리를 표현할 수 있게 되었으니, 이제야 비로소 recursion-schemes의 이점을 누릴 수 있습니다!
cata 사용하기recursion-schemes 라이브러리는 우리가 방금 정의한 ASTF 같은 재귀 데이터 타입을 다루기 위한 콤비네이터와 도구들을 제공합니다. 보통은 원래의 재귀 타입(AST)과 재귀를 분리한 버전(ASTF) 사이를 어떻게 변환하는지 라이브러리에 알려주기 위해 Recursive 타입클래스와 Base 타입 패밀리를 구현해야 합니다. 그런데 Fix로 감싼 임의의 Functor는 이들 타입클래스의 구현을 공짜로 얻습니다! 따라서 우리는 바로 recursion-schemes의 도구를 사용할 수 있어요.
함수는 아주 많지만, 여기서 주로 볼 것은 cata 콤비네이터(‘카타모르피즘’의 줄임말)입니다. 이름은 어렵지만, 본질적으로는 재귀 데이터 타입을 간단한 함수들로 하나의 값으로 접어(fold) 내릴 수 있게 해 주는 함수입니다.
사용법은 이렇습니다:
interpret :: Fix ASTF -> Int
interpret = cata algebra
where
algebra :: ASTF Int -> Int
algebra (Num n) = n
algebra (BinOpF Add a b) = a + b
algebra (BinOpF Mult a b) = a * b
이 마법은 뭐죠? 기본적으로 cata는 Fix로 감싼 데이터 타입을 어떻게 순회해야 하는지 알고, 재귀 구조의 각 층마다 함수를 적용해 “unfix”합니다! 우리가 해야 할 일은 algebra(일반적으로 Functor f => f a -> a 형태를 갖는 함수)를 하나 넘겨주는 것뿐입니다.
AST의 서브트리를 직접 평가할 걱정을 전혀 하지 않아도 된다는 점을 보세요. cata는 트리의 바닥까지 자동으로 내려갔다가, 아래에서부터 위로 올라오며 각 서브트리를 평가한 “결과”로 재귀 자리를 대체합니다. 여기까지 오기까지 준비할 것이 많았지만, 대가로 얻는 대수의 단순함은 충분히 가치가 있어요!
Fix와 recursion-schemes는 AST를 표현하는 한 가지 방법이지만, 여기서 더 파고들고 싶은 또 다른 방법이 있습니다. 바로 Free 모나드예요!
Free 모나드는 종종 DSL을 표현하거나, “나중에” 해석하거나 실행할 명령 집합을 표현하는 데 쓰입니다. AST와 꽤 닮았죠! Free 자체가 재귀 전용 도구는 아니지만, AST의 재귀를 표현하는 데 꽤 손쉽게 활용할 수 있습니다. Free가 처음이라면, 여기서 진행하기 전에 잠깐 읽고 오시는 걸 추천해요.
먼저 AST 타입의 새로운 버전을 정의해 봅시다:
data Op = Add | Mult
deriving Show
data ASTFree a =
BinOpFree Op a a
deriving (Show, Functor)
이번에는 Num Int 가지를 제거했다는 점에 주목하세요. 이 말은 ASTFree를 Fix로 감싸면 끝없이 재귀한다는 뜻입니다. 하지만 Free에는 Pure라는 종료(종착) 가지가 있어서, Functor의 고정점(즉, 종료 지점)으로 Num Int 대신 쓸 수 있습니다.
Free로 다시 쓴 원래 수식은 다음과 같습니다:
simpleExprFree :: Free ASTFree Int
simpleExprFree = Free (BinOpFree Mult (Free (BinOpFree Add (Pure 1) (Pure 2))) (Pure 3))
이번에는 말단 표현식의 타입(Int)을 AST 안에 집어넣지 않고, 바깥 타입 매개변수로 뺀 것도 보세요. 이제 문자열, 실수 등 원하는 타입으로도 쉽게 식을 작성할 수 있죠. 다만 인터프리터가 그것을 처리할 수 있도록 만들어야 합니다.
인터프리터는 Fix에서 cata가 맡던 역할을 Control.Monad.Free의 iter로 대신할 수 있습니다:
interpFree :: Free ASTFree Int -> Int
interpFree = iter alg
where
alg (BinOpFree Add a b) = a + b
alg (BinOpFree Mult a b) = a * b
그렇게 어렵지 않죠! 이게 Free 모나드를 약간 과하게 사용하는 걸 수도 있지만, 꽤 잘 동작합니다! 한번 돌려보세요:
>>> interpFree simpleExprFree
9
물론 더 복잡한 AST와 변환에도 이 기법들을 응용할 수 있습니다!
조금이나마 배움이 있었길 바랍니다 🤞! 만약 그렇다면, 제 책도 한 번 살펴봐 주세요. Haskell과 다른 함수형 언어에서 optics를 사용하는 원리를 다루고, 초보자에서 시작해 모든 종류의 optics를 자유자재로 다루는 수준까지 안내합니다. 여기에서 확인하실 수 있어요. 판매 수익은 이런 블로그 글을 쓰는 시간을 확보하고, 교육용 함수형 프로그래밍 콘텐츠를 계속 만드는 데 큰 도움이 됩니다. 감사합니다!