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変換する際には関係ないのだろう、きっと・・・