Rustの型システムでSudoku Checkerを作る話🦀
この記事から着想を得ています。
TypeScriptの型システムって（実用的かはおいておいて）そんなに応用的なんだな...と感動を覚えたのです。
そして私が今学習中のRustの型システムでも同様のことができないかと考えました。
TypeScriptの型システムはチューチング完全で、数独も競技プログラミングもできるらしいですが、
5月29日追記: DOOMもできるらしいです。ヤバすぎる。
Rustだって型で四則演算ができますし、チューリング完全です。
Rustは所有権・借用やライフタイムなど、厳格なシステムを持ちますが、ジェネリクスやトレイト境界の概念により型の表現力も兼ね備えています。ということで、RustでもSudoku型を実装してみます。
Rustのジェネリクス・トレイトについて
短く言うと:
- ジェネリクス: 様々な型に対して動作する関数、データ構造などを定義できる。
- 任意の値を格納するベクタ
Vec<V>や、任意の型からの型変換を定義するトレイトFrom<T>
- 任意の値を格納するベクタ
- トレイト: 他言語でのインターフェースで、共通した振る舞いを定義する。
- ある型が特定のトレイトを実装すると、そのトレイトが定義するメソッドを利用できる
-
From<i32>トレイトを実装している型は、::from(i32)メソッドでi32からの型変換を行える
-
- ジェネリクスにおいては、「このトレイトを実装している任意の型」という制約（トレイト境界）の表現ができる
- トレイト境界を指定することで、その型がトレイトが規定するメソッドを使えることが保証される
- ある型が特定のトレイトを実装すると、そのトレイトが定義するメソッドを利用できる
詳しくはRust By Exampleを。
以降の実装においては以下さえ覚えてもらえばOKです
- ジェネリクスは任意の型を表すもの
- ジェネリクスは、型がトレイトを実装しているかという制約ができる
- トレイトは任意の型に実装できる
実装の過程
1. 構造の定義
Sudoku型をおおよそ以下のような特徴を持つものとします。
- Sudokuのルールに合致した入力のみを受ける型
- 要素は1~9の整数と、未入力のいずれか
- 9x9で81の要素を持つ
- 縦・横・3x3のブロックについて要素の被りが無い
- これに違反したとき、コンパイル時で型エラーが出る
1.2.について、Sudoku型は以下のような構造としました。
型パラメータを1つ1つのセルに付与してあげることで、各セルについて型として処理できるようにしています。
各数字について、enum/列挙型ではなくstruct/構造体として1つ1つ定義しているのもそのため。enum Cell { One, Two, ...}みたいな表現だと「Cellです」以上には型システムで制約できなくなってしまうので。
その代わりに各構造体にIsCellトレイトを実装し、全パラメータにトレイト境界としてIsCellを制約することでこれらの構造体のみを入力できるようにしている。
2. 「重複がないこと」をどう判定するか
直感的にわかると思いますが、3.が一番難しい。要するに、「重複がない」ことを判定しないといけないのですが、型でどうやればいいのか...；；
普通ならforネストしてやりたいところですが、ここで元のtypescript-sudokuのソースコードを読んでみましょう。
Different型は異なる値が入力された時にTrueを返す型で、AllDifferent型は9つの入力の組み合わせ全てについてDifferentをかけている...
あれ、これもしかしてゴリ押しが正解？
AllDifferentを全部の列・行・ブロックの組み合わせにかけている。ゴリ押し。
これならStableなRustでもできますよ！
まずはIsDiffTypeトレイトを...
tsに比べてスマートじゃなさすぎるのは御愛嬌。RustにはExtendsなんて便利なものはありません。
いえ、「型が同じ」ときに実装されるトレイトは以下のコードで簡単に書けるのですが、その裏返しの「型が違う」ときに実装されるトレイトは作れないんです...
trait Eq<T, U> {} // T, U 2つの型パラメータを持つ
impl<T> Eq<T, T> for () {} // Eqに共通の型パラメータTを代入する
// -> 共通の型を代入できるときのみEqトレイトは実装される
とはいえ、これで型が違うときを検出できるようになったので、あとはゴリゴリ書いていくだけですね！
AllDiffTypeParamsトレイトは9つの型パラメータをもち、9つの組み合わせ全部についてIsDiffTypeトレイトの制約をしています。
そしてSudoku型では、行・列・ブロックのそれぞれ9つずつの重複があるべきでない部分を、AllDiffTypeParamsトレイトにかけています。
これでSudoku型の実装完了です！🦀
3. 実行してみる
さて、型チェックが効くか確かめてみましょう。ルールに反する値を入力しています。
fn main() {
// ぜひどこがミスってるか探してみてください。
let sudoku = Sudoku (
__, __, __, __, __, _9, __, _2, __,
_2, __, __, __, __, __, _4, __, __,
__, _8, __, __, __, _2, __, __, _5,
__, __, __, __, _2, __, __, __, _2,
__, __, _6, _4, __, _3, __, _5, __,
__, __, __, _1, __, _8, __, __, _9,
__, __, __, _2, __, __, __, _8, __,
__, _1, __, __, _8, __, _3, __, __,
__, __, __, __, __, _4, __, _9, __,
);
}
そしてコンパイラが吐いたエラーがこちら。
error[E0277]: the trait bound `(): IsDiffType<_2, _2>` is not satisfied
--> src/sudoku_stable.rs:210:18
|
210 | let sudoku = Sudoku (
| __________________^
211 | | __, __, __, __, __, _9, __, _2, __,
212 | | _2, __, __, __, __, __, _4, __, __,
213 | | __, _8, __, __, __, _2, __, __, _5,
... |
221 | | __, __, __, __, __, _4, __, _9, __,
222 | | );
| |_____^ the trait `IsDiffType<_2, _2>` is not implemented for `()
// トレイト `IsDiffType<_2, _2>`は () に実装されていません
|
= help: the following other types implement trait `IsDiffType<T, U>`:
`()` implements `IsDiffType<_1, _2>`
`()` implements `IsDiffType<_1, _3>`
`()` implements `IsDiffType<_1, _4>`
`()` implements `IsDiffType<_1, _5>`
`()` implements `IsDiffType<_1, _6>`
`()` implements `IsDiffType<_1, _7>`
`()` implements `IsDiffType<_1, _8>`
`()` implements `IsDiffType<_1, _9>`
and 83 others
note: required for `()` to implement `AreDiffTypeParams<__, __, __, __, _2, __, __, __, _2>`
// note: () に `AreDiffTypeParams<__, __, __, __, _2, __, __, __, _2> の実装が必要です
--> src/sudoku_stable.rs:129:42
|
129 | impl<T1, T2, T3, T4, T5, T6, T7, T8, T9> AreDiffTypeParams<T1, T2, T3, T4, T5, T6, T7, T8, T9> for ()
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^
...
135 | (): IsDiffType<T5, T6> + IsDiffType<T5, T7> + IsDiffType<T5, T8> + IsDiffType<T5, T9>,
| ------------------ unsatisfied trait bound introduced here
note: required by a bound in `Sudoku`
--> src/sudoku_stable.rs:179:7
|
142 | pub struct Sudoku<
| ------ required by a bound in this struct
...
179 | + AreDiffTypeParams<X41, X42, X43, X44, X45, X46, X47, X48, X49>
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `Sudoku`
Rustコンパイラ、エラーがやたら詳しいことでおなじみですが、めちゃくちゃちゃんとエラー吐いてくれていますね。
一番下のAreDiffTypeParams<X41, X42, X43, X44, X45, X46, X47, X48, X49>は、行4の重複チェックなので、ここが上手くいかなかったという情報、そして_2が被ったという情報が簡単に読み取れます。
もっと読み解けば、IsDiffType<T5, T9>がトレイト境界を満たさなかったというところまで書かれています。T5は5つめの型パラメータ、T9は9つめの型パラメータを指しているので、
先のAreDiffTypeParams<X41, X42, X43, X44, X45, X46, X47, X48, X49>という情報と合わせると、X45（行4列5）、X49（行4列9）が重複したというところまでわかります。
全然ちゃんと数独のヒントになりそうです。
もう少しスマートにやりたい
他はtypescript-sudokuでも同じ実装なので仕方がないとしても、
IsDiffTypeトレイトの実装、もう少しスマートにしたいですね。
そこでNightlyのRustコンパイラの限定で使える機能、Unstable Featuresを使ってみましょう🦀
rustup override set nightly
を実行することで、実行されたディレクトリではnightlyチャンネルが利用されます。
1. generic_const_exprsを使う
generic_const_exprsについて
Rust 1.51で導入されたconst genericsにより、ジェネリクスに値を渡すことができるようになりました！
例として、ビットの配列を実装することを考えてみましょう。
#[derive(Debug, Copy, Clone, Eq, PartialEq)]
enum Bit {
One, Zero
}
#[derive(Debug, Copy, Clone, Eq, PartialEq)]
pub struct BitArray<const N: usize>(pub [Bit; N]);
pub type Bits16 = BitArray<16>;
pub type Bits32 = BitArray<32>;
pub type Bits64 = BitArray<64>;
impl<const N: usize> Not for BitArray<N> {
type Output = Self;
fn not(self) -> Self {
BitArray (self.0.map(|bit| !bit))
}
}
BitArray構造体を定義し、16/32/64BitはBitArrayへのエイリアスとして実装しています。これにより各ビット長ごとにいちいち再実装...ということをせずに済みます。
かつ、各エイリアスがリンクされているBitArray<16>, BitArray<32>, BitArray<64>はそれぞれ別の型として扱われますから、違うビット長のインスタンスが紛れるということもないわけです。
Option<bool>とOption<i32>が別なのと同じですね。
これを使ってやると、パラメータによって全く違う構造体を返す構造体を実装することができます。
pub struct TypeHelper<const N: usize>;
trait TypeHolder<const N: usize> { type Output; }
impl TypeHolder<1> for TypeHelper { type Output = u32 };
impl TypeHolder<2> for TypeHelper { type Output = Box<bool> };
type TypeChanger<const N: usize> = <TypeHelper<N> as TypeHolder<N>>::Output;;
TypeChanger型は、TypeChanger<1>のときu32を返し、TypeChanger<2>のときはBox<bool>を返します。
この例だと「普通に型パラメータ渡せよ」にはなるかもしれません。が、座標のような構造体は、二次元の座標・三次元の座標はフィールドが異なるので、
Coordinate::<2>{ x = 1, y = 2 }, あるいはCoordinate::<3>{ x = 3, y = 2, z = 10 }のように直感的に書けるのは価値があるかもしれません。
そして、Unstable Featureの一つであるgeneric_const_exprsを有効化することで、このConst genericsを関数に渡したり計算を行うことができます。
例として、「奇数のときのみ実装されるトレイト」を作ることができます。
struct Assert<const COND: bool>;
trait IsTrue {}
impl IsTrue for Assert<true> {}
struct Num<const N: usize>;
// const fnはコンパイル時に評価される関数のキーワード。
// 諸々の制限があるが、昔よりはかなり制約は少なくなったらしい。
const fn is_odd(num: usize) -> bool {
N % 2 == 1
}
trait IsOdd {}
impl<const N: usize> IsOdd for Num<N>
where Assert<{ is_odd(N) }>: IsTrue { // <{ N % 2 == 1 }>と書いてもいい
// Assert<true>はトレイトIsTrueを実装するので、
// is_odd(N) がtrue、すなわちNが奇数のときのみにトレイト境界を満たし、
// トレイトIsOddが実装される
fn foo() { }
}
Num<3>::foo();
// Num<4>::foo(); -> コンパイルエラー
これは面白いことができそうですね...！
generic_const_exprsを使った実装
ということで、const genericsとgeneric_const_exprsを利用し、プリミティブな整数型を利用したSudoku型も実装してみました。
ここでAssert型を定義しています。
CellTypeはSudoku型の要素の方を指定しています。Enumが良かったらEnumにしましょう。
あんなに長かったsudoku型の定義が二行で済んでいるの、感動モノですね？？？？？
9*9の２次元配列をconst genericsでパラメータに取り、それをそのままsudoku_is_valid関数に渡しています。
sudoku_is_validがtrueを返すと、Assert<true>: IsTrueよりトレイト境界を満たして型チェックをパスし、falseだとその逆です。
2つのconst fnを実装しています。結局ここで総当たりで、本質はあまり先程のstableバージョンと変わりませんが、こちらではrustのプリミティブな整数型と!=演算子を用いれているというのがポイント高いです。
fn main() {
let sudoku = Sudoku::<{[
[5, 3, 4, 6, 7, 8, 9, 1, 2],
[6, 7, 2, 1, 9, 5, 3, 4, 8],
[1, 9, 8, 3, 4, 2, 5, 6, 7],
[8, 5, 9, 7, 6, 1, 4, 2, 3],
[4, 2, 6, 8, 5, 3, 7, 9, 1],
[7, 1, 3, 9, 2, 4, 8, 5, 6],
[9, 6, 1, 5, 3, 7, 2, 8, 4],
[2, 8, 7, 4, 1, 9, 6, 3, 5],
[3, 4, 5, 2, 8, 6, 1, 7, 9],
]}>;
}
このSudoku型はコンパイルを通ります。やったね。
2. specializationを使う
さてさて、お気持ちはわかります。全通りのimpl文を書くのも、関数に甘えるのは美しくありません。
「重複がないことをどう判定するか」節にて、以下のことを述べました。Rustは同じ型を検知することは簡単にできます。
trait Eq<T, U> {} // T, U 2つの型パラメータを持つ
impl<T> Eq<T, T> for () {} // Eqに共通の型パラメータTを代入する
// -> 共通の型を代入できるときのみEqトレイトは実装される
これをなんとか使えないでしょうか。直接的にはnegative_boundsfeatureというのがあるのですが、コンパイラ内でのテストを書くためだけにfeatureとして登録されており、実態としては実装されていません。
trait Eq<T, U> {}
impl<T> Eq<T, T> for () {}
trait AreDiffTypeParams<T1, T2, T3, T4, T5, T6, T7, T8, T9> {}
impl<T1, T2, T3, T4, T5, T6, T7, T8, T9> AreDiffTypeParams<T1, T2, T3, T4, T5, T6, T7, T8, T9> for ()
where
(): !Eq<T1, T2> + !Eq<T2, T3> + ... // はるか未来にはできるかも
{}
negative_implsfeatureは「トレイトが実装されない場合を明示的に定義できる」というもので、あまり関係がありません。
impl<T, U> !Eq<T, U> where /* Eqトレイトが実装されない（同じじゃない場合）を自分で定義する */ for () {}
ここで、specializationfeatureを利用します。
Rustでは、ある1つの型について、あるトレイトを2種類実装することはできません（一貫性の保持のため）。specializationを有効化すると、コンパイラがトレイトの実装において、より一般的な実装をより特定の条件に特化した実装で上書きします。
これを利用し、違う型を検知することができました。
trait EqHelper<T, U> {
const ARE_EQUAL: bool;
}
impl<T, U> EqHelper<T, U> for () { // あらゆる型の入力に合致するデフォルト実装
default const ARE_EQUAL: bool = false;
}
impl<T> EqHelper<T, T> for () { // 型パラメータが同じ時のみの特別な実装
const ARE_EQUAL: bool = true;
}
EqHelperトレイトは、関連constARE_EQUALを持ち、デフォルト実装ではfalseになっていますが、
２つの型パラメータが一致するときにのみ実装される後者ではtrueになります。
trait NotEq<T, U> {}
impl<T, U> NotEq<T, U> for ()
where
Assert<{ <() as EqHelper<T, U>>::ARE_EQUAL }>: IsFalse,
{}
これを利用し、２つの型パラメータをEqHelperにぶち込んでARE_EQUALを返してもらい、それをAssertに突っ込んでいます。
結果的に、NotEqトレイトは２つの型パラメータが異なるときにのみ実装されます。
後はこれまでと同じように総当たりでOK。
まとめ
そういう言語じゃねぇからこれ🦀。
TypeScript、すごい。
でも、ゼロコスト抽象化と型安全性重視の設計を維持しながらここまでの表現力を両立しているのがRustという言語です。
みんなもRust、始めよう。多くの人にはRustの安全性や速度が本当に必要、ということはあまりないかもしれませんが、それでも本当に書いてて楽しい言語です。
1番愛されるプログラミング言語は伊達じゃない。
正直まだThe Book, rustlingsなどその他公式教材を履修したくらいで、非同期周り全くわかってないです。やってること間違ってるだろ。勉強頑張ります。
Discussion