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

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:実際には宣言される

(故)insLTのチラ裏 #coinsLT

この記事は LT Advent Calendar 2016 - Adventar 11日目の記事です。 前回は id: yagamian_sobaya さんの「今年やったLT」でした。次回の記事は間が空いていて謎なので、更新され次第追記したいと思います。

こんにちは id: everysick です。現在は筑波大学情報科学類でほのぼの生活しています。 今回は coinsLT について1, 2年前に何をしていたのか、今はなぜ開催されていないのかなどの話をだらだら書き、引き継ぎたい旨を伝えたいと思います。 色々端折りつつ時系列を追って説明していくと思うので、よろしくお願いします。

ちなみにcoinsLTに関して、私は書類出したりconnpassを編集していた主催側の人間であったことだけ明記しておきます。


皆さんは筑波大学を知っていて、LTが何なのかというのもご存知かと思います。 筑波大学でのLTは学類ごとに任意の学生が開催しており、coinsLTも情報科学*1のLTとして開催をしていました。 学類ごとと言ってもほぼ非公式*2であり、発表時間が長いなどLTとしてグレーなイベントもありました。 学類LT文化の発祥は正しく語れないような気がするので話題にしませんが、少なくともcoinsLTではありません。

coinsLTが発足したのは2014年5月ごろ、当時mastやesysがLTを開催している中、coinsLTがあってもいいよねなどの話があり*3、 その年に入学したての複数名で適当な団体名をでっちあげて開催を決定しました。開催の際に教員の署名が必要なのですが、 当時特に宛もなかったため、クラス担当の教員へお願いしたところ「問題は起こさないでね…?」とのことであっさり貰えていた記憶があります。 そんなこんなで開催が一月後に決定したんですが、登壇者を募う、当日投影用のプロジェクターやマイクを確保する、 発表題目を登壇者から集めてタイムテーブルを作る、開催の周知をするなど、ちょっと手間がかかったりしました。

LT自体は盛況で、#11回まで開催が続いていたのですが、主催者がなんらかの事情で忙しくなるなどのことがあり、 2015-12-02 の開催をもって一年ほど開かれていません。


長くなりましたが本題はここからで、旧オーガナイザーによってcoinsLTは現在名前をオープンに貸し出していて、 forkしてPullrequestを送るだけ*4で開催可能になっています。

github.com

しかし開催するっていっても何を準備する必要があるのかなど、結局面倒くさいことは共有していないわけで、 そういうところを書くので、若い力で盛り上げてほしいというのがこの記事の目的です。

開催ノウハウ

まず前提として、主催一人は完全に厳しいので、3人ほど集めると良いです。 ただ、当日配信したい場合などはもっと人が必要だと思います。 機材脈のある人、喋れる人、開催周知できる人、書類仕事できそうな人などですかね。

開催に向けて難しいことは3つほどあるのでそれぞれ書いていきます。

書類

教室を借りたり会を開催したりするのには学生事務へ事前に申請が必要です。 「学生集会願」という書類を手に入れて申請し、空いている教室を確保するなどのことをします。 書類には以下のような項目を記載する必要があったような気がします。

  • 参加人数
    割りと適当でもどうなかなるので、前回のconnpassの人数でも書いておきましょう。 余談ですが、なんだかんだconnpassなどで集めた人数の3倍は集まるのでその気持ちでいましょう。
  • 開催日時/開催教室
    実は教室は別途借りる必要があるのですが、書類提出時にしか借りられないため、日程と教室の確保は気をつけましょう。 また、教室が閉まる時間は21時と固定されているので、放課後の開催はぎりぎりにならないようにしましょう。 おすすめの教室は3A402です。広いし全席電源あるし階段教室で見通しが良いからです。
  • 責任者名
    オーガナイザーの名前でも書くといいでしょう。
  • 開催概要
    概要などが適当であったり、遊戯目的での開催であることが記載してあると(教員や事務に)嫌な顔をされる恐れがあります。 できるだけ真面目な文章でLTの概要をまとめつつ、「情報科学に関する理解や知識を〜」などと書いておくと良いと思います。

ちなみにconnpassなどは日付と教室が決定するまで適当な未来に時間を設定しておいて 開催の気持ちを表明しておくと良いと思います。 逆に日付や教室を先に周知するとリスケが面倒だったりするため、書類先行をおすすめします。

署名

実は「学生集会願」には教員の署名を貰わなければならないため、学生だけで開催することができません。 過去開催では御二方の教員に署名をお願いし、承諾をいただいていますが、 そもそもこんな怪しい会に関して誰でも署名をしてくれるわけではありません。 できるだけ仲の良い、物分りの良さそうな教員の方にお願いしましょう。 (深い意味はありません)

道具

教室の貸出が決定しても備品を借りることは難しいです。なんと学生には貸出をしてくれないのです。 大まかに必要なものは4つあります。ただ、教室によってもしかしたら元々置いてあるものを使えるかもしれませんが、 破損するなど問題になると大学生活に支障がでるため、できるだけ避けましょう。

  • プロジェクターと周辺ケーブル
    本来教室にあるものは使えないので、自前で用意する必要があります。また、ケーブル類はPCまでの長さが必要なので 下見をして長さを把握しておきましょう。
  • マイクと周辺ケーブル
    生の声だと厳しい場合があるため、マイク・周辺ケーブルを用意して使用できるかテストも行いましょう。
  • 喋る人
    司会進行
  • タイムキーパー
    5分経ったら強制終了させるために時間を見る人と合図をしてなんらかの音を用意する人が必要です。

ざっと書きましたが、たぶん最低限これくらい知っておくと開催できるかと思います。 何か不明点がありましたら、コメントやリプライを送っていただければお答えします。 雑な気持ちでやっていくのが重要です。

関連リンク

coinsLT

coinsLT #0 : ATND

coinsLT #1 - connpass

coinsLT #10 - connpass

coinsLT #11 - connpass

coinsLT - YouTube

*1:College of Information Science 略して coins. この略称は大学公式

*2:公式で開催しているところを知らない

*3:きっかけ覚えてない

*4:README参照

就活を目的させていただきます

参加記 日報 雑記

こういうのに行ってきた❗️❗️❗️

cdgh.connpass.com

就活目的レンジャー藍色 

f:id:everysick:20161118220234j:image

内容がオフレコすぎて何も書くことができない

f:id:everysick:20161118220241j:image

また次も別の企業主催でもあるらしい

f:id:everysick:20161118220604j:image

 

まともな日本語が出てこない

開催していただきありがとうございました

 

ps. 渋谷に来た

f:id:everysick:20161118222445j:image

 

つづきをよむ

http://diary.hatenablog.jp/entry/2016/11/18/215539

http://polamjag.hatenablog.jp/entry/2016/11/18/222830

http://osyoyu.hatenablog.com/entry/2016/11/18/222820