この記事はThe Architecture of Open Source Applications (Volume 2): The Glasgow Haskell Compilerの翻訳です。

The Glasgow Haskell Compiler

Simon MarlowとSimon Peyton-Jones

Glasgow Haskell Compiler（GHC）は次のいくつかの目標と共に、1990年代の初めに英国政府によって学術研究プロジェクトの一環として設立されました。

• 堅牢で移植性があり、高性能なコードを生成できるHaskellのコンパイラを自由に利用できるようにする
• 他の研究者が拡張・開発することができるモジュラー基盤を提供する
• より良いコンパイラを設計・構築することができるように、現実世界のプログラムがどのように動作するかを学習する

GHCは現在、20歳以上になり、 プロジェクト開始以降、継続的に活発に開発が行われています。今日では、GHCのリリースは数十万人にダウンロードされ、Haskellライブラリのオンラインリポジトリは3000以上のパッケージを持っており、多くの学部課程でHaskellを教えるために使用され、商業的にHaskellが使われる事例も増えてきています。

GHCのその生涯の中で、GHCにいくらかのコードを貢献した人は数百人いるものの、大抵は2人または3人のアクティブな開発者がいました。GHCのメインの開発者の私達の究極の目標はコーディングよりも学術的研究を行うことだが、GHCの開発を不可欠な前提条件と考えています。 研究成果物はGHCにフィードバックされるため、GHCはこれまでのアイデアを基にしたさらなる研究の基礎として使用することができます。さらに、それを用いて製造研究成果に大きな信頼を与えるため、GHCが非常に強力な製品であることが重要です。このように、GHCには最先端の研究のアイデアのが詰まっています。一方で、それがプロダクション利用で信頼できるようにすることにもかなり多くの労力を払っています。一見矛盾した2つのゴールに多くの場合葛藤がありますが、私たちは概ね研究目的とプロダクション利用の2つを満たすパスを見つけました。

この章では、GHCのアーキテクチャの概要をお伝えし、GHCで成功している一握りのキーアイデアに焦点を当てたいと思います（まだ成功していないものも幾つか）。以下のページを通して、私達が（一般的に言って）小さな開発チームで、どのようにして巨大なソフトウェアプロジェクトを20年以上に渡り自重により崩壊させることなく管理し続けられたのか、についてみなさんが知見を得られることを望んでいます。

5.1.　Haskellとは何ですか？

Haskellとは、Haskell 2010が最新版の「Haskell Report」というドキュメントによって定義されている関数型プログラミング言語です [Mar 10]。Haskellは、関数型言語に興味を持つ学術研究コミュニティの数人のメンバーによって、彼らの調査研究の中心として用いることのできる共通言語の欠如の埋め合わせとして、1990年に創出されました。

諸プログラミング言語中、Haskellの下記2点の特徴が際立っています。

• それは純関数(purely functional)です。つまり、関数は副作用や変化するデータを持つことができません（入力（引数）のセットに対して関数は常に同じ結果を返します）。このモデルのコードについての推論をする上での利点は明らかですが(コードを書くことについても同様だと信じています)、入出力を純粋な関数の環境に結合することは重要な課題でした。幸いにも、モナドという形式のエレガントな解決策を発見されました。それは入出力を適切に純関数のコードに結合するだけではなく、新しい強力な抽象化をもたらしHaskellでのコーディングに革命を起こしました（そしてその後他の言語にも影響を与えた）。
• それは非正格(lazy)です。これは言語の評価戦略を示しています。ほとんどの言語では、関数が呼び出される前に、関数の引数が評価される正格(strict)な評価を使用しているのに反して、Haskellでは関数に評価されていない引数が渡され、必要になり次第評価されます。

Haskellはまた、強い型付を持っていて、型推論をサポートしています（これは型注釈がめったに必須にならないことを意味します）。

Haskellの完全な歴史に興味のある方は、こちらをお読みください [ HHPW07 ]。

5.2.　High-Level Structure

最も上位のレベルにおいて、GHCは、3つの個別の塊に分割することができます。

• コンパイラ自体。これは、Haskellソースコードを実行可能なマシンコードに変換することを役割とする本質的なHaskellのプログラムです。
• ブートライブラリ。GHCはコンパイラ自体が依存するライブラリを構成する為に、ブートライブラリと呼ばれるライブラリのセットを備えています。ソースツリーにこれらのライブラリを持つことは、GHCが自身をブートストラップできることを意味します。プリミティブなInt型のように、低レベルの機能を実装するため、これらのライブラリのいくつかは非常にしっかりとGHCに結合されています。Data.Mapのような他のライブラリはより高レベルであり、コンパイラに依存しません。
• ランタイム・システム（RTS）。これは、ガベージコレクションやスレッドスケジューリング、プロファイリング、例外処理を含む、コンパイルされたHaskellコードの実行に関連するすべてのタスクを処理するC言語の大規模なライブラリです。RTSはすべてのコンパイルされたHaskellのプログラムにリンクされています。RTSはGHCにとりこまれた開発成果の重要な部分であり、そこでの設計上の決定は、並行性と並列処理の効率的なサポートなどのHaskellの強みに対していくつかの責任があります。RTSについてはSection 5.5でより詳細に説明します。

実際にこれら3つの区分はGHCのソースツリーの3つのサブディレクトリーと正確に対応します（compiler と libraries , rts）。

ここでブートライブラリについての議論に多くの時間を費やすことはありません。なぜなら、それらはの大部分はアーキテクチャの観点から面白くないためです。すべての主要な設計上の決定は、コンパイラとランタイムシステムで具現化されているので、これらの二つのコンポーネントについての議論に、この章の残りを捧げます。

Code Metrics

我々が最後にGHCの行数を測定したのは1992年のこと（"The Glasgow Haskell compiler: a technical overview", JFIT technical conference digest, 1992）であり、そこからどのような変化があるのか見てみることは興味深いです。図5.1は、 GHCのコードを主要なコンポーネントごとに分割した行数の内訳です。現在の結果と1992年のものを比較してみています。

これらの図にはいくつかの注目すべき側面があります。

• 20年近くのコンパイラのノンストップな開発にもかかわらず、Haskelのコード行数は約28,000から約140,000と5倍程度にしか増加していません。私達は新しいコードを追加するとともに、コードベースを可能な限り新鮮な状態に維持できるよう、執拗にリファクタリングをしてきました。
• 幾つかの新しいコンポーネントがあるが、これらは約28,000行程度の新規の行のみを占めている。新しいコンポーネントの多くはコード生成に関するものです（各種プロセッサのネイティブコードジェネレータ、およびLLVMコードジェネレータ）。（旧"Low Level Virtual Machine"、LLVMプロジェクトには多くの異なるプロセッサをターゲットとする汎用コード・ジェネレータが含まれています。詳細についてはhttp://llvm.org/および、"The Architecture of Open Source Applications"第1巻のLLVMに関する章を参照してください。）また、対話型のインタプリタGHCiのためのインフラストラクチャについては7000行以上を追加しました。
• 単一のコンポーネントでの最大の増加はtype checkerであり、20,000以上の行が追加されています。これは、GHCを用いた最近の研究の多くは、新しい型システムの拡張になっていることを考えると驚くべきことではありません（例: GADTs [PVWW06 ]やType Families[ CKP05 ]）。
• Mainコンポーネントには多くのコードが追加されましたが、これは部分的です。なぜなら、driverと呼ばれる3000行のPerlスクリプトだったものがHaskellで書き換えられ、適切なGHCに移されたためであり、また、複数のモジュールをコンパイルするためのサポートが追加されたことも一因です。
• ランタイムシステムはわずかに成長しています。多くの新機能を積み上げて、より多くのプラットフォームに移植されたのにもかかわらず、10%程度大きくなったのみです。私たちは1997年辺りにそれを完全に書き直しました。
• 現在、GHCはGNU makeの約6,000行のコードからなる複雑なビルドシステムを持っています。それは、4回の完全な書き直しの上で成り立っています。この継続的な繰り返しはコードの量を削減しました。

The Compiler

コンパイラは３つに分割することができます。

