Rustで圏論(3) 圏はトレイトでは？

前回の話

前回、同型かどうかを判断するコードの中に間違いがあるという話を書きました。 中心となる処理は以下です。

    fn is_isomorphism(&self, object1: &str, object2: &str) -> bool {
        self.has_arrow(object1, object2) && self.has_arrow(object2, object1)
    }

与えられた2つの対象でf: A->Bとg: B->Aの射が存在していれば、同型である。 と書いてあるように見えるんですけど、これだと全然定義通りじゃなかったですね。すいません。 f;g = 1A かつ g;f = 1Bじゃないとダメです。そもそも、射の合成も恒等射もないですし。

そもそも、圏はstructじゃなくてtraitなのでは

話題が変わってしまいますが、当初はstructでCategoryを定義したものの、これだとあんまりしっくりきません。 「圏というもの」が存在する、というよりはいろんなものが「圏と見なせる」というケースが多い気がするためです。 というわけで、structではなくtraitで実装し直してみました。今度は圏の定義に忠実に。

use std::cmp::PartialEq;

trait Category {
    type Object: PartialEq;
    type Arrow: PartialEq;

    fn domain(&self, f: &Self::Arrow) -> Self::Object;
    fn codomain(&self, f: &Self::Arrow) -> Self::Object;
    fn identity(&self, a: Self::Object) -> Self::Arrow;
    fn composition(&self, f: Self::Arrow, g: Self::Arrow) -> Option<Self::Arrow> {
        if self.codomain(&f) != self.domain(&g) {
            None
        } else {
            Some(self.composition_internal(&f, &g))
        }
    }
    fn composition_internal(&self, f: &Self::Arrow, g: &Self::Arrow) -> Self::Arrow;
    fn ci(&self, f: &Self::Arrow, g: &Self::Arrow) -> Self::Arrow {
        self.composition_internal(f, g)
    }

    fn objects() -> HashSet<Self::Object>;
    fn arrows() -> HashSet<Self::Arrow>;

    fn associativity(&self, f: Self::Arrow, g: Self::Arrow, k: Self::Arrow) -> bool {
        self.ci(&self.ci(&f, &g), &k) == self.ci(&f, &self.ci(&g, &k))
    }
    fn unit_law_domain(&self, o: Self::Object, f: Self::Arrow) -> bool {
        self.ci(&self.identity(o), &f) == f
    }
    fn unit_law_codmain(&self, o: Self::Object, f: Self::Arrow) -> bool {
        self.ci(&f, &self.identity(o)) == f
    }
}

下の3つは公理なんですが、証明系の言語ではないので、定義したものの使いどころがわからない。 traitをimplementする側が保証しないといけないわけです。Haskellの型クラスもそうですね。 具体例も徐々に書いていきましょう。

Rustで圏論(2) マクロで独自記法

【要訂正】同型を判断したい

前回は圏を構造化したところまででした。というわけで、そこから様々なことを調べられるようにしたい。 手始めに、同型かどうかを調べる関数を追加した（関数名がダサいのは気にしないでください）。 しかし、実はこの関数の中身は大きく間違ってるんですけど、お分かりでしょうか。 修正したのは次回、出します。

独自記法をマクロで書く

最初はCategory::newを普通に作って書いてたんですが、面倒なのでマクロで簡単に書けるようにした。 こういうのがあっさりできるの、ほんまRust最高である。 マクロ展開のデバッグには、trace_macros!(true) trace_macros!(false)が便利でした。 事前に#![feature(trace_macros)]をお忘れなく。

結果、以下のように書けるようになりました。

    let category1 = cat!(
        [A B C]
        [f: A -> B
         g: A -> C
         h: B -> C]
    );

全コード

そのうち全部は載せられなくなりそうですけど、その時はまた考えます。

macro_rules! cat {
    ([ $( $object:ident )* ]
     [ $( $arrow_name:ident : $domain:ident -> $codomain:ident )* ]) => ({
        let mut objects = Vec::new();
        $( objects.push(stringify!($object)); )*
        let mut arrows = Vec::new();
        $( arrows.push((
            stringify!($arrow_name), 
            stringify!($domain), 
            stringify!($codomain))); )*
        new_category(objects, arrows)
    })
}

use std::fmt::Display;
use std::collections::HashMap;

type Arrows = HashMap<String, (String, String)>;

struct Category {
    objects: Vec<String>,
    arrows: Arrows
}

