環境の使い捨てをやめよう！ 〜環境にやさしい環境リサイクル continuation with assembly 編〜
君は継続(continuation)を効率よく使える言語を知っているか！！
そんな、アレだったり、コレだったりではない！原点にかえってアセンブリ言語の話をしよう。なんと、アセンブリ言語は継続を効率良く扱うことができるのだ！！CPUは素晴らしい！！
アセンブリで継続を扱う方法は、
- ebp保存は呼び出し側でやる
- espは減らさない
たったこれだけ！！
void do_nothing( void ) { return ; }
void main( ) { const char *p = "hogehoge"; do_nothing(); puts(p); }こーいうプログラムを考えよう。
ふつーにコンパイルすると、こんな感じ。
.globl main .globl puts .section .rodata str: .string "hogehoge" .text do_nothing: pushl %ebp # ebp 保存 movl %esp, %ebp # スタック先頭をフレームに movl %ebp, %esp # スタック戻す popl %ebp # ebp戻す ret main: pushl %ebp movl %esp, %ebp subl $4, %esp movl $str, -4(%ebp) # p = "hogehoge" call do_nothing # callで呼ぶだけ pushl -4(%ebp) call puts movl %ebp, %esp popl %ebp ret
こいつを、少し考えかたを変える。
struct cont { prog_addr *addr, frame_addr *env }; /* 継続はジャンプ先アドレスと環境をペアにしたの */
void do_nothing( cont c ) {
super_goto *c; /* super_gotoは、フレームも戻すgoto */
}
void main( ) {
const char *p = "hogehoge";
cont c = { retaddr, get_curent_frame() }; /* get_current_frame() は今のフレームを拾ってくる */
do_nothing( c );
retaddr:
puts(p);
}こんな感じにする。super_gotoとget_current_frame()はなんか拡張だと思って。
引数と一緒に、継続データ（続きの実行アドレスとその環境をあわせたもの）を渡しておくのだ。
アセンブリで書くとこんな感じ。
# | local var | # | local var | # | cont addr | <- esp # | cont env | # | argument | # | argument | # | ... | # 何もしないでおわる関数 do_nothing: movl %esp, %ebp # フレーム構築 movl (%ebp), %ebx movl 4(%ebp), %ebp # 引数で渡された環境に戻す jmp *%ebx # 引数で渡されたアドレスにジャンプ .globl puts .globl main main: movl %esp, %ebp # フレーム構築 addl $-4, %esp # 本題とは関係無いけど、addl -4と、subl 4はどのぐらい違うんだろうか movl $message, -4(%ebp) pushl %ebp # 呼び出し側でebpを保存 call do_nothing pushl -4(%ebp) # ライブラリ関数を呼ぶ時は呼びかた変えないと… call puts movl %ebp, %esp ret # mainはライブラリルーチンから呼ばれてるのでそれにあわせないと… .section .rodata message: .string "hogehoge"
で、これで、何ができるのか。
いや、なんでもできるよ。
void do_nanika( int x, int y )
{
int sum = x+y; /* この処理は重い(?)ので、あんまりやりたくない */
printf( "%d\n", sum ); /* ので、この部分だけを実行する処理を値として返したい */
}どんな状況だ。
これを継続を使うと、こう書ける。
cont *do_nanika( ret_cont, int x, int y )
{
int sum = x+y; /* この処理は重い(?)ので、あんまりやりたくない */
cont c = { next, get_current_frame() };
super_goto *ret_cont(c);
next:
printf( "%d\n", sum ); /* ので、この部分だけを実行する処理を値として返したい */
super_goto *ret_cont(c);
}
void nanika_loop( int n )
{
cont *c = do_nanika( next_cont(), 300, 500 ); /* next_contは継続を拾ってくる都合の良い関数 */
if ( n >= 0 ) {
n --;
super_goto *c;
}
}嬉しいのか…は、ともかく、これはC言語では書けない。しかし、アセンブリなら書ける。
.globl main
.globl printf
.section .rodata
format:
.string "%d\n"
.text
# c = -12,-8(ebp) {jump_addr,frame_addr}
# sum = -4(ebp)
# cont = 0(ebp), 4(ebp)
# x = 8(ebp)
# y = 12(ebp)
do_nanika:
movl %esp, %ebp
subl $12, %esp
movl 12(%ebp), %ebx
movl 8(%ebp), %ecx
addl %ebx, %ecx
movl %ecx, -4(%ebp) # sum = x+y
movl $next_addr, -12(%ebp)
movl %ebp, -8(%ebp) # next_cont()
leal -12(%ebp), %eax # 戻り値(継続)は%eaxへ
movl (%ebp), %ebx
movl 4(%ebp), %ebp
jmp *%ebx # super_goto
next_addr:
pushl -4(%ebp)
pushl $format
call printf
addl $8, %esp # printf( "%d\n", sum )
leal -12(%ebp), %eax # 戻り値(継続)は%eaxへ
movl (%ebp), %ebx
movl 4(%ebp), %ebp
jmp *%ebx # super_goto
# c = -4(ebp)
# cont = 0(ebp), 4(ebp)
# n = 8(ebp)
nanika_loop:
movl %esp, %ebp
subl $4, %esp # cont *c
pushl $500
pushl $300
pushl %ebp # 継続を積む
call do_nanika
# もどってきた継続 = %eax
cmpl $0, 8(%ebp)
je .L3
decl 8(%ebp) # n--
movl (%eax), %ebx
movl 4(%eax), %ebp # super_goto c
jmpl *%ebx # super_goto
.L3:
movl (%ebp), %ebx
movl 4(%ebp), %ebp
jmp *%ebx
main:
movl %esp, %ebp
pushl $10 # 10回ループ
pushl %ebp
call nanika_loop
movl %ebp, %esp
retまったく、なんということだろうか。低級言語であるC言語には扱えない概念だけど、アセンブリ言語なら扱える概念というのが存在するのである。Common Lispや、OCamlでさえ、ファーストクラスオブジェクトとして持ってない概念を、アセンブリ言語はファーストクラスオブジェクトとして扱えるのだ！！一級市民だ！！
いや、アセンブリ言語におけるファーストクラスオブジェクトがなんなのかわからないけど。まあ、レジスタ二個ぐらいに入るんだったら、多分一級市民。
と、いうのは、非常に嬉しいような感じなんだけど、このトリックは実はespを減らさない、というところにあるので、なにをどうやっても、そのうちスタックオーバーフローしてしまうのだった。
…いや、ほら、なんていうか、昨今のGC技術の発展によってですね。使わないスタックフレームを捨てたり折りたたんだりとかは自動でやってくれるんですよねぇ…多分。
いや、まあ、そんな感じで、どうでもいい遊び。
なんだけど、これはそれなりに重要なことを表してると思うのだけど。
スタックフレームを柔軟にぐにょぐにょできるのは、非常に興味深い、ということ。で、それは、つまり、「C言語やら、既存の仮想マシンやらのようにフレームをいじれないやつをコンパイラのバックエンドに使ってはいけない」と、いうこと。
Schemeにおける継続、Rubyにおけるイテレータ、ブロック、Pythonにおけるジェネレータ、と、「実行途中の状態を環境ごと閉じ込めてしまう」、という概念は、非常に便利で、応用の幅が広いことは、そういうのを使ったことがある人なら、誰だって知ってることだろう。
しかし、C言語や既存のVMは、そういう概念を扱うことができない。
継続、もしくは、そんな感じのものを実現しようとしたら、効率と美しさを放棄して、無理矢理、そういう概念をエミュレーションするしかなくなる。なんて無駄！なんたる無駄ッ！
CPUを直接弄れば、シンプルかつ、効率よく扱うことができるというのに！たとえ、安全ではないにしても。
コンパイラは、安全な世界と、危険だけど、効率の良い世界とを繋ぐかけ橋として存在しなければならないはず。コンパイラが生成したあとの世界が安全である必要なんてない。そう、つまり、つまりは、アレだ。コンパイラはいつだって、機械語を生成しないといけない。
