GHC의 최신 기능을 활용해 타입 수준에서 비어 있지 않은 문자열을 보장하는 Haskell 기법과, 이를 통해 TemplateHaskell 호출을 대체해 빌드 시간을 줄인 사례를 살펴봅니다.
이 글은 Haskell 코안입니다. 배경과 동기에 대해서도 이야기하겠지만, 여기서의 목표는 우리가 사용해 보았고 만족스러웠던, 작고 흔치 않은 기법 하나를 공유하는 것입니다. 블로그 글감으로 안성맞춤이죠.
요약하면, 우리는 타입 검사를 거치는 비어 있지 않은 문자열 생성자를 작성했고, 그와 동등한 수천 개의 TemplateHaskell 호출을 대체했으며, 그 결과 이를 많이 호출하던 크고 데이터가 많은 패키지에서 약 10%의 빌드 시간 개선을 얻었습니다.
before, after, invalidBefore, invalidAfter :: NonEmptyText
before = $$(NonEmptyText.make "hello")
after = NonEmptyText.make "hello"
invalidBefore = $$(NonEmptyText.make "") -- ⇝ splice 평가 중 오류 ...
invalidAfter = NonEmptyText.make "" -- ⇝ 타입 오류: 비어 있지 않은 문자열이 필요함
유효하지 않은 상태를 표현 불가능하게 만들기는 Bellroy 소프트웨어의 핵심 설계 목표입니다. 이를 염두에 두고, 우리가 텍스트 데이터에 자주 사용하는 타입 하나가 있는데 — 그리고 그런 데이터는 아주 많습니다 — 바로 NonEmptyText입니다. 이름 그대로, 이 타입의 값은 최소 한 글자를 가진 문자열입니다.
이 기법은 지난 15년 정도에 걸쳐 GHC 기능들이 한데 모인 결과입니다. 특히 GHC 9.10에서 도입된 RequiredTypeArguments를 사용하면 타입 수준 문자열 리터럴을 마치 값인 것처럼 함수에 전달할 수 있습니다. 그리고 빈 문자열을 타입 수준에서 발견했을 때, 다음처럼 사용자 정의 타입 오류 메시지인 "Expected a non-empty string"를 던질 수 있습니다.
type family IsNonEmptySymbol symbol :: Constraint where
IsNonEmptySymbol "" = Unsatisfiable (Text "Expected a non-empty string")
IsNonEmptySymbol _ = (()::Constraint) -- 빈 제약은 항상 만족됨
-- RequiredTypeArguments 이전 문법:
-- make :: forall symbol. IsNonEmptySymbol symbol => NonEmptyText
-- 사용 예: `make @"hello!"`
make :: forall symbol -> (IsNonEmptySymbol symbol) => NonEmptyText
make symbol = NonEmptyText (fromString (symbolVal (Proxy :: Proxy symbol)))
test :: NonEmptyText
test = make "hello!"
적절한 LANGUAGE 마법 주문과 함께라면, 이것은 실제로 동작합니다. 이를 위해서는 UndecidableInstances가 필요한데, 이것 자체가 해롭지는 않지만 무엇이 잘못될 수 있는지의 가능성을 열어 두기는 합니다1.
또한 IsNonEmptySymbol은 타입 패밀리이기 때문에, 일반적인 타입클래스 제약처럼 직접 사용할 수는 없습니다. 예를 들어 Dict에 담을 수도 없고, Data.SOP.hcfoldMap 같은 함수와 함께 사용할 수도 없습니다. 제약을 반환하긴 하지만, 일반적인 타입클래스처럼 그냥 “인스턴스를 하나 요청하는” 식의 대상은 아닙니다.
이 트릭의 마지막 단계는 IsNonEmptySymbol을 타입클래스로 작성하는 것입니다.
class IsNonEmptySymbol symbol
instance {-# OVERLAPPING #-} Unsatisfiable (Text "Expected a non-empty string") => IsNonEmptySymbol ""
instance IsNonEmptySymbol a
-- make: 위와 동일
make :: forall symbol -> (IsNonEmptySymbol symbol) => NonEmptyText
make symbol = NonEmptyText (fromString (symbolVal (Proxy :: Proxy symbol)))
GHC가 빈 문자열에 대해 IsNonEmptySymbol 제약을 해석할 때, 두 가지를 모두 찾게 됩니다: _ => instance IsNonEmptySymbol ""와 instance IsNonEmptySymbol a입니다. 만약 OVERLAPPING pragma를 생략하면, 바로 그 지점에서 GHC가 오류를 발생시킬 것입니다. 실제로 어느 인스턴스를 선택해야 할지 알 수 없기 때문에, 겹치는 가능성이 있다고 불평하게 됩니다. 그런데 그것은 괜찮습니다. 겹치는 인스턴스가 존재하는 유일한 경우가 바로 우리가 금지하고 싶은 경우, 즉 입력이 ""일 때이기 때문입니다.
따라서 여기서 OVERLAPPING pragma의 효과는 GHC가 우리가 “원하는” 인스턴스를 선택하게 만든다는 것입니다. 즉, 사용자 정의 타입 오류를 담은 인스턴스 말입니다. 그러면 그 인스턴스가 사용자가 비어 있지 않은 문자열을 기대했다는 사실을 알리는 우리의 사용자 정의 오류 메시지를 발생시킵니다.
사내 bellroy-data 패키지에는 알려진 화물 및 배송 제공업체, 회계 시스템, 제품 데이터, 세금 코드 등에 대한 정보 같은 데이터가 들어 있는데, 그 안에는 $$(NonEmptyText.makeTH _) 같은 TH splice가 수천 개 있었습니다. 이를 RequiredTypeArgument 방식으로 옮기자 해당 패키지의 컴파일 시간이 약 10% 줄었습니다.
거의 똑같은 코드를 재사용해서, 주어진 Natural이 양수인지 검증하는 타입 검사용 Positive 생성자를 만들 수 있습니다. 일반적으로는 타입 수준 술어를 정의할 수 있는 어떤 타입에 대해서든 이 기법을 사용할 수 있습니다.
여기서부터는 예를 들어 URI를 구성하기 위한 타입 안전한 term 문법을 정의하기 위해 타입 수준 문자열 파싱을 상상할 수도 있을 것입니다. 작동은 하겠지만, GHC의 기본 reduction 한도인 20에 꽤 빨리 부딪히게 됩니다. 길이가 _n_인 문자열에 대한 O(n) 타입 수준 검증기는 최대 20번의 “reduction”, 즉 파싱 단계만 허용되므로, 20자를 넘어서면 파싱이 진행될 수 없습니다. 물론 파싱 단계 자체가 그 한도에 포함되지 않는다고 가정하더라도 말입니다.
일반적으로 사소하지 않은 알고리즘은 타입 패밀리로 표현하기도 꽤 까다롭습니다. 예를 들어 let 바인딩을 작성할 방법도 없고, case와 비슷한 문법으로 패턴 매칭을 할 수도 없습니다. 둘 중 하나라도 필요하다면, 추가 타입 인자와 보조 타입 패밀리의 조합으로 표현해야 합니다. 위에서 만든 IsNonEmptySymbol 클래스처럼 이를 타입클래스로 동작하게 하려면 약간의 배선 작업도 필요합니다.
그럼에도 여기까지 읽으셨다면, 아마 그것이 어떤 모습일지 궁금하실 겁니다. 자, 보세요 🪄, DynamoDB 테이블 이름을 위한 타입 수준 파싱입니다.
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE QuantifiedConstraints #-}
{-# LANGUAGE RequiredTypeArguments #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE UndecidableInstances #-}
import Data.Proxy
import Data.String (fromString)
import Data.Text (Text)
import Data.Type.Bool qualified as Bool
import GHC.TypeError
import GHC.TypeLits
-- | 유효한 DynamoDB 테이블 이름은 regex /^[a-zA-Z_.-]{3,255}$/ 와 일치해야 함
newtype TableName = TableName Text
deriving (Show)
make :: forall name -> (IsValidTableName name) => TableName
make name = TableName (fromString (symbolVal (Proxy :: Proxy name)))
지금까지는 좋습니다. 하지만 유효하지 않은 모든 문자열을 일일이 나열하는 데는 시간이 꽤 걸릴 것입니다. 위의 IsNonEmptySymbol이 작동한 방식이 아니라, 알고리즘적인 접근이 필요합니다. 위와 마찬가지로, 이것을 kind가 Type -> Constraint인 타입클래스로 캡슐화하는 편이 좋습니다. 여기서 제가 사용하는 접근법은 내부 타입클래스의 해석을 지시하기 위해 타입 패밀리를 사용하는 것입니다. 그래서 이 방식은 단항 타입클래스로도 동작하고(바람직하죠), 동시에 프로그래머에게 사용자 정의 타입 오류 메시지도 보여 줍니다(아주 좋습니다).
class (KnownSymbol a) => IsValidTableName a
instance (KnownSymbol a, IsValidTableName_ validity a) => IsValidTableName a
-- | 보기 좋은 오류 메시지를 만들어 내는 래퍼 클래스
--
-- `wasValid` 매개변수는 `IsValidTableName__` 타입
-- 패밀리에 의해 계산됩니다. 그러면 GHC를 아무 일도 하지 않는 인스턴스(성공)나,
-- 어느 정도 정보를 담은 오류를 던지는 인스턴스로 유도할 수 있습니다.
class (IsValidTableName__ a ~ wasValid) => IsValidTableName_ (wasValid :: Bool) a
instance (IsValidTableName__ a ~ 'True) => IsValidTableName_ 'True a
instance (Unsatisfiable ('Text "Encountered invalid TableName")) => IsValidTableName_ 'False a
이제 실제로 IsValidTableName__ (input :: Symbol) :: Bool처럼 생긴 IsValidTableName__ 타입 패밀리를 구현해야 합니다.
type IsValidTableName__ text = IsValidTableName_go 0 'Nothing (UnconsSymbol text)
-- IsValidTableName__를 위한 내부 루프
type family IsValidTableName_go (len :: Nat) (invalidLastChar :: Maybe Char) (unconsResult :: Maybe (Char, Symbol)) :: Bool where
IsValidTableName_go len 'Nothing ('Just '(x, xs)) = IsValidTableName_go (len + 1) (InvalidTableChar x) (UnconsSymbol xs)
IsValidTableName_go len 'Nothing _ = (3 <=? len) Bool.&& (len <=? 255)
IsValidTableName_go len ('Just invalidChar) _ = 'False
-- 개별 문자의 유효성 검사
type family InvalidTableChar (ch :: Char) :: Maybe Char where
InvalidTableChar ch = Bool.If (IsValidTableChar ch) 'Nothing ('Just ch)
type family IsValidTableChar (ch :: Char) :: Bool where
IsValidTableChar '-' = 'True
IsValidTableChar '_' = 'True
IsValidTableChar '.' = 'True
IsValidTableChar ch =
('a' <=? ch Bool.&& ch <=? 'z')
Bool.|| ('A' <=? ch Bool.&& ch <=? 'Z')
Bool.|| ('0' <=? ch Bool.&& ch <=? '9')
마지막으로, 이것을 실제로 사용할 수 있습니다.
valid, invalid, invalid2 :: TableName
valid = make "hello-bellroy123"
invalid = make "no" -- 오류! "Encountered invalid TableName"
invalid2 = make "tablename!!" -- 오류! "Encountered invalid TableName"
여기서는 singletons-th 패키지를 사용해 IsValidTableName 함수 같은 실제 term 수준 함수를 승격시킬 수도 있겠지만, 여기서의 요점은 그것이 내부적으로 실제 어떻게 동작하는지를 보여 주는 것입니다.
Dependent Haskell을 향한 거스를 수 없는 행진이 이어지고 있고, 주요 GHC 릴리스가 나올 때마다 그것은 천천히지만 분명하게 현실에 가까워지고 있습니다. Idris와 Lean 같은 언어는 이미 그것을 갖추고 있지만, 좋든 싫든 Haskell은 이 영역에서 가장 큰 채택과 관성을 가진 언어입니다. GHC 개발자 여러분, 계속 부탁드립니다! 🙂
UndecidableInstances를 자세히 설명하는 훌륭한 블로그 글을 썼고, 이것이 꽤 위험할 수 있는 사용 사례도 다룹니다.↩︎