impl Category {
    fn has_arrow(&self, domain: &str, codomain: &str) -> bool {
        for (dom, cod) in self.arrows.values() {
            if dom == domain && cod == codomain {
                return true
            }
        }
        false
    }

    fn is_isomorphism(&self, object1: &str, object2: &str) -> bool {
        self.has_arrow(object1, object2) && self.has_arrow(object2, object1)
    }
}

impl Display for Category {
    fn fmt(&self, dest: &mut std::fmt::Formatter) -> std::fmt::Result {
        let mut arrow_texts = vec![];
        for (k, v) in &self.arrows {
            arrow_texts.push(format!("{}: {} -> {}", k, v.0, v.1));
        }
        write!(dest, "objects: {:?} \n arrows: {:?}", self.objects, arrow_texts)
    }
}

fn insert_arrow(arrows: &mut Arrows, name: &str, domain: &str, codomain: &str) {
    arrows.insert(name.to_string(), (domain.to_string(), codomain.to_string()));
}

fn check_isomorphism(category: Category, object1: &str, object2: &str) {
    println!("{} and {} are isomorphism: {:?}",
        object1, object2, category.is_isomorphism(object1, object2));
}

fn new_category(objects: Vec<&str>, arrow_names: Vec<(&str, &str, &str)>) -> Category {
    let mut arrows = HashMap::new();
    for arrow in &arrow_names {
        insert_arrow(&mut arrows, arrow.0, arrow.1, arrow.2);
    }
    let category = Category {
        objects: objects.iter().map(|s| s.to_string()).collect(), 
        arrows: arrows
    };
    println!("made {}", category);
    category
}

fn main() {
    let category1 = cat!(
        [A B C]
        [f: A -> B
         g: A -> C
         h: B -> C]
    );
    check_isomorphism(category1, "A", "B");

    let category2 = cat!(
        [A B]
        [f: A -> B
         g: B -> A]
    );
    check_isomorphism(category2, "A", "B");
}

Rustで圏論(1)

発端

圏論を勉強しているのだが、本格的に書籍を買ってから約一年になる。圏論の勉強では、実際に手を動かして図式を書かないとかなり効率が悪くて、ものぐさな自分もさすがにペンでお絵かきしていた。が、だんだんそれもイヤになってしまい、せっかくなのでiPad ProにApple Pencilで図を描き始めた。これはいい。標準のメモアプリで、図とテキストが共存できるのがめちゃ便利だ。ところが今度は図の変形や、証明を追う段階になるとこれでもつらい。ということでプログラミングで解決したくなった。ごぶさたなのでRustで書きたくなった。

というわけで、リハビリを兼ねて書き始めた。めちゃくちゃアホっぽいが、まずはこれでいい。少しずつやっていく所存である。

struct Category {
    objects: Vec<String>,
    arrows: Vec<String>
}

fn main() {
    let category = Category {
        objects: vec![
            "A".to_string(),
            "B".to_string(),
            "C".to_string()
        ],
        arrows: vec![
            "f: A -> B".to_string(),
            "g: A -> C".to_string(),
            "h: B -> C".to_string()
        ]
    };
}

さすがに、射の方をそのまま文字列で持っているのは変更。でも一気にコードの雰囲気は変わってくる。 ひとまず射をそれっぽく表示するようにDisplayをimplする。

use std::fmt::Display;
use std::collections::HashMap;

type Arrows = HashMap<String, (String, String)>;

struct Category {
    objects: Vec<String>,
    arrows: Arrows
}

impl Display for Category {
    fn fmt(&self, dest: &mut std::fmt::Formatter) -> std::fmt::Result {
        let mut arrow_texts = vec![];
        for (k, v) in &self.arrows {
            arrow_texts.push(format!("{}: {} -> {}", k, v.0, v.1));
        }
        write!(dest, "objects: {:?} \n arrows: {:?}", self.objects, arrow_texts)
    }
}

fn insert_arrow(arrows: &mut Arrows, name: &str, domain: &str, codomain: &str) {
    arrows.insert(name.to_string(), (domain.to_string(), codomain.to_string()));
}

fn main() {
    let mut arrows = HashMap::new();
    insert_arrow(&mut arrows, "f", "A", "B");
    insert_arrow(&mut arrows, "g", "A", "C");
    insert_arrow(&mut arrows, "h", "B", "C");

    let category = Category {
        objects: vec![
            "A".to_string(),
            "B".to_string(),
            "C".to_string()
        ],
        arrows: arrows
    };

    println!("{}", category);
}

というわけで、実行すると以下が表示される。

