2016年9月12日月曜日

プログラミングにおける演算子と言語の進化に関する思想録

いきなり紛糾から本文を始めてしまいますが、現代において最も幅広く使われている言語の直系の始祖はC言語です。しかし、このC言語は最大にして不可侵の過ちを犯してしまいました。それはそう、"代入演算子"です。
数学における"="記号は"等価"を表します。a = 1という式は、aは1と等しいという意味であり、それ以外の何者でもありません。しかし、あやつ(C言語)はこの記号に代入という新たな意味を割り当て、代わりに等価演算子は"=="という新たな記号を生み出してしまいました。これにより、数学世界とコンピュータ世界の乖離が発生してしまったのです。

この乖離により、コンピュータ言語への入門のハードルが一段階上がってしまったと言えるでしょう。なぜなら、C言語での代入記号の導入により、その血筋を受け継ぐ言語(いわゆるC系言語)においても、"="記号は、代入演算子として使用される羽目となり、その結果、これら後継言語においても数学世界との乖離を生み出してしまったためです。
代入記号の導入により生み出される混乱は以下の通りです。


  1. if文内で数学の"="記号として、この記号を使用する
  2. 実際には代入となるため、左辺の値が変わってしまう
  3. 特にC言語系においては、if文の条件式になんら制約がないので、コンパイルが通ってしまう
  4. 結果、if文内で変数の値が変わってしまい、想定と違う動作をするバグを作りこんでしまう

もちろん、この程度の落とし穴ならば、人間が細心の注意を払えば回避可能ではありますが、現代のコンピュータ業界において、性能の向上は著しいものがあります。このような、多少のコンピュータリソースの消費で回避できうるミスならば、回避できる機構を用意して、使うべきだというのが持論です。
その持論に沿うように、最近作られた言語では、if文の条件式にbool値を返す式しか書けないようになっていたりして対策が施されています。
登場当初は、その万能性から高級言語と呼ばれていたであろうC言語も、今となっては、中級言語と呼ぶべき存在になってしまいました。今後も、言語が進化を続け、ヒューマンエラーの排除を言語が行ってくれるようになるといいですね。

※思想「録」と言いつつ、1エントリーしかありませんσ^_^;

2016年9月9日金曜日

TS LISPソース

どうも、はざまです。
前回の記事で、TS LISPの紹介をしました。今回の記事は、そのTS LISPのソースを全掲載しようと思ったのですが、さすがに長くなりすぎる上に、一覧で見せられても、閲覧性が悪くなるだけなので、その役目はGithubに譲るとして、解説を軽くふわりとするだけに留めようと思います。
中身自体、TypeScriptのコンパイラのバージョンがまだ0.8.*だか、0.9.*の時代に書いたものなので、現在のコンパイラでコンパイルしたら、時代遅れ感が否めませんが、まあ参考になる箇所もあるでしょう。
まあ、解説と言っても、そのファイルが何をしているか概要を説明するだけの簡便なものです。人によっては煩わしく感じるかもしれませんが、お付き合いください。


  • Common.ts - IEnumeratorやDictionaryなど、.NET環境の実行環境で広く必要になる基本的なクラス群を独自定義しています。ただ、このソースを書いた時点のTypeScriptの制限で、ちょっと本物の.NET環境とは異なるメソッド定義になっている箇所があります。新しいTypeScript環境では、解消されているのかな
  • WebHelpers.ts - 見た目をコンソール状にする外部ライブラリ"jqconsole"のラッパと、同じ機能を持つクラスを独自定義しようとしているファイル。ただ、独自実装は、途中で力尽きてます( ;´Д`)
  • ErrorFactory.ts - 様々な種類の例外を投げる"例外ファクトリ"クラスを定義
  • Utils.ts - 全体で必要になる種々のユーティリティ関数群を定義
  • LispTypes.ts - LISPの実行環境となるクラス群を定義
  • Reader.ts - LISPのトークンを識別する文法解析器と"クォーサイクォート"と呼ばれる特殊形式の内部表現を行うクラスを定義
  • LispFunctions.ts - 基本的なLISP関数のネイティブ実装を定義
  • Interpreter.ts - 実際にLISPの処理を行うインタープリタ
  • Snippets.ts - LispFunctions.tsだけでは足りない、よく使われる関数やマクロをLISPとして定義し、文字列で保持するモジュール。load-sample関数で読み込めるS式もこの中に定義されてます
  • main.ts - インタープリタ自体のブートアップを行う処理が記載されている
以上が概要です。こんなほとんど中身のない記事ですが、参考に(?)していただけると光栄です。
今更、なんでこんな記事を書いたのかって怒る方もいらっしゃるかもしれませんね。その理由は、なんとなくとしかお答えできませんε-(´∀`; )

2016年9月7日水曜日

新技術と旧技術の融合

みなさん、ご無沙汰してます。はざまです。
今回は、以前何の目的で作ったかは忘れましたが、作成したLISP処理系の紹介です。といっても、実装内容自体は、完全に借用しているため、そのポーティング程度しか語ることはありません。
そのポーティング先となったのが、今やVisualStudioでも、正式にサポートされ、一線級で活躍していると思われる初期のTypeScriptです。まだ、コンパイラのバージョンが0.8.*だか、0.9.*時代に書いたものなので、今から見ると粗がある可能性も否めませんが、大筋は今の思想と合致しているはずなので、今回、紹介するに至った次第です。これを期に、今後、TypeScriptの記事を増やせていけたらいいな〜とか思ったり、思わなかったり。
Jsdo.itがTypeScriptに対応したとの話も聞くので、修正するなら参考実装もそれに合わせて変更する形になるでしょうかね。
そうそう、Web上で動くLISP実装としての活用もしていただけると、ありがたい限りです。

2016年8月3日水曜日

AppStoreに公開するのになかなか苦労した話

どうも、ご無沙汰になってしまいました。はざまです。
最近になって初めて、App Storeでのアプリ公開を経験し、これについて調べている過程で色々思うことがあったので、メモ代わりに記事を残しておこうと思います。

