📐トランポリンループでスタックオーバーフローを回避せよ
再帰関数は、関数が自分自身を呼び出すことで動作する関数のことを指します。しかし、深い再帰を行うと、関数の呼び出しスタックが増えていき、スタックオーバーフローを引き起こすリスクがあります。この問題を解決するための一つの手法が、トランポリンループです。
トランポリンループの基本的な考え方は、再帰を使う代わりにループを使い、そのループ内で関数の実行を行うというものです。これにより、関数の呼び出しスタックが増えることを防ぎ、スタックオーバーフローのリスクを軽減します。
FPの世界に足を踏み入れると、再帰と呼ばれるものに突き当たります。
トランポリン関数は、基本的に再帰的な関数をループで包む。トランポリン関数は、再帰関数をループで包み、再帰関数が呼び出されなくなるまで、少しずつ呼び出します。
CPS(継続渡しスタイル (CPS: Continuation-passing style) )が連続を作成して渡すところ、メモリ圧迫を緩和する別のテクニックとして、トランポリンと呼ばれるものがあります。このスタイルのコードでは、CPSのような連続性が作成されますが、渡されるのではなく、浅く返されます。関数が関数を呼び出すのではなく、各関数が次に呼び出すべき関数を返すだけなので、スタックの深さが1より深くなることはない。ループは、返された関数を、実行すべき関数がなくなるまで実行し続けるだけである。トランポリンの利点は、PTC(Proper Tail Calls 末尾再起最適化) をサポートする環境に限定されないこと、もう一つは、各関数呼び出しが PTC 最適化ではなく通常のものなので、より高速に実行できる可能性があることです。
Kyle Simpson
Proper Tail Calls (PTC) は ECMAScript 6 言語に追加された新機能です。この機能は、再帰的なプログラミングパターンを促進するために追加されたもので、直接再帰と間接再帰の両方があります。PTC は他の様々なデザインパターンにも有効で、例えば、ある機能をラップするコードでは、ラップしたコードがその結果を直接返します。PTC を使用することで、コードの実行に必要なメモリ量が削減されます。深い再帰的なコードでは、PTC を使用するとスタックオーバーフロー例外が発生するようなコードも実行できます。
関数型プログラミングにおいて、継続パッシングスタイル（CPS）とは、継続という形で明示的に制御を渡すプログラミングのスタイルである。これは、通常のプログラミングスタイルである直接スタイルと対比される。Gerald Jay SussmanとGuy L. Steele, Jr.がプログラミング言語Schemeの最初のバージョンを定めたAI Memo 349 (1975)でこの言葉を作った[1][2] John C. Reynoldsは継続に関する数々の発見を詳細に説明している[3]。
JavaScript は ES6 までテールコールを必要とせず、また禁じてもいませんでした。ES6では、Proper Tail Calls (PTC) と呼ばれる特定の形式のテールコールを認識し、PTC形式のコードが無制限にスタックメモリを増やすことなく実行されることを保証することを義務付けました。
いいなと思ったら応援しよう！