objects: ["A", "B", "C"]
 arrows: ["g: A -> C", "f: A -> B", "h: B -> C"]

ちなみに、図式で書くと以下のようになる。

Programming Rustを読んだ

以下の書籍を読んだので、その感想を書くことにする。 shop.oreilly.com

やっとProgramming Rustを最後まで読み切った〜！雑に読めばすぐだがちゃんと読むと大変だったぞ！！！

— イロノワ (@ironoir) 2018年4月19日

というわけで、タイトルが紛らわしいが、公式のドキュメントである プログラミング言語Rust ではなく、オライリーの書籍である。また、日本語訳はまだ出ておらず、英語版である。

ちょうどいい広さと深さ

Rustに関しては、日本語だと公式のドキュメント以外に書籍で出ているものは見つからず、パイオニアの方々のブログ記事しかググっても出てこないイメージである（もしかしたらあるのかもしれないけど）。網羅的に知りたい人間なので、チュートリアルの次にがっつり読める書籍を探していたところ、今回読んだProgramming Rustを見つけて即購入した。

Prefaceが

Rust is a language for systems programming.

という一文で始まるように、Rustの適用範囲を明確にした上で、サブタイトルである"Fast, Safe Systems Development"の具体的な内容を明らかにしていくという構成になっている。 章立ては以下。

1. Why Rust?
2. A Tour of Rust
3. Basic Types
4. Ownership
5. References
6. Expressions
7. Error Handling
8. Creates and Modules
9. Structs
10. Enums and Patterns
11. Traits and Generics
12. Operator Overloading
13. Utility Traits
14. Closures
15. Iterators
16. Collections
17. Strings and Text
18. Input and Output
19. Concurrency
20. Macros
21. Unsafe Code

導入と概要 1~2章

1・2章が導入だが、2章はいきなりがっつり読むには割と重い気がした。雰囲気をつかめさえすればいったんは次に進んだ方が良いと思う。それ以降を大雑把に分けるとすれば、3~11章までが基礎的な言語要素に関する内容、12~21章が応用的な内容になるだろうか。

基礎 3~11章

最初の難関はやはり4章と5章の所有権周りかと。公式ドキュメントを読んでからだとそれらの知識が補足できるだろうが、個人的にはもう少しライフタイムの内部構造に関して突っ込んでもらえるとありがたかった。

7章ではOptionとResultが顔を出してくる。PanicがいかにSafe側に倒された設計になっているのか、という話も。8章はクレートとモジュールの話。意外とありがたかったのが、ここでcargo testの話が出てくるところ。うろ覚えだが「別に必然性はないけどここで書いとくね」的なことが書いてあった記憶。そういうエコシステム的な話が出てくるのはここだけだが、そういう話が書いてあるだけでありがたい。

応用 12~21章

13章は読んでほしい。Rustは本来言語組み込みっぽい機能をTraitに任せる傾向があって、しかもそれぞれ、名前を見ただけでは違いがわかりにくいが、ここでまあまあ突っ込んで解説されている。14章もClosureとTraitの関係がわかればいろんなことがつながってくるという意味でその続きである。15章のIteratorも同様。IntoIteratorとIteratorがいつもごっちゃになる自分としては、スッキリした。ちなみにこの仕組みってPythonとめちゃ似てるよね（イテラブルオブジェクトとイテレータの違い）。参考にしたんやろな。そしてあのたくさんあるイテレータの便利メソッドも解説されているので、使ってみようかな、という気にさせられた。

17章は文字列の話だが、文字列のメソッドの解説をしている章ではなく（それもあるが）、どちらかというとUTF-8を採用した背景みたいなものが読み取れる興味深い章である。18章は入出力に関してだが、PathやOsStrとかの話が参考になった。

19章は、著者の書き方からして、この書籍のクライマックス感がある。ここまでの章が伏線で、最も"Fast, Safe Systems Development"と相反する歴史を持つ並列処理を、Rustがどのように捌いているのか、ということが語られている。

残りはクールダウンという趣きだが、マクロの実例がJSONパーサだったので実用的で良いなと思った。これは最終章の実例がGitのwrapper作成という点でも同じである。

見どころ

図解が良い

全体に、これがこの本を読んで最も良かった点だ。Vecとslice・Stringとstrの関係はRustやるやつ全員読め、的な感じである。「ゼロコスト抽象化」をどのように実現するのかという文脈もあいまって、fat pointer/smart pointerの実装が、C++やPythonとの差異で図示されるのはめちゃめちゃわかりやすかった。Derefも関係するしね。ほんま、これだけのために買う価値がある。