まず、私の場合、iOS Developer Programに登録するところでちょっとはまりました。本名がローマ字表記すると、2通りの表記ができる名前なので、アカウントの登録時と、Developer Programへの登録申請時に記載した名前の表記が合わなかった結果なのか、自動承認がなされず、サポートに問い合わせる結果となってしまいました。
もっとも、サポートの対応が非常に素晴らしく、1営業日中には返答があったため、特にストレスにはなりませんでした。
この部分に関しては、のちにiTunes Connectを使ってアプリの登録申請を行う際にまで尾を引きます。なので、iDPを申請する際には、アカウントと申請内容を統一しておくことをお勧めします。

そして、アプリ公開申請を行う上で、最大の注意点となるのが、iTunes Connectを使用した申請手続きです。頻繁にiTunes ConnectのUIが変わっているのか、検索で引っかかった手順と実際行った手順が一致したことはほぼありませんでした。こちらで、その手順を逐一記述しても、またすぐに変わってしまうでしょうから、手順の詳細を記述することはしません。
iTunes Connectの申請手順に関しては、手順をググるよりも、公式のドキュメントを参照した方がやりやすいかなと思いました。Appleの場合、ちゃんとドキュメントもローカライズされて日本語のものがリリースされているのもそう思った理由の一つです。

ちなみに、iTunes Connectでのアプリ審査申請から、承認までには1営業日しかかかりませんでした。承認されるまでに2週間もかかったというような記事も見受けられたので、だいぶ、そこら辺個人差があるのかもしれません。

2016年5月15日日曜日

クロージャの変数捕捉タイミングが変わってる!(JS編)

みなさん、こんにちは。また間が空いてしまいました。はざまです。
今回は久しぶりにJSの話題をしようと思います。

今日、昔書いたJSアプリの修正を行っていたのですが、以下のようなコードを書いてみて愕然としました。

jsdo.itの説明文にも書いた通り、コメント内の記法でChromeやSafariで評価を行うと、これまたコメント内のように、関数の実行順とリンクした結果が表示されたんですね。一昔前の挙動は、jsdo.it内のテストコードのように、順繰りにカウントアップされるというものだったんですが、いつからこのような挙動になったんでしょうか。
そもそも、jsdo.it内だと、ループ内にクロージャを定義できなくなっていること、Chrome、Safariともに同じ挙動だったことから、おそらく標準規格が変わったんだと思いますけど、今はそこまで追う余裕もないので、推測だけ記載しておきます。きっと、パフォーマンスの観点から、ループ内に無名関数を定義できなくした上に、既存のコードを吟味して下方互換性を保たなくても大丈夫という判断がなされたんでしょうけど、私個人としては、かなり衝撃的な仕様変更でした。……って、めちゃくちゃ個人的な理由ですね。
ワークアラウンドとしては、例にも示した通り、Function.prototype.bindを使うことです。クロージャを保持するための一時変数が必要になったり、thisにbindするわけでなければ、第1引数にnullを指定しなきゃいけなかったり、クロージャをさっと書けていた時代に比べると、ちょっと不格好なのは否めませんが、ループ最適化でパフォーマンスが向上するのなら、我慢しようといったところでしょうか。

6/7 追記: TypeScriptのマニュアルを読んでいて見つけた別のワークアラウンド。即時実行関数を挟むパターン。例に出している構文も酷似してるし、MS内に私のクローンがいるんでしょうか……

ではでは、またそのうちお会いしましょう^^/

2016年3月13日日曜日

C++プログラマー向けRust 翻訳シリーズ12

クロージャと第1級関数


クロージャと第1級および、高階関数は、Rustの核心部分である。
CとC++には、関数ポインタ(とC++限定で、まったく要領のわからなかった奇妙なメンバ/メソッドポインタとかいうもの)があった。とはいうものの、比較的使われる機会は少なく、さほどプログラマーフレンドリーでもなかった。
C++11でラムダ式が導入され、こちらは、Rustのクロージャに瓜二つのものである。特に、実装方法が似通っているという点でね。

手始めに、これらの概念のさわりに触れておきたい。それから、詳細に移っていこう。

ここにfoo関数があるとしよう。定義はpub fn foo() -> u32 { 42 }だ。
さらに、別の関数barを思い浮かべよう。こちらは、引数に関数を取る(bar関数の見た目は、後述する)。宣言はfn bar(f: ...) { ... }
foo関数をbar関数に、Cで関数ポインタを渡すような感じで与えることができる - bar(foo)
bar関数の内部で引数fを関数かのように呼び出すことができる - let x = f();

Rustには第1級関数が存在すると言う。理由は、関数を持ち回り、他の値同様に使うことができるからだ。
また、関数barは高階関数であると言う。理由は、関数を引数に取る、つまり、関数を操作する関数だからだ。

Rustのクロージャは、書きやすい記法の無名関数だ。|x| x + 2というクロージャは、引数を一つ取り、それに2を足して返す。なお、クロージャの引数に対して型を明示する必要はない(大抵型推論される)。また、戻り値も然りだ。
クロージャ本体が式1つ以上になる場合は、大かっこを使う - |x: i32| { let y = x + 2; y }
クロージャも関数と同じように引数に渡せる - bar(|| 42)

クロージャとその他の関数の大きな違いは、クロージャが周りの環境を保持することにある。これはつまり、クロージャ内からクロージャ外の変数を参照できるということである。

let x = 42;
var(|| x);
変数xがクロージャのスコープ内に存在するあり方に注目してほしい。

以前にもクロージャは見かけてきており、その時はイテレータとともに使用していた。これは、よくある使用方法である。具体例: ベクターの各要素に値を加える。

fn baz(v: Vec<i32>) -> Vec<i32> {
    let z = 3;
    v.iter().map(|x| x + z).collect()
}
ここで、引数xはクロージャに対するものであり、変数vの各要素が引数xとして渡されてくる。変数zは、クロージャの外部で定義されているが、クロージャであるがゆえに参照することができる。また、mapメソッドに関数を渡すこともできる。

