GHC 깊이 들여다보기: 중간 형태

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

지난 블로그 글에서는 GHC 컴파일러 내부에서 사용되는 고수준 API를 살펴보았습니다. 이번에는 컴파일 파이프라인의 프런트엔드를 구성하는 요소들, 즉 다음 항목들을 자세히 살펴봅시다.

파싱
이름 변경
타입 검사
디슈거링
단순화
코드 생성

**[Accompaying Source Code](https://github.com/sdiehl/dive-into-ghc/tree/master/02-parser)**

패스

다음 함수들은 HscMain의 컴파일러 드라이버 함수 내부에서 사용되는 주요 패스입니다.

-- Parse a module.
parseModule :: GhcMonad m => ModSummary -> m ParsedModule

-- Typecheck and rename a parsed module.
typecheckModule :: GhcMonad m => ParsedModule -> m TypecheckedModule

-- Desugar a typechecked module.
desugarModule :: GhcMonad m => TypecheckedModule -> m DesugaredModule

-- Extract ModGuts
coreModule :: DesugaredMod m => m -> ModGuts

-- Generated STG bindings from Core module
coreToStg :: DynFlags -> Module -> CoreProgram -> IO [StgBinding]

이 함수들은 각각 Haskell 모듈을 기계어 코드로 컴파일하거나 인터프리트할 수 있는 형태로 컴파일하는 과정에서 사용되는 중간 형태를 다룹니다.

파서

Haskell의 프런트엔드 구문은 상당히 방대하며, 일부는 Haskell 2010 명세에 정의되어 있고 GHC가 이를 확장합니다. 파서는 두 가지 전용 도구를 사용하여 작성됩니다.

어휘 분석을 위한 Alex. 참고: Lexer.x
파서 자체를 위한 Happy. 참고: Parser.y

Happy는 Haskell을 위한 파서 생성기 시스템으로, 다음 C 도구와 유사합니다: yacc' for C. It works as a preprocessor with it's own syntax that generates a parse table from two specifications, a lexer file and parser file. The Happy parser consists of a list of a production rules and a monad to running the parser in. Production rules consist of a set of options on the left and generating Haskell expressions on the right with indexed variables ( $1, $2, ...) mapping to the ordered terms on the left (i.e. in the second termterm~ $1, term~$2`).

terms
    : term                   { [$1] }
    | term terms             { $1 : $2 }

렉서에서 가장 복잡한 부분은 공백에 민감한 레이아웃과 관련된 부분입니다. 공백을 처리하기 위해 렉서는 특정 생성 규칙의 줄 위치를 분석하고, 문법을 정규화하는 데 사용되는 가상 토큰(vbrace, vsemi 등)을 출력합니다. 예를 들어 do 표기법에서 레이아웃 규칙을 사용하는 경우는 다음과 같습니다.

main = do
  putStrLn "Hello"
  putStrLn "Haskell"

이는 파싱 시점에 명시적인 가상 중괄호와 세미콜론으로 변환됩니다.

main = do { putStrLn "Hello"; putStrLn "Haskell" }

주요 진입점은 Parser 파서 모듈에 정의되어 있으며, 소스 버퍼와 파일 이름 및 위치에 대한 상태를 담는 모나드 P로 귀결됩니다. 그 결과로 생성되는 AST는 HsSyn이라고 하며, 토큰에서 보존된 위치 정보를 담고 있습니다.

parseType :: P (LHsType RdrName)
parseExpression :: P (LHsExpr RdrName)
parseModule :: P (Located (HsModule RdrName))

Located

GHC의 프런트엔드 구문은 오류 보고에 사용할 수 있는 위치 정보를 함께 가지고 다닙니다. 위치 정보는 Located 타입으로 정의되며, 이 타입은 “위치가 지정될” AST 요소를 나타내는 타입 매개변수 하나를 가집니다. 일반적으로 타입 동의어는 타입 앞에 “L“이 붙으면 위치가 지정된 요소에 대한 동의어임을 나타내는 관례를 따릅니다. 따라서 위치가 지정된 HsExpr는 LHsExxpr입니다.

data GenLocated l e = L l e
type Located e = GenLocated SrcSpan e

unLoc :: GenLocated l e -> e
unLoc (L _ e) = e

getLoc :: GenLocated l e -> l
getLoc (L l _) = l

noLoc :: e -> Located e
noLoc e = L noSrcSpan e

가장 주목할 만한 것은 위치 정보가 붙은 요소에 대해 fmap을 적용하기 위한 함자 인스턴스로, 이는 위치를 보존하면서 내부 타입을 변경합니다.

instance Functor (GenLocated l) where
  fmap f (L l e) = L l (f e)

프런트엔드 구문

프런트엔드 구문(HsSyn이라고 부릅니다)은 파서가 생성하는 모든 구문 요소를 담고 있는 여러 데이터 타입에 걸쳐 나뉘어 있습니다. 이 타입들은 이름 타입으로 매개변수화되어 있으므로, 변환(renamer 등)이 구문 트리 구조를 보존하면서 바인딩과 식별자의 구조를 바꿀 수 있습니다.

HsModule - 모듈의 최상위 구조입니다. 모듈 이름, export, import, 최상위 선언을 담고 있습니다.
HsDecl - 타입, 클래스, 값, 인터페이스 시그니처 선언입니다
HsBind - 최상위 바인딩과 중첩된 바인딩 모두에 사용되는 값 바인딩입니다.
HsGroup - HsGroup은 서로 관련된 HsDecl들의 그룹입니다.
HsLit - 리터럴 값(Int, Char 등)입니다
HsExpr - Haskell 표현식입니다.
HsType - 프런트엔드 타입 주석입니다.
Pat - case 문이나 최상위 바인딩에서의 패턴 매치입니다.

컴파일의 여러 단계에서 사용되는 식별자에는 여러 변형이 있습니다. 일반성 순서대로 나열하면 다음과 같습니다.

OccName - 사용되는 가장 단순한 이름으로, 이름을 문자열로 담으며 그 이름이 유래한 네임스페이스와 위치도 함께 담습니다.
RdrName - 파서에서 곧바로 나오는 이름의 타입입니다. 이름이 한정되지 않았는지, 아니면 (모듈 이름으로) 한정되었는지에 대한 정보를 담고 있습니다.
Name - 스코프와 바인딩이 해석된 이름의 타입입니다. OccName을 가질 뿐 아니라 Name들을 서로 구별해 주는 Unique도 가집니다
Var - Name뿐 아니라 Type도 가지는 이름의 타입입니다. Var는 전역이거나 지역입니다.

Name들은 Unique라고 부르는 내부의 고유한 숫자 키로 서로 구별되며, 이 키는 UniqSupply에서 생성됩니다. 이것들은 흔히 패스의 모나드 트랜스포머 MonadUnique 계층 안에 들어 있습니다.

타입 검사 이후에는 Var와 Id 이름을 다루는데, 이들은 다음 함수들을 사용하여 언제나 Name과 Type을 복원할 수 있다는 성질을 가집니다.

varName :: Var -> Name
varType :: Var -> Kind

또한 많은 조회 함수는 식별자나 타입 생성자처럼 스코프 안에 있으면서 타입을 가지는 “것들“을 감싸는 합 타입 TyThing을 사용합니다.

data TyThing
  = AnId Id
  | AConLike ConLike.ConLike
  | ATyCon TyCon
  | ACoAxiom (CoAxiom Branched)

Outputable

GHC API 안에는 많은 내부 타입의 요약을 보기 좋게 출력하는 데 사용할 수 있는 프리티 프린터가 있습니다. 이 클래스의 구조는 Show 타입 클래스와 비슷합니다.

class Outputable a where
  ppr :: a -> SDoc
  pprPrec :: Rational -> a -> SDoc

showPpr :: Outputable a => DynFlags -> a -> String

조금 더 편하게 작업하기 위해, 기본 dynflags를 사용하여 Outputable 인스턴스를 출력하는 래퍼 showGhc를 작성할 수 있습니다.

showGhc :: (Outputable a) => a -> String
showGhc = showPpr unsafeGlobalDynFlags

컴파일 추적하기

다음 예제 모듈이 주어졌을 때, 이 모듈이 컴파일러를 거치는 동안 중간 형태들이 어떻게 변환되는지 추적해 보겠습니다.

module Example where

data Animal = Cat | Dog

add :: Int -> Int -> Int
add x y = x + y

이전 글에서 만든 장치를 사용하여 모듈 타깃을 임포트하고 로드한 다음, 이를 대화형 컨텍스트에 추가하는 대신 개별 패스의 함수를 명시적으로 호출하여 그 구조를 화면에 출력합니다.

main :: IO ()
main = runGhc (Just libdir) $ do
  env <- getSession
  dflags <- getSessionDynFlags
  setSessionDynFlags $ dflags { hscTarget = HscInterpreted }

  target <- guessTarget "Example.hs" Nothing
  setTargets [target]
  load LoadAllTargets
  modSum <- getModSummary $ mkModuleName "Example"

  pmod <- parseModule modSum      -- ModuleSummary
  tmod <- typecheckModule pmod    -- TypecheckedSource
  dmod <- desugarModule tmod      -- DesugaredModule
  let core = coreModule dmod      -- ModGuts
  stg <- liftIO $ coreToStg dflags (mg_module core) (mg_binds core)

  liftIO $ banner "Parsed Source"
  liftIO $ putStrLn $ showGhc ( parsedSource pmod )

  liftIO $ banner "Renamed Module"
  liftIO $ putStrLn $ showGhc ( tm_renamed_source tmod )

  liftIO $ banner "Typechecked Module"
  liftIO $ putStrLn $ showGhc ( tm_typechecked_source tmod )

  liftIO $ banner "Typed Toplevel Definitions"
  liftIO $ putStrLn $ showGhc ( modInfoTyThings (moduleInfo tmod) )

  liftIO $ banner "Typed Toplevel Exports"
  liftIO $ putStrLn $ showGhc ( modInfoExports (moduleInfo tmod) )

  liftIO $ banner "Core Module"
  liftIO $ putStrLn $ showGhc ( mg_binds core )

  liftIO $ banner "STG"
  liftIO $ putStrLn $ showGhc stg

파싱

모듈 요약에서 소스 파일 Example.hs의 기반 텍스트 스트림을 추출할 수 있습니다. 여기에 파서를 실행하면 원시 OccName이 담긴 HsSyn AST를 포함하는 ParsedSource 데이터 타입이 생성됩니다.

data ParsedModule = ParsedModule
  { pm_mod_summary :: ModSummary
  , pm_parsed_source :: ParsedSource
  , pm_extra_src_files :: [FilePath]
  , pm_annotations :: ApiAnns
  }

===============================Parsed Source===============================
module Example where
data Animal = Cat | Dog
add :: Int -> Int -> Int
add x y = x + y

이름 변경

파싱 후에는 리네이머 패스를 실행합니다. 이 패스는 스코프와 연산자 우선순위를 해석하고, 충돌이 일어나지 않도록 모든 이름을 고유하게 만드는 일을 맡습니다. 리네이머는 모든 구문 요소에 걸쳐 RdrName을 Name으로 해석합니다. 또한 각 이름에 한정된 전역 이름인지, 현재 모듈의 지역 이름인지를 주석으로 붙입니다. 이름이 스코프에 없으면 컴파일은 그 자리에서 멈추고 누락된 이름을 보고합니다.

===============================Renamed Module===============================
Just (add :: Int -> Int -> Int
      add x y = x + y

      data Animal = Cat | Dog,
      [import (implicit) Prelude],
      Nothing,
      Nothing)

타입 검사

이름이 변경된 AST는 이어서 타입 검사기를 거치며, 타입 검사기는 Name을 Id로 매핑하고 타입 추론으로 추론한 타입을 덧붙입니다.

data TypecheckedModule = TypecheckedModule
  { tm_parsed_module :: ParsedModule
  , tm_renamed_source :: Maybe RenamedSource
  , tm_typechecked_source :: TypecheckedSource
  , tm_checked_module_info :: ModuleInfo
  , tm_internals_ :: (TcRnTypes.TcGblEnv, HscTypes.ModDetails)
  }

그 결과로 얻는 구조는 모든 바인딩과 모든 하위 표현식의 최상위 타입을 담은 타입 검사된 모듈입니다.

=============================Typechecked Module=============================
{AbsBinds [] []
   {Exports: [add <= add
                <>]
    Exported types: add :: Int -> Int -> Int
                    [LclId, Str=DmdType]
    Binds: add x y = (+) x y}}

결과 데이터 타입에는 ModuleInfo 필드가 있으며, 여기에는 타이핑 환경, 스코프 안의 이름, 내보낸 타입 클래스에 관한 다양한 메타데이터가 담겨 있습니다.

data ModuleInfo = ModuleInfo
  { minf_type_env :: HscTypes.TypeEnv
  , minf_exports :: NameSet.NameSet
  , minf_rdr_env :: Maybe RdrName.GlobalRdrEnv
  , minf_instances :: [ClsInst]
  , minf_iface :: Maybe ModIface
  , minf_safe :: SafeHaskellMode
  , minf_modBreaks :: ModBreaks
  }

coreModule을 사용하면 끔찍한 이름의 ModGuts 데이터 타입도 구성할 수 있습니다. 이 데이터 타입에는 각종 내보내기와 타입이 관련 메타데이터와 함께 펼쳐진 형태로 담겨 있습니다.

data ModGuts = ModGuts
  { mg_module :: !Module,
  , mg_boot :: IsBootInterface
  , mg_exports :: ![Avail.AvailInfo]
  , mg_deps :: !Dependencies
  , mg_dir_imps :: !ImportedMods
  , mg_used_names :: !NameSet.NameSet
  , mg_used_th :: !Bool
  , mg_rdr_env :: !RdrName.GlobalRdrEnv
  , mg_fix_env :: !FixityEnv
  , mg_tcs :: ![TyCon]
  , mg_insts :: ![ClsInst]
  , mg_fam_insts :: ![FamInst]
  , mg_patsyns :: ![PatSyn.PatSyn]
  , mg_rules :: ![CoreSyn.CoreRule]
  , mg_binds :: !CoreSyn.CoreProgram
  , mg_foreign :: !ForeignStubs
  , mg_warns :: !Warnings
  , mg_anns :: [Annotations.Annotation]
  , mg_hpc_info :: !HpcInfo
  , mg_modBreaks :: !ModBreaks
  , mg_vect_decls :: ![CoreSyn.CoreVect]
  , mg_vect_info :: !VectInfo
  , mg_inst_env :: InstEnv.InstEnv
  , mg_fam_inst_env :: FamInstEnv.FamInstEnv
  , mg_safe_haskell :: SafeHaskellMode
  , mg_trust_pkg :: Bool
  , mg_dependent_files :: [FilePath]
  }

이 시점에서는 ModuleInfo에 타입이나 이름에 관한 어떤 정보든 질의할 수 있습니다. 예를 들어 어떤 전역 이름의 타입이 궁금하다면 타이핑 환경 안에서 TyThing으로 찾아볼 수 있습니다.

modInfoTyThings :: ModuleInfo -> [TyThing]
modInfoExports :: ModuleInfo -> [Name]

=========================Typed Toplevel Definitions=========================
[Type constructor ‘Animal’, Data constructor ‘Cat’,
 Data constructor ‘Dog’, Identifier ‘add’, Identifier ‘Cat’,
 Identifier ‘Dog’]

===========================Typed Toplevel Exports===========================
[Animal, Cat, Dog, add]

Core

Core 언어는 GHC에서 가장 핵심적인 데이터 타입입니다. Core는 System FC를 변형한, 매우 작고 명시적으로 타입이 지정된 언어입니다. typecheckModule 함수의 출력은 CoreModule 데이터 타입이며, 여기에는 Core 프로그램이 타이핑 환경으로 담겨 있습니다.

data CoreModule = CoreModule
  { cm_module :: !Module
  , cm_types :: !HscTypes.TypeEnv
  , cm_binds :: CoreSyn.CoreProgram
  , cm_safe :: SafeHaskellMode
  }

Core 모듈을 살펴보면 이제 프로그램의 각 이름에 명시적 타입이 주석으로 붙어 있고 타입 클래스 딕셔너리가 삽입되어 있음을 알 수 있습니다.

================================Core Module================================
[add :: Int -> Int -> Int
 [LclIdX, Str=DmdType]
 add = \ (x :: Int) (y :: Int) -> + @ Int $fNumInt x y]

그런 다음 Core는 코드 생성을 위해 프로그램을 최적화하는 여러 분석 패스를 적용하기 쉬운 중간 형태로 변환됩니다. 이 형태는 Spineless Tagless G-Machine이라고 알려진 추상 기계입니다. 이 구문에서 모든 클로저에는 연관된 Static Reference Table, 즉 SRT가 있습니다. 이에 관해서는 나중에 더 다룹니다.

====================================STG====================================
[add :: Int -> Int -> Int
 [LclIdX, Str=DmdType] =
     \r srt:SRT:[r6ry :-> $fNumInt] [x y] + $fNumInt x y;]

요약 및 다음 단계

Core와 STG는 간략하게만 언급했습니다. 프런트엔드 구문이 Core로 변환되는 과정이 다음 주제가 될 것입니다. Core의 설계는 언어의 구조에 관한 많은 측면을 정의하며, 타입 시스템과 코드 생성에도 영향을 줍니다.

Keyboard shortcuts

Stephen Diehl 블로그 한국어 번역