日本語がやたら出てくる

Programming Rustでトレイトの使い分けがわかってきた気がするけど、問題は突然「Great Teacher Onizuka」とか例に出てきて全然落ち着かんこと。Unicodeのとこでも日本語まあまあ出てくるので絶対著者日本好きやんってなってる

— イロノワ (@ironoir) 2018年1月21日

このツイートの通りなのだが、Unicodeの説明でもなぜか日本語（うどんとかそばとか）が多いし、なんとなく嬉しい。他国の人が読むとこれらの文字はどう見えるんだろう、などという興味も湧いたりした。

まとめ

RustはC++に対するcounterpartとして産まれたもの（ですよね？）でありながら、fastとsafeの両立のためにC++とは異なるアプローチで設計されていて、初学者は混乱しがちだというイメージがある。この書籍はその詳細に切り込んだ良い本だと思う。また、公式のドキュメント日本語訳も第2版が出ようとしているものの（contributorの方々には本当に頭が下がります）、内容を見る限りこの書籍の有用性は大きく減ることはないと感じている。おすすめ。というかお仕事やらなんやらでRust書けていないので、できるだけ早く再開したい。

新しい言語の学び方の一工夫

「見渡したい」

人それぞれだろうが、私は新しいものを学ぶ時、全体像を把握したい人間だ。「見渡したい」という表現がしっくりくる。

プログラミング言語に関しても同様である。Hello Worldだけ見せられても、スッキリしない。まずは「文法の一覧と標準ライブラリを見せてくれ」という思いが先につく。最近は言語にせよフレームワークにせよライブラリにせよ、キレイなWebサイトを持っていて、トップページに簡単な説明が書いてあるのだが、PowerfulだのSimpleだのFlexibleだのFastだのLow Costだのが大げさな修飾語を伴っていたりするだけのことが多くて、欲しい情報ではなかったりする。

とはいえ、チュートリアルは有効なことも多い。というのも、文法や標準ライブラリだけではわからない「文脈」が見えるからだ。「歴史」「文化」と言い換えてもいい。その点では自然言語と似ているなあ、と思う。

具体的なチェックポイント

一方プログラミング言語は、自然言語よりも範囲が明確に決まっている分、全体像が把握しやすい。知らないプログラミング言語（フレームワーク・ライブラリ）を学ぶ第一歩は、文法・標準ライブラリ・チュートリアルのコード例と、その他ドキュメントに書いてある「その言語のアピールしたそうなポイント」を見比べながら、だいたい以下のようなポイントに考えを巡らせる。

• 既存のどの技術に影響を受けているのか
• 既存技術のどこに不満があって作り始めたのか
• アピールしたい一番のポイントはどこなのか

学ぶ順番を見定める

ふんわり全体像がわかった気になるだけであれば、上記でなんとかなるのだが、実際に使う分には、結局コードを書かないと上達しない。しかし、チュートリアルを終えた後は大抵、彷徨う羽目になる。Webで情報を漁ったりしても、応用しようとした時に少しのことでつまづいて、数日間ちょっとしたことで悩み続けることになってストレスマッハである。

というわけで、こういう時に私が使うちょっとした工夫がある。

その技術の「ライバル」をいくつかピックアップするのである。

「ライバル」と比較する

「競合比較」自体は目新しい手法ではないはずだが、勉強する順番を決めるために使う、というのを喧伝しているのはあまり聞いたことがない。例えば、自分がWebフレームワークについてほとんど知識がない（Webの仕組みはふんわりわかっている）状態で勉強を始めるとしよう。

Railsのようないわゆるフルスタックと呼ばれるフレームワークは全体像の把握が困難である。本を読んで色々できるのはわかったが、どうもまとまらない、という状態になる。そこで私が行った次の一手は、闇雲にRailsのコードを書いたりドキュメントを読むのではなく、他のフレームワークを調べることだった。Railsは確かにRubyでは有名だが、Sinatraというのがある。これは全体が小さいことをアピールしているので、その方が全体像を把握しやすいし、Railsを勉強するにしても、まずはSinatraとの共通部分になっていそうなドキュメントを読む方が良い。Rubyじゃなくても、PHPにもPythonにもNode.jsにもたくさんWAFがあるので、たくさん見ているうちに同じようなキーワードがたくさん出てくるはずである。まずは、その部分が大切なのだな、とわかる（以下はそのキーワードの例）