fn add_two(x: i32) -> i32 {
    x + 2
}

fn baz(v: Vec<i32>) -> Vec<i32> {
    v.iter().map(add_two).collect()
}
ちなみに、Rustでは、関数内関数も定義することができる。こちらは、クロージャではなく、つまり、環境にはアクセスできない。スコープを限るためにあるようなものである。

fn qux(x: i32) {
    fn quxx() -> i32 {
        x // エラー: 変数xはスコープにない
    }

    let a = quxx();
}

関数タイプ


新しい例題関数を導入しよう。

fn add_42(x: i32) -> i64 {
    x as i64 + 42
}
以前にも見かけたように、関数を変数に代入することができる。例: let a = add_42;
この時、変数aの厳密な型は、Rustでは記述できない。時折、コンパイラがこれをエラーメッセージ内でfn(i32) -> i64 {add_42}と表現しているのを目撃するだろう。
各関数は、各々固有かつ匿名の型を持っている。宣言が同じ見た目でも、fn add_41(x: i32) -> i64は、異なる型になる。

いささか正確でないlet a: fn(i32) -> i64 = add_42などの型名なら、記述することができる。宣言が同じ関数はすべて、fn型に簡約化される(これなら、プログラマが記述できる)。

変数aはコンパイラに関数ポインタとして表現されるが、厳密な型を把握している場合、コンパイラはその関数ポインタを実際には使用しない。a()のような呼び出しは、aの型に基づいて静的に行われる。もし、コンパイラが(fn型であることしか把握していないなど)厳密な型を把握していない場合、呼び出しは値に含まれる関数ポインタを使用して行われる。

Fn型(先頭のFに注目)というのもあり、trait同様、制約である(実際のところ、traitである。いずれわかるだろう)。Fn(i32) -> i64はこのような宣言を持つ関数様オブジェクトの型に対する制約である。関数ポインタへの参照を取得すると、実際には、非正規化ポインタ(DSTの箇所を参照)で表されるtraitオブジェクトを生成していることになるのだ。

関数を別の関数に引き渡したり、フィールドに代入するには、型を記述しなければならない。書き方はいくつかあり、fn型ともFn型とも書くことができる。
このうち、後者の方が望ましい。なぜなら、これにはクロージャ(や可能性として他の関数様のオブジェクト)も含まれるからだ。一方、fn型には含まれない。
Fn型は動的サイズ付けである。つまり、値として使用することはできない。
関数オブジェクトを渡すか、ジェネリクスを使うかのどちらかにしなければならない。まず、ジェネリクスを使う方法を見てみよう。

fn bar<f>(f: F) -> i64
    where F: Fn(i32) -> i64
{
    f(0)
}
関数barは、Fn(i32) -> i64という宣言を持つ関数ならば、どんなものでも受け取ることができる(つまり、Fという型引数に対して、あらゆる関数様の型で実体化することができる)。
bar(add_42)と呼び出して、関数add_42を関数barに渡せば、型引数Fadd_42の匿名型で実体化する。また、bar(add_41)と呼び出しても動作する。

さらに、クロージャを関数barに渡すこともできる。例: bar(|x| x as i64)
これが動作するのは、クロージャの型も宣言に合致するFn型制約に紐づけられているからだ(関数のように、クロージャも各々、独自の匿名型を持っている)。

最後に、関数やクロージャへの参照を引き渡すこともできる。例: bar(&add_42)bar(&|x| x as i64)

関数barは、fn bar(f: &Fn(i32) -> i64) ...とも書くことができる。これら2種のアプローチ法(ジェネリクスと関数/traitオブジェクト)は、全く異なる意味を持っている。
ジェネリクスの場合、関数barは単態化(造語: polymorphize - 多態化の逆から。単射化でもいいか?)され、コード生成時には、コンパイラがfの型を把握できるので、静的ディスパッチされる。
関数オブジェクトを使用しているなら、関数は単態化されない。fの厳密な型がわからないので、コンパイラは仮想ディスパッチコードを生成せねばならない。
後者の方がスピードが遅いが、前者はコード生成量が多くなる(型引数インスタンス一つにつき単態化された関数が一つ)。

実は、Fn型以外にも関数traitは存在する。FnMutFnOnceである。使い方は、Fn型と同じである。例: FnOnce(i32) -> i64
FnMut型は、呼び出し中に可変化できるオブジェクトを表す。これは、普通の関数には適用されず、クロージャに作用してクロージャが環境を可変化できるようにする。
FnOnceは、(最大でも)1回しか呼び出せない関数を表し、こちらもまたクロージャにしか関連しない。

Fn型とFnMut型、FnOnce型は、継承関係にある。Fn型はFnMut型でもあり(Fn型の関数を可変化許可を得た状態で呼び出しても何ら害はないが、逆は言えない)、Fn型とFnMut型は、FnOnce型でもある(通常の関数を1回しか呼び出さなくても害はないが、逆は言えない)。

以上より、高階関数をなるべく柔軟にするには、Fn型ではなく、FnOnce型を使うべきだ(あるいは、この関数を2回以上呼び出す必然性があるなら、FnMut型を使う)。

メソッド


メソッドは、関数と全く同じように使用できる。つまり、ポインタ化したり、変数に代入するなど。ドット演算子は使用できず、メソッド名をフルネーム(UFCS - universal function call syntax ~普遍的関数呼び出し記法~と呼ばれることもある)で記述しなければならない。
self引数がメソッドの第一引数になる。

struct Foo;

impl Foo {
    fn bar(&self) {}
}

trait T {
    fn baz(&self);
}

impl T for Foo {
    fn baz(&self) {}
}

fn main() {
    // 固有メソッド
    let x = Foo::bar;
    x(&Foo);

    // traitメソッド。フルネームで記述していることに注目
    let y = <foo as T>::baz;
    y(&Foo);
}

汎用メソッド


汎用メソッドへのポインタを取得することはできず、汎用関数型を表現する手段も存在しない。しかし、全型引数がインスタンス化されていれば、関数への参照を取ることができる。

