Loading article…
コンピュータサイエンスにおいて、末尾呼び出しは、プロシージャの最後のアクションとして実行されるサブルーチン呼び出しです。 [1]末尾のターゲットが同じサブルーチンである場合、そのサブルーチンは末尾再帰であると言われ、これは直接再帰の特殊なケースです。末尾再帰（または末尾再帰）は特に便利で、実装で最適化するのが簡単な場合がよくあります。
末尾呼び出しは、呼び出しスタックに新しいスタック フレームを追加せずに実装できます。現在のプロシージャのフレームの大部分は不要になり、末尾呼び出しのフレームに置き換えて、必要に応じて変更することができます (プロセスのオーバーレイに似ていますが、関数呼び出し用です)。その後、プログラムは呼び出されたサブルーチンにジャンプできます。標準の呼び出しシーケンスの代わりにこのようなコードを生成することを、末尾呼び出しの削除または末尾呼び出しの最適化と呼びます。末尾呼び出しの削除により、末尾の位置にあるプロシージャ呼び出しをgotoステートメントと同じくらい効率的に実装できるため、効率的な構造化プログラミングが可能になります。Guy L. Steeleの言葉を借りれば、「一般に、プロシージャ呼び出しは、パラメータも渡す GOTO ステートメントとして便利に考えることができ、 [マシン コード] JUMP 命令として統一的にコード化できます。」[2]
すべてのプログラミング言語が末尾呼び出しの削除を必要とするわけではありません。しかし、関数型プログラミング言語では、末尾呼び出しの削除は言語標準によって保証されていることが多く、末尾再帰が同等のループと同量のメモリを使用することを許可しています。関数が自分自身を呼び出すという末尾再帰呼び出しの特殊なケースは、一般的な末尾呼び出しよりも呼び出しの削除が適している可能性があります。言語セマンティクスが一般的な末尾呼び出しを明示的にサポートしていない場合でも、コンパイラは兄弟呼び出し、つまり呼び出し元と同じ型を受け取って返す関数への末尾呼び出しを最適化できることがよくあります。[3]
説明
関数が呼び出されると、コンピュータは呼び出しが完了したら結果を持ってその場所に戻れるように、関数が呼び出された場所、つまり戻りアドレスを「記憶」しておかなければなりません。通常、この情報は呼び出しスタックに保存されます。呼び出しスタックは、呼び出し場所に到達した順序で戻り場所のリストです。末尾呼び出しの場合、呼び出し元を記憶する必要はありません。代わりに、末尾呼び出しの削除では、スタック フレームに渡す前に最小限必要な変更のみが行われ、[4]末尾で呼び出された関数は元の呼び出し元に直接戻ります。末尾呼び出しは、ソース コード内の他のすべてのステートメントの後に字句的に現れる必要はありません。呼び出し関数が末尾呼び出しの直後に戻り、末尾呼び出しの結果があればそれを返すことだけが重要です。これは、最適化の実行時に呼び出し関数がバイパスされるためです。
非再帰関数呼び出しの場合、呼び出すことができる関数の種類はそれほど多くないため、これは通常、時間とスペースを少ししか節約しない最適化です。ただし、末尾呼び出しによって再帰が発生する再帰関数または相互再帰関数を扱う場合、関数が直接的または間接的に自分自身を呼び出して、そのたびに新しい呼び出しスタック フレームを作成するため、スタック スペースと節約される戻り値の数がかなり大きくなる可能性があります。末尾呼び出しの削除により、漸近的なスタック スペース要件が線形、つまりO (n) から定数、つまりO (1) に削減されることがよくあります。そのため、末尾呼び出しの削除は、 Scheme、[5] [6]やMLファミリーの言語など、一部のプログラミング言語の標準定義で必須となっています。Scheme 言語定義では、どの構文形式が末尾コンテキストで結果を持つことを許可するかを指定することにより、末尾位置の直感的な概念を正確に形式化しています。[7]末尾呼び出しの除去により、同時に無制限の数の末尾呼び出しをアクティブにできる実装は、「適切な末尾再帰」とも呼ばれます。[5]
スペースと実行効率に加えて、継続渡しスタイル(CPS)と呼ばれる関数型プログラミングの慣用句では末尾呼び出しの排除が重要であり、そうしないとスタック スペースがすぐに不足してしまいます。
構文形式
末尾呼び出しは、関数の構文上の終了の直前に配置できます。
関数foo (データ) { a (データ);戻り値b (データ); }
ここで、 と は両方ともa(data)呼び出しb(data)ですが、 はbプロシージャが戻る前に最後に実行されるため、末尾の位置にあります。ただし、すべての末尾呼び出しが必ずしもサブルーチンの構文上の末尾に配置されるわけではありません。
関数bar (データ) { if ( a (データ)) { return b (データ); } return c (データ); }
ここで、bとの両方の呼び出しは末尾の位置にあります。これは、最初の呼び出しが構文的にはの本体
cの末尾にないにもかかわらず、それぞれが if ブランチの末尾にあるためです。bar
このコードでは:
関数foo1 (データ) {戻り値a (データ) + 1 ; }
関数foo2 (データ) { var ret = a (データ);戻り値ret ; }
関数foo3 (データ) { var ret = a (データ); return ( ret == 0 ) ? 1 :戻ります。}
への呼び出しはa(data)では末尾位置にありますfoo2が、や では末尾位置にありません。これは、戻り値を返す前に呼び出し元が戻り値を検査または変更できるようにするために、制御を呼び出し元に戻す必要があるためです
foo1。foo3
サンプルプログラム
次のプログラムはSchemeの例である: [8]
;; 階乗: number -> number ;;
n 以下のすべての正の整数の積を計算します。
( define ( factorial n ) ( if ( = n 0 ) 1 ( * n ( factorial ( - n 1 )))))
これは、乗算関数 ("*") が末尾の位置にあるため、末尾再帰スタイルで記述されていません。これは、次のコードと比較できます。
;; 階乗: number -> number ;;
n 以下のすべての正の整数の積を計算します。
( define ( factorial n ) ( fact-iter 1 n )) ( define ( fact-iter product n ) ( if ( = n 0 ) product ( fact-iter ( * product n ) ( - n 1 ))))
このプログラムは適用順序評価を前提としています。内部手続きは制御フローの最後にfact-iter自分自身を呼び出します。これにより、インタープリタまたはコンパイラは実行を再編成することができ、通常は次のようになります。[8]
階乗を呼び出す (4)
ファクトイターに電話する (1 4)
ファクトイターに電話する (4 3)
ファクトイターに電話する (12 2)
ファクトイターに電話する (24 1)
戻る 24
戻る 24
戻る 24
戻る 24
戻る 24
空間と時間の両方の観点から、 より効率的な変種に変換します。
階乗を呼び出す (4) ファクトイターに電話する (1 4) 引数を（4 3）に置き換える 引数を（12 2）に置き換える 引数を（24 1）に置き換える 戻る 24 戻る 24
この再編成により、呼び出し関数のアドレス以外の状態をスタックまたはヒープに保存する必要がなく、呼び出しスタック フレームがfact-iter中間結果のストレージに再利用されるため、スペースが節約されます。これは、プログラマーが極端に深い再帰のためにスタックまたはヒープ領域が不足することを心配する必要がないことも意味します。一般的な実装では、末尾再帰バリアントは他のバリアントよりも大幅に高速になりますが、その速度は定数倍のみです。
関数型言語で作業するプログラマーの中には、この機能を活用できるように、再帰コードを末尾再帰に書き直す人もいます。この場合、product関数に「アキュムレータ」引数 (上記の例の場合) を追加する必要があります。
cons を法とする末尾再帰
末尾再帰を法とする cons は、明示的に一度だけ設定される言語と見なされるPrologのコンパイルのコンテキストでDavid HD Warren [9]が導入した末尾再帰最適化の一般化です。これは、 1974 年にDaniel P. Friedmanと David S. Wise [10]によってLISPコンパイル手法として説明されました (ただし、名前は付けられていません) 。名前が示すように、これは、再帰呼び出し後に実行する必要がある唯一の操作が、そこから返されるリストの前に既知の値を追加すること (または、一般的には、定数の単純なデータ構築操作を実行すること) である場合に適用されます。したがって、この呼び出しは、前述のcons操作を除けば ("法")末尾呼び出しになります。ただし、再帰呼び出しから出るときにリストの先頭に値をプレフィックスすることは、再帰呼び出しに入るときにこの値を増加するリストの末尾に追加することと同じであり、暗黙のアキュムレータ パラメータの場合と同様に、副作用としてリストを構築します。次の Prolog フラグメントは、この概念を示しています。
サンプルコード
したがって、末尾再帰変換では、このような呼び出しは、最初に新しいリスト ノードを作成してそのfirstフィールドを設定し、次にノードのフィールドへのポインターを引数として末尾呼び出しを行って再帰的に埋めるという形に変換されます。再帰が遅延評価データ コンストラクターの下で保護されているrest場合、同じ効果が得られます。これは、Haskell などの遅延プログラミング言語では自動的に実現されます。
Cの例
次のコードは、リンク リストを複製する Cの再帰関数を定義します(比較のために、同等の Scheme および Prolog コードをコメントとして示しています)。
この形式では、関数は末尾再帰ではありません。再帰呼び出しが入力リストの残りを複製した後、制御が呼び出し元に戻るからです。たとえ、残りを複製する前にヘッドノードを割り当てるとしても、呼び出し後にnext再帰呼び出しの結果をフィールドに挿入する必要があります。 [a]
したがって、関数はほぼ末尾再帰です。ウォーレンの方法は、フィールドを埋める責任を再帰呼び出し自体に押し付け、その結果、末尾呼び出しになります。[b]センチネルヘッドノードを使用してコードを簡素化します。
next
呼び出し側が返されたリストの先頭に追加するのではなく、呼び出し先が増大するリストの末尾に追加します。作業は、再帰呼び出しが結果を返した後にリストの末尾から逆方向に進むのではなく、再帰呼び出しの前に、リストの先頭から順方向に行われます。したがって、これは累積パラメータ手法に似ており、再帰計算を反復計算に変換します。
この手法の特徴は、実行呼び出しスタック上に親フレームが作成され、末尾呼び出し最適化が存在する場合、末尾再帰呼び出し先がそれを独自の呼び出しフレームとして再利用できることです。
末尾再帰実装は、累積ループとして明示的に反復する実装に変換できるようになりました。
歴史
1977 年にシアトルで開催されたACMカンファレンスで発表された論文で、Guy L. Steele はGOTOと構造化プログラミングに関する議論を要約し、プロシージャの末尾位置でのプロシージャ呼び出しは、呼び出されたプロシージャへの制御の直接転送として扱うのが最適であり、通常は不要なスタック操作操作が排除されると指摘しました。[2]このような「末尾呼び出し」は、プロシージャ呼び出しが至る所にある言語であるLispでは非常に一般的であるため、この形式の最適化により、他の実装と比較してプロシージャ呼び出しのコストが大幅に削減されます。 Steele は、実装が不十分なプロシージャ呼び出しにより、プロシージャ呼び出しに比べて GOTO の方が安価であるという人為的な認識が生じていると主張しました。 Steele はさらに、「一般にプロシージャ呼び出しは、パラメータも渡す GOTO 文として便利に考えることができ、マシン コードの JUMP 命令として統一的にコード化できる」と主張し、マシン コードのスタック操作命令は「最適化と見なされます (その逆ではなく!)」[2]スティールは、Lispのよく最適化された数値アルゴリズムは、Lispの手続き呼び出しのコストがはるかに低いため、当時入手可能な商用Fortranコンパイラで生成されたコードよりも高速に実行できるという証拠を挙げました。スティールがジェラルド・ジェイ・サスマンと開発したLisp方言であるSchemeでは、末尾呼び出しの削除はどのインタープリタでも実装されることが保証されています。[11]
実施方法
末尾再帰は、一部の高級言語、特に関数型言語や論理型言語、 Lispファミリーの言語にとって重要です。これらの言語では、末尾再帰は反復処理を実装する最も一般的な方法 (場合によっては唯一の方法) です。Scheme の言語仕様では、末尾呼び出しはスタックを増やさないように最適化する必要があります。Perl では、関数名を受け取る "goto" ステートメントのバリエーションを使用して、末尾呼び出しを明示的に行うことができます。[ 12 goto &NAME;]
ただし、関数の引数とローカル変数をコール スタックに格納する言語実装 (これは、多くの言語、少なくともx86などのハードウェア スタックを備えたシステムではデフォルトの実装です) の場合、一般化された末尾呼び出し最適化 (相互末尾再帰を含む) を実装すると問題が発生します。呼び出し先のアクティベーション レコードのサイズが呼び出し元のアクティベーション レコードのサイズと異なる場合、スタック フレームの追加のクリーンアップまたはサイズ変更が必要になる場合があります。これらの場合、末尾再帰の最適化は簡単ですが、一般的な末尾呼び出し最適化を効率的に実装することは困難になる可能性があります。
例えば、Java仮想マシン（JVM）では、末尾再帰呼び出しは（既存の呼び出しスタックを再利用するため）削除できますが、一般的な末尾呼び出しは（呼び出しスタックを変更するため）削除できません。[13] [14]その結果、 JVMをターゲットとするScalaなどの関数型言語は、直接末尾再帰を効率的に実装できますが、相互末尾再帰は実装できません。
GCC 、LLVM/Clang、およびIntelコンパイラスイートは、より高い最適化レベルまたはオプションが渡された場合に、 Cおよびその他の言語の末尾呼び出し最適化を実行します。 [15] [16] [17]指定された言語構文が明示的にサポートしていない場合でも、呼び出し元と呼び出し先の戻り値の型が同等であり、両方の関数に渡される引数の型が同じであるか、呼び出しスタック上に同じ量の合計ストレージスペースを必要とすると判断できる場合はいつでも、コンパイラはこの最適化を行うことができます。[18]-foptimize-sibling-calls
さまざまな実装方法が可能です。
組み立て中
末尾呼び出しは、関数型プログラミング言語や論理型プログラミング言語のインタープリタやコンパイラによって、より効率的な反復形式に最適化されることが多い。たとえば、Schemeプログラマーは一般的にwhileループを末尾位置のプロシージャの呼び出しとして表現し、Schemeコンパイラまたはインタープリタが末尾呼び出しをより効率的なジャンプ命令に置き換えることを期待している。[19]
アセンブリを直接生成するコンパイラの場合、末尾呼び出しの除去は簡単です。スタック上のパラメータを修正した後、呼び出しオペコードをジャンプオペコードに置き換えるだけで十分です。コンパイラの観点から見ると、上記の最初の例は、最初は疑似アセンブリ言語に変換されます(実際、これは有効なx86 アセンブリです)。
foo:
Bを呼び出し、Aを呼び出し、ret
末尾呼び出しの削除により、最後の 2 行が 1 つのジャンプ命令に置き換えられます。
foo:
B を呼び出す、 Aをジャンプする
サブルーチンが完了すると、不要なステートメントを省略して、Aの戻りアドレスに直接戻ります。
fooret
通常、呼び出されるサブルーチンにはパラメータが提供される必要がある。したがって、生成されたコードは、末尾に呼び出されるサブルーチンにジャンプする前に、 A の呼び出しフレームが適切に設定されていることを確認する必要がある。たとえば、呼び出しスタックに戻りアドレスだけでなくサブルーチンのパラメータも含まれているプラットフォームでは、コンパイラは呼び出しスタックを調整するための命令を発行する必要がある場合がある。このようなプラットフォームでは、コードは次のようになる。
関数foo(データ1, データ2) B(データ1) A(データ2) を返す
(ここでdata1、 とdata2はパラメータ) コンパイラはこれを次のように翻訳する: [c]
フー:
mov reg ,[ sp + data1 ] ; スタック(sp)パラメータからdata1をスクラッチレジスタにフェッチします。
push reg ; データ1をスタックBが期待する場所に置く
Bを呼び出す；Bはデータ1を使用する
pop ; スタックからデータ1を削除する
mov reg ,[ sp + data2 ] ; スタック(sp)パラメータからdata2をスクラッチレジスタにフェッチします。
push reg ; data2をAが期待するスタックに置く
Aを呼び出す；Aはデータ2を使用する
pop ; スタックから data2 を削除します。
戻る
末尾呼び出しオプティマイザーはコードを次のように変更します。
フー:
mov reg ,[ sp + data1 ] ; スタック(sp)パラメータからdata1をスクラッチレジスタにフェッチします。
push reg ; データ1をスタックBが期待する場所に置く
Bを呼び出す；Bはデータ1を使用する
pop ; スタックからデータ1を削除する
mov reg ,[ sp + data2 ] ; スタック(sp)パラメータからdata2をスクラッチレジスタにフェッチします。
mov [ sp + data1 ], reg ; Aが期待する場所にdata2を置く
jmp A ; A は data2 を使用し、すぐに呼び出し元に戻ります。
このコードは、実行速度とスタック領域の使用の両方の点でより効率的です。
トランポリンを通して
多くのSchemeコンパイラはC を中間ターゲット コードとして使用するため、C コンパイラが末尾呼び出しを最適化しない場合でも、末尾再帰はスタックを増やさずに C でエンコードする必要があります。多くの実装では、トランポリンと呼ばれるデバイス(関数を繰り返し呼び出すコード) を使用してこれを実現しています。すべての関数はトランポリンを介して入力されます。関数が別の関数を末尾呼び出しする必要がある場合、関数を直接呼び出して結果を返すのではなく、呼び出される関数のアドレスと呼び出しパラメータをトランポリン (関数自体の呼び出し元) に返し、トランポリンは指定されたパラメータを使用してこの関数を次に呼び出す処理を行います。これにより、C スタックが拡大せず、反復を無制限に継続できます。
Groovy、Visual Basic .NET、C#などの高階関数をサポートする言語では、高階関数を使用してトランポリンを実装することができます。[20]
すべての関数呼び出しにトランポリンを使用すると、通常の C 関数呼び出しよりもコストがかかるため、少なくとも 1 つの Scheme コンパイラであるChickenでは、Andrew Appelの未発表の提案からHenry Bakerが最初に説明した手法が使用されています[21]。この手法では、通常の C 呼び出しが使用されますが、各呼び出しの前にスタック サイズがチェックされます。スタックが最大許容サイズに達すると、スタック上のオブジェクトは、すべてのライブ データを別のヒープに移動することにより、 Cheney アルゴリズムを使用してガベージ コレクションされます。その後、スタックが巻き戻され (「ポップ」され)、プログラムはガベージ コレクションの直前に保存された状態から再開されます。Baker は、「Appel の方法は、エンパイア ステート ビルから時々飛び降りることで、多数の小さなトランポリン バウンドを回避する」と述べています[21]。ガベージ コレクションにより、相互末尾再帰が無期限に継続できます。ただし、このアプローチでは、呼び出し元のスタック フレームがまだ存在するという保証がないため、C 関数呼び出しが返されないことが必要です。したがって、プログラム コードの内部的な書き換えがはるかに劇的になります(継続渡しスタイル)。
との関係その間声明
末尾再帰は、 while文、明示的な反復と関連している可能性があり、例えば次のように変換します。
手順foo( x )
if p ( x )
return bar( x )
else
return foo(baz( x ))
の中へ
手順foo( x )
while true
if p ( x )
return bar( x )
else
x ← baz( x )
ここで、x は複数の変数を含むタプルである可能性があります。その場合、依存関係が尊重されるように、代入ステートメント x ← baz( x ) を実装する際に注意する必要があります。補助変数を導入するか、 swap構造を使用する必要がある場合があります。
より一般的には、
手順foo( x )
、 p ( x )
の場合は bar( x )
を返し、 q ( x )
の場合はbaz( x )を返す
...
そうでなければ、 r ( x )
の場合はfoo(qux( x ))を返す。
...
それ以外の場合は
foo(quux( x ))
を返す
に変換できる
手順foo( x )
がtrueの場合 p ( x )を
返し、そうでない場合はq ( x )
を返しbaz( x )
を返す
...
そうでなければ、 r ( x )
x ←qux( x )
...
そうでない場合は
x ← quux( x )
たとえば、このJuliafactプログラムは階乗の
非末尾再帰定義を提供します。
関数階乗( n )
n == 0の場合
戻り値1
それ以外
n *階乗( n - 1 )を返す
終わり
終わり
確かに、n * factorial(n - 1)は の呼び出しをラップします。しかし、アキュムレータと呼ばれるfactorial引数を追加することで、末尾再帰定義に変換できます。[8]a
fact_iterこの Julia プログラムは、階乗の
末尾再帰定義を提供します。
関数階乗( n :: Integer 、a :: Integer )
n == 0の場合:
返す
それ以外
階乗を返す( n - 1 , n * a )
終わり
終わり
関数階乗( n ::整数)
階乗を返す( n , 1 )
終わり
fact_iterこの Julia プログラムは階乗の
反復定義を提供します。
function fact_iter ( n :: Integer , a :: Integer ) while n > 0 a = n * a n = n - 1 end return a end
関数factorial ( n :: Integer ) return fact_iter ( n , one ( n ))終了
言語サポート
- Clojure – Clojureには
recur特別な形式があります。[22] - Common Lisp – 速度を最適化するためにコンパイル時に末尾呼び出し最適化を実行する実装もあります
- Elixir – Elixirは、現在BEAM VMをターゲットにしているすべての言語と同様に、末尾呼び出し最適化を実装しています[23] 。
- ニレ– はい[24]
- アーラン– はい
- F# – F#は可能な場合はデフォルトでTCOを実装します[25]
- ゴー– サポートなし[26]
- ハスケル– はい[27]
- JavaScript – ECMAScript 6.0準拠のエンジンは末尾呼び出し[28]を持つべきであるが、これはSafari / WebKit [29]では現在実装されているが、V8とSpiderMonkeyでは拒否されている。
- Kotlin –
tailrec関数の修飾子を持つ[30] - Lua – 末尾再帰は言語定義によって要求される[31]
- Objective-C – コンパイラは、-O1 (またはそれ以上) のオプションが指定されている場合に末尾呼び出しを最適化しますが、自動参照カウント(ARC)によって追加された呼び出しによって簡単に妨害されます。
- OCaml – はい
- Perl – 関数名を取る「goto」ステートメントのバリエーションで明示的に記述する:
goto &NAME;[32] - PureScript – はい
- Python – Pythonの標準実装では末尾呼び出し最適化は実行されませんが、サードパーティのモジュールを使用することでこれを実行することが可能です。[33]言語の発明者であるGuido van Rossumは、末尾呼び出しの削除によってスタックトレースが変更され、デバッグが困難になると主張し、代わりに明示的な反復処理を使用するようにプログラマーに推奨しています。[34]このため、Pythonでは末尾呼び出し最適化が実装されないことが予想されます。
- R – はい、R.4.4.0でtailcall()関数が導入されました[35]
- ラケット– はい[36]
- Ruby – はい、ただしデフォルトでは無効になっています[37]
- Rust – 末尾呼び出し最適化は限られた状況で行われる可能性があるが、保証されているわけではない[38]
- Scala – 末尾再帰関数はコンパイラによって自動的に最適化されます。このような関数にはオプションで注釈を付けることができ
@tailrec、末尾再帰でない場合はコンパイルエラーになります[39] - スキーム– 言語定義で必須[40] [41]
- スイフト– いくつかのケース（2014年現在）。[42]
- Tcl – Tcl 8.6以降、Tclにはtailcallコマンドがあります[43]
- ジグ– はい[44]
参照
無料辞書のウィクショナリーで末尾再帰を調べてください。
注記
- ^ このように:
if ( ls != NULL ) { head = malloc ( sizeof * head ); head -> value = ls -> value ; head -> next = duplicate ( ls -> next ); }
- ^ このように:
if ( ls != NULL ) { head = malloc ( sizeof * head ); head -> value = ls -> value ; duplicate ( ls -> next , & ( head -> next ) ); }
- ^ 命令
callはまず現在のコード位置をスタックにプッシュし、次にラベルで示されたコード位置への無条件ジャンプを実行しますret。命令はまずスタックからコード位置をポップし、次に取得したコード位置への無条件ジャンプを実行します。
参考文献
- ^ Steven Muchnick、Muchnick and Associates (1997 年 8 月 15 日)。Advanced Compiler Design Implementation。Morgan Kaufmann。ISBN 978-1-55860-320-2。
- ^ abc Steele, Guy Lewis (1977)。「「高価なプロシージャ コール」神話の打破、またはプロシージャ コールの実装が有害であると考えられる、または LAMBDA: 究極の GOTO」。1977年ACM年次会議議事録。pp. 153–162。doi : 10.1145 /800179.810196。hdl :1721.1/5753。ISBN 978-1-4503-2308-6. S2CID 9807843。
- ^ 「LLVM ターゲット非依存コードジェネレーター — LLVM 7 ドキュメント」。llvm.org。
- ^ 「再帰 - 末尾呼び出しのスタックメモリ使用量 - 理論計算機科学」 Cstheory.stackexchange.com. 2011-07-29 . 2013-03-21に閲覧。
- ^ ab 「アルゴリズム言語スキームに関する改訂版^6レポート」 R6rs.org 。 2013年3月21日閲覧。
- ^ 「アルゴリズム言語スキームに関する改訂版^6レポート - 理論的根拠」 R6rs.org . 2013年3月21日閲覧。
- ^ 「アルゴリズム言語スキームに関する改訂版^6レポート」 R6rs.org 。 2013年3月21日閲覧。
- ^ abc Sussman, GJ; Abelson, Hal (1984). コンピュータプログラムの構造と解釈。ケンブリッジ、マサチューセッツ州：MITプレス。ISBN 0-262-01077-1。
- ^ DHD Warren、DAI研究報告書141、エディンバラ大学、1980年。
- ^ Daniel P. Friedman および David S. Wise、「技術レポート TR19: 構造化再帰の反復への展開」、インディアナ大学、1974 年 12 月。PDF はこちらから入手できます (Web アーカイブ コピーはこちら)。
- ^ R5RS Sec. 3.5、Richard Kelsey、William Clinger、Jonathan Rees、他 (1998 年 8 月)。「アルゴリズム言語スキームに関する改訂レポート」。高階および記号計算。11 (1): 7–105。doi : 10.1023 /A:1010051815785。S2CID 14069423 。
- ^ 連絡先の詳細。「goto」。perldoc.perl.org 。 2013年3月21日閲覧。
- ^ 「末尾呼び出しと末尾再帰の違いは何ですか?」、Stack Overflow
- ^ 「JVM は末尾呼び出しの最適化にどのような制限を課すのか」、Programmers Stack Exchange
- ^ Lattner, Chris. 「LLVM 言語リファレンスマニュアル、セクション: LLVM ターゲット非依存コードジェネレータ、サブ: 末尾呼び出し最適化」。LLVMコンパイラインフラストラクチャ。LLVM プロジェクト。2018年6 月 24 日閲覧。
- ^ 「GNU コンパイラ コレクション (GCC) の使用: 最適化オプション」gcc.gnu.org。
- ^ 「foptimize-sibling-calls」. software.intel.com .
- ^ 「C++ 末尾呼び出しへの対処」。
- ^ Probst, Mark (2000 年 7 月 20 日). 「gcc の適切な末尾再帰」. GCC プロジェクト. 2015 年3 月 10 日閲覧。
- ^ サミュエル・ジャック、「Bouncing on your tail（尻尾で跳ねる）」。Functional Fun。2008年4月9日。
- ^ ヘンリー・ベイカー、「CONS は議論を否定すべきではない、第 2 部: MTA に関するチェイニー」
- ^ "(recur expr*)". clojure.org .
- ^ 「再帰」elixir-lang.github.com。
- ^ Czaplicki, Evan. 「Elm での関数型プログラミング: 末尾呼び出しの除去」
- ^ 「F# での末尾呼び出し」。msdn。Microsoft。2011年 7 月 8 日。
- ^ 「提案: Go 2: 末尾呼び出しをサポートするために become ステートメントを追加する」。github.com。
- ^ 「末尾再帰 - HaskellWiki」. wiki.haskell.org . 2019年6月8日閲覧。
- ^ Beres-Deak, Adam. 「一見の価値あり: Douglas Crockford が 2014 年の JavaScript の新たな優れた点について語る」bdadam.com。
- ^ 「WebKit の ECMAScript 6」。2015 年 10 月 13 日。
- ^ 「関数: infix、vararg、tailrec - Kotlinプログラミング言語」。Kotlin 。
- ^ 「Lua 5.3 リファレンスマニュアル」。www.lua.org。
- ^ "goto - perldoc.perl.org". perldoc.perl.org .
- ^ “baruchel/tco”. GitHub . 2022年3月29日.
- ^ Rossum, Guido Van (2009 年 4 月 22 日)。「Neopythonic: 末尾再帰の除去」。
- ^ 「R 4.4.0 の新機能」www.jumpingrivers.com 2024-04-25 2024-04-28閲覧。
- ^ 「Racket リファレンス」. docs.racket-lang.org .
- ^ 「Ruby 末尾呼び出しの最適化」。ruby -doc.org。
- ^ 「Rust FAQ」. prev.rust-lang.org .
- ^ 「Scala 標準ライブラリ 2.13.0 - scala.annotation.tailrec」。www.scala-lang.org 。2019年 6 月 20 日閲覧。
- ^ 「アルゴリズム言語Schemeに関する改訂版^5レポート」www.schemers.org。
- ^ 「アルゴリズム言語スキームに関する改訂版^6レポート」www.r6rs.org。
- ^ 「Swift は末尾呼び出し最適化を実装していますか?」 2014 年. 2024 年3 月 13 日閲覧。
- ^ 「tailcall マニュアル ページ - Tcl 組み込みコマンド」。www.tcl.tk。
- ^ 「ドキュメント - Zig プログラミング言語」。