2007/06/23

Schemeの多値の正体は継続

SICPでは「多値」を表立って使うことはない。ただ、5.2.2で2種類のリストをやりとりするときに2変数のプロシージャを使った一見するとトリッキーな処理が登場して、これが実は多値なんだよという種明かしを脚注4でやっている。さらに、そのトリッキーな2変数プロシージャのことを継続(continuation)と呼ぶと説明している。

多値も継続だったのか。

噛みしめるために小さな例を考えてみた。つぎのプロシージャ one は、プロシージャ sincos が返す 2 値を受け取り、その 2 乗和を返す。sincos は引数の角度に対する sin の値と cos の値を返すので、プロシージャ one は引数にどんな数値を指定しても実数の 1 を返す。
(define (one rad)
(receive (sin cos)
(sincos rad)
(+ (* sin sin) (* cos cos))))

(define (sincos rad)
(values
(sin rad) (cos rad)))
このプロシージャ one は、values や receive という組み込みの多値のしくみを使わなくても、つぎのように継続を表すプロシージャ cont を使って多値を模倣できる。
(define (one rad)
(sincos
rad
(lambda (sine cosine)
(+ (* sine sine) (* cosine cosine)))))

(define (sincos rad cont)
(cont (sin rad) (cos rad)))
いちおう実行結果。
gosh>(one 123456)
1.0
gosh>(one -9876)
1.0


まとめ

計算の一部または全部をどうにかしたい場合があって(よその関数に渡したいとか、ちょっと保留しておきたいとか)、そのときの定石は「プロシージャでくるんでしまえ」。で、そういうプロシージャのことを「継続」(continuation)と呼ぶ。

2007/06/18

ついやってしまった。

Functional Programming IAT
関数型指数(潜在的な関数型プログラミングの嗜好度)をはかる IAT
http://dame.dyndns.org/misc/fpiat/


「あなたの関数型指数は 0.62331761674765 です。正が関数型、負が手続き型です。」

でも、設問では"Lisp"(Schemeではない)が関数型言語とされているんだけど、それはどうなの?

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のコードのようなレジスタへの代入とスタックへの出し入れだけの形(現代のコンピュータがかろうじて完璧に扱える形)に解くほぐせて、しかも動く、という話なんだよね。プログラミング言語っていうのは、もしかして、ここで手動で試してみたコードからコードへの変換みたいな処理を自動的に行うしくみのことなのか?

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