7

JavaScript でおもちゃの Lisp インタープリターを作成しています。JS には末尾再帰の削除 (TRE) がないため、JS で while ループを使用して TRE を実装しました (疑似コード):

function eval (exp, env)
  while true
    if exp is self evaluating
      return exp
    else if ...
      ...
    else if exp is a function call
      procedure = eval(car(exp), env)
      arguments = eval_operands(cdr(exp), env)
      exp = procedure.body
      env = extend_env(procedure.env, env)
      continue # tail call

だから私は満足しており、次のような末尾再帰関数はスタックを使い果たしません:

(define +
  (lambda (n m)
    (cond ((zero? n) m)
          (else (+ (sub1 n) (add1 m))))))

(+ 10000 1) ;=> 10001

ただし、末尾再帰ではない関数は JS スタックを使い果たします (JS コードが であまりにも多く再帰するためeval_operands):

(define +
  (lambda (n m)
    (cond ((zero? n) m)
          (else (add1 (+ (sub1 n) m)))))  ; not proper tail-recursive

(+ 10000 1) ;=> JS: Maximum call stack size exceeded

非末尾再帰関数を処理するにはどうすればよいですか? オプションは何ですか？良いリソースとは？トランポリン、スタックの外部化、および継続渡しスタイルについて少し読んだことがありますが、インタープリターを作成するためにこれらの手法を使用する方法ではなく、これらのスタイルでコードを記述する方法しか見つかりませんでした。

4

1 に答える 1

4

呼び出しフレーム情報を別の場所に保持できる場合は、いつでも呼び出しをジャンプに変えることができます。それが「スタックの外部化」と呼ばれるものです。

インタープリターの場合、呼び出しフレーム データは末尾呼び出し以外の呼び出しの継続を保持する必要があります (アクセスが必要な変数への参照など、それ自体がさらに参照を保持する場合があります)。アクティブな非テール コールごとに 1 つのコール フレームが必要です。

もちろん、これが行うことは、スタック領域をヒープ領域と交換することだけです。結局、この方法では実際にはメモリを節約できません。:-)

于 2013-02-01T02:52:05.500 に答える