• 「リクエスト」
• 「レスポンス」
• 「ルーティング」
• 「テンプレート」
• 「セッション管理」

「書籍」を比較する

上記の変形バージョンなのだが、全く無知な分野の場合、関連書籍の目次を読みまくり、その共通キーワードをあぶり出す、という手もよく使う。一度重要なキーワードが分かればググりやすくなるので、格段に進歩が早くなる。ただ、これは近くに巨大書店がある時に一番有効な手なので、そうでない場合は得られる情報の精度が限られるという問題はある。

個別事例より先に、体系を学ぼう

「別にほしい機能が作れればそれでいいよ」という方もたくさんいるし、場合によるのだが、実際に使うつもりのある技術に関しては、基本的にはTIPSではなくて全体像を掴むような学び方をしてほしいなあ、とは思う。

Rustで文字列・ファイル、両方からbyteを読みたいだけなのに

バイト配列をイテレータで読み込みたい

Rustでプログラミング言語を作っている。基本的には、ソースコードはファイルを読み込むのだが、テストのために固定の文字列をソースコードとして読ませたくなることが多い。そういうわけで、字句解析器（Lexer）に両方を受け付けられるインターフェースを作ろうとしたのだが、これが意外と面倒なことに気づいたので書く。

文字列もファイルからのストリームもイテレータなのに

&strからイテレータを取り出すときは、bytesメソッドを使えばIteratorが取れる。一方、ファイルではstd::io::BufReaderにもbytesメソッドがある。これらはReadトレイトのメソッドなので、「じゃあ、Read型を引数で受け取ればいいのかな」と安易な気持ちで書いてみたら、全然ビルドが通らない。よーく見ると、当然だった。

まず、文字列&strの場合。

    let s = "Please iterate me!";
    let mut bytes = s.bytes();
    while let Some(b) = bytes.next() {
        print!({:?}, b);
    }

そして、ファイルから読み込む場合。

    let f = File::open("_.txt").unwrap();
    let mut bytes = BufReader::new(f).bytes();
    while let Some(Ok(b)) = bytes.next() {
        print!({:?}, b);
    }

おわかりいただけただろうか……nextメソッドの返す型が違うのである。str::bytes()はIterator<Item=u8>を返し、BufReader::bytes()はIterator<Item=::std::io::Result<u8>>を返す。ファイルは間にstd::io::Resultが挟まっているのである。だから当然これらを共通の引数にしてメソッドを定義することはできない。

しょうがない

というわけで、普通にどちらでもいけるようにがりがりifで書き直しました。そのまんま、何の工夫もしていないので見せるほどのコードでもない。しかし、もうちょっと何とかならんかなあ。

補足

Iterator<Item=::std::io::Result<u8>>は、Iterator<Item=Result<u8>>とは書けない。std::result::Resultだと思われてしまうので。ただ、Iterator<Item=std::io::Result<u8>>とも書けない。うまくパースできないようなので、Iterator<Item=::std::io::Result<u8>>と書く必要があります。これって::を省いて書けるようになったりするんかな。まあともかく、そんな感じです。

勝手にevalしない言語をRustで作ったら意外なものになった

概要

この記事は言語実装Advent Calendar 2017 25日目用として書かれたものです。 Advent Calendar初参加です。迷っていたら25日が空いていたので、思い切って飛び込んでみました。 でもよく見たら、なんだかテーマは高度なことばかり。 私はそのようなことは全然書けるような実力はありませんので、できることだけをやりました。こわい。すいません。

ソースコード

Epiqsという名前です。たらい関数とfibonacciは動いてますよー。 READMEは古い記述がたくさん残ってるので直したいよー。 github.com

動機

たくさんある。なんだか思いの丈がまとまっていないが、そのまま書く。 ちなみに私は「ポエム」という表現を使うのは好まない。 書いていて気づいたが、言語実装というよりは言語「設計」という趣である。

コンスセル大好き

Lisp系言語が好きなのだが、最近、どちらかというとコンスセルが好きなのだと気付いた。 Lispの書籍には最初、初心者用に正方形が二つ横に並んだものが矢印で結ばれた図が載っている。あれである。 あれが至高。むしろ私の志向がアレなのかもしれないが。

コンスセルをepiqと呼ぶことにした

既存の名前は好きじゃない

• cons/car/cdrという名前は好みではない
• first/restも惜しいがもう一声欲しい

piq

というわけで、ある日突然、コンスセルにpiqという名前をつけた。「ぴっく」と読む。