• 複数のHaskellのソースファイルのコンパイルを担当しているcompilation manager 。コンパイルマネージャーの仕事は、異なるファイルをどの順序でコンパイルするか、 どのモジュールはコンパイルする必要が無いか（それの依存が最後のコンパイル以降変更されていないため）、を理解することです。
• 単一のHaskellソースファイルのコンパイルを処理するHaskellのコンパイラ（私たちはGHC内でHscと略しています）ご想像の通り、アクションのほとんどはここで行われます。Hscの出力は選択されているバックエンドに依存します（アセンブリ、LLVMコード、またはバイトコード）。
• HscがHaskellコードをオブジェクトコードにコンパイルするのに必要な外部プログラムを一緒に構成する責任があるpipeline 例えば、HaskellのソースファイルはHsc に流し込む前に、Cプリプロセッサで前処理が必要になる場合があります。 Hscの出力は通常アセンブリファイルであり、これはオブジェクトファイルを作るためにアセンブラに流し込む必要があります。

コンパイラはこれらの機能を実行するだけの単純さではありません。それ自体が、IDEや分析ツールなどのHaskellソースコードと共に動作する他のツールを構築するために使用できる大きなAPIを備えた ライブラリです。

Compiling Haskell Code

ほとんどのコンパイラと同様に、Haskellのソースファイルのコンパイルは、連続したフェーズで進みます。各フェーズの出力は次の段階の入力になっています。各フェーズの全体像は図5.2 に示されています。

Parsing

入力としてHaskellのソースファイルを受け取り抽象構文を出力する、伝統的な方法で構文解析を初めます。GHCでは抽象構文データ型HsSyn、はそれが含む識別子の型によってパラメーター化されます。つまり、抽象構文木はいくつかの識別子の型tのためのHsSyn t型を持っています。 これは、同じタイプの抽象構文木を再利用しながら、プログラムがコンパイラのさまざまな段階を通過するように、識別子に多くの情報を追加することを可能にしています。

parserの出力は、識別子がRdrNameと呼ばれる単純な文字列である抽象構文木です。したがって、parserによって生成された生成抽象構文はHsSyn RdrName 型を持ちます。

GHCは字句解析機と構文解析機それぞれの生成にAlexとHappyというツールを使います。これらはCでの lexとyaccに類似しています。

GHCのparserは純粋に機能的です。実際には、GHCのライブラリは、parserと呼ばれる純粋な関数を提供します。これは1つのString（と他の幾つか）を受取り、パースされた抽象構文またはエラーメッセージを返します。

Renaming

Renamingは、Haskellソースコード内のすべての識別子を完全修飾名に解決するプロセスです。同時に、スコープ外の識別子を特定し、エラーを適切に報告することができます。

Haskellでは別のモジュールからインポートした識別子を再度エクスポートすることが可能です。例えば、モジュールAでfと呼ばれる関数が定義さている場合に、モジュールBでモジュールAをインポートした上で再度f をエクスポートすることができます。ここで、モジュールCがモジュールBをインポートすると、fをB.fとして参照できるが、fのオリジナルはモジュールAで定義されています。これは、名前空間操作の有用な形態です。ライブラリは内部的に好きなモジュール構造を使用することを意味しますが、内部モジュールから識別子を再エクスポートするいくつかのインターフェイスモジュールを介してクリーンなAPIを公開しています。

しかし、コンパイラはそれをすべて解決しないといけません。そのためにソースコード上の各名前がどのようなものに対応しているかを知っている必要があります。私たちは entities間できれいに区分しました。「それら自体」(例ではA.f )、及び参照できるentitiesによる名前(例: B.f)。ソースコード中の任意の時点で、スコープ内のエンティティのセットがあり、それぞれは、1つまたは複数の異なる名前で知られています。renamerの仕事は、特定のエンティティを参照することによって、コンパイラのコードの内部表現での名前のそれぞれをリネームすることです。時々名前は、いくつかの異なるエンティティを参照することができます。それ自体ではエラーになりませんが、名前が実際に使用されている場合、renamerは曖昧性エラーのフラグを立て、プログラムをリジェクトします。

renamingは、Haskellの抽象構文（HsSyn ,RdrName）を入力とし、抽象構文（HsSyn Name ）を出力として生成します。ここでNameは特定のエンティティへの参照です。

名前の解決はrenamerの主な仕事ですが、それは他にも多すぎるタスクを実行します。

• 一緒に関数の方程式を収集し、引数の数が異なる場合は、エラーフラグを立てます。
• 演算子の結合性に応じて中置式を再配置します。
• 重複する宣言を見つける。
• 未使用の識別子へのワーニングを生成する。
• など他にも

Type Checking

想像されるように型チェックは、Haskellのプログラムの型が正しいことを確認するプロセスです。プログラムは型チェッカーを通過した場合、実行時にクラッシュしないことが保証されています。（ここでの「クラッシュ」という用語は"segmentation fault"のようなハードクラッシュを含むが、パッターンマッチングの失敗のような事は含まないという正式な定義があります。非クラッシュ保証は、外部関数インタフェースなどの特定の危険な言語機能を使用することによって破壊させることができます。）

型チェッカーに入力されるのはHsSyn Name （修飾名とHaskellソース）であり、出力はHsSyn Id です。Idは特別な情報、とりわけtype 、を持つNameです。実際に、型チェッカーによって生成されたHaskellの構文は型情報で完全に修飾されています。 すべての識別子にそれの型が付加されていて、どの部分式の型を再構築するのにも十分な情報があります（これは、例えばIDEにとって便利です）。

実際問題として、Template Haskellの機能は実行時にコードを生成するため、型チェックと名前の変更が挟み込まれることがあります。

Desugaring, and the Core language

Haskellは多くの異なる構文形式を含む、とても大きな言語です。これは人間にとって読み書きしやすいことを意図しています。 広い範囲の公文構造があり、プログラマが状況に応じて最も適切な構成を選択できる用、多大な柔軟性を与えています。しかし、この柔軟性は、同じコードを記述する場合、いくつかの方法があることがよくある事を意味します。例えば、if式は、TrueとFalseに分岐するcaseと同じ意味であり、リスト内包表記はmap や filter 、concat の呼び出しに変換することができます。実際には、Haskell言語の定義は、これらを単純な構成物に変換することで、これらの構成物を定義します。このように別の構成物に変換できる構築物は、「糖衣構文（シンタックスシュガー）」と呼ばれています。

すべてのシンタックスシュガーが取り除かれている状態は、コンパイラにとって遥かに単純です。Haskellプログラムで動作する必要がある後続の最適化パスに対処する言語が小さくなるためです。デシュガーのプロセス、つまりすべてのシンタックスシュガーを取り除くプロセスは、フルのHaskellの構文をCoreと呼ばれるはるかに小さい言語に変換することです。Coreについての詳細は後で 述べます。

Optimisation

今、プログラムはCoreとなっているので 、最適化のプロセスを初めます。GHCの大きな強みの一つは、抽象化レイヤーから離れて最適化することであり、この作業のすべてがCoreレベルで発生します。 Coreは小さな関数型言語であるが、最適化を表現するためのとてつもなく柔軟な中間物であり、正格性解析のような非常にハイレベルなものから、演算子強度低減のような非常にローレベルなものまでを範囲としています。

最適化パスのそれぞれがCoreを受取り、Core を生成します。ここでの主なパスはSimplifierと呼ばれ 、これの仕事はcorrectness-preserving transformationsの大きな集まりを適用することで、より効率的なプログラムを生成することです。これらの変換のいくつかは、精査されている値が明らかである場合のデッドコードの除去やcase式の縮小など単純で明確であり、また、関数のインライン展開や書き換え規則の適用などもっと複雑な物もあります（後に議論します ）。

単純化は通常他の６つある最適化パスの間に実行されます。それらが実際に実行される順序は、ユーザーが選択した最適化レベルに依存します。

Code Generation

一度Coreプログラムが最適化されると、コード生成のプロセスが開始します。幾つかのadministrative passesの後、コードジェネレーションが開始します。 コードは2つのルートの打ち一つを取ります。対話型インタプリタによって実行されるバイトコードに変換されるか、または最終的に機械コードに変換されるコードジェネレータに渡されます。

コードジェネレーターは最初にCoreをSTGと呼ばれる言語に変換します。これはコードジェネレータが必要とするより多くの情報を注釈したのみで、本質的には単にCoreです。そして、 STGは、明示的なスタックを備えた低レベルの命令型言語であるCmmに翻訳されます 。ここから、コードは3つのルートのいずれかを取ります。

