master-q/History-of-Ajhc-Haskell-compiler.md

## History-of-Ajhc-Haskell-compiler.md

      
    Raw
  

              History-of-Ajhc-Haskell-compiler.md
            
          
    \Chapter{めたせぴ☆ふぁうんでーしょん}{@master_q}
はじまり

\def\slimdakuten{{\kern-0.5ex}゛{\kern-1.5ex}}
西暦2013年。凶の年。
ソフトウェアエンジニアの多くはWebの世界に住んでいた。
じゃう\slimdakuten ぁすくりぷと、あんどろいどじゃう\slimdakuten ぁ 、
おぶじぇくとしー、しーしゃーぷ。高機能な言語と環境をあやつり、彼等は栄
華をきわめていた。きらびやかなUI、きらびやかな通信。またある人々はしー
げんごとしーぷらすぷらすをあやつり、匠の技で複雑なハードウェアをあやつ
り、複雑多機能なうぇぶぶらうざを作り、そしてそれらを支えるオペレーティ
ングシステムりなっくすを作っていた。
しかしぼくらは幸か不幸かそのどちらでもなかった。
オープンソースのソフトウェアを使って組み込みデバイスを作っていたのだ。
世間からは考えられないほど古いバージョンのオープンソースを使い、
世間からは考えられないほど汚れたソースコードを弄り、
そして世間からは考えらない奇妙なデバイスの集合を組み合わせていた。
それだけならまだよいのだが悲しいことに作った製品への世間からの評価は低かった。
ぼくらの中にはこの製品化の渦に飲み込まれて息絶える者もいた。
そうして生き延びたぼくたちは現実から逃避するようにインドネシアに逃げのびた。
もう設計などしたくはなかったのだ。
自然豊かなこの国で、ぼくたちは安らぎ、ソフトウェアのことなど忘れかけていた。
それでも組み込みシステムへの想いは捨てきれず、
何か改善する手はないかと失われたテクノロジ 型システム を学び会得していた。
しかし祖国を離れてまともな仕事がある訳もなく、
先進国向けのWebサービスを作るアルバイトで食い繋いでいた。
もはや組み込みの民はこのまま消えゆくしかないのか……
そう思いかけたとき…… \newline
「ワシが めたせぴ☆ でゲソ!」 \newline
どこからともなく静かだが力強い声が響いた。 \newline
「これからおぬし達は一本の糸をたどることになるでゲソ。
この糸は古えのテクノロジー 型システム によって綿密に計算/予測された運命なのでゲソ!」 \newline
なにかわからないが、安心とやはり不安がいりまじって混乱する。
この娘はいったい何を言っているのだ？ \newline
「今おぬし達を囲んでいる状況はよくわかっているでゲソ。
増えるカスタムシステムコール。多種のデバイス。崩壊しつつある旧来のCPUアーキティクチャ。
POSIX API上に構築された複雑なミドルウェア。絶え間ない製品リリース。
猛進進化する型付けされていないオープンソースソフトウェアへの追従」 \newline
この娘は何者だろう？しかし、そうだ。その通りだ…… \newline
「そしておぬし達は今、型システムを手にしている。
それがおぬし達だけが持つ特性、もしくは力じゃなイカ？
それならこれから取るべき道はあまりにもわかりきっているでゲソ!!!」 \newline
そう言うと、めたせぴ☆と名乗る娘は消えてしまった。
……あれは夢だったのか？今となってはぼくたちにもわからない。
レストランにて

