Scheme:Cへのトランスレート

Scheme:Cへのトランスレート

Gaucheのページで出た以下のやりとり

なお、Cを介したネイティブコードへのcompileも視野の隅っこには入れています。 ただhobbitを使うかどうかは… Gaucheの中間コードコンパイラである程度の 最適化やフロー解析はやってしまう予定なので、そこからCへ落すほうが 素直なような。 --Shiro (2002/05/24 23:51:03 PDT)

  • そのままCに変換するとgc回りで問題がでませんか? scheme-objectを作らない様な処理(検索系)ならいいんですけど。--moxth
  • 保守的gcでなければローカル変数が指してるobjectを全部認識させる様に作る 必要があるので面倒ですよね。--moxth

に関する議論。


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もこのタイプですね。


ネイティブコンパイル

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

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

この辺の作りって、どういう設計方針でやるかによってがらっと変わってくると思います。 例えば変数をブロックに置くべきか、自分の用意したスタックに入れていくかで、かなりの 変化がありそう。 最近自分なりに少し作り始めているんですが、結局やってる事はかなり行き当 たりばったりな方法です。適当に作って問題にぶち当たるの繰り返しというか。 運良く目的とうまく合致したら、とりあえずそれで推し進めていく。 この方法だと多分、数回は作り直す必要があるかと思います。 答えの幅が広すぎて、何が良い方法か?ってのがいまいちつかめない。 持ちまわりクロージャ関数や、継続切り替えの作りをどうするか、の根本部分をまだ本気 で考えてないってのもあるんですが。 副作用なしに多少こだわるのもその辺でなるべく制約を作りたくないためです。 現段階では、letの検証で(scheme->c '(let loop ...))みたいにしてそのままCコードの断片として適用できる様な出力を吐ければいいです。いまのところ組み込み関数を作る上での サポート的な役割程度はなんとか果たるかな?というレベルです。変換例--moxth(2002/06/04 07:07:37 PDT)

おじゃまします。ふと思ったんですが、 Lispならではの括弧のネストのレベルの数を添えた変数名を生成する、 ってのは意味ありますか? a_1とかc_3とか。 んでCの{}をそのネストレベルにあわせるように挿入すると、名前は衝突しないかなーと。 -戯

More ...