トランポリンの仕組みを教えてください

Question

前提・実現したいこと

JavaScriptのスタックオーバーフロー対策として、トランポリンというものがあると知りました。

https://qiita.com/41semicolon/items/985bdd2f551d9392463c

発生している問題・エラーメッセージ

トランポリンの仕組みについて、URL先で海外のURLをのせているんですが、英語が苦手で、Google翻訳で翻訳してもいまいち仕組みを理解できませんでした

そこで、日本語情報がないかと調べましたが、情報が少なく、この海外のURLを読むしかないようで、困っています
なので、トランポリンの仕組みを教えていただきたいです

もうひとつ質問なのですが、トランポリンについてあまり解説などがないのは、末尾再帰という仕組みができたからなのでしょうか？
それとも、[forやwhileなどのループを使えばそもそもスタックオーバーフローが起きないから、再帰とかは使わない]ということなのでしょうか？

よろしくおねがいします。

Answer 1

トランポリン

JavaScriptのスタックオーバーフロー対策として、トランポリンというものがあると知りました。
https://qiita.com/41semicolon/items/985bdd2f551d9392463c

トランポリンは知りませんでしたが、リンク先を読んで、おおよそ理解しました。
まず、再帰呼び出し時の関数呼び出しを「次の処理(関数)」に書き換え、countDown を**「次に処理」を返す関数**に書き換えます。
(「次に処理」を返すだけで「次の処理」は関数呼び出しされません。つまり、countDownを呼び出しても後続処理が発生しません。)
そして、while 文内ではcountDown関数が「次の処理」を返さなくなるまで、countDownを繰り返し、関数呼び出しさせます。
仰る通り、再帰ではなくなるので、スタックオーバーフローが起きる可能性は0になります。

最適化

ただし、トランポリンは原理的にwhile文で関数呼び出ししているのと同義であり、私としては最適化の過程で単純なwhile文に書き換えたくなります。
countDown2 を「次の処理」ではなく、「次の数値」を返すようにコードを書き換えるとこうなります。

function countDown3 (num) {
  if (num % 1000 === 0) console.log(num);
  return --num;
}

function callCountDown (i) {
  while (i) {
    i = countDown3(i);
  }
}

callCountDown(1000);

そして、countDown3 を while 文内に取り込むと、こうなります。

function countDownWhile (i) {
  while (i) {
    if (i % 1000 === 0) console.log(i);
    --i;
  }
}

countDownWhile(1000);

こちらの方が格段にシンプルですよね。
トランポリンは再帰呼び出しの関数コードを少ない手間でwhile文に書き換える為のテクニックだと思います。
修正箇所は少なくなりますが、そこに至るまでの無駄は多くなります。

イテレータ

• イテレーターとジェネレーター - JavaScript | MDN

トランポリンはイテレータと似ています。
(イテレータの .next() は「次の値を返す関数」なので、厳密には違いますが、「次の～を返す関数」という意味では似ていると私は感じました。)
実際に、イテレータで書き直してみましょう。

function CountDown (i) {
  this.i = i;
  this.next = function next () {
    let i = this.i;
    if (i % 1000 === 0) console.log(i);
    return {value: this.i = --i, done: !i};
  }
}

let count = new CountDown(3000), result = {done: false};
while (!result.done) {
  result = count.next();
}

このコードはイテレータの原理を利用していますが、iterableではない為、for-of やSpreadElementが使用できません。
そこで、次のように書き換えます。

function CountDown2 (i) {
  this[Symbol.iterator] = function () {
    return {
      i: i,
      next: function next () {
        let i = this.i;
        if (i % 1000 === 0) console.log(i);
        return {value: this.i = --i, done: !i};
      }
    }
  }
}

