迷路探索ライブラリをRust移植するために調べたことのメモ

迷路探索ライブラリをRust移植するために調べたことのメモ

Rust
libamaze

この記事の目的

個人的な備忘録です． 読んでも有用な情報はあまりないと思います．

えーと，前回の記事 を書いたおかげでブログ更新のハードルが下がりました． アホみたいな記事を書くのもいいもんですね．

どうやらRustがアツいらしい

どうやらRustがアツいらしいということはずいぶん前から見たり聞いたりしていたのですが，当時は仕様が安定していなかったり未実装の機能が多かったりと，開発しづらいイメージが先行してしまい，結局2020年に入るまでいじらずじまいでいました． ところが最近になってROS互換のフレームワークをRust実装しているらしいロボットベンチャーが現れたり，STM32をはじめとする ARM Cortex-M 系マイコン向けのサポートの整備が急速に進んだりしており，「乗るしかない！このビッグウェーブに！」と思い現在に至るわけです．

どうアツいのか

散々ほかのサイトでも解説されていると思いますが，私の知る限りのRustのアツい点を羅列すると，

  • C, C++と同様にバイナリにコンパイルする言語であること (マイコン使いには重要)
  • 標準装備のビルドシステム(cargo)やテストフレームワークが強力であること
  • オブジェクトの所有権が明確であること (moveした変数にアクセスしようとするとコンパイル時に怒られる)
  • 所有権の制約を利用してスレッド安全性をコンパイル時に担保できること (マイコンでは使わないけどすごい)
  • C++20のConceptsに相当する，Boundsが実装されていること

などなど，高度(?)なアルゴリズムをマイコンに載せたい私としては，嬉しいことが満載なのです．

移植にあたって

拙作の迷路探索ライブラリの移植を目論んでいます．

libamaze

このライブラリは，迷路やグラフの情報の格納に必要な領域をコンパイル時に計算して静的にメモリ確保することや，グラフ表現やソルバ(A*アルゴリズム，幅優先探索など)の付け替えが可能であることが特徴です． 途中まで順調に開発が進んでいたのですが，設計に致命的なミスがあったため結局完成しないまま放置されています(ひどい)．

そういえばこのライブラリについての記事も書いてない(ひどい)．

まずはRustの基礎の習得

まずはRustを勉強します．

The Rust Programming Language を読んで，環境の構築(1章)と基本的な文法の習得(2,3章)を行いました． こいつはとにかく書き方が冗長丁寧なので，暇なときに読む分には良いと思います． はじめはなかなか先に進まず，英語を読むスピードが遅いからかなと思っていましたが，どうやらそうではなさそうだと気づいた私は3章で脱落しました． 戦略的撤退です．

代わりに rustlings という入門例題集を一気にやりました． これを終えた頃には，なんとか調べながらRustを書けそうな気がしてきました．

効率厨の私としては，bookはさらっと眺めてからrustlingsを進めつつ読んで，最後にまたbookに戻って補強すると良いのかなと思いました． でも最初からbookを読んだほうが楽という方もいるかもしれません(私は読んだだけでは頭に入らないもので…)．

上級者には Rust Quiz なるマニアックな問題集もあるらしいので，モリモリ書けるようになったらやりたいです．

ではRustでどう実現するか

Rustの基礎が身についたところで，libamazeの2つの特徴に絞って，Rustでどう実現するか考えていきます．

グラフ表現やソルバの付け替え

Rustには継承の概念がありません． その代わりに，グラフやソルバのtraitsを定義して，boundsとして使ってやればよいはずです．
(用語の使い方が怪しい… 今のところそのように理解していますが，あってるよね…？)

静的アロケーション

こちらの要件が少し厄介かもしれません． 組み込み向けのRustについては， The Embedded Rust Book に詳しくまとまっています(まだ全部読めていない…)． これによると，ビルトインの固定長配列を利用するのはもちろんですが，VecやHashMapを利用したい場合は heaplessを利用するのが一般的な解決方法のように見えます．

しかし，ここで別の問題があります． stable版のRustではC++でいうテンプレート引数に定数を渡すことができないのです．

対応するものは，現状unstableなconstant genericsという機能ですが，執筆時点ではconstant genericsは指定された定数を演算して利用できないという機能の制約があります． libamazeでは，迷路のサイズから自動的にグラフのノード数を計算したり，サイズの整合性をチェックしたりする機能を実装しており，これをRustで再現するのは難しそうです．

以上を受けて移植の方針

  • マイコンでの動作を確実にするため，no_std を前提としてコードを書く
  • 迷路サイズはハードコーディングした定数とし，グラフのサイズもそこから計算する (迷路サイズはライブラリ使用側から変更できない，もしくはコンパイル時にコマンドラインやファイルで指定する)
  • (前回の反省: 結合して動作するコードよりも先に単体テストをしっかり書く)

Constant genericsで実現しようとした迷路・グラフのサイズのコンパイル時計算ですが，typenum crate を使ったり，マクロを組んだりすれば実現できるようです． しかし，いずれもハック的な解決方法でしっくり来なかったため，この機能については諦めることにし，迷路サイズは定数(幅・高さ32マス)とすることにしました． 振り返ってみれば，C++版libamazeもこの W というパラメータのせいで無駄に複雑になっていた節があるので，切り捨てて正解のような気がします．

また，libamazeでは迷路データの壁有無フラグの格納にビットフィールドを利用していましたが，これは modular-bitfield を使えば実現できそうです．

頑張るぞい

(๑•̀ㅂ•́)و✧

C++17漬けになってしまった私ですが，これでようやくモダンな言語に入門できそうです． 進捗状況はなるべく記事にしていきたいと思うので，サボってたらつついてください．

リポジトリの予定地: tokoro10g/amaze

Share Comments