SECDV Schemeの実装 - その他基本ライブラリ

というわけでSchemeの基本要素だけで実装できるものは一通り実装を終えてテストも書いた。
... 本当に書くことが無いな。。ライブラリを他所からパチって来ずに自前で実装しているのは、ゲームに組込むのにパブリックドメインなランタイムが欲しいため。expanderはゲームの実行時は不要なのでAlexpanderを使い続けているけど、ランタイム側は組込まれてしまうのでライセンスの制約を受ける。

mapforeach

mapやfor-eachは当然Scheme上で実装できる。一応、R7RSのstring-mapやvector-mapも普通に実装している。テストは座標とデータのリストを渡して文字列を構築するやつを良く使っているので今回もそれで。
入力は4要素までのサポートにした。https://github.com/okuoku/yuni/blob/d759e40bd57dd2eabdc19271b8735837e5b0c088/lib-r7c/r7c-basic/lib/mapforeach.sls#L400 もっと多くの要素をサポートするのはapplyがちゃんと動くようになってから。
基本的にmapや→list系のリスト構築手続きはset-cdr!を使ってlinear updateにしている。普段は逆方向に構築してreverseして返すコーディングをしているけど、mapやstring→list類は多用されるのでまぁ多少はね。。

strings

stringsライブラリはScheme上で実装するのには向いてない気がする。今回の実装はO(1)文字列アクセスを強く期待しており、基本的には文字列は 長さを決定してmake-stringで確保 → string-set! で文字を一つ一つセット という方式で実装している。
今回で言うと、BASICやGame Makerのようなベースになるランタイムが存在する環境では、その環境の文字列がO(1)アクセス可能という保証は無いので、あまりパフォーマンスが出ない危険がある。また、Scheme処理系でも rope 構造を文字列に採用していたり(Picrin等)、UTF-8な内部表現を直接利用する処理系(Chibi-scheme等)もあるため打率は悪い。ちなみにR6RSはO(1)文字列アクセスを要求しているが、R7RSは特に要求していない。

‌ Implementors should make string-ref run in constant time.

chibi-schemeは文字列を実際の文字列と文字列カーソルに分けている。UTF-8のような構造を採用すると、string-refの実装のためには文字の位置と実際のバイト位置の対応を適切に管理する必要があるが、適当な時間文字列カーソルをキャッシュするのは悪くないアイデアかもしれない。
vectorやbytevectorと異なり、文字列は比較演算を実装する必要がある。...これをどうやってエレガントに実装するかというのは悩みどころだが、考えてる時間は無いので

  1. "あいこ" だったら次の文字を比較する https://github.com/okuoku/yuni/blob/d759e40bd57dd2eabdc19271b8735837e5b0c088/lib-r7c/r7c-basic/lib/strings.sls#L44
  2. そうでないケースは比較して試合終了 https://github.com/okuoku/yuni/blob/d759e40bd57dd2eabdc19271b8735837e5b0c088/lib-r7c/r7c-basic/lib/strings.sls#L46
  3. 最終文字であいこを勝たせるかどうかはフラグで渡す https://github.com/okuoku/yuni/blob/d759e40bd57dd2eabdc19271b8735837e5b0c088/lib-r7c/r7c-basic/lib/strings.sls#L32
  4. ゼロ文字ケースは特別扱いする
  5. フラグ引数の数をケチするために、等長文字列の比較と長さが違う文字列の比較は分ける

で実装してみた。実は最初"あいこ"ケース以外では次に行く必要が無いことを見落していて、えらい複雑な条件を書いていた。
まぁ速度的に不満が出てきたらちゃんと実装するということで。。今は正確に動くことの方がずっと重要。

vectors

特記事項なし!
実は、string→vector系をstringsライブラリに入れるかどうかはちょっと悩んだ。たぶんvectorsライブラリにstring→vector類を入れたのは間違いで、vectorはpair等同様Scheme固有のデータ型で、どちらかというとベースランタイムの性質が出やすいstringsに実装を集中させた方が再利用性の面では有利なのではないか。
vectorsに限らず、indexの算術演算には専用のfixnumライブラリを使用している($fx=とか$fx+など)。R7RSでは、これらのインデックスを表わす数値は必ず正確数を使うことを求めているのと、完全なnumeric towerをScheme側を使って実装する必要が有る場合に依存関係の循環が出ないようにするため。

bytevectors

ほぼvectorsのコピペ!
最大の問題はutf8→stringとstring→utf8で、これだけのために乗除算(またはビット演算)が必要というアンバランスぶり。というわけで未実装(ASCIIだけ)。
R7RS smallでは、R6RSに見られたようなu8-list→bytevectorに相当するようなコンストラクタは無い。実際にはbytevector手続きへのapplyという形で同じ処理が可能だが。。

次の一手

冒頭のように、ヒープの操作機能だけで記述できるものはこれで終りで、ここからはScheme処理系として固有の機能を活用しながらでないと実装できない部分になる。つまり、

  • numeric tower。今回は複素数有理数のサポートはせずに、flonum(不正確数)、fixnumの2つだけ。bignumは後で考える。
  • port。今回はsimple-structを使って"vectorと区別できるvector"を用意できるので、それを使って簡易なオブジェクトシステムを作って対応する。
  • equal?。サボるR6RS/R7RSのequal?には停止性要求があるため、単純に再帰的なeqv?を実装するだけではNGとなる。が、個人的には困らないので後回し。
  • reader / writer。気合でどうにかする。今のところyuniに無いのはwriter全部とnumber reader。

以前挙げたように( http://d.hatena.ne.jp/mjt/20170530/p1 )、portをvectorで表現することはSchemeの仕様上許されていないので、独自のオブジェクトシステムを構築する方法がどうしてもどこかのタイミングで必要になる。

equal?はサボる決断さえすれば実装を始められる。なのでequalは適当にやっつけて終わりとして、残りの要素にどこから手を付けていくべきか。。とりあえずnumeric towerかな。。?numeric towerにせよportにせよ、今回のScheme on Scheme環境で実験をするために、ホストSchemeの機能を呼ぶための良い方法を考えておく必要がある。
portを後回しにするのは、抽象化レイヤを考える必要があるため。numeric towerでも実際には抽象化レイヤは必要だけど、今回は"inexactでなければfixnum"という単純なものなのでScheme標準の語彙(inexact?とかexactといった表現型を扱う手続き群)が抽象化レイヤとして機能できる。