for (let v of new CountDown2(3000));
console.log(JSON.stringify([...new CountDown2(1000)])); // [999,998,997,996,995,994,993,992,991,990,989,988,987,986,985,984,983,982,981,980,979,978,977,976,975,974,973,972,971,970,969,968,967,966,965,964,963,962,961,960,959,958,957,956,955,954,953,952,951,950,949,948,947,946,945,944,943,942,941,940,939,938,937,936,935,934,933,932,931,930,929,928,927,926,925,924,923,922,921,920,919,918,917,916,915,914,913,912,911,910,909,908,907,906,905,904,903,902,901,900,899,898,897,896,895,894,893,892,891,890,889,888,887,886,885,884,883,882,881,880,879,878,877,876,875,874,873,872,871,870,869,868,867,866,865,864,863,862,861,860,859,858,857,856,855,854,853,852,851,850,849,848,847,846,845,844,843,842,841,840,839,838,837,836,835,834,833,832,831,830,829,828,827,826,825,824,823,822,821,820,819,818,817,816,815,814,813,812,811,810,809,808,807,806,805,804,803,802,801,800,799,798,797,796,795,794,793,792,791,790,789,788,787,786,785,784,783,782,781,780,779,778,777,776,775,774,773,772,771,770,769,768,767,766,765,764,763,762,761,760,759,758,757,756,755,754,753,752,751,750,749,748,747,746,745,744,743,742,741,740,739,738,737,736,735,734,733,732,731,730,729,728,727,726,725,724,723,722,721,720,719,718,717,716,715,714,713,712,711,710,709,708,707,706,705,704,703,702,701,700,699,698,697,696,695,694,693,692,691,690,689,688,687,686,685,684,683,682,681,680,679,678,677,676,675,674,673,672,671,670,669,668,667,666,665,664,663,662,661,660,659,658,657,656,655,654,653,652,651,650,649,648,647,646,645,644,643,642,641,640,639,638,637,636,635,634,633,632,631,630,629,628,627,626,625,624,623,622,621,620,619,618,617,616,615,614,613,612,611,610,609,608,607,606,605,604,603,602,601,600,599,598,597,596,595,594,593,592,591,590,589,588,587,586,585,584,583,582,581,580,579,578,577,576,575,574,573,572,571,570,569,568,567,566,565,564,563,562,561,560,559,558,557,556,555,554,553,552,551,550,549,548,547,546,545,544,543,542,541,540,539,538,537,536,535,534,533,532,531,530,529,528,527,526,525,524,523,522,521,520,519,518,517,516,515,514,513,512,511,510,509,508,507,506,505,504,503,502,501,500,499,498,497,496,495,494,493,492,491,490,489,488,487,486,485,484,483,482,481,480,479,478,477,476,475,474,473,472,471,470,469,468,467,466,465,464,463,462,461,460,459,458,457,456,455,454,453,452,451,450,449,448,447,446,445,444,443,442,441,440,439,438,437,436,435,434,433,432,431,430,429,428,427,426,425,424,423,422,421,420,419,418,417,416,415,414,413,412,411,410,409,408,407,406,405,404,403,402,401,400,399,398,397,396,395,394,393,392,391,390,389,388,387,386,385,384,383,382,381,380,379,378,377,376,375,374,373,372,371,370,369,368,367,366,365,364,363,362,361,360,359,358,357,356,355,354,353,352,351,350,349,348,347,346,345,344,343,342,341,340,339,338,337,336,335,334,333,332,331,330,329,328,327,326,325,324,323,322,321,320,319,318,317,316,315,314,313,312,311,310,309,308,307,306,305,304,303,302,301,300,299,298,297,296,295,294,293,292,291,290,289,288,287,286,285,284,283,282,281,280,279,278,277,276,275,274,273,272,271,270,269,268,267,266,265,264,263,262,261,260,259,258,257,256,255,254,253,252,251,250,249,248,247,246,245,244,243,242,241,240,239,238,237,236,235,234,233,232,231,230,229,228,227,226,225,224,223,222,221,220,219,218,217,216,215,214,213,212,211,210,209,208,207,206,205,204,203,202,201,200,199,198,197,196,195,194,193,192,191,190,189,188,187,186,185,184,183,182,181,180,179,178,177,176,175,174,173,172,171,170,169,168,167,166,165,164,163,162,161,160,159,158,157,156,155,154,153,152,151,150,149,148,147,146,145,144,143,142,141,140,139,138,137,136,135,134,133,132,131,130,129,128,127,126,125,124,123,122,121,120,119,118,117,116,115,114,113,112,111,110,109,108,107,106,105,104,103,102,101,100,99,98,97,96,95,94,93,92,91,90,89,88,87,86,85,84,83,82,81,80,79,78,77,76,75,74,73,72,71,70,69,68,67,66,65,64,63,62,61,60,59,58,57,56,55,54,53,52,51,50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1]

多少、複雑化していますが、ここまで書けば、多くのイテレータ用機能が使えます。
条件次第では、採用する価値があります。

Re: awewewew さん

Comments

[think49]

> もうひとつ質問なのですが、トランポリンについてあまり解説などがないのは、末尾再帰という仕組みができたからなのでしょうか？
所感なのでコメントに留めますが、「無駄が多いから」だと思います。
私は「一から作るコード」としては、トランポリンを積極的に採用する価値を感じませんでした。
「再帰呼び出しコードを少ない手間で修正する手法」としては優れていますが、付け焼刃的な印象は拭えません。
トランポリンの無駄を排除し続けると、「単純なwhile文」に終着します(パフォーマンス重視)。
トランポリンの原理を利用しつつ、現在のECMAScript仕様に合った手法に改善していくと「イテレータ」になります。
親記事にサンプルコードを追記しましたので、参考にどうぞ。