• Native code generation ：GHCにはいくつかのプロセッサ・アーキテクチャのための簡単なネイティブコードジェネレータが含まれています。この経路は、高速であり、ほとんどの場合、合理的なコードを生成します。
• LLVM code generation ： Cmm はLLVMコードに変換され、LLVMコンパイラに渡されます。この経路はNative code generationよりも長い時間がかかるが、場合によっては著しくより良いコードを生成することができます。
• C code generation ：GHCは通常のCコードを生成することができます。このルートは、他の2つの経路よりも大幅に遅いコードを生成しますが、新しいプラットフォームへのGHCを移植するのに便利です。

5.3.　 Key Design Choices

このセクションでは、GHCで特に有効であった設計上の選択の一握りに焦点を当てます。

The Intermediate Language

静的型付け言語のコンパイラのための典型的な構造はこれです。プログラムが型をチェックされ、最適化される前に、いくつかの型付けされていない中間言語に変換されます。GHCは違います。それは静的に型付けされた中間言語を持っています。結論から言うと、この設計上の選択は、GHCの設計と開発に波及効果がありました。

GHCの中間言語はCore（実装のことを考える場合）またはSystem FC（理論を考える場合）と呼ばれています。その構文は。図5.3 で示されています。正確な詳細はここでは重要ではありません。興味のある読者はさらなる詳細を[SCPD07]で調べることができます。しかし、私たちの現在の目的のためには、以下の点が重要です。

• Haskellは非常に大規模なソースの言語です。その構文木を表すデータ型は、数百通りものコンストラクタを持っています。

  これとは対照的にCoreは 小さく、原則に基づいた、ラムダ計算です。それは非常にすくないいくつか文法の形式があり、まだ我々はへのHaskellのすべてをCore に翻訳することができます。

• Haskellは暗黙的に型付けされたソースの言語です。プログラムは、少しの方注釈を持っているかまたは持っていません。代わりに、型推論のアルゴリズムが、すべてのbinderと部分式の型を把握します。この型推論アルゴリズムは複雑であり、いくぶんその場しのぎであり、各々の実際のプログラミング言語が具現化する設計の妥協点を反映しています。

  これとは対照的にCore は明示的に型付けされた言語です。各バインダは開示的な方を持ち、Every binder has an explicit type, and terms include explicit type abstractions and applications. Coreは非常に単純で、プログラムが正しい型であることをチェックする高速な型チェックアルゴリズムを持っています。このアルゴリズムは完全に率直です。何のその場しのぎの妥協はありません。

GHCのすべての解析と最適化パスはCore の上で動作します。これは素晴らしいです。なぜなら、 Coreは最適化に対処するためのたったいくつかのケースのみを持っているような小さな言語だからです。 Coreは小さいが、極めて表現力があります。結局のところ、System Fは、元は型付き計算の基礎計算として開発されました。新しい言語機能がソース言語に追加される際（これは常に起こります）、変更はフロントエンドのみに制限され、Coreは変更されません。そしてコンパイラの殆どは変更されません。

しかしCoreはなぜ型付けされているのでしょうか？結論、型推論エンジンがソース言語を受け入れた場合、そのプログラムは恐らく正しい型を持っていて、各最適化パスは恐らく型の正当性を維持しています。 Core高速な型チェックアルゴリズムを持てますが、なぜあなたはそれを実行したいのでしょうか？そのうえ、Coreに型をつけることは重要なコストです。なぜなら各変換や最適化パスは正しい方のプログラムを生成する必要があり、そのすべての型注釈を生成する必要があることは、多くの場合些細なコストではないからです。

それにもかかわらず、いくつかの理由のために、明示的に型指定された中間言語を持つことは大きく優位性があります。

• 実行中のCoreの型チェッカー（我々はLintと呼んでいる ）は、コンパイラ自体にとって非常に強力な整合性チェックとなります。仮に、あなたが誤って、整数値を関数として扱うコードを生成する最適化を書いてしまい、それを呼び出すところを想像してみてください。チャンスは、プログラムがセグメンテーションファルトするか、奇妙な方法で実行時に失敗することです。セグファルトをトレースしプログラムを壊している特定の最適化パスを見つけることは長い道のりです。

  今度は代わりに、各最適化パスの後にLintを実行していることを想像してみてください(-dcore-lint フラグを使うと実行される)。それは問題の最適化後の正格な一のエラーをすぐに報告します。What a blessing.

  もちろん、「型の正しさ」は「正しいこと」と同じではありません： Lintはあなたが(x*1)をxにする代わりに1と最適化してしまった場合はエラーを通知しません。プログラムが Lint に合格した場合は、セグファルトなしで動作することが保証されています。 さらに実際には、型は正しいが意味的に間違っている最適化を書くことは驚くほど困難であることを私たちは発見しました。

• Haskellのための型推論アルゴリズムは非常に大きく、非常に複雑です。図5.1を見ると、型チェッカーがGHCの最大の単一コンポーネントであることが確認できます。大規模で複雑であることはエラーが発生しやすいことを意味します。しかし、 Lintは型推論エンジンに100％依存しないチェックとして機能します。型推論エンジンが、実際には型が正しくないプログラムを受け入れた場合、 Lintがそれを拒否します。ゆえに、 Lintは型推論エンジンの強力な監査役として機能します。

• Coreの存在は、ソース言語の設計についての強力な健全性のチェックでもあることが判明しています。私達のユーザーは常々彼らの好きな機能の追加を提案します。時には、これらの機能は、明らかに「シンタックスシュガー」で、既に可能なことに対する便利な新しい構文です。しかし時々それらは奥深くなり、機能がどれほど遠くにあるのかを知るのは難しいかもしれません。

  Coreは私たちにそのような機能を評価するための正確な方法を提供します。機能を容易にCoreに翻訳できる場合は、本質的な新規性はないと私達を安心させます。新しい機能はシンタックスシュガーのようです。一方、coreに拡張が必要な場合は、もっともっと慎重に考えます。

実際にCoreは信じられないぐらいステイブルでいます。20年の間で、我々はたった1つの新しい主要な機能をcoreに追加しました（具体的には、暗黙の型変換およびそれらに関連するキャスト）。同期間、ソース言語は莫大に進化してきました。私たちはこの安定性を私達の優れた才気によるものではないとしていて、Coreが基礎数学に直接結びついているという事実に起因しています。bravo Girard!

Type Checking the Source Language

興味深い設計上の決定の1つは、型検査は脱糖の前後どちらに行われるべきかどうかです。トレードオフは次のとおりです。

• 脱糖前の型チェックは、Haskellの非常に大規模な構文を直接扱う必要があるということを意味し、型チェッカーが考慮すべきケースがたくさんあります。仮に、最初に（型がない版の）Coreに脱糖した場合、型チェッカーがはるかに小さくなることが期待されます。
• 一方、脱糖後の型チェックは重要な新たな責務を発生させます。脱糖はプログラムがそれらのプログラムの方が正しいかどうかに影響しません。結局、脱糖は意図的に情報量を落としていることを意味します。これはおそらく95％の場合に問題ないが、ここに何かしら問題がある場合は、Coreの設計においていくつかの余分な情報を保持するようにいくつかの妥協を強いるでしょう。
• 最も深刻なこととして、脱糖されたプログラムの型チェックは元のプログラムのテキストに対してエラーを報告するのがはるかに困難になり、そして（ときには精巧な）脱糖されたバージョンではない。

殆どのコンパイラが脱糖後に型チェックを行います。しかしGHCにおいて、私たちは反対の選択をしました。私たちはHaskellの完全な構文に対して型チェックをします。そしてその結果を脱糖します。これは、新しい構文構造を追加する際に、複雑になるかもしれないように聞こえますが（フランス語学校に続いて）、私たちはそれを簡単にできるように型推論エンジンを簡単に構成しました。型推論は、次の2つの部分に分かれています。

1. 制約の生成：構文木を探索し、型制約のコレクションを生成します。このステップはHaskellの完全な構文を扱うが、それは非常に簡単コードであり、新しいケースを追加するのは簡単です。
2. 制約の解決：集められた制約を解決します。これは型推論エンジンの巧妙な部分ですが、これはソース言語のシンタックスから独立していて、言語が大きくても小さくても同じものです。

概して、脱糖前の型チェックという設計は大きな勝利であるということが判明しました。確かに、それは型チェッカーへのコードの追加を必要としますが、単純なコードです。これは、2つの相反した役割を同じデータ型に与えることを回避し、型推論エンジンをそれほど複雑ではなくし、変更しやすくしています。さらには、GHCのタイプエラーのメッセージはかなり良いです。