fn foo<T>(x: &T) {}

fn main() {
    let x = &foo::<i32>;
    x(&42);
}
汎用クロージャを定義する方法もない。複数の型に作用するクロージャが必要ならば、traitオブジェクトやマクロ(でクロージャを生成すること)を使ったり、クロージャを返すクロージャ(返ってくるクロージャごとに違う型に作用する)を渡せばいい。

汎用ライフタイム関数と超高位型(higher-ranked type)


ライフタイムについて汎用的な関数型やクロージャを存在させることができる。

無所有権参照を取るクロージャを想像してほしい。参照のライフタイムが何であれ、このクロージャは同じ挙動をするが(また、実際のところ、コンパイル済みのコードからは、ライフタイムは消去される)、その型定義はどんな感じだろうか?

fn foo<f>(x: &Bar, f: F) -> &Baz
    where F: Fn(&Bar) -> &Baz
{
    f(x)
}
この時、参照のライフタイムは何になるだろうか?この単純な例では、単一ライフタイムを使用しても構わない(汎用クロージャを使う必要性はない)。

fn foo<'b, F>(x: &'b Bar, f: F) -> &'b Baz
    where F: Fn(&'b Bar) -> &'b Baz
{
    f(x)
}
しかし、変数fに異なるライフタイムを入力できるようにする必要があったらどうだろうか?その場合は、汎用的な関数型が必要になる。

fn foo<'b, 'c, F>(x: &'b Bar, y: &'c Bar, f: F) -> (&'b Baz, &'c Baz)
    where F: for<'a> Fn(&'a Bar) -> &'a Baz
{
    (f(x), f(y))
}
ここでの新規要素は、for<'a>という箇所であり、これは、ライフタイムについて汎用的な関数型を記述し、「すべての'a, ...に対して」と読む。専門用語で言えば、この関数型は普遍定量化されているという。

なお、上述の例で'afooに捕らえさせることはできない。反例:

fn foo<'a, 'b, 'c, F>(x: &'b Bar, y: &'c Bar, f: F) -> (&'b Baz, &'c Baz)
    where F: Fn(&'a Bar) -> &'a Baz
{
    (f(x), f(y))
}
これはコンパイルが通らない。なぜなら、コンパイラがfooの呼び出しに対してライフタイムを推論する際、'aに対して単一のライフタイムを選択しなければならないが、'b'cが異なる場合にはそれができないからである。

このような感じで汎用的な関数型は、超高位型(higher-ranked type)と呼ばれる。上層のスコープのライフタイム変数は、ランク1になる。上記の例の'aは、上位スコープに移動できないため、このランクは2以上ということになる。

超高位関数型の引数を持つ関数を呼び出すのは簡単だ。コンパイラがライフタイム引数を推論してくれる。例: foo(&Bar { ... }, &Bar {...}, |b| &b.field)

実際問題、たいていの場合、そのようなことを気にかける必要さえない。関数引数のライフタイムを省略できるのと同じようにして、コンパイラが定量化されたライフタイムを省略させてくれる。具体的には、上記の例を以下のように書き換えることができる。

fn foo<'b, 'c, F>(x: &'b Bar, y: &'c Bar, f: F) -> (&'b Baz, &'c Baz)
    where F: Fn(&Bar) -> &Baz
{
    (f(x), f(y))
}
(これは不適切な例なので、'b'cしかライフタイムパラメータは必要ない)

Rustにおいて、無所有権参照を含む関数型が認識される箇所には、通常の省略ルールが適用され、この関数型(すなわち、超高位型)のスコープにおいて省略された変数の定量化が行われる。

このような非常に稀な使用例に対して、なぜこんなに悩まされなければならないのかと疑問に思っているかもしれないね。本当のきっかけは、外部の関数から渡されるデータに処理を施す関数を引数にする関数なのだ。

fn foo<f>(f: F)
    where F: Fn(&i32) // 完全明示記法: for<'a> Fn(&'a i32)
{
    let data = 42;
    f(&data)
}
このようなケースの場合は、超高位型が必要不可欠になる。代替手段として関数fooにライフタイム引数を追加したとしても、正常なライフタイムを推論することはできない。その理由を探るために、どのような挙動をするのか見てみよう。fn foo<'a, F: Fn(&'a i32')> ...というものを考えてほしい。
Rustでは、いかなるライフタイム引数も、自分が定義されている文法項目より長生きすることが必須条件になる(このような条件がない場合、このライフタイムを持つ実引数が、その関数内で使用できるが、ここでの存在は保証されないことになってしまう)。
foo関数内で、f(&data)という記述をしており、この参照のライフタイムはコンパイラにより推論され、(最大でも)変数dataが定義された箇所から、この変数がスコープを抜けるまでの間存在する。ライフタイム変数'aは、関数fooよりも長生きせねばならないが、ここで推論されたライフタイムはそうはならないため、このような方法で関数様オブジェクトfを呼び出すことはできない。

ただ、超高位型ライフタイムがあれば、オブジェクトfはどんなライフタイムでも受け取れることになり、&dataの無名ライフタイムも道理が通るので、この関数型もチェックが付くのだ。

Enumコンストラクタ


少し関係のない話をするが、役に立つこともある豆知識を紹介しょう。enumの状態はすべて、その状態のフィールドからenum自体にマッピングする関数を定義している。

enum Foo {
    Bar,
    Baz(i32),
}
これは二つ関数を定義する。Foo::Bar: Fn() -> FooFoo::Baz: Fn(i32) -> Fooというものだ。通常、各状態をこのように使うことはない。状態は関数というよりも、データ型として扱われるのだ。しかし、時として役に立つこともある。具体的には、i32型のリストがあるとして、以下のようにしてenum Fooのリストを作れたりすることだ。

list_of_i32.iter().map(Foo::Baz).collect()

クロージャの風味付け


クロージャは2種類の入力を持つ。明示的に引き渡される実引数と、環境から横取りする変数だ。普段なら、いずれの入力も推論されるので、(訳注: 特に気にかける必要はないが)、必要に応じて細かい制御を行うこともできる。

実引数に関しては、コンパイラに型推論させるのではなく、型を宣言することができる。これは戻り値の型にも適用できる。
|x| { ... }と書く代わりに|x: i32| -> String { ... }と書けばいい。実引数が所有権ありになるか、所有権なしになるかは、(宣言されていようが、型推論だろうが)型によって決まる。

捕捉される変数については、ほとんどの場合、型はその環境からわかっているが、もう少し魔法の呪文があるのだ。捕捉変数が参照渡しになるか、値渡しになるか?
コンパイラは、クロージャ本体からこの情報を推論し、可能な限り、参照渡しをしてくれる。

fn foo(x: Bar) {
    let f = || { ... x ... };
}
すべてがつつがなくいっていれば、クロージャf内で、引数xは関数fooの生存期間を持つ&Bar型になる。
ところが、引数xが可変な場合、捕捉変数は可変参照渡しと推論され、すなわち引数xの型は&mut Barになる。引数xがクロージャf内でムーブ(変数や値型のフィールドに代入されるなど)されていると、捕捉変数は値渡しと推論され、すなわち型はBar型となる。

この挙動は、プログラマーが変更できる(クロージャがフィールドに代入されたり、戻り値になる場合には必要になることもある)。クロージャの前にmoveキーワードを付ければ、捕捉変数はすべて値渡しされるようになる。具体例: let f = move || { ... x ... };と書くと、引数xの型は常にBar型になる。

先刻、関数の種類について話をした。つまり、FnFnMutFnOnceの話だ。今なら、なぜこれらが必要なのか説明がつく。
クロージャにおいて、可変性と呼び出しの唯一性は、捕捉変数にかかるものである。捕捉によって、捕捉された変数が一つでも可変になったら、FnMut型になる(なお、コンパイラにより推論されるものなので、宣言は必要ない)。
変数がクロージャにムーブされていたら、つまり、値渡しになっていたら(moveの明示と型推論によるもの、両方の可能性がある)、クロージャはFnOnce型になる。このようなクロージャを二度以上呼び出してしまうと、複数回捕捉変数がムーブされることになるので、危険である。

コンパイラは可能な限り、クロージャが柔軟な型になるよう、推論を行う。

実装


クロージャは、無名構造体として実装されている。この構造体が、クロージャの捕捉変数を各々フィールドとして格納しているのだ。この構造体は、単独のライフタイム引数を持ち、これが捕捉変数のライフタイムに制約としてかかる。また、この無名構造体はcallという名のメソッドを持ち、これを使ってクロージャを実行する。


fn main() {
    let x = Foo { ... };
    let f = |y| x.get_number() + y;
    let z = f(42);
}
例として、上記のクロージャを考えよう。これをコンパイラは、以下のように解釈する。

struct Closure14<'env> {
    x: &'env Foo,
}

