「Example4.6」の編集履歴（バックアップ）一覧はこちら
「Example4.6」(2011/02/24 (木) 08:32:40) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
#co(){
4.6 Tail Recursion
Consider the following function to compute the greatest common divisor of two given numbers.
}
** 4.6 末尾再帰
与えられた２つの数の最大公約数を計算する、次の関数について考えてみましょう。
def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
#co(){
Using our substitution model of function evaluation, gcd(14, 21) evaluates as follows:
}
関数評価の置き換えモデルを用いると、gcd(14, 21) は次のように評価されます。
gcd(14, 21)
→ if (21 == 0) 14 else gcd(21, 14 % 21)
→ if (false) 14 else gcd(21, 14 % 21)
→ gcd(21, 14 % 21)
→ gcd(21, 14)
→ if (14 == 0) 21 else gcd(14, 21 % 14)
→ → gcd(14, 21 % 14)
→ gcd(14, 7)
→ if (7 == 0) 14 else gcd(7, 14 % 7)
→ → gcd(7, 14 % 7)
→ gcd(7, 0)
→ if (0 == 0) 7 else gcd(0, 7 % 0)
→ → 7
#co(){
Contrast this with the evaluation of another recursive function, factorial: }
もう一つの再帰関数 factorial の評価と比較して下さい。
def factorial(n: Int): Int = if (n == 0) 1 else n * factorial(n - 1)
#co(){
The application factorial(5) rewrites as follows:
}
factorial(5) の適用は次のように書き換えます。
factorial(5)
→ if (5 == 0) 1 else 5 * factorial(5 - 1)
→ 5 * factorial(5 - 1)
→ 5 * factorial(4)
→ . . . → 5 * (4 * factorial(3))
→ . . . → 5 * (4 * (3 * factorial(2)))
→ . . . → 5 * (4 * (3 * (2 * factorial(1))))
→ . . . → 5 * (4 * (3 * (2 * (1 * factorial(0))))
→ . . . → 5 * (4 * (3 * (2 * (1 * 1))))
→ . . . → 120
#co(){
There is an important difference between the two rewrite sequences: The terms in the rewrite sequence of gcd have again and again the same form. As evaluation proceeds, their size is bounded by a constant. By contrast, in the evaluation of factorial we get longer and longer chains of operands which are then multiplied in the last part of the evaluation sequence.
}
２つの書き換え列には重要な違いがあります。gcd の書き換え列の項は、同じ形を繰り返しています。評価が進んでもその大きさは一定に抑えられています。対照的に factorial の評価では、オペランドの列はどんどん長くなり、評価列の最後でそれらは掛け合わされます。
#co(){
Even though actual implementations of Scala do not work by rewriting terms, they nevertheless should have the same space behavior as in the rewrite sequences. In the implementation of gcd, one notes that the recursive call to gcd is the last action performed in the evaluation of its body. One also says that gcd is "tail-recursive". The final call in a tail-recursive function can be implemented by a jump back to the beginning of that function. The arguments of that call can overwrite the parameters of the current instantiation of gcd, so that no new stack space is needed. Hence, tail recursive functions are iterative processes, which can be executed in constant space.
}
Scala の実際の実装が項書き換えで行われていないとしても、やはり、書き換え列と同様の空間的な振る舞いをします。gcd の実装をみると、gcd の再帰呼び出しは評価本体の最後のアクションであることに気付きます。gcd は「&bold(){末尾再帰的}」だとも呼ばれます。末尾再帰関数の最後の呼び出しは、関数の先頭への戻りジャンプとして実装できます。その呼び出しの引数は、gcd の現在のインスタンスの引数を上書きできるので、新しいスタック空間を必要としません。ですから末尾再帰関数は繰り返し処理であり、一定の空間で実行できます。
#co(){
By contrast, the recursive call in factorial is followed by a multiplication. Hence, a new stack frame is allocated for the recursive instance of factorial, and is deallocated after that instance has finished. The given formulation of the factorial function is not tail-recursive; it needs space proportional to its input parameter for its execution.
}
対照的に factorial の再帰呼び出しでは、掛け算があとで施されます。ですから新しいスタックフレームが factorial の再帰インスタンス用に割り当てられ、インスタンス終了後に割り当てが除かれます。この階乗関数の設計は末尾再帰的ではありません。実行するには入力パラメータに比例した空間が必要となります。
#co(){
More generally, if the last action of a function is a call to another (possibly the same) function, only a single stack frame is needed for both functions. Such calls are called "tail calls". In principle, tail calls can always re-use the stack frame of the calling function. However, some run-time environments (such as the Java VM) lack the primitives to make stack frame re-use for tail calls efficient. A production quality Scala implementation is therefore only required to re-use the stack frame of a directly tail-recursive function whose last action is a call to itself. Other tail calls might be optimized also, but one should not rely on this across implementations.
Exercise 4.6.1 Design a tail-recursive version of factorial.
}
より一般的には、もし関数の最後のアクションが他の (同じでも可) 関数の呼び出しであれば、両方の関数は一つのスタックフレームだけで充分です。そのような呼び出しは「末尾呼び出し(tail call)」と呼ばれます。原理的には、末尾呼び出しは常に呼び出した関数のスタックフレームを再利用できます。しかし (Java VM のような) いくつかの実行時環境では、末尾呼び出しでのスタックフレーム再利用を効率化するプリミティブに欠けています。ですから製品品質の Scala の実装では、直接的な末尾再帰(最後のアクションが自分自身の呼び出しとなる再帰)のスタックフレーム再利用だけが要求されています。他の末尾呼び出しも最適化されるかもしれませんが、多くの実装でそうなるということは、当てにすべきではありません。
&b(){演習 4.6.1 } factorial の末尾再帰版をデザインしなさい。
#center(){[[前ページ>Example4.5]] [[ 4 章>ExampleChap4]] [[目次>ScalaByExample和訳]] [[次ページ>ExampleChap5]]}
----
- お疲れさまです。「評価が進んでもその大きさは定数で・・・」の「定数で」は「一定に」の方が適しているように思います。 -- ryugate (2008-05-19 22:13:10)
- あちこちのご指摘どうもありがとうございます＞ryugateさん。現時点ではとりあえず誤字誤訳も含めてまずは一巡翻訳しようと考えております。その間に皆さんに色々ご指摘頂き、纏めて修正していこうかと。訳語などもどこまで日本語にするかあるいはカタカナにするかなど迷っている箇所が多いので、気軽にアドバイス頂ければと思います。 -- tmiya (2008-05-23 07:06:24)
#comment
#co(){
4.6 Tail Recursion
Consider the following function to compute the greatest common divisor of two given numbers.
}
#setmenu2(ex-r-menu)
** 4.6 末尾再帰
与えられた２つの数の最大公約数を計算する、次の関数について考えてみましょう。
def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
#co(){
Using our substitution model of function evaluation, gcd(14, 21) evaluates as follows:
}
関数評価の置き換えモデルを用いると、gcd(14, 21) は次のように評価されます。
gcd(14, 21)
→ if (21 == 0) 14 else gcd(21, 14 % 21)
→ if (false) 14 else gcd(21, 14 % 21)
→ gcd(21, 14 % 21)
→ gcd(21, 14)
→ if (14 == 0) 21 else gcd(14, 21 % 14)
→ → gcd(14, 21 % 14)
→ gcd(14, 7)
→ if (7 == 0) 14 else gcd(7, 14 % 7)
→ → gcd(7, 14 % 7)
→ gcd(7, 0)
→ if (0 == 0) 7 else gcd(0, 7 % 0)
→ → 7
#co(){
Contrast this with the evaluation of another recursive function, factorial: }
もう一つの再帰関数 factorial の評価と比較して下さい。
def factorial(n: Int): Int = if (n == 0) 1 else n * factorial(n - 1)
#co(){
The application factorial(5) rewrites as follows:
}
factorial(5) の適用は次のように書き換えます。
factorial(5)
→ if (5 == 0) 1 else 5 * factorial(5 - 1)
→ 5 * factorial(5 - 1)
→ 5 * factorial(4)
→ . . . → 5 * (4 * factorial(3))
→ . . . → 5 * (4 * (3 * factorial(2)))
→ . . . → 5 * (4 * (3 * (2 * factorial(1))))
→ . . . → 5 * (4 * (3 * (2 * (1 * factorial(0))))
→ . . . → 5 * (4 * (3 * (2 * (1 * 1))))
→ . . . → 120
#co(){
There is an important difference between the two rewrite sequences: The terms in the rewrite sequence of gcd have again and again the same form. As evaluation proceeds, their size is bounded by a constant. By contrast, in the evaluation of factorial we get longer and longer chains of operands which are then multiplied in the last part of the evaluation sequence.
}
２つの書き換え列には重要な違いがあります。gcd の書き換え列の項は、同じ形を繰り返しています。評価が進んでもその大きさは一定に抑えられています。対照的に factorial の評価では、オペランドの列はどんどん長くなり、評価列の最後でそれらは掛け合わされます。
#co(){
Even though actual implementations of Scala do not work by rewriting terms, they nevertheless should have the same space behavior as in the rewrite sequences. In the implementation of gcd, one notes that the recursive call to gcd is the last action performed in the evaluation of its body. One also says that gcd is "tail-recursive". The final call in a tail-recursive function can be implemented by a jump back to the beginning of that function. The arguments of that call can overwrite the parameters of the current instantiation of gcd, so that no new stack space is needed. Hence, tail recursive functions are iterative processes, which can be executed in constant space.
}
Scala の実際の実装が項書き換えで行われていないとしても、やはり、書き換え列と同様の空間的な振る舞いをします。gcd の実装をみると、gcd の再帰呼び出しは評価本体の最後のアクションであることに気付きます。gcd は「末尾再帰的」だとも呼ばれます。末尾再帰関数の最後の呼び出しは、関数の先頭への戻りジャンプとして実装できます。その呼び出しの引数は、gcd の現在のインスタンスのパラメータを上書きできるので、新しいスタック空間を必要としません。ですから末尾再帰関数は繰り返し処理であり、一定の空間で実行できます。
#co(){
By contrast, the recursive call in factorial is followed by a multiplication. Hence, a new stack frame is allocated for the recursive instance of factorial, and is deallocated after that instance has finished. The given formulation of the factorial function is not tail-recursive; it needs space proportional to its input parameter for its execution.
}
対照的に factorial の再帰呼び出しでは、掛け算があとで施されます。ですから新しいスタックフレームが factorial の再帰インスタンス用に割り当てられ、インスタンス終了後に割り当てが除かれます。この階乗関数の設計は末尾再帰的ではありません。実行するには入力パラメータに比例した空間が必要となります。
#co(){
More generally, if the last action of a function is a call to another (possibly the same) function, only a single stack frame is needed for both functions. Such calls are called "tail calls". In principle, tail calls can always re-use the stack frame of the calling function. However, some run-time environments (such as the Java VM) lack the primitives to make stack frame re-use for tail calls efficient. A production quality Scala implementation is therefore only required to re-use the stack frame of a directly tail-recursive function whose last action is a call to itself. Other tail calls might be optimized also, but one should not rely on this across implementations.
Exercise 4.6.1 Design a tail-recursive version of factorial.
}
より一般的には、もし関数の最後のアクションが他の (同じでも可) 関数の呼び出しであれば、両方の関数は一つのスタックフレームだけで充分です。そのような呼び出しは「末尾呼び出し(tail call)」と呼ばれます。原理的には、末尾呼び出しは常に呼び出した関数のスタックフレームを再利用できます。しかし (Java VM のような) いくつかの実行時環境では、末尾呼び出しでのスタックフレーム再利用を効率化するプリミティブに欠けています。ですから製品品質の Scala の実装では、直接的な末尾再帰(最後のアクションが自分自身の呼び出しとなる再帰)のスタックフレーム再利用だけが要求されています。他の末尾呼び出しも最適化されるかもしれませんが、多くの実装でそうなるということは、当てにすべきではありません。
&b(){演習 4.6.1 } factorial の末尾再帰版をデザインしなさい。
#center(){[[前ページ>Example4.5]] [[ 4 章>ExampleChap4]] [[目次>ScalaByExample和訳]] [[次ページ>ExampleChap5]]}
----
- お疲れさまです。「評価が進んでもその大きさは定数で・・・」の「定数で」は「一定に」の方が適しているように思います。 -- ryugate (2008-05-19 22:13:10)
- あちこちのご指摘どうもありがとうございます＞ryugateさん。現時点ではとりあえず誤字誤訳も含めてまずは一巡翻訳しようと考えております。その間に皆さんに色々ご指摘頂き、纏めて修正していこうかと。訳語などもどこまで日本語にするかあるいはカタカナにするかなど迷っている箇所が多いので、気軽にアドバイス頂ければと思います。 -- tmiya (2008-05-23 07:06:24)
#comment