No Symbol Table

コンパイラは通常シンボルテーブルとして知られる1つ以上のデータ構造を持っています。これはシンボル(変数など)からの、それの型や、それがどこで定義されているかなどの情報へのマッピングです。

GHCでは、非常に控えめにシンボルテーブルを使用します（主にrenamerと型チェッカー内で）。可能な限り、我々は代替の戦略を使用します。変数はそれ自体に関するすべての情報を含むデータ構造です。実際、変数のデータ構造をトラバースすることによって、大量の情報に到達することができます。 変数からその型を見ることができます。型コンストラクタはデータコンストラクタを含み、型コンストラクタ自体にも型があります。たとえば、GHCのデータ型（大幅に簡略化している）を次に示します。

  data Id      = MkId Name Type
  data Type    = TyConApp TyCon [Type]
               | ....
  data TyCon   = AlgTyCon Name [DataCon]
               | ...
  data DataCon = MkDataCon Name Type ...

Id はそのType を含んでいます。Typeはいくつかの引数を適用されるかもしれません（Maybe Int等）。そのような場合は TyCon を含みます。TyCon は代数データ型とすることができます。その場合にはデータコンストラクタのリストを含みます。各DataConは、そのTypeを含み、もちろん TyCon にも同じことがいえます。等など。構造全体が高度に相互接続されています。例えば、 TyConには、TyConを含むTypeを含むDataConが含まれています。

このアプローチにはいくつかの利点と欠点があります。

• シンボルテーブル内のルックアップを必要とする多くのクエリは、シンプルなフィールドアクセスに削減でき、これは効率化やコードのクリーンさのために最適です。
• 余分なシンボルテーブルを持ち歩く必要がなく、抽象構文木にはすでに、すべての情報が含まれています。
• スペースのオーバーヘッドが優れています。同じ変数のインスタンスは同じデータ構造を共有し、テーブルのために必要なスペースはありません。
• 変数に関連付けられた情報を変更する必要がある場合のみ、困難が生じます。シンボルテーブルが優位性を持っているところです。シンボルテーブルのエントリを変更するだけですみます。GHCでは、抽象構文木を横断し、すべての古い変数のインスタンスを新しいものに変更する必要があります。各変数に関するある種の最適化関連の情報を更新する必要があるので、実際に、単純化はこれを定期的に行います。

設計のこの側面は、変化がほとんど不可能なほど基本的なところなので、シンボルテーブルを使用することが、全体的に良いか悪いかを知ることは難しいです。それでも、シンボルテーブルを回避することは純関数の背景においては自然な選択なので、このアプローチがHaskellのために良い選択である可能性は高いようです。

Inter-Module Optimisation

関数型言語は、小さな定義を書くことをプログラマに奨励します。例えば、これは標準ライブラリでの&&の定義です。

(&&) :: Bool -> Bool -> Bool
True && True = True  
_    && _    = False  

このような関数を使用する際に毎回、実際に関数呼び出しが行われているとしたら、効率はひどく悪くなります。一つの解決策は、コンパイラが特定の関数を特別に扱うようにすることです。 別の解決策は、プリプロセッサを用いて、「呼び出し」を展開されたインラインコードに置き換えることです。これらのソリューションのすべては、いずれかの方法で不満足です。特に後者の解決策は非常に明白です。 「関数をインライン化」するということは、適切にそのパラメータをインスタンス化し、関数呼び出しを関数の内容に置き換えるということを意味します。

GHCでは、このアプローチを体系的に採用しています[PM02を ]。事実上、コンパイラに何も内蔵されていません。その代わりに、ライブラリ内でできるだけ多くを定義し、オーバーヘッドを排除するために積極的なインライン化を使用します。これは、 プログラマは、GHC付属のライブラリと同じように、自身のライブラリもインライン化され最適化される用に定義できる ことを意味します。

その結果として、GHCはcross-module(実際にはcross-packageも同様に)のインライン化ができる必要があります。アイディアは単純です。

• HaskellのモジュールLib.hs をコンパイルする際、GHCは、オブジェクトコードをLib.oに、「インタフェース・ファイル」を Lib.hi に生成します。このインタフェースファイルには、Libからエクスポートされるすべての関数に関する情報が含まれていて、それにはその種類と、十分に小さな関数についてはそれらの定義、の両方を含んでいます。
• モジュールClient.hsをコンパイルするときにはLibをインポートし、GHCはインタフェースLib.hi を読み取ります。そしてClient がLib で定義されたLib.fを呼び出すのであれば、GHCはLib.f をインライン化するためにLib.hi内の情報を使うことができます。

デフォルトでは、GHCは関数が「小さい」場合にのみ、インタフェースファイル内に関数の定義を載せます（このサイズの閾値を制御するためのフラグがあります）。しかし、サイズに関係なく、呼び出し側で、積極的な定義のインライン化をする用にGHCに指示するための、INLINEプラグマをサポートしています。

