Compile Time Mathematics in Rust

技育展 ぼくのさいきょうの○○ テーマで発表させていただいたときの発表資料です

Transcript

1. © 2020 @White_Green2525 #技育展 #RoomB Compile Time Mathematics in Rust 型レベルの静的計算と処理効率化
2. Compile Time Mathematics in Rust © 2020 @White_Green2525 #技育展 #RoomB ⾃⼰紹介 • 九州⼯業⼤学 情報⼯学部 B2 • C#とRustが好き • この前誕⽣⽇でした 2
3. Compile Time Mathematics in Rust © 2020 @White_Green2525 #技育展 #RoomB Rustとは？ • C++からの置き換えを⽬指している⾔語 • ⾼速 • インタプリタを挟まずネイティブに動く • C++と同等または若⼲遅い程度の速度で動作 • 安全 • ライフタイム,所有権等 • メモリリーク,並列処理時の競合が起こらない仕組み • C++なんか⽐較にならない程安全 3
4. Compile Time Mathematics in Rust © 2020 @White_Green2525 #技育展 #RoomB Rustでできること • 組み込みシステム • Arduino等 • OS • ネイティブアプリ • WinRTはRust対応 その他にもたくさん • Webフロントエンド • WebAssemblyにコンパイルできる 対応FWもある 4
5. Compile Time Mathematics in Rust © 2020 @White_Green2525 #技育展 #RoomB 関連型 関連定数 5 • trait(interfaceが近い)の実装時 に、実装毎に型を指定できる (関連型) • 同様に定数も(関連定数)
6. Compile Time Mathematics in Rust © 2020 @White_Green2525 #技育展 #RoomB ⾯⽩いことできそうですね？ 6
7. Compile Time Mathematics in Rust © 2020 @White_Green2525 #技育展 #RoomB 型レベルで整数加算 • A=0000,0000,0000,0000,0000,0000,0000,0010=2 • B=0000,0000,0000,0000,0000,0000,0000,0100=4 • C=A+B=6 7
8. Compile Time Mathematics in Rust © 2020 @White_Green2525 #技育展 #RoomB 型計算の表現⼒ • チューリング完全 • 証明) ラムダ計算が実装できた □ 8
9. Compile Time Mathematics in Rust © 2020 @White_Green2525 #技育展 #RoomB 応⽤:⾏列サイズをコンパイル時に決定 普通 • 可変⻑配列+⾏列サイズ 静的サイズ • 可変⻑配列のみ • 16バイト節約 9
10. Compile Time Mathematics in Rust © 2020 @White_Green2525 #技育展 #RoomB 主産物:型レベルで計算する利点 • ⾏列計算はサイズにより定義される場合とされない場合がある • 通常:定義されない場合panicする/無効な値を返す • 最善でも単体テストで発⾒/最悪の場合潜在的な不具合として残る • 静的:定義されない場合コンパイルエラー • 不具合発⾒にかかるコストが実質0 10
11. Compile Time Mathematics in Rust © 2020 @White_Green2525 #技育展 #RoomB 副産物:計算処理の⾼速化 • 同サイズの正⽅⾏列同⼠の和/積演算が⾼速化 11
12. Compile Time Mathematics in Rust © 2020 @White_Green2525 #技育展 #RoomB なんで⾼速になるのか • コンパイル時の最適化に起因(詳しい⼈教えて) 12 動的サイズ 静的サイズ
13. Compile Time Mathematics in Rust © 2020 @White_Green2525 #技育展 #RoomB 参考資料/リンク • コンピュータの構成と設計 第5版 • ISBN:978‐4822298425, 978‐4822298432(上下巻) • ディジタル回路設計とコンピュータアーキテクチャ 第2版 • ISBN:978‐4798147529 • 型システム⼊⾨ • ISBN:978‐4274069116 • 低レベルプログラミング • ISBN:978‐4798155036 13 ぼくのさいきょうの⾏列ライブラリ https://github.com/White-Green/ct-math
14. Compile Time Mathematics in Rust © 2020 @White_Green2525 #技育展 #RoomB 余談①:数値の表現⽅法 • Q. 型で整数を表現するときに⼆進数でやってるけど、理由は? • A. ペアノの公理から定義する形式を最初に試したけど、それだ と型名がO(N)の⻑さに、⾜し算にO(N)、掛け算にO(N^2)の時 間がかかるのでコンパイルが⻑くなる。⼆進数使うと型名の⻑ さがO(logN)になってうれしい 14
15. Compile Time Mathematics in Rust © 2020 @White_Green2525 #技育展 #RoomB 余談②:⾜し算の実装 • Q. 型計算だけで⼆進数の⾜し算実装どうやるの? • A. 型計算処理でprefix加算器を書く謎なことをしていました 15