読者です 読者をやめる 読者になる 読者になる

Region based mini ml - intro

Algorithm 開発

この記事は 言語実装 Advent Calendar 2016 - Qiita 20日目の記事です。 introと書いてあるのは、この内容で通年講義を受講しており、その最終発表が1ヶ月後くらいにあるため、 実装に関する部分などは別途記事化する予定でいるからです。 言語実装アドベントカレンダーに載せるのはこのintroのみなので、 それ以降はアドベントカレンダー関係なく、別途タイミングを見計らって投稿します。


今年度、大学の単位認定と自主学習を含めてRegion推論を導入したMLのサブセットを実装しています。 きっかけとしては、昨年度言語実装アドベントカレンダーに投稿されていたRegionの記事*1はてブから発掘し、 学習量として良さそうなテーマだなぁと思ったのが始まりです。

事始めとして、Regionを元にしたアイデアを扱う論文である以下を読み進めました(長かった…)。

Region-Based Memory Management

とりあえず読んでいたのですが、実は下記の論文のほうが良かったのではないか疑惑があったりしました。

A Region Inference Algorithm

前者の論文ではRegionの考え方など導入的な部分から多相型、推論に至るまで必要最低限のことが記載されているのに対し、 後者ではRegion推論そのものを扱っているので、詳細度が違うんですよね。ただ、前者だけでも実装はできそうな気がします(終わってないんですが)。


本題に入りますが、論文の内容を少しなぞりつつ、Region推論するにあたって予備知識などの準備事項を書いていきます。 個人的な解釈や、論文実装を拡張した構文などが出て来る場合もあるため、全て元の論文と同様の説明をしているとは限りません。

Region の考え方

世の中には多彩なプログラミング言語があって、それぞれ異なった機能を持っています。 その中で計算資源であるメモリに対して観点を向けたときに言語はどのようにメモリを扱っているでしょうか。 言語によってはmalloc, freeなどの領域確保のためのAPIを使用しているものもあればGarbage Collectionを用いて 必要・不必要の判断を言語機能に載せているものもあります。 Region推論 はそういったメモリの扱いを静的に決定し、実行時に(できれば)最適なメモリの割り当てをしよう という考えのもとで発案された手法です。

そもそもの話になりますが、ここで扱うRegionというのは、大雑把に名前付きStack領域を指すもので、その名称には良く  {\rho} が使用されます。 その {\rho}が指す領域には、整数値・実数値・文字列といった、上記での計算資源に格納すべき要素を保存します。 また、 {\rho}には、どこで確保され、どこで解放されるかといった情報が付随します*2。 そのため、 {\rho} が必要になるまではメモリの準備が必要無く、 {\rho}が不必要になればメモリは解放されます。 つまりプログラム全体として、この要素はどこで確保され、どこで解放されるかが明示されます。

Regionの注釈を記述する方法は二種類あります。大雑把に説明すると、 一つ目の式は整数値やラムダ式など、Storableな要素に対してRegionの注釈をつける方法です。 二つ目の式は式全体としてRegion変数の導入をし、そのRegionに紐付いている要素の生存範囲を記述するものです。

e1 at r1
letregion r2 in e2 end

今回扱うML方便の言語では、以下の例文のように、Storableな要素をRegionに割り当てていきます。 ここで詳しくは説明しませんが、あくまで一例としてこのように記述するものと認識してください。

(* already allocated three regions : r1, r2, r3 *)
letregion r4, r5 in
  letregion r6 in
    let x = (5 at r2, 3 at r6) at r4 in
      (lambda y -> (#1 x, y) at r1) at r5
    end
  end
  5 at r3
  (* do anything *)
end

推論結果によっては上記のようにRegionが適切に割り当てられるとは限りません。 アルゴリズムによってはRegionが全て大域に紐付いてしまうこともあります。

また、ここの節では説明はしませんが、純粋にRegionを割り当てるだけでなく、 Regionに対しても多相を導入し、関数の引数や返値のRegion割り当てにも行うことが可能です。 後半に書く予定であるTranslationの部分にて詳しく説明します。

Region 推論 前準備

上記で説明したRegionを、推論アルゴリズムを用いて決定することができます。 大まかに方針を説明すると、ありがちなML構文を規則に従ってregion注釈の付いた方便へとtranslationをしていきます。 説明を簡易化するため、元言語をSource Language(以下 SExp)、変換後をTarget Language(TExp)とします。

SExp

SExpは以下のgrammarで定義されます。

e := c 
     | x 
     | (lambda x. e)
     | e1 e2
     | let x = e1 in e2 end
     | letrec f(x) = e1 in e2 end

型定義も単純な Damas and Milner (1982) の MLtype, ML type scheme を活用します。

{
\tau^{ML} ::= int \ | \ \alpha \ | \ \tau^{ML} \rightarrow \tau^{ML}
}

{
\sigma^{ML} ::= \forall \alpha_{1} \cdots \alpha_{n} \tau^{ML}
}

というように何の変哲もない定義であるため、これ以上のSExpの説明に関しては割愛します。

TExp

TExpは以下のgrammarで定義されます。 もちろん先程例示したコードも生成可能です。

e := c at r
     | x 
     | f [r_1, ... , r_n] at r
     | (lambda x. e) at r
     | e1 e2
     | let x = e1 in e2 end
     | letrec f[r_1, ..., r_k](x) at r = e1 in e2 end
     | letregion r in e end

型定義に関しては書き換えの項目で一緒に説明します。

Translation

SExpからTExpへの書き換えは、SExpの型に対してRegion, Effect, ArrowEffectといった注釈を追加し、 決定可能な規則に基いて適用を行います。ここからが一番長い部分ですので、 この記事では一旦ここまでとして、次回書き換え部分の説明を書いていきたいと思います。

予定としては、記事をあと2, 3回に分けてそれぞれ

  • Translation(年内, 年明けてから)
  • Translation実装(1/12以降)
  • TExpステップ実行(1/12以降)

を説明できればなと思います。実装の公開は訳あって1/12以降となる予定です。


参考

Region based memory management, Mads Toftea, Jean-Pierre Talpinb

リージョンについて | κeenのHappy Hacκing Blog

*1:参考参照

*2:実際には宣言される