foo :: Int -> Int  
{-# INLINE foo #-}
foo x = <some big expression>  

クロスモジュールのインライン化は、超効率的なライブラリを定義するための必要不可欠ですが、それはコストが付属していません。作者がライブラリをアップグレードする場合、Client.oを新しいLib.oと再リンクするだけでは十分ではありません。なぜなら、Client.oは古いLib.hsのインラインフラグメントを含んでいて、これは新しいものと互換性がないかもしれないからです。言い換えると、Lib.oのABI（Application Binary Interface）が、それのクライアントの再コンパイルが必要なように、変更されたということです。

実際に、fixedでpredictableなABIのコードを生成するためにコンパイルする唯一の方法は、ABIがクロスモジュール最適化を無効にすることであり、これはABIの互換性のために支払うのには、一般的に言って高すぎるコストです。GHCで作業するユーザーは、通常、スタック全体のソースコードを用意してますので、再コンパイルは通常は問題ありません（また、後に説明するように、パッケージシステムは、この作業モードを中心に設計されています）。しかし、再コンパイルが現実的ではないシチュエーションもあります。例えば、OSのディストリビューション内のライブラリに対してバグ修正を配布する場合などです。将来的には、私たちは、クロスモジュール最適化を可能にしつつ、ABIの互換性を保つことを可能にする解決策を見つけられることを願っています。

5.4.　Extensibility

プロジェクトの生死が、その拡張性の有無によって決まるというのは、よくあるケースです。拡張可能でないモノリシックなソフトウェアは、すべてのことができ、それを正しく行うことができる必要があります。一方で拡張可能なソフトウェアは、すべての必要な機能をすぐに使える状態で提供していなくても、役に立つ土台となりえます。

オープンソースプロジェクトは、もちろん定義によっては拡張可能です。つまり誰でもコードを取得し、自分で機能を追加できるという点です。 コードを取ると、自分自身の機能を追加することができ、誰に、定義によりコースの拡張可能です。しかし、他の誰かによってメンテナンスされているオープンソースコードを変更するというのは、ハイオーバーヘッドなアプローチと言うだけではなく、あなたの拡張機能を他に人に共有する助けとなっていません。したがって、成功したプロジェクトは、コアコードの変更を伴わない、拡張性の形態を提供する傾向があり、GHCもこの点で例外ではありません。

User-Defined Rewrite Rules

GHCのコアは、いくつかのsemantics-preserving transformationをそれぞれ実行する（CoreからCoreに）、最適化パスの長いシーケンスである。しかく、ライブラリの作者は、多くの場合、いくつかの非自明な、それ自身のドメイン固有の変換を持つ関数を定義します。それはGHCからは予測できません。そこで、GHCはライブラリ作者に、最適化中にプログラムを書き換えるのに使用されるrewrite rulesを定義できるようにしました[ PTH01 ]。このように、プログラマは、実際には、ドメイン固有の最適化とともに、GHCを拡張することができます。

一例として、foldr/build のルールは次のような式となっています。

{-# RULES "fold/build"    
    forall k z (g::forall b. (a->b->b) -> b -> b) . 
       foldr k z (build g) = g k z
 #-}

すべてのルールはプラグまであり、{-# RULES によって開始されます。このルールは、GHCが式(foldr k z (build g))を見つけたときは、いつでも、(g k z)と書き換えるように言っています。この変換は、semantics-preservingですが、これについて論じている研究論文を取るので[GLP93]、GHCがそれを自動的に適用するチャンスはありません。他のルールや幾つかのINKINEプラグマの一握りと共に、GHCはlist-transforming機能を融合することができます。例えば、(map f (map g xs))中の2つのループは一つに融合されます。

書き換え規則は、シンプルで使いやすいが、それらは非常に強力な拡張機構であることが証明されています。10年前に我々が最初にGHCにこの機能を導入したとき、我々はそれが時折便利な設備になることを期待していました。しかし、実際には、その効率性が書き換え規則に決定的に依存している、多くのライブラリで便利なものとなった。例えば、GHC自身のbaseライブラリは、100を超えるルールを含み、普及しているvectorライブラリは数十を使用しています。

Compiler Plugins

コンパイラが拡張性を提供できる為の一つの方法は、プログラマがコンパイラのパイプラインに直接挿入されるパスを記述できるようにすることです。このようなパスは多くの場合、「プラグイン」と呼ばれています。GHCは、次のような方法でプラグインをサポートしています。

• プログラマは、モジュール内にCoreからCoreへのパスを通常のHaskellの関数として書きます。例えばP.hs。そしてオブジェクトコードにコンパイルします。
• いくつかのモジュールをコンパイルするとき、プログラマは、-plugin Pコマンドラインフラグを使用しています 。（代わりに、モジュールの先頭でプラグマのフラグで指定することもできます）
• GHCはをP.oを検索し、実行されているGHCバイナリに動的にリンクして、パイプライン内の適切な時点でそれを呼び出します。

しかし、「パイプライン内の適切なポイント」とはどこですか？GHCはそれを知らないので、プラグインがその決定を行うことができます。これやその他の事項の結果として、プラグインが提供しなければならないAPIは、単一CoreへのCore関数よりも少し複雑であるが、そこまで多くはありません。

プラグインは時に、補助的なプラグイン固有のデータを必要とするか、または生成します。例えば、プラグインがモジュールがコンパイルされる際に関数ないで何らかの解析を行うとし（ M.hs とする）、その情報をインターフェースファイルM.hiないに置きたいとします。そうすると、プラグインは、M をインポートするモジュールのコンパイル時に、その情報へアクセスできます。GHCはこれをサポートするアノテーションの仕組みを提供しています。

GHCにとって、プラグインと注釈は比較的新しいものです。これらは、GHC内部のデータ構造を扱うため、書き換えルールよりも高い壁を持っているが、当然プラグインはより多くのことができます。それらがどのぐらい広く使われるかはまだわかっていません。

GHC as a Library: The GHC API

GHCの当初の目標の一つは、他の人がその上に構築することができるモジュール式の基盤であることでした。他の人達による研究プロジェクトの基礎として利用できるように、我々はGHCのコードが、わかりやすく、良くドキュメント化されていることを望みます。我々は、人々が、自身の変更をGHCに加えたり、実験的な新機能や最適化を加えうことを望んでいる想像しています。確かに、このような例がいくつかありました。例えば、LispをフロントエンドとしたGHCのバージョンや、Javaのコードを生成するGHCのバージョンが存在し、 両方の開発はGHCチームへのコンタクトは殆ど又は全く無く、完全に個別に行われました。

しかしながら、GHCの修正バージョンを生成することは、GHCのコードが再利用できる方法のほんの一部を表します。Haskell言語の人気が成長してきたように、Haskellのソースコードに通じているツールやインフラへのニーズが高まってきた。そしてもちろんのGHCは、これらのツールを構築するために必要な多くの機能が含まれています（Haskellのパーサ、抽象構文、型をようにチェッカーなど）。

これを念頭において、私たちはGHCに簡単な変更をしました。モノリシックなプログラムとしてGHCを構築するよりも、むしろ、GHCをライブラリとしてビルドし、実行可能なGHCを作るために小さなMain モジュールとリンクしています。ライブラリ形式で提供されるため、ユーザーは自身のプログラムからそれを呼び出すことができます。同時に、私たちはクライアントにGHCの機能を公開するためのAPIを構築しました。APIは、GHCバッチコンパイラとGHCiのインタラクティブな環境を実装するために十分な機能を提供しますが、それはまた、そのようなパーサとタイプチェッカーなどの個々のパスへのアクセスを提供し、これらのパスによって生成されたデータ構造を検査することを可能にします。この変更は、GHCのAPIを使用して構築された次のようなツールの広い範囲への向上を与えています：

• 文書化ツール、 Haddock、これはHaskellのソースコードを読み取り、HTMLドキュメントを生成します。
• 追加機能を持つ新しいバージョンのGHCiのフロントエンド（例えば、 ghci-haskeline）、その後GHCにマージバックされました。
• Haskellのソースコードでの高度なナビゲーションを提供するのIDE。例えば、 Leksah 。
• hint 、Haskellのソースコードのon-the-flyでの評価のためのシンプルなAPI。

The Package System

パッケージシステムは、近年のHaskell言語の利用の成長における重要な要因となっています。その主な目的は、Haskellのプログラマはお互いにコードを共有できるようにすることであり、それは拡張性の重要な側面である。パッケージシステムは、GHC自体を超えて共有コードベースを拡張します。

パッケージシステムは、コードの共有を簡単にするインフラストラクチャのさまざまな部分を体現しています。パッケージシステムをイネーブラーとして使用することで、コミュニティは共有コードを大量に構築しています。Haskellプログラマーは、単一のソースからのライブラリに頼るのではなく、コミュニティ全体が開発したライブラリを利用しています。このモデルは、他の言語でもうまく働いています。 例えばPerl用のCPAN。 Haskellが主にインタプリタで実行されるのではなくコンパイルされる言語であることはやや異なる一連の課題を提示しますが。

基本的には、パッケージシステムは、ユーザが他の人によって書かれたHaskellコードのライブラリを管理し、独自のプログラムやライブラリでそれらを使用できるようにします。Haskellのライブラリのインストールは、単一のコマンドを打つだけで簡単です。例えば。

$ cabal install zlib

これはzlibの為のコードをhttp://hackage.haskell.orgからダウンロードし、GHCを使いそれをコンパイルし、コンパイルされたコードをあなたのシステム上にインストールし（例えば、Unixシステムではあなたのホームディレクトリ）、GHCでインストールを登録します。さらにzlibがまだインストールされていない何らかのパッケージに依存しているのであれば、それらもzlib のインストールの前に、自動的にダウンロード、コンパイル、インストールされます。それは、他の人が共有したHaskellコードライブラリを動作させるすさまじくスムーズな方法です。

パッケージシステムは、１つ目のみ厳密にGHCプロジェクトの一部である、4つのコンポーネントで構成されています。

• あなたのシステムにインストールされているパッケージに関する情報についての単純なリポジトリ、を管理するパッケージデータベース。GHCは起動時にそれを参照し、どのパッケージが有効なのか、それはどこにあるのか、を知ります。
• Cabalと呼ばれるライブラリ（Common Architecture for Building Applications and Libraries） 。これは各々のパッケージをビルド・インストール・登録するための機能を実装します。
• http://hackage.haskell.orgのあるウェブサイト。これはユーザによって書かれアップロードされたパッケージをホストします。ウェブサイトはパッケージのドキュメントを自動生成し、オンラインで閲覧できます。執筆時点では、Hackageは3000以上のパッケージをホストしています。これらは、データベースライブラリ、Webフレームワーク、GUIツールキット、データ構造、およびネットワーキングなどの機能をカバーしています。
• HackageのウェブサイトとCabalライブラリを結びつけるツールcabal。それは、正しい順序で、Hackageからパッケージをダウンロードし、その依存関係を解決し、ビルド、インストールを行います。新しいパッケージもまた、コマンドラインからcabalを使用してHackageにアップロードすることができます。

これらのコンポーネントは、HaskellのコミュニティとGHCチームのメンバーが数年にわたって開発してきました。ともにオープンソース開発モデルに完璧にフィットシステムを作ります。コードを共有するか、他の人が共有しているコードを使用することに何も障壁はありません（当然、関連するライセンスを尊重している限り）。あなたは、ほんの数秒でHackageから他の誰かが書いたパッケージを見つけ出し、それを使うことができます。

Hackageは成功していて、残る問題は現在の規模になったことによるものです。例えば、ユーザーは４つの異なるデータベースフレームワークから、選択をすることに難しさを感じています。進行中の開発は、コミュニティを活用しこれらの問題を解決することを目的としています。例えば、ユーザーがパッケージについてコメントや投票をできるようにし、最も最適で人気のパッケージを見つけられるようにします。さらに、ユーザーからビルドの成否に関する情報を収集し、結果をレポートすることで、メンテナンスされていないパッケージや問題のあるパッケージを避けることを可能にします。

5.5. The Runtime System

ランタイムシステムは主にCのライブラリで、すべてのHaskellのプログラムにリンクされています。それはコンパイルされたHaskellのコードを実行するために必要なサポートインフラストラクチャを提供します。それは次の主要コンポーネントを含みます。

• メモリ管理。並列、世代別、ガベージコレクタを含みます。
• スレッドの管理とスケジューリング。
• GHCによって提供される基本操作。
• GHCiのためのバイトコードインタプリタと動的リンカ。

この節の残りの部分は、2つに分割されています。 前半は、RTSの幾つかのデザイン的な面について終点を当ます。それが成功しうまく機能することに役立ってきたと考えている面です。後半は、実践的なコーディングとインフラについて話します。これはかなり敵対的なプログラミング環境に対処するために、RTS内で作り上げられたものです。

Key Design Decisions

このセクションでは、特に成功していると考えているRTSにおける設計上の決定のうちの2つを説明します。

The Block Layer

ガベージコレクタはblock layerの上に構築されています。それはブロック単位でメモリを管理します。1ブロックは4KBの倍数です。ブロック層は、非常にシンプルなAPIを持っています。

typedef struct bdescr_ {  
    void *               start;
    struct bdescr_ *     link;
    struct generation_ * gen;   // generation
    // .. various other fields
} bdescr;

bdescr * allocGroup (int n);  
void     freeGroup  (bdescr *p);  
bdescr * Bdescr     (void *p);  // a macro  

これは、メモリを割り当て、割り当て解除のために、ガベージコレクタによって使用される唯一のAPIです。メモリのブロックはallocGroupで割り当てられ、freeGroup で解放されます。すべてのブロックは、block describerとよばれる、それに関連付けられた小さな構造体を持ちます（bdescr）。Bdescr(p)の操作は任意のアドレスpに関連付けられたblock descriptorを返します。これはp の値に基づく純粋なアドレス計算であり、少量の演算とビット操作命令にコンパイルされます。

ブロックはbdescr 内のlinkのフィールドを使用してチェーンにリンクすることができ、これがこのテクニックの新のパワーです。ガベージコレクタは、 世代など、幾つかの個別のメモリの領域を監視する必要があります。そして、それらの領域は時間とともに拡大・縮小することがあります。リンクされたブロックのリストとしてメモリ領域を表すことによって、GCは、多数の可変サイズのメモリ領域をフラットなメモリ空間に割り当てる難しさから開放されます。

ブロック層の実装は、Cのmalloc()/free() APIからよく知られているテクニックを使用しています。それは様々なサイズの空きブロックのリストを維持し、空き領域を合体します。freeGroup()とallocGroup()の操作は、O(1)であるように慎重に設計されています。

この設計の1つの主要な利点は、OSからのサポートはほんの少ししか必要なく、それゆえに移植性がとても高くなることです。ブロック層は、1 MB単位でメモリを割り当て、1 MB境界に合わせて配置する必要があります。一般的なOSのどれもがこの機能を直接提供するわけではありませんが、提供する機能の点ではそれほど難しいことはありません。GHCは、OSによって使用されるアドレス空間レイアウトの特定の詳細に依存せず、共有ライブラリやオペレーティングシステムのスレッドなど、アドレス空間の他のユーザと平和的に共存するという利点があります。

連続したメモリではなく、ブロックのチェーンを管理する点について、ブロック層には少しの複雑なコストがかかります。しかし、我々はこのコストは、フレキシビリティとポータビリティについて、見合う以上であることを見出しました。 例えば、ブロック層は並列GCを特に単純なアルゴリズムで実装することを可能にしました[MHJP08]。

Lightweight Threads and Parallelism

並行性は、特に多数の外部エージェントと同時に対話する必要のあるWebサーバーのようなアプリケーションを構築するために、非常に重要なプログラミングの抽象概念だと考えています。並行性が重要な抽象概念なのであれば、プログラマがそれを避けるほど高価であってはいけません。またはプログラマがそのコストを償却できるほど精巧な作りでないといけません。私たちは並行性は、正常に動作し、あなたが小さなタスクのためにスレッドをフォークすることを心配しなくても良いべきだと信じています。

すべてのオペレーティングシステムは完璧に正常に動作するスレッドを提供しているが、問題は、それらがあまりにも高価であるということです。典型的なOSが数千のスレッドを扱うことで努力しているのに対し、私たちは100万からのスレッドを扱いたいです。

Green Threads（または軽量スレッド、ユーザー空間スレッドとして知られる）は、OSスレッドのオーバーヘッドを回避するための周知の技術ですアイディアは、スレッドをオペレーティングシステムによってではなく、プログラム自体、またはライブラリ（私たちの場合は、RTS）によって管理させるというものです。オペレーティングシステムへのトラップが少なくて済むため、ユーザー空間のスレッドを管理するほうが安価です。

GHC RTSでは、このアイデアをフル活用します。スレッドが、追加の状態をほとんど保存する必要のない安全点にあるときにのみコンテキストスイッチが発生します。正確なGCを使用するので、スレッドのスタックは必要に応じて移動、拡張、縮小することができます。これをOSスレッドと比較すると、OSスレッドはすべてのコンテキストスイッチがプロセッサの状態全体を保存しなければならず、スタックが動かせないので、スレッドごとに大きなアドレス空間を予約する必要があります。

グリーンスレッドはOSスレッドよりもはるかに、より効率的な可能性があります、その上でなぜOSスレッドを使いたい人がいるんのでしょうか？それは3つの主要な問題にたどり着きます。

• ブロッキングと外部呼び出し。スレッドは、システム内の他のすべてのスレッドをブロックすることなく、ブロックするOS APIまたは外部ライブラリを呼び出すことができます。
• 並列処理。システム上に複数のプロセッサコアがある場合、スレッドは自動的に並列に実行される必要があります。
• 一部の外部ライブラリ（特にOpenGLといくつかのGUIライブラリ）は、スレッドローカルな状態を使用しているため、毎回同じOSスレッドから呼び出されなければならないAPIを持っています。

それらのすべてをグリーンスレッドで手配するのは困難なことがわかりました。それにもかかわらず、我々はGHCをグリーンスレッドでやり通し、3つのすべてへの解決策を見つけました。

• Haskellのスレッドが外部呼び出しを行うと、他のOSのスレッドが残っているHaskellのスレッドの実行を引き継ぎます [ MPT04 ]。OSスレッドの小さなプールは、この目的のために保持され、新しいものは要求に応じて作成されます。

• GHCのスケジューラは多くの軽量スレッドを幾つかの重たいOSスレッドに多重化します。これは透過的なM:Nスレッドモデルを実装します。典型的なNは、マシンのプロセッサコア数と同じになるように選択され、実際の並列処理が行われますが、各Haskellの軽量スレッドに対してフルのOSスレッドを持つオーバーヘッドはかかりません。

  Haskellのコードが実行されるためにはOSスレッドがCapabilityを保持していなければいけません。Capabilityとはnurserly(新しいオブジェクトが生成されるメモリ)のように、Haskellのコードの実行に必要なリソースを保持するデータ構造のこと。ある時点でただ1つのOSスレッドのみが、与えられたCapabilityを保持することができます。（我々はこれを「Haskell Execution Context」とも呼んでいるが、コード上では現在Capabilityという用語を使っています。）

• bound threadを作成するためのAPIを提供しています。これは、1つの特定のOSスレッドに結び付けられたHaskellスレッドであり、このHaskellスレッドによるすべての外部呼び出しは、そのOSスレッドによって行われることが保証されています。

したがって、大多数のケースでは、HaskellのスレッドはOSスレッドと全く同じように動作します。つまり、他のスレッドに影響を与えることなくOSコールをブロックし、マルチコアマシン上で並列実行することができます。しかし、それらは、時間と空間の両面で、より効率的なオーダーです。

しかし、この実装は、1つの問題を持っています。これには、ユーザーは時折、とりわけベンチマーク実行時に、衝突します。上で述べた通り、軽量スレッドは"safe points"でのみコンテキストスイッチを行うことで効率を引き出しています。コンパイラが安全であると示したコード上のポイント、そこでは内部状態（スタック、ヒープレジスタなど）が整理された状態にあり、ガベージコレクションが実行される可能性があります。GHCでは、メモリが割り当てられるたびに安全な点があります。ほとんどのHaskellプログラムでは、プログラムが安全な点にぶつかることなく数十以上の命令を実行することはありません。しかし、高度に最適化されたコードではメモリを割り当てることなく、多くの反復処理を行うことがありえます。これは、ベンチマーク（階乗やフィボナッチのような関数など）で頻繁に発生する傾向があります。それが実際のコードで起こることは非常に稀ではあるが、起きはします。安全なポイントがないと、スケジューラが実行されなくなり、有害な影響が生じる可能性があります。この問題を解決することは可能ですが、これらのループのパフォーマンスに影響を与えないことはありません。多くの場合、各サイクルを内部ループに保存することに注意しています。これは正に、私達が我慢しなければならない妥協かもしれない。 ￥

5.6.　Developing GHC

GHCは、20年生存する単一のプロジェクトであり、まだ革新と開発の変化の中にあります。ほとんどの場合、私たちのインフラとツールは従来のものでした。例えば、我々はバグトラッカー（Trac）とwiki(同じくTrac)、リビジョン管理にはGitを使っています。（このリビジョン管理の仕組みは、純粋な手動から始まり、CVS、それからDarcs、最終的に2010年にGitリポジトリに移行、と進展してきました）一般的ではないかもしれない幾つかの点があるので、それらを提示します。

Comments and Notes

大規模で長寿命なプロジェクトでの最も深刻な問題の一つは、技術文書を最新の状態に保つことです。私たちは銀の弾丸を持っていないが、私達をとりわけよく助けているローテクなメカニズムを提案します。それは 注釈 です。

コードを書くときには、慎重なプログラマーが精神的に「このデータ型は重要な不変性を持っている」のようなことを言う瞬間がしばしばあります。彼女は両方を満たすことはできない2つの選択に直面しています。彼女は不変性をコメントとして追加することができますが、データ型宣言が長すぎるため、コンストラクタが何であるか分かりにくいことがあります。代わりに、彼女は他の場所で不変性を文書化することもできますが、それがout of dateになるリスクがあります。20年間で、 すべてが古くなってしまいます！

このような動機から、私たちは、次のようなとても単純な規則を開発しました。

• 意味のあるサイズのコメントは、コードで差し込まれるのではなく、標準形式で見出しが付いています。

  Note [Equality-constrained types]
      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
      The type   forall ab. (a ~ [b]) => blah
      is encoded like this:

         ForAllTy (a:*) $ ForAllTy (b:*) $
         FunTy (TyConApp (~) [a, [b]]) $
         blah

• コメントが関連している箇所で、我々は注釈を参照する短いコメントを追加します。

 data Type
       = FunTy Type Type -- See Note [Equality-constrained types]

       | ...

コメントが何か興味深いことがあることを強調して、それを説明するコメントを正格に参照しています。それは些細に聞こえるが、「上記のコメントを参照してください」という以前の習慣よりも遥かに制度が向上しています。なぜなら、上記にあるたくさんのコメントのどれを意図しているか明確では無いためや、数年後にはコメントが「上記」に残っていないためです（それは下記であったり全く違うところにあったりします）。

ノートを参照するコードからノート自体に進むことが可能なだけでなく、その逆も可能であり、それはしばしば有用です。さらに、コード内の複数のポイントから同じノートを参照することができます。

自動化されたサポートがないシンプルなASCII専用の技術は、私たちの生活を変えました。GHCは約800のノートを持ち、その数は毎日増えています。

How to Keep On Refactoring

GHCのコードは、10年前と同じくらい速く騒動しています。同じ期間でシステムの複雑さが何倍も増加したことは間違いありません。 私たちは以前はGHCのコード量を計測していました。いまだ、システムは管理可能な状態です。私達はこれを3つの要因によるものだとしています。

• 優れたソフトウェアエンジニアリングに勝るものはありません。コンポーネント間のAPIを可能な限り小さくすると、相互依存性がより少ないため、個々のコンポーネントの柔軟性が向上します。例えば、GHCのCore {}データ型が小さいと、Core-to-Coreパス間の結合を、それらがほぼ完全に独立しており、任意の順序で実行できる程度に、減少します。
• 強く型付けされた言語で開発することで、リファクタリングが容易になります。データ型を変更したり、関数の引数の数やデータ型を変更したりする必要があるときはいつでも、コンパイラがコードの他の場所を修正する必要があるかどうかをすぐに教えてくれます。単に、大きなクラスのエラーが静的に排除されていることを絶対に保証するだけで、特にリファクタリング時に、膨大な時間を節約できます。型システムが提供するのと同じレベルのカバレッジを手動で補う場合、いくつのテストケースになるのかは想像するのも恐ろしいです。

• 純粋に機能的な言語でプログラミングする場合、状態によるアクシデント的な依存関係を導入することは困難です。あなたが、突如、アルゴリズムの深い部分にアクセスする必要があると判断した場合に、命令型言語ではそれを必要な場所に明示的に渡していくのではなく、グローバルに参照できる状態を作るように誘惑されるかもしれません。このようにして、最終的には見えない依存関係が混じり、脆いコードとなります。純粋な関数型プログラミングでは、すべての依存関係を明確にすることを強制します。それは新しい依存関係を追加することにいくらか負の圧力をかけます。そして、より少ない依存関係は良いモジュール性であることを意味します。確かに、新しい依存関係を追加する必要がある場合、純度性は依存関係を表現するためにより多くのコードを書かせますが、私たちの見解では、コードベースの長期的な健康の為に払う価値がコストです。

  追加のメリットとして、純粋な関数型のコードは構造上スレッドセーフであり、並列化が容易な傾向があります。

Crime Doesn't Pay

成長してきたGHCの変化を振り返ると、共通の教訓が浮かび上がってきます。効率化と利便性の目的のどちらかは関係なく、純関数的ではないものは、道筋に悪影響を及ぼす傾向があります。私たちは数個の偉大な例を持っています。

• GHCは内部的に状態変更に依存するいくつかのデータ構造を使用します。一つはFastStringタイプ。それは単一のグローバルハッシュテーブルを使用します。別のはグローバルなNameCache。これはすべての外部名が固有の番号が割り当てられていることを保証します。私達がGHCの並列化に挑戦したとき（つまり、GHCをマルチプロセッサ上で並列に複数のモジュールをコンパイルできるようにすること）、それらの状態変化に基づくデータ構造が唯一の粘着点でした。我々はこれらの場所での状態変化に頼っていなかったら、GHCの並列化は、ほとんど些細な事でしたでしょう。

  実際に、プロトタイプの並列バージョンのGHCを構築しましたが、GHCは現在のところ並列コンパイルのサポートを含んでいません。しかしその主な理由は、これらの変更可能なデータ構造をスレッドセーフにするために必要な労力にまだ投資していないからです。

• GHCの動作は、コマンドラインフラグによって大きく左右されます。これらのコマンドラインフラグはGHCの実行で与えられた定数で定義されているので、GHCの初期のバージョンでは、これらのフラグの値をトップレベルの定数として利用できました。たとえば、Bool型の最上位の値opt_GlasgowExtsがありました。この値は、特定の言語拡張を有効にするかどうかを決定します。トップレベルの定数は、それらの値をアクセスする必要のあるすべてのコードに明示的に引数として渡す必要がないため、非常に便利です。

  もちろん、これらのオプションは実行時に変更されるため、実際には定数ではありません。opt_GlasgowExtsの定義ではunsafePerformIOを呼び出す必要があります。それが副作用を隠すためです。それにもかかわらず、このトリックは、値が任意の実行内で一定であるため、通常、「十分に安全」とみなされます。 たとえば、コンパイラの最適化を無効にしません。

  しかし、後にGHCは、単一モジュールコンパイラからマルチモジュールコンパイラに拡張されました。この時点で、異なるモジュールをコンパイルするときにフラグが異なる値を持つ可能性があるため、フラグのトップレベル定数を使用するトリックが壊れました。そこで、フラグを明示的に渡すために大量のコードをリファクタリングする必要がありました。

  もしかしたら、あなたは命令型言語で自然なように、最初にフラグを状態として扱うことで問題を回避できたと主張するかもしれません。これはある程度真実ですが、純関数的なコードには他の多くの利点がありますが、不変なデータ構造によってフラグを表すことは、結果的にコードが既にスレッドセーフであり、修正なしで並列に実行されることを意味します。

Developing the RTS

GHCのランタイムシステムは、多くの点で、コンパイラとはかなり対照的です。ランタイムシステムは、HaskellではなくCで書かれているという明確な違いもありますが、異なる設計思想を生み出すRTSへの特有の考慮事項もあります。

1. すべてのHaskellプログラムはRTSでコードを実行するのに多くの時間を費やしています。20〜30％は典型的ですが、Haskellプログラムの特徴によってが大きく異なるため、この範囲より上下することも一般的です。RTSを最適化することによって節約される各サイクルは何度も何度も乗算されるので、これらのサイクルを節約するために多くの時間と労力を費やす価値があります。
2. ランタイムシステムは静的にすべてのHaskellのプログラムにリンクされているので（動的リンクが使用されない限り）、それを小さく維持する動機があります。

3. ランタイムシステムでのバグは、多くの場合、ユーザにとって不可解であり（"segmentation fault"等）、解決することは困難です。たとえば、ガベージコレクタのバグは、特定の言語機能の使用に結びつかない傾向があるが、いくつかの複雑な要因の組み合わせが実行時に現れる場合に発生します。さらに、この種のバグは非決定的（一部の実行でのみ発生する）かつ、とてもセンシティブ（プログラムの僅かな変更でバグが再現しなくなる）になる傾向があります。ランタイムシステムのマルチスレッド版のバグは、さらに大きな課題を提示します。したがって、これらのバグを予防することや、それらを簡単に確認できるインフラを構築することには、特別な期間を費やすことは価値があります。

   RTSバグの症状は、多くの場合、他の2つの障害と区別がつきません。ハードウェアの障害、これはあなたが思っているより一般的かもしれません。または、FFI(Foreign Function Interface)のような安全でないHaskellの機能の仕様に誤りがある場合。実行時のクラッシュを診断する最初の仕事は、これら他の二つの原因を除外することです。

4. RTSは、いくつかの異なるアーキテクチャとオペレーティングシステム上で実行される低レベルのコードであり、それは定期的に新しいアーキテクチャに移植されます。移植性は重要です。

すべてのサイクル、すべてのバイトが重要ですが、正当性はなおさらです。また、ランタイムシステムによって実行されるタスクは、本質的に複雑であるため、正当性で始まるのは難しいです。これらを両立することは、いくつかの興味深い守備技術を私たちに導き出させます。これについて次のセクションで説明します。

Coping With Complexity

RTSは、複雑で不利なプログラミング環境です。コンパイラとは対照的に、RTSは殆ど型安全性がありません。実際、他のほとんどのCプログラムよりも型の安全性が低くなっています。それは、Haskellレベルの型で、Cレベルでは存在しない型を持つデータ構造を管理するためです。例えば、RTSは、cons cellの末尾が指し示すオブジェクトが[]を指しているのか、別のconsを指しているのかを知りません。この情報は単にCレベルには存在しません。また、Haskellのコードをコンパイルするプロセスは、型を消去し、私たちはcons cellの末尾がリストであるとRTSに告げたとしても、それはまだcons cellの先頭へのポインタについての情報を持っていないだろう。故に、RTSコードはCのポインタ型のキャストの多くを行う必要があり、それはCコンパイラから型安全性についてほんの少しの助けしか得られません。

この戦いでの私たちの最初の武器は、RTSにコードを入れないようにすることです。可能な限り、我々はRTSへは最小限の機能を入れ、Haskellのライブラリに残りを書きます。これはめったに悪くはない。 HaskellのコードはCよりはるかに堅牢で簡潔であり、通常はパフォーマンスも完全に受け入れられます。多くの場合、それが合理的に明らかであるが、どこに行を追加すべきか、正確に科学的ではありません。例えば、Haskellでガベージコレクタを実装することは理論的には可能かもしれませんが、実際にはそれは極めて難しい。なぜなら、Haskellはプログラマがメモリ割り当てを正確に制御できないため、この種の低レベルなタスクをCに落とすことは、実践的な判断です。

Haskellでは（簡単に）実装することはできない多くの機能があり、RTSにコードを書くことは楽しいことではありません。次のセクションでは、RTSにおいて複雑さと正確性を管理する1つの側面に焦点を当てます。不変条件を維持する。

Invariants, and Checking Them

RTSは不変条件で満たされています。それらの多くはささいで簡単にチェックできます。たとえば、キューの先頭へのポインタがNULLの場合、末尾へのポインタもNULLにする必要があります。 RTSのコードには、このようなチェックをするためのアサーションが散りばめられています。アサーションは、バグが現れる前に発見するためのツールです。 実際、新しい不変条件が追加される際、不変条件を実装するコードを書く前にアサーションを追加することがよくあります。

ランタイムの不変条件の中には、満たすことや確認することがはるかに難しいものがあります。この手の不変条件のうち、他よりも多くのRTSに広がっているのは、次のとおりです。ヒープはダングリングポインタを持っていない

ダングリングポインタは容易に発生し、コンパイラとRTS自体の両方がこの不変条件を破壊することができる多くの場所があります。コードジェネレータは、無効なヒープオブジェクトを作成するコードを生成する可能性があります。 ガベージコレクタは、ヒープをスキャンするときにオブジェクトのポインタを更新するのを忘れるかもしれません。この種のバグを追跡することは、非常に時間がかかることがあります（しかしながら、著者の好きなアクティビティの一つです！）。それは、プログラムが実際にクラッシュするまでに、ダングリングポインタが発生した場所から、実行が進んでしまっているためです。利用可能なデバッグツールがありますが、プログラムを逆順で実行するのは得意では無い傾向があります。（ただし、最近のGDBとMicrosoft Visual Studioデバッガでは、いくつかの逆実行をサポートしています）。

一般的な原理は、 プログラムがクラッシュしようとしている場合、それは、可能な限り、すぐに、うるさく、頻繁に、クラッシュすべきである。 （この引用は、GHCコーディングスタイルのガイドラインに由来し、もともとRTSの初期バージョンで作業していたAlastair Reidによって書かれました）。

問題は、「ダングリングポインタでない不変式」を定数時間内のアサーションでチェックできないということです。それをチェックするアサーションは、ヒープの完全な走査を行う必要があります！明らかに、すべてのヒープの割当のたびに、またはGCがオブジェクトをスキャンするたびに、このアサーションを実行することはできません（実際には、メモリが解放されるまで、ダングリングポインタはGCの最後まで現れないため、これも十分ではありません）。

そこで、RTSデバッグは、我々がsanity checkingと呼ぶオプションのモードがあります。sanity checkingは、高価なアサーションのすべての種類を有効にし、プログラムをよりゆっくりと何度も実行することができます。具体的には、sanity checkingは、すべてのGCの前後に、(主に)ダングリングポインタをチェックするために、ヒープの完全スキャンを実行します。ランタイムクラッシュを調査するときに最初にスべきことは、sanity checkingをオンにしてプログラムを実行することです。 プログラムが実際にクラッシュする前に不変式の違反を捕捉することがあります。

5.7. Conclusion

GHCは20年の間で著者の生活のかなりの部分を消費してきました。GHCはHaskellの唯一の実装ではありませんが、何十万人もの人が実際の作業を行うために常用している唯一のものです。ハスケルが以外な場所で使われた時に、私たちはいつも驚いています。 最近の例の1つは、Haskellがゴミトラックのシステムを制御するために使用されていることです。

多くの人にとってHaskellとGHCは同義です。それは全く意図していなかったことであり、実際のいろいろな場合において、標準に対してただひとつの実装を持つことは逆効果です。しかし、実際のところ、プログラミング言語の優れた実装を維持することは大きな仕事です。GHCの、「標準をサポートし、各言語拡張は明確に区切る取り組み」によって、より多くの実装が出現し、パッケージシステムやその他のインフラと統合できるようになることを願っています。競争はすべての人にとって良いことです！

私達の研究の一環としてGHCを開発し、オープンソースとして配布する機会を与えてくださったMicrosoftにとりわけの感謝を捧げます。

This work is made available under the Creative Commons Attribution 3.0 Unported license. Please see the full description of the license for details.

Back to top
Back to The Architecture of Open Source Applications.