カスタムVMで末尾再帰を実装する方法

Question

私はカスタム仮想マシンに末尾再帰を実装する方法を教えてください。

私は、元の関数のローカルスタックからポップする必要があることを知って、それは引数が、その後、新しい引数にプッシュします。しかし、私は、関数のローカルスタックからポップした場合、どのように私は新しい引数を押すことになってんですか？彼らはただ、スタックからポップしてきます。

Answer 1

私たちはここに、伝統的な「スタックベースの」仮想マシンを議論していることを許可されたためにそれを取るます。

あなたは現在の関数のローカルスタックからポップの非スタック「レジスタ」で、まだ、関連する部分を保存の（「関連する部分は、」どこ、明らかに、今後の再帰的な末尾呼び出しの引数）、その後、（関数のローカルスタックおよび引数のすべてがクリーンアップされたら）あなたが再帰呼び出しの引数を押してください。例えば、機能を仮定しますしている最適化のようなものです。

def aux(n, tot):
  if n <= 1: return tot
  return aux(n-1, tot * n)

：最適化することなく、象徴のようなバイトコードを生成可能性がある。

AUX:   LOAD_VAR   N
       LOAD_CONST 1
       COMPARE
       JUMPIF_GT  LAB
       LOAD_VAR   TOT
       RETURN_VAL
LAB:   LOAD_VAR   N
       LOAD_CONST 1
       SUBTRACT
       LOAD_VAR   TOT
       LOAD_VAR   N
       MULTIPLY
       CALL_FUN2  AUX
       RETURN_VAL

CALL_FUN2「は、2つの引数で関数を呼び出す」を意味します。最適化と、それはいつかのようになる可能性があります：

   POP_KEEP     2
   POP_DISCARD  2
   PUSH_KEPT    2
   JUMP         AUX

もちろん

私が一緒に行くように私は私のシンボリックバイトコードを作るんだけど、私は意図を希望は明確である：POP_DISCARD nは、スタックからちょうど破棄トップnエントリをすることを、通常のポップですが、POP_KEEP nはそれらを保持した変種です（例えば、アプリケーションに直接アクセスするだけVM自身の機械にはない補助スタック内 - VMの実装を議論する際に、このようなAの文字でストレージが時々「レジスタ」と呼ばれている）「どこか」と「レジスタを空に一致PUSH_KEPT n 「VMの通常のスタックに戻っています。

Answer 2

私はあなたがこの時に間違った方法を探していると思います。代わりに、スタックから古い変数をポップして、新しいものをプッシュするのは、単純に（慎重に）既に存在するものを再割り当てします。これは大体、あなたが同等の反復アルゴリズムするコードを書き直したらどうなる同じ最適化されます。

このコードの場合、

 int fact(int x, int total=1) {
     if (x == 1)
         return total;
     return fact(x-1, total*x);
 }

タグになります

 fact:
   jmpne x, 1, fact_cont  # if x!=1 jump to multiply
   retrn total            # return total
 fact_cont:               # update variables for "recursion
   mul total,x,total      # total=total*x
   sub x,1,x              # x=x-1
   jmp fact               #"recurse"

単に再割り当てするか、スタック上に何かをポップまたはプッシュする必要はありません。
明らかに、これはさらに私たちは、より少ない操作で、その結果、ジャンプをスキップすることができ、第二の出口条件を置くことによって、最適化することができます。

 fact_cont:               # update variables for "recursion
   mul total,x,total      # total=total*x
   sub x,1,x              # x=x-1
 fact:
   jmpne x, 1, fact_cont  # if x!=1 jump to multiply
   retrn total            # return total

再び見ると、これは「アセンブリ」より良い明確に再帰呼び出しを避けてきたこのC ++を、反映します。

int fact(int x, int total=1)
    for( ; x>1; --x)
        total*=x;
    return total;
}