とりあえず、書きかけで公開 (^^;
いにしえ(1977年発表)の言語として Robot言語 というものがあり。
シェルピンスキー曲線 PCが普及しておらず、グラフィック機能が珍しいときに、出た言語。
しいて関数型と言えば関数型だが、変数が一つしかなく、極めて限定された言語。
リカーシブ・コールが前提。
なので、ループも、リカーシブに記述。
下の絵が、2関数が互いに呼び合う無限ループの例。
ループをリカーシブに書くということは、インタープリタは、テールリカーシブ・インタープリタであって欲しい。
Robot言語は、極めて単純な言語なので、実行系をテールリカーシブ・インタープリタとして実現するのは、容易である。
私が、大昔に、Mac用にCで書いたものがあるはずだが、ソースごと失った。
ケータイ用のJavaの出始め("KVM"と呼ばれた) に、KVM用に書いたソースは、いまだに公開中。
Krobot として公開中。
このソースは、素朴な仮想機械のインタープリタである。
と見せかけて、関数呼び出しの部分が、テールリカーシブ・インタープリタになっている。
そこだけ、解説をしたい…
… といいつつ、とりあえず、ここまでで公開。(^^;
すんません > 世界
ここから、2014/OCT/19 追記 (10ヶ月以上、経ってしまったか)
昨日の、kernel/VM つくば にて、「Robot言語と末尾再帰インタープリタ」というLighting Talkをしてきた。
「資料スライド」
スライドに書いてあるのだが、要するに、
・一命令ていどしか見ない、(仮想機械)インタープリタで、末尾再帰 最適化を行う方法があり、
それでインタープリタを作ってる。
・大事なことは、新しい関数を見つけて、それを呼び出すときに、不要な情報はセーブ(スタックへpush)しない。
・そのために、新しい関数を呼ぶ前に、ほんの少しだけ先読みして、現在のプログラム・カウンタの指しているところが、呼び出し元の関数の末尾かどうかを確認。
もし、末尾であれば、そこに戻ってきて続ける必要が無い。よって、情報をセーブ(push)しない。
・極めて簡単であるが、それによって、Continuation Passingになる。
私のKRobot(と、今回、やっとX Window に持ってこれた Robot言語インタープリタ)のソースでは、
exeq()という関数が、機械の一命令を実行する関数である。
その最後あたり(switch文のdefault)が、ユーザ定義関数から、別な関数を呼び出す部分である。
そこで、新しい関数を呼び出す直前に、末尾か(やることがあるか?)を、CT[Pc]が'\0'か、否かで判定し、
末尾なら push をサボって、最適化している。
(CTは、ユーザ定義関数のボディを保持。Pcは、プログラム・カウンタで、次に実行する命令を指している)
int
exeq() // 1命令を実行する
{
n= term();
switch((ccc=CT[Pc++])){
case 'f' :
x1=x + n*v*step; y1=y + n*u*step;
drawLine(x,y, x1,y1, 0);
x=x1; y=y1;
break;
:
:
default: /* ユーザ定義関数 */
top= defun[ccc-'a'];
/* 末尾再帰 最適化可能な時は、pushしない
ユーザ関数定義の末尾、すなわち、後に実行すべきものが何もない */
if(n!=1 || CT[Pc]!='\0'){ /*やるべきことがある時、セーブ*/
Context c;
c.n=n; c.top=top; c.pc=Pc; c.ct=CT;
stk_push(&c);
} // やることが無いときは、何もしない。最適化できた!!
CT= top; Pc=0;
//printf(" userFunc %c CT=%x ",ccc,CT);
}
}
以上のような、構造のインタープリタを、
「テール・リカーシブ・インタープリタ(末尾再帰インタープリタ)」という。
スタックを無駄遣いしないので、末尾再帰による無限ループでも、スタックが減らず、永久にループしつづける。
Schemeは言語仕様書に、インタープリタは、テール・リカーシブ・インタープリタとして実現することとされている。
PrologやSmalltalkなどのコンパイルド・コードを実行する仮想機械インタープリタも、テール・リカーシブ・インタープリタとして実現されることが通常である。
X window版のRobotのソースは、そのうち公開するであろう。
しかし、MacでRobotインタープリタを作ったのが、1988 or 1989年ごろだったが、成長してないなぁ。
というか、Mac版は、テキスト編集とインタープリタの統合環境だったので、どんどん退化してるやん。(涙)