ObjectPascal Magic Programming
Tail Recursive

遅延評価(もしくは環境付きの関数ポインタ)はそのままとして、こちらも実は関数型言語で言うところの(静的)束縛になっていることは、皆さんお気づきでしょうか？

僕？僕はついさっきまで気づきませんでしたよ。いやー、考えてもみませんでしたなあ。こうしてみると、便利なトリックってば関数型言語に実装済みなのですねえ。今さらこんなことを書いているのは、Schemeをアセンブラレベルで解説してくれているページなんてのを読んだからなのですけれど。

さて、構造化以前のBASICでは構造化プログラミングはできません。 GOSUBはありますが、ローカル変数が無いからです。特定の言語を、無理やり想定されているのとは別のパラダイムで使用することは可能です。 C言語でも関数ポインタを駆使してOOPはできます。ですが、C言語で関数型プログラミングは、辛いものがあります。関数型プログラミングに必要な、遅延評価、束縛、末尾再帰、その他諸々に対応する言語機能が無いからです。もちろんPascalにも無いです。 (C++ですとtemplateでモドキなら可能です)

しかし、関数型言語といえど、静的に機械語にコンパイル可能な言語という点では、CやPascalと何一つ変わりません。最終的には機械語に落ちるのです。そう、どんな機能でも、機械語にコンパイルものでありさえすれば、それは、インラインアセンブラで上手く模倣してやれば、きっと実現できるでしょう。おお、気づけば、遅延評価と束縛は既にここで書いてるじゃないかっ！

…で、冒頭となるわけです。

末尾再帰とは、スタックを消費せずに同じ関数(または別の関数)を呼び出す機能です。これがあれば、forとかwhileとかrepeat..untilを使うことなく、ループを記述できたりします。また、再帰呼出しを記述する時、スタック消費を気にせずに書けます。

要するに、関数の最後でretせずに、リターンアドレスを崩さないように引数部分を次の呼び出しのものに書き換えてjmpするだけの話です。スタック節約の為DOS時代のアセンブラでは普通に使われていたテクニックに過ぎません。

さて、素直にインラインアセンブラで書くことは単純なのですが、その場合、引数がスタック上で消費するサイズを把握しておかなければなりません。また、クリーンナップが必要な型(stringとか)をローカル変数として使っていた場合、インラインアセンブラで他の関数に飛んでしまうと、それらはメモリリークする事になります。

…で、考えたのが、これ(↓)。

program Project2;

{$APPTYPE CONSOLE}

threadvar
  Proxy: array[0..255] of Byte;

procedure _Jump(Func: Pointer); cdecl;
const
  AddESP = $c483;
  PushDWORD = $68;
  MovEAX = $b8;
  JmpEAX = $e0ff;
var
  Base, Ret, ArgSize, I, P, ParentEBP, OrgRet: Cardinal;
begin
  asm
    mov Base, EBP
  end;
  Ret := PCardinal(Base + 4)^;
  Assert(PWord(Ret)^ = AddESP);
  ArgSize := PByte(Ret + 2)^ - 4;
  P := Cardinal(@Proxy);
  for I := 1 to ArgSize div 4 do
  begin
    PByte(P)^ := PushDWORD;
    PCardinal(P + 1)^ := PCardinal(Cardinal(@Func) + I * 4)^;
    Inc(P, 5);
  end;
  ParentEBP := PCardinal(Base)^;
  OrgRet := PCardinal(ParentEBP + 4)^;
  PPointer(ParentEBP + 4)^ := @Proxy;
  PByte(P)^ := PushDWORD;
  PCardinal(P + 1)^ := OrgRet;
  Inc(P, 5);
  PByte(P)^ := MovEAX;
  PPointer(P + 1)^ := Func;
  PWord(P + 5)^ := JmpEAX;
end;

var
  Jump: procedure(Func: Pointer); cdecl varargs = _Jump;

function B(X: Integer): Integer; stdcall;
begin
  Result := X + 1;
end;

function A(X: Integer): Integer; stdcall;
begin
  Jump(@B, X * 2);
  Result := 0; {←未代入の警告を抑止}
end;

begin
  WriteLn(A(10));
end.

ちゃんと21と表示されるでしょう？

もひとつ、今度はきちんと末尾再帰な例。

...前略...

{$STACKFRAMES ON}
procedure Loop(I: Integer); stdcall;
begin
  if I > 0 then
  begin
    Write('X');
    Jump(@Loop, I - 1);
  end;
end;
{$STACKFRAMES OFF}

begin
  Loop(40);
end.

40個の'X'が表示されます。このような方法でループを組んでも、スタックは一段しか消費しないわけです。

やっていることは、次の関数を呼び出すコード片を作成し、リターンアドレスをそこへ書き換える、Vol.2の応用です。呼び出される側(B)のstdcallは必須です。 Aのstdcallは、リターンアドレスを確定するために必要なスタックフレームを作らせるために付けています。 {$STACKFRAMES ON}でもいいです。というかstdcallならスタックフレームが作られるなんてのは保証されているわけではないと思うので{$STACKFRAMES ON}の方がいいでしょう。 Jumpが関数ポインタなのは、varargsを使うためのテクニックというかコンパイラの多分バグを突いたワザです。 Proxyがthreadvarなのは、マルチスレッドを考慮して。

…正直、効率は凄く悪い筈です。 Vol.1、Vol.2は、それぞれ、パラメータをLPARAMみたいな引数で引き渡したり、GetPropでSelfを得るよりも、効率はいいのですが、これは、効率を悪化させます。コンパイラがサポートしていれば、数個のmovとjmpで済むところを、コードを動的に作ったりリターンアドレスを書き換えたりしてるのですもの。 CPUの分岐予測？何ですかそれは？の世界です。素直にスタックを消費した方が、いや、それよりも普通にforとかwhileとかrepeat..untilを使ってしまえば済む話です。

しかしっ
好奇心こそアマチュアの原動力っ

おそまつさま。これ読んで、本当にPascalで関数型プログラミングを行ってしまった猛者がいらっしゃれば、お便りくださいね。

ObjectPascal Magic Programming Tail Recursive

ObjectPascal Magic Programming
Tail Recursive