Cygwinのメモリ

Cygwinだけなのか、Mingwもなのか、そもそもC++の企画なのか分からんけど、メモリの確保ではまった話。

Cygwin上のGCCで(正確にはG++)1M以上のメモリを確保して、そのメモリに生でアクセスしようとしたらセグメンテーションフォールトが起きた。
なんでだろうと思ったが、プログラム全体で見ると動いていたのでとりあえず放置していたのが、やっぱりおかしいよなぁと思って検証してみた。

検証プログラム

#include "test-a.h"
#include 
int main()
{
  void* p = (void*)new char[1024* 1024];
  printf("%p\n", p);

  test t;
  t.print();

  test *t2 = new test();
  t2->print();
  delete t2;
  return 0;
}

test-a.hはtestクラスを持ち、そのコンストラクタ内で1Mのメモリをoperator newで確保し、printメソッドでメモリアドレスをプリントする。それだけ。
実際はtestクラスの詳細はスタティックライブラリにしてある。スタティックライブラリの制限かなとも思ったので。

結果。
そもそも最初のnewで死んでた。
帰ってきたアドレスが、0x7fea0008。完全に死亡アドレスです。
理由は分からんが、アウトなんだろう。

しょうがないのでとりあえずWin32APIのVirtualAllocを使って回避。こっちならOKっぽい。
この制限があると、多き目のメモリープールとか不可能になる気がするが、どうなんだろう？
ってか、一気にメガ単位で確保しちゃ駄目ってこと？
誰か理由教えて(´；ω；`)

2011/10/25 追記
ひょっとしたらこの辺と関係あるかも=>Cygwinのヒープ

英語の発音について

英語の発音で日ごろ理不尽に感じてることをちょっと書いてみる。
(なんで今更こんなことをとか自分で突っ込み)

同スペル、異発音
Houston:
/ˈhjuːstən/ ≒ ひゅーすとん と発音すればテキサス州の都市(が有名、ほかにもある)
/ˈhaʊstən/ ≒ はうすとん と発音すればニューヨーク市の通りの名前(が有名、ほかにもある)

読みにくい系
simultaneously:
/ˌsī-məl-ˈtā-nē-əs-ly/ ≒ さいみゅるてにあうすりぃ。
ちなみにsimulateは/ˈsim-yə-ˌlāt/ ≒ しみゅれいと だったりする。(個人的に前者は米語だと思ってる)。

cupboard:
/ˈkʌbərd/ ≒ かばーど。知らなきゃ読めない。
ちなみに、boardは/bord/ ≒ ぼーど なので、後半だけ見ると同スペル、異発音かも。

nature:
/ˈnā-chər/ ≒ ねいちゃー。でもこれ、naturalになると/ˈna-chə-rəl/ ≒ なちゅらる になる。

英語と米語で発音が違う系
tomato:
「これが、"とめいと"だと！」と中学に入ってまず間違いなくショックを受けた言葉の一つだと思う。でも、英語(イギリス系)だと"とまーと"と発音したりする。ちなみに、tamagoは「ためいご」ではないのであしからず。

あんまりぱっと思いつかなかった。
この手のねたは需要があるかテストもかねて投稿してみたり。

Java: Preferenceクラス

Javaのことを書くなんて本当はしたくないがあまりにネタがないので。
(Schemeの方は遅々として進まん・・・orz)

仕事は当然Javaを使うのだが、APIではまった話。
Preferenceというクラスがあるのだが、こいつは設定とか値をプラットフォーム固有の方法で永続化して使いまわせる便利なもの(のはず)
っで、今のプロジェクトでこいつを使っているのだが、なんか値がおかしい。
Windowsなので、レジストリに登録されるのだが、どうも1個しか値が存在してない。
っで調べてみた。

JavaDocによると、こいつはノードを取得する際にクラスを要求するくせに、値の保存はパッケージごとに行われるということ。クラスを要求するのは、パッケージ名を取得するためだけみたい。
つまり、
foo.bar.Hogeと、foo.bar.FugaっていうクラスでPreferenceを使うと値が共有されるらしい。
この方がありがたい人もいれば、そうじゃない人もいるだろう。僕は後者なわけだが・・・

foo.bar.configなんてパッケージを作ってその下にいくつかの設定値クラスなんかを作った場合問題になる、というか僕の問題はまさにこれ。
パッケージごとに一個の永続値って需要があるのだろうか？
ドキュメントをしっかり読めば早期発見できた問題ではあるが・・・

魚

前回から1ヶ月くらい離れてるなぁ・・・

日本にいたときは便利だったなぁという話。

スーパーとかなら切り身で売ってるけど、
マーケットで魚を買うとあまり魚はきれいになっていない。
頭、内臓、鱗のことだけど。
鮮度とか安さとかならきっと上なんだと思うけど、よくて内臓くらいまでか、さばいてくれるの？
しょうがないので、包丁で鱗を落とすし、三枚にもおろす。
(身が骨の方にたくさんつくときもあるが)

この辺のサービスは絶対的に日本の方がいい気がする。
しても、追加料金取るとかざらだし。
こっちの人たちあんまり客を大切にしないイメージ。

日本が過剰サービス過ぎなのか？

どれが正しいんだ？

Schemeでdefine-syntaxの実装をしないといけないことに気づき、ちょっと調査。
単にマクロ展開のタイミングの話なのかな？

(import (rnrs))
(define (print x)
  (display x)
  (newline))

(define x 1)
(define (incf x . i)
  (if (pair? i)
      (begin (set! x (+ x (car i)))
      (print "procedure")
      x)
      (begin (set! x (+ x 1))
      (print "procedure")
      x)))
(print (incf x 2))

(define (test x i)
  (print (incf x i)))
(test x 1)

(print "define incf as define-syntax!")

(set! x 1)
(define-syntax incf
  (syntax-rules ()
    ((_ x) (begin (set! x (+ x 1)) x))
    ((_ x i) (begin (set! x (+ x i)) x))))
(print (incf x 2))
(test x 1)

こんなコードを、Chez(7.9.4)、Ypsilon(0.9.6-update3)、Mosh(0.2.5)に食わせてみる。

結果。
Chezは正常終了。最後の(test x 1)で展開されると思われてincfマクロは展開されず。
Ypisilonは最後の(test x 1)でincfの定義がない(多分、マクロで上書きされたから？)と怒る。
Moshはincfが複数定義されたといって例外。

それぞれの結果はこれ。
Chez
------------
procedure
3
procedure
2
define incf as define-syntax!
3
procedure
4
------------

Ypsilon
------------
procedure
3
procedure
2
define incf as define-syntax!
3

error: unbound variable incf

backtrace:
0 (incf x i)
..."D:/home/t.kato/test.scm" line 18
1 (test x 1)
..."D:/home/t.kato/test.scm" line 29
------------

mosh
------------
Condition components:
1. &who who: incf
2. &message message: "multiple definitions of identifier"
3. &syntax form: incf
subform: #f

Exception:
error in raise: returned from non-continuable exception

Stack trace:
1. throw:
2. (raise c): baselib.scm:943
3. apply:
------------

これだけバラバラだとどれが正しいのかわからない・・・

英語で仕事をするということ

最近、楽天の社長が社内公用語を英語にするという記事を読んだのと、
それに反応してソニーかどこかの人がTwitterで、そんなことするくらいなら公用語をC言語にする、などといったのを読んだので無駄に反応してみた。

個人的な意見。
まったく無駄だと思います。
日本に本社があって、社長も日本人で、働いてる人の95%以上が日本人の環境で、英語にする意味がない。こっちで働いていて、使用言語はオランダ語ではなく英語なわけだが、オランダ人同士が会議している場所だと当然オランダ語。
そもそも、怪しい英語で会議しても意味なくね？英語が喋れることが最重要事項な会社って、翻訳会社か何かだと思う。楽天はそっち系に変わるのかね？

できることなら日本語環境がいいなぁと思う人の独り言・・・

街が揺れた日

その日は暑い夏の日だった。仕事帰りの私はいつもと同じ道を歩いていた。
突如凄まじい轟音とともに街が一瞬揺れた！

えぇ、その瞬間がオランダがブラジルを下したことが決定した瞬間です。
正直、1点とったのかなと思ったんだけど、勝ってました。
ブラジルにですよ。信じられん。

ブラジルに勝てたということはそのまま優勝ということもありえるなぁ。

C++で書き始めた

Scheme処理系をC++で書き始めた。
(実際は片付いてない問題が多々あるのだが・・・)

とりあえず、コードがVectorで構成されているのでVectorを。あと物が動くとやはりうれしいので、Fixnumなクラスを作成。
xyzzyの参考に(パチッてとも言う)、クラスのタグ付けとか、即値の判定とか作成。
っで、適当にごにょごにょして動かす。

(+ 1 2 3)をコンパイルした結果をC++のオブジェクトに置き換えたものが動いた。
説明が長い・・・

気になる点としては、現状だとコードはベクターの中にベクターが入れ子になるように作ってあるのだが、これだとメモリー効率が激しく悪い気がする。
Schemeで書いてるときは気にしなかったのだが、C++で書いてみると一つのコードを書くのにベクターの割り当てが激しく出てくる感じ。
コンパイラを書き換えて全部フラットにするべきだろうか・・・するべきなんだろうなぁ・・・

ワールドカップ

日本が3－1でデンマークに勝った！！
何が起きてるんだろう？天変地異の前触れか？

どうでもいいが、ここオランダではサッカーがあるとえらいことになる。
僕の住んでるライデンにはちょっとした広場が街の中央にあるのだが、そこにパブリックビューがあって結構な人が集まっていた。
酒が飲めればいいのか、騒げればいいのか、純粋にサッカーが好きなのかどれなのかは分からないが、街中がやかましい。
噂によると、サッカーの観戦をするために仕事を病欠する人がいるそうだ。
そんな国。

letのフレーム

A正規化の話だったりする。
たとえばこんなコード(変な数字が入ってるのはα変換後だから)

(define
 tarai
 (lambda
  (x.1 y.2 z.3)
  (if
   (not (< y.2 x.1))
   y.2
   (tarai
    (tarai (- x.1 1) y.2 z.3)
    (tarai (- y.2 1) z.3 x.1)
    (tarai (- z.3 1) x.1 y.2))))

こいつをA正規形にするとこうなる

(define
 tarai
 (lambda
  (x.1 y.2 z.3)
  (let
   ((#:G267 (< y.2 x.1)))
   (let
    ((#:G268 (not #:G267)))
    (if
     #:G268
     y.2
     (let
      ((#:G269 (- x.1 1)))
      (let
       ((#:G270 (tarai #:G269 y.2 z.3)))
       (let
        ((#:G271 (- y.2 1)))
        (let
         ((#:G272 (tarai #:G271 z.3 x.1)))
         (let
          ((#:G273 (- z.3 1)))
          (let
           ((#:G274 (tarai #:G273 x.1 y.2)))
           (tarai #:G270 #:G272 #:G274)))))))))))

見てのとおりコードが増大。それだけならまだいいのだが(よくないが)、問題はコードの増大に伴ってletが出現していること。
前回、継続周りで不具合が起きることを踏まえて、letが現れたらフレームを作るようにコンパイラとVMを修正したのだが、その影響で単なるたらいまわし関数がスタックオーバーフローを起こすようになった。
原因は、この大量のlet。これだけコードが増大すれば当然VMのインストラクションも増大する。どれだけ影響があるかスタックを1000から10000にして上記の関数でベンチマークをとってみた。
4秒が14秒に・・・orz

後の最適化がしやすいようにと思ってのA正規化だが、ちょっとないなぁ・・・
今のところこいつの恩恵って、変数の寿命がわかりやすいことだけだし・・・
どうしよう。

スタックポインタ、フレームポインタ

Schemeのコンパイラの話。
3impという論文のコンパイラを参考に作っているわけだが、スタックポインタとフレームポインタではまった。
(ってか、今でも解決してない)

ここにあるスタックとフレームの関係を参考にして、letのコンパイルをしたのだが、上手くいかない。
原因は分かっている。本来はletごとにフレームを作成して自由変数とかの解決をしないといけないのに、フレームを作るコストを嫌って、letが続く限り一つのローカルフレームのようにしたから。
そもそも、letではフレームを作ってないので、フレーム情報があることを前提にしているVMインストラクションでおかしなことが起きる。

どうしよう。
とりあえず、Gaucheがletをどう処理してるのかdisasmしてみた。
...
let毎にフレーム作ってる・・・
やっぱりそうするべきかなぁ？でもA正規化後ってあほかと思うほどletが増えるんだよなぁ・・・
その辺も踏まえてどうしよう。

コンパイル

いろいろ弄って、letをコンパイルできるようにした。
意外と上手くいくもんだ。四苦八苦したけど・・・

っで、たらいまわし関数を動かしてみたら、10,5,0の引数で36秒かかる・・・
まぁ、schemeをscheme上で動かしてるのでオーバーヘッドとかもあるだろう。っがあまりに遅いのでできそうな高速化を施すことに。
現状リストでVMのインストラクションを書いていたが、全部ベクターに変更。でも、面倒くさがりなので、
ベクターの中にベクターを入れるといういんちき(？)をして、データ構造は特に変更しない。
勢いあまってVMにプログラムカウンタをつけてみたけど、要らん気がする。まぁいいや。

これで、一時的に5倍くらい早くなった。
次にインストラクションを今後のために数値に変更。これは逆に遅くなった。
考えられそうな理由は現状プリミティブの実装がかなり適当で、シンボルと数値の比較が一つのcond文に混在している。なので、シンボルの比較を先にしないと、Gaucheに怒られた。っで先に回したら鈍足に・・・
比較の分だけ遅くなるわね。
逆に言えば、よく使われるインストラクションは前の方に持ってくると幸せになれるか？

っで、とりあえずプリミティブをいんちきせずにコンパイルするようにしている最中。
物が動いてくるとやはり楽しい。

カメルーンに勝った

ワールドカップの話。
職場が半日だれも仕事しないくらいオランダはサッカーが熱い(個人的にはどうでもいいが)
職場で点が入るたびに雄たけびが聞こえてくるくらい。

っで、それのあおりで日本VSカメルーンを少し見た。
あれ？勝ってる？
1-0で日本が勝った・・・

とりあえず、前評判を的確に表していたであろうコピペ。

Ａ　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　Ｂ　
南アフリカ「ガチ抽選をした結果がこれだよ！」　　　アルゼンチン「なんだ楽勝じゃん」
メキシコ「南アフリカ乙」　　　　　　　　　　　　　　　　　ナイジェリア「２位ならなんとか」
ウルグアイ「南アフリカ乙」　　　　　　　　　　　　　　　韓国「＼( ^o^)／」
フランス「実質シードﾜﾛｽｗｗ」　　　　　　　　　　　　　ギリシャ「２位ならなんとか」

Ｃ　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　Ｄ　
イングランド「アジアとやらせろよ」　　　　　　　　　　　ドイツ「そこそこの組み合わせかな」
アメリカ「微妙・・・」　　　　　　　　　　　　　　　　　　　　オーストラリア「２位いけるな」
アルジェリア「無理くさい」　　　　　　　　　　　　　　　　セルビア「２位いけるな」
スロベニア「微妙・・・」　　　　　　　　　　　　　　　　　　ガーナ 「２位いけるな」

Ｅ　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　Ｆ
オランダ「まぁ、おｋ」　　　　　　　　　　　　　　　　　　　イタリア「楽勝ｗｗｗ」
デンマーク「日本には勝つとして・・・」　　　　　　　　　パラグアイ「ニュージーには勝つ」
日本「なかなかいい組み合わせだな(ｷﾘｯ」　　　　　　ニュージーランド「なにこの無理ゲー？」
カメルーン「日本には勝つとして・・・」　　　　　　　　　スロバキア 「ニュージーには勝つ」

Ｇ　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　Ｈ
ブラジル「１位通過するよ」　　　　　　　　　　　　　　　スペイン「楽勝すぐるｗｗ」
北朝鮮「どうしてこうなった！」　　　　　　　　　　　　　スイス「ホンジュラスには勝つ」
コートジボワール「１位通過するよ」　　　　　　　　　　ホンジュラス「まぁ、がんばる」
ポルトガル「１位通過するよ」　　　　　　　　　　　　　　チリ 「ホンジュラスには勝つ」 

う～ん、何が起きたんだろう？

ミーはおフランス帰りざんす

ということで、パリに行ってきました。
パッケージツアーというのは今までの人生でほとんど経験がないので(修学旅行等除く)それなりにいい経験になったかなと。
言葉の壁さえ考えなければ、交通費、朝食、夕食、セーヌ川のボートツアー、その他いろいろ混みで150ユーロは安いのではないかな。

パリの街は思っていた以上になじむなぁとちょっと感じた。
そこらじゅうで言われていた、犬の糞の問題は特になく、きれいだったし。

っが、街はきれいでも人は・・・
パリで運転する必要がある人はかなりの胆力が必要になるだろうなぁと。

時間がないので適当。

やっつけA正規形拡張

とりあえず、オリジナルのA正規形で問題かなと思ったのが以下の点。

1. letが引数一つ
2. cond、letrec等の必要そうな構文がない(condはif文で書きかえれるけど・・・)
3. quoteしたものも正規化する

ということでちょいちょい変更。

1. letが変数一つって扱い難いので複数取るように変更。(let (<binds>) <body>)というが普通のletなのでこれを取るようにし、<binds>の(変数 値)という式を一つずつ正規化後letを再構築。

2. condは

(cond (<pred1> <then1>)
      (<pred2> <then2>)
      (else <then>)

という式なので、pred1 ... pred2をこんな感じに

(let ((p1 (normalize <pred1>)))
   ; 以下predの数だけ

っでthenを正規化してcondを再構築。
letrecとletrec*はバインド変数だけ正規化してそのまま放置。とりあえずこれでいいか？

3. オリジナルは(display 'a)というのが(let ((r 'a)) (display r))ってなってたので、さすがにあほらしいかと思い、quoteは正規化しないことにした。

っで、とりあえず3impのコンパイラでコンパイルしてみた。
おぉ、コンパイルできた。
っが、コンパイラにletをコンパイルする記述はない・・・さて、考えるか・・・

A正規形に切り替える

CPS変換がどうにも上手くいかない。
なんとかなるんだろうけど、涙が出そうになってきたので断念。
一応、それ以外の理由として、

1. コードの肥大化がすさまじい
2. 変換することによって、関数のシグネチャが変わる(継続を渡すように変更するため）
3. ベンチマークで脅威の低速を叩き出してる

この辺がそれ以外の理由。まぁ、3番目はVMの最適化次第だと思うけど・・・
(Gauche上で動かしてるのでしょうがない)

ということで、A正規形に切り替えることにする。
A正規形はCPS変換後逆CPS変換した形に極めて近い気がする。すべての継続の結果を変数として確保するので、スタックの肥大化が問題かな？
ここが詳しい。別に論文も読むといいと思う。
論文の最後にアルゴリズムをschemeで実装した例がある。
問題はこいつはCore SchemeというSchemeのサブセットを対象としているので、いろんな部分で限定的。(letrecとかないし・・・condとかどうするんだろう？)
その辺りを自前で拡張することができればよさそうだ。できるかな？

コメントの仕方

コメントの仕方が分からないという指摘が累計2件ほどたまったので(少ない)
蛇足ではあると思うけど書いてみる。

コメントしたいと思う投稿の一番下にある、数字 + コメントという(このブログだと緑)のリンクをクリックする。
するとなんとも味気ないコメント投稿画面が現れるので、大き目のテキストエリアにコメントを書き込む。
スパム防止機能があるので、コメントのテキストエリアの下にあるフィールドに画像の英数字を入力。
投稿者のIDを選択。OpenIDはよく分かっていないが、Googleアカウントがあればそれでもいいし、そんなもの無いなら名前/URLを選択し名前を入力。もちろん匿名でも構わない。
最後に投稿ボタンを押せば完了。
bloggerのコメントはきっと共通だと思うので、これで他のbloggerにもコメントができる！

さぁ、早速この投稿にコメントして練習だ！

ぬか喜びだった件・・・

前述のベンチマークだが、手動CPS変換が間違っていた。
正しくはこう

(define (<=/cps x y k) (k (<= x y)))
(define (-/cps x y k) (k (- x y)))
(define tarai-cps  
  (lambda (x y z k)
    (<=/cps x y
     (lambda (b)
       (if b
    ;ここが違う
    (k y)
    (-/cps x 1 
    (lambda (x2)
      (tarai-cps x2 y z
          (lambda (t1)
     (-/cps y 1 
     (lambda (y2)
       (tarai-cps y2 z x
           (lambda (t2)
             (-/cps z 1
             (lambda (z2)
        (tarai-cps z2 x y
            (lambda (t3)
              ;ここも
              (tarai-cps t1 t2 t3 k))))))))))))))))))
(time (tarai-cps 10 5 0 (lambda (x) x)))

っで、ベンチマークの結果。

Petite Chez Scheme 7.9.4
(time (tarai-org 10 ...))
    no collections
    16 ms elapsed cpu time
    0 ms elapsed real time
    0 bytes allocated
(time (tarai-cps 10 ...))
    10 collections
    125 ms elapsed cpu time, including 0 ms collecting
    0 ms elapsed real time, including 0 ms collecting
    44600752 bytes allocated, including 42111448 bytes reclaimed
(time (tarai-anf 10 ...))
    7 collections
    78 ms elapsed cpu time, including 0 ms collecting
    0 ms elapsed real time, including 0 ms collecting
    29505120 bytes allocated, including 29499488 bytes reclaimed
(time (tarai-lambda 10 ...))
    7 collections
    78 ms elapsed cpu time, including 0 ms collecting
    0 ms elapsed real time, including 0 ms collecting
    29505120 bytes allocated, including 29490760 bytes reclaimed

Gauche 0.9
;(time (tarai-org 10 5 0))
; real   0.016
; user   0.015
; sys    0.000
;(time (tarai-cps 10 5 0 (lambda (x) x)))
; real   0.453
; user   0.407
; sys    0.047
;(time (tarai-anf 10 5 0))
; real   0.031
; user   0.031
; sys    0.000
;(time (tarai-lambda 10 5 0))
; real   0.422
; user   0.375
; sys    0.047

圧倒的じゃないか。。。orz
どう考えてもなしの方向っぽいです、本当に(ry

ベンチマーク

CPS変換の勉強中にANF(A-normal form)との共通点を見つけて、
ひょっとしてCPS変換しなくてもA正規化すればいいのでは？
という誘惑にかられたことから、ちょっとベンチマークとってみた。
(どっちが速度が出るか比較したかった。速い方がいいじゃん！)

使用したコードは以下

(define tarai-org
  (lambda (x y z)
    (if (<= x y)
 y
 (tarai-org (tarai-org (- x 1) y z)
     (tarai-org (- y 1) z x)
     (tarai-org (- z 1) x y)))))
(time (tarai-org 10 5 0))

(define (<=/cps x y k) (k (<= x y)))
(define (-/cps x y k) (k (- x y)))
(define tarai-cps  
  (lambda (x y z k)
    (<=/cps 
     x y
     (lambda (b)
       (if b
    y
    (-/cps
     x 1 
     (lambda (x2)
       (tarai-cps 
        x2 y z
        (lambda (t1)
   (-/cps
    y 1 
    (lambda (y2)
      (tarai-cps
       y2 z x
       (lambda (t2)
         (-/cps
   z 1
   (lambda (z2)
     (tarai-cps
      z2 x y
      (lambda (t3)
        (k (tarai-cps t1 t2 t3)))))))))))))))))))
(time (tarai-cps 10 5 0 (lambda (x) x)))

(define tarai-anf
  (lambda (x y z)
    (let ((G139 (<= x y)))
      (if G139
   y
       (let ((G140 (- x 1)))
  (let ((G141 (tarai-anf G140 y z)))
    (let ((G142 (- y 1)))
      (let ((G143 (tarai-anf G142 z x)))
        (let ((G144 (- z 1)))
   (let ((G145 (tarai-anf G144 x y)))
     (tarai-anf G141 G143 G145)))))))))))
(time (tarai-anf 10 5 0))

(define tarai-lambda
 (lambda (x y z)
  ((lambda (G143)
     (if G143
  y
  ((lambda (G144)
     ((lambda (G145)
        ((lambda (G146)
    ((lambda (G147)
       ((lambda (G148)
   ((lambda (G149)
      (tarai-lambda G145 G147 G149))
    (tarai-lambda G148 x y)))
        (- z 1)))
     (tarai-lambda G146 z x)))
  (- y 1)))
      (tarai-lambda G144 y z)))
   (- x 1))))
   (<= x y))))
(time (tarai-lambda 10 5 0))

tarai-orgが元のたらいまわし関数。以下、-cps、-anf、-lambdaと続くが、順に元の関数のお手製CPS変換、A正規化、A正規化後letをlambdaに変換したものとなっている。 っで、以下がベンチマーク結果

Petite Chez Scheme 7.9.4
(time (tarai-org 10 ...))
    no collections
    16 ms elapsed cpu time
    0 ms elapsed real time
    0 bytes allocated
(time (tarai-cps 10 ...))
    no collections
    0 ms elapsed cpu time
    0 ms elapsed real time
    840 bytes allocated
(time (tarai-anf 10 ...))
    7 collections
    78 ms elapsed cpu time, including 0 ms collecting
    0 ms elapsed real time, including 0 ms collecting
    29505472 bytes allocated, including 29469704 bytes reclaimed
(time (tarai-lambda 10 ...))
    7 collections
    78 ms elapsed cpu time, including 0 ms collecting
    0 ms elapsed real time, including 0 ms collecting
    29505120 bytes allocated, including 29489216 bytes reclaimed

Gauche 0.9
;(time (tarai-org 10 5 0))
; real   0.016
; user   0.016
; sys    0.000
;(time (tarai-cps 10 5 0 (lambda (x) x)))
; real   0.000
; user   0.000
; sys    0.000
;(time (tarai-anf 10 5 0))
; real   0.031
; user   0.031
; sys    0.000
;(time (tarai-lambda 10 5 0))
; real   0.437
; user   0.359
; sys    0.078

個人的には超意外にもCPSが一番早かった！！
Gaucheのdisasm関数でコンパイル結果を見てみたが、末尾最適化が効いてるのかな？
Chez　Schemeの結果からアロケーションが結構発生するみたいだけど、それを踏まえてもありと思わせる結果である。

でも、これってこれらのVMがCPS変換されたコードを速く走らせるのであって、CPS変換されたコードが無条件で速くなるわけではないんだよなぁ・・・
う～ん・・・

CPS変換

とりあえず基本的なことを勉強してみた。
とにかく、すべてのλ抽象は次に計算される継続を持てばいいみたいで、こんな感じに変換される。
(この辺は知っていた・・・つもり)

; 変換前
(define (pyth x y)
  (sqrt (+ (* x x) (* y y))))
; 変換後
(define (pyth x y k)
  (* x x (lambda (x2)
    (* y y (lambda (y2)
      (+ x2 y2 (lambda (x2py2)
          (sqrt x2py2 k))))))))

CPS変換するとこうなる。プログラムは継続渡しスタイルなので、「*」、「+」といったプリミティブでさえ、引数に継続を取る。
ということは、継続を取る引数を定義しないといけない・・・
こんな感じ。

(define (cps/* x y k) (k (* x y)))
(define (cps/+ x y k) (k (+ x y)))
(define (cps/sqrt x k) (k (sqrt x)))

上記のプログラムの*、+及びsqrtをCPSなプリミティブに置き換えれば動く。面倒・・・

っで、これ見ると分かるのだが、継続渡しのプログラムは戻り値を次の継続に渡すので必然的に渡される継続の引数は1つに固定される。
引数を一つに固定して、あだこだするというと、カリー化が思い浮かぶが、やらにゃならんのだろうか・・・

とりあえず、用事ができたのでここまで。続きは帰ってきてから。

-----------------
帰ってきた。

引数を一つに固定したくないという思いをいただいたので(誰からだよ！)
継続の戻り値が多値なら問題ないかと。とりあえず、実験。

(define (cps/+ k . arg)(k (apply + arg)))
(call-with-values (lambda () (values (lambda (k) k) 1 2 3)) cps/+)

call-with-valuesが内部で何してるのか実はよく分かっていないが、動きから第二引数に第一引数の戻り値をapplyしてるのではないかと・・・
まぁ、どうでもいいや。
こう書けば一応複数の引数を何とかできそうだが、いいのか？
とりあえず、最初のプログラムを手動CPS変換してみる。

と思ったが、CPS変換で生じたλ抽象って、この場合だと(* x y)の戻り値を引数にするのだから、1つ固定でも問題ない気がする。もちろん、　(values 1 2)見たいな多値を返すんだとしたら問題かもしれないが、Schemeは多値をそのままでは扱えないので、やっぱり問題ない気がする。

例みたいな、defineをCPS変換する際には関係ないのだろう、きっと・・・