Scheme:Cへのトランスレート
Gaucheのページで出た以下のやりとり
なお、Cを介したネイティブコードへのcompileも視野の隅っこには入れています。 ただhobbitを使うかどうかは… Gaucheの中間コードコンパイラである程度の 最適化やフロー解析はやってしまう予定なので、そこからCへ落すほうが 素直なような。 --Shiro (2002/05/24 23:51:03 PDT)
に関する議論。
gcとのインタラクション
実行中のメモリイメージのダンプからではなくソースからのコンパイルならば、 認識するのはリテラルオブジェクトだけで良いような気も。 トップレベル処理(例えば、 (define *table* (make-hash-table)) みたいなの) は初期化ルーチンで走らせればいいわけですし。 それとも別のことを言っていますか? >> moxthさん --Shiro
moxthです。
ちょっと違うかもしれません。 以下は(map car l)をCへ変換したコードですが、consを一個所使ってます。 { pointer result = NIL; //戻り pointer g1 = l; pointer resultg1 = NIL; map1_g1: if (pairp(g1)) { resultg1 = cons(NIL, resultg1); if (!pairp(result))result = resultg1; car(resultg1) = car(car(g1)); g1 = cdr(g1); goto map1_g1; } } もしこのconsでgcが動いた場合、result,g1,resultg1の参照先が 保証されないのではないのか、って事でした。
ただ、後でよくよく考えると、gcで読みに行くスタックを設けて、 以下の様に変換すればそんなに煩雑にはならないかなと思いました。 (ref_stack[0...sp]までをgcの範囲に入れる)
{ int bp = sp; // ベースポインタを待避 sp += 3; //スタックを3つ使用する ref_stack[bp+0] = NIL; // pointer result = NIL; //戻り ref_stack[bp+1] = l; // pointer g1 = l; ref_stack[bp+2] = NIL; // pointer resultg1 = NIL; map1_g1: if (pairp(ref_stack[bp+1])) { ref_stack[bp+2] = cons(NIL, ref_stack[bp+2]); if (!pairp(ref_stack[bp+0]))ref_stack[bp+0] = ref_stack[bp+2]; car(ref_stack[bp+2]) = car(car(ref_stack[bp+1])); ref_stack[bp+1] = cdr(ref_stack[bp+1]); goto map1_g1; } sp = bp; // スタックを元に戻す //ref_stack[sp] が戻り値 } ただし、ローカル変数名をref_stack..の形に直す処理でもう一波乱、 ありそうな気がします。(ちょっと直しました。)
どうも。Shiroです。 なるほど、これはトランスレートされたCコードだけでなく、 Schemeから呼ばれるCコードに共通の問題ですね。
GCがスタックエリアやマシンレジスタを見てくれない実装の場合は、 Schemeオブジェクトを参照するCの一時変数を保護する必要があるでしょう。 stack scavenging conservative GC みたいにスタックエリアやマシンレジスタが 指しているアドレスも保護してくれるGCならほとんど何も気にしないで使えます。 Gaucheが使っているBoehm GCとか、SCMやGuileが使っているGCもこのタイプですね。
- mainの最初とgcのマークの所でローカル変数を取って、 その間をvoid*にキャストしてスキャンしてやればいい気も。 ってSCM等もたぶんそういう実装でしょうね。 レジスタ回りの為にsetjmp使うのも合わせてgcでは常套手段だと思います--有野
- いままで保守gcは、C言語の仕様(実際の言語の実装側からみたら妥当?)からかなりはみ出してる気がして、気持ち悪く感じてたんですが、この辺どうなんでしょうか。開き直った方が道は開けるでしょうか?unsafe-gcだとちょっとした気の緩みでバグが混入するのが怖い。(実際そういう対策を考えてない処理系を公開してるサイトがあった(笑いごとじゃねー・・)--moxth
- 保守gcはハック以外の何者でもないですね:-) 処理系の動作は未定義でしょうから、 何が起こっても不思議ではない。経験上、大抵はうまくゆくけれど、 例えば最適化によって生ポインタの値がレジスタ上に見えなくなったりする 問題がBoehmのページで指摘されてたと思います。そういう不確実さを排したい とするなら、保守gcはだめでしょうね。ミッションクリティカルな用途とか。 ただ、一度Boehm GCを使っちゃうとあまりの便利さに戻れなくなります --Shiro
- うーんやっぱりそうですか。例えばWindowsのコールバック越しに使った場合はどうなるとか、不安はありそうですね。スタックフレーム毎に参照の有無をgcに教えられる手段が あれば解決できそうですけど。これは一度使ってみて、それから考えてみることにします。お答えありがとうござます。--moxth
ネイティブコンパイル
gcとはまた別の話で、Cへの変換で問題になる事態がさらにいくつかありますよね。
- 解析処理なんかで多用する、関数の相互(末尾)再帰とか、継続そのものとか。
いっぺんに考えると頭痛いです。(笑
この辺はhobbitだと色々制限がある様です。
schemeはCとかの手続き型言語とは親和性低いのかな。 TinyBasicとかに逃げたくなります。--moxth
SICPを見てると、アセンブリの方がむしろ相性良いように見えます(^^;--有野
スタックレスな再帰の構想は思い浮かびますが、実装する段になるとなかなかむずかしい感じです。 相互末尾再帰、普通再帰と継続については状態退避と復帰でそれなりに組めそうな気がします。 粒度の荒いインタプリタの延長的なコードを吐かせるってイメージです。 自己末尾再帰系は引数付きgotoに展開できるなら全部やる、と。 ただこれ、Cコンパイラが別途必要ってのがどうにも引っかかってしまう。完全にCに変換できるケースって結構少ないでしょうし。 欲を言えば、いきなりオブジェクトコードをヒープに吐かせて動的に呼び出せれば一番いい。無茶な話だけど不可能じゃない(笑 結局、どれぐらいの時間をこれに割く事ができるか、ということかも。--moxth
処理系作成という観点から見ると、究極はそこになると思うんですね。それに1980年代くらいはそういう研究が盛んに行われてたと思いますし。論文を見ていると、ネイティブコンパイルならではのアイディアがたくさんあって悔しいですね。今残っているのはChezくらいですかねえ。--Shiro
現在、ネイティブコンパイラを自力で書こうとした場合の問題点は、「プロセッサの進化のスピードを考えると、チップメーカーや大手コンパイラベンダが出してくるコンパイラに速度面で勝つのはまず不可能だ」ということだと思います。GCCのフロントエンドを書くってのはありかもしれん。--Shiro
似たような事を考えてみましたが、こんな記事を見つけました。 RTL/tree (from gcc) and Scheme 今はどうなってるんだろ...2007/03/15
とりあえず基本的な変換についてのtipsなどを思いついたら追加していこうと思います。 --moxth
末尾再帰展開の問題
(let loop ((s "...")(si 0)(ei 0) (r '())) (if ... (loop s (+ si 1) (+ ei 1) (cons (substring s si ei) r)) ) )
こういったコードは引数付きgotoへ変換できます。 が、単純に変換するだけでは問題が出てきます。
{ pointer s = make_string("..."); int si = 0; int ei = 0; pointer r = NIL; loop: if (...) { si = si + 1; ei = ei + 1; r = cons(substring(s,si,ei),r); goto loop; } }
なぜか。この変換結果ではsi eiが先にインクリメントされるので、 substringで意味が変わってしまう。 一時変数を経由して、こうすると簡単に意味を保持できる。
if (...) { int tmp_si = si + 1; int tmp_ei = ei + 1; pointer tmp_r = cons(substring(s,si,ei),r); si = tmp_si; ei = tmp_ei; r = tmp_r; goto loop; }
ただし、各引数が互いに影響を及ぼさない場合は、一時変数を介する必要はない。 (rがこの場合に該当する)
if (...) { int tmp_si = si + 1; int tmp_ei = ei + 1; r = cons(substring(s,si,ei),r); si = tmp_si; ei = tmp_ei; goto loop; }
一時変数を経由させるのは機械的な変換でできますが、この「互いに影響を及ぼさない」という判定は、ちょっと面倒な解析が必要かも。--moxth
- 余分な一時変数の利用は、C compilerのoptimizerが後で取り除いてくれるのを当てにする、というのはだめですか --Shiro (2002/06/03 14:56:41 PDT)
- そうですね。特別に処理する内容としては、1引数の場合の切り分けや、sの様な変化しない物についてだけでよいかも。--moxth
letのbind順序
(let ((a 1)(b 2)(c 3)) (let ((a c)(b a)(c b)) (+ a b c))) =>6
これをそのまま変換すると問題発生です。
{ pointer a = make_number(1); pointer b = make_number(2); pointer c = make_number(3); { pointer a = c; pointer b = a; pointer c = b; result = a + b + c; } } resultは9になる。
これはC言語の変数宣言の右辺の初期化式がlet*のバインド順序になっているため。 こういう場合も一時変数を経由させる。
{ pointer tmp_a = c; pointer tmp_b = a; pointer tmp_c = b; { pointer a = tmp_c; pointer b = tmp_a; pointer c = tmp_b; result = a + b + c; } }
個人的には、こうやって一時変数を作っていくと、ブロックがやたらネストして 見苦しくなるんで、宣言部が続く場合、ブロックを取っ払う処理を思わず入れた くなります。上の例だとこんな感じの変換結果になるでしょう。
{ pointer a = make_number(1); pointer b = make_number(2); pointer c = make_number(3); pointer tmp_a = c; pointer tmp_b = a; pointer tmp_c = b; pointer a = tmp_c; pointer b = tmp_a; pointer c = tmp_b; result = a + b + c; }
しかし、このように同じ名前の変数が同一ブロック内に連続するとC言語では再定義 エラーとなるらしいので、この変換はローカル変数名のリストを参照しながら切り分 けるしかなさそうです。
{ pointer a = make_number(1); pointer b = make_number(2); pointer c = make_number(3); pointer tmp_a = c; pointer tmp_b = a; pointer tmp_c = b; { pointer a = tmp_c; pointer b = tmp_a; pointer c = tmp_b; result = a + b + c; } }
くだらない問題の割に長くなってしまいました。 --moxth2002/06/03 20:33:38 PDT
- 私が以前書いたScheme->C処理系では、Cへ落す変数はSchemeでの名前に_42 みたいな形で識別番号をつけて、スコープの違う変数は名前が衝突しないようにしていました。あと、「出来るだけSchemeコードの形をキープしたまま変換したい」というなら難しいですが、トランスレータは全ての変数を知っているわけなので、関数冒頭で全部の変数の宣言をやってしまうって手もあるのでは。--Shiro (2002/06/03 20:42:58 PDT)
- 単純に連番を付けるってのは手っ取り早くて良いですね。 冒頭部に宣言を集めるのは僕の頭ではちょっと難しそうです。 副作用無しで作れるかな?--moxth(2002/06/04 07:07:37 PDT)
この辺の作りって、どういう設計方針でやるかによってがらっと変わってくると思います。 例えば変数をブロックに置くべきか、自分の用意したスタックに入れていくかで、かなりの 変化がありそう。 最近自分なりに少し作り始めているんですが、結局やってる事はかなり行き当 たりばったりな方法です。適当に作って問題にぶち当たるの繰り返しというか。 運良く目的とうまく合致したら、とりあえずそれで推し進めていく。 この方法だと多分、数回は作り直す必要があるかと思います。 答えの幅が広すぎて、何が良い方法か?ってのがいまいちつかめない。 持ちまわりクロージャ関数や、継続切り替えの作りをどうするか、の根本部分をまだ本気 で考えてないってのもあるんですが。 副作用なしに多少こだわるのもその辺でなるべく制約を作りたくないためです。 現段階では、letの検証で(scheme->c '(let loop ...))みたいにしてそのままCコードの断片として適用できる様な出力を吐ければいいです。いまのところ組み込み関数を作る上での サポート的な役割程度はなんとか果たるかな?というレベルです。変換例--moxth(2002/06/04 07:07:37 PDT)
おじゃまします。ふと思ったんですが、 Lispならではの括弧のネストのレベルの数を添えた変数名を生成する、 ってのは意味ありますか? a_1とかc_3とか。 んでCの{}をそのネストレベルにあわせるように挿入すると、名前は衝突しないかなーと。 -戯