ぼくたちはちょっと贅沢をして海辺のレストランに来ていた。
いつも作っているWebサービスではない別の話をしたくなったのだ。
さっきの娘にそそのかされたわけじゃない、ほんの気晴らし。
それでもぼくたちの話題はいつも組み込みシステムに向いた。
あの頃ぼくたちを苦しめていた問題の根っこは何だったのだろう？
製品開発において最も重要なのは不具合の解消だ。
不具合の解消方法には根本対策と暫定対策がある。
根本的に対策できれば100点満点だが、工数の関係上たいていの対策は暫定策に終わる。
暫定対策を施しても似た不具合が将来必ず起きることになる。
不具合の根本原因を放置しておくと長い時間をかけて毒が体全体にまわり、
そしてプロジェクトそのものが死ぬのだ。
ぼくらは先輩からこの法則を何度も教えれられ、そして痛いほど体で味わっていた。
だからぼくらが集まるといつも"組み込みシステムの持つ不具合の根本対策"に話題が向くのだった。
レストランでの話し合いは長時間にわたり、そしてぼくらは誰しもが落ちつく結論に辿りついた。 \newline
「やはり最も大きな不具合は実行時エラーの増加なんだ」 \newline
そうこの結論には誰だって辿りつく。
実行時エラーを減らすために色々な手法が提案されているのがその証拠だ。
UMLによる設計もそうだろう。モデル駆動型アーキテクチャもそうだろう。
契約プログラミングもそうだろう。
でもぼくたちがいた大規模組込開発のドメインで、
それらが特効薬になったという話は聞いたことがなかった。 \newline
「努力目標は機能しない」 \newline
だれかがそう言った。
ぼくらは型推論を知っていた。
具体的な理論はよくわからないが、
実行時エラーの一部を魔法のようにコンパイル時に知ることができた。
ぼくらはこの特性が気に入って、日々のWebサービスの開発にも使っていた。 \newline
「どうしてkernelドメインで型による設計が使えないんだろう？」 \newline
まただれかがボソっとつぶやいた。
ぼくらはUNIXライクkernelをカスタマイズ/メンテするチームだった。
そのkernelを使うプロジェクトは10年以上も続いていた。
(国を逃がれた今、そのプロジェクトがどうなったのかはわからない) \newline
「型でkernelを書くプロジェクトはたくさんある
^["Haskell/OCaml製のOSって何があるんでゲソ？" \hrefT{http://metasepi.org/posts/2012-08-18-haskell-or-ocaml-os.html} ] みたいだよ。
OCamlでkernelを書くとか手堅い選択肢かもしれないよ？」 \newline
「うん、ぼくもソース読んでみたさ。でもこれはオモチャkernelだよ。
割り込みはポーリングで拾っているしバスドライバさえない。移植性は皆無だ。
このkernelを拡張していっても、かつてぼくらがいたドメインで使えるようにはならないよ」 \newline
ちょっとビンタン ^[インドネシア定番のビール \hrefT{http://www.multibintang.co.id/}]
を飲みすぎたみたいだ。
ぼんやりする頭を海からの風がすぎる。
ぼくらのレストランでの会合はいつもこんな感じだ。この国はいい。こうやってぼんやりと昔話をして過ぎる時間。
もういいじゃないか。そんなばかでかい問題。もう、ぼくらの知ったことじゃないよ。
でも今日はいつもと少し違っていた。 \newline
「いきなりスクラッチから書くのが無理なんじゃないか？」 \newline
いつもの話題がもう一つ先に進んだのだ。 \newline
「UNIXライクkernelはもう世界に浸透しきってしまった。
いまさら新しいインターフェイスのkernelがすぐに受け入れられるとは思えない。
それなら型によるkernel設計も自然にUNIXライクkernelを目指すべきなんじゃないかな」 \newline
正直ぼくらはPOSIXインターフェイスにもうお腹いっぱい ^[参考: "Copilotへの希望と絶望の相転移" \hrefT{http://www.paraiso-lang.org/ikmsm/books/c81.html} ] だった。
しかしkernelは所詮ただのkernel。使ってくれる人がいなければゴミ同然だ。 \newline
「kernelの品質維持のためにドッグフード
^[闘うプログラマー \hrefT{http://www.amazon.co.jp/dp/4822247570}]
が有効なことはもう20世紀に結論が出ている。
ドッグフードを行なうにしてもPOSIXインターフェイスがなければ今使っているプログラムのほとんどが使えない」 \newline
ドッグフードというのは"自分達の開発したソフトウェアを使って自分達のソフトウェアを作る"
という意味だ。
この開発手法は単純で自社製品の品質維持に効果的だ。
というのも品質が維持できなければ開発行為自体に大きく影響するからだ。
ドッグフード開発されていないために品質が悪化する例としては、
社内部門が作った使いにくい社内ツールがイメージしやすい。
社内部門が自分達が使わないソフトウェアを開発して、それ以外の全社員が使うことがある。
このような会社はソフトウェアに対する理解が浅いと言えるかもしれない。
\begin{wrapfigure}[15]{r}{90mm}
\includegraphics[width=90mm]{figure/masterq/need_unixlike_kern.eps}
\caption{POSIX APIを採用することでOS開発の工数を削減}
\label{fig:use_posix_api}
\end{wrapfigure}
\noindent 「試しにPOSIXインターフェイスでない独自APIのkernelを作ってドッグフード可能になるまでの道のりを考えてみようよ」 \newline
「そうだなぁ、ドッグフード可能にするためにはkernelをコンパイルするコンパイラとその他日々使う最低限のソフトウェア全部を作り込まなければならないはめになるよ(図 \ref{fig:use_posix_api} )。
でも、もしPOSIXインターフェイスをまずは採用すれば既存のGCCコンパイラやFirefoxのようなWebブラウザも比較的容易に移植できる。
だから新しいkernelを作り込むことに集中できると思う。
もしそのkernelが安定動作するようになれば、POSIXではない新しいインターフェイスをドッグフードの開始後にゆっくり作り込むことに後から挑戦することだってできるじゃないか」
\begin{wrapfigure}[14]{r}{90mm}
\includegraphics[width=90mm]{figure/masterq/2012-12-27-arafura_design.eps}
\caption{スナッチ設計: 既存kernelを少しずつ設計置換}
\label{fig:snatch}
\end{wrapfigure}
\noindent 「それなら スナッチ
^[コナミのゲームであるスナッチャー \hrefT{http://en.wikipedia.org/wiki/Snatcher} から]
すればいいんじゃない？」 \newline
耳慣れない用語だ。 \newline
「アイデアレベルだけど、既存のC言語で設計されたkernelを関数単位かモジュール単位で強い型を持つ言語で置換すればいいんじゃないかな」 \newline
砂の上に図を描きはじめた(図 \ref{fig:snatch} )。
ぼくらの中には一人だけいつも非現実的なアイデアばかりを主張するやつがいる。 \newline
「そんな簡単に言うけど可能なのかな？この図のモデル
……ああ、めんどうだから以後 スナッチ設計 と呼ぼう、
このスナッチ設計を実現するためには"相応のコンパイラ"と
"POSIXインターフェイスがなくても動くランタイム"が必要になるけれど、
そんなコンパイラ実在するのかい？
OCamlを使うにしてもランタイムをずっとスリムにしなきゃいけない。
それから割り込みベースで動作しているUNIXライクkernelをスナッチするのであれば、
割り込みコンテキストを扱う方法も考えないと……」 \newline
また壁だ。いつもこの話題はどこかで大きな壁にはばまれる。 \newline
「ごめん、ちょっと酔ったみたいだ。散歩に行ってくるよ」 \newline
ぼくは一足早めにレストランを出ることにした。
砂の中

家に帰らずにぼくはまだ暗い海岸にいた。
あれ？暗闇にさっきの娘が見えるような。名前は……なんだっけ。 \newline
「めたせぴ☆でゲソ! いいかげん覚えてほしいでゲソ」 \newline
元気の良い声が場違いに響き渡った。 \newline
「なにを悩んでいるんでゲソ？さぁワシに話してみるが良いでゲソ」 \newline
ニヤニヤ笑いが癪に障る。 \newline
「おぬしの思っていることは全部お見通しでゲソ!
どうやら自分の使いやすいコンパイラがどっかに落ちてないか砂の中を探しているようじゃなイカ？
すでに小さなバイナリを吐く型推論を持つコンパイラに出会っているのに、
おぬしはそのコンパイラが最適解なのか悩んでいるようでゲソ。
しかし最適解を探しているだけではいたずらに時間が過ぎるだけということも理解しているはずじゃなイカ？」 \newline
いや心配しているのはそこじゃないんだ。 \newline
「曳光弾とプロトタイプ
^[達人プログラマー \hrefT{http://www.amazon.co.jp/dp/4894712741}]
でゲソ」 \newline
うん？ \newline
「自分が作っているものが製品化できるのか、それとも単に実証実験にのみ使っていずれ捨てるのか、
作る前にあらかじめその決断をしておけば、どんなコードも無駄にはならないんでゲソ」 \newline
プロトタイプはわかるんだけど……曳光弾ってなんだろう？ \newline
「おぬしはあまり本を読まないようでゲソ。
曳光弾は"射撃後飛んでいく間に発光することで軌跡がわかるようになっている弾丸"
のことでゲソ。おぬしは今、暗闇のなかにいるんじゃなイカ？進む方角さえわからないでゲソ。
もっと言えば本当に解が存在するかさえ不安なんじゃなイカ？
そんな時、おぬしが取り得る選択肢は二つしかないのでゲソ。
プロトタイプは要求から製品に近いものをでっちあげる作業でゲソ。当然品質は劣悪なものになるはずでゲソ。これでは最終的な製品にはならない、けれど方角はわかるかもしれないでゲソ。
曳光弾はプロトタイプとは違い、しっかりとした品質のソフトウェア部品を作る行為でゲソ。
この曳光弾は運がよければ製品に搭載できるかもしれないでゲソ。
品質が確保できているからじゃなイカ。
ただしもちろん運わるく製品の方向性とは見当違いの部品かもしれないでゲソね。
それでも曳光弾を作ることによって、その近傍にあるモノが暗闇の中で少しだけ見えるはずでゲソ。
それもまた前進と言えるんじゃなイカ？」 \newline
ややこしいな……えっとこの場合は？ \newline
「かんたんじゃなイカ。コンパイラが曳光弾。その他のコード全てはプロトタイプにすぎないんでゲソ」 \newline
よく言いきれるな…… \newline
「固く考えることはないでゲソ。曳光弾とは言っても好きなコンパイラをベースにすればいいんでゲソ。
どーせどのコンパイラを選んだにしても不足した機能を追加しなければならないことには変わりがないのでゲソ。
この間おぬしはコンパイラを物色していたんじゃなイカ？」
そう、あの時はjhc ^[Jhc Haskell Compiler \hrefT{http://repetae.net/computer/jhc/}]
が組み込み開発にとても良い特性を持っていた。
コンパイラが組み込みに向いているかどうかは三つの指標を比較すればだいたい見当がつく。
A.  バイナリサイズ
B.  未定義シンボル数
C.  依存ライブラリ数
Aに関しては自明だ。組み込み開発では使えるメモリ領域が限られていることがある。
もちろんスワップなど使えない。プログラムのサイズは小さいにこしたことはないのだ。
Cに関しても比較的理解しやすい。
プログラムが別のライブラリに依存している場合にはPOSIX APIのない世界にそのライブラリもろとも移植しなくてはならなくなる。
それでももしかするとプログラム自体を変更すればライブラリ依存を削除できる可能性はある。
Bは少しわかりにくい。プログラムバイナリがあるライブラリへの未定義シンボルを多く持つということは、
そのライブラリへの依存度が高いということだ。
ということはプログラム本体へ修正をほどこしても、
その依存度が強いライブラリへの癒着はほどけない可能性が高くなる。
つまりA,B,Cの値それぞれが小さければ小さいほどPOSIXの外の世界への移植度が高いことになるのだった。
いくつかの型推論を持つコンパイラについて、三つの指標の値を調査して表にまとめてみよう。
\begin{longtable}[c]{@{}llll@{}}
\hline\noalign{\medskip}
\begin{minipage}[b]{0.22\columnwidth}\raggedright
コンパイラ
\end{minipage} & \begin{minipage}[b]{0.26\columnwidth}\raggedright
バイナリサイズ (byte)
\end{minipage} & \begin{minipage}[b]{0.25\columnwidth}\raggedright
未定義シンボル数
\end{minipage} & \begin{minipage}[b]{0.26\columnwidth}\raggedright
依存ライブラリ数
\end{minipage}
\\noalign{\medskip}
\hline\noalign{\medskip}
\begin{minipage}[t]{0.22\columnwidth}\raggedright
GHC-7.4.1
\end{minipage} & \begin{minipage}[t]{0.26\columnwidth}\raggedright
\begin{verbatim}
797228
\end{verbatim}
\end{minipage} & \begin{minipage}[t]{0.25\columnwidth}\raggedright
\begin{verbatim}
144
\end{verbatim}
\end{minipage} & \begin{minipage}[t]{0.26\columnwidth}\raggedright
\begin{verbatim}
9
\end{verbatim}
\end{minipage}
\\noalign{\medskip}
\begin{minipage}[t]{0.22\columnwidth}\raggedright
SML#-1.2.0
\end{minipage} & \begin{minipage}[t]{0.26\columnwidth}\raggedright
\begin{verbatim}
813460
\end{verbatim}
\end{minipage} & \begin{minipage}[t]{0.25\columnwidth}\raggedright
\begin{verbatim}
134
\end{verbatim}
\end{minipage} & \begin{minipage}[t]{0.26\columnwidth}\raggedright
\begin{verbatim}
7
\end{verbatim}
\end{minipage}
\\noalign{\medskip}
\begin{minipage}[t]{0.22\columnwidth}\raggedright
OCaml-4.00.1
\end{minipage} & \begin{minipage}[t]{0.26\columnwidth}\raggedright
\begin{verbatim}
183348
\end{verbatim}
\end{minipage} & \begin{minipage}[t]{0.25\columnwidth}\raggedright
\begin{verbatim}
84
\end{verbatim}
\end{minipage} & \begin{minipage}[t]{0.26\columnwidth}\raggedright
\begin{verbatim}
5
\end{verbatim}
\end{minipage}
\\noalign{\medskip}
\begin{minipage}[t]{0.22\columnwidth}\raggedright
MLton-20100608
\end{minipage} & \begin{minipage}[t]{0.26\columnwidth}\raggedright
\begin{verbatim}
170061
\end{verbatim}
\end{minipage} & \begin{minipage}[t]{0.25\columnwidth}\raggedright
\begin{verbatim}
71
\end{verbatim}
\end{minipage} & \begin{minipage}[t]{0.26\columnwidth}\raggedright
\begin{verbatim}
5
\end{verbatim}
\end{minipage}
\\noalign{\medskip}
\begin{minipage}[t]{0.22\columnwidth}\raggedright
jhc-0.8.0
\end{minipage} & \begin{minipage}[t]{0.26\columnwidth}\raggedright
\begin{verbatim}
21248
\end{verbatim}
\end{minipage} & \begin{minipage}[t]{0.25\columnwidth}\raggedright
\begin{verbatim}
20
\end{verbatim}
\end{minipage} & \begin{minipage}[t]{0.26\columnwidth}\raggedright
\begin{verbatim}
3
\end{verbatim}
\end{minipage}
\\noalign{\medskip}
\hline
\noalign{\medskip}
\caption{``hoge''と印字するプログラムに見るコンパイラの特性}
\end{longtable}
この表を見るかぎりjhcは小さなバイナリを吐き、さらにはPOSIXインターフェイスへの依存度も低い。
そのためkernelドメインにランタイムを移植する工数も少なく済みそうだ。
ここまではわかっている。 \newline
「ベースにするコンパイラは決まったようでゲソね。
あとはプロトタイピングを繰り返して、コンパイラに不足している機能を燻り出せばいいんじゃなイカ」 \newline
そうはいっても適切な題材が思い付かない…… \newline
「絵を描く前には白いキャンバスにスケッチをするものでゲソ」 \newline
そう言うとまたあの娘は消えてしまった。
最初のスケッチ: POSIXからの脱出

POSIX上で動いているプログラムとPOSIXの外で動くプログラムとの違いとはなんなのだろう (図 \ref{fig:posix_inout} ) 。
\begin{wrapfigure}[15]{r}{90mm}
\includegraphics[width=90mm]{figure/masterq/posix_inout.eps}
\caption{POSIX内と外のHaskellプログラムの想像イメージ}
\label{fig:posix_inout}
\end{wrapfigure}
POSIX上で動作するHaskellプログラムの内部は大きく二つの部分にわかれている。
Haskellコード由来の部分とランタイム由来の部分だ。
Haskellコードはどのような外部APIにも依存していないハズだ。FFIなどを使わなければだけれど。
Haskellコードはランタイムのみに依存している。
さらにそのランタイムは外部のライブラリに依存しているはずだ。
libcだけか、libpthreadもか、とにかくなにかのライブラリ依存があるはずだ。
そうでなれば副作用を実現できないからだ。
そのライブラリ群は最終的にはPOSIX APIにいきつく。
そのAPIを実現しているのはlibcとkernelのセットだ。
さてこのHaskellプログラムをPOSIX APIのない生のハードウェアが見える世界に移植するにはどうしたら良いのだろう？
ランタイムが依存するPOSIX APIのみをカバーする最低限のコードを用意すればいい。
"最低限のコード"。それがHaskellプログラムを動作させるために必要なHaskellで書けない部分、
プリミティブだということになる。
ぼくはそんなプログラムを作る練習になる題材を探してみることにした。
調査

ぼくは9セルバッテリを付けたThinkPad
^[今回対象とする実行環境はDebian GNU/Linux amd64 sid 2013/06/10時点。
GHCのバージョンは7.6.3。] を開いた。
ディスプレイから無機質なxmonadのタイルが目に入る。
ぼくらは以前NetBSD kernelを製品開発に採用していた。
その頃のクセがまだ残っていて、
ぼくのPCにはNetBSDのソースコードリポジトリを丸ごとrsync
^["Linux上でのNetBSDバーチャル開発の方法" \hrefT{http://d.masterq.net/?date=20110207#p01}] してあった。
ネットワークが不通になっても開発できるようにするのが先進国の外での常識だ ^[筆者は東日本大震災後にこの開発スタイルを取るようになったようでゲソ。] 。
jhcで実験的なアプリケーションを作る方針を決めたは良いが、現時点では重大な制約がある。
それはjhcの吐くバイナリが再入可能ではないということだ。
jhcの吐くバイナリはコンテキストを一つしか持てない。もちろんスレッドも扱えない。
つまり、jhcではハードウェア割り込みを前提としたkernelを書くことは出来ないことになる。
しかし何かkernelに近いところの題材が欲しい。
NetBSDのソースコードツリーを探していたら格好の題材がすぐ見つかった。bootloaderだ。
NetBSD bootloaderは起動するとキーボード入力を待つ。
この待ちがタイムアウトするとNetBSD kernelが自動的に起動されるのだが、
タイムアウト前に何かキーを入力するとbootloaderは独自のコマンドラインを起動する。
NetBSD bootloaderのコマンドラインを起動して、
helpコマンドを実行してみた結果が以下のログだ。
>> NetBSD/x86 BIOS Boot, Revision 5.9 (from NetBSD 6.0.0_PATCH)
>> Memory: 639/130048 k
Press return to boot now, any other key for boot menu
booting cd0a:netbsd - starting in 0 seconds.
> help
commands are:
boot [xdNx:][filename] [-12acdqsvxz]
     (ex. "hd0a:netbsd.old -s"
--snip--
help|?
quit
>

\begin{wrapfigure}[13]{r}{80mm}
\includegraphics[width=80mm]{figure/masterq/bootloader_nointr.eps}
\caption{bootloaderは割り込み禁止で実行される}
\label{fig:boot_nointr}
\end{wrapfigure}
このコマンドラインからbootコマンドを使えば、ファイル名を指定してNetBSD kernelを起動できる。
このコマンドラインループはNetBSD kernelが起動するまでの間割り込み禁止のまま動作する(図 \ref{fig:boot_nointr})。
さすがにこのコマンドラインとbootoaderの全てのコマンドをHaskellで実装するのは大変だ。
しかしhelpとbootコマンドのみをHaskellでスナッチすることはできるのではないか？
どちらのコマンドももちろん割り込み禁止で動作するからだ。
ぼくはまずjhcのランタイム
^[\hrefT{https://github.com/ajhc/ajhc/tree/arafura/rts}]
をよく観察してみることにした。
\begin{wrapfigure}[13]{r}{80mm}
\includegraphics[width=80mm]{figure/masterq/2012-12-22-jhc_compile.eps}
\caption{jhcのコンパイルフロー}
\label{fig:jhc_compile_flow}
\end{wrapfigure}
jhcはHaskellコードをコンパイルすると単一のC言語ソースコードを吐き出す。
このC言語ソースコードの中にはHaskellソースコードに由来する全てのロジックが写し込まれている。
その後jhcはGCCを呼び出して左記のC言語ソースコードとランタイムのソースコードを一緒にコンパイルする(図 \ref{fig:jhc_compile_flow} )。
すると無事実行バイナリができる訳だ。
このjhcのコンパイルフローは途中で停止させることもできる。
それが"-C"オプション ^[\hrefT{http://ajhc.metasepi.org/manual_ja.html#オプション}] だ。
また"--tdir"オプションを使うことで中間生成されたランタイムソースコードをjhcが削除するのを防止できる。
例えば次のようなコマンドを使えば生成されたC言語ソースコードとランタイムソースコードが手に入る。
$ echo 'main = print "hoge"' > Hoge.hs
$ jhc -C --tdir=rts Hoge.hs
$ ls
Hoge.hs  rts/
$ ls rts
HsFFI.h  jhc_rts_header.h  lib/  main_code.c  rts/  sys/

main_code.cがHaskellコードをコンパイルして得られた結果のC言語ソースコード。
その他のファイル群がjhcのランタイムソースコードだ。
jhcはコンパイルを実行する毎にランタイムを再コンパイルする。
ランタイムの規模が劇的に小さいからこそなせる技だ。
ここで生成されたC言語ソースコードmain_code.cの中身を見てみる。
char jhc_c_compile[] = "gcc rts/rts/profile.c rts/rts/rts_support.c rts/rts/gc_
none.c rts/rts/jhc_rts.c rts/lib/lib_cbits.c rts/rts/gc_jgc.c rts/rts/stableptr
.c -Irts/cbits -Irts rts/main_code.c -o hs.out '-std=gnu99' -D_GNU_SOURCE '-fal
ign-functions=4' -ffast-math -Wextra -Wall -Wno-unused-parameter -fno-strict-al
iasing -DNDEBUG -O3 '-D_JHC_GC=_JHC_GC_JGC'";
char jhc_command[] = "jhc -C --tdir=rts Hoge.hs";

丁寧にもGCCに渡す予定だった引数が列挙されている。
そこで指示通りにjhcが本来実行するはずだったコンパイルの続きを手動で実行してみた。
$ gcc rts/rts/profile.c rts/rts/rts_support.c rts/rts/gc_none.c rts/rts/jhc_rts
.c rts/lib/lib_cbits.c rts/rts/gc_jgc.c rts/rts/stableptr.c -Irts/cbits -Irts r
ts/main_code.c -o hs.out '-std=gnu99' -D_GNU_SOURCE '-falign-functions=4' -ffas
t-math -Wextra -Wall -Wno-unused-parameter -fno-strict-aliasing -DNDEBUG -O3 '-
D_JHC_GC=_JHC_GC_JGC'
$ ls
Hoge.hs  hs.out*  rts/
$ ./hs.out
"hoge"

なるほど。あっさり実行バイナリが手に入った。
設計

ということは下記のような設計が可能なのではないか？
(図 \ref{fig:snatch_boot} )

bootloaderの初期化が終わってからjhcが生成したC言語ソースコードを呼び出す
Haskellを使って書かれたコマンドラインループが起動する
コマンドラインループがkernel起動コマンドを検出したら既存のC言語ソースコードに戻る

\begin{wrapfigure}[12]{r}{80mm}
\includegraphics[width=80mm]{figure/masterq/boot_sequence_diagram.eps}
\caption{bootloaderの一部をHaskellで再設計}
\label{fig:snatch_boot}
\end{wrapfigure}
問題はどうやって実現するかだ。NetBSD bootloaderは四つのライブラリを内包していて、
比較的リッチな環境でプログラミングできる(図 \ref{fig:libsa} )。
ひょっとするとjhcランタイムの実行に必要な機能がすでにそろっている可能性もある。
とにかくいきなり生のハードウェアの上で動くコードをjhcで作るよりもはるかに楽ができるはずだ。
残る疑問はjhcが生成したC言語ソースコードはどのようにして呼び出されるのかだ。
答は生成されたランタイムソースコード ^[ \hrefT{https://github.com/ajhc/ajhc/blob/v0.8.0.1/rts/rts/jhc_rts.c#L164} ]
を調べてすぐに判明した。
\begin{wrapfigure}[12]{r}{80mm}
\includegraphics[width=80mm]{figure/masterq/libsa.eps}
\caption{bootloaderで使えるライブラリ}
\label{fig:libsa}
\end{wrapfigure}
jhcが生成するC言語コードのmain関数は以下のような動作をする。

hs_init関数call
setjmpの設定
_amain関数call
hs_exit関数call

つまりGHCと同じようにhs_init関数を呼び出した後、
_amain関数というjhc独自の関数を呼び出せば良いようだ。
setjmpの設定は、例外を扱うためだけだ。
例外が起きないようにHaskellコードを書く上ではこれは不要と思っていい。
_amain関数はjhcがHaskellコードをコンパイルした結果のC言語ソースコード内にある。
// File: rts/main_code.c (ミューテータ)
void
_amain(void)
{
        return (void)b__main(saved_gc);
}

static void A_STD
b__main(gc_t gc)
{
        return ftheMain(gc);
}

ftheMain関数というのがHaskellのMain.main関数に相当するようだが、
_amain関数はそのラッパーになっているようだ。
これで材料を集めるのは終わっただろう。設計 ^[最初のスケッチのソースコード \hrefT{https://gitorious.org/metasepi/netbsd-arafura}] に入ろう。
まず既存のNetBSD bootloaderのソースコードを観察すると、
boot2という関数がメイン関数のようだった。
/* file: sys/arch/i386/stand/boot/boot2.c */
void
boot2(int biosdev, uint64_t biossector)
{
/* --snip-- */
	print_banner();
#endif

	printf("Press return to boot now, any other key for boot menu\n");

ここで注意しなければならないことがある。bootloaderの中では簡単にprintf関数が使えない。
POSIX上で動作するプログラムと異なり、bootloaderの下にはlibcもkernelもいない。
bootloaderの中でprintf関数を使うには、ビデオやシリアルの初期化をしなければならない。
このboot2関数の中ではじめてprintf関数を使う箇所が上のソースコードだった。
ということはこのprintf関数の直前までの間にコンソールの初期化は終わっているはずで、
当該箇所でHaskellコードをそのまま実行すれば文字を印字できるはずだ。
おそらくキー入力も受け付け可能だと思われる。
そこで以下のようにprintf関数直前にHaskellコードの呼び出しを追記した。
/* file: sys/arch/i386/stand/boot/boot2_ara.c */
	print_banner();
#endif
	{ /* Run Haskell code */
		int hsargc = 1;
		char *hsargv = "nbboot";
		char **hsargvp = &hsargv;

		hs_init(&hsargc, &hsargvp);
		if (jhc_setjmp(&jhc_uncaught)) {
			jhc_error("Uncaught Exception");
		} else {
			_amain();
		}
		/* hs_exit(); */
	}
	printf("Press return to boot now, any other key for boot menu\n");

これでHaskellコードがbootloaderから呼び出されるはずだ。
次の課題はhs_init関数と_amain関数の先にあるjhcランタイムが依存している関数の実装ということになる。
ほとんどは単純なスタブ関数を実装するだけだが、唯一面倒だったのがメモリ管理まわりだった。
jhcランタイムはmalloc関数を要求していた。
幸いにもNetBSD bootloaderが内包するライブラリがallocという関数を持っている。
これを使えばmallocのAPIを実装することは可能だ。
これでC言語側の設計は終わりだ。
コマンドラインループをHaskellで記述しよう。
NetBSD bootloaderのC言語での設計を見るかぎり、以下のようなHaskellコードと等価のようだった。
-- file: metasepi-arafura/sys/arch/i386/stand/boot/Boot2Ara.hs
import Control.Monad
import Data.Maybe
import Data.Map (Map)
import qualified Data.Map as Map
import Foreign.C.Types
import Foreign.Ptr

foreign import ccall "glue_netbsdstand.h command_boot" c_boot :: Ptr a -> IO ()

commands :: Map String (IO ())
commands = Map.fromList [("help", command_help),
                         ("boot", c_boot nullPtr)]

command_help :: IO ()
command_help = putStr $ "\
\commands are:\n\
\boot [xdNx:][filename] [-12acdqsvxz]\n\
\help\n"

main :: IO ()
main = do
  putStrLn "Haskell bootmenu"
  forever $ do
    putStr "> "
    s <- getLine
    fromMaybe (putStr s) $ Map.lookup s commands

上記のHaskellコードはコマンドラインから"boot"という入力を検出すると
C言語で書かれたcommand_boot関数を呼び出す。
このcommand_boot関数がkernelをファイルシステムから取り出し起動する。
つまりこれでコマンドラインループのみをHaskellコードでスナッチできたわけだ。
さてqemuでbootloaderを起動してみよう……あれ？Haskellコードが実行されない。動くはずなのに……
デバッグの結果どうやらmallocが1MBのメモリを確保しようとしているために、
NetBSD bootloaderのallocヒープが狭すぎてabortしているようだった。
bootloaderはコンベンショナルメモリ内の640kBで動作するため1MBもの大きなallocヒープは確保できない。
別の方法としては1MB以降の潤沢な拡張メモリをallocヒープとして使う手もあるが、
今度はBIOSから読み書きすることができなくなってしまう
^[リアルモードでも拡張メモリをアクセスする方法は存在するらしいです。
残念ながら筆者は具体的な手順を知りません……] 。
しかもリソースの制御は設計において重要な課題の一つだ。
実際の製品ではリソースは無限にあるわけではなく制約がつくのが通常だ。
たかだかコマンドラインループを実現するために最低1MBものヒープが必要になるのではこの先
kernelを書く上で致命的な欠陥を生じかねない。
ここは踏み止まって省メモリ化を検討すべきだ。
そこでぼくはjhcランタイム中でのmallocの使用箇所を洗い出してみることにした。
$ grep -n malloc rts/rts/gc_jgc.c
193:    saved_gc = gc_stack_base = malloc((1UL << 18)*sizeof(gc_stack_base[0]));
298:    base = _aligned_malloc(MEGABLOCK_SIZE, BLOCK_SIZE);
320:    struct s_megablock *mb = malloc(sizeof(*mb));
512:    struct s_cache *sc = malloc(sizeof(*sc));
588:    struct s_arena *arena = malloc(sizeof(struct s_arena));
618:gc_malloc_foreignptr(unsigned alignment, unsigned size, bool finalizer) {

193行目と298行目がどちらも1MByteものメモリを確保している。
このサイズを単に小さくしてしまえば逃げられないのだろうか？

gc_stack_base: 1MByte → 128kByte
MEGABLOCK_SIZE: 1MByte → 64kByte
BLOCK_SIZE: 4kByte → 256Byte

再コンパイル……実行……動いた!
だましだましコンベンショナルメモリに押し込んだが、
jhcはPOSIXレイヤーがなくとも動作可能なバイナリを吐き出せることを実証できた。
またスナッチモデルが少なくとも割り込み禁止状態で動作するソフトウェアに対しては有効であることもわかった。
ぼくは意気揚々としてみんなにこの成果を報せた。
あの苦しみを経験したぼくらならこのjhcコンパイラを製品化可能なレベルにまで、
みんなで成長させることができるのではないかと思ったのだ。
ところがみんなの反応はぼんやりしていた。 \newline
「bootloaderを書き換えても何の証左にもなっていないと思う」 \newline
「デバイスドライバ書くならメモリマップドIOをさわらなきゃだけどHaskellだと無理じゃない？」 \newline
「そもそもC言語で記述されたkernelと同等の表現を得られるのかな？」 \newline
「もし製品化するならコンパイラの中身を弄らなきゃならない。素人には無理だよ」 \newline
みんなから湧き出る不安と疑問。
ぼくは意気消沈した。
冷たい壁

海が見える。
この国では外洋に接する海岸が多く、しかも地震が多い。
例年のように津波による被害が出る
^[\hrefT{http://ja.wikipedia.org/wiki/スマトラ島沖地震}] 。
いつものおだやかな海岸も時に本来の巨大な力を剥き出しにする。
技術探索も同じだ。
一見うまく出荷できそうな基本設計も詳細な実装をする段階になって根本的な欠陥が見つかることも多い。
出荷できない技術など存在しないも同然だ。
人はみな視界を持っている。どこまで見通せるかは人それぞれだが、その範囲はたかだか有限なのだ。
ぼくの道は光に通じるのか、それともやはり冷たい高い壁が待ち構えるのみなのか…… \newline
「モチベーションを複製することは困難でゲソ」 \newline
いつの間にかあの娘が隣にいた。 \newline
「おぬしが出会う問題と他人が出会う問題は同じようでも微妙に異なるじゃなイカ。
それらが蓄積されると問題の集合同士は大きく異なることになるでゲソ」 \newline
なにを当然のことを言ってるんだよ…… \newline
「モチベーションは問題意識から生まれることが多いでゲソ。
するとモチベーションを他人の中に完全に複製するためには、
おぬしがこれまで出会ってきた問題を全部説明しなければならないことになるんじゃなイカ？」 \newline
そんなことは有限時間では不可能だ。 \newline
「いまは初速が必要なのでゲソ」 \newline
つまり？ \newline
「モチベーションを共有していなくてもプロジェクトに参加したくなる、
そんな魅力的な機能と性能と品質とそして明確な用途を示す必要があるのでゲソ。
そして究極的にはその魔法の瞬間まではおぬし一人で辿りつくしかないんじゃなイカ？」 \newline
しかしぼくの中にあるエネルギーは有限だ。
その初速を得るに足りない場合はどうすればいいんだ…… \newline
「その時は」 \newline
風がきこえる。 \newline
「未到達ということになるんじゃなイカ。
おぬしはいつも自分のことしか見ていないようでゲソ。
いま足場にしているjhcコンパイラという一つの到達点に誰がいったいどうやって辿りついたのか、
そのことを考えてみるべき時じゃなイカ？」 \newline
… \newline
　… \newline
…　…
決めた。jhcコンパイラをぼく一人の手で成長させる。
この純朴なコンパイラが秘めた光をはなつまでは。
jhcコンパイラの作者である J
^[John Meacham \hrefT{http://repetae.net/}]
に何度かpatchを送ってみたが、mergeはしてくれどもあまり活発な応答はなかった。
おそらくとてつもなく忙しいのかもしれない。
もしかしたら……いや、どんな天才でも気力が底をつくことだってある。
全てのリソースは有限なのだ。
jhcのランタイムとコンパイルパイプラインの最終段については理解が進んでいたので、
修正のアイデアがいくつもあった。
そこでぼくはjhcをフォークして Ajhc
^[Ajhc - Haskell everywhere \hrefT{http://ajhc.metasepi.org/}]
というプロジェクトを立ち上げることにした。
オープンソースプロジェクトにおいてプロジェクトのフォークはあまり良いイメージがない。
しかしリポジトリがない状況でこれ以上jhcの機能開発をすることは困難だった。
もちろんぼくが実装する機能の宣伝をする場所が欲しかったこともある。
Jには悪いと思ったが、正直に何が問題であるのかをまとめてメールを送った。
^[ANNOUNCE: Start Ajhc project with forking jhc. \hrefT{http://www.haskell.org/pipermail/jhc/2013-March/001007.html}]
さぁ準備は整った。あとは進むだけだ。ぼくのリソースのあるかぎり。
二度目のスケッチ: 省メモリ化の追求

プロジェクトを起こしたからにはわかりやすい応用例があった方がいい。
最初のスケッチではbootloaderをスナッチしたが、今ふりかえると見た目が地味だったと思う。
もっとわかりやすいアピールが必要だ。
最近Makerムーブメントの影響でマイコンプログラミングが流行っている。
ArduinoのようなC言語ではない言語を使う開発環境もある。
jhcを使ったマイコン開発という切り口はわかりやすいのではないか？
ハードウェア選定

bootloaderのスナッチではallocヒープを320kByte確保していた。
このallocヒープはC言語のmallocとHaskellヒープの両方を管理している。
kernelのファイル読み込みでallocヒープは酷使されるので、
マイコンではHaskellヒープのみを使い、さらにjhcのGCをよく観察すれば、
ヒープ全体の容量は桁を一つ落とすことが不可能でないかもしれない。
つまり数十kByteのメモリ(RAM)で動作するHaskellコードだ。
やるからには限界に挑戦したくなっていた。
そんなマイコンを探してみよう。
この国には秋葉原のような便利な場所がない。
それでもインターネットはやはり便利でネット通販で開発ボードを買える。
今回のスケッチにぴったりのボードが見つかった。

ボード名: STM32F3DISCOVERY \hrefT{http://www.st.com/stm32f3discovery}
CPU: ARM Cortex-M4
ROM: 256kByte
RAM: 48kByte
備考: ST-LINK/V2チップ付属 - gdbによるデバッグが可能 ^[\hrefT{https://github.com/texane/stlink}]
価格: 950円

\begin{wrapfigure}[14]{r}{90mm}
\includegraphics[width=90mm]{figure/masterq/stm32lib.eps}
\caption{Corntex-M4上のプログラムのスナッチ}
\label{fig:stm32lib}
\end{wrapfigure}
すごい時代だ。評価ボードがこんな価格で入手できる。さっそく注文した。
手元に届くまでの間に開発環境を整えよう。
STM32F3-Discovery Application Template ^[\hrefT{https://github.com/mblythe86/stm32f3-discovery-basic-template}]
にSTM32F3DISCOVERY用のLEDチカチカのソースコード一式が落ちていた。
ありがたくスケッチの足場として使わせてもらうことにした ^[二度目のスケッチのソースコード \hrefT{https://github.com/ajhc/demo-cortex-m3}] 。
数日の後ボードが届いたので、クロスgdbでC言語のデモを動かしてみたところ問題なく動作した ^[\hrefT{http://www.slideshare.net/master_q/20130629-deb-cortexm3}] 。
これでスタート地点に立てたことになる。
作戦

さっき見つけたC言語で書かれているLEDチカチカデモをスナッチしてみることにした。
おそらくこのスケッチの全体像は図 \ref{fig:stm32lib} のようになるだろう。
このデモはC言語とアセンブラでできているはずだった。
これをHaskellコードを使ってスナッチする。
この時、jhcランタイムが依存するプリミティブが足りないこともあるかもしれない。
その場合は適宜ランタイムサポートのためのコードを書くしかない。
このランタイムサポートのコードを小さく抑えれば、
jhcランタイムの依存する機能プリミティブが見えてくるはずだ。
\begin{wrapfigure}[15]{r}{90mm}
\includegraphics[width=90mm]{figure/masterq/cross_compile.eps}
\caption{Corntex-M4クロスコンパイル環境}
\label{fig:cross_env}
\end{wrapfigure}
ぼくはこのスナッチのゴールについて考えてみた。
アセンブラのコードはおそらくC言語でさえ記述できないしろものなので、
置換することは不可能だ。
ということはランタイムサポートと既存C言語コードの最小値を得た地点がゴールということになる。
さて、先のbootloaderのスナッチではあまりちゃんとしたビルドプロセスを作らなかった。
まだjhcについての理解が浅かったためだ。
今回はx86の開発マシンの上でARMのバイナリをコンパイルするため、
しっかりとしたクロスコンパイル環境を整えた方がいい。
また、前回のスナッチではjhcのランタイムソースコードを開発対象のディレクトリに含めてしまっていた。
これは開発対象のソースコードがjhcの特定バージョンに紐づいてしまう原因になる。
\begin{wrapfigure}[15]{r}{90mm}
\includegraphics[width=90mm]{figure/masterq/memmap.eps}
\caption{Cortex-M4上で動作する実行バイナリのメモリマップ例}
\label{fig:memmap}
\end{wrapfigure}
そこで図 \ref{fig:cross_env} のようなクロスコンパイル環境を作った。
開発環境にAjhcランタイムソースコードを保持するのではなく、
Haskellソースコードをコンパイルする際に生成されるAjhcランタイムソースコードをライブラリ化してリンクするようにした。
これでコンパイル時に使用しているバージョンのAjhcに対応するランタイムを使うことができる。
もしAjhcランタイムに修正を入れたくなったらAjhc本体に修正を加えなければならない。
libstm32f3.aは先のTemplateに付属していたユーティリティが入っている。
またTemplateにはmalloc APIがなかったので、
bootloaderのallocコードを移植した。
いろいろな要素が出てきて混乱してきた。
クロスコンパイラによって生成された実行バイナリの中身を一度整理してみることにした。
図 \ref{fig:memmap} は実行バイナリのメモリマップだ。
\begin{wrapfigure}[14]{r}{90mm}
\includegraphics[width=90mm]{figure/masterq/boot.eps}
\caption{Cortex-M4上でのHaskellコードの起動}
\label{fig:boot_cortexm4}
\end{wrapfigure}
TEXT領域には手書きしたC言語コードとAjhcが吐き出したC言語コードがまざっている。
Haskellで動的に確保するサンクはHaskellヒープの中に配置される。
Haskellコードがこの領域より多くのサンクを同時に確保しようとした場合にはabortになる。
さらにHaskellヒープの管理を目的としてmallocヒープが用意されている。
このmallocヒープがあふれた場合も即abortだ。
Ajhcの吐き出すコードは再帰の実行のためにスタックを多く消費することがある。
スタックは若いアドレスに向かって成長するため、
このメモリマップだとスタックがBSSを破壊することがある。
製品化の際にはスタック領域をRAMの先頭に配置した方が良いかもしれない。
クロスコンパイラによって生成された実行バイナリは次のように起動する(図 \ref{fig:boot_cortexm4} )。

CPUはリセットベクタから実行を開始する
リセットベクタはC言語のmain関数を呼び出す
C言語のmain関数はハードウェアの初期化を行なう
C言語のmain関数はAjhcランタイムのhs_initを呼び出す
hs_init関数はAjhcランタイムの初期化を行なう
C言語のmain関数は_amain関数を呼び出しHaskellコードが走る

さぁHaskellコードを書いてみよう。
マイコンのHello WorldといえばLEDチカチカだろう。
このボードにはLEDが8つ搭載されているが、その内LED3だけをblinkさせてみた。
import Data.Word
import Control.Monad
import Foreign.Ptr
import Foreign.Storable

foreign import ccall "c_extern.h Delay" c_delay :: Word32 -> IO ()
foreign import ccall "c_extern.h &jhc_zeroAddress" c_zeroAddress16 :: Ptr Word16

gpioPin9, led3 :: Word16
gpioPin9 = 0x0200
led3     = gpioPin9

brrPtr, bsrrPtr :: Ptr Word16
brrPtr  = c_zeroAddress16 `plusPtr` 0x48001028
bsrrPtr = c_zeroAddress16 `plusPtr` 0x48001018

ledOff, ledOn :: Word16 -> IO ()
ledOff = poke brrPtr
ledOn  = poke bsrrPtr

main :: IO ()
main = forever $ do
  ledOn led3
  c_delay 10
  ledOff led3
  c_delay 10

\begin{wrapfigure}[15]{r}{100mm}
\includegraphics[width=100mm]{figure/masterq/running_blink.eps}
\caption{LEDチカチカプログラムの動作}
\label{fig:blink_led}
\end{wrapfigure}
このHaskellコードの動作をおおざっぱに図示してみる(図 \ref{fig:blink_led} )。
Haskellは実はPtr型を通して生のメモリへ直接読み書きを行なうことができる。
書き込み関数がpoke
、読み込み関数がpeek
だ。このボードの場合0x48001028アドレスに0x200を書くとLED3が点灯し、
0x48001018アドレスに同じく0x200を書くことでLED3が消灯する。
c_delay関数はC言語のDelay関数を呼び出して、時間待ち合わせを行なう。
ここでjhc_zeroAddressというC言語側で定義されたグローバルポインタ経由でPtr型を作っていることに疑問を持つかもしれない。
これには理由がある。
仮にnullPtr ^[\hrefT{http://hackage.haskell.org/packages/archive/base/latest/doc/html/Foreign-Ptr.html#v:nullPtr}]
を使って通常のHaskell APIのみで実装してみる。
--- a/stm32f3-discovery/hs_src/MainBlinkLedSimple.hs
+++ b/stm32f3-discovery/hs_src/MainBlinkLedSimple.hs
@@ -11,8 +11,8 @@ gpioPin9 = 0x0200
 led3     = gpioPin9
 
 brrPtr, bsrrPtr :: Ptr Word16
-brrPtr  = c_zeroAddress16 `plusPtr` 0x48001028
-bsrrPtr = c_zeroAddress16 `plusPtr` 0x48001018
+brrPtr  = nullPtr `plusPtr` 0x48001028
+bsrrPtr = nullPtr `plusPtr` 0x48001018
 
 ledOff, ledOn :: Word16 -> IO ()
 ledOff = poke brrPtr

このHaskellコードをAjhcでコンパイルするとHaskellのmain関数は以下のようなC言語ソースに変換されることになる。
static void A_STD
ftheMain(gc_t gc)
{
        fR$__fControl_Monad_forever__2:;
        {   *((uint16_t *)(1207963672)) = 512;
            saved_gc = gc;
            (void)Delay((uint32_t)10);
            *((uint16_t *)(1207963688)) = 512;
            saved_gc = gc;
            (void)Delay((uint32_t)10);
            goto fR$__fControl_Monad_forever__2;
        }
        return;
}

一見0x48001028アドレスに0x200を正常に書き込んでいるように見える。
しかし上記のC言語ソースコードをよく見ると、ポインタアクセスにvolatileが付いていない。
これではGCC側では最適化で消されてしまうことになる。副作用と認められないのだ。
static void A_STD
ftheMain(gc_t gc)
{
        fR$__fControl_Monad_forever__2:;
        {   *((uint16_t *)(1207963672 + ((uintptr_t)&jhc_zeroAddress))) = 512;
            saved_gc = gc;
            (void)Delay((uint32_t)10);
            *((uint16_t *)(1207963688 + ((uintptr_t)&jhc_zeroAddress))) = 512;
            saved_gc = gc;
            (void)Delay((uint32_t)10);
            goto fR$__fControl_Monad_forever__2;
        }
        return;
}

元のjhc_zeroAddressを使ったHaskellコードをC言語に変換すると上記のような
jhc_zeroAddressグローバルポインタに書き込みアドレスを加えたポインタに0x200を書き込むコードが生成される。
Haskell側でPtr型にvolatileを付けるプラグマがあればよかったのだが、その方法はないようだった。
jhc_zeroAddressは0アドレスへのポインタとしてC言語側で宣言されている。
そのためこの方式であればC言語コンパイラは愚直にメモリ書き込みを行なうアセンブラを吐くようになる。
どうやらAjhcを使ったハードウェア制御コードではこのイディオムがセオリー ^[\hrefT{https://github.com/ajhc/demo-cortex-m3#write-haskell-code}] になりそうだった。
デバッグ

さて作成したコードを実行してみた。なんとあっさりLEDがチカチカ光るじゃないか。
型の力はすばらしい。
ポインタアクセスをしている界面のみ気をつけて設計すれば残りは型に守られた設計ができるのだ。
ところが先の簡単なforeverループを拡張してちょっと純粋な関数を加えるとコードが動かない。
これは何が起きているのだろうか？
gdbで追ってみると例外ベクタに飛んでいる。なぜ例外が起きるのか？
もっと丁寧に追うとコードのかなり深くで例外が起きる。
ヒープの制御がおかしいのだろうか。スタックがあふれたのだろうか。
数日の間このことが頭をはなれず、アルバイトでもぼーっとしていた。 \newline
「なにを悩んでるの？」 \newline
ふりむくと同僚がいた。彼はプログラミング言語にとても詳しく、なにかあるとサポートしてもらっていた。
ぼくは思い切ってAjhcの計画について打ち明けてみた。 \newline
「うーん、その不具合の原因はよくわからないけれど、その計画は明らかにGCが鍵になるね」 \newline
jhcのGCはC言語のみで記述されていて、行数も800行程度と短かい。
しかしその実装はトリッキーでこれまで理解することを避けてきていた。
それが今のデバッグの困難に結びついていたのだ。 \newline
「ちょっとコードを読んできてあげるよ。なにかわかったらメールするね」
数日後、ぼくは彼からjhcのGC ( jgc と呼ばれる) のしくみを教えてもらった ^[小二病でもGCやりたい \hrefT{http://www.slideshare.net/dec9ue/gc-16298437}] 。
とてもわかりやすい資料だった。
ぼくはこれを元にして自分なりにjgcのコードを読んでみた。
\begin{wrapfigure}[17]{r}{110mm}
\includegraphics[width=110mm]{figure/masterq/heap_struct.eps}
\caption{jgcでのHaskellヒープの管理}
\label{fig:jgc_arena}
\end{wrapfigure}
まずjgcはHaskellヒープ全体をarenaグローバル変数で管理する(図 \ref{fig:jgc_arena} )。
次にHaskellのサンクなどのデータを格納するための器がある。
その最も大きい単位がmegablockだ。Haskellヒープの容量が不足するたびにmegablockは追加で確保される。
megablockの中には固定サイズのblockという構造がある。
このblockをさらに固定サイズのチャンクに分割して、そのチャンクにHaskellで使用するデータを格納する。
blockにはused bitの配列があり、使用中 ^[ここではGCルートから辿れることを使用中を呼んでいる]
のチャンクに対応するビットには1を。未使用のチャンクに対応するビットには0を書くのが決まりだ。
さらにblockにはlinkというメンバーがあり、
当該のblockがHaskellヒープ全体から見てどこに繋っているのかリスト管理できるようになっている。
例えば、s_arena構造体にはfree_blocksというメンバーがあり、
このメンバーに繋がっているblockは内包する全てのチャンクが未使用であることを表わす。
\begin{wrapfigure}[17]{r}{110mm}
\includegraphics[width=110mm]{figure/masterq/chunk_struct.eps}
\caption{jgcでのチャンクの構造はcacheで定義される}
\label{fig:jgc_cache}
\end{wrapfigure}
ここから少し見慣れない構造がでてくる。 cache だ。
s_arena構造体のcachesメンバーにはcacheという構造がぶらさがっている。
このcacheの先にはblockがぶらさがっているのだが、
そのblockの中のチャンクのデータ構造をcacheによって定義している(図 \ref{fig:jgc_cache} )。
すなわちcacheのnum_ptrsメンバーはチャンクの中のポインタの個数を表わし、
sizeメンバーはチャンクの全体サイズを表わす。
\begin{wrapfigure}[17]{r}{110mm}
\includegraphics[width=110mm]{figure/masterq/gc_mark.eps}
\caption{jgcのGCマーキング}
\label{fig:jgc_marking}
\end{wrapfigure}
この時チャンク内のポインタは先頭から配置されるのが約束になっている。
ポインタはスマートポインタになっていて格納される値は即値である可能性もある ^[\hrefT{http://ajhc.metasepi.org/manual_ja.html#ランタイムシステム}] 。
このcacheのリストはAjhcランタイムの初期化の中でfind_cache関数によって動的に確保される。
このチャンクはHaskell由来のデータを格納しているが当然GCする必要がある。
jgcのGCはミューテータがコンストラクタによってHaskellヒープから新しいメモリ領域を確保しようとする時にのみ呼び出される。
またGCはマーキングだけを行ないスイープをしない。
というのもcacheのblocksメンバーのused bitを検索すれば未使用チャンクが見つかるし、
仮にそこで見つからなかった場合にはs_arena構造体のfree_blocksから新しいblockを補充するれば良いからだ。
jgcのGCは以下のような手順を取る(図 \ref{fig:jgc_marking} )。

Haskellヒープのアロケート関数s_allocがミューテータによって呼び出される
s_alloc関数は要求されたコンストラクタに対応する未使用チャンクを探す
2で見つからなかった場合megablockを新たに確保すべきかGCすべきかを判定する
3でGCすべきと判断した場合gc_perform_gc関数を呼び出す
gc_perform_gc関数はHaskellヒープ全てのused bitを0クリアする
gc_perform_gc関数はGCルートから参照を辿り、当該チャンクに対応したused bitに1を立てる
2と同じように未使用チャンクを探してミューテータに渡す

\begin{wrapfigure}[17]{r}{110mm}
\includegraphics[width=110mm]{figure/masterq/eval_thunk.eps}
\caption{サンク評価の一例}
\label{fig:thunk}
\end{wrapfigure}
スマートポインタにはいくつか種類があり、fptr_tもその一種だ。
このfptr_tには最初はクロージャの評価関数へのポインタが格納されている。
つまり未評価サンクだ(図 \ref{fig:thunk} )。
このサンクを評価するにはサンクのスマートポインタをevalの第二引数に渡す。
するとevalはサンクの遅延ビットをチェックし、
未評価サンクだと判定すればfptr_tの先にあるクロージャ評価関数にnode_tを渡す。
クロージャの評価が終わったらupdate関数を呼び出してチャンクに入っている
fptr_tをクロージャの評価結果で上書きする。
この時fptr_tの遅延ビットは0にする。これで評価済みサンクのできあがりだ。
かなりGCのコードを読み込んだおかげでAjhcのランタイムの動作が想像できるようになった気がする。
やはり同僚のアドバイスは正しかったようだ。ありがたいことだった。
ぼくはデバッグを再開した。
やはり例外が起きている。
どうも単純なIOのみのforeverループを逸脱するとHaskellヒープを使うようになるようだ。
この時サンクの評価のために関数ポインタへのジャンプ命令が実行されるのだが、
その近辺で例外ベクターに飛んでしまう。関数ポインタの先もtext領域の範囲内だ。
これはソフトウェアの問題ではなくARMプラットフォーム側の問題ではないか？
ぼくはobjdumpでeval関数のアセンブラを見てみた。
関数ポインタジャンプはARMではblxという命令のようだ。
なんとなく嫌な予感がする。
ARMの命令リファレンスからblx命令の章 ^[\hrefT{http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dui0489i/CIHBJCDC.html}] を見てみよう。
The BLX instruction can change the instruction set.
BLX label always changes the instruction set. It changes a processor in ARM
state to Thumb state, or a processor in Thumb state to ARM state.
BLX Rm derives the target instruction set from bit[0] of Rm:
* if bit[0] of Rm is 0, the processor changes to, or remains in, ARM state
* if bit[0] of Rm is 1, the processor changes to, or remains in, Thumb state.

な　ん　だ　と　？
Cortex-M4はARM stateはサポートせずThumb stateのみしか使えないはずだ。
ということは関数ポインタアクセスの場合は0ビット目に必ず1を立てないと例外が起きるということなのか？
なんというアーキティクチャだ……信じられない。
\begin{wrapfigure}[22]{r}{65mm}
\includegraphics[width=65mm]{figure/masterq/leak.eps}
\caption{s_alloc関数フローチャートとGC後のリトライ追加}
\label{fig:s_alloc_flow}
\end{wrapfigure}
まだ納得できないのでGCCが良きにはからってくれないかWeb検索してみた。
ところがどうも最新のGCCでもこの問題には決着がついていない ^[\hrefT{http://communities.mentor.com/community/cs/archives/arm-gnu/msg01904.html2}] ようだった。
さすがにこれはAjhcのランタイム側に修正を加えるしかない。
ぼくは"_JHC_ARM_STAY_IN_THUMB_MODE"というコンパイルフラグ ^[\hrefT{http://ajhc.metasepi.org/manual_ja.html#cflagsで指定できる特殊なdefine}] を用意することにした。
ソースコード ^[ \hrefT{https://github.com/ajhc/ajhc/blob/v0.8.0.4/rts/rts/jhc_rts.h#L99} ] ^[ \hrefT{https://github.com/ajhc/ajhc/blob/v0.8.0.4/rts/rts/jhc_rts.c#L147} ]
を読めばわかる通りだが、
このフラグを有効にすると関数ポインタを使う前に0ビット目を立てる。
やっとHaskellヒープを使うプログラムが動作するようになった。
ぼくは安堵して夕食を取ることにした。少しビンタンも飲もう。
ところが机に戻ってみるとさっき実行させたままだったデモアプリケーションが停止している。
おかしい……abortで停止している。
gdbでバックトレースを取ってみるとどうやらs_allocでメモリ領域を確保しようとして失敗しているようだった。
メモリリークをしているのか？
もう一度s_allocのソースコードを良く読んでみることにした。
すると原因が判明した。
jgcはmegablockとblockの確保を富豪的に楽観的に行なう。
図 \ref{fig:s_alloc_flow} のフローチャートはs_alloc関数の実行フローだ。
よく見るとGCを実行した後にmegablockを確保してしまうことがわかる。
このままではヒープが足りているにもかかわらず、不要なmegablockを投機的に確保してしまう。
メモリが豊富にあるのであれば、時間効率をかせぐために投機的なmegablock確保は有効かもしれない。
しかし数十kBしかメモリがないマイコンではこの富豪的なmegablock確保方式は致命傷だ。
これもまたAjhcランタイムを修正する他にない。
"_JHC_JGC_NAIVEGC"というコンパイルフラグを作った。
このフラグを有効にするとGC実行の後、一度だけs_alloc関数を最初からリトライする。
GCをしているということはblocksもしくはfree_blocksにエントリが追加されたかもしれないからだ。
これでやっとデモプログラムが安定動作するようになった。
ちょっと凝ったプログラムを作ろう。
任意の文字列をLEDでモールス信号表示するプログラムだ。
まずモールス信号の型を決める。
data Morse = S | L | LetterSpace | WordSpace

\begin{wrapfigure}[15]{r}{90mm}
\includegraphics[width=90mm]{figure/masterq/running_morsecode.eps}
\caption{モールス信号LED表示デモの関数}
\label{fig:morse_flow}
\end{wrapfigure}
Sがトン、Lがツーだ。
制御コードは長いので、ここではその構造を図にしてみることにする(図 \ref{fig:morse_flow} )。
containersライブラリのMapを使ってmorseCodeという文字→モールス信号列の変換表を作る。
さらにモールス信号をLEDのblinkアクション列に変換するmorseToIO関数を作る。
この二つを組み合わせることで任意の文字列をLEDのblinkアクション列に変換する
morseEncodeIO関数を作ることができる。
最後にまたforeverループに食わせれば任意の文字列を繰り返しモールス信号表示するプログラムが完成する。
ぼくはこのモールス信号プログラムを作っている時、一度もデバッガを使わなかった。
またLinux上でのテストもしなかった。
ただ書き下してコンパイルが通ればその通りに動いた。
型安全の威力はどのドメインにおいても有効なのだと思い知った。
このデモをみんなに見せてみた。こんどはみんなびっくりしてくれた。
しかしツテを頼ってもAjhcを収益化する見込みは得られなかった。
アルバイトをしながらAjhcを開発していてもなかなか先に進めない。
どうやらもう一頑張り必要なようだった。
あこがれ

ぬるくなったビンタンの瓶が見える。
最近は暇されあればjhcのソースコードを読んでいた。
jhcのソースコードはおせいじにもキレイとは言いがたかった。
それでも時間をかければ全体像が見えてきた。
"An informal graph of the internal code motion in jhc" ^[\hrefT{http://repetae.net/computer/jhc/big-picture.pdf}]
にも解説があるが、もっと関数レベルの関係図を頭に入れておきたい。
描いてみると図 \ref{fig:jhc_compie_pipeline} ができあがった。
まだ少しイメージがつかみにくいので型の変換に注目してみよう。
jhcのコンパイルパイプラインはHaskellソース文字列を以下の型を通してC言語ソース文字列に変換する。
この型の変換そのものがコンパイルという行為だというわけだ。

[FilePath]型 (Haskellソースコードのファイルパス)
CollectedHo型 ∋ IdMap Comb型 ∋ E型 (コンパイル対象単体での最適化)
Program型 ∋ Comb型 ∋ E型 (プログラム全体の最適化)
Grin型 ∋ [FuncDef]型 ∋ Lam型 (λ抽象での最適化)
ByteString型 (C言語ソースコード)

\begin{wrapfigure}[17]{r}{110mm}
\includegraphics[width=110mm]{figure/masterq/2013-01-25-jhc_compile_flow.eps}
\caption{jhcコンパイルパイプラインの全体像}
\label{fig:jhc_compie_pipeline}
\end{wrapfigure}
Haskellコードはjhcコンパイルパイプラインの中で大きく二つの型で表現されているようだった。
E型とGrin型だ。
E型は二つの最適化フェーズで使われる。
一つ目はコンパイル対象単体での最適化だ。
実行プログラムをコンパイルする際にもこの最適化が行なわれるが、
より注目すべきはhlファイルだ。
このhlファイルはjhcにおけるコンパイル済みHaskellライブラリのフォーマットで、
第一段階のE型最適化が完了した時点で凍結されたHaskellコードが格納されている。
二つ目はプログラム全体での最適化だ。
この第二段階のE型最適化ではコンパイル対象とhlファイルを一緒にして最適化する。
そのためhlファイルの中でも未到達な関数はこの第二段階で削除されることになる。
Grin型はC言語ソースコードに変換される直前の変形に用いられる。
他にまとまったドキュメントには "Jhc User's Manual" ^[Jhc User's Manual(英語) \hrefT{http://repetae.net/computer/jhc/manual.html}] がある。
このドキュメントは英語で、ぼくには読みにくかった。
そこで英語が得意な友達 ^[@dif_engineさんに手伝ってもらったでゲソ!]
に協力してもらって日本語訳 ^[Ajhcユーザーズマニュアル(日本語) \hrefT{http://ajhc.metasepi.org/manual_ja.html}] をしてみた。
このマニュアルを読むことでjhcの設計ポリシーがわかってきた。

grinは未到達のコードを削除する
hlファイルは動的/静的リンクなどはできず、grinにかけてバイナリ化しないと実行できない
Haskellのプリミティブ型はC言語の型そのまま
コンパイルパイプライン途中のASTをダンプできるオプションが多数ある
m4プリプロセッサのような変態的な機能
スマートポインタのためにInt型は30ビット幅
Integer型はまっとうに実装されておらずIntMax型と同じ精度しか保持できない
pure type systemという型システムを採用していて、これはラムダキューブに対応する

特に重要なアイデアがプリミティブ型についてだ。
-- File: ajhc/lib/jhc-prim/Jhc/Prim/Bits.hs
data Bits32_  :: #

-- File: ajhc/lib/jhc/Jhc/Type/Word.hs
data {-# CTYPE "int"      #-} Int = Int Bits32_

このCTYPEというのは型プラグマ ^[ \hrefT{http://ajhc.metasepi.org/manual_ja.html#型プラグマ} ]
でFFIの先であるC言語から見た型を指示する。
つまりHaskellのInt型はC言語側から見るとC言語のint型に見えるということだ。
Bits32_型は"#"という見慣れない型に落ちているが、
これは"プリミティブ型である"という意味しか持っておらず、
単にHaskell側の型推論のつじつま合わせとして使われる。
これらのプリミティブ型は当然アンボックス化された型で、
この型をボックス化するのはHaskellで書かれたライブラリの責務だ。
この型定義を見て、ぼくは(+)演算子の実装はどうなっているのか気になった。
jhcのHaskellライブラリ側では以下のような実装になっており、
Int同士の和は"Add"というプリミティブ型に落とされているようだった。
このAddプリミティブ型はjhcコンパイラでのgrin=>Cへの変換で単にC言語の"+"演算子に変換される。
Intは完全にアンボックス化されて直接C言語コードに落ちることになるわけだ。

Haskellの(+)演算子
↓変換 --- ajhc/lib/jhc/Jhc/Num.m4 (Numクラスの(+)関数定義)
jhcの"Add"プリミティブ
↓変換 --- ajhc/src/Cmm/Op.hs (プリミティブの定義)
↓変換 --- ajhc/src/C/Generate.hs (オペレータの定義)
↓変換 --- ajhc/src/C/FromGrin2.hs (Grin=>C変換)
C言語"+"演算子

今度は型の変換を調べてみよう。
例えばfromIntegral関数を使ったIntからFloatへの変換だ。

HaskellのfromIntegral :: Int -> Float関数
↓変換 --- ajhc/lib/jhc/Jhc/Num.hs (fromIntegralの定義)
fromInteger . toInteger
↓変換 --- ajhc/lib/jhc/Jhc/Num.m4 (toIntegerの定義)
fromInteger . I2I
↓変換 --- ajhc/lib/jhc/Jhc/Float.hs (fromIntegerの定義)
I2F . I2I
↓変換 --- ajhc/src/Cmm/Op.hs (I2Iのようなキャスト型定義)
↓変換 --- ajhc/src/C/Generate.hs (キャスト操作の定義)
↓変換 --- ajhc/src/C/FromGrin2.hs (Grin=>C変換)
C言語の二回キャスト (float)(int32_t)

なにやらややこしいが"I2I"と"I2F"というプリミティブを合成したものがIntからFloatへの変換のようだ。
この二つのプリミティブはやはりgrin=>Cへの変換で解釈される。
そうしてなんのことはない単にC言語のキャストに変換されるだけだ。
もっと簡単に言ってしまえば、
jhcにおいてHaskellのデータ型は全てC言語と紐づけられたプリミティブ型のみで構成されている。
もちろんHaskell関数の評価についてはC言語とは別物だ。
C言語の演算子や関数が部分適用された場合には相応の変換をかける必要がある。
しかしその評価順序さえC言語と等価なもの(C言語への変換直前のgrinコード)に落としてしまえば、
後はプリミティブ型をC言語型に写像すればそのままC言語コードができあがる。
この一見不可能に思えるアイデアこそがjhcの秘密のようだった。
jhcはHaskellコードをC言語に変換することを最初から強く意図して設計されていたのだ。
jhcのソースコードを読めば読むほどぼくはコンパイラという世界の魅力にとりつかれた。
こんなアイデアを思いつきそして具現化したJの才能にあこがれた。そしてもちろん嫉妬した。
なぜこれほどの頭脳がオープンソースの世界で発揮されず、開発が停滞してしまっているのか。
なぜ世界はこの偉業を引き継ごうとしないのか。焦りと失望が頭をめぐる。 \newline
「なにを考えているでゲソ？」 \newline
元気なあの声がする。 \newline
「コンパイラの開発仲間が増えないことに焦っているんじゃなイカ？」 \newline
そうだ。ぼく一人でできることは限られている。
このままのスピードではいつになったらkernelをスナッチできるのか予想ができなかった。 \newline
「そもそも今のAjhcコンパイラをはじめて見た者はどう感じると思うでゲソ？」 \newline
小さなマイコンにも適用できる組み込み用途のHaskellコンパイラ。 \newline
「じゃあHaskell言語をはじめて使ってみようと思った者が使うコンパイラはなんでゲソ？」 \newline
……GHC以外にありえない…… \newline
「ということはこのままでは小規模組み込みのエンジニアでなおかつ型推論を持つ言語に興味のあるユーザーしか獲得できないでゲソ。
人はいきなりコンパイラの開発者になったりしないものでゲソ。
まずはそのコンパイラのユーザーになって、
そしてコンパイラそのものに興味が出た者が開発者に昇格するのでゲソ。
世の中の人間が、おぬしのように自分が使いもしないコンパイラをいきなりいじりはじめる変態ばかりだったら大変でゲソ」 \newline
「おぬしは今までAjhcに適したドメインにしかコンパイラの応用例を示してこなかったのでゲソ。
それはたしかに有用だったでゲソ。
しかしこれ以上に開発者を増やしたいのであればAjhcコンパイラの適用可能なドメインを広げる必要があるんじゃなイカ？
これまではプロトタイプに必要な機能しかAjhcコンパイラに追加してこなかったじゃなイカ。
つまり曳光弾を使うべきときが来たのでゲソ」 \newline
しかし、そもそもAjhcに欠けている機能はあまりにも多い。
まだ通っていない退行テストがたくさんある。
GHCとプリミティブ型が違うため多くのライブラリはそのままでは移植できない。
Template Haskellも使えない。
どこから手をつければいいんだ？ \newline
「とぼけても無駄でゲソ!
Ajhcに決定的に欠けている機能が、おぬしにはすでに解っているじゃなイカ。
もちろんその機能はkernelを設計する際にも必須でゲソ。
実装できないのであれば、
Ajhcの先にはkernelをスナッチ可能なコンパイラとしての未来はない、ということになるんじゃなイカ？」
三度目のスケッチ: コンテキストを操る

そう、Ajhcの決定的な欠陥。それは コンテキスト が一つしか持てないことだ。
これは最初のスケッチの時からわかっていたことだ。
このままではスレッドを実現できないし、割り込みコンテキストも扱えない。
UNIXライクkernelの中はイベントドリブンの処理が主であることを考えると、
今のAjhcではkernelの初期化処理の一部しかスナッチできないように思えた。
今はkernelをスナッチしているわけではない。そこで、二度目のスケッチをよく観察してみた。
すると、図 \ref{fig:snatchintr} のように既存のC言語コードは二つの部分にわかれていることがわかった。
\begin{wrapfigure}[15]{r}{90mm}
\includegraphics[width=90mm]{figure/masterq/snatchintr.eps}
\caption{二度目のスケッチでスナッチできなかった部分}
\label{fig:snatchintr}
\end{wrapfigure}
二度目のスケッチでスナッチ対象にしていたのはメインコンテキストだ。
このコンテキストが通常の動作では動いている。
しかしクロック例外が起きた場合、即座にメインコンテキストは停止して割り込みハンドラに遷移する。
つまり 受動的コンテキストスイッチ が起きる。
この割り込みハンドラをスナッチするにはコンパイル済みHaskellコードはもちろん、
jhcランタイムさえ 再入可能 でなければならない。
なにせランタイムの関数を実行途中のどの段階においても、
受動的コンテキストスイッチが起きて割り込みハンドラが起動し、
さらには再度実行途中の同じランタイムの関数が再実行されてしまう可能性があるのだ!
少し脱線するが 能動的コンテキストスイッチ というものも存在する。
その例としてはkernelのプロセス切り換えや、ユーザ空間スレッドライブラリのスレッドスイッチ、
それからコルーチンのyieldなどがあるだろう。
今回のCortex-M4のデモの中にはこの能動的コンテキストスイッチは見つからなかった。
ChibiOS/RT ^[ChibiOS/RT free embedded RTOS \hrefT{http://www.chibios.org/dokuwiki/doku.php} ]
のようなスレッドを使うOSをCortex-M4に搭載する場合にはスナッチ対象になる可能性はある。
しかし受動的コンテキストスイッチよりは難易度が低いだろう。
\begin{wrapfigure}[15]{r}{90mm}
\includegraphics[width=90mm]{figure/masterq/switch_ongc.eps}
\caption{GC実行中の割り込みコンテキストへのスイッチ}
\label{fig:switchongc}
\end{wrapfigure}
しかし当然だが複数コンテキストの管理は難しい問題だ。
既にjgcの実装が単一コンテキストを前提にして作り込まれてしまっている。
しかもUNIXライクkernelを実装することを考えると、
スレッド対応だけではなく再入可能も必須だ。
多くの言語処理系は受動的なコンテキストスイッチを受け付けないが、
Ajhcに関してはその逃げは許されない。
さらに割り込み応答のジッターをなくすためにはメインコンテキストがGCを実行している最中でも割り込みコンテキストに受動的に切り換え可能でなくてはならない(図 \ref{fig:switchongc} )。
GCの実行最中で単純に割り込み禁止にすればいいというものではない。
GCの処理時間が長いかもしれないからだ。
もちろんGCを小間切れにする方法もあるが、いずれにせよなんらかの対策が必要ということだ。
もう少しだけ整理して考えてみよう。そもそもコンテキストとはいったいなんなのだろう？
Ajhcの文脈でのコンテキストとはC言語のコンテキスト、もっと言えばCPUのコンテキストのことだ。
CPUは レジスタ を持っており、そのレジスタを変化させることでプログラムを実行している。
近代のCPUではさらにそのレジスタの中にはスタックポインタがあり、
メモリ上の一点を指し示している。
その先のメモリには スタック領域 があり、その中に計算途中のデータが納められている。
なんらかのイベントをトリガーにして、このレジスタとスタックを違うものに入れ代える行為がコンテキストスイッチだ。
能動的コンテキストスイッチではこのトリガーのタイミングはソフトウェア自身で決定できる。
ところが受動的コンテキストスイッチではこのトリガーはソフトウェアではなくハードウェアによって任意のタイミングで起きてしまう。
この"いつトリガーが引かれるのかソフトウェア側からわからない"という点が難題なのだった。
jgc詳細

再入可能を実現するためにはクリティカルリージョンを見つけだして管理することが必要になる。
Ajhcの中ではGCがその主要因であることは間違いない。
もう少しjgcのしくみを詳細に追ってみよう。
jgcのGCルートはいったい何なのだろうか。GCルートの種類によっては排他制御が必要になるはずだ。
ランタイムのgc_perform_gc関数の動作を見てみよう。

GCマーク用のバッファ確保
すべてのcacheの下にあるblockのused bitを0クリア
全StablePtrをマークしてバッファにコピー
GCスタック内のスマートポインタをマークしてバッファにコピー
バッファの後ろからスマートポインタを取り出す
スマートポインタの先にあるスマートポインタをマークしてバッファにコピー
バッファが空でなければ5に戻る
バッファを解放

ということは、主にGCルートとなるのは以下の二つのようだ。

確保したStablePtr
GCスタック (gc変数とgc_stack_baseグローバル変数の間にある要素)

StablePtrの方は簡単だ。
newStablePtr関数によって、
GCが回収しないグローバルなポインタを作った場合、当該ポインタはGCルートになるべきだ。
一方GCスタックというのは何者だろう？
saved_gcとgc_stack_baseという二つのグローバル変数は
Ajhcのランタイムが起動する際にGCスタック領域の先頭を指すように初期化される ^[ \hrefT{https://github.com/ajhc/ajhc/blob/v0.8.0.4/rts/rts/gc_jgc.c#L198} ] 。
つまり最初はsaved_gcとgc_stack_baseは同じ場所を指していたわけだ。
このsaved_gcはAjhcランタイムから呼び出されるHaskellコードのエントリポイントである
_amain関数の先ではgcという引数によって取り回される。
// File: main_code.c (ミューテータ)
void 
_amain(void)
{
        return (void)b__main(saved_gc);
}

static void A_STD
b__main(gc_t gc)
{
        return ftheMain(gc);
}

この引数gcをミューテータがどのように使うかというところが少しややこしい ^[ \hrefT{https://github.com/ajhc/ajhc/blob/v0.8.0.4/rts/rts/gc_jgc.h#L53} ] 。
// File: main_code.c (ミューテータ)
static wptr_t A_STD A_MALLOC
fR$__fJhc_Basics_$pp(gc_t gc,sptr_t v80776080,sptr_t v58800110)
{
    {   gc_frame0(gc,1,v58800110); // <= GCルートにv58800110を登録
        wptr_t v100444 = eval(gc,v80776080);
        if (SET_RAW_TAG(CJhc_Prim_Prim_$BE) == v100444) {
            return eval(gc,v58800110);
        } else {
            sptr_t v106;
            sptr_t v108;
            /* ("CJhc.Prim.Prim.:" ni106 ni108) */
            v106 = ((struct sCJhc_Prim_Prim_$x3a*)v100444)->a1;
            v108 = ((struct sCJhc_Prim_Prim_$x3a*)v100444)->a2;
            {   gc_frame0(gc,2,v106,v108); // <= GCルートにv106とv108を登録
                sptr_t x7 = s_alloc(gc,cFR$__fJhc_Basics_$pp);

\begin{wrapfigure}[15]{r}{90mm}
\includegraphics[width=90mm]{figure/masterq/gcstack.eps}
\caption{GCスタックとミューテータ}
\label{fig:gcstack}
\end{wrapfigure}
このソースコードでミューテータはs_alloc関数かeval関数を呼び出す手前で
GCルートにすべきスマートポインタをgc変数の手前に登録している。
つまりGCスタックにスマートポインタを積んでいるわけだ。
このGCスタックへの登録マクロはgc_frame0という名前だが、
呼び出し前に必ずスコープを新たに作ることが約束事だ。
こうすることで、スコープを抜けると自動的に元のGCスタックが復元される(図 \ref{fig:gcstack} )。
こんな簡単なしくみでGCルートを制御できるということが信じがたいが、
とにかくjhcではうまくいっていたようだ。
おそらくコンパイルパイプラインの中段あたりに秘密があるに違いなかった。
クリティカルリージョンの排他方法

jgcのGCルートのしくみがわかったので、Ajhcのクリティカルリージョンをあらいだしてみよう。
その前にクリティカルリージョンを保護するためのロックについてリストにしておこう。
AjhcはPOSIXの上だけではなく様々なドメインで使えるようでなければならない。

pthread_mutex_lock ^[\hrefT{http://netbsd.gw.com/cgi-bin/man-cgi?pthread_mutex_lock++NetBSD-current}]
NetBSD kernelのmutex_enter ^[\hrefT{http://netbsd.gw.com/cgi-bin/man-cgi?mutex_enter++NetBSD-current}]
CASを使ったシンプルなロック
割り込み禁止
ロックなし

POSIXの上で動かすときはpthread_mutex_lockを使えばいい。
Cortex-M4のようなマイコンでのロックは割り込み禁止で十分だ。
遠い将来NetBSD kernelをスナッチすることになったらmutex_enterに対応させる必要がある。
これまでのjhcと互換性のある動作、つまりpthreadを使わない場合にはロックなしで良いかもしれない。
mutex_enterはAPIが複雑なので対応は後回しにすることにして、
現状ではpthread_mutex_lockに合わせたAjhcランタイムのAPIを定義して、
他のロック機構を使う場合には切り換えられるようにした。
\begin{wrapfigure}[15]{r}{90mm}
\includegraphics[width=90mm]{figure/masterq/2lock.eps}
\caption{割り込みと自コンテキストによる二重lock}
\label{fig:2lock}
\end{wrapfigure}
排他とは言ったが、再入可能についても考えた場合にはただ単にロックすれば良いというものではない。
例えばコンテキストAが処理X中にロックYを獲得していたとしよう(図 \ref{fig:2lock} )。
その最中に割り込みが入り、今度は割り込みコンテキストBが処理Xを再度実行してロックYの獲得を試みたとする。
この時、当然ロックYへの二回目の獲得であるために割り込みコンテキストBはロックYの解放待ちになる。
ところがロックYを獲得しているコンテキストAは割り込みコンテキストBが完了しないかぎりロックYを手放さない。
みごとなデッドロックの完成だ。このとき処理Xは"再入可能ではない"とされる。
スレッドセーフであっても再入可能でなくなってしまうこのような要因をコンパイラで防止することはできないものか？
Haskellコードやランタイムにmutexを使わせることによっていらぬ危険が増えるのは避けたかった。
ぼくは長い時間この問題について考えてみた。
しかしNetBSD kernel mutex_enterについて調べているうちに結論が得られた。
結論として、
この再入時の二重ロックの問題はコンパイラによって解決されるべき問題ではない。
mutexの実装によって防御するか、プログラマが適切に再入時の排他制御を設計する必要がある。
NetBSD kernelのmutex_enter関数は、以下のようなAPIで制御される。
mutex_enter関数はpthread_mutex_lock関数と等価、
mutex_exit関数はpthread_mutex_unlock関数と等価だ。
注目すべきはpthread_mutex_init関数と同じ機能を持つmutex_init関数だ。
属性を指定するtype引数があるところまでは似ているがiplという見慣れない引数が追加されている。
このmutexをロックしている最中はipl引数で指定したレベルまで割り込みが禁止される。
// File: netbsd/src/sys/sys/mutex.h
* void mutex_init(kmutex_t *mtx, kmutex_type_t type, int ipl);
* void mutex_enter(kmutex_t *mtx);
* void mutex_exit(kmutex_t *mtx);

ここで割り込みレベルという聞き慣れない用語が出てくるが、
これはハードウェア割り込みを応答性を求められる順番に優先度分けするものだ。
より応答性が必要な優先度の高い割り込みを禁止している最中はそれより低い優先度の割り込みも禁止される。
ややこしいが、ここでは優先度をつけた割り込み禁止の機構だと理解して問題ないだろう。
例えば、Intel PRO/Wireless 3945ABGの割り込みルーチンを見てみよう。
wpi_attach関数がデバイスドライバの初期化だ。
この中でwpi_intr関数が割り込みレベルIPL_NETで励起されるように設定されている。
// File: netbsd/src/sys/dev/pci/if_wpi.c
static void
wpi_attach(device_t parent __unused, device_t self, void *aux)
{
// --snip--
	sc->sc_ih = pci_intr_establish(sc->sc_pct, ih, IPL_NET, wpi_intr, sc);
// --snip--
	if ((error = wpi_alloc_rpool(sc)) != 0) {
// --snip--
}

static int
wpi_alloc_rpool(struct wpi_softc *sc)
{
// --snip--
	mutex_init(&ring->freelist_mtx, MUTEX_DEFAULT, IPL_NET);
	SLIST_INIT(&ring->freelist);

このwpi_intr関数は割り込みコンテキストで実行されるにもかかわらず、中では以下のようにmutexを使う。
しかし先のwpi_alloc_rpool関数の中でこのmutexはIPL_NET割り込みレベルで初期化されているため、
mutex_enter(&sc->rxq.freelist_mtx)とmutex_exit(&sc->rxq.freelist_mtx)
の区間はアーキティクチャ側でIPL_NETに対応する割り込み禁止をかけた状態になるはずだ。
そのためこのmutexを保持している最中はIPL_NET割り込みによる受動的コンテキストスイッチが起きないことになる(図 \ref{fig:netbsdipl} )。
// File: netbsd/src/sys/dev/pci/if_wpi.c
static int
wpi_intr(void *arg)
{
// --snip--
	if (r & WPI_RX_INTR)
		wpi_notif_intr(sc); // 中でwpi_alloc_rbuf関数を呼ぶ
// --snip--
}

static struct wpi_rbuf *
wpi_alloc_rbuf(struct wpi_softc *sc)
{
	struct wpi_rbuf *rbuf;

	mutex_enter(&sc->rxq.freelist_mtx);
	rbuf = SLIST_FIRST(&sc->rxq.freelist);
	if (rbuf != NULL) {
		SLIST_REMOVE_HEAD(&sc->rxq.freelist, next);
		sc->rxq.nb_free_entries --;
	}
	mutex_exit(&sc->rxq.freelist_mtx);

	return rbuf;
}

\begin{wrapfigure}[14]{r}{90mm}
\includegraphics[width=90mm]{figure/masterq/netbsdipl.eps}
\caption{mutex_enterのiplについて}
\label{fig:netbsdipl}
\end{wrapfigure}
POSIXの上でシグナルハンドラのようなものを使う際にもこのような特別な排他制御をコンパイラの利用者やライブラリ設計者が適切に設定するべきだ。
例えばシグナルハンドラ中で実行可能な関数は制限されるべきだ。
もちろんPOSIXにその制限は明記されている。
もしシグナルを受けた際にその限定されたAPI以外の関数を実行する場合にはsigwait
^[sigwait(2) \hrefT{http://netbsd.gw.com/cgi-bin/man-cgi?sigwait++NetBSD-current}]
でシグナルを受け取る専用のスレッドをプロセス内で一つ作り、適切なスレッドにシグナル受信メッセージを配送すべきだ。
一般化すると、Haskellで書くコードであったとしても、そのコードが受動的コンテキストスイッチを受ける側なのか、それともハードウェアトリガーによって起動される側なのかを意識して設計する必要があるのだ。
コンパイラ利用者がこの制約を受け入れないかぎり、
そのコンパイラはC言語をスナッチするに足る能力を得ることはできない、
というのが今の時点でのぼくの結論だった。
再入可能の実現

コンパイラへの要求がぼんやりと見えてきた気がする。
さぁAjhcのクリティカルリージョンを調べてみよう。
ざっと調べる限りでは以下に大別されるようだった。
これらをコンテキストローカルな配置にすることができないか、
もしそれが不可能であれば排他してやる必要がありそうだ。
A.  ランタイム
1. グローバル変数として確保されるgc_t saved_gc
2. グローバル変数として確保されるstruct s_arena *arena
3. GCスタック
4. megablock
5. struct s_arenaの下に繋がれるstruct s_cache
B.  ミューテータ
1. グローバル変数として確保されるstruct s_cache
2. GCスタックを管理するgc引数
グローバル変数に関してはコンテキスト毎の管理にできないか検討して、
無理であればmutexで排他するしかないだろう。
megablockに関しても複数の利用者がいる場合であればalloc/free時にロックするしかない。
残る問題はGCスタックだ。
\begin{wrapfigure}[15]{r}{90mm}
\includegraphics[width=90mm]{figure/masterq/heapstyle.eps}
\caption{グローバルヒープとローカルヒープ}
\label{fig:heapstyle}
\end{wrapfigure}
思い出してみよう。GCスタックはミューテータによって管理されていて、GCルートになるのだった。
このGCスタックをコンテキスト間で共用することを考えよう。
GCスタックはミューテータのgc変数のスコープによって管理されていた。
変数スコープはコンテキストの外からは知ることが難しい。
そこで退避されているコンテキストの中からスタックポインタを取り出して、
当該スタックの中でスマートポインタに該当しそうなものをGCルートと見做すしかない。
でもこれはBoehm GC ^[A garbage collector for C and C++ \hrefT{http://www.hpl.hp.com/personal/Hans_Boehm/gc/}]
とほとんど同じ処理をすることになる。
もしくは別の案として、GCスタックという領域をC言語のスタックとは別に確保して、
GCスタックへのスマートポインタの追加と削除をグローバルロックで排他する……ナンセンスだ。
もっと高い場所からこのGCルートとHaskellヒープの問題を見渡してみよう。
そこには二つの道が見える。 グローバルヒープ と ローカルヒープ だ(図 \ref{fig:heapstyle} )。
グローバルヒープはこれまで議論してきたGCルートの管理方式だ。
すなわちコンテキストが多数あってもHaskellヒープは唯一一つだけ用意する。
そのためHaskellヒープへの操作は場合によって排他制御する必要が生じる。
もう一つ考えられるのがHaskellヒープをコンテキスト毎に一つずつ持つ案だ。
\begin{wrapfigure}[15]{r}{90mm}
\includegraphics[width=90mm]{figure/masterq/localheap_mvar.eps}
\caption{MVarに繋いだサンクは誰が評価すべきなのか？}
\label{fig:localheapmvar}
\end{wrapfigure}
グローバルヒープのメリットは明確だ。
コンテキスト間で同一のヒープを使っているため、
排他処理さえ気をつければコンテキスト間のサンクの受け渡しがゼロコピーで実現できる。
ほとんどの言語処理系はグローバルヒープを選択している。
しかし、先に見たとおりjgcとの相性は悪いようだ。
Ajhcでグローバルヒープを使う場合にはGCをほぼまるまる再設計する必要がありそうだ。
ローカルヒープを採用した場合にはグローバルヒープとは異なりコンテキスト間でサンクを受け渡すのは難しくなる(図 \ref{fig:localheapmvar} )。
サンクを作る時点ではコンテキストの中のみで消費するのか、
MVarのようなしくみを使って別のコンテキストに渡すために作るのか判別できない。
MVarに繋いだ後にサンクを作ったコンテキストではない別のコンテキストから評価しようとするとややこしい事態になる。
誰がこのサンクを評価すべきなのだろうか？
ローカルヒープにはさまざまな問題が考えられるが、
ぼくはAjhcの再入可能を実現するにあたってローカルヒープを採用することにした。
理由はいくつかあるが最も大きな理由はHaskell言語が状態の共有を嫌う言語だということだ。
グローバルヒープを採用した場合、状態の共有は実現しやすいけれど並列実行に気をつかう必要がある。
ローカルヒープを採用した場合、ロックなしに並列実行を実現できる。並列GCもおまけでついてくる。
メインコンテキストがGC実行中でも割り込みを受けられる。
さらにコンテキストとゴミが紐づいているために、
自コンテキストで出したゴミは自コンテキストのGCペナルティになる。他人に迷惑をかけないわけだ。
もっと考えると、kernelの中はイベントドリブンが主だ。
ということはGCする前にコンテキストそのものが消滅する可能性も高いかもしれない。
コンテキストが消滅したら紐づいていたHaskellヒープをまるごと回収してしまえば良いのだ。
ヒープ回収の時点になってしまえばマーキングする必要もない。
最初のコンテキストの定義を思い出してみよう。
コンテキストとはレジスタとスタックのセットなのだった。
ローカルヒープはこのコンテキストのセットに二つの要素 GCスタック と Haskellヒープ
を追加することに他ならない。
いわばHaskell文脈の中においてだけC言語のABIを拡張していることになる。
こう考えればなんともシンプルな発想だ。
方針は決まった。GCスタックとHaskellヒープをコンテキスト毎に持つように変更しよう。
まず考えるべきなのが管理構造体だ。Haskellヒープはarenaグローバル変数で管理されていた。
このarenaグローバル変数をコンテキストローカルに持つにはgc変数を同じように関数の引数で持ちまわるのが一番簡単だ。
POSIXの外ではスレッドローカルストレージなど使えないからだ。
一見してgc変数とarena変数の二つをミューテータ内の全関数の引数に追加するのは無駄に思えた。
arena変数の1メンバーとしてgc変数を持てば良いのではないか？
しかし調査をすすめてみるとそれほど簡単な問題ではないことがわかった。
arena変数の方は簡単だ。常にコンテキストに対して一つだけ存在し、そのアドレスは変化しない。
しかしgc変数はミューテータ内のローカルスコープによってその具体的なアドレスは変動している。
スコープや関数を抜ければ元の状態が復元されなければならない。
このような復元をコンパイラパイプライン側で実現するのは不可能ではないが、煩雑だ。
また、当然このgc変数の復元にはコストがかかる。
x86のようにレジスタが少ないアーキティクチャはこれから淘汰されることを祈って、ぼくはgcとarena両方の引数をミューテータに追加することにした。
\begin{wrapfigure}[15]{r}{90mm}
\includegraphics[width=90mm]{figure/masterq/arenat.eps}
\caption{s_arena構造体とGCスタックの構造と配置}
\label{fig:arenat}
\end{wrapfigure}
arena変数の構造体を変更しよう(図 \ref{fig:arenat} )。
いままでグローバル変数で定義されていた管理構造体はできるだけarena変数の中に埋め込むべきだ。
linkはarena変数を管理するリスト用メンバーだ。
arena変数はused_arenasかfree_arenasどちらかのグローバルリストに繋がれる。
全コンテキストにメッセージを送りたければused_arenasを辿れば良いし、
新しくコンテキストにarena変数を割り当てたければfree_arenasから取り出せば良いわけだ。
gc_stack_baseメンバーはそのままこれまでのgc_stack_baseグローバル変数の意味そのままだ。
GCスタックの初期ポインタを保存している。
array_cachesとarray_caches_atomicメンバーもこれまでのグローバル変数をそのままarena変数に埋め込んだものだ。
force_gc_next_s_allocというメンバーは"次回のs_alloc時に強制的にGCをかける"というフラグだ。
なぜこんなものが必要になるのかというと、
hs_perform_gcというC言語関数がHaskell標準で決まっているためだ。
この関数はAjhc側のコンテキストを全く知ることなく強制GCを指示する。
そのため、今回の実装ではランタイムをグローバルロックした後で、このフラグを立てる必要がある ^[ \hrefT{https://github.com/ajhc/ajhc/blob/v0.8.0.7/rts/rts/gc_jgc.c#L826} ] 。
そしてHaskellヒープから領域を確保するs_alloc関数の頭でこのフラグの判定して強制GCを実行すればいい ^[ \hrefT{https://github.com/ajhc/ajhc/blob/v0.8.0.7/rts/rts/gc_jgc.c#L573} ] 。
arena変数にはもう一つpublic_caches_pというメンバーが追加されている。
このメンバーはミューテータ側で宣言されるcache管理構造体へのポインタだ。
s_arena構造体の中身はミューテータ側から隠されているが、このミューテータが宣言したcacheだけは見えてほしい。
そのためにこんなややこしいしくみがどうしても必要だった。
ミューテータは以下のようなコードで、コンテキスト起動時にpublic_caches_pメンバーを初期化する。
// File: main_code.c (ミューテータの例)
struct s_caches_pub {
    struct s_cache *cCJhc_Prim_Prim_$x3a;
    struct s_cache *cFR$__fJhc_Basics_$pp;
    struct s_cache *cCJhc_Type_Ptr_Ptr;
};
// --snip--
void
jhc_hs_init(gc_t gc,arena_t arena)
{
        alloc_public_caches(arena,sizeof(struct s_caches_pub));
        find_cache(&public_caches(arena)->cCJhc_Prim_Prim_$x3a,arena,
                   TO_BLOCKS(sizeof(struct sCJhc_Prim_Prim_$x3a)),2);
        find_cache(&public_caches(arena)->cFR$__fJhc_Basics_$pp,arena,
                   TO_BLOCKS(sizeof(struct sFR$__fJhc_Basics_$pp)),3);
        find_cache(&public_caches(arena)->cCJhc_Type_Ptr_Ptr,arena,
                   TO_BLOCKS(sizeof(struct sCJhc_Type_Ptr_Ptr)),0);
}

// File: ajhc/rts/rts/gc_jgc.c
void
alloc_public_caches(arena_t arena, size_t size) {
        if (arena->public_caches_p == NULL) {
                arena->public_caches_p = malloc(size);
        }
}

ちょっとややこしくなってきた。
気分をかえて、ローカルヒープを採用したAjhcでのコンテキストの一生を見てみよう。
AjhcにおけるコンテキストはC言語からの関数呼び出しによって始まる。
C言語からHaskellコードのmain関数を呼び出す際には_amain関数をC言語から呼び出すのだった。
// File: main_code.c (ミューテータ)
void
_amain(void)
{
        arena_t arena;
        gc_t gc;
        gc = NULL;
        arena = NULL;
        jhc_alloc_init(&gc,&arena);
        jhc_hs_init(gc,arena);
        b__main(gc,arena);
        jhc_alloc_fini(gc,arena);
}

\begin{wrapfigure}[14]{r}{90mm}
\includegraphics[width=90mm]{figure/masterq/arenalife.eps}
\caption{gcとarena変数とコンテキストの一生}
\label{fig:arenalife}
\end{wrapfigure}
C言語文脈にはなかったgcとarenaという引数を二つの言語の界面である
export関数で初期化するように変更した(図 \ref{fig:arenalife} )。
jhc_alloc_init関数ではgcとarenaをプールから確保して初期化する。
その後jhc_hs_init関数を使ってミューテータで定義されているcacheを初期化する。
export関数から呼び出されるb__main関数から先はgcとarenaを引数によって引き回す
Haskellコンテキストの世界だ。
b__main関数が完了したら、このgcとarenaは解放される。
もちろんfreeしてしまうのでなく、ランタイム側内部でプールして次回使用時に使いまわす。
このようなarena引数を持ち回るしくみをミューテータに追加するには、
もちろんAjhcのコンパイルパイプラインに修正を加える必要がある。
このarena引数を追加する変更はgrin=>Cへの変換に細工をすれば実現できる(図 \ref{fig:gtoc} )。
compileGrin関数はGrin型をC言語のソースコードが入ったByteString型に変換する。
この関数の頭でC言語ソースコードの構造がansで示されている。
Grin型で定義されている内容をansにつめかえるのがこの変換の役目だ。
ansの個々の要素に関して、修正箇所を見てみよう ^[ \hrefT{https://github.com/ajhc/ajhc/blob/v0.8.0.7/src/C/FromGrin2.hs#L129} ] 。
\begin{wrapfigure}[15]{r}{90mm}
\includegraphics[width=90mm]{figure/masterq/gtoc.eps}
\caption{grin→C変換}
\label{fig:gtoc}
\end{wrapfigure}
最初に変更するべきはjgcsエントリだ。
GCタイプとしてjgcが選択された場合にのみs_caches_pub構造体にミューテータ側で定義するべきキャッシュを列挙することにしよう ^[ \hrefT{https://github.com/ajhc/ajhc/blob/v0.8.0.7/src/C/FromGrin2.hs#L150} ] 。
さらにjhc_hs_init関数の宣言にarena引数を加える。このheaderとbodyはansのエントリだった。
つまりC言語の関数定義をgenerateCに通すとヘッダと本体が得られるのだ ^[ \hrefT{https://github.com/ajhc/ajhc/blob/v0.8.0.7/src/C/FromGrin2.hs#L157} ] 。
Haskell由来のC言語関数全てに第一引数にgcを第二引数にarenaを取ることにしよう。
jhc_hs_init関数の中身はicachesで定義されている ^[ \hrefT{https://github.com/ajhc/ajhc/blob/v0.8.0.7/src/C/FromGrin2.hs#L158} ] 。
ミューテータ側で定義されたcacheはarenaの下のs_caches_pubメンバーに配置することにしたので、
そのように書き換えた。
もし当該のHaskell関数がFFIでexportされていたらgcとarenaの新規割り当てを行なうようにした ^[ \hrefT{https://github.com/ajhc/ajhc/blob/v0.8.0.7/src/C/FromGrin2.hs#L214} ] 。
また場合によってはHaskellコードからランタイムの関数をimportして使いたい時がある。
この時にもgcとarenaを渡す必要がある。
そこでjhc_contextという特殊なimport種別を作った ^[ \hrefT{https://github.com/ajhc/ajhc/blob/v0.8.0.7/src/C/Prims.hs#L22} ] ^[ \hrefT{https://github.com/ajhc/ajhc/blob/v0.8.0.7/src/FrontEnd/ParseUtils.hs#L410} ] ^[ \hrefT{https://github.com/ajhc/ajhc/blob/v0.8.0.7/src/C/FromGrin2.hs#L596} ] 。
\begin{wrapfigure}[13]{r}{90mm}
\includegraphics[width=90mm]{figure/masterq/jhccontext.eps}
\caption{C言語の関数呼び出しにgcとarenaを追加する}
\label{fig:jhccontext}
\end{wrapfigure}
jhc_context付きのimportのおかげで、
gcとarena引数付きでC言語の関数を呼び出せるようになった(図 \ref{fig:jhccontext} )。
exportにも同様のしくみが必要になりそうな気もしたが、
いまのところは明確な用途が見あたらないのでimport側のみの修正にとどめた。
例えばランタイムのgc_new_foreignptr関数は、
これまではHaskell側からgc引数がわたってこないので、
saved_gcというグローバル変数経由でGCスタックへのポインタを受け取っていた。
jhc_contextを使えば、
Haskell側から直にgcとarena引数を任意のC言語関数に渡すことができるようになった ^[ \hrefT{https://github.com/ajhc/ajhc/blob/v0.8.0.7/lib/jhc/Jhc/ForeignPtr.hs#L64} ] ^[ \hrefT{https://github.com/ajhc/ajhc/blob/v0.8.0.7/rts/rts/gc_jgc.c#L781} ] 。
\begin{wrapfigure}[13]{r}{90mm}
\includegraphics[width=90mm]{figure/masterq/thrtype.eps}
\caption{コンパイルフラグによるmutexの実装差異}
\label{fig:thrtype}
\end{wrapfigure}
やれやれ。これであらかたGCスタックとarena変数をコンテキストローカルにできたはずだ。
あとは残ったクリティカルリージョンをmutexで保護するだけだ。
様々なロック機構に対応するため、
図 \ref{fig:thrtype} のように3種類の並列実行に大別してオプションを作った。
将来はもっと増えるかもしれない。
また、ランタイムのグローバルロックのためにmutexをグローバル変数で一つだけ定義した。
ロックを細分化した方がいいかもしれないが、今は簡単な実装にしておきたい。
スレッドの実装

これでコンテキストとコンテキストの分離が実現できた。
ということは割り込みコンテキストのような受動的なコンテキスト切り換えが可能になったわけだ。
もちろん"jhc_mutex_tを適切に設計した場合は"
というただし書きはついてしまうがこれは設計開始当初に受け入れた制約だ。
このままでもシングルコアのマイコンを制御するには当面十分だ。
しかしどうせ再入可能にできたのであれば、POSIX上でのスレッドもサポートしておきたい。
継続的インテグレーション ^[執筆時点ではTravis CIを使っている \hrefT{https://travis-ci.org/ajhc/ajhc}]
することを考えれば、マイコンよりもPOSIX上でテスト可能にした方がいい。
またマルチコア環境でしか起きない不具合も検出できるかもしれない。
\begin{wrapfigure}[15]{r}{90mm}
\includegraphics[width=90mm]{figure/masterq/forkos.eps}
\caption{forkOSをpthreadで実装}
\label{fig:forkos}
\end{wrapfigure}
既にランタイムのmutexはpthreadを使って実装済みなので、
状態共有をしない並列実行であればforkOSをpthread_createを使って作れば十分だろう。
まずランタイム側でpthread_createを使ったスレッド生成の関数を作る。
Haskell側はGHCのforkOS実装を真似てStablePtr経由でIO ()を渡すようにした(図 \ref{fig:forkos} )。
どうもjhcではStablePtrは直接FFIに渡すことはできず、Bang_という型で包む必要があるようだった。
この実装で動きそうに思えるが、なぜかコンパイルエラーだ……
ajhc: Grin.FromE.compile'.ce in function: FE@.CCall.forkOScreateThreadWrapper
can't grok expression: <fromBang_ x108042543::IO ()> x62470112

エラーメッセージを読むかぎりではコンパイルパイプラインの中の
Grin.FromE.compile'.ce関数はfromBang_型を受け取ることを予期していないようだ。
FromEでの評価にはce関数とcc関数の二つの形式がある。
今回のエラーが起きているce関数は正格評価で、cc関数は遅延評価だ。
fromBang_型を受け取るのはcc関数のみで、ce関数には当該のパターンマッチが存在しない。
cc関数でのパターンマッチの前にfromBang_
プリミティブを削除する関数をかませてしまうことにした ^[ \hrefT{https://github.com/ajhc/ajhc/blob/v0.8.0.7/src/Grin/FromE.hs#L365} ] 。
おそらくBang_型は正格にするためのプリミティブだと思われるのでce関数では無視してよさそうだが、多少不安だ。
fromBang_プリミティブについては後付けでもう少し調査が必要そうだ。
さて、いくつかテストを書いてみよう。
最初のテストは三つのスレッドから文字を吐き出すプログラムだ。
これはさすがにうまくいった。
import Control.Monad
import Control.Concurrent

main :: IO ()
main = do
  l <- putStrLn "Type some string and enter." >> getLine
  forkOS $ (forever $ putChar '*')
  forkOS $ (forever $ putStr l)
  forever $ putChar '.'

\begin{wrapfigure}[14]{r}{90mm}
\includegraphics[width=90mm]{figure/masterq/emu_intr.eps}
\caption{割り込みハンドラの動作をpthreadでエミュレーション}
\label{fig:emuintr}
\end{wrapfigure}
次にマイコンと同じような動作をするテストを書いてみた(図 \ref{fig:emuintr} )。
つまり割り込みコンテキストの動作をpthreadを使ってエミュレーションするのだ。
まずC言語側でHaskellコードに隠れてスレッドを生成しておく。
この減算スレッドはHaskellで書かれたtimingDelayDecrement関数を定期的に呼び出して、
TimingDelayグローバル変数が0になるまで減算する。
Haskell側のmyDelay関数は待ち時間が経過するのをビジーループで待ちあわせる。
このテスト実行すると、
減算スレッドのsleepが解除されると同時にmyDelay関数の待ち合わせが解除された。
これでマイコンの割り込みをスナッチする自信がついた。
割り込みコンテキストのスナッチ

今回のスケッチで作った再入可能の機能を使って、
Cortex-M4マイコンの割り込みハンドラをHaskellでスナッチしてみよう。
\begin{wrapfigure}[15]{r}{90mm}
\includegraphics[width=90mm]{figure/masterq/hs_intr.eps}
\caption{割り込みハンドラをHaskellでスナッチ}
\label{fig:intr}
\end{wrapfigure}
図 \ref{fig:intr} はHaskellでスナッチしたクロック割り込みによるdelayの実装だ。
まずマイコンの電源が入るとC言語のmain関数がHaskellのメインコンテキストを起動する。
これまで出てきたように_amain関数がメインコンテキストの入口だった。
この時、Ajhcランタイムはarenaとgcをプールからメインコンテキストに割り当てる。
メインコンテキストは何度かコンストラクタを呼び出すうちに、おそらくは、
二つのmegablockを手に入れるだろう。
このmegablock達の中にメインコンテキストが作ったサンクが納めれれる。
メインコンテキストは電源OFFまでの間終了せず、ずっと滞留することになる。
一方C言語のmain関数がクロックの初期化をすると、
メインコンテキストとは全く関係のないタイミングでクロック割り込みが発生するようになる。
このクロック割り込みが発生するとクロック割り込みベクタに実行が移り、
クロック割り込みベクタはHaskellで記述されているtimingDelayDecrement関数を起動する。
この時、メインコンテキストとは別のHaskellコンテキストを起動したので、
メインコンテキストとは別にarenaとgcがランタイムによって割り当てられる。
クロック割り込みコンテキストが終了すると、
arena,gc,megablockはランタイムによって回収されて次回誰かが使うまでプールに保管する。
もちろん次回このプールからarena達を確保するすのは次のクロック割り込みだろうけれど。
こうしてコンテキストの分離が済んでしまえば、Haskellでの割り込み実装は簡単だ。
C言語側でグローバル変数TimingDelayを用意して、
このグローバル変数をPtr型によってアクセスすればコンテキスト間通信ができる。
さて、長い今回のスケッチで結局Cortex-M4マイコン上で動作するプログラム
^[\hrefT{https://github.com/ajhc/demo-cortex-m3/tree/master/stm32f3-discovery}]
のどこまでHaskellでスナッチすることができたのだろうか？
実行バイナリ内に含まれるシンボルの中で、
Ajhcランタイム、ランタイム用ダミー関数、malloc、Haskellコード由来ではないものを列挙してみよう。

例外/割り込みハンドラ
data/bss初期化コード(アセンブラ)
Haskellスレッド間通信用グローバル変数
クロックの初期化コード
GPIOの初期化コード
LEDのGPIO初期化コード

割り込みハンドラは使っていないものは全部abortだ。
dataとbssの初期化はC言語を使う前にアセンブラで行なう必要があるためHaskell化は不可能。
Haskellスレッド間通信用グローバル変数についてはMVarのようなスレッド間状態共有のしくみを構築すれば解決するだろう。もちろんそれは非常に困難な課題だけれど。
上記以外の初期化コードは全てメモリへの読み書きによって作られている。
ということはPtr型を使えばHaskellでスナッチできるということだ。
つまりCortex-M4マイコン上で動作するソフトウェアに関しては、
限界までHaskellでスナッチする見込みがたったのだ!
突然の連絡

何度目かのAjhcリリースノートを書いていると、携帯のアラームが鳴った。
From J, at 2013年05月25日(土):
会社をやめることにしたよ。きっとjhcの開発に戻れると思う。
いままでメーリングリストで返事ができなくてすまなかった。
それもみんな会社が従業員に個人プロジェクトを持つことを許さなかったからだ。
オレはもう一度jhcのようなオープンソース活動をしてみたい。だからやめた。

J、今まで疑っててごめん。本当はずっと気にかけていてくれたんだね。
ぼくは最初から一人ぼっちじゃなかったんだ。
ふいにあの娘の声が聞こえたような気がする。 \newline
「ああ、わかっているさ。次のスケッチはもう見えている」 \newline
ぼくは思わず独り言をつぶやいた。
これからのこと

結局この一連のスケッチで勝ち取ったものはなんだったのだろう？
一見なにも変化していないように思える。
なにせシングルコアの小さなマイコンで動くソフトウェアを型付けできたにすぎない。
しかしとにかく実際に使われているプログラムを型によって少しずつ再設計できる、
ということは確かめられたようだ。
これからの課題も山積みだが、何が必要なのかは今なら理解できる。

MVarのような型を経由したスレッド間状態共有の実現
ユーザー空間スレッドの実装
Haskell Platform相当のライブラリを移植
cabalのようなパッケージ管理システム
大規模なHaskellプログラムのコンパイル実績
さらなる応用例の提案

おぼろげながら見える。スケッチの糸が遠くデザインへと繋がっている。
ふと目をあげると、まだ見慣れぬ優しい アラフラの海
^[デザインArafura \hrefT{http://metasepi.org/posts/2013-01-09-design_arafura.html}]
が広がっていた。
\begin{figure}[h]
\centering
\includegraphics[width=60mm]{figure/masterq/sunset_bintang.jpg}
\caption{"ビンタンビール"}
\label{fig:bintang}
\end{figure}
参考文献


図 \ref{fig:bintang}: Sunset with Bintang - Copyright (C) 2010 Matteo Catanese All Rights Reserved. ^[ \hrefT{http://www.flickr.com/photos/matteocatanese/5166690955/} ] ^[Licensed under a Creative Commons Attribution 2.0 Generic License. \hrefT{http://creativecommons.org/licenses/by/2.0/} ]
The NetBSD Project \hrefT{http://www.netbsd.org/}
Metasepi Project \hrefT{http://metasepi.org/}
Metasepi Projectの近傍 \hrefT{http://metasepi.org/map.html}
Five-Year Plan for the Metasepi Union \hrefT{http://metasepi.org/doc/20130508\_5year\_plan.pdf}
Jhc Haskell Compiler \hrefT{http://repetae.net/computer/jhc/}
Ajhc - Haskell everywhere \hrefT{http://ajhc.metasepi.org/}
「ファウンデーション」、アイザック・アシモフ著、岡部宏之訳、ハヤカワ文庫