2019への参加レポートとして、私の印象に残った発表を紹介します。今回は、Gibbonという、GHC以外のHaskell(の、サブセット)の処理系についての発表です。UniversityGibbonは最適化の手法を研究するために作られたコンパイラーです。具体的には、我々(特にHaskeller)がよく使う、木構造全体に対する処理の最適化です。した木構造のデータは、通常ポインターを使ってメモリー内にバラバラに格納されますが、Gibbonによる最適化を行うと、実際にプログラムがどのような順番で木を処理しているのか解析して、(元のデータ構造を配列に変換した上で)その順番に並べられた配列として処理するコードに変換する、という大胆な変換を行います。図にするとこんなイメージでしょうか?変換前の木構造。Gの順)でアクセスする👆における、赤い線の順番(行きがけ順)にアクセスする関数があったとします。適当にHaskellの再帰関数として書くと、👇こういうコードです。👆のような、ただの配列(とそれに対する関数)にまとめて変換してしまう、というのです!現代のコンピューターは、このような配列の要素にまとめてアクセス処理する方が、ポインターをたどって各要素を処理するより、たいてい遙かに速いです。Gibbonはこの特性を活かすべく、我々Haskellerが好んで使うような、ポインターだらけの木構造を可能な限り配列に変換することで、要素をまとめて処理する(traverseする)演算の最適化を図るコンパイラーです。ちなみに、元の木に対するノードの追加に相当する処理は、新しいノードに対するポインターを書き込む処理に変換するそうです。何度も追加を繰り返すと、あまり恩恵が受けられなくなってしまいそうです。興味深いアイディアですが、個人的に聞きそびれた疑問が2つあります。一つは、そもそも木構造を定義するような状況というのは、いろいろな順番でアクセスしたいし、新しい要素の追加も繰り返し行いたいケースではないでしょうか?例えばunordered-containersにあるHashMap型は探索木を使った頻繁に使われるデータ構造ですが、HashMapを使う場合に行う処理の多くは、ランダムアクセスや要素の追加・削除でしょう。Gibbonが最適化したい「木構造」というのは、どちらかというと探索木のような木ではなく、構文木のような、要素をまとめて処理することを前提とした木のことなのかもしれません。確かに人間が書く言語の構文木程度であれば、すべてメモリー上で処理できる程度のサイズに収まる(という想定でなければコンパイラー作りがものすごく難しくなる)でしょうし、構文木の処理を高速化できれば、遅い遅いと言われるGHCのコンパイル速度も高められるはずです。それはそれでありがたい。n)からO(1)に変わるわけですし、要素をまとめて処理する以外の演算についても劇的な改善が見込めるかもしれません。これも先ほどの推測が正しければ無意味な想像ですが、夢のある話ですね。Gibbonは将来的には、Packedという型クラスを提供することで、GHC本体への統合も視野に入れているそうです。Packedを実装した型は、値をどのように配列に変換するのか定義することで、Gibbonによる最適化のためのヒントを与えることができます。ライセンスの下に提供されています。Analyticsでアクセス情報を収集しています。集めた情報は統計的に処理した上で、当ウェブサイトの改善のための参考情報としてのみ使用します。