• 目を細めてみると、pとqがそれぞれ二つのポインタに、間のiが仕切りに見える気がする。
• この言語ではcarのことはpと呼び、cdrのことはqと呼ぶ。pとqがアルファベットで隣同士なのもポイント高し。
• 昔作ったものがBriqsDBだったので、それと語呂を合わせたかった（BriqsDBは変なDB(？)とそのクエリ言語）。

コンスセル大好きだけど、情報が足りない

「コンスセルを使えばあらゆる構文を表現できる」のは確かだ。ただ、ポインタ2つだけではもの足りないというか、効率が悪いと常々感じていた。「カッコだけだから統一感があって美しい」にはほぼ賛成なのだが、キーワードに複雑さを転化しているとも解釈できる。

あと一つ情報を付け足すとしたら

それでは、コンスセルに付け足してメモリ効率を上げられるような最低限の情報ってなんだろう、と考えて、結局、読み取り専用タグをつけた。こうして、piqはタグ（otag、pの前のアルファベットなので）を持つことになり、「タグ埋め込み」という意味を込めてepiqと呼ぶことにした。言語名はここから来ている。epicとかけたのも、もちろんある。

暗黙の動作をなくしたい

勝手にevalしない

マクロの複雑さは、evalが再帰呼出されるから？

Lispでマクロを書く時には、特にマクロを生成するマクロなんかだと、quoteとunquoteがこんがらがる。この点に関してはいくつかの解決策や妥協案があるが、そもそもそれって、evalしたら再帰的に評価を行うからなんじゃないの？という疑問が浮かんできた。

evalの再帰性は、共犯関係から成り立っている？

SICPにも出てくる評価機を見ても、evalから呼ばれる各種special formやapplyは、それぞれの要素に対してevalを呼び直しているのだ。つまりevalが再帰的に実行されるのは当然ながら単体でなされたものではなく、evalと他の言語要素との共犯関係が前提にあってのことである。

evalではなくてwalk

というわけで、デフォルトでは何もせず、評価させたい部分だけをevalするアイディアが浮かんだ（ただ、言語を作った今だから言えるが、実際にはそんな簡単な話ではなかった）。だから、"REPL"ではなくRead-Walk-Print-Loop(RWPL?)になる。walkする中で、evalが明示的に呼び出されている部分だけが評価される。evalを使わずにコードを返す関数を書けば、それはマクロ定義になる。

applyはたくさんのことを一度にやりすぎ

applyって結構、色々なことをやっている。ここでのapplyは、apply関数というよりは、通常の関数適用のことだと考えてほしい。

• シンボルを解決して関数本体を取得する
• そして引数のリストを評価する
• それを関数本体にバインディングする（必要ならばパターンマッチも）
• 環境も整える
• ようやく中身の実行

最低限でもこれだけある。これらもなるべく分解して、明示的にしたいと考えた。わかりやすさと柔軟性を求めてのことである。Epiqsのapplyは、「シンボル解決」「引数リストの評価」「戻り値を返す方法の指定」は他のオペレータに任せている。

ASTをそのまま書きたい

これも「暗黙的なものを晒したい」という動機の一部である。Elixirのマクロの内部構造がイメージに近く、あれをなるべくマシな形で書きたい、とも言い換えられる。その代償として、syntax sugarなしでは、かなり冗長なソースコードになってしまった（下記参照）。

なぜRustで作ったのか

以前公開した言語はC++で作ったのだが、いざ出来上がったものを動かしていると、謎のメモリエラーが出てデバッグに難儀したが、そこで出会ったのがRustだった。だいたい以下の話。

• 安全性
• モダンなツールチェイン（モジュールシステムやパッケージマネージャ）
• 構文面（パターンとか）
• 型システム
• 将来性

Rustで作る時のハマったポイント

所有権/ライフタイム

慣れるまではきつい。安全性のためなので学習コストが高いのは仕方ないかな、という印象。今回作ったインタプリタは内容としてはC++の時と大差なく、構造は単純でLL(1)パーサとAST書き換えを行なっているだけだが、所有権/ライフタイムの高い壁に阻まれまくった。ただし、Rustはどちらかというと「リソース管理に関わるコストをきちんと可視化して」ユーザーにコストを意識させる設計になっていると感じているし、それはEpiqsでやろうとした、「暗黙の要素をなるべく明示的に指定する」というポリシーとも近くて、要するに個人的には相性が良い言語である。

とにかくASTの書き替えができない

