2007/06/17

練習問題を放置したままだったSICPの第5章をぽちぽち再開。こうやって再読してみると、すっかりどんな話だったか忘れてる。やっぱり手を動かさないで本を読んでいるだけじゃなんにも身につかない。編集という、まさに読んでいるだけの職業に自分が従事している現実を呪うのはこういう瞬間だ。ただの逆ギレだけど。

というわけで第5章の練習問題に着手しはじめた。ところがすぐに困っちゃったのは、この章の内容がGauche(などのSchemeインタプリタ)で式を実行すれば確かめられる話じゃないこと。とくに5.2節でレジスタマシンのシミュレータをSchemeで作るまでは、紙と鉛筆でデータの流れを図示したりしながら、脳内レジスタマシンを妄想して読み進めるしかない。「レジスタマシンの動作を手でシミュレートしろ」といった問題を考えるのは楽しいんだけど、どうにも「わかった気になっているだけかも」という懸念がぬぐえないのが気持ち悪い。どうでもいいけど、専門書や専門雑誌の編集者を楽しく長く続けていくのに求められる最強のスキルは、「わかった気になったところで留まっていられる」ことだとおもう。前々から気がついてはいたけれど、最近になってひどく実感するようになった。こういう感情をわざわざ書きとめているということは、そういうことだ。ここまでどうでもいい話。

この気持ち悪さはレジスタマシンがあれば解決する。かといって5.2節でシミュレータを作るまで待ってられないし(経験上、1問でも練習問題をぬかすと最後まで練習問題に手をつけずに読了する。帰納法で証明できたらかっこいいかもね)、そもそもSchemeでシミュレートするっていうのも気持ちが悪い。最初にこの章を読んだときは「これは教科書として画期的なアイデアだ」と思ったけど、実際はめんどくささのランクをひとつ繰り上げているだけなような気もする。

アセンブリというわけにもいかないので、Cで書いてみることにした。たとえばフィボナッチ数列の第n項を求めるレジスタマシンのコントローラ(原書512ページのFigure5.12)。
/* Implementation of a recursive fibonachi machine in C.
(Figure 5.12 of "SICP")
2007/6/17
k16.shikano@gmail.com
*/

#include <stdio.h>
#include <stdlib.h>
#define STACKSIZE 100

void fibloop();
void afterfib1();
void afterfib2();
void fibdone();
void immediate();
void rtc(int);

void initstack();
void save(int);
int restore();

int cont = 0;
int val;
int n;

main(int argc, char *argv[])
{
initstack();
n = atol(argv[1]);

fibloop();
}

void fibloop()
{
while(n >= 2)
{
save(cont);
cont = 1;
save(n);
n = n - 1;
}
immediate();
}

void afterfib1()
{
n = restore();
cont = restore();
n = n - 2;
save(cont);
cont = 2;
save(val);
fibloop();
}

void afterfib2()
{
n = val;
val = restore();
cont = restore();
val = val + n;
rtc(cont);
}

void immediate()
{
val = n;
rtc(cont);
}

void fibdone()
{
printf("answer = %d\n", val);
exit(1);
}


/* return to continue */
void rtc(int c)
{
switch(c)
{
case 0: fibdone();
case 1: afterfib1();
case 2: afterfib2();
}
}


/* naive stack implementation */
int stack[STACKSIZE];
int *pstack;
int *pinit;

void initstack()
{
pstack=stack;
pinit=pstack;
}

void save(int val)
{
if (pstack > pinit+STACKSIZE){
perror("Reached Stack End");
exit(1);
}

*pstack=val;
++pstack;
}

int restore()
{
if (pstack == pinit){
perror("Reached Stack Head");
exit(1);
}

--pstack;
return *pstack;
}
スタックの機能をでっちあげて、Figure5.12にあるSchemeっぽい式をもじどおりCに置き換えただけ。コンパイルして実行すると(想定内のセグメンテーション違反はおこすけど)あっさりうごく。
k16@debian:~/play $ ./fib 24
answer = 46368
k16@debian:~/play $ ./fib 25
セグメンテーション違反です

これは、Cでフィボナッチを書きました、という話ではなく、これまでSchemeというレイヤでプログラミングしているときに再帰関数だと思っていたコレが、
(define (fib n)
(if (< n 2)
n
(+ (fib (- n 1)) (fib (- n 2)))))
その下のレイヤでは上記のCのコードのようなレジスタへの代入とスタックへの出し入れだけの形(現代のコンピュータがかろうじて完璧に扱える形)に解くほぐせて、しかも動く、という話なんだよね。プログラミング言語っていうのは、もしかして、ここで手動で試してみたコードからコードへの変換みたいな処理を自動的に行うしくみのことなのか?

なんだかこの本を読みはじめたときのようなわくわく感が。

No comments :