Ads by Google
新しい記事を書く事で広告が消せます。
疲れたよ…
来る日も来る日も，コンパイラが生成した，ほとんどアセンブリみたいな C 言語とにらめっこしつつ，バグを取る日々．そりゃぁ，精神も荒廃してきますよ．日記が壊れ気味でも気にしてはいけにゃい．
今日は，length とかをコンパイルしてみた．これは，末尾再帰ではなく，再帰を使わざるを得ない例題，という難しさがあるの〜．
// (length *リスト *リストの長さ)
(length () *N) --> (= *N 0).
(length (? | *Xs) *N) --> (length *Xs *N1), (:= *N (+ *N1 1)).
そうすると，問題は，今までのように goto だけでは上手くいかないのである．スタックかどっかに戻り番地を確保しておいて，処理が終わったら，終わったところから元の場所 (これが，いわゆる，アセンブリ言語のレベルでの，継続 continuation という値の正体．高級言語になればなるほど，もっといろいろな実行時の環境 (コンテキスト)情報が増える) まで飛んで処理を再開しないといけない．
しっかし，戻ってくるところのアドレスなんて，C みたいな高級言語からは，ポータブルには取れっこないよなぁ…
# ETI レベルでは，どこまでプリミティブにプログラム変換しようとも限界があり，ここまで低水準なところにはもともと触れないので，問題が表面化しない．
というわけで，今のところは，本当に関数を再帰呼び出しているのですが…
この方法だと，複数のお互いに呼び合う D ルールを，一つの巨大な C 関数に無理矢理融合変換，関数呼び出しなんて無し，内部で直接 goto でぐるぐる回りまくる，とかいうコンパイルができなくなるとか，いろいろと問題が．
GCC なんかだと，
みたいな，いろいろと無理があることを強引にすれば，なんとかなるかも．
5.3 Labels as Values
(このときの C スタックやら実行時コンテキストを setjmp かなんかで，どっかに丸ごと保存しておいて，&&LABEL といっしょにクローズしておけば，継続オブジェクトとかができる… のかもしれない．よく知らない．setjmp/longjmp とかもあんまり使ったことないし…)
もはや C 言語でも何でも無い ！
関数を超えたジャンプも余裕．ダイクストラ先生もびっくりだ．
というか，無理やり，関数呼び出しという C 言語の構造化言語としての枠組みを使わないで，ネイティブコンパイラを書いたほうが楽なことっていっぱいあるんだよなぁ… でもポータビリティが無くなり過ぎるし，いまどきの CPU のレジスタ割り当てとかパイプライニングとかは，もう素人じゃどうしようもないレベルだし．やっぱり，C の歴史とポータビリティとベンダー提供の超絶コンパイラは捨てがたい．C-- とか良く知らないだけですけど…
それにしても，値としてラベルを使うことができる GCC は偉いよ．C って，やっぱり，いまいち中途半端に高級なんだよなぁ．リターンアドレスぐらい触らせてくれ〜 スタックフレーム弄らせてくれ〜 これぐらい標準化してくれ ！！ ていぅか関数呼び出しによる構造化なんていらねーよー 本当に，単なるポータブルなアセンブリ言語だったら良かったのに (無茶苦茶)
(いろいろ毒されてきて，もはや関数型どころか，構造化プログラミングすらどうでもよくなってきている管理人)
今日は，length とかをコンパイルしてみた．これは，末尾再帰ではなく，再帰を使わざるを得ない例題，という難しさがあるの〜．
// (length *リスト *リストの長さ)
(length () *N) --> (= *N 0).
(length (? | *Xs) *N) --> (length *Xs *N1), (:= *N (+ *N1 1)).
そうすると，問題は，今までのように goto だけでは上手くいかないのである．スタックかどっかに戻り番地を確保しておいて，処理が終わったら，終わったところから元の場所 (これが，いわゆる，アセンブリ言語のレベルでの，継続 continuation という値の正体．高級言語になればなるほど，もっといろいろな実行時の環境 (コンテキスト)情報が増える) まで飛んで処理を再開しないといけない．
スタック (ワード配列) に順番に引数積む;
ベース値を適切に書き換える;
(ベース + n が，n 番目のローカル変数のインデクスになる．テキトーに，スタック配列の 1 番目とかに確保してる．0 番目には現在のスタックの長さが入っている．スタックフレームの構造はいろいろ変わるかも．今はかなりテキトー)
goto length; // サブルーチンの最初に戻る．
次にここに戻ってきて，ここから処理を再開しないといけない．
しっかし，戻ってくるところのアドレスなんて，C みたいな高級言語からは，ポータブルには取れっこないよなぁ…
# ETI レベルでは，どこまでプリミティブにプログラム変換しようとも限界があり，ここまで低水準なところにはもともと触れないので，問題が表面化しない．
というわけで，今のところは，本当に関数を再帰呼び出しているのですが…
この方法だと，複数のお互いに呼び合う D ルールを，一つの巨大な C 関数に無理矢理融合変換，関数呼び出しなんて無し，内部で直接 goto でぐるぐる回りまくる，とかいうコンパイルができなくなるとか，いろいろと問題が．
GCC なんかだと，
bool
func(word stack[], word mem[]) {
．．．
dokka :
なんか処理;
goto (void *)stack[retValueIndex];
← 今ここをプログラムカウンタが指しているとする;
引数積む;
ワード配列に，無理やり void * を詰め込む;
stack[retValueIndex] = (word)&&continuationLABEL;
スタックポインタずらす．
goto dokka;
continuationLABEL :
継続処理;
...
}
みたいな，いろいろと無理があることを強引にすれば，なんとかなるかも．
5.3 Labels as Values
(このときの C スタックやら実行時コンテキストを setjmp かなんかで，どっかに丸ごと保存しておいて，&&LABEL といっしょにクローズしておけば，継続オブジェクトとかができる… のかもしれない．よく知らない．setjmp/longjmp とかもあんまり使ったことないし…)
もはや C 言語でも何でも無い ！
関数を超えたジャンプも余裕．ダイクストラ先生もびっくりだ．
というか，無理やり，関数呼び出しという C 言語の構造化言語としての枠組みを使わないで，ネイティブコンパイラを書いたほうが楽なことっていっぱいあるんだよなぁ… でもポータビリティが無くなり過ぎるし，いまどきの CPU のレジスタ割り当てとかパイプライニングとかは，もう素人じゃどうしようもないレベルだし．やっぱり，C の歴史とポータビリティとベンダー提供の超絶コンパイラは捨てがたい．C-- とか良く知らないだけですけど…
それにしても，値としてラベルを使うことができる GCC は偉いよ．C って，やっぱり，いまいち中途半端に高級なんだよなぁ．リターンアドレスぐらい触らせてくれ〜 スタックフレーム弄らせてくれ〜 これぐらい標準化してくれ ！！ ていぅか関数呼び出しによる構造化なんていらねーよー 本当に，単なるポータブルなアセンブリ言語だったら良かったのに (無茶苦茶)
(いろいろ毒されてきて，もはや関数型どころか，構造化プログラミングすらどうでもよくなってきている管理人)
コメント
setjmp() は何でも出来る魔法の関数っすよ。
setjmp()だけだとレジスタしか保存してくれないから、スタックさえどこぞに保存しておけば、それだけで継続だろうがマイクロスレッドだろうが・・・・
ふがふが
setjmp()だけだとレジスタしか保存してくれないから、スタックさえどこぞに保存しておけば、それだけで継続だろうがマイクロスレッドだろうが・・・・
ふがふが
> kosaki さん
ちょうど今，「はじめて読む 486」の，「プロセス管理 - タスク切り替えの実現方法」のところを読んで，うほっ と思っていたところでした．タイムリーなコメントですねぇ．
なんか，たまに Ruby とか Scheme とか JavaScript とかの，超高級言語使いの人達が，継続とかコルーチンとか yield とかマイクロスレッドとか騒いでますが，CPU の世界ではごく普通のことなんですよねぇ．
一通りいろんな言語を試した後は，やっぱり生機械語とレジスタの，男の世界を体験しておくべきだと思いました．
エリックレイモンドも，「毎年一つ，新しい CPU を学ぶべき」 と言っていますし (ぇ
# 「毎年一個言語」が許されるのならば，アセンブリ言語だって許されるのではないか ? 世の中の高級言語の数よりも，CPU の数の方が少ないじゃないか ！ と半分マジで思っている管理人．まぁ，つまり「プログラミングを独習するには10年かかる」という話．
http://www.yamdas.org/column/technique/21-daysj.html
まとめると，C 言語は，カリー化したり，クロージャとか作れたり，コルイーチンもサポートしていて，継続も取れて，処理の yield もマイクロスレッディングもできる魔法の言語ということで．
http://d.hatena.ne.jp/w_o/20060808#p2
なんか，たまに Ruby とか Scheme とか JavaScript とかの，超高級言語使いの人達が，継続とかコルーチンとか yield とかマイクロスレッドとか騒いでますが，CPU の世界ではごく普通のことなんですよねぇ．
一通りいろんな言語を試した後は，やっぱり生機械語とレジスタの，男の世界を体験しておくべきだと思いました．
エリックレイモンドも，「毎年一つ，新しい CPU を学ぶべき」 と言っていますし (ぇ
# 「毎年一個言語」が許されるのならば，アセンブリ言語だって許されるのではないか ? 世の中の高級言語の数よりも，CPU の数の方が少ないじゃないか ！ と半分マジで思っている管理人．まぁ，つまり「プログラミングを独習するには10年かかる」という話．
http://www.yamdas.org/column/technique/21-daysj.html
まとめると，C 言語は，カリー化したり，クロージャとか作れたり，コルイーチンもサポートしていて，継続も取れて，処理の yield もマイクロスレッディングもできる魔法の言語ということで．
http://d.hatena.ne.jp/w_o/20060808#p2
> h_sakurai さん
おー，なるほど．これは面白い記事ですね．
私の場合は，機械的にこういう C コードを自動生成することを前提としているので，構造体みたいなものは一切使わず，単なる整数配列に何でも間でもぶち込んでますが，ちゃんとやるとこういう風になると思います．
こういう凄い人が手書きしたのと同じレベルのコードが出せたら最高なんですが… (^^;
私の中では word (unsigned int) と void * は同じものなんですが，堕落レベル 2 ですな ｗ
http://d.hatena.ne.jp/w_o/20060808#p3
# Ruby は unsigned long (ほとんどの環境では，sizeof(int) == sizeof(long) のはず) ≧ ポインタを仮定していたような… ?
ちゃんとやるならば上記サイトのように union か，C99 の uintptr_t 型を使ってやるべきですよね．
他にも UTF のエンディアンやらなにやら 32 bit LE 決め打ちだらけで移植性ゼロなので，そこらへんもちゃんとしてかないといけませんね．
GCC の独自拡張を使ってしまうか，もっとポータブルなやり方 (ぶっちゃけ，GCC と インテル純正の ICC で動けば，私的には満足なんですが ｗ) でやるべきなのかは，追々ということで．
とりあえず今は，ボスに報告する，進捗状況のネタができたので，ほっとしているところです．
私の場合は，機械的にこういう C コードを自動生成することを前提としているので，構造体みたいなものは一切使わず，単なる整数配列に何でも間でもぶち込んでますが，ちゃんとやるとこういう風になると思います．
こういう凄い人が手書きしたのと同じレベルのコードが出せたら最高なんですが… (^^;
私の中では word (unsigned int) と void * は同じものなんですが，堕落レベル 2 ですな ｗ
http://d.hatena.ne.jp/w_o/20060808#p3
# Ruby は unsigned long (ほとんどの環境では，sizeof(int) == sizeof(long) のはず) ≧ ポインタを仮定していたような… ?
ちゃんとやるならば上記サイトのように union か，C99 の uintptr_t 型を使ってやるべきですよね．
他にも UTF のエンディアンやらなにやら 32 bit LE 決め打ちだらけで移植性ゼロなので，そこらへんもちゃんとしてかないといけませんね．
GCC の独自拡張を使ってしまうか，もっとポータブルなやり方 (ぶっちゃけ，GCC と インテル純正の ICC で動けば，私的には満足なんですが ｗ) でやるべきなのかは，追々ということで．
とりあえず今は，ボスに報告する，進捗状況のネタができたので，ほっとしているところです．
すでにすごい人たちがすごい回答を書いているので、匿名に…。
標準Cだけでやるには、while と switch case を使う！！
わざと末尾再起しない再起関数を
int length(char* c)
{
if( *(c+1) != 0 ){
return length(c+1)+1;
}else{
return 1;
}
}
見たいなのを、あろはさんのコンパイラで、コンパイルすると、
#include <stdio.h>
unsigned int stack[1024];
#define PUSH(x) sp++; *sp = (x);
#define POP(x) x = *sp ; sp--;
#define PUSHCH(x) sp++; *sp = (unsigned int)(x);
#define POPCH(x) x = (char*)*sp ; sp--;
int length(char* c)
{
// context initialize
int reg1, pc;
unsigned int* sp;
sp = stack;
reg1 = 0;
pc = 0;
// int length(char* c) {
PUSHCH(c);
PUSH(255);
while(1){
switch(pc){
case 0:
length_re:
c = (char*)*(sp-1);
/* if ( *(c+1)!= 0 ){/*
if( *(c+1) == 0 )
goto ELSE;
/* return length(c+1)+1; */
c++;
PUSHCH(c);
PUSH(1);
goto length_re;
case 1:
POP(reg1);
POP(pc);
sp--;
PUSH(reg1+1);
break;
/* }else{ */
ELSE:
//return 1;
POP(pc);
sp--;
PUSH(1)
break;
/*}*/
default:
goto OUT;
}
}
OUT:
POP(reg1);
return reg1;
}
int main(int argc, char** argv)
{
printf("%d\n",length("AAAA"));
}
見たいになると、goto と、末尾再起でない再起が混在できますです。ハイ！
標準Cだけでやるには、while と switch case を使う！！
わざと末尾再起しない再起関数を
int length(char* c)
{
if( *(c+1) != 0 ){
return length(c+1)+1;
}else{
return 1;
}
}
見たいなのを、あろはさんのコンパイラで、コンパイルすると、
#include <stdio.h>
unsigned int stack[1024];
#define PUSH(x) sp++; *sp = (x);
#define POP(x) x = *sp ; sp--;
#define PUSHCH(x) sp++; *sp = (unsigned int)(x);
#define POPCH(x) x = (char*)*sp ; sp--;
int length(char* c)
{
// context initialize
int reg1, pc;
unsigned int* sp;
sp = stack;
reg1 = 0;
pc = 0;
// int length(char* c) {
PUSHCH(c);
PUSH(255);
while(1){
switch(pc){
case 0:
length_re:
c = (char*)*(sp-1);
/* if ( *(c+1)!= 0 ){/*
if( *(c+1) == 0 )
goto ELSE;
/* return length(c+1)+1; */
c++;
PUSHCH(c);
PUSH(1);
goto length_re;
case 1:
POP(reg1);
POP(pc);
sp--;
PUSH(reg1+1);
break;
/* }else{ */
ELSE:
//return 1;
POP(pc);
sp--;
PUSH(1)
break;
/*}*/
default:
goto OUT;
}
}
OUT:
POP(reg1);
return reg1;
}
int main(int argc, char** argv)
{
printf("%d\n",length("AAAA"));
}
見たいになると、goto と、末尾再起でない再起が混在できますです。ハイ！
shiro@acm.org
> Scheme とか JavaScript とかの，超高級言語使いの人達が，継続とかコルーチンとか yield とかマイクロスレッドとか騒いでますが，CPU の世界ではごく普通のことなんですよねぇ．
む、聞き捨てならねぇな。
確かにSchemerは騒いでいたさ。Steeleとかいう兄ちゃんがな。継続は関数呼び出しだし、関数呼び出しは引数付きgotoだってな。わざわざアセンブラコードと並べて比べたりしてな。
…もうかれこれ30年前のことだがな。
む、聞き捨てならねぇな。
確かにSchemerは騒いでいたさ。Steeleとかいう兄ちゃんがな。継続は関数呼び出しだし、関数呼び出しは引数付きgotoだってな。わざわざアセンブラコードと並べて比べたりしてな。
…もうかれこれ30年前のことだがな。
> とくめいきぼう さん
>> すでにすごい人たちがすごい回答を書いているので、匿名に…。
もしかして，同じような気持ちで，なかなかコメントとか書き込む気がおきない方々がけっこういたりするのかなぁ，と思いました．
このブログのコメント欄がいつも閑散としているのは，そのせい ? (単に私の文章がつまんなさすぎるだけかもしれませんが)
確かに書き込んでくださる方々は，みなさんもの凄くて，私自身もいつも強縮しているのですが，管理人自体は全然凄くないので，もっとお気楽にいろいろ思いついたことをテキトーに書き込んでくださるとうれしいです．匿名でも全然かまいませんが (^o^)
情報は発信する人のところに集まる，の原則を目当てに，ブログを書いているので，フィードバックは，何でも素直にとっても嬉しいです．
>> 標準Cだけでやるには、while と switch case を使う！！
おー，なるほど．いやいや，とても素晴らしい回答だと思いますよ ！！！ 大感謝．
いろいろなやり方があるものですねぇ・・・ 文字へのポインタをワード配列に突っ込んでいるところに，男気を感じました w
# 私の場合は，ポインタ演算はあんまり使わないで，ベースポインタもスタックポインタも，全て自然数の配列インデックスと考えて，何もかもワード配列のスタックの特定のインデックスに突っ込んじゃってますが・・・ (^^;
/*
どうでもよいことですが，処理の流れを追うために printf してたら気付いたのですが (頭悪くてすいません・・・)
スタックの先頭が使われていないのが，ちょっと勿体無いかなと思いました (本当にどうでもよくてすいません)．
0, 134514271, 255, 134514272, 1,
0, 134514271, 255, 134514272, 1, 134514273, 1,
0, 134514271, 255, 134514272, 1, 134514273, 1, 134514274, 1,
ここに，現在のスタックの使用長とか入れておくと，表示の時
{
int i;
for(i = 0; &stack[i] <= sp; i++)
printf("%u, ", stack[i]);
puts("\n");
}
こういう，ちょっと違和感があることをしなくてすむかも．for(i = 0; i < stack[0]; i++) ... みたいに．私は，スタックポインタは配列のインデクスとして持つことが多いです (いちいち加算が発生するので，効率悪いですが・・・ どうもポインタ演算は好きじゃないのですよ．単なる構文糖衣の問題ですが)．
*/
これの一般化は (私の頭では) なかなか難しそうですが，勉強になりました．もっといろいろなコンパイル手法を探ってみたいと思います．コメントありがとうございました m(_ _)m
# もっと C 言語のソースを読む訓練をつまないとなぁ・・・ 人の書いたソースが全然読めない．初心者ですいません・・・ orz
もしかして，同じような気持ちで，なかなかコメントとか書き込む気がおきない方々がけっこういたりするのかなぁ，と思いました．
このブログのコメント欄がいつも閑散としているのは，そのせい ? (単に私の文章がつまんなさすぎるだけかもしれませんが)
確かに書き込んでくださる方々は，みなさんもの凄くて，私自身もいつも強縮しているのですが，管理人自体は全然凄くないので，もっとお気楽にいろいろ思いついたことをテキトーに書き込んでくださるとうれしいです．匿名でも全然かまいませんが (^o^)
情報は発信する人のところに集まる，の原則を目当てに，ブログを書いているので，フィードバックは，何でも素直にとっても嬉しいです．
>> 標準Cだけでやるには、while と switch case を使う！！
おー，なるほど．いやいや，とても素晴らしい回答だと思いますよ ！！！ 大感謝．
いろいろなやり方があるものですねぇ・・・ 文字へのポインタをワード配列に突っ込んでいるところに，男気を感じました w
# 私の場合は，ポインタ演算はあんまり使わないで，ベースポインタもスタックポインタも，全て自然数の配列インデックスと考えて，何もかもワード配列のスタックの特定のインデックスに突っ込んじゃってますが・・・ (^^;
/*
どうでもよいことですが，処理の流れを追うために printf してたら気付いたのですが (頭悪くてすいません・・・)
スタックの先頭が使われていないのが，ちょっと勿体無いかなと思いました (本当にどうでもよくてすいません)．
0, 134514271, 255, 134514272, 1,
0, 134514271, 255, 134514272, 1, 134514273, 1,
0, 134514271, 255, 134514272, 1, 134514273, 1, 134514274, 1,
ここに，現在のスタックの使用長とか入れておくと，表示の時
{
int i;
for(i = 0; &stack[i] <= sp; i++)
printf("%u, ", stack[i]);
puts("\n");
}
こういう，ちょっと違和感があることをしなくてすむかも．for(i = 0; i < stack[0]; i++) ... みたいに．私は，スタックポインタは配列のインデクスとして持つことが多いです (いちいち加算が発生するので，効率悪いですが・・・ どうもポインタ演算は好きじゃないのですよ．単なる構文糖衣の問題ですが)．
*/
これの一般化は (私の頭では) なかなか難しそうですが，勉強になりました．もっといろいろなコンパイル手法を探ってみたいと思います．コメントありがとうございました m(_ _)m
# もっと C 言語のソースを読む訓練をつまないとなぁ・・・ 人の書いたソースが全然読めない．初心者ですいません・・・ orz
>> Scheme Arts L.L.C. 代表様
あぁ，すいません，日本 scheme の会会長様 ！！ (そんな会はありませんが)
この言及の主語は，強く JavaScript に (私の中で) かかっていて，つまり (アタフタ)，この最近話題になっている記事にあてこすったというか，なんというか，すぐ調子に乗って，ついついこういう挑発的なことを書いてしまう癖が・・・ 本当に関係各所各方面の皆皆様，いろいろすいません．
http://d.hatena.ne.jp/amachang/20060805/1154743229
scheme は，御本尊ということで，とりあえず載せただけで・・・ 貶めるような他意はありませんでした．
むしろ Shiro さんの記事で聞きかじった知ったかぶり知識ばかりなので，なんというか，釈迦に説法，顔から火が出るとは，まさにこういう心境なのだろうと・・・ (汗)
・・・ ということを
>> む、聞き捨てならねぇな。
わかっててわざと釣られるとは，人が悪いですなぁ，先生 w ！ (^^;
λ ・・・
この言及の主語は，強く JavaScript に (私の中で) かかっていて，つまり (アタフタ)，この最近話題になっている記事にあてこすったというか，なんというか，すぐ調子に乗って，ついついこういう挑発的なことを書いてしまう癖が・・・ 本当に関係各所各方面の皆皆様，いろいろすいません．
http://d.hatena.ne.jp/amachang/20060805/1154743229
scheme は，御本尊ということで，とりあえず載せただけで・・・ 貶めるような他意はありませんでした．
むしろ Shiro さんの記事で聞きかじった知ったかぶり知識ばかりなので，なんというか，釈迦に説法，顔から火が出るとは，まさにこういう心境なのだろうと・・・ (汗)
・・・ ということを
>> む、聞き捨てならねぇな。
わかっててわざと釣られるとは，人が悪いですなぁ，先生 w ！ (^^;
λ ・・・
美味しそうだったので釣られてみました。
でも、Steeleの "Lambda: the ultimate goto" とか読むと、
かなり「関数呼び出しは重くない！ほらアセンブリにすると
こんだけだ」とか力説していたりするので、そこから逆に当時の
ソフトウェア界の常識みたいなものが推し量られる気がします。
せっかくですからSteele御大のLambda papers (Scheme教の
old testament?) などつれづれに眺めてみるのも一興では。
私の記事はみんなそのへんからの受け売りです。
でも、Steeleの "Lambda: the ultimate goto" とか読むと、
かなり「関数呼び出しは重くない！ほらアセンブリにすると
こんだけだ」とか力説していたりするので、そこから逆に当時の
ソフトウェア界の常識みたいなものが推し量られる気がします。
せっかくですからSteele御大のLambda papers (Scheme教の
old testament?) などつれづれに眺めてみるのも一興では。
私の記事はみんなそのへんからの受け売りです。
> shiro さん
ちょうど，やっぱりコンパイル技法がいろいろと高度に発達している （イメージがある） Lisp は見ておかないと駄目だろうなぁ，と思っていたところでした．
Lambda paper は，フォントが見難いというしょうもない理由で読んでなかったのですが (汗)，良い機会ですので眺めて見ます (と思ったら，今日は研究室のネットワークが不安定になっていて，印刷ができない… これだもんなぁ orz)．
Procedure call implementations considered harmful とか，タイトルからして素敵すぎですね，Steele おじさま，さすがです (笑)
Lambda paper は，フォントが見難いというしょうもない理由で読んでなかったのですが (汗)，良い機会ですので眺めて見ます (と思ったら，今日は研究室のネットワークが不安定になっていて，印刷ができない… これだもんなぁ orz)．
Procedure call implementations considered harmful とか，タイトルからして素敵すぎですね，Steele おじさま，さすがです (笑)
