Don't Repeat Yourself

Don't Repeat Yourself (DRY) is a principle of software development aimed at reducing repetition of all kinds. -- wikipedia

Rust でステートマシンを扱えるライブラリを書いてみた

TL; DR

  • Rust でステートマシンをいい感じに扱えるようにするライブラリを書いてみた。
  • とくに他の言語のライブラリを調査したわけではないので、もう少しいいアイディアがあるかもしれない。

何を作ったか

Rust でマクロや他のライブラリを一切使わずにステートマシンを実装できるライブラリを作り、crates.io に公開してみました。

https://crates.io/crates/statemachine-rs

ドキュメントはこちらにあります。

docs.rs

リポジトリはこちらです。

github.com

何ができるのか

詳しくは README に記載しておりますので、使用してみたい場合はぜひご覧ください。

Rust には enum(Rust では代数的データ型になっています)という大変素晴らしい概念が利用できます。ステートマシンにもこれを利用しないわけにはいきませんよね。このライブラリは、enum 等を使用したステートマシンの実装のお手伝いをします。

下記のサンプルでは、ボタンの切り替えを行ってみています。

まず初期設定を StateMachineBuilder というビルダーを使って行えるように実装してあります。

State として ButtonState を用意し、Input として Input という enum を定義します。下記では On/Off という状態を、Press という入力を使って切り替えられるようにしています。

Input に対して State がどのように変化するのかは、クロージャーで定義します。transition 関数の引数は StateInput のタプルになっています。ここで、状態と入力のパターンマッチングを行い、状態遷移を定義します。

use statemachine_rs::machine::{builder::StateMachineBuilder, StateMachine};

#[derive(Clone, Debug, PartialEq)]
enum ButtonState {
    On,
    Off,
}

enum Input {
    Press,
}

fn main() {
    let sm = StateMachineBuilder::start()
        .initial_state(ButtonState::Off)
        .transition(|state, input| match (state, input) {
            (ButtonState::On, Input::Press) => ButtonState::Off,
            (ButtonState::Off, Input::Press) => ButtonState::On,
        })
        .build()
        .unwrap();

    assert_eq!(ButtonState::Off, sm.current_state());
    sm.consume(Input::Press);
    assert_eq!(ButtonState::On, sm.current_state());
}

状態を進める際には consume という関数が生えており、この consume に入力を渡すと状態遷移が行われます。consumeStateMachine トレイトの関数です。consume 以外にも、現在の状態の取得や状態のリセットなどを行える関数を用意してあります。また、StateMachine トレイトは pub なため、自身で構造体とその実装を定義してオリジナルのステートマシンを用意することもできます。

pub trait StateMachine<State, Input> {
    fn current_state(&self) -> State;

    fn consume(&self, input: Input) -> State;

    fn reset(&self) -> State;

    fn set(&self, new_state: State);
}

実装して迷っているポイント

今回 Rust ではじめて OSS のライブラリを作ってみたので、慣習がわかっていない部分があります。

実装の都合で Stateenum に対しては現在 Clone が要求されます。現在、標準で提供しているのは BasicStateMachine という構造体です。これは StateClone を要求しています。実装側を見ていただくとわかるのですが、どうしても clone が必要と思われる箇所が出てくるためです。

/// The basic state machine implementation.
/// It holds `initial_state`, `current_state`, `transition` function.
pub struct BasicStateMachine<State, Input, Transition>
where
    Transition: Fn(&State, Input) -> State,
    State: Clone,
{
    /// `initial_state` is literally an initial state of the state machine.
    /// The field isn't updated the whole life of its state machine.
    /// That is, it always returns its initial state of its machine.
    initial_state: State,
    /// `current_state` is the current state of the state machine.
    /// It transit to the next state via `transition`.
    current_state: RefCell<StateWrapper<State>>,
    /// `transition` is the definition of state transition.
    /// See an example of [`StateMachine::consume()`], you can grasp how
    /// to define the transition.
    transition: Transition,
    _maker: PhantomData<Input>,
}

もし StateClone を要求するのが、大きなパフォーマンス劣化を招く原因になりうるのだとしたら、この Clone の制約を外せるように実装を調整する必要があるのかなと思っています。が、正直これをどう上手に調整したらよいかの想像がついていません。このあたりのワークアラウンドは結構迷ってます…。

もし何かアイディアがある方がいらっしゃいましたら、お気軽に Issue を立てたり、PR を投げたりなどよろしくお願いします😃

また、BasicStateMachineRefCell を使用していることからもわかるようにスレッドセーフではありません。スレッドセーフな StateMachine 実装は、今後時間を見つけて追加する予定です。

はじめてのクレート公開の感想

cargo package からの cargo publish をするだけでクレートを公開できてしまうのは、正直かなり便利ですね。Scala のときは sonatype だったか、どこかの外部サービスに一度ユーザー登録をして、JIRA をうんたらかんたら…といった作業が必要だった(勘違いしてるかも)と記憶しているのですが、crates.io は GitHub の ID さえあればアカウントを作成でき、サイト上でアクセスキーを生成してあとはローカルから cargo publish を打つだけ、という非常にスムーズな構成になっていました。

OSS の公開に際しての悩みの種といえばドキュメントですが、ドキュメントは crates.io に登録した時点で自動的に URL を用意してくれ、そちらに cargo doc の結果をホストしてくれます。今回私が作ったクレートのドキュメントはこちらにありますが、これを見たときに「ああ、クレートを公開しちゃったよ…すごい…」という気持ちになりました。いたれりつくせり。

ドキュメントを書くのはかなり骨の折れる作業で、主にサンプルコードの用意の部分で結構手間取りました。ただ、サンプルコードを用意しておくと、cargo test したタイミングで doc test が走り、コメント内のコードのコンパイルが通るかや assertion が通るかを自動でチェックしてくれます。ドキュメントのメンテ漏れに気づけるようになるので、この仕組みは非常に素晴らしいです。ちなみに他の言語での経験だと Python でも同じことができますね。

クレートの使い勝手については、自分が普段 Rust コードを書く際には問題ないなというレベルで公開してしまっているため、他の方がどう感じるかが結構気になっています。というわけで、ドッグフーディングしてくださる方、よろしくお願いします。Issue や PR お待ちしております!

Rust を始めるための資料集

かとじゅんさんのお誘いで、私塾匠真堂にて登壇させていただき、Rust に関する話をさせていただきました。ありがとうございました。

今回のセッションを通じて Rust を始めたくなった方向けに、Rust をはじめるための資料をいくつかリストアップしてます。よかったらどうぞ。

プログラミング言語の学習方法について

みなさんは新しいプログラミング言語を学ぶ際、どのように学びますか?

私は、軽く制御構文やデータ型の作り方などを学んだ後は、すぐにアプリケーションを作ってみて、詰まったらリファレンスを参照するといった学び方をしていることが多いです。

逆に、リファレンスをまず眺めて、文法をしっかり把握した後にアプリケーションを作ってみるという方もいるかもしれません。

いずれにせよ、

  • リファレンスを眺める。
  • アプリケーションを何かしら作ってみる。

の2つを、多くのプログラマは新しいプログラミング言語を習得する際にやっているのではないでしょうか?ということで、この2つについて、私の知る限りで資料を列挙したいと思います。

各資料の紹介時には、どういったシチュエーションで使用できるか、どのような特徴をもった資料かを簡単に補足説明しました。

Rust についてまず概観を掴む

Rust がどのような言語なのかについて、まず概略でいいから掴みたいという方向けにおすすめできる記事です。(他にもいい記事があるので、思い出し次第追加します)

  • 最速で知る! プログラミング言語Rustの基本機能とメモリ管理【第二言語としてのRust】: 少し古めの記事ではあるのですが、この頃から Rust のコンセプトは大きくは変わっていません。Rust がどのような言語かについて簡単に触れた後、所有権などを図を用いて説明しており大変わかりやすいです。
  • Rust は何が新しいのか: これは少々突っ込んだ話側かもしれませんが、Rust の「新しさ」について解説された記事です。Rust ではムーブセマンティクスと呼ばれる概念を使ってメモリ管理をしているわけですが、そのムーブセマンティクスは C++ から輸入され、Rust 向けにアレンジされた概念です。C++ におけるムーブセマンティクスの利点とペイン、そしてそれらを Rust がどう解決したかについて簡潔にまとまっています。
  • プログラミング言語 Rust のご紹介: これは私が以前発表した資料ですが、Rust の2020年時点での現状や言語機能、日本でのコミュニティ活動をまとめてみたものです。
  • Rust入門ガイド (sapporo.rs) #Rust - Qiita: sapporo.rs という勉強会で発表されたプレゼンのようですが、Rust の特徴が非常に簡潔にまとまっていてよいです。どういう用途に使用できそうか、という話まで込みで書かれており、Rust を使うイメージがわかない場合には読まれるとよいかと思います。

文法を学ぶ