// 実際の実装とは異なる。以下を参照
impl<'env> Closure14<'env> {
    fn call(&self, y: i32) -> i32 {
        self.x.get_number() + y
    }
}

fn main() {
    let x = Foo { ... };
    let f = Closure14 { x: x }
    let z = f.call(42);
}

前述したように、3つの異なる関数traitが存在する。FnFnMutFnOnceだ。現実的には、callメソッドはこれらのtraitが必要とするものであって、実装に固有であるものではない。
Fn型のcallメソッドは、特殊変数selfを参照で取り、FnMut型のcall_mutメソッドは可変参照で、FnOnce型のcall_onceメソッドは特殊変数selfを値で取る。

ここまで見てきた関数型は、Fn(i32) -> i32のような形をしており、あまりtrait型らしくない。ここには、少し秘密の呪文がかかっているのだ。コンパイラは、この丸括弧形砂糖を関数型にしか、かけさせてくれない。通常の型(山括弧型)に精製すると、引数の型がタプルとして扱われ、型パラメータで渡され、戻り値型もOutputと呼ばれる結合型になる。
以上より、Fn(i32) -> i32は、Fn<(i32,), Output=i32>という型に精製されるので、Fn traitの定義は以下のようになる。

pub trait Fn<args> : FnMut<args> {
    fn call(&self, args: Args) -> Self.Output;
}
したがって、上記のClosure14型の実装はむしろこうなる。

impl<'env> FnOnce<(i32,)> for Closure14<'env> {
    type Output = i32;
    fn call_once(self, args: (i32,)) -> i32 {
        ...
    }
}
impl<'env> FnMut<(i32,)> for Closure14<'env> {
    fn call_mut(&mut self, args: (i32,)) -> i32 {
        ...
    }
}
impl<'env> Fn<(i32,)> for Closure14<'env> {
    fn call(&self, args: (i32,)) -> i32 {
        ...
    }
}
この関数traitは、core::opsモジュール内に存在する。

先ほど、ジェネリクスを使用すると、静的ディスパッチになり、traitオブジェクトを使用すると、仮想ディスパッチになる話をした。今なら、もう少しその理由について突っ込んで話すことができる。

callメソッドの呼び出しは、静的メソッドディスパッチになり、仮想ディスパッチにはならない。単態化された関数を渡しても、やはり型は静的に把握できるため、静的ディスパッチになる。

クロージャをtraitオブジェクトに押し込むことができる。具体例: &fBox::new(f)で型は&Fn(i32)->i32Box<Fn(i32)->i32>になる。
これらは、ポインタ型になり、traitを指しているので、非正規化ポインタである。要するに、データ自体を指すポインタとvtable(翻訳者注: C++などで使われる仮想メソッドルックアップテーブルのこと。これとメタデータを用いて、実際に呼び出すメソッドの実装を決定する)を指すポインタで構成されるということだ。vtableを使用して、callメソッド(やcall_mutメソッドなど何でも)のアドレスを参照する。

