多値を考える

ずっと放置していた問題の一つ。

最近2chのLisp Schemeスレッドで多値が話題に上がっていて、せっかくだし便乗して考えることにした。(意味不明)

Sagittariusでは多値は第1級オブジェクトになっていて、valuesを呼ぶたびにメモリのアロケーションが走る。これは実は実装の手抜きで、

(apply values (iota 10000 1))

のようなコードをとりあえず走らせるための妥協の産物となっている。ちなみに、Gauche 0.9.3とMosh0.2.7ではこのコードはエラーになる。多分Gaucheは0.9.4辺りできっと直されるだろう(希望的観測)

valuesに期待したいことの一つとして、「これ使っておけば処理系はconsicingしない」というのがある(と思う)。そういう意味ではSagittariusはプログラマの期待を裏切っているわけだ。

自分自身、せっかくvalues使うんだしという感もあるので、現状の上限なしを維持しつつある程度は期待を裏切らない実装にしたい。案としては以下のようになるだろう。

• ある程度割り付けておいて、あふれた分は都度割付
• 必要になったら割付してそのバッファを再利用。足りなかったら再度割り付け(Racket方式)

一つ目と二つ目のどこに違いがあるのか？というレベルだが、実装レベルでは多少違うはず。一つ目は上限超えた際に常にメモリ割付が発生するが、そもそもvaluesに(こちらが考えた)上限を超える値は渡されないだろうという楽観的な実装になる。二つ目はユーザは常にこちらの想像を超えるものだが、それを見越してある程度の性能を出しておきたいという悲観的実装になる。
正直、一長一短ではあると思うが、二つ目の実装で困りそうなのが、上記の例みたいなことをされた際に10000個のバッファを常に保持する羽目になることだろう。多分、どこかの段階でGCされるような仕組みにしておかないと、不必要なバッファがメモリを食いつぶすなんて事になる。

さて、どうしたものかな。

括弧ゴルフ再び

リードマクロを実装したときに書いたネタ再び。(書いたよね？)
ちなみに、元ネタはこちら

本当にLispはカッコが多い？ - 八発白中 