[awewewew]

通常の再帰では[再帰呼び出しした関数の終了を待つ]せいでスタックオーバーフローがおこってしまうから、再帰呼び出しをせずに再帰呼び出ししたい関数を戻り値にして関数をいったん終わらせることでスタックオーバーフローを予防しているんですね

>仰る通り、再帰ではなくなるので、
なるほど。これは再帰ではないのですか？
関数内にその関数がでてきていれば再帰と呼んでいいものだと思っていました
たしかに、関数内でその関数を呼び出していないので、再帰ではないのかもしれませんが･･･ここの理解も浅かったようです

>「再帰呼び出しコードを少ない手間で修正する手法」としては優れていますが、付け焼刃的な印象は拭えません。
仰るとおりだとおもいます
whileやfor、イテレータなどがあるから、そもそもJavaScriptでは再帰という仕組みは使わないのかもしれないですね(他の言語にもこれらの機能はあるはずですが、どうなのでしょうね･･･)

-----

質問の主題からはそれてしまいますが、質問させてください

まず、のせてくださったURLから、イテレータは
1.nextメソッドを実装している
2.value プロパティ、done プロパティがイテレータの戻り値になっている
の2つを満たすオブジェクトだと認識しています

>純粋なイテレータではない為、for-of やSpreadElementが使用できません。

そこで上の文についてですが、[純粋なイテレータ]とは何でしょうか？[反復可能オブジェクト]ではないということですか？もしそうなら、上で書いた2つの条件以外にくわえて、イテレータであるためには[反復可能オブジェクトでなければならない]ということでしょうか？

そもそも[イテレータとはなにか]の認識から間違えているのでしょうか･･･.
何か見落としがあればぜひ教えていただきたいです

長くなってしまいましたが,よろしくおねがいします

[think49]

> 関数内にその関数がでてきていれば再帰と呼んでいいものだと思っていました
関数内で別の関数を返しているので、一般には「クロージャ」と呼ばれると思います。
関数が参照する変数をメモリに保持し続ける事となり、ガベージコレクションを考えると悩ましい(ガベージコレクションはコーダが制御できません)ですが、それぞれの関数呼び出しで処理は完了している為、コールスタックが積み上がる事はありません。

> そもそもJavaScriptでは再帰という仕組みは使わないのかもしれないですね
再帰を使ってはいけない、とまでは思いません。
膨大な再帰処理のアルゴリズムを考案するにあたって、人間にとっては再帰呼び出しの方が組みやすいと感じるかもしれません。
最も、私がまだ繰り返し処理をイメージできる程に習熟していないだけかもしれませんが…。
私が主張したのは「トランポリンに必要性を感じない」です。