時として、これら2種のクロージャの表現方法を箱詰め型クロージャや非箱詰め型クロージャなどと呼んでいるのを見かけるだろう。非箱詰め型クロージャは、静的ディスパッチによる値渡し型、箱詰め型クロージャは、動的ディスパッチによるtraitオブジェクト型のものをいう。
かつてRustには、箱詰め型のクロージャしか存在しなかった(また、システムも全く異なっていた)。

参考資料



注: 以下の資料はすべて、英語表記

翻訳者後記: お疲れ様でした。これにて、Rust for C++ programmersブログポストシリーズの翻訳は終わりです。原文にはTODOが記載されていて、今後加筆修正がありそうなため、適宜修正は行うつもりですが、原文とリンクしていなくても怒らないでください。
この記事を通して、一人でも多くのC++プログラマーがRustの利便性や動作原理などを理解していただけたら、翻訳者冥利に尽きます。
なお末筆ながら、この記事により発生した損害、賠償などの責務は当方では負いかねます。予めご了承ください。(訳: この記事の訳語を使用したけど、周りのプログラマーに通じなかったから責任取れなど)


原文: https://github.com/nrc/r4cppp/blob/master/closures.md

2016年3月11日金曜日

C++プログラマー向けRust 翻訳シリーズ11

グラフとアリーナ型メモリアロケータ


(注: この章の例は、このディレクトリをダウンロードしてcargo runコマンドを入力すると、実際に動かすことができる)

グラフ構造は、Rustにおいて非常に厳密なライフタイム管理と可変性管理があるため、いささか構築がめんどくさい。ただオブジェクト指向プログラミングにおいて、オブジェクトのグラフ構造は、非常によく使われるものである。
このチュートリアルでは、グラフ構造の実装方法を数種類提示していこうと思う。個人的には、アリーナ型メモリアロケータを使用し、多少ライフタイムの明示を駆使する方法が好みだ。また最後に、今後Rustに導入されそうな機能のうち、ここで紹介する実装方法の簡略化を行ってくれそうなものについて議論して締めたいと思う。

グラフ構造は、一連のノードとそのノード間を結ぶエッジで構成され、リストや木構造を一般化したものと言える。各ノードは、複数の子や親を持つことがある(尤も、グラフ理論では親子とは呼ばずに、内向・外向という)。
グラフ構造は、隣接するリストや行列で表すことができる。前者は、根本的にはグラフのノードを表すオブジェクトがあり、そのオブジェクトが隣接するノードのリストを持つものである。一方、行列で表す場合は、行ノードから列ノードへの辺があるかどうかを表す論理値の行列を使う。
ここでは、隣接リスト方式での実装方法のみ解説する。隣接行列方式は、Rust固有とは言い難い全く別の問題を抱えているのだ。

本質的には、二種の直交する問題が存在する。どうやってグラフ全体のライフタイムを管理するかと、どうやってその可変性を管理するかだ。

一つ目の問題は、究極的には、グラフ内の他のノードを指し示すのにどんなポインタを使うかという問題に帰着する。グラフ様のデータ構造は、再帰的であるため(たとえ、データはそうでなくとも、型自体が再帰的になる)、完全に値だけでグラフ構造を構築することはできず、何らかのポインタを使わざるをえなくなる。
グラフ構造は再帰的になりうるが、Rustの所有権は再帰的にはできないため、Box<Node>型を使用することはできない(ただ、擬似木構造のデータや連結リストには使用できるけど)。

いかなるグラフも真の意味で、不変たりえない。どこかで円環状になる可能性があるため、一文でグラフを構築することはできないからだ。ゆえに、最低限でも、初期化処理中はグラフを可変にする必要がある。
Rustにおいて、通常、ポインタはすべて固有か不変でなければならないというのは、普遍の真理である。グラフの辺は、(少なくとも初期化中は)可変でなければならず、いかなるノードにも内向する辺が2つ以上存在する可能性がある以上、辺の固有性を保証することはできない。したがって、何かしら幾分高度なことをして、可変性を扱わねばならないわけだ。

解決策の一つとして、可変生ポインタ(*mut Node)を使うことが挙げられる。これは、最も柔軟性の高い手段だが、同時に最も危険でもある。
ライフタイム管理は、型システムのサポートなしにすべて自分で行わなければならない。こうすれば、非常に柔軟で効率的なデータ構造を構築できるが、同時に慎重にならねばならない。
この方法ならば、先ほどのライフタイムと可変性問題は一掃できる。しかし、それは結局、Rustの利点をすべて無視することで得られるものである。つまり、コンパイラの支援を受けることはできない(また、生ポインタは、自動(被)参照しないため、特別人間に優しくない)。生ポインタを使ったグラフ構造は、C++のものと大して相違ないので、ここでは解説しない。

ライフタイム管理には参照カウント(共有所有権、Rc<...>を使用)かアリーナ型メモリアロケータ(全ノードがアリーナに管理された同じライフタイムを持つ、無所有権参照&...を使用)を使用するという選択肢がある。前者の方がより柔軟(あらゆるライフタイムを持つ個々のノードを外部から参照することができる)であるが、後者の方はそれ以外のあらゆる点で勝っている。

可変性管理について、RefCellクラスを使用してRustの動的な内部可変性機構を援用するか、可変性を自ら管理することができる(この場合、UnsafeCellクラスを使用して内部可変性をコンパイラとやりとりせねばならない)。前者の方が安全、後者はより効率的、両者ともプログラマーフレンドリーではない。

なお、円環状になっている可能性のあるグラフがあるのに、Rcクラスを使用している場合、さらなるアクションを行って再帰構造を破り、メモリリークを避ける必要がある。Rustには、Rcポインタを再帰的に保持できるコレクションがないため、グラフ内に再帰構造がある場合、参照カウントが0にならず、グラフは解放されなくなる。
グラフ内にWeakポインタを使用するか、グラフ破棄の時期に再帰構造を手動で破ることで解決できる。前者の方が信頼性が高い。ここでは、どちらも解説しない。例では、単にメモリリークさせる。
無所有権参照とアリーナ型メモリアロケータを使用したアプローチならば、このような問題はないため、その点で優れている。