かなりの時間が吸われた。丁寧なエラーメッセージを読んで、ライフタイムを書き換え、参照と各種スマートポインタ（とその組み合わせ）を縦横無尽に試しながら、コストを最小限に抑えつつビルドを通すにはどうしたら良いのかを考えさせられた。まだまだ非効率な部分も多くて、誘惑に負けてcloneしてしまった部分もたくさんある。

とにかく思った通りのフローで処理を書かせてもらえない

所有権周り

変数のスコープを短く保つためには、適当に書くわけにはいかない。他の言語では見慣れない、ブロック囲みのスコープ限定をたくさんやることになる。

エラーハンドリング

方法がいくつかあるが、これも明確な基準がないと他の方法に切り替えるためのコストが結構かかった。try!が?になったのとか、どんどん書きやすくはなっているのは間違いないが、「なんとなく」が恐ろしいほど通用しない言語だということは骨身に染みて理解した。

でも良い言語

ある程度理解できれば、強い味方になってくれるので、次回からはそこまで悩まずにRustが書けると思う。基本的にはとても良い言語だと感じています。

実装面

言語実装Advent Calendarなので、できる限り実装面のことも書いてみる。

全体の構造

Lexer / Parser / Walker(not Evaluator) / Printerと分かれている。 Rustの練習を兼ねているので、全て手書きである。

Lexerをモジュール化してみた

Web開発界隈ではBabelやPostCSSなどを使って、JavaScriptやCSSに、部分的に構文を付け足すことができる。これと似たようなことを実現したいと考えて、Lexerの中で、Scannerという名前で構文ごとにstructを持つようにした。ただ実行効率を考えて、Babelなどのように外部から指定するのではなく、あくまでも内部でモジュール分解しただけである。静的ディスパッチにしたくて色々試したが、勉強不足からか結局動的にしか書けなかった。実質Lexerはイテレータのように作った（下記コードのtokenise()メソッドがいわゆるnext()にあたる）のだが、大変なのでIteratorトレイトの実装は見送った。ちなみにParserやWalkerに関しても、時間がなくてモジュール化は断念した。

    let scanners: &mut Vec<&Scanner> = &mut vec![
        &DelimiterScanner,
        &AlphabetScanner,
        &ZeroScanner,
        &IntegerScanner,
        &EOFScanner,
    ];

    let mut iter = text.bytes();
    let mut lexer = Lexer::new(&mut iter, scanners);
    lexer.tokenize();

ASTと記号表

ASTというかRustで木構造を書き換えることの難しさはこの後に書いてあるが、試行錯誤の末、ASTの中枢部はArenaと呼ばれるものを利用することになった。メインデータであるEpiqにNodeという中間物を挟んでVec<Node<Epiq>>になっている。困ったのは、記号表であるSymbolTableの中身だった。最初はVec<Vec<(String, &Epiq)>>にしたいと考えていたのだが、どうしてもこの中の参照に適切なilfetimeを与えられず、結局Vec<Vec<(String, usize)>>と、参照ではなくてindexを持つように変更することになった。あとは、これらをstructにまとめてRc<RefCell<_>>の形にして、各モジュールはASTからEpiqを貸し出してもらう、という形に落ち着いた。ただ、真面目に作ろうとすると中身の要素がどんどん増えっぱなしでゴミになったepiqを制御できていない問題をなんとかしなければならないだろう。

仕様

epiq

繰り返すが、コンスセルのことである。以下のように書く。pとqが要素である。

|: p q

実は最初の|はディスパッチャであり、次の:がこのepiqが単純なコンスセルであることを示すotagになっている。 他にも以下のようなepiqがある（現在の実装とは実は噛み合っていないが）。 ちなみに;はUnitであり、リストの末尾などに多用される。

その他のepiq一覧

• |: pval qval linked-list(normal cons cell)
• |# smbl valu bind
• |. trgt kynm access
• |\ envn body function piq block
• |! func args apply
• |% ; prms environment
• |@ ; smbl resolve symbol
• |> ; aexp exec eval

最後にevalがあるが、これはつまり、基本的にevalは全て明示的に指定する必要がある、ということでもある。

ディスパッチャ

epiqの引数は必ず2つあるが、いつも片方（大抵はqの方）しか指定しないepiqもある。このような場合は|の代わりに'を使う。 '> aexpと書けば、それは|> ; aexpと同じ意味である。

リスト

見た目は（カンマ区切りじゃないけど）Haskellと同じである。 [a b c]であり、これはepiqで書くと|: a |: b |:c ;である。a:b:c:;という中置記法があるのもHaskellっぽい。

たらい関数

恐る恐る作って回してみたが、ちゃんとある程度の時間で返ってきてよかった。tak(12, 6, 0)で70秒ほど。 なんの工夫も最適化もしていない木構造のインタプリタとしてはマシなのでは。Rustありがとう。 ただし、記述が冗長すぎて1行が長い。eval(|>)を逐一指定しているのは大きな一因だろう。 というわけで、syntax sugarを入れたものを2段階に分けて載せておく。

(defun tak (x y z)
  (if (<= x y)
    y
    (tak (tak (1- x) y z)
      (tak (1- y) z x)
      (tak (1- z) x y))))

(tak 12 6 0)

syntax sugarなし

|> ; ^> -1 [
   |# tak |\ |% ; [x y z] ^> -1 [
          |? |> ; |! |> ; |@ ; ltoreq [|> ; |@ ; x |> ; |@ ; y]
             |: |> ; |@ ; y
                |> ; |! |> ; |@ ; tak [
                     |> ; |! |> ; |@ ; tak [|> ; |! |> ; |@ ; decr [|> ; |@ ; x] |> ; |@ ; y |> ; |@ ; z]
                     |> ; |! |> ; |@ ; tak [|> ; |! |> ; |@ ; decr [|> ; |@ ; y] |> ; |@ ; z |> ; |@ ; x]
                     |> ; |! |> ; |@ ; tak [|> ; |! |> ; |@ ; decr [|> ; |@ ; z] |> ; |@ ; x |> ; |@ ; y]
                ]
   ]

   |! |> ; |@ ; tak [12 6 0]
]

tarai関数(with syntax sugar1, 実装中)

|>>>> [
   |# tak |\ '% [x y z] ^>> [
          |? '> |! '> @ltoreq ['> @x '> @y]
             |: '> @y
                '> |! '> @tak [
                   '> |! '> @tak ['> |! '> @decr ['> @x] '> @y '> @z]
                   '> |! '> @tak ['> |! '> @decr ['> @y] '> @z '> @x]
                   '> |! '> @tak ['> |! '> @decr ['> @z] '> @x '> @y]
                ]
   ]

   |! '> @tak [12 6 0]
]

tarai関数(with syntax sugar2, 草案)

^>>>> [
   |# tak |\ '% [x y z] ^>> [
          |? @ltoreq!, @x, @y
             |: @y
                @tak! [
                   @tak!, @decr! [@x], @y, @z
                   @tak!, @decr! [@y], @z, @x
                   @tak!, @decr! [@z], @x, @y
                ]
   ]

   @tak!, 12, 6, 0
]

下まで来ると、見た目はだいぶマシになる。まだ実装していないけど。 ちなみにfibonacciも作った。(fib 30)が15秒ぐらい。

(letrec 
  fib 
    (lambda n
      (if (eq n 0)
        0
        (if (eq n 1)
          1
          (+ (fib (- n 2)) (fib (- n 1))))))
  (fib 30))

fibonacci数(with syntax sugar2, 草案)

^>>>> [
   |# fib |\ '% [n] ^>> [
          |? @eq!, @n, 0
             |: 0
                |? @eq!, @n, 1
                   |: 1
                      @plus! [
                        @fib!, @minus! [@n 2]
                        @fib!, @minus! [@n 1]
                      ]
   ]

   @fib!, 30
]

振り返って気づくこと

Lisp系以外の言語構文の馴染みやすさ

前置記法から初めて、なんとか自分なりに見やすく、かつなるべくsyntax sugarというかマクロで実装できそうな形で置き換えることを考えた結果、他の言語の構文がなぜそうなっているのか、気づく点が多々あった。様々な言語(C系/ML系/Erlang/Prolog...)の独特な見た目も、構文を考えると「なるほどな」となることがあった。 「こうして色々な言語が産まれていっているのだな」「みんなある程度、問題意識は同じ部分に収束していくのだな」という気づきがあった。

テンプレート言語を作ったことになった

これが今回の一番の驚きだった。「evalを勝手にしない言語を作りたい」と思って作っていたら、ある日「これってエントリポイントがたくさんあるってことだよなあ」と気づく。木構造を部分的に書き換えることもできるわけで、それってつまりはWAFとかでよく見るテンプレート言語じゃないか、と思った次第。そういう用途で機能を追加してみようと思う。

さいごに

読んでくださってありがとうございます。 みなさま、メリークリスマス、そしてよいお年を！