Scheme処理系をC++で書き始めた。
(実際は片付いてない問題が多々あるのだが・・・)
とりあえず、コードがVectorで構成されているのでVectorを。あと物が動くとやはりうれしいので、Fixnumなクラスを作成。
xyzzyの参考に(パチッてとも言う)、クラスのタグ付けとか、即値の判定とか作成。
っで、適当にごにょごにょして動かす。
(+ 1 2 3)をコンパイルした結果をC++のオブジェクトに置き換えたものが動いた。
説明が長い・・・
気になる点としては、現状だとコードはベクターの中にベクターが入れ子になるように作ってあるのだが、これだとメモリー効率が激しく悪い気がする。
Schemeで書いてるときは気にしなかったのだが、C++で書いてみると一つのコードを書くのにベクターの割り当てが激しく出てくる感じ。
コンパイラを書き換えて全部フラットにするべきだろうか・・・するべきなんだろうなぁ・・・
Syntax highlighter
2010-06-30
2010-06-24
ワールドカップ
日本が3-1でデンマークに勝った!!
何が起きてるんだろう?天変地異の前触れか?
どうでもいいが、ここオランダではサッカーがあるとえらいことになる。
僕の住んでるライデンにはちょっとした広場が街の中央にあるのだが、そこにパブリックビューがあって結構な人が集まっていた。
酒が飲めればいいのか、騒げればいいのか、純粋にサッカーが好きなのかどれなのかは分からないが、街中がやかましい。
噂によると、サッカーの観戦をするために仕事を病欠する人がいるそうだ。
そんな国。
何が起きてるんだろう?天変地異の前触れか?
どうでもいいが、ここオランダではサッカーがあるとえらいことになる。
僕の住んでるライデンにはちょっとした広場が街の中央にあるのだが、そこにパブリックビューがあって結構な人が集まっていた。
酒が飲めればいいのか、騒げればいいのか、純粋にサッカーが好きなのかどれなのかは分からないが、街中がやかましい。
噂によると、サッカーの観戦をするために仕事を病欠する人がいるそうだ。
そんな国。
2010-06-22
letのフレーム
A正規化の話だったりする。
たとえばこんなコード(変な数字が入ってるのはα変換後だから)
前回、継続周りで不具合が起きることを踏まえて、letが現れたらフレームを作るようにコンパイラとVMを修正したのだが、その影響で単なるたらいまわし関数がスタックオーバーフローを起こすようになった。
原因は、この大量のlet。これだけコードが増大すれば当然VMのインストラクションも増大する。どれだけ影響があるかスタックを1000から10000にして上記の関数でベンチマークをとってみた。
4秒が14秒に・・・orz
後の最適化がしやすいようにと思っての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正規化だが、ちょっとないなぁ・・・
今のところこいつの恩恵って、変数の寿命がわかりやすいことだけだし・・・
どうしよう。
2010-06-18
スタックポインタ、フレームポインタ
Schemeのコンパイラの話。
3impという論文のコンパイラを参考に作っているわけだが、スタックポインタとフレームポインタではまった。
(ってか、今でも解決してない)
ここにあるスタックとフレームの関係を参考にして、letのコンパイルをしたのだが、上手くいかない。
原因は分かっている。本来はletごとにフレームを作成して自由変数とかの解決をしないといけないのに、フレームを作るコストを嫌って、letが続く限り一つのローカルフレームのようにしたから。
そもそも、letではフレームを作ってないので、フレーム情報があることを前提にしているVMインストラクションでおかしなことが起きる。
どうしよう。
とりあえず、Gaucheがletをどう処理してるのかdisasmしてみた。
...
let毎にフレーム作ってる・・・
やっぱりそうするべきかなぁ?でもA正規化後ってあほかと思うほどletが増えるんだよなぁ・・・
その辺も踏まえてどうしよう。
3impという論文のコンパイラを参考に作っているわけだが、スタックポインタとフレームポインタではまった。
(ってか、今でも解決してない)
ここにあるスタックとフレームの関係を参考にして、letのコンパイルをしたのだが、上手くいかない。
原因は分かっている。本来はletごとにフレームを作成して自由変数とかの解決をしないといけないのに、フレームを作るコストを嫌って、letが続く限り一つのローカルフレームのようにしたから。
そもそも、letではフレームを作ってないので、フレーム情報があることを前提にしているVMインストラクションでおかしなことが起きる。
どうしよう。
とりあえず、Gaucheがletをどう処理してるのかdisasmしてみた。
...
let毎にフレーム作ってる・・・
やっぱりそうするべきかなぁ?でもA正規化後ってあほかと思うほどletが増えるんだよなぁ・・・
その辺も踏まえてどうしよう。
2010-06-15
コンパイル
いろいろ弄って、letをコンパイルできるようにした。
意外と上手くいくもんだ。四苦八苦したけど・・・
っで、たらいまわし関数を動かしてみたら、10,5,0の引数で36秒かかる・・・
まぁ、schemeをscheme上で動かしてるのでオーバーヘッドとかもあるだろう。っがあまりに遅いのでできそうな高速化を施すことに。
現状リストでVMのインストラクションを書いていたが、全部ベクターに変更。でも、面倒くさがりなので、
ベクターの中にベクターを入れるといういんちき(?)をして、データ構造は特に変更しない。
勢いあまってVMにプログラムカウンタをつけてみたけど、要らん気がする。まぁいいや。
これで、一時的に5倍くらい早くなった。
次にインストラクションを今後のために数値に変更。これは逆に遅くなった。
考えられそうな理由は現状プリミティブの実装がかなり適当で、シンボルと数値の比較が一つのcond文に混在している。なので、シンボルの比較を先にしないと、Gaucheに怒られた。っで先に回したら鈍足に・・・
比較の分だけ遅くなるわね。
逆に言えば、よく使われるインストラクションは前の方に持ってくると幸せになれるか?
っで、とりあえずプリミティブをいんちきせずにコンパイルするようにしている最中。
物が動いてくるとやはり楽しい。
意外と上手くいくもんだ。四苦八苦したけど・・・
っで、たらいまわし関数を動かしてみたら、10,5,0の引数で36秒かかる・・・
まぁ、schemeをscheme上で動かしてるのでオーバーヘッドとかもあるだろう。っがあまりに遅いのでできそうな高速化を施すことに。
現状リストでVMのインストラクションを書いていたが、全部ベクターに変更。でも、面倒くさがりなので、
ベクターの中にベクターを入れるといういんちき(?)をして、データ構造は特に変更しない。
勢いあまってVMにプログラムカウンタをつけてみたけど、要らん気がする。まぁいいや。
これで、一時的に5倍くらい早くなった。
次にインストラクションを今後のために数値に変更。これは逆に遅くなった。
考えられそうな理由は現状プリミティブの実装がかなり適当で、シンボルと数値の比較が一つのcond文に混在している。なので、シンボルの比較を先にしないと、Gaucheに怒られた。っで先に回したら鈍足に・・・
比較の分だけ遅くなるわね。
逆に言えば、よく使われるインストラクションは前の方に持ってくると幸せになれるか?
っで、とりあえずプリミティブをいんちきせずにコンパイルするようにしている最中。
物が動いてくるとやはり楽しい。
2010-06-14
カメルーンに勝った
ワールドカップの話。
職場が半日だれも仕事しないくらいオランダはサッカーが熱い(個人的にはどうでもいいが)
職場で点が入るたびに雄たけびが聞こえてくるくらい。
っで、それのあおりで日本VSカメルーンを少し見た。
あれ?勝ってる?
1-0で日本が勝った・・・
とりあえず、前評判を的確に表していたであろうコピペ。
う~ん、何が起きたんだろう?
職場が半日だれも仕事しないくらいオランダはサッカーが熱い(個人的にはどうでもいいが)
職場で点が入るたびに雄たけびが聞こえてくるくらい。
っで、それのあおりで日本VSカメルーンを少し見た。
あれ?勝ってる?
1-0で日本が勝った・・・
とりあえず、前評判を的確に表していたであろうコピペ。
A B 南アフリカ「ガチ抽選をした結果がこれだよ!」 アルゼンチン「なんだ楽勝じゃん」 メキシコ「南アフリカ乙」 ナイジェリア「2位ならなんとか」 ウルグアイ「南アフリカ乙」 韓国「\( ^o^)/」 フランス「実質シードワロスww」 ギリシャ「2位ならなんとか」 C D イングランド「アジアとやらせろよ」 ドイツ「そこそこの組み合わせかな」 アメリカ「微妙・・・」 オーストラリア「2位いけるな」 アルジェリア「無理くさい」 セルビア「2位いけるな」 スロベニア「微妙・・・」 ガーナ 「2位いけるな」 E F オランダ「まぁ、おk」 イタリア「楽勝www」 デンマーク「日本には勝つとして・・・」 パラグアイ「ニュージーには勝つ」 日本「なかなかいい組み合わせだな(キリッ」 ニュージーランド「なにこの無理ゲー?」 カメルーン「日本には勝つとして・・・」 スロバキア 「ニュージーには勝つ」 G H ブラジル「1位通過するよ」 スペイン「楽勝すぐるww」 北朝鮮「どうしてこうなった!」 スイス「ホンジュラスには勝つ」 コートジボワール「1位通過するよ」 ホンジュラス「まぁ、がんばる」 ポルトガル「1位通過するよ」 チリ 「ホンジュラスには勝つ」
う~ん、何が起きたんだろう?
ミーはおフランス帰りざんす
ということで、パリに行ってきました。
パッケージツアーというのは今までの人生でほとんど経験がないので(修学旅行等除く)それなりにいい経験になったかなと。
言葉の壁さえ考えなければ、交通費、朝食、夕食、セーヌ川のボートツアー、その他いろいろ混みで150ユーロは安いのではないかな。
パリの街は思っていた以上になじむなぁとちょっと感じた。
そこらじゅうで言われていた、犬の糞の問題は特になく、きれいだったし。
っが、街はきれいでも人は・・・
パリで運転する必要がある人はかなりの胆力が必要になるだろうなぁと。
時間がないので適当。
パッケージツアーというのは今までの人生でほとんど経験がないので(修学旅行等除く)それなりにいい経験になったかなと。
言葉の壁さえ考えなければ、交通費、朝食、夕食、セーヌ川のボートツアー、その他いろいろ混みで150ユーロは安いのではないかな。
パリの街は思っていた以上になじむなぁとちょっと感じた。
そこらじゅうで言われていた、犬の糞の問題は特になく、きれいだったし。
っが、街はきれいでも人は・・・
パリで運転する必要がある人はかなりの胆力が必要になるだろうなぁと。
時間がないので適当。
2010-06-09
やっつけA正規形拡張
とりあえず、オリジナルのA正規形で問題かなと思ったのが以下の点。
1. letが変数一つって扱い難いので複数取るように変更。(let (<binds>) <body>)というが普通のletなのでこれを取るようにし、<binds>の(変数 値)という式を一つずつ正規化後letを再構築。
2. condは
letrecとletrec*はバインド変数だけ正規化してそのまま放置。とりあえずこれでいいか?
3. オリジナルは(display 'a)というのが(let ((r 'a)) (display r))ってなってたので、さすがにあほらしいかと思い、quoteは正規化しないことにした。
っで、とりあえず3impのコンパイラでコンパイルしてみた。
おぉ、コンパイルできた。
っが、コンパイラにletをコンパイルする記述はない・・・さて、考えるか・・・
- letが引数一つ
- cond、letrec等の必要そうな構文がない(condはif文で書きかえれるけど・・・)
- 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をコンパイルする記述はない・・・さて、考えるか・・・
2010-06-08
A正規形に切り替える
CPS変換がどうにも上手くいかない。
なんとかなるんだろうけど、涙が出そうになってきたので断念。
一応、それ以外の理由として、
(Gauche上で動かしてるのでしょうがない)
ということで、A正規形に切り替えることにする。
A正規形はCPS変換後逆CPS変換した形に極めて近い気がする。すべての継続の結果を変数として確保するので、スタックの肥大化が問題かな?
ここが詳しい。別に論文も読むといいと思う。
論文の最後にアルゴリズムをschemeで実装した例がある。
問題はこいつはCore SchemeというSchemeのサブセットを対象としているので、いろんな部分で限定的。(letrecとかないし・・・condとかどうするんだろう?)
その辺りを自前で拡張することができればよさそうだ。できるかな?
なんとかなるんだろうけど、涙が出そうになってきたので断念。
一応、それ以外の理由として、
- コードの肥大化がすさまじい
- 変換することによって、関数のシグネチャが変わる(継続を渡すように変更するため)
- ベンチマークで脅威の低速を叩き出してる
(Gauche上で動かしてるのでしょうがない)
ということで、A正規形に切り替えることにする。
A正規形はCPS変換後逆CPS変換した形に極めて近い気がする。すべての継続の結果を変数として確保するので、スタックの肥大化が問題かな?
ここが詳しい。別に論文も読むといいと思う。
論文の最後にアルゴリズムをschemeで実装した例がある。
問題はこいつはCore SchemeというSchemeのサブセットを対象としているので、いろんな部分で限定的。(letrecとかないし・・・condとかどうするんだろう?)
その辺りを自前で拡張することができればよさそうだ。できるかな?
2010-06-07
コメントの仕方
コメントの仕方が分からないという指摘が累計2件ほどたまったので(少ない)
蛇足ではあると思うけど書いてみる。
コメントしたいと思う投稿の一番下にある、数字 + コメントという(このブログだと緑)のリンクをクリックする。
するとなんとも味気ないコメント投稿画面が現れるので、大き目のテキストエリアにコメントを書き込む。
スパム防止機能があるので、コメントのテキストエリアの下にあるフィールドに画像の英数字を入力。
投稿者のIDを選択。OpenIDはよく分かっていないが、Googleアカウントがあればそれでもいいし、そんなもの無いなら名前/URLを選択し名前を入力。もちろん匿名でも構わない。
最後に投稿ボタンを押せば完了。
bloggerのコメントはきっと共通だと思うので、これで他のbloggerにもコメントができる!
さぁ、早速この投稿にコメントして練習だ!
蛇足ではあると思うけど書いてみる。
コメントしたいと思う投稿の一番下にある、数字 + コメントという(このブログだと緑)のリンクをクリックする。
するとなんとも味気ないコメント投稿画面が現れるので、大き目のテキストエリアにコメントを書き込む。
スパム防止機能があるので、コメントのテキストエリアの下にあるフィールドに画像の英数字を入力。
投稿者のIDを選択。OpenIDはよく分かっていないが、Googleアカウントがあればそれでもいいし、そんなもの無いなら名前/URLを選択し名前を入力。もちろん匿名でも構わない。
最後に投稿ボタンを押せば完了。
bloggerのコメントはきっと共通だと思うので、これで他のbloggerにもコメントができる!
さぁ、早速この投稿にコメントして練習だ!
2010-06-03
ぬか喜びだった件・・・
前述のベンチマークだが、手動CPS変換が間違っていた。
正しくはこう
どう考えてもなしの方向っぽいです、本当に(ry
正しくはこう
(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正規化すればいいのでは?
という誘惑にかられたことから、ちょっとベンチマークとってみた。
(どっちが速度が出るか比較したかった。速い方がいいじゃん!)
使用したコードは以下
Gaucheのdisasm関数でコンパイル結果を見てみたが、末尾最適化が効いてるのかな?
Chez Schemeの結果からアロケーションが結構発生するみたいだけど、それを踏まえてもありと思わせる結果である。
でも、これってこれらのVMがCPS変換されたコードを速く走らせるのであって、CPS変換されたコードが無条件で速くなるわけではないんだよなぁ・・・
う~ん・・・
ひょっとして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変換されたコードが無条件で速くなるわけではないんだよなぁ・・・
う~ん・・・
2010-06-01
CPS変換
とりあえず基本的なことを勉強してみた。
とにかく、すべてのλ抽象は次に計算される継続を持てばいいみたいで、こんな感じに変換される。
(この辺は知っていた・・・つもり)
ということは、継続を取る引数を定義しないといけない・・・
こんな感じ。
っで、これ見ると分かるのだが、継続渡しのプログラムは戻り値を次の継続に渡すので必然的に渡される継続の引数は1つに固定される。
引数を一つに固定して、あだこだするというと、カリー化が思い浮かぶが、やらにゃならんのだろうか・・・
とりあえず、用事ができたのでここまで。続きは帰ってきてから。
-----------------
帰ってきた。
引数を一つに固定したくないという思いをいただいたので(誰からだよ!)
継続の戻り値が多値なら問題ないかと。とりあえず、実験。
まぁ、どうでもいいや。
こう書けば一応複数の引数を何とかできそうだが、いいのか?
とりあえず、最初のプログラムを手動CPS変換してみる。
と思ったが、CPS変換で生じたλ抽象って、この場合だと(* x y)の戻り値を引数にするのだから、1つ固定でも問題ない気がする。もちろん、 (values 1 2)見たいな多値を返すんだとしたら問題かもしれないが、Schemeは多値をそのままでは扱えないので、やっぱり問題ない気がする。
例みたいな、defineを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変換する際には関係ないのだろう、きっと・・・
2010-05-30
ラムダ計算 入門
SchemeでSchemeのコンパイラを作っているのだが、いろいろやるに当たって必要になったので勉強中。
(泥縄とかそういう突っ込みはいらない)
ラムダ計算入門のPDFが分かりやすかったのでこれを元に入門編を勉強。
とりあえずラムダ計算の定義。
Schemeで変数を定義するときにlet式を使うが、let式もlambdaに変換できる。
(SICPで出たが復習)
(let ((x 1)) <body>) -> ((lambda (x) <body>) 1)
λ式に対して関数適用をするといった感じ?
β簡約
いくつかやり方があるらしい。とりあえず資料にあったのは、R-Beta、R-App1、R-App2とR-Absの4つ。
じゃあ、正確には[c/a]bdじゃないのだろうかと、ちと疑問。
例は資料になかったので自分で考えた。間違い指摘大歓迎!!
α変換
変数名を一意に変換すること。こんな感じ(まんま資料から)。
(λx.λy.xy)y -α変換-> (λx.λy'.xy')y -β簡約-> λy'.yy'
最初の式のyと適用されるyは異なる変数だが同名がつけられている。このまま簡約すると式の意味が変わるので変数名を変えようというだけの話。
仰々しい名前が着いてるけど、変数名の衝突を防ぐだけ・・・
とりあえず、入門の入門としてはこれくらいにする。
1時間の勉強内容としてはこんなもんだろう・・・
最終的にはSabry&WadlerのCPS変換の実装をSchemeでできるまでには習得したい・・・
(泥縄とかそういう突っ込みはいらない)
ラムダ計算入門のPDFが分かりやすかったのでこれを元に入門編を勉強。
とりあえずラムダ計算の定義。
e(λ式) ::= x (変数) | λx.e (λ抽象) | e1e2 (関数適用)この辺は余裕。
Schemeで変数を定義するときにlet式を使うが、let式もlambdaに変換できる。
(SICPで出たが復習)
(let ((x 1)) <body>) -> ((lambda (x) <body>) 1)
λ式に対して関数適用をするといった感じ?
β簡約
いくつかやり方があるらしい。とりあえず資料にあったのは、R-Beta、R-App1、R-App2とR-Absの4つ。
R-Beta: -------------------------- (λx.e1)e2 -> [e2/x]e1 例: (λx.x)y -> y (λx.λy.x)z -> λy.z[e2/x]e1はe1の変数xにe2を代入したという意味。
R-App1: e1 -> e1' ----------------- e1e2 -> e1'e2 例: (λa.b)cd -> bdλ式は左結合なので、(λa.b)cdは実際は((λa.b)c)dとなる。R-Betaで(λa.b)cが[c/a]bになって、このbに対してdを適用するということ。
じゃあ、正確には[c/a]bdじゃないのだろうかと、ちと疑問。
R-App2: e2 -> e2' ----------------- e1e2 -> e1e2' 例: a((λx.x)b) -> abR-App2はR-App1のe2版。つまり引数に対してβ簡約をするということ。
例は資料になかったので自分で考えた。間違い指摘大歓迎!!
R-Abs: e -> e' ------------------- λx.e -> λx.e' 例: λx.(λy.y)x -> λx.xλ抽象に対しての簡約。実行時に関数を評価するMLでは必要ないらしい。でも、簡約=最適化だとすればコンパイル時に評価しなくてもいいので、簡約はしておきたいなぁ。ということでこれも必要としておこう。
α変換
変数名を一意に変換すること。こんな感じ(まんま資料から)。
(λx.λy.xy)y -α変換-> (λx.λy'.xy')y -β簡約-> λy'.yy'
最初の式のyと適用されるyは異なる変数だが同名がつけられている。このまま簡約すると式の意味が変わるので変数名を変えようというだけの話。
仰々しい名前が着いてるけど、変数名の衝突を防ぐだけ・・・
とりあえず、入門の入門としてはこれくらいにする。
1時間の勉強内容としてはこんなもんだろう・・・
最終的にはSabry&WadlerのCPS変換の実装をSchemeでできるまでには習得したい・・・
2010-05-23
New York最終日
書いてる時間がおかしいが、まぁ無事に帰ってきた後ということで^^;
特に何もない、実は(じゃあ書くなよ)
飛行場の近くにあるモールでランチ取っただけという話。
飛行場はNewarkという飛行場。なんとも紛らわしい名前だ。
んでもって、あほかというほど混んでた。
飛行場でいつも気になるのは、清掃のおばちゃんじゃないけど、係員みたいな人は大抵アメリカ人じゃない発音の英語を話すこと。
大抵インド系かスペイン系。
そういえばタクシーの運ちゃんとかバスの運ちゃんもスペイン系が多かったなぁ。
この辺りは移民が着く仕事なんだろうか?
帰りの飛行機は特に問題なく7時間弱で到着。
特に時差ぼけも無く、普通のフライトだった。
どうでもいいが、今回の旅行で分かったことがある。
僕は英語が話せない・・・(T_T)
特に何もない、実は(じゃあ書くなよ)
飛行場の近くにあるモールでランチ取っただけという話。
飛行場はNewarkという飛行場。なんとも紛らわしい名前だ。
んでもって、あほかというほど混んでた。
飛行場でいつも気になるのは、清掃のおばちゃんじゃないけど、係員みたいな人は大抵アメリカ人じゃない発音の英語を話すこと。
大抵インド系かスペイン系。
そういえばタクシーの運ちゃんとかバスの運ちゃんもスペイン系が多かったなぁ。
この辺りは移民が着く仕事なんだろうか?
帰りの飛行機は特に問題なく7時間弱で到着。
特に時差ぼけも無く、普通のフライトだった。
どうでもいいが、今回の旅行で分かったことがある。
僕は英語が話せない・・・(T_T)
2010-05-21
New York四日目
四日目もニューヨーク。
今日はツアーバスには乗らずいろいろぶらぶら。
といっても、あんまりどこにも行ってないなぁ。
お茶して、
自由の女神をフェリーから見て、
セントラルパークで(大分遅い)昼食をとって(17時)、
チャイナタウンで買い物して、
終了。
セントラルパークはかなりいい感じの公園だった。
都会の雑踏を完全に忘れることができるというか、まぁそんな感じ。
しかも、やたらでかい!
もう来ることはないと思うが、もし機会があればレンタル自転車で一周してみたいなぁ。
今日はツアーバスには乗らずいろいろぶらぶら。
といっても、あんまりどこにも行ってないなぁ。
お茶して、
自由の女神をフェリーから見て、
セントラルパークで(大分遅い)昼食をとって(17時)、
チャイナタウンで買い物して、
終了。
セントラルパークはかなりいい感じの公園だった。
都会の雑踏を完全に忘れることができるというか、まぁそんな感じ。
しかも、やたらでかい!
もう来ることはないと思うが、もし機会があればレンタル自転車で一周してみたいなぁ。
2010-05-20
New York三日目
今日もNew York。
New YorkというかManhattanは基本的に3つの地域(?)から成り立つっぽい。
Uptown、MidtownそれにDowntownの3つ。DowntownにはWall Streetとか経済の中心っぽいところがあり、UptownはHarlemとか居住地っぽい感じ。
個人的にHarlemって聞くとスラム街ってイメージがあったのだが、それは今や昔の話で今は(バスのガイドさんの話によると)完全に安全らしい。
どうでもいいのだがUptownにはコロンビア大学があり、コロンビア大学というとシヴァ、アレクサンドライトなどの漫画が思い浮かぶ。
(浮かぶ人の方が少ないだろう上に、20年近く前の漫画だったりする)
個人的に、あの漫画のManhattan描写はなんだかいろいろ違うような気が今更ながらにしたが、20年くらい前なので当時はそうだったのかもしれない。どうでもいい話。
ちなみに、コロンビア大学はもっとも学費が高い私立大学の一つらしい。っで、同じくManhattanにあるニューヨーク大学は年間5万ドル(500万円くらい?)ほどするらしい。漫画の中の話とは言え、彼らはものすごく金持ちだったのだろう・・・
そんなことを考えながら観光バスのUptownツアーを終了し、タイムズスクエアに戻る。っで、何故か吉野家で昼食。
味はまぁまぁだったのだが、なぜ吉野家に寿司があるんだろう?
その後Downtownツアーのバスに乗り、ナイトツアーでManhattan → Brooklyn → Manhattanと移動。無いとツアーのガイドのおっさんがやたら面白い人だった。
ちょっとだけこの街に慣れてきた気がするが、やはり肌に合わない・・・
New YorkというかManhattanは基本的に3つの地域(?)から成り立つっぽい。
Uptown、MidtownそれにDowntownの3つ。DowntownにはWall Streetとか経済の中心っぽいところがあり、UptownはHarlemとか居住地っぽい感じ。
個人的にHarlemって聞くとスラム街ってイメージがあったのだが、それは今や昔の話で今は(バスのガイドさんの話によると)完全に安全らしい。
どうでもいいのだがUptownにはコロンビア大学があり、コロンビア大学というとシヴァ、アレクサンドライトなどの漫画が思い浮かぶ。
(浮かぶ人の方が少ないだろう上に、20年近く前の漫画だったりする)
個人的に、あの漫画のManhattan描写はなんだかいろいろ違うような気が今更ながらにしたが、20年くらい前なので当時はそうだったのかもしれない。どうでもいい話。
ちなみに、コロンビア大学はもっとも学費が高い私立大学の一つらしい。っで、同じくManhattanにあるニューヨーク大学は年間5万ドル(500万円くらい?)ほどするらしい。漫画の中の話とは言え、彼らはものすごく金持ちだったのだろう・・・
そんなことを考えながら観光バスのUptownツアーを終了し、タイムズスクエアに戻る。っで、何故か吉野家で昼食。
味はまぁまぁだったのだが、なぜ吉野家に寿司があるんだろう?
その後Downtownツアーのバスに乗り、ナイトツアーでManhattan → Brooklyn → Manhattanと移動。無いとツアーのガイドのおっさんがやたら面白い人だった。
ちょっとだけこの街に慣れてきた気がするが、やはり肌に合わない・・・
2010-05-19
New York二日目
今日は普通の時間に起きたのでそれなりに元気。
ホテルで朝食を取ってシャトルバスでManhattanへ。
あいにくの雨なので適当にぶらぶら。
(セントラルパークとか行ってみたいところはあるのだが、雨だしやめた。明日)
タイムススクエアとかそれっぽいとこを見た感じ。
48時間乗り降り自由の観光バスのチケットを買い、それに乗って時間をつぶす。
雨なので説明を聞いてもそれそのものは見えない・・・
無駄金払った気分orz
明日があるさ!
そんな感じでとりあえず二日目終了。
ホテルで朝食を取ってシャトルバスでManhattanへ。
あいにくの雨なので適当にぶらぶら。
(セントラルパークとか行ってみたいところはあるのだが、雨だしやめた。明日)
タイムススクエアとかそれっぽいとこを見た感じ。
48時間乗り降り自由の観光バスのチケットを買い、それに乗って時間をつぶす。
雨なので説明を聞いてもそれそのものは見えない・・・
無駄金払った気分orz
明日があるさ!
そんな感じでとりあえず二日目終了。
2010-05-18
New York一日目
無事に飛行機に乗れ、無事にNew Yorkに到着。
実際にはNew Jerseyだったりするが、まぁ主に活動するところはNew Yorkになるので細かいことは気にしない。
とりあえず、今日も4時おきだったりするので、ホテルに到着し次第爆睡・・・
う~ん。
飛行場からホテルまでまぁ距離があって、電車に乗る必要があったのだが、その車窓から覗いた世界がなんだかセピア色だった。
う~ん、とりあえずすでに自分になじまないなぁという雰囲気が漂っている・・・
実際にはNew Jerseyだったりするが、まぁ主に活動するところはNew Yorkになるので細かいことは気にしない。
とりあえず、今日も4時おきだったりするので、ホテルに到着し次第爆睡・・・
う~ん。
飛行場からホテルまでまぁ距離があって、電車に乗る必要があったのだが、その車窓から覗いた世界がなんだかセピア色だった。
う~ん、とりあえずすでに自分になじまないなぁという雰囲気が漂っている・・・
2010-05-17
Orlandおまけ
Orlandoを出発する予定だったのだが、いろいろあって飛行機に乗れなかった・・・
ということで、おまけの一日。
朝4時起きという超睡眠不足に加えて連日の疲れから何もできなかったけど・・・
とりあえず、シーワールドに行っておしまい。
明日は本当にNew Yorkのはず・・・
ということで、おまけの一日。
朝4時起きという超睡眠不足に加えて連日の疲れから何もできなかったけど・・・
とりあえず、シーワールドに行っておしまい。
明日は本当にNew Yorkのはず・・・
Subscribe to:
Posts (Atom)