アプローチの比較のため、例は非常にシンプルに保つ。グラフ内の一ノードを表すNodeオブジェクトに、文字列データ(より複雑なデータの代わり)と隣接ノード(edges)のVecを持たせる。複数ノードを持つシンプルなグラフを作成するinit関数と事前順序付け深さ優先探索を行うtraverse関数を定義する。traverse関数で各ノードのデータを表示する。
最後に、selfが表すノードの最初に隣接したノードへの参照を返すNode::firstメソッドとノードの持つデータを表示するfoo関数を定義する。これらの関数を介してグラフ内部のより複雑なノード操作を行う。

平易になりすぎずになるべく情報量を詰め込めるよう、可能な組み合わせのうち2通りを解説する。参照カウントとRefCellクラスを使用するものと、アリーナ型メモリアロケータとUnsafeCellクラスを使用するものだ。他の2通りの組み合わせは、学習用に残しておく。

Rc<RefCell<Node>>


完全な例はこちら

unsafeコードがないので、こちらの方が安全な選択肢である。また、最も非効率的で人間工学的でもない。ただ、非常に柔軟ではある。ノードが参照カウントされているため、グラフ外での再利用も利くからね。完全に可変なグラフが必要だったり、グラフ自体の存在にかかわらず、ノードが必要な場合は、こちらの手段を取るといいだろう。

ノードは以下のような構造をしている。

struct Node {
    datum: &'static str,
    edges: Vec<Rc<RefCell<Node>>>,
}
新規ノードを作るのは、さほどめんどくさくない。Rc::new(RefCell::new(Node { ... }))と書けばいい。初期化時に辺を追加するには、先頭ノードを可変無所有権参照し、終端ノードをクローン(こうすると、ポインタをコピーし、参照カウントを1増やす。ノード自体はコピーしない)して辺のベクターコンテナに追加する。

let mut mut_root = root.borrow_mut();
mut_root.edges.push(b.clone());
RefCellクラスを使うことで、書き込み時にノードが読み書き中ではないことが動的に保証される。

ノードへのアクセスは、必ず.borrow()メソッドを使用してRefCellクラスを無所有権参照しなければならない。firstメソッドは、無所有権参照ではなく、参照カウント式ポインタを返す必要がある。従って、firstメソッドの呼び出し元でも、無所有権参照せねばならない。

fn first(&self) -> Rc<RefCell<Node>> {
    self.edges[0].clone()
}

pub fn main() {
    let g = ...;
    let f = g.first();
    foo(&*f.borrow());
}

&NodeUnsafeCell


完全な例はこちら

このアプローチでは、辺に無所有権参照を用いる。これは素晴らしく人間工学的だ。こうすれば、主に無所有権参照(なお、Rustの参照カウント式オブジェクトの素晴らしい点は、ライフタイムシステムによく馴染むことにある。Rcクラスへの無所有権参照を作成して、直接かつ安全にデータを参照することができる。先ほどの例において、RefCellクラスのせいでこのようなことはできなかったが、RcUnsafeCellクラスならば可能なはずだ)を対象とするRustの標準的なライブラリを、ノードに対して援用することができるようになるのだ。

また、破棄も正常に行われる。唯一の制約は、全ノードが同時に破棄されなければいけないことだけである。ノードの破棄および、確保は、アリーナで行われる。

他方、わずかではあるが、ライフタイムを明示しなければいけない。残念ながら、ここでライフタイム省略記法の恩恵にあずかることはできない。この節の末尾で、このような事態を改善する言語の進化の方向性を探っていく。

構築フェーズでは、複数参照される可能性のあるノードを可変化するだろう。このようなことは、通常のRustコード内では不可能なので、unsafeブロック内で初期化しなければならない。ノードが可変かつ複数参照されているので、UnsafeCellクラスを使用して通常の不変性原則に依存しないことを、Rustコンパイラに通知するのだ。

では、いつこのアプローチは現実的になるのだろうか?
グラフは、初期化時のみ可変である必要がある。加えて、グラフ内の全ノードは同じライフタイムである必要がある(同時に破棄することが可能であれば、この制約を緩めて後々ノードを追加するようにもできる)。
同様に、ノードを可変化できる時期について、より複雑な不変性原則に依存することもできるが、実装を単純には保てなくなる。プログラマーがそれらの安全について面倒を見なければいけなくなるからね。

アリーナ型メモリアロケーションは、メモリ管理法の一種であり、一まとまりのオブジェクトが同じライフタイムを持ち、同時に解放される。
アリーナとは、メモリ確保と解放を司るオブジェクトである。(個々のオブジェクトごとにメモリ確保するのではなく)ひとくくりに巨大なメモリ領域が確保されたり、解放されたりするため、アリーナのメモリ確保は非常に効率的だ。
通常、オブジェクトはすべて連続したメモリ領域に確保される。そうすれば、グラフを辿る際のキャッシュ利用効率が上がる。

Rustにおいて、アリーナ型メモリアロケーションは、libarenaでサポートされ、コンパイラ全体で活用されている。アリーナには二種類ある。型付けアリーナと型なしアリーナだ。
前者の方が、効率的で使いやすいが、ある型のオブジェクトしか確保できない一方で、後者ならば、より柔軟でどんなオブジェクトでも確保することができる。
アリーナで確保されたオブジェクトは、すべて同じライフタイムであり、このライフタイムはアリーナオブジェクトのパラメータになる。型システムにより、アリーナにより確保されたオブジェクトへの参照が、アリーナ自体よりも長く生き残り続けないことを保証してくれる。

さて、ノード構造体にグラフのライフタイム('a)を含める必要が出た。隣接ノードのVecコンテナをUnsafeCellクラスで包んで、不変であるはずのVecコンテナを可変化できるようにする。

struct Node<'a> {
    datum: &'static str,
    edges: UnsafeCell<Vec<&'a Node<'a>>>,
}
new関数もこのライフタイムを使用し、メモリ確保を行うアリーナオブジェクトを引数に取らなければならない。