2021年現在では、下記がおすすめできるかなと思っています。

  • Comprehensive Rust🦀 [未邦訳]: Google社が提供するRustのチュートリアルで、4〜5日で一巡できるように設計されています。まだ英語しかありませんが、簡潔に書かれています。Rustのメモリ管理を理解するためには、そもそも他のプログラミング言語でのメモリ管理をある程度知っておかなければならなかったりしますが、そうした「Rustをやる前に必要になる前提知識」も簡潔ながら抑えられておりよさそうです。
  • Rust の最初のステップ: Microsoft社が提供する Rust の入門講座で、文法を1から学んで最終的にはちょっとした CLI アプリを作るところまで到達します。Rust を書き始める際に必要な項目がコンパクトにまとまっており、一番最初に取り組むチュートリアルとしておすすめできます。
  • Tour of Rust [一部邦訳]: これは現時点で最初の一歩におすすめできる資料かなと思います。Go 言語には A Tour of Go という、Go を始める際にうってつけな教材があります。それの Rust 版です。Rust の文法を1ページ1ページ解説しつつ、横で Playground を使ってコードを実際に実行して挙動を確かめるところまでセットでできます。まずこれを軽く通してみて、簡単に文法の概観を掴むとよいのではないかと思います。
  • Rust by Example: 文法の細かい解説というよりは、サンプルスクリプトを通じて Rust を学んでいける資料に仕上がっています。細かい解説はいいから、とりあえずサクサク写経しつつ概観を掴んで実際にアプリケーションを作って学んでいきたい、という方におすすめできるかなと思います。
  • とほほの Rust 入門: あのとほほさんの Rust 入門です。非常に簡潔に Rust の文法が網羅されており、サクサク Rust の文法を見ていく場合に適しているように思います。
  • Rustlings [未邦訳]: コンパイルエラーになる Rust コードのコンパイルを通るようにしていく問題集です。Rust のコンパイルエラーを直していく過程で、さまざまな Rust の文法について学んでいくことができるように設計されています。Rust にちょっと慣れてきたくらいでやってみるといいかもしれません。
  • RustCoder ―― AtCoder と Rust で始める競技プログラミング入門: 競技プログラミングを Rust でやりたい方向けに書かれた資料だとは思いますが、Rust の基本的な文法がよく解説されています。その章の文法を学んだ後に、AtCoder の問題を解いてみるという形式になっており、非常に導入がスムーズに感じます。
  • Rust入門: この本も日本語で書かれた Rust 入門に適した本で、Rust の概要をサクッと学んでみたい方にオススメです。各概念について完結にまとめられていて、必要に応じて概念図も用意されており、実用的なドキュメントになっていると思います。
  • Rustハンズオン@エウレカ社: 拙作で恐縮ですが、以前依頼されて行ったハンズオンをスライドとして公開しています。簡単に文法を解説したあと、cat コマンドや grep コマンドを作り、さらに grep コマンドについてはいくつか拡張をするという構成になっています。3時間程度あれば終わることを想定して作られたハンズオンです。

これまでは TRPL を薦めてきましたし、実際私も TRPL の第1版の日本語訳で入門しました。今でも TRPL は第一のリファレンスに使えます。一方で、国内海外問わず、TRPL がまずまずハードだという声も聞きます。近年 Rust ユーザーの増加により、入門用のドキュメントだんだん種類が増えてきました。これから学ばれる方の他の言語での習熟度や、これまで取り組んできた領域によってどの資料が合うかは変わってきます。上のリストのものをいくつか試してみて、ご自身にあうと思うものを選ばれるとよいと思います。

何かアプリケーションを実装してみる

Rust では本当にさまざまなものが作れます。また、それらの作り方について解説したチュートリアルがかなりの数存在しており、最初に取り掛かる際におすすめできそうなものをご紹介します。Rust らしい書き方を学ぶには、やはりこうしたチュートリアルのコードを写経してみるのがいいのではないでしょうか。

あるいは、ここで紹介したチュートリアルではなくて、何か別の言語向けに書かれたチュートリアルを Rust に直してみるのもいいトレーニングかもしれません。実際、私も LSH という小さな C で書かれたシェルを Rust に直してみるなどの遊びをしてみました。

ちょっと突っ込んだ話を知りたい

たとえばもう少し体系的に学びたいとか、特定の文法機能を実アプリケーションでどのように使いこなしたら良いのかを知りたい、といった話題に応えてくれるドキュメントです。

  • The Rust Programming Language: 通称 TRPL。Rust を使う際のバイブル的な存在です。が、すべてをこなすとハードな仕上がりになっている(と個人的には思う)ので、発展的な話題は一旦見切って何かサンプルのアプリケーションの実装に移るといいかもしれません。Rust を書いている最中に何度も立ち返ることになるドキュメントでもあります。Rust だけでなく、コンピュータ一般に関する細かい解説も載っており、読むだけでも勉強になるドキュメントに仕上がっています。
  • Learn Rust With Entirely Too Many Linked Lists [未邦訳]: Rust で LinkedList を実装しながら、LinkedList のように再帰的な構造をもつデータ構造を Rust ではどう扱ったらよいかについて学ぶことができます。また、所有権や unsafe 、スマートポインタの扱い方などのワークアラウンドについても確認することができます。
  • Rust Language Cheat Sheet [未邦訳]: Rust のチートシートではあるものの一歩踏み込んだ話題にも触れていて、たとえば「ムーブが起きた際には、一体裏側では何が起きているの?」などといった細かい話を図付きで確認することができます。メモリレイアウトがどうなっているかは、やはり図で示されるととても理解しやすいです。
  • Rust Cookbook [未邦訳]: Rust は標準ライブラリが薄く作られています。これには理由があるのですが、クレート(ライブラリ)探しを少々がんばる必要があります。「シングルトンを Rust でやりたい」「データベースにつなぎたい」「日付を扱いたい」といったユースケースごとに、どのようなクレート(ライブラリ)を使用したらいいかを教えてくれる本です。
  • The Rustnomicon: Rust には、生ポインタを扱えるようにする unsafe という機能があります。この unsafe を扱う際には数々の危険行為が存在するわけですがそれらについていろいろ教えてくれる本です。Rust でシステムプログラミングをする際には、この本を一読しておくことをおすすめします。
  • The Rust Reference: Rust を構成する各機能について、入門書以上のことが書いてあります。ある機能について、どういうことができるのかなどをより深く知りたくなった場合、この本を参照することがままあります。
  • Rust API ガイドライン: たとえば変数名や関数名はどうつけたらよいのかといった話や、ドキュメントの書き方、どのように関数の引数をデザインしたらよいか、型のよい使い方などが書かれています。
  • Effective Rust[未邦訳]: 文法に少し慣れてきた頃におすすめできるドキュメントです。たとえばマクロをどのタイミングで使ったらよいかや、エラー型の作り方、あるいはボローチェッカーのおさらいや、CIをどうすべきかなど、実アプリケーションをRustで構築する上で必要になる、「入門の次」について教えてくれるドキュメントになっています。他のプログラミング言語におけるEffectiveシリーズと似た立ち位置の一冊に仕上がっていると思います。
  • Common Newbie Mistakes and Bad Practices in Rust: Bad Habits[未邦訳]: これは非公式ですが、他言語出身者が Rust を書き始める際にやりがちな(Rust 的には)ミスを紹介し、それを Rust ではどう回避するのかを教えてくれる記事です。少し慣れてきたころに読むと、役に立つ情報がたくさんあるはずです。

コミュニティの力を借りる

Rust を一人で学んでいると、どうしてもわからないことが出てくると思います。私もそうでした。

Rust には、現在日本の Zulip (Slack のようなコミュニケーションツール)があります。ここで質問してみるのはいかがでしょうか。#beginner や #code というチャンネルがあり、多くの方が質問をしています。

https://rust-lang-jp.zulipchat.com/rust-lang-jp.zulipchat.com

もし英語のコミュニケーションに抵抗のない方であれば、

  • Reddit: クレート(ライブラリ)の作者や Rust 言語の設計者本人からの回答を得られることがたまにあります。日本語で2次情報に当たり続けるより確度の高い情報を得られる可能性があります。
  • ユーザーフォーラムで質問する: こちらも同様に英語圏の詳しい人が答えてくれます。

仲間を見つける

勉強会が都内を中心にいくつか開催されています。COVID-19 の関係で現在はオンライン開催が多くなっていますが、2020年中ですと、下記のような勉強会が開催されていました。

また、日本向けの Rust カンファレンスである Rust.Tokyo というものを毎年11月頃に開催予定しております。2020年は RustFest Global という形で開催しました。2021年は再び Rust.Tokyo として開催していきたいと思っています。

Webサイト(2020年のままです🙇‍♀️) rust.tokyo

Twitter アカウント https://x.com/rustlang_tokyo