今回はSRFI-49という最強の武器(w を持ったのでこんな風に書ける(0.3.7)

#!reader=srfi/:49
import
  srfi :1

define
  fact x
  if
    = x 0
    1
    * x
      fact
        - x 1

define
  printer i
  print i " ! = "
    fact i

define
  main args
  for-each
    printer
    iota
      if
        null? args
        1
        string->number
          cadr args
      1

Readerの切り替えに#!を使うので括弧0を実現可能！！！wwww
SRFI-49をサポートしている処理系(今のところSagittariusだけっぽい) ならSchemeで括弧ゴルフに勝利することができる。
なんだか、行き着くところまで来てしまったか感がする。

ユーザー定義のReader

こんな意見をいただいた。

@tk_riple R6RSでは#!で始まる識別子をフラグにできると書かれています。 r6rs.org/final/html/r6r… 汎用的にするなら例えば #!reader=srfi-49 みたいな書き方で任意のリーダを設定できるとかどうでしょう。 ファイル内での混在もできるかも。
— (32) 齊藤敦志さん (@SaitoAtsushi) 9月 21, 2012

これはいい！ということで、こっちにしてみた。

多少そのままではまずいので、定義を以下のように変更。

#!reader=srfi/:49

これで、今回ならSRFI-49を読み込むようになる。見ればすぐ分かると思うけど、(srfi :49)がsrfi/:49と変更されている。多少以上に醜いのはこの際目をつぶらないといけない。「.」とかだとライブラリ名が含んでいる可能性があるので「絶対含めることが出来ない文字」にする必要があったのだ。これならファイルシステムがエラー出すので、「実用上ありえない」が少なくとも保障される(少なくともWindowsとUNIX系OSなら)。

それに伴って一つ前の使用例を修正。この形式ならリーダマクロもいけるよなぁ、ポータビリティのために追加しようかな。

SRFI-49をまじめに検討してみる

きっかけはこの一言

@tk_riple srfi-49を標準サポートしてる処理系を自分は知らないんですが、遂に標準搭載の処理系が現われるのでしょうかｗ
— ⠗⠐⠥ ⠵⠱⠊⠷さん (@g000001) 9月 20, 2012

ないのか？ならば最初の処理系になってみようではないか！おぉぉ、燃え上がれ俺の小宇宙！

と、ここまで意気込むのはいいんだけど、このSRFI先頭にマークがあるわけではないし、105のように{}で囲まれているわけでもないのでreader(日本語で書くとleaderと混同しそう)そのものを置き換える必要がある。
確かに、参照実装のGuileではオリジナルのreadをこれように上書きしていたが、Sagittariusではファイルから起動する際はCで書かれたread相当の関数を直接読んでいるので上書きしても嬉しい結果にはならない。むしろ悲しくなる。
また、この面白SRFIを適用したした結果他のファイルに影響があっても嫌だ。となると、リードマクロと同様、適用したファイルのみに働くことが絶対条件かつなんらか既存のreaderを置き換える仕組みが必要になる。

実は腹案が既にあって(朝起きてシャワー浴びてたら思いついた)、ライブラリ自体に一つだけreaderを持たせることを許せば、持っていない場合はデフォルトで持ってる場合はユーザ定義という形で振り分けができそう。多少のオーバヘッドがかかるが、これを入れれば単に面白SRFIのサポートのみではなく、Cで書いたと思ったのにSchemeで実行されているでござる！ということが可能になるかもしれない。(結局ネタだな)
暇なので(これがいけない、ネタがあると飛びついてしまう)、この方針でとりあえず実装してみることにする。

Sagittarius 0.3.6 リリース

今回のリリースはメンテナンスリリースです。
ダウンロード: Sagittarius Scheme

修正された不具合

• SOBER-128がpseudo-random手続きで初期化不可能だった不具合が修正されました。
• read-delimited-listがcustom textual portに対してCレベルのアサーションで落ちる不具合が修正されました。
• リードテーブルが#!r7rs及び#!compatibleでリセットされない不具合が修正されました。
• import句のprefix が正しく動作しない不具合が修正されました。
• (syntax bar)が正しいライブラリを参照していない不具合が修正されました。

新しく追加された機能

• mod-expt及びmod-inverseがCでより高速に書き直されました。
• syntax-case及びsyntax-rules(R6RS版)がシンボルのリネームを行うようになりました。
• path-for-each、path-map、delete-directory*及びcreate-directory*が(util file)ライブラリに追加されました。
• copy-file手続きが追加されました。この手続きはOSの機能を使ってファイルをコピーするので、高速に動作することが期待できます。
• list->stringがオプショナル引数startとendを取るようになりました。
• read-random-bytes!手続きが(math random)に追加されました。

新たに追加されたライブラリ

• SRFI-86、SRFI-31、SRFI-29及びSRFI-43がサポートされました。

改善された機能

• split-at手続きが末尾再帰になるように書き直されました。
• condがSRFI-61スタイルをサポートするようになりました。

互換性のない変更

• カスタムハッシュのread-randomスロットの名前及びセットされるべき手続きが取る引数が変更になりました。詳しくはドキュメントを参照してください。

マクロ戦争ひとまず終結

マクロの不具合に出会うたびに戦争だといっているだけ。それくらいR6RSのマクロ周りは複雑怪奇だと僕は思っている。

一つ前と二つ前の記事でマクロ周りの不具合が(まだまだたくさん)残っていることを書いたが、黒魔術的な処方を用いて直すことに成功したのでちょっと備忘録。

何が問題だったか？
2つの問題があって、1つはマクロを生成するマクロが生成した識別子の問題。もう一つはリネームの問題。

識別子の問題
問題点は2つ前の記事に書いたので、どう解決したかだけ。問題になるのはsyntax-caseのテンプレート部分のみだったので、どこにも束縛されていない識別子のライブラリを展開されているライブラリに置き換えるようにした。記事のコードで言えばdummyがあたかも(test-lib)内で定義されるかのように振舞うよう変更した。(本来はそうあるべきだった)。
ただ、これだけのことでも一筋縄ではいかず、結局コンパイラに手を入れたりと結構な量の修正が入った。問題だったのは、ライブラリ内で展開されるマクロがそのライブラリで定義された値を知っている必要があって、Sagittariusではその情報はコンパイラのみが知ることができるもの (マクロ展開器は構文について一切知らない)なので。これを入れたので、恐らくやろうと思えば未定義の値の参照を検出したり、未定義なexportを検出したり出来るはず。(まだやらない)

リネームの問題
これは本当に苦労した。一つ前の記事で書いた動作の修正になる。これについてはあほみたいな黒魔術を使って直した感があるが、そのうちリファクタリングしてやるという意思表示のためにどう直したかという恥をさらす。
Sagittariusにはgensymがあるのだけど、それを少し拡張して、与えられたシンボルに戻すことが出来るreversible-gensymという手続きを導入した。なぜこんなものが必要だったかと言えば、syntax-rulesやsyntax-caseにあるリテラル(キーワード？)の処理に必要だったから。単純にリネームしただけではこれらのキーワードが比較不可能なシンボルに変換されてしまうが、それはマッチする際に比較できずパターンエラーになる。なので、マッチする際にリテラルを強引に元に戻すという荒業を使っている。スマートな解決策がほしいところだが、僕の頭ではいい案が出なかった。

 問題になるかもしれない変更点
 リネーム問題の解決するに伴い、「それどうよ？」的な変更が入っている。それは、syntax-rulesもしくはsyntax-caseで定義されたリテラルが暗黙の内にマクロとして定義される。まぁ、大きな問題としては、unboundだと思って&assertionを期待していると&syntaxが飛んでくるようになった程度か？

とりあえず、0.3.6でマクロ周りが多少改善されるはず。小宇宙が少し高まっただろうか？

syntax-rules

マクロ周りは非常に奥が深くて僕では溺れてしまうという話。
昨日の記事を書いた後(しばらくは冪剰余やってたけど)気づいた。そういえば、Sagittariusではsyntax-rulesを使ってdummyみたいなことは出来ないと。
ということで、テスト。

;;(import (rnrs))
;;(import (scheme))
(define-syntax test
  (syntax-rules ()
    ((_ var val)
     (begin
       (define dummy val)
       (define (var) dummy)))))

(test a 'a)
(test b 'b)
(display (a)) (newline)
(display (b)) (newline)

最初のコメントは処理系に応じて入れたり消したり。試した処理系。

• R5RS Gauche、Racket(plt-r5rs)
• R6RS Ypsilon、Mosh、Petite Chez Scheme、Sagittarius(R6RS?)
• R7RS Chibi-Scheme(一応そう謳ってるし)

とりあえず、ほしい結果は多分以下。

#| R6RS的にはこうだよね？
a
b
|#
#| 字面的にはこうでもよさげ？(2)
b
b
|#

dummyというシンボルを使いまわしているように見えるので、(2)でもいいような気がしないでもない。(R6RSまじめに読んでない、R5RSは目を通したことすらない気がする・・・)
結論を言えば、Racket、Ypsilon、Mosh、Petite Chez Schemeは最初の結果、残り(Gauche、Chibi及びSagittarius)は2番目になった。

分かっていたんだけどね、こうなるって(Sagittariusの話)。そして、これは現状のつくりを維持するなら正直直しようがない。原因は2番目の結果になった処理系は、dummyを参照することができるということ。Sagittariusは確定なんだけど、恐らく残りの2つもマクロ展開時にシンタックスの情報を持っていない。なので、dummyとdefineの区別がつけられず、シンボルのrename(もしくはunintern)を行えない。

単純な話、上記の例で言えば、2つのdummyは同じrenameされたシンボルに変換できる。そうすると、トップレベルではdummyというシンボルは何かしらにrenameされているので見えないが、varが束縛(捕捉？)したdummyは同一のものにrenameされているのでそこからは見える。

これ多分、明示的にマクロ展開のフェーズを持たないと無理じゃないかな？もしくは、マクロ展開器がもっといろいろ知っている必要がある。あぁ、でもそれくらいならいけるかな？

結局、テンプレートをre-writeする際に、それがグローバルに束縛されているならそのままで、そうじゃないものならrenameとかすればいいかも。(でも、やるなら0.3.7以降だな。0.3.6はリリースが近いから無理だ)

これって、R5RSとR6RSで明確に定義されている非互換な動作なのだろうか？

マクロ、マクロ、マクロ

Sagittariusを試してもらえているというのは非常にありがたいし、嬉しいことである。それがたとえ動かない動作であっても(T_T)

動かない動作は以下のサイトより

衝突回避と暗黙のimport - 主題のない日記 

id:SaitoAtsushさん(こう書くのがHatena流だっけ？)は僕が絶対書かないタイプのマクロをガンガン書かれて、しかもそのテストにSagittariusも使ってくださっていてなんともありがたい。

ただ、まともに動いたことがない感じがするのがとても心苦しかったりもするだけれど・・・(R6RS名乗るの無理になってきたか・・・？)

さて、今回の不具合はパッと見、恐らく現状のマクロ展開の仕組みを使っていると直すのがかなり厳しい気がする。問題なのは、define-settable内で定義される識別子(ここではset-dummy!)は自身の定義されているライブラリの参照としてオリジナルのライブラリ(settable-variable)を持つ(はず)。そうすると、(test-lib)内で定義されているにも関わらず、参照を解決する際にオリジナルを見に行く。っで、unbound variableが投げられて悲しい思いをする。というのがパッと見た感じのエラーの原因と思う。
(あれ？でもこんな感じのマクロはdefine-record-typeとかでも普通に使われているはずだから、そんなはずないよなぁ？)

見た感じ、このマクロは結構コーナーエッジっぽいみたいで、意図どおりに動く処理系はRacketとYpsilonのみっぽい。実際手元のnmoshで試したらエラー投げた。
ちょっとpriority低めでIssue上げとくか・・・

冪剰余

まだ実装中なんだけど、必要な部分は出来て動いたのでちょっとベンチマークを取ってみた。

(import (rnrs) (crypto) (math) (time))
(time (generate-key-pair RSA :size 1024 :prng (pseudo-random RC4)))

自宅のX60で2048bitの鍵を作るのは自殺行為なので1024bitで。っで、以下が結果。

$ sash test.scm

;;  (generate-key-pair RSA :size 1024 :prng (pseudo-random RC4))
;;  4.265625 real    4.188000 user    0.078000 sys

$ ./build/sash.exe -Llib -Lsitelib -Lext/crypto test.scm

;;  (generate-key-pair RSA :size 1024 :prng (pseudo-random RC4))
;;  0.953125 real    0.890000 user    0.046000 sys

下が開発版。4倍程度高速になっているのが分かる。これくらい高速なら実用に耐えるだろうか？まだJavaと比較すると2倍から3倍遅いが・・・(比較する対象が間違っているのかもしれないと思い始めてもいる。)

Javaの実装に習って、Miller Rabinテストの試行回数を1024bit以上の時は2回にしてメルセンヌ数をチェックする処理を試したんだけど、結果が返ってこなかった。多分ヤコビシンボルを探すのが遅いのだろう。さすがにそこまでC側で実装するべきか悩むところだ。(Lucus Lehmer法自体がBignumを直接操作しないと遅いのかもしれない。まぁ、後の課題にする。)

mod-exptの動作としては、まだ対称の数(x ^ e mod mのx)が偶数の場合の処理が未テストかつ多分動きがおかしいはず。テストを書きつつ動作を検証していかないと。

Open Monumentendag@Haarlem

I actually didn't know what open monumentendag was. But I went there.

This was meetup stuff and originally it was Utrecht however organiser had just heard that most of the monuments were closed on Saturday so he changed it to Haarlem. Well, I've never been to Haarlem before (even though I've been living here for 3 and half years already!) so there was no reason not to go;)

 Central square? I don't know the place name. The sun glasses guy was the organiser.

 Inside of the city hall (if I following the explanation correctly...)

 They have a huge draw.

 Inside of the church which was on the first photo. Male choir was there. They were pretty good.

Should be a pipe organ. But I also saw a much smaller one, so this might not be the one.

Yes, as you already know I'm not a good photographer, so the photos are that's it.

Then we went through the city and into some museums. It was quit interesting to me. The city itself was totally different from other cities such as Leiden, Amsterdam or the Hague. (I don't know much about Rotterdam even though I work there:P)

冪剰余実装中

単にメモリ割り当てを減らしただけでは鍵対生成に対して実用的なパフォーマンスが得られないことが分かったので(2048bitで5秒からかかる)、どこが遅いかを調査した。結果、素数テストを行っている手続きで使用されている冪剰余の計算が遅いことが判明。x^e mod mを計算する際のx, e, m全ての数が2048bitあった際に20秒かかるという脅威の遅さだった。(3GHz Core i7)

Javaは2048bitの鍵対生成でも同マシンで1秒以下の時間で作ってくる。篩とかあるけど、何より素数チェック、その中で使われている冪剰余が高速なのだと仮定して実装をチェック。素数チェックはTwitterでも呟いたけど、Miller Rabinテストが1024bitを超えると試行回数が2回で、その代わりメルセンヌ数のチェックが入っていた。冪剰余についてはColin PlumbのBignumライブラリを元にした高速な実装になっている。

現状Sagittariusでは冪剰余を求める際に単純なバイナリ法を使っている。普通に

(mod (expt x e) m)

とするよりは遥かに高速なのだが、数値がBignumになってくると計算の度にメモリ割り当てが入りあまり嬉しくない。(eは1bitずつ右シフトされるので、2048bitあると、32bit環境では単純計算で2000回以上の割り当てがexponent部分だけで発生する)。
上記の実装(とりあえずはJavaの)ではメモリ割り当てがかなり削られている。正確には数えていないが、最大でも20回行かない程度に抑えられそうである。

ならばやらないわけには行くまいと、とりあえずJavaから実装を移植したら嵌った。

問題になったのはJavaのBigIntegerは内部で持っているintの配列のオーダーがSagittariusとは逆順になっているのだ。理由は知らないんだけど、きっとその方が効率がいい場面が多いのだろう。もしくはPrimitiveな配列でさえサイズを取ることができるからなのかもしれない。なので、単純にJavaから実装を持ってくるのは失敗に終わった。

恐らく中で何をやっているのか理解してやれば逆順に対応するのも難しくはないのだろうが、高速なモントゴメリ法の実装自体に興味があるわけではないので、可能な限りその労力は避けたい(ものぐさ)。ということでオリジナルの実装を当たってみることにした。←いまここ

マクロ展開時のライブラリ

以下のツイートを発見。

文字列補間マクロ書いたけど Sagittarius で動かない。
— (32) 齊藤敦志さん (@SaitoAtsushi) 9月 5, 2012

動かないのは許せない(というか、バグだし)ので、原因を探る。元コードはきっとこれだろう。

文字列補間 - 主題のない日記 

とりあえず、走らせる。&assertionか。なんとなく既に嫌な予感がしている。 いろいろ省略して原因箇所：

(datum->syntax #'string-interpolate 'x->string)

これ。全体というよりも、#'string-interpolateの部分のみ。

何故か？これ多分マクロ展開器の根幹の問題で、(syntax foo)という構文は定義されたライブラリ内ではなくimportされた先のライブラリで解決される。つまり、識別子が所属するライブラリがおかしいのである。なので、datum->syntax手続きが、#'string-interpolateからx->stringを作る際に本来ならば定義されたライブラリの情報を付加しないといけないんだけど、importしたライブラリの情報を付加する。結果、unbound variableといって怒られる。

とりあえず、一時的なしのぎとしてx->stringもexportしてしまうのが最も簡単な解決方法であろう。0.3.6以降のどこかで頑張って直そう。ちょっと(かなり？)大き目のバグが2つになった。燃える(φΛφ)

やはりいろいろな人に検証してもらうのは非常にありがたい。僕一人では恐らく未来永劫気づかなかったバグだ。

相手の言いたいことを想像する

こっそり転職活動をしていて、ふと思ったこと。ちなみに、行間を読むのではなく、もっと物理的な話。

こっちでは(僕があんまり熱心に転職活動をしていないからなのか)、エージェントが電話もしくはメールを送ってきて求職条件にマッチしたら先に進めるという、どちらかといえば受動的な感じでことが進む。もちろん、自分から応募した場合は向こうの条件に職歴等がマッチした場合のみ先に進む。この辺はどこでも一緒だろう。

さて、現在僕は1件面接が予定されていて今日の午後にそれに行く予定である。っが、それは別の話。今回はその面接をアレンジしたエージェントの話である。

よく、「オランダ人では話しかけた言語で会話を進められる」といわれるくらい言語能力が高いと信じられている。まぁ、ヨーロッパ内の言語なら概ねそうと言えるが、もちろん例外もいる。件のエージェントはどちらかと言えばその例外に当てはまる方のタイプで、ちょっと英語能力が怪しい。そうすると、たまに「何が言いたいのかいまいち分からない表現」というのが出てきて、多分これかなぁと想像することがある。正直なところこれが結構きつい。

何故きついか？普通に日本語を勉強している外国人と会話する際のことを思い浮かべればいいだろう。途切れ途切れで話すとか、言い回しがなんだかわけの分からないものだったりとか、そんな感じ。そうすると、多分こういいたいのかな？と推測をするわけだ。問題は、母語であればその推測が大抵当たるし、そんなに大変じゃないんだけど、第二外国語以降の言語だと習熟度に応じて難易度が変動する。僕の英語はリーズナブル(なんて訳すといいんだろう？)レベルだと思っていて、その手のことをするのは結構しんどいのである。特に、つっかえつっかえだと1秒前に言われた言葉が頭から抜けるのだ。

理解できなかった部分はどうするのか？聞きなおしても同じことが起きるので、「とりあえず最後にメール送ってくれるように聞いてみるか」となって理解を放棄する傾向にある。水は低い方に流れるのだ。あまり、相手の言いたいことを想像しない。よくない傾向である。

ちなみに、この現象は人ごみの中で電話をとったときとか、バスの中、電車の中でも起きる。雑音の中から向こう側の声を拾えないのである。(取りこぼすといった方がいいか？)。これは単純に言語能力の問題なのでヒアリング能力を上げるしかないのだが。

こういう細かい部分ってどうやって鍛えればいいのだろう？なにかいい方法があれば是非教えて欲しいです。

メモリ使用量

Sagittariusは割りと富豪的にメモリを喰う傾向にある。理由はいたって単純で、いろんなところで利便性のため冗長な情報を持たせているからである。

っが、それでは困ることが出てきた。テストを走らせるとかなりのメモリを消費し、Cygwin上でメモリ不足で落ちることがあるのである。地道に不要なオブジェクトをGCフレンドリにしたりして、50MB程度使用量を削ったのだが、焼け石に水感が拭えない。結局後100とかテストファイルが増えれば元の木阿弥な気がするからだ。

実は何が冗長な情報を持っているかは分かっている。ライブラリだ。どこかで書いたがSagittariusではライブラリもオブジェクトでその中にいくつかのメタ情報を持たせてある。importやexportの情報だ。 この二つは必須なので削りようがないのだが、もう一つ、そして恐らく大量にメモリを消費している情報で、親ライブラリ情報がある。これは何をしているのかと言えば、どのライブラリから何がimportされたかという情報である。たとえば以下のコード；

(library (lib1) (export v1) (import (rnrs)) (define v1 1))
(library (lib2) (export v1 v2) (import (rnrs) (lib1)) (define v2 2))

(lib2)は(rnrs)と(lib1)を親ライブラリとして持ち、(lib1)からv1を(rnrs)からは全てのシンボルをimportしているという感じである。

これが、かなり冗長(無駄ともいう)情報を持っていて、たとえば、(rnrs)は親に(rnrs base)とか持っていて、(lib2)はそれが何をexportしているという情報を全て持っている。なんでそんな冗長にしてあるかと言えば、ライブラリから値を引っ張り出してくる際に、その方が楽だからなのだが、はっきり言えば無駄である。実際、import情報だけあれば、全て解決するものであるのだからだ。

このライブラリの実装は複雑怪奇になっていて、正直自分でも必要がなければ構いたくないレベルになっている。(キャッシュもそうだが・・・)。っが今回必要が出てきてしまったので、頑張ってリファクタリングすることにする。とりあえず、意思表示だけ。

RSA key generation

I wasn't satisfied with the performance of RSA key pair generation at all since Sagittarius supported cryptographic operations. So I've done a lot of performance tuning such as bytevector->integer, integer->bytevector procedures. These changes, however, did not make that much difference even it's been improved 100 times faster than previous implementation.

Why? Actually I knew why. The prime number generation was really slow. It reads random number each time and checks if the number is prime or not with Millar Rabin test. In this prime number generation procedure, bytevector->integer is used so I thought if I improve the performance it would be changed dramatically. I've bet on the wrong horse, unfortunately.

Then I let it be for long time (I guess 3 month or so?) and I've got an idea today. The random number generation creates fresh bytevector each time, what if I modified it to read destructively. So I have introduced read-random-bytes! procedure and modified random-prime to use it. Now it's benchmark time. I used following code which generates 1024 bits RSA key pair.

(import (crypto) (math) (time))
(generate-key-pair RSA :prng (pseudo-random RC4))

To make sure the key generation procedure uses the same random generator, I specified :PRNG keyword. The result is below;

% sash test2.scm

;;  (generate-key-pair RSA :prng (pseudo-random RC4))
;;  1.7565269470214844 real    1.826000 user    0.047000 sys

% ./build/sash.exe -Llib -Lsitelib -Dbuild -L./ext/crypto -Lext/time test2.scm

;;  (generate-key-pair RSA :prng (pseudo-random RC4))
;;  0.769230 real    0.749000 user    0.031000 sys

Yes! It's improved as twice fast as before. The problem is, however, this change, more specificaly read-random-bytes!, introduced imcompatiblity of 0.3.5. Well, the change only affects custom pseudo random generator and I guess it's used by only me. So just wrote note on the document.

続 exportされた変数

一つ前の記事で、実行時エラーにしていたがえいやっとコンパイル時エラーにすることにした。

Sagittariusではライブラリも(実は)First class object(訳語忘れた)で、普通のR6RS処理系がするようなライブラリをrenameしてごにょごにょということは(いい悪いは別にして)行わない。 マクロ展開フェーズというものもなく、全てコンパイル時に解決している。これは、マクロ展開器とコンパイラで定義が被るのが嫌だったので。似たようなコードがそこかしこに出てくるのが我慢ならなかった。

本題に戻る。なので、ライブラリが別であれば、識別子は被っても問題ない。lookup(訳語知らない)時にimportされているものを調べて合致したものを返しているだけなので。なので再定義されても、参照される先が変わるだけ。正直特に必要性を感じていなかったし、今では面倒になっただけかも感があるのだが、規格に準拠するのもポータブルなコードを書くのには欠かせない部分だろうと重い腰を上げた感じ。

どう実装したか？
実は非常に簡単で、グローバルに値を定義できる構文と値を変更できる構文ってSchemeでは合計で3つしかない(よね？)。つまり、define、define-syntaxとset!の3つ。前2つは定義された値が同じライブラリ外で既に定義されていればエラーを投げる。set!は先に局所変数を探して、違ったら大域変数なので、その際にチェック。
問題だったのは、bootコードを生成するSchemeコードが再定義を前提で書かれていること。全部ライブラリ形式に書き換えてすっきりさせるというのもありだったのだが、面倒だったのでとりあえず再定義可能なモードを急遽入れて対応。ごにょごにょ黒魔法的な何かを使うよりはいいだろうと思う。そのうち書き直そう。

ちょっとした課題？
正直デフォルトで書き換え不可はあまりに面倒だなぁと思っているので、R6RSもしくはR7RSモードの際だけにするかもしれない。テストケースをコンバートしている際に思った。どうも僕はゆるい開発スタイルの方が好きらしい。

Shiroさんのコメントで何故R6RSが再定義を許さないかというのが非常に面白かった。既存の名前空間(モジュールシステム？)を実装していない処理系でもライブラリが持てるような考慮なんだろうか？psyntaxとか他の展開器(Andre van Tonderのしか知らないけど)ではlibraryも展開するようになってるし。

exportされた変数

一つ前の記事に言及していた記事の著者さんからコメントが付いてた。っで、自分の書いたコメントに疑問が(ぉぃ

set!で変更可能となると、「取り扱い注意」のラベルが必要かもしれませんが。

よく考えてみると、Sagittariusでは以下のようなことができる。

(library (test)
    (export variable)
    (import (rnrs))
  (define variable 1))

(import (test))
(set! variable 2)
(print variable)
#|
;; Output
2
|#

これはR6RS的にはエラーにならないとまずい。記憶が正しかったら、R7RS的にもエラーだったはず。
Sagittariusではデフォルト(というか、現状だと必ず)「取り扱い注意」のラベルが要ることになる。直すかなぁ。変更できた方が便利だろうかと思ったんだけど、変更されない方が便利だよなぁ。

でも、Ypsilonでも#!r6rsをつけないとエラーにならないなぁ。 どうしよう？