fn new<'a>(datum: &'static str, arena: &'a TypedArena<Node<'a>>) -> &'a Node<'a> {
    arena.alloc(Node {
        datum: datum,
        edges: UnsafeCell::new(Vec::new()),
    })
}
アリーナオブジェクトを使ってノードオブジェクトのメモリ確保を行っている。グラフのライフタイムは、アリーナオブジェクトへの参照から派生している。そのため、アリーナオブジェクトは、グラフのライフタイムを包括するスコープから渡す必要がある。今回の例で言えば、initメソッドに渡すことを意味する。(表記上のスコープ外で値を生成できるように型システムを拡張することが考えられるが、今すぐ実装の予定はない)。
アリーナオブジェクトがスコープ外に抜ければ、グラフ全体も破棄される(Rustの型システムにより、この時点以降までグラフへの参照が残らないことが保証される)。

辺の追加方法は少し趣が異なる。

(*root.edges.get()).push(b);
本質的には、root.edges.push(b)を呼び出してノード(b)を辺のリストに追加しているだけである。とはいえ、edgesフィールドがUnsafeCellクラスに包まれているため、get()を呼んであげる必要がある。こうすると、辺への可変生ポインタ(*mut Vec<&Node>)が得られ、edgesフィールドを可変化することができる。ところが、これはこのポインタを手動で被参照しなければいけないこと(生ポインタは自動被参照できない)でもあり、(*...)と書いているのだ。
最後に、生ポインタの被参照は非安全なので、全体をunsafeブロックに入れ込む必要がある。

traverse関数の気になる箇所は以下の通りだ。

for n in &(*self.edges.get()) {
    n.traverse(f, seen);
}
辺のリストを取得するのに先ほどと同じ手順を踏んでいるため、unsafeブロックが必要になる。この場合、実際には安全である。なぜなら、すでに初期化は完了しており、可変化処理がないからだ。

さて、firstメソッドもリストを取得する手順は同じであり、unsafeブロックが必要になる。ただ、Rc<RefCell<_>>を使用したグラフとは対照的に、ノードへの単純な無所有権参照を返せばいい。とても便利だ。どこにも可変化処理がなく、初期化済みのため、このunsafeブロックは安全だと推論できる。

fn first(&'a self) -> &'a Node<'a> {
    unsafe {
        (*self.edges.get())[0]
    }
}

このアプローチに対する将来的な言語の改善点


Rustにおいて、アリーナ型メモリアロケーションと無所有権参照の使用は、重要なパターンと考えられる。言語に改良を施して、これらのパターンをより安全に使いやすくするべきだ。アリーナの使用がメモリアロケータに対する現在進行中の改良によって、よりプログラマーフレンドリーになることを願っている。
その他、著者が把握している改良点は3つある。

安全な初期化処理


オブジェクト指向の世界では、初期化時のみ可変性を保つ機構に関して多数の調査が行われてきた。一体、この機構がRustでいかように作動するかは、未解決な疑問だが、可変ではあるが固有ではなく、スコープに閉じられたポインタを示す必要があるということのようだ。そのスコープ外では、既存のポインタはいかなるものであっても、通常の無所有権参照、つまり、不変か、固有になるのだ。

そのような機構の利点は、初期化時は可変で、それから不変になる一般的なパターンを示す手段ができることにある。また、これは、個々のオブジェクト自体は、複数所有されているものの、その集合全体(今は、グラフ)は単一所有されているという普遍的原則にも依存している。
こうすれば、UnsafeCellクラスとunsafeブロックの必要なく、参照とUnsafeCellクラスを使用するアプローチを適用することができるようになり、この手段がよりプログラマーフレンドリーかつ安全なものになる。

ETH Zurich(訳注: 大学名か何か?)のAlex SummersとJulian Viereckが、これを追求している。

汎用的なモジュール


グラフのライフタイムは、いかなるグラフでも定数になる。ライフタイムを繰り返し記述するのは、冗長でしかない。
これをプログラマーフレンドリーにする一手段は、グラフのモジュールにライフタイムのパラメータを持たせられるようにすることだ。そうすれば、struct、impl、関数ごとに記述する必要がなくなる。
それでも、グラフのライフタイムは、モジュール外から指定する必要があるが、たいていの場合、推論でなんとかなる(今日、関数呼び出しではできている)と好ましい。

モジュールがどんな見た目になるかは、ref_graph_generic_mod.rsを参照されたし。((上記で確約されている)安全初期化処理を援用してunsafeコードを排除することもできるはずだ)

また、このRFC issueも参照されたし。

この機能によって、参照とUnsafeCellクラスアプローチのコードの重複箇所が大幅に削減されるだろう。

ライフタイム省略


現時点で、プログラマーは関数定義のライフタイムを一部省略してプログラマーフレンドリーにすることができる。グラフに対して&Node型を使用するアプローチが、いささか見目麗しくない理由の一つは、ライフタイム省略記法を使用していないからだ。

Rustにおいてよく使われるイディオムに共通ライフタイムを持つデータ構造がある。そのようなデータ構造への参照は、&'a Foo<'a>のような型を立てる。具体例: グラフの例では&'a Node<'a>
このようなケースに役に立つ省略記法があると便利だが、どんな挙動をすべきかは確信が持てない。

汎用モジュールの例を見ると、さほどライフタイム省略記法を拡張する必要はないようだ(Node::newメソッドがライフタイムを与えられなくても動作するか皆目見当がつかないが、仮にそうであっても、ほんの些細な拡張を施すだけで、動作するようになるだろう)。
スコープ内で唯一のときは、モジュール全体で('static以外の)ライフタイムを省略できる何らかの新しいルールを追加したくなるかもしれないが、スコープ内に複数のライフタイムがある場合(fooinit関数を参照)の挙動が読めない。

汎用モジュールを追加しなくても、&'a Node<'a>という書き方に特化した省略記法を導入する可能性はある。まあ、どう実装するのかは知ったこっちゃないけど。


原文: https://github.com/nrc/r4cppp/blob/master/graphs/README.md