更新履歴

  • 2024-04-07: 『AtCoder と Rust で始める!競技プログラミング入門』→『RustCoder ―― AtCoder と Rust で始める競技プログラミング入門』。ならびに、URLを修正。『Effective Rust』を追加。
  • 2022-10-13: 最近アクティブでないLT会を削除。Slack の rust-jp グループを削除。Zulip の rust-jp グループを追加。
  • 2022-01-01: Rustで始める自作組込みOS入門 を追加。
  • 2021-12-05: Rustハンズオン@エウレカ社、Risp (in (Rust) (Lisp))、Common Newbie Mistakes and Bad Practices in Rust: Bad Habits を追加。

CPUエミュレータをRustで自作する

この記事は Rust Advent Calendar 2020 ならびに CyberAgent Developers Advent Calendar 25日目の記事です。

今年のはじめの頃になりますが、『CPUの創り方』という本に載っている TD4 という CPU を実装してみました。TD4 は「とりあえず動作するだけの4bit CPU」の略です。この本に載っている CPU エミュレータを実際に実装してみました。ただし、本書には GUI が載っていましたが、それは省略しました。

CPUの創りかた

CPUの創りかた

  • 作者:渡波 郁
  • 発売日: 2003/10/01
  • メディア: 単行本(ソフトカバー)

「最近話題の RISC-V などの CPU エミュレータを作ってみたいものの、いきなり作るにはハードルが高い。何か簡単なもので素振りをして CPU の動作の仕組みをまずは知りたい」という方にはかなりオススメできる教材だと思います。私自身、TD4 のエミュレータを実装してみて CPU の動作原理やコンセプトがわかり、その後製作中の RISC-V エミュレータに生きているように思います。

今回私が実装したものは下記です。だいたい1日くらいで実装できました:

この記事では、まず CPU の動作原理について TD4 を通じて簡単に解説し、Rust による実装例を見ていきます。また実装したインタプリタについても簡単に解説を加える予定です。

f:id:yuk1tyd:20201225203217p:plain
加算を行う処理を動かしてみた図

今回の記事では Rust を用いた実装になっていますが、Rust 以外の言語でもまったく問題なく実装できる内容だと思っています。たとえば PythonJava 、Go のようなアプリケーション向けの言語であっても問題なく実装できるはずです。Rust のシステムプログラミング言語としての側面を利用した実装箇所は今回はないためです*1

このブログでは恒例行事になっていますが、すべての解説を盛り込んだためかなりのボリュームになっています。お好きなところをかいつまんでお読みください。

リポジトリ

github.com

方針

今回のエミュレーションの方針は、クロックごとのレジスタ内の値を再現することとしました。本書を読むと、実際は CPU を論理回路から作り上げて再現することも可能なのですが、今回は命令を書いてそれを読み込ませるとレジスタに値を読み込んで計算などを行ってくれるという部分を再現することとしました。

予備知識

TD4 のような小さな題材であっても、基本的なアイディアは実際の CPU とそう相違ないはずです。TD4 を元に、CPU に関しての予備知識を少し書いておきたいと思います。

fetch-decode-execute サイクル

CPU は、fetch-decode-execute というステップを踏みながら計算を実行します*2

  1. fetch: メモリ上からプログラムを読み出すフェーズ。
  2. decode: 取り出した命令を元に内部的にどういった処理に対応するかを紐付け、行う計算を確定するフェーズ。
  3. execute: 2で確定した計算を実際に実行するフェーズ。

このサイクルをプログラムが終了するまで実行し続けます。

今回の TD4 エミュレータも同様にこのサイクルを実行して計算を行うように実装しました。

ROM

TD4 では ROM (Read-Only Memory) と呼ばれる領域にプログラムを書き出し、そこからプログラムを1行1行読み取って計算処理を行います。

Rust ではたとえば下記のようにして表現されており、ここにプログラムの内容(今回はバイナリ表現)が入っています。

pub struct Rom {
    pub memory_array: Vec<u8>, // ここに [00000000, 00010000, 11100001] のような形でプログラムが入っている。
}

現在どの番地のプログラムを読み出しているかについては、プログラムカウンタ(pc)と呼ばれるフラグによって管理されます。先ほどの fetch-decode-execute サイクルが1サイクル終了するとプログラムカウンタが足され、次のプログラムを読み出し、ということを ROM の配列が終了するまで行うことになります。

プログラムは「オペレーションコード」と「イミディエイトデータ」と呼ばれる領域に分けて書かれています。

たとえば、00000001 という値があったときには、TD4 は 0000 をオペレーションコード、0001 をイミディエイトデータとして解釈します。ちなみにオペレーションコード 0000 は TD4 では A レジスタ(このあと説明します)の値とイミディエイトデータの ADD 命令を意味します。

レジスタ

一言で言うなら CPU における記録領域のようなものです。

TD4 では A レジスタと B レジスタという2つのレジスタが用意されています。このレジスタに計算途中の内容を出し入れしながら、計算処理を次々行っていきます。

I/O ポート

これは CPU に対して入力を与えたり、あるいは演算の結果を出力するために使用するポートです。TD4 の場合は CPU から直接 I/O が出るという構成を取っているようです。これは規模の小さい CPU で多く採用されている方式だそうです。

TD4 の命令

TD4 では加算命令(add)、レジスタの値の転送命令(mov)、入出力ポートのやりとり(in, out)、ジャンプ命令(jmp, jnc)の4つの動作が組み込まれています。

実際の CPU になってくると、これらに四則演算が追加されたり、浮動小数点演算が追加されたりと高機能になっていきます。

こうした命令はプログラム側に書かれており、CPU の役割は命令を解釈し計算処理を実行していくことにあたります。

CPU エミュレータの実装

それでは CPU エミュレータの実装の紹介に移っていきましょう。

データ構造を用意する

CPU エミュレータを作り始めた際によかった手順としては、まずデータ構造を用意し、その後に一気にそれらを紐付けていくという方法でした*3

最初に命令を表現する enum を用意しました。OpCode という enum です。なお num_derive という便利なトレイトを今回は使用しています。

use num_derive::FromPrimitive;

#[derive(Debug, PartialEq, FromPrimitive)]
pub enum Opcode {
    AddA = 0b0000,
    AddB = 0b0101,
    MovA = 0b0011,
    MovB = 0b0111,
    MovA2B = 0b0001,
    MovB2A = 0b0100,
    Jmp = 0b1111,
    Jnc = 0b1110,
    InA = 0b0010,
    InB = 0b0110,
    OutB = 0b1001,
    OutIm = 0b1011,
}

各命令の詳しい内容は省略しますが、TD4 では12個の命令を実装すればいったん動くようにできています。ということで、enum を12個用意しました。

また、レジスタも用意します。レジスタは A レジスタ、B レジスタ以外に、キャリーフラグとプログラムカウンタを持っています。

#[derive(Clone)]
pub struct Register {
    register_a: u8, // register a
    register_b: u8, // register b
    carry_flag: u8, // carry flag
    pc: u8,         // program counter
}

I/O ポートも用意します。TD4 では入力と出力をもっているので、それらを用意します。

pub struct Port {
    input: u8,
    output: u8,
}

ROM も用意します。これは先ほどもご紹介しましたがもう一度ここに貼っておきます。プログラムの内容そのものを保持しています。

pub struct Rom {
    pub memory_array: Vec<u8>,
}

エントリポイント

今回のプログラムのエントリポイントとして重要なのは CpuEmulator という構造体です。これが実質エミュレータの構造を表現しています。ここに、先ほども説明した fetch-decode-execute サイクルを表現していくとスムーズでした。

まず CPU エミュレータ自体は下記のような構造体です*4

pub struct CpuEmulator {
    register: RefCell<Register>,
    port: RefCell<Port>,
    rom: RefCell<Rom>,
}

まず fetch です。ここでは現状のプログラムカウンタの値を確認し、プログラムカウンタに該当するプログラムを ROM から読み取ります。

(...)
    fn fetch(&self) -> u8 {
        let pc = self.register.borrow().pc();
        if self.rom.borrow().size() <= pc {
            return 0;
        }

        let code = self.rom.borrow().read(pc);

        code
    }
(...)

次は decode です。ここでバイナリ形式になっているオペレーションコードを解読して、先ほども紹介した内部表現(enum Opcode)に変換をかけます。

(...)
    fn decode(&self, data: u8) -> Result<(Opcode, u8), EmulatorErr> {
        let op = data >> 4;
        let im = data & 0x0f;

        if let Some(opcode) = FromPrimitive::from_u8(op) {
            match opcode {
                Opcode::AddA
                | Opcode::AddB
                | Opcode::MovA
                | Opcode::MovB
                | Opcode::MovA2B
                | Opcode::MovB2A
                | Opcode::Jmp
                | Opcode::Jnc
                | Opcode::OutIm => Ok((opcode, im)),
                Opcode::InA | Opcode::InB | Opcode::OutB => Ok((opcode, 0)),
            }
        } else {
            // never comes
            Err(EmulatorErr::new("No match for opcode"))
        }
    }
(...)

最後は exec です。先ほどの decode の結果をもとに、その Opcode に対応した関数を実行させます。

(...)
    pub fn exec(&self) -> Result<(), EmulatorErr> {
        loop {
            let data = self.fetch();
            let (opcode, im) = self.decode(data)?;

            match opcode {
                Opcode::MovA => self.mov_a(im),
                Opcode::MovB => self.mov_b(im),
                Opcode::AddA => self.add_a(im),
                Opcode::AddB => self.add_b(im),
                Opcode::MovA2B => self.mov_a2b(),
                Opcode::MovB2A => self.mov_b2a(),
                Opcode::Jmp => self.jmp(im),
                Opcode::Jnc => self.jnc(im),
                Opcode::InA => self.in_a(),
                Opcode::InB => self.in_b(),
                Opcode::OutB => self.out_b(),
                Opcode::OutIm => self.out_im(im),
            };

            // To prevent infinite loop
            if opcode != Opcode::Jmp && opcode != Opcode::Jnc {
                self.register.borrow_mut().incr_pc();
            }

            if self.does_halt() {
                return Ok(());
            }
        }
    }
(...)

細々とした各関数の実行内容については、こちらのコードをご覧いただくと、各々の命令がどういった処理を行っているかについて概略を掴むことができるかと思います。

実行自体は、CpuEmulator::withCpuEmulator の構造体を生成したあとに exec() 関数を呼び出すことによって行われます。program という箇所に、たとえば [00110011, 00000001] のようなバイナリが入ってきて、これを解釈して計算処理が走るというのが、このエミュレータの大まかな構造です。

(...)
    let rom = Rom::new(program);
    let register = Register::new();
    let port = Port::new(0b0000, 0b0000);
    let emulator = CpuEmulator::with(register, port, rom);
    match emulator.exec() {
        Ok(_) => (),
        Err(err) => panic!("{:?}", err),
    }
(...)

命令コンパイラの実装

さてここからは、本などには載っていない独自コンテンツになります。命令をアセンブラのように書くと、中でコンパイルして CPU エミュレータ用のプログラムに変え、シームレスに計算処理まで紐付けられる実装を追加してみました。

設計

今回の TD4 エミュレータは、バイナリを渡す必要があります。これでも十分楽しめるのですが、せっかくなのでアセンブラのような書き味の形式のファイルを用意して、それを読み込むとコンパイルが走ってバイナリ表現に変えてくれる形式にしてみたら、より使いやすいエミュレータになるのではないかと思いました。

具体的には、下記のようなファイルを読み込ませると、中で加算処理を行い加算結果を返してくれるというようなものです(コメント部分は実際のファイルには入れられません)。

mov A 0001 // 0001 という値を A レジスタに転送する
add A 0001 // A レジスタの値と 0001 を加算する
mov B A // A レジスタの値を B レジスタに転送する
out B // B レジスタの内容を出力する

このファイルを sasm(simple assembly の略のつもり)という拡張子に変えたテキストファイルにして保存しておき、TD4 エミュレータに読ませると、あとは中で任意の計算処理を走らせるようにしました。

なお、出来としてはおもちゃレベルのもので、エラーハンドリングなども結構雑に作ってあります。意図しない構文を入れると普通に落ちると思います。

パース部分の実装

よくあるコンパイラのパーサーのデザインだと思いますが、下記のような構造体を用意しました。私は 9cc を作ったことがあるのですが、それを一部真似しました。

pub struct Parser {
    pos: usize, // 今どの番地を読んでいるのかを保持する
    source: Vec<String>, // ファイルから読み込んだ内容を文字列で保持する
}

このアセンブラの内容はとてもシンプルなので、空白部分 split をかければ、欲しい内容は一通り抽出できてしまいます。たとえば

mov A 0001

この場合ですと、空白で split をかけると、mov, A, 0001 という文字列が取得できます。TD4 の場合、命令がとても単純なので、たとえば mov の後ろには必ず A か B という文字列が来ているはず、といった感じでシンプルに条件分岐をしながらパースしていくと、一通り命令をパースして解釈できるようになります。

mov の場合のパースの実装例は、たとえば下記のようになっています。パース関数はこちらにあります。

(...)
    pub fn parse(&mut self) -> Result<Vec<Token>, EmulatorErr> {
        let mut result = Vec::new();

        loop {
            let op = self.source.get(self.pos);

            if op.is_none() {
                break;
            }

            let op = op.unwrap();

            if op == "mov" {
                self.pos += 1;
                let lhs = self
                    .source
                    .get(self.pos)
                    .ok_or_else(|| EmulatorErr::new("Failed to parse mov left hand side value"))?;

                self.pos += 1;
                let rhs = self
                    .source
                    .get(self.pos)
                    .ok_or_else(|| EmulatorErr::new("Failed to parse mov right hand side value"))?;

                let token = if lhs == "B" && rhs == "A" {
                    Token::MovBA
                } else if lhs == "A" && rhs == "B" {
                    Token::MovAB
                } else {
                    Token::Mov(
                        Register::from(lhs.to_string()),
                        self.from_binary_to_decimal(rhs)?,
                    )
                };

                result.push(token);
            }
(...)

最終的な結果は Token と呼ばれる enum に詰めて返しています。この enum は Opcode とは別物にしてあって、下記のような定義にしました。

pub enum Register {
    A,
    B,
}

pub enum Token {
    Mov(Register, u8),
    MovAB,
    MovBA,
    Add(Register, u8),
    Jmp(u8),
    Jnc(u8),
    In(Register),
    OutIm(u8),
    OutB,
}

そしてこの Token は、のちのコンパイルフェーズで一旦バイナリ表現に変換されます。

コンパイル部分の実装

コンパイル部分の実装も行いました。

Token ごとに所定のバイナリに変換していきます。たとえば add A 0001 とあったら、まず A レジスタ値との加算命令をしめすバイナリ 0000 とイミディエイトデータ 0001 をくっつけるイメージです。

(...)
    pub fn compile(&self, tokens: Vec<Token>) -> Result<Vec<u8>, EmulatorErr> {
        if tokens.is_empty() {
            return Err(EmulatorErr::new(
                "Failed to start to compile because token list is empty.",
            ));
        }

        let mut result = Vec::new();

        for token in tokens {
            let program = match token {
                Token::Mov(Register::A, im) => self.gen_bin_code(0b0011, im),
                Token::Mov(Register::B, im) => self.gen_bin_code(0b0111, im),
                Token::MovAB => self.gen_bin_code_with_zero_padding(0b0001),
                Token::MovBA => self.gen_bin_code_with_zero_padding(0b0100),
                Token::Add(Register::A, im) => self.gen_bin_code(0b0000, im),
                Token::Add(Register::B, im) => self.gen_bin_code(0b0101, im),
                Token::Jmp(im) => self.gen_bin_code(0b1111, im),
                Token::Jnc(im) => self.gen_bin_code(0b1110, im),
                Token::In(Register::A) => self.gen_bin_code_with_zero_padding(0b0010),
                Token::In(Register::B) => self.gen_bin_code_with_zero_padding(0b0110),
                Token::OutB => self.gen_bin_code_with_zero_padding(0b1001),
                Token::OutIm(im) => self.gen_bin_code(0b1011, im),
            };
            result.push(program);
        }

        Ok(result)
    }
(...)

あとは gen_bin_code などの関数が、指定のバイナリを生成して返すというイメージです。イミディエイトデータを受け取らない命令も TD4 にはあるのですが、その場合は 0000 で詰めればよいことに仕様上なっているので、それ用の関数も用意しました。

やってみた感想

コンピュータの内部については、これを実装してみるまでは全然知らない状態でした。何がどこから読み込まれて計算処理が行われるのかについて、あまり理解できていませんでした。

まず、CPU エミュレータを実装してみたことによって fetch-decode-execute サイクルに関して知ることができ、「このようにしてコンピュータは動いているのか!」と身を持って理解できたように思います。

コンパイラのフェーズは、単に空白を split しただけですし、登場してくる文字列もパターンがかなり定まりきったものを使っただけなので、そこまで難しいことはしていないのですが、自分で1からこうしたコンパイラインタプリタを作るのは楽しいですね。

ちょっとやってみたいなと思ったものの、実力が足りずにできなかったなと思っているものは、今回用意したアセンブラを吐くプログラミング言語を自分で設計して、そのコンパイラを実装してみるというものです。まだまだプログラミング言語そのものに対する理解や、文法の設計経験などが足りないため難しいです。が、いつか取り組めたらいいなと思いました。

次は RISC-V のエミュレータにもチャレンジしてみています。命令数ははるかに多いですし、考慮しなければならない内容やコードベースもこの TD4 エミュレータと比較すると比ではないくらいに多いのですが、がんばって作りきろうと思っています。

*1:パターンマッチがあると、命令のデコード周りをきれいに実装できるかな、というくらいですかね。

*2:fetch-decode-execute cycle: https://www.bbc.co.uk/bitesize/guides/z2342hv/revision/5

*3:ちょっと記憶がなく、そこからしっかり始めたかはもう覚えていませんが。

*4:今思うとここは RefCell である必要はなく、おとなしく &mut にするべき箇所だったかもなと思っています。

Rustでもモナドは実装できるのか?(再)

この記事は言語実装Advent Calendar 2020 25日目の記事です。(2022-11-06: 記事の内容を追記していますが、この記事の結論としては「似たようなものは作れるが、完全体にはならない」です)

モナドに関する話題が言語実装アドベントカレンダーの範疇に入るのかわかっていませんが*1プログラミング言語がお好きな方はきっとモナドもお好きだろう…ということで、Rust におけるモナドの扱いについて記事にしたいと思います。

この記事では、Rust を使って

  • モナドを実装してみる。
  • do 記法を実装してみる。

ところまでやってみました。後半で、GATs と呼ばれる Rust の nightly に入った機能に関して少し細く説明を加えています。

なおこの記事では、モナドとは何かという話はあまり触れていません。

さらに執筆時間*2と記事の都合上、Rust 言語の細かい文法に関する解説もとくに行っていません🙇‍♀️ 登場してくる文法には、適宜注釈でコメントをできるかぎり付与するようにしましたが、不十分かもしれません。

今回の記事は、ずいぶん前に登壇した内容のアップデートです。この発表以降にさらに Rust の言語機能にアップデートがあり、その内容を使ってモナドを実装してみるという記事です。

Rust でもモナドは実装できるのか? - Speaker Deck

前提知識

解説を加えてしまうと記事の長さがとても大変なことになってしまうので今回は省かせていただきますが、いくつか詳しく解説された記事があるのでそちらをリンクさせていただきます。

高階カインド型

まず高階カインド型そのものについては、Scala による説明ですが、下記の記事が直感的でわかりやすいです。

qiita.com

また、なぜ高階カインド型が必要とされるのかについては、この記事がわかりやすいです。

keens.github.io

モナド

モナドというのはいくつか説明の仕方があるかとは思いますが、

ubiteku.oinker.me

個人的にはこの記事の説明が丁寧でわかりやすいかなと思いました。

従来のエミュレーション方法

従来のやり方では、HKT<T> と呼ばれる高階カインド型を表現するトレイトを用意し、HKT トレイトに関連型を2つ(高階を示すものと、高階の中身の型を示すもの)用意すれば、完全ではないものの近い形でエミュレーションできました。たとえば、従来のやり方ではモナドは下記のようにエミュレーションできます。

trait HKT<T> {
    type C;
    type H;
}

trait Functor<U>: HKT<U> {
    fn map<F>(self, f: F) -> Self::H
    where
        F: Fn(Self::C) -> U;
}

trait Monad<U>: Functor<U> {
    fn pure(self, m: U) -> Self::H;
    fn bind<F>(self, f: F) -> Self::H
    where
        F: Fn(Self::C) -> Self::H;
}

単純なデータ構造を例にとって、実装をしてみます。たとえば Id モナド*3を実装してみると、

struct Id<T>(T);

// 高階カインドに関するエミュレーションをここで行う。
impl<T, U> HKT<U> for Id<T> {
    type C = T;
    type H = Id<U>;
}

// ファンクタを定義する
impl<T, U> Functor<U> for Id<T> {
    fn map<F>(self, f: F) -> Self::H
    where
        F: Fn(Self::C) -> U,
    {
        Id(f(self.0))
    }
}

// モナドを定義する
impl<T, U> Monad<U> for Id<T> {
    fn pure(self, m: U) -> Id<U> {
        Id(m)
    }

    fn bind<F>(self, f: F) -> Id<U>
    where
        F: Fn(T) -> Id<U>,
    {
        f(self.0)
    }
}

といった形で、一応型パズルは解け、実際に動かしてみるときちんとそれらしい動きをしていることがわかります。残りは発表資料をご覧ください。

Generic Associated Types を用いたエミュレーション(new!)

ここからが本題です。

Rust nightly 1.50 から入った Generic Associated Types(解説は後ほど)という機能を使うと、従来の HKT トレイトを使う場合と比べ、かなり実装をきれいにすることができます。

1つ1つ型クラスを定義していきます。

型クラスを定義する

Functor を用意する

まずは Functor を用意します。Functor は変換処理の一般化です。

この FunctorFunctor の型パラメータとなる A を関連型 *4 でもたせ、高階カインド型そのものを Lifted<B> という形でもたせます。LiftedFunctor を実装してある必要があるという制約も付与しています。ここに後ほど具体的な型が入ってくることになります。

pub trait Functor {
    type A;
    type Lifted<B>: Functor;

    fn map<F, B>(self, f: F) -> Self::Lifted<B>
    where
        F: FnMut(Self::A) -> B;
}

そして、Lifted<B> の部分に、いわゆる Generic Associated Types(GATs)が使用されています。GATs については後ほど解説します。現在の stable Rust においては、このように Lifted という関連型に型パラメータを付与することはできません。

Pointed を用意する

続いて Pointed を用意します。Pointedpure 関数の一般化です。この関数は、元の型をモナドの文脈の型に変換する機能を持ちます。

PointedFunctor のトレイト境界をもちます。実装先が、Functor も実装してある必要があります。

pub trait Pointed: Functor {
    fn pure(t: Self::A) -> Self::Lifted<Self::A>;
}

Applicative を用意する

続いて Applicative を用意します。Applicative は関数適用の一般化です。apply という関数を持ちます。トレイト境界に Pointed を持ちます。

pub trait Applicative: Pointed {
    fn apply<F, B, C>(self, b: Self::Lifted<B>, f: F) -> Self::Lifted<C>
    where
        F: FnMut(Self::A, B) -> C;
}

Monad を用意する

最後に Monad を用意します。Monad は手続きの結合の一般化です。bind という関数を持ちます。トレイト境界に Applicative を持ちます。

pub trait Monad: Applicative {
    fn bind<B, F>(self, f: F) -> Self::Lifted<B>
    where
        F: FnMut(Self::A) -> Self::Lifted<B>;
}

いくつか型を実装していく

ここまで用意できたところで、実際にいくつか型を実装していきましょう。まずは最も単純な例として、先ほどもご紹介した Id モナドを実装してみます。

pub struct Id<M>(pub M);

impl<A> Monad for Id<A> {
    fn bind<B, F>(self, mut f: F) -> Id<B>
    where
        F: FnMut(A) -> Id<B>,
    {
        f(self.0)
    }
}

impl<A> Pointed for Id<A> {
    fn pure(t: A) -> Id<A> {
        Id(t)
    }
}

impl<A> Applicative for Id<A> {
    fn apply<F, B, C>(self, b: Id<B>, mut f: F) -> Id<C>
    where
        F: FnMut(A, B) -> C,
    {
        Id(f(self.0, b.0))
    }
}

impl<A> Functor for Id<A> {
    type A = A;
    type Lifted<B> = Id<B>;

    fn map<F, B>(self, mut f: F) -> Id<B>
    where
        F: FnMut(A) -> B,
    {
        Id(f(self.0))
    }
}

また、Rust にすでに存在する OptionResult も、一応今回用意したモナドにすることができます。*5

まずは Option モナドを用意してみます。

impl<A> Monad for Option<A> {
    fn bind<B, F>(self, mut f: F) -> Option<B>
    where
        F: FnMut(A) -> Option<B>,
    {
        self.and_then(f)
    }
}

impl<A> Pointed for Option<A> {
    fn pure(t: A) -> Option<A> {
        Some(t)
    }
}

impl<A> Applicative for Option<A> {
    fn apply<F, B, C>(self, b: Option<B>, mut f: F) -> Option<C>
    where
        F: FnMut(A, B) -> C,
    {
        let a = self?;
        let b = b?;
        Some(f(a, b))
    }
}

impl<A> Functor for Option<A> {
    type A = A;
    type Lifted<B> = Option<B>;

    fn map<F, B>(self, mut f: F) -> Option<B>
    where
        F: FnMut(A) -> B,
    {
        self.map(f)
    }
}

また、Result モナドは今回は Ok 側にバイアスをもたせた形で用意してみました。

impl<A, E> Monad for Result<A, E> {
    fn bind<B, F>(self, f: F) -> Result<B, E>
    where
        F: FnMut(A) -> Result<B, E>,
    {
        self.and_then(f)
    }
}

impl<A, E> Pointed for Result<A, E> {
    fn pure(t: A) -> Result<A, E> {
        Ok(t)
    }
}

impl<A, E> Applicative for Result<A, E> {
    fn apply<F, B, C>(self, b: Result<B, E>, mut f: F) -> Result<C, E>
    where
        F: FnMut(A, B) -> C,
    {
        let a = self?;
        let b = b?;
        Ok(f(a, b))
    }
}

impl<A, E> Functor for Result<A, E> {
    type A = A;
    type Lifted<B> = Result<B, E>;

    fn map<F, B>(self, mut f: F) -> Result<B, E>
    where
        F: FnMut(A) -> B,
    {
        self.map(f)
    }
}

現状実装できないもの

ただし、関数型プログラミングにおいて利用する道具が完全に実装できるというわけではありません。たとえば、

  • いわゆる flattenjoin の処理はコンパイル時にコンパイラがパニックを出して落ちる(バグの可能性がある)。
  • traverse を実装しようとするとうまくコンパイルが通らない*6

といった内容が、この記事にて報告されていました

do 記法

Haskell には do 記法、Scala には for-yield と呼ばれる構文があり、これらを用いることで次のように bind(あるいは flatMap)がいくつも重なってしまう現象を回避できたりします。

// Rust による例
Option::pure(...).bind(|o| return_option_function(o).bind(|p| return_option_function(p))

モナドの真骨頂は、こうした do 記法や for-yield などとともに利用するところにあると思うのですが、Rust にはそうした専用の構文はありません。

そこで、Rust のマクロという機能を用いて do 記法を実装しました。do は Rust においては予約語になっており使用できないので、monad-do から取って mdo というマクロを作りました。

macro_rules! mdo {
    ($i:ident <- $e:expr; $($t:tt)*) => {
        $e.bind(move |$i| mdo!($($t)*))
    };
    ($e:expr; $($t:tt)*) => {
        $e.bind(move |()| mdo!($($t)*))
    };
    (ret $e:expr) => {
        $e
    };
}

少し Rust のマクロに関して補足を入れておくと、

  • $i, $e, $t: マクロ内における変数。
  • $(...)**: 0回以上の繰り返しを意味します。
  • :ident: これはいわゆる識別子がやってくることを示します。
  • :expr: これはいわゆる式がやってくることを示します。
  • :tt: 何か単一のトークン木がやってくることを示します。

内部で軽い構文解析を行い、<- の前後を解析して式なのか識別子なのか、それ以降に続く別のトークン木なのかを見分けます。その後、取り出せた式と識別子を使ってモナドに紐づけて実装されている(はずの) bind を呼び出し、残ったトークン木を更に再帰的に mdo! マクロにかける、ということをしています。また、結果は ret と書いた後ろの式を返します。

これを用いることで、

mdo! {
    a <- {何かモナドを作る};
    b <- {何かモナドを作る};
    ret result(a +b) // 何か結果を返す
}

といった記法が可能になります。

実際 Rust でこれを使用してみると、下記のように記述可能になり、テストを通すことができました。

mod test_do {
    use crate::data::option::*;
    use crate::{applicative::Applicative, functor::Functor, functor::Pointed, monad::Monad};

    #[test]
    fn test_do_notation() {
        let actual = mdo!{
            x <- Option::pure(1);
            y <- Option::pure(2);
            ret Option::pure(x + y) // Some(3) が返るはず
        };
        assert_eq!(actual, Some(3));
    }
}

便利ですね。

Generic Associated Types(GATs)とは何か

ここからは言語実装やプログラミング言語全般の話というより Rust 特有の事情の話になってしまい大変恐縮なのですが、GATs が一体何なのか、どういう使い道があるのかについて RFC を読みながら簡単にまとめておきたいと思います。

github.com

GATs というのは先ほども軽く触れたとおり、関連型に何かしらの型パラメータ(AT みたいなもの)をもたせることができる機能です。Rust にいわゆる高階カインド型を導入するための機能です。

Rust の場合は、他の言語でもあるような型パラメータ以外にもライフタイム注釈*7をこの位置に入れることができます。つまり、型パラメータの位置に入るのは A というような型情報と、もうひとつは 'a というライフタイム注釈が来ることになります。GATs はこれら2つを関連型で扱えるようにするための機能です。

下記は RFC から拝借してきたコードですが、ライフタイムに関しては次のような記述が GATs で行えるようになります。これは Rust を書いていると多々直面する内容で、ユーザーが求めていた機能でもありました。

trait StreamingIterator {
   type Item<'a>;
}

impl<T> StreamingIterator for StreamIterMut<T> {
    type Item<'a> = &'a mut [T];
    ...
}

また、型パラメータを関連型にもたせる側では、たとえば下記のような記述が GATs を用いて行えるようになります。Rust には RcBox などのスマートポインタがいくつか存在しますが、これらは型パラメータを引数に取ります。そうしたポインタを関連型の具象実装側を切り替えることで切り替えたい場合に、GATs が役に立ちます。

trait PointerFamily {
    type Pointer<T>: Deref<Target = T>;
    fn new<T>(value: T) -> Self::Pointer<T>;
}

struct ArcFamily;

impl PointerFamily for ArcFamily {
    type Pointer<T> = Arc<T>;
    fn new<T>(value: T) -> Self::Pointer<T> {
        Arc::new(value)
    }
}

struct RcFamily;

impl PointerFamily for RcFamily {
    type Pointer<T> = Rc<T>;
    fn new<T>(value: T) -> Self::Pointer<T> {
        Rc::new(value)
    }
}

struct Foo<P: PointerFamily> {
    bar: P::Pointer<String>,
}

RFC によると、GATs が入ったからと言ってモナドを完全に実装できるようになるというわけではないと注意書きがなされています。私がモナドを実装することに関してそこまで深い知識があるわけではないので、一体どういったポイントが足りなくてそうなっているのかは今後の探求の課題だなと思いました。

追記(2022-11-06)

さて、この記事を書いてから2年が経ち、いくつかの検証記事やそもそも GATs が stable になるといったアップデートがありました。この件を少し補足しておきます。

まず結論から行くと、

私がモナドを実装することに関してそこまで深い知識があるわけではないので、一体どういったポイントが足りなくてそうなっているのかは今後の探求の課題だなと思いました。

これに足りない部分を検証している記事があります。

zenn.dev

Monad であれば Applicative を Monad から定義できるはずですが、どうやら難しいようです。具体的には map2 の実装時に返しの型を一つに定められなくなる、という問題があるようです。

GATs がいわゆる関連型である都合、型をひとつに同定することが難しく、たとえば、Option 型に対する Monad を実装しているにもかかわらず Result 型を指定できてしまいます。言語機能的に、関連型についた型パラメータがきちんと消費されているかは見ていないようで、これも実装できないポイントの一つです。

impl<A> Monad<A> for Option<A> {
  type A = A;
  type This<B> = Result<A, Error>;
}

そもそも Applicative を Monad で定義できない問題もありますし、運用に「関連型に必ず正しい型を入れる必要がある」といったような紳士協定を結ぶ必要があるので普段使いは難しそうですね。後者の問題はマクロを使って解決できそうではありますが、試していないのでわかりません。

リポジトリ

まだいろいろ実験中ですが、リポジトリはこちらにあります。

github.com

参考文献

*1:カレンダーに登録してみたものの、プログラミング言語そのものに関わりそうな話題としての持ちネタがこれくらいしかありませんでした🙏

*2:12/24に書き始めたのが間違いだった。もう少し時間を取るべきでしたね。

*3:恒等モナド。単に 1i32 のような値をモナド文脈の中に持ち込める存在です。これを用いるとたとえば、Id(1).map(|i| i + 1) = Id(2) のような計算を行うことができます。

*4:Rust ではトレイト内部に type という他の言語でも見られるような型エイリアスをつけることができます。これは関連型と呼ばれ、Rust を書いていると何度も登場してくる概念になります。高階カインド型のエミュレーションは、この関連型を用いて行うことになります。後ほど解説しますが、現状の stable Rust ではこの関連型に型パラメータを付与することはできません。が、nightly で型パラメータを付与することが可能になり、より関連型の一般化をしやすくなりました。

*5:Rust では実際のところ、これらの型は Iterator として一般化されているのであまりやる意味はないのですが…

*6:ただ、これは直せそうな気がしました。関連型のうちどれを使用すればいいかをきちんと明示的に書いてあげる必要があるかも?

*7:Rust にはダングリングポインタを防止するための仕組みとしてライフタイムという概念が存在します。このライフタイムというのは、ユーザーがライフタイム注釈を個別に指定してライフタイムを明示的に書くこともできるようになっています。ライフタイム注釈というのは 'a というようにシングルクオートで始まる形で、通常の型情報と同じ位置(<> 内)に入れて書きます。

RustFest Global を開催しました

この記事は Rust Advent Calendar 2020 その3の4日目の記事です。今日は Rust に関する話ではあるのですが、技術的な話ではない記事になってしまうことをお許しください。

1ヶ月ほど経ってしまいましたが、Rust の全世界的なカンファレンス RustFest Global を、11/7〜11/8で開催しました。スピーカーとして参加してくださった皆さん、また RustFest Global に遊びに来てくださった皆さん、ありがとうございました。

今日はその RustFest Global に関する話を書きたいと思います。ちなみに多分この記事を Google 翻訳にかけて読まれる海外の方も多いと思うので、先に書きます。英語にするので少しお待ち下さい!

For non Japanese speakers: I'm going to jot down my thoughts regarding RustFest Global. Unfortunately, there is no English version right now. I'm planning to translate this post into English soon. Please gimme a moment!

RustFest Global とは?

f:id:yuk1tyd:20201204143538p:plain
RustFest Global

rustfest.global

ヨーロッパの RustFest チームの声掛けで始まった、複数のタイムゾーンにまたがる Rust カンファレンス

たしか夏前だったと思いますが、RustFest チームからの声掛けで、今回 Rust.Tokyo のチームもこのカンファレンスの運営に参加することになりました。

RustFest チームというのはヨーロッパ圏の Rust カンファレンスを開くチームで、ヨーロッパで毎年カンファレンスを開催しています。前回はバルセロナだったと思います。実は去年の Rust.Tokyo にて、Rust コアチームの Florian Gilcher 氏が基調講演を行ってくれましたが、彼も RustFest チームの主催者の一人でした。現在は卒業生のようです。

Rust.Tokyo は今年は中止の判断をしていた

私たち Rust.Tokyo のチームは、今年は Rust.Tokyo を実施しないという判断をしていました。理由はご多分に漏れずコロナウィルスです。中止の判断をした4月時点では、コロナウィルスがいつ収まりを見せるか、あるいはどのように今後感染拡大していくのかがまったく見えない状態でした。周りのカンファレンスも中止の判断をしているところが多かったというのもあります。

rust.tokyo

しかし一方で、2020年になって Rust はさらに広まりを見せ、私自身も本を共著で出版させてもらうなど盛り上がりを感じていました。そのような状況でカンファレンスを今年は開けないというのは、少し歯がゆい思いがありました。

そんななかでの RustFest チームからの声掛けということもあり、Rust.Tokyo としてもぜひ、ということで運営に参加することになりました。

ラテンアメリカのチームも一緒に運営をすることに

Rust.Tokyo 以外には、日本のユーザーの方は本当にあまり馴染みがないかもしれませんが、Rust LATAM というラテンアメリカのチームも運営に参加することになりました。彼らはアルゼンチンなどに済んでいるようです。日本の真裏、12時間の時差です。

開催まで

毎週ヨーロッパとラテンアメリカと一緒にミーティング

開催までは、毎週ヨーロッパとラテンアメリカ、ならびに日本のチームが Zoom で集まってミーティングを行いました。

グローバル規模で会議をすることになって大変だったのは時差の問題です。JST では1時開始のミーティングでした。ラテンアメリカチームが入ってきて、JST で19時スタート(ラテンアメリカは朝の7時スタート)のミーティングも追加され、隔週で時間帯をラテンアメリカと交代しながら行いました。

私は普段は英語はそれなりに聞けるのですが*1、夜中の1時に第二外国語を聞くのはなかなかハードでした笑。でも、毎週のミーティングは楽しかったです :)

翻訳チームの結成

今回のカンファレンスは「グローバルである」ことにとてもこだわっていました。つまり、Rust.Tokyo は日本だけでなくアジア太平洋地域(APAC)の担当をすることが期待されていました。

本来であればアジアの様々な国の言葉に英語の文章をローカライズして提供するべきだったのですが、参加者の人口比やツテの問題などを考慮して、韓国語と中国語(簡体字繁体字)の翻訳ができる方を募集しました。

韓国語については Enwei Jin さん、中国語の簡体字については Xidorn Quan さん、繁体字については Rust.Tokyo にも参加してくれた Cheng You Bai さんと Kan-Ru Chen さんが担当してくださいました。

改めてお礼をさせてください!本当にありがとうございました。Thank you for the translation team! I appreciate your swift & professional work.

翻訳チームとは基本的にすべて英語でやりとりをしました。英語は世界の標準語になっていますね。

翻訳チームには、主に RustFest のアカウントで告知される内容の翻訳と、CfP に際してサイトに掲載された文章を翻訳していただきました。たとえばこのような感じに。

全然話が逸れますが、個人的には、実際に翻訳されてあがってきた文章を見ながら「この言語ではこういう言い方をするんだ〜」というのを知ることができてとてもおもしろかったです。私は韓国系のドラマや YouTuber を見るのが好きで、韓国語を少しだけ勉強しているというのもあり、韓国語はとくに勉強になりました。できれば英語の字幕なしでそうした番組や YouTube の動画を観られるようになりたい…。

発表が英語でなかった場合の事前字幕付け

発表者が英語話者でない場合も想定していました。その場合には事前にプレゼンテーションを録画してもらい、その録画内容に字幕をつけることで対応という形になりました。

結果、日本から参加してくださったスピーカーの方は日本語でお話いただきました。ほかは、すべて英語のセッションとなりました。

字幕自体はプロの翻訳の会社に依頼してつけてもらいました。できあがった成果物について、スピーカーが話している内容と字幕の表示される内容があっているか、また字幕が表示されるタイミングは正しいかを確認しました。

準備

準備のほとんどは RustFest チームが行ってくれました。改めて本当にありがとうございました。

  • スピーカーの募集
  • スポンサーの募集
  • アーティストの募集
  • スケッチノーターの募集
  • 使用するツールの手配
  • 翻訳業者の手配

などを行っていました。

日本のカンファレンスと圧倒的に違うと感じたのは、アーティストの募集とスケッチノーターの募集でした。アーティストによる演奏があるカンファレンスは、日本ではまったく見ませんね。海外系のカンファレンスだと結構見るのでわりと一般的だと思います。アメリカの Rust のカンファレンスの RustConf は演奏していたような気がします。

スケッチノートというのは、日本でもカンファレンスに参加した方がボランティアで SNS などに流してくださるのを見ることはあるかもしれません。一方で、このように公式に募集しているカンファレンスは、私の知っている範囲が狭いだけかもしれませんが、カンファレンスサイドが公式に募集しているのは日本ではあまり見ないように思います。

ヨーロッパ圏というか欧米圏は、このようにアートも含めて「場」を設計するところに力を注いでいるところがとても見習うべきポイントだなと個人的には思いました。神は細部に宿る、のかもしれません。

(日本におけるアートの立ち位置は、今回のイベントのように(ヨーロッパのような)積極的に「場」に入れ込んでいくという立ち位置では必ずしもないように思います。日常にアートがそこまで入り込んでいないという感じがあります。東京には美術館は多いんですけどね。カンファレンスや人が集まった際、ふとした瞬間にアートを入れようとはならないのだと思います。私だけかもしれませんが、「何かこう、気合いをいれて楽しむもの」という印象が強いかもしれません。なので、カンファレンスとアートを融合させようという発想にそもそも至りません。ヨーロッパ圏とアジア圏のアートの考え方やアートへの接し方の違いはとても興味がわきました。)

あつ森のグッズ

同じく RustFest 主催者の Pillar さんがあつ森用のグッズを作ってくれたので、記念にもらって撮影してみました。

めっちゃかわいいのである。

当日

チャットルームのモデレータ

私は主にチャットルームのモデレータをしていました。Code of Conduct に反する発言をする人がいないかを監視していました。

途中で「資本主義とはなんたるか、あなたはどう思うか」というコメントが始まって、テックイベントで政治的発言は大丈夫なのかな…と思う場面もありましたが、スピーカーの方が機転を利かせて「あとは DM しよ!」と言ってくれていて内心かなりホッとする出来事がありました笑。

結局まあまあ見てしまった

20時間にも及ぶカンファレンスでしたが、日本時間であれば、開始からラテンアメリカの途中までは見られるタイムスケジュールでした。どのセッションもおもしろく、ところどころ休憩を取りながらすべてのブロックを一通り見ることができました。

次々に日が昇っていく

運営のチャットルームがあったんですが、APAC が終わったくらいで日が昇ってくる写真がヨーロッパから投稿されるなど、ワイワイ楽しくやっていました。

日本は日本から開始すると一番早く日がのぼっている国で、ヨーロッパが次に日が昇り、ラテンアメリカが最後に日が昇るという感じでした。実はラテンアメリカの方は APAC のセッションの方の最初の方は見てくれていて、最初のプレゼンテーションの前には「gambatte!」というコメントをくれてとてもほっこりしました。

難しいと感じたこと

英語の壁

日本向けのカンファレンスではないので仕方がありませんが、やはり英語のセッションのときは如実にTwitterやチャットルームのリアクションが減ってしまったように思いました。英語、大変ですよね。私もネイティブスピーカーというわけではないので、英語を使う際は少し頭を切り替えないといけません。

日本に住んでいると、英語を使う機会がそもそもありませんよね。英語を見ない・聞かない・話さない日が大半だと思います。自分から注意深く英語のコンテンツを見るようにしないと、なかなか触れる機会がないと思います。これは、地政学的な要因や文化的な要因が絡んでいて、致し方ない問題だと思います。

英語の壁の突破策は、やはり同時通訳なのでしょう。ScalaMatsuri などでは同時通訳で日本語→英語訳、あるいは英語→日本語訳が聞けたりしますが、そうした施策はやはり有用なのだなあと思いました。こうした同時通訳の用意などは、今回感じた「完全なローカライゼーション」への課題感にもつながっていきます。

すべての人が楽しめるカンファレンスにするために、言語の障壁はできる限り取り払わなければならないというのは、去年の Rust.Tokyo でも感じたことでした。

「完全な」ローカライゼーション

ローカライゼーションというのは難しいですね。日本語訳を用意することはもちろんローカライゼーションの一つではあるのですが、それだけでは足りないことがあります。

たとえば最近あがっていた記事でおもしろかったものなのですが、海外サイトのローカライゼーションだけでも、これだけ気にしなければならないことが出てきます。デザインだけでなく、よく使われる言葉やキャッチコピーに変えるなどの対応も必要になってきます。

zenn.dev

ツールに関するローカライゼーションなどもあるでしょう。たとえばメッセージングアプリに関して言えば、海外では WhatsApp が大半ですが日本では LINE が大半といった具合にです。日本では使い慣れないツールを使う必要が出てくると、どうしても操作に慣れなくてストレスが…といったこともあるかもしれません。

要するに、言語の翻訳だけではなく文化の翻訳も本来は行う必要がある、ということです。

しかし、こうしたローカライゼーションは完全対応しようとすると、費用と人がより多く必要になります。限られた資源の中で適切なローカライゼーションを優先順位をつけて行っていく必要があるというのが現実です。的確なローカライゼーション施策を打つのはとても難しいのだなあと思いました。

来年以降

RustFest Project 始動

まだ詳細は未定の部分が多いですが、RustFest Project が始動します。

これは、たとえば今はコミュニティが存在しない国や地域で新しくコミュニティを立ち上げたい!となった際に、RustFest Project がいろいろノウハウや資金面でコミュニティの立ち上げや運営を援助できる仕組みです。

blog.rustfest.eu

予算の使途などをオープンに管理するために下記のページで今後予算状況や何に使用したかなどを知ることができます。ならびに、金銭的なコントリビューションをこのページから応募することもできます。

opencollective.com

技術とコミュニティは密接な関係にあります。その技術が、いい形で普及するかどうか、また発展するかどうかはコミュニティの力にかかっています。こうした、 Rust がコミュニティを大切にする姿勢は、Rust の好きなところのひとつでもあります。

遊びに行きたい

コロナ終わってたら来年の RustFest と Rust LATAM に遊びに行きたいです!

*1:ただ、子どものころ英語を使う環境にいただけなので、大人の使う単語は正直わからん!となることは多いです。あとはアメリカ英語がわかりません。

Mac かつ VSCode で Idris の環境構築をする

Idris Advent Calendar 2020 3日目の記事です。

2020年今年の言語に Idris を選んで年始に Hello, World していたのですが、見事にその後 Python をしていた1年でした(仕事で使うことになったので Python を覚える必要が出てきました)。

完全に Idris は初心者ですが、Idris 楽しんでいきたいと思います!

今回は Mac ユーザー向けに Idris の開発環境構築を紹介します。

Idris とは

だいぶ雑に説明するなら、依存型つき Haskell です。詳しくは2020年 Idris Advent Calendar 1日目の記事をご覧ください。

環境

VSCode 上でコードが書けると安心できますね、ということで VSCode を使用する前提でいます。Idris は REPL が使えるので、それを利用するだけでも Hello, World くらいなら結構簡単にできますが。

Idris のインストールをする

Idris 自体を入れる

2つルートがあります。今回私は Homebrew を使用しました。一方で、公式には cabal によるインストール方法が記載されています。たぶんどちらでもいいと思います。

まず Homebrew から。

$ brew install idris

これが終わった後に、

$ idris --version

しましょう。私の環境では、

❯ idris --version
1.3.3

と返ってきました。Idris は1系と2系があり、2系は開発中なんだそうです。

cabal を入れる

cabal 自体はこのあと必要になるので、別途インストールしておきましょう。

$ brew install cabal-install

これを行ったあとにパスを通す必要があります。.zshrc などに下記を書き足しましょう。

PATH = "$HOME/.cabal/bin:$PATH"

stack の場合は試したことはないです。

VSCode の Extension を入れる

プラグインのインストール

VSCodeプラグインを入れましょう。Extensions で「Idris」と検索すると出てきます。

github.com

この README にしたがって、idringen というプロジェクトマネジメントツールを入れる必要がありそうです*1。プロジェクトマネジメントツールを入れるのは少々抵抗があるかもしれませんが、初心者の場合そもそも言語的なベストプラクティスも知らないと思うので、入れて勉強しようということで私は入れてみました。

最後のメンテが4年前だけど…

idringen を入れる

github.com

cabal を経由して入れます。

$ cabal install idringen

インストール後、下記を叩きます。

$ idrin --help

help コマンドは実装されていないらしい…。メンテのしがいがありそう。

❯ idrin --help
idrin: not support subcmd --help yet
CallStack (from HasCallStack):
  error, called at src/Idringen.hs:28:24 in drngn-0.1.0.3-b556eddc:Idringen

idringen でプロジェクトを作ってみる

sandbox プロジェクトを作りましょう。ちなみに、名前に「-」を入れると生成後エラーになってビルドできません。ご注意を。

new コマンドでプロジェクトを作成できます。

❯ idrin new sandbox
Creating new project named sandbox

Hello, World

ビルドして…

❯ idrin build

実行しましょう。

❯ idrin run
hello sandbox!

これで完了です!

VSCode で開いてみる

シンタックスハイライトもしっかりついていて完璧ですね!これで開発をスタートしていきましょう!

f:id:yuk1tyd:20201202114631p:plain
VSCode で Idris プロジェクトを開いてみた

(これだけ見ると、めっちゃ Haskell ですね)

Idris の本

『Type-Driven Development with Idris』という本があって、いろいろ詳しく書かれているように思います。

PDF も存在していて、下記です。

www.pdfdrive.com

12月中に時間があったら、この本からいくつかエクササイズして記事にしてみようかなと思っています。

*1:なんとExtensionの作者が作っています

2020年。あなたとJAVA、今すぐダウンロー

ド。(いつものやつ)

2020年時点で改めてよさそうな Java のインストール方法についてまとめておきます。

ちなみにですが、

  • Scala(sbt)を利用する。
  • Scala のプロダクトでは Java 8 を使用し、プライベートでは Java 14 を使用する。
  • Open JDK そのものの縛りは特にない。
  • macOS を使用する。

という前提のもと行う環境構築です。jenv を利用してバージョンの切り替えを行いながら開発することを前提としています。IntelliJ を使用しているとほとんど意識することはないんですが。

インストール方法

brew tap をして、AdoptOpenJDK を入れます。

$ brew tap AdoptOpenJDK/openjdk

JDK 8 なら、下記のように入力すると入れられます。

$ brew cask install adoptopenjdk8

AdoptOpenJDK という選択肢

という観点から、今回は AdoptOpenJDK を使用しています。

jenv で複数バージョンを管理する

Java は最近、バージョンリリースのサイクルが速くなりました。サクッと最新版を試したいけれど、普段のプロダクトでは少し古いバージョンを使用しているということもあるかと思います。

そういったときには jenv というツールが使えます。

github.com

brew install jenv

をして、

jenv versions

で、動いているかを確認します。その後、AdoptOpenJDK で入れたバージョンたちを次のようなコマンドで追加していくと、jenv の管轄下に置くことができます。

mkdir ~/.jenv/versions

ディレクトリがないと、↓でコマンドを叩いた際にディレクトリがないよと怒られます。

echo 'export PATH="$HOME/.jenv/bin:$PATH"' >> ~/.bashrc

などを忘れずに。パスを通さないと、java -version したときに jenv の設定が読まれないみたいです。

$ brew cask install adoptopenjdk11
$ brew cask install adoptopenjdk10
$ brew cask install adoptopenjdk8

インストールした AdoptOpenJDK の分しか入れられないので注意。

これを、jenv に追加します。

$ jenv add /Library/Java/JavaVirtualMachines/adoptopenjdk-11.0.2.jdk/Contents/Home/
$ jenv add /Library/Java/JavaVirtualMachines/adoptopenjdk-10.jdk/Contents/Home/
$ jenv add /Library/Java/JavaVirtualMachines/adoptopenjdk-8.jdk/Contents/Home/

Java 8 なら Java 8 を標準に設定して、

$ jenv global 8.0

これで、

$ java -version

をした際に、8に切り替わっていれば成功。ちなみに特定のディレクトリ配下だけ Java のバージョンを変える設定もできるみたいです。

参考記事: https://www.dhiller.de/2019/01/06/setup-multiple-jdks-with-jenv-and-adoptopenjdk.html