9

私はこのコードを持っています：

(define (prog1 x y)
    (let ([rel (related x y)])
      (cond
        [(null? rel) (list x)]
        [else (cons x (map (lambda (d) (prog1 (neighbour d) y)) rel))])))

私がやりたいのは、末尾再帰にすることです。私は次のようなことをする必要があることを知っています：

(define (prog1 x y)
  (prog1-iter x y `()))

(define (prog1-iter x y acc)
  (...
   ))

しかし、自分のコードからこのコードに移行する方法がわかりません...オリジナルにマップが含まれているためだと思います。これをに組み込む方法がわかりませんprog1-iter。誰かが私を正しい方向に向けることができますか？

4

1 に答える 1

4

末尾再帰は、本質的に反復的なものに対して簡単に記述できます。関数は自分自身を何度も呼び出す可能性があるため、単純ではありません。それでも、どのプログラムも反復可能にすることができるので（たとえば、コンピューターが巨大な反復マシンである場合）、それを実行できます。

まず第一に、関数は直接再帰的ではprog1ありません（つまり、関数自体を直接呼び出すことはありません）。むしろ、をprog1呼び出しますmap。これにより、指定したラムダが（おそらく複数回）呼び出され、次にprog1;が呼び出されます。したがって、間接的です。toの呼び出しmapは末尾呼び出しではありません。からのラムダへの呼び出しmapは、確かに末尾呼び出しではありません（複数回呼び出す必要がある場合があります）。ラムダからへの呼び出しprog1は末尾呼び出しです。

したがって、「末尾再帰」を要求するときに、正確に何が必要かはわかりません。からの呼び出しのチェーン内の各呼び出しprog1をそれ自体への末尾呼び出しにしますか？または、プログラム内のすべての呼び出しを末尾呼び出しにしますか？の「末尾再帰」バージョンが存在しますが、からのmap呼び出しに関しては「末尾再帰」のみであり、マッピング関数の呼び出しではないため、この場合には役立ちません。mapmap

プログラム内のすべての呼び出しを末尾呼び出しにする一般的な方法は、継続渡しスタイルと呼ばれます。基本的に、すべての関数は追加の関数引数「継続」を取ります。関数に対して非末尾呼び出しを行う代わりに、関数に対して末尾呼び出しを行い、関数呼び出しの結果を処理する方法を指定する継続を渡します。基本的に、継続は非末尾呼び出しの後の元の関数の「残り」を含み、元の非末尾呼び出しの「戻り結果」を引数として受け取ります。プログラムをCPSに変換する方法の演習として残しておきます。

于 2012-12-29T00:07:51.137 に答える