> [純粋なイテレータ]とは何でしょうか？[
すみません。「純粋なイテレータ」は適切な表現ではなかった為、"iterable" に訂正しました。
イテレータの定義はご認識の通りで合っています。
iterable とは「for-of で列挙可能なオブジェクト」を指します。
MDN(日本語)では「反復可能オブジェクト」と表現していますね。
https://developer.mozilla.org/ja/docs/Web/JavaScript/Guide/Iterators_and_Generators#Iterables

Answer 2

簡単に言えばこうです。

function a() {
  console.log('execute a');
  a();
  return console.log('return');
}

これ、a();を実行すると無限ループします。
そして、絶対にreturn文にたどり着きません。
ずーっとexecute aと出力され続け、そのうちスタックオーバーフローします。

関数内の処理は上から順に解決されていくので、まずa();を実行するとコンソールログを出します。
その後自分自身を呼び出します。
永遠にこれの繰り返しです。

最初に実行したa();はまだ終了していません。
自分の中から読んだa();の解決待ちで終了できないのです。
これがどんどん連鎖して、スタックに積んで待ち続けてます。
待ってるやつがスタックに溜まりすぎるのでスタックオーバーフローです。

こう書き換えると

function a() {
  console.log('execute a');
  var func = function() {
    a();
  }
  return console.log('return'), func;
}

a();を実行したら1回で終わります。
return文にたどり着いて終了できるのです。
戻ってくるのはaを呼び出すことができる関数です。

これをwhileループで呼び出せば、あたかも再帰しているかのように振舞います。
晴れて本当の無限ループの完成です。
やると無限ループするんでやらないことをお勧めしますが。

末尾呼び出しの最適化は期待しない方がいいと思います。
現状、safariだけが最適化してくれるようですね。
http://kangax.github.io/compat-table/es6/
proper tail calls (tail call optimisation)の行。

トランポリンについてあまり解説などがないのは、

単純にみんな気を付けて使っているか、スタックオーバーフロー起きた時に対処法を都度考えているか、ですかね。
あと、再帰がスタックオーバーフローするほど深くなるようなことって、実際はあまり起こらないかもしれません。
猫も杓子も再帰！とかやらない限りあまり問題にはならないような気はします。

Comments

[awewewew]

回答ありがとうございます

再帰呼び出し部分を関数の外で実行することで、再帰呼び出しした関数の実行が終了するのを待機する動作を防ぐ、ということですね
そもそも、再帰呼び出しをしないようにコードを変更してしまっているんですね･･･てっきり再帰をしているのかとおもっていました

>末尾呼び出しの最適化は期待しない方がいいと思います。
そうなのですか？じつは末尾呼び出しについては、あまり調べられていません。
関数の呼び出しが関数の末尾にあるもののこと、という認識で、JavaScriptのコンパイラ?が具体的にどのような最適化をするのかといったことまでは把握できていません(というより、解説記事を読んでもちんぷんかんぷんでした･･･)

> 単純にみんな気を付けて使っているか、スタックオーバーフロー起きた時に対処法を都度考えているか、ですかね。
再帰が行っていることは、結局は単純な繰り返しで、for, whileなどでスタックオーバーフローを発生させること無く行えるものなので、そもそも[スタックオーバーフローに気をつかってまで再帰を使う]ような場面があるのか、ともおもえてきますね

>再帰がスタックオーバーフローするほど深くなるようなことって、実際はあまり起こらないかもしれません。
そうなのですね。簡単に起こってしまうものかと思っていたので、意外です
実際はあまり起こらないことだから、トランポリンなどの解説がそもそも必要ない、ということも考えられますね

回答をしていただきありがとうございました

Answer 3

単純な話で、スタックオーバーフローはスタックがオーバーフローしてるだけです。
とりあえず例としてフィボナッチ数列の関数を用意してっと

const fib = (num) => {
  if (num < 2) return num;
  return fib(num - 1) + fib(num - 2);
}
console.log(Array(10).fill(0).map((_, i) => fib(i + 1)));
// [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

はい、ちゃんと動いているようですね。
このフィボナッチ数列関数のreturn fib(num - 1) + fib(num - 2);の行に着目してください。

実行中の関数というのはどっかのメモリ領域に保存しなければ、今どの計算してるんだっけ？という状態がわかりませんので、スタックと呼ばれる領域に保存します。
つまりスタック≒実行中関数
実行中関数は関数の実行が終了したタイミングでスタックから開放されます。

戻り値を返す為にreturn 関数実行 + 関数実行としていますが、
２つの関数実行が終わり、戻り値を返してくれない事には、この関数は一生実行しっぱなしという事ですね。

fib(10000)みたいなとても大きい数字を入れた場合を見ていきます。
fib(10000)はfib(9999)とfib(9998)の実行が終わるまでは終了しないぞと言っています。
作られたfib(9999)もfib(9998)とfib(9997)の実行が終わるまでは終了しないぞと言っています。
この調子で関数実行がネストすれば、外側の関数はずっと実行しっぱなし…最終的にブラウザが用意してるスタック領域は全て消費しつくしてもう保存出来なくなってしまいます。

この用意しているスタック数というのはブラウザによって数が違うのですが、だいたい数千〜数万です。
なので、今回のfib(10000)を実行すれば大抵どのブラウザでもスタックオーバーフローのエラーが出ます。

---

次にトランポリン関数を見ていきます。

トランポリン関数はnumという変数を保持しては居ますが、
次回計算用の関数を生成した後、関数実行は終了していますね。

これをwhile文(for文)でループさせた場合、
関数実行自体は毎回しっかり終わっているのでスタックは都度開放されます。
なら同時スタック消費量は1〜2くらいのままずっと推移することになります。

スタックはオーバーフローしませんね。

リンク先の英語記事は1ミリも読んでませんが、
こういう内容の事が英文で書かれているのでしょう。
以上を踏まえて読んでみてください。

Comments

[awewewew]

再帰呼び出し部分を関数の外で実行することで、再帰呼び出しした関数の実行が終了するのを待機する動作を防ぐ、ということですね
そもそも、再帰呼び出しをしないようにコードを変更しているんですね

ただwhile、 forを使っているだけであれば、こんなに難しい書き方をしなくてもいいのに･･･とおもってしまいます

回答ありがとうございました