53

関数型言語である程度の経験を積んだ後、私は Java で再帰をより多く使用するようになりました - しかし、この言語の呼び出しスタックは約 1000 と比較的浅いようです。

コールスタックを大きくする方法はありますか? Erlang のように、何百万もの呼び出しが深い関数を作成できますか?

Project Euler の問題をやっていると、このことにますます気づきます。

ありがとう。

4

10 に答える 10

90

スタック サイズを増やすと、一時的な包帯としてのみ機能します。他の人が指摘しているように、本当に必要なのはテール コールの削除ですが、Java にはさまざまな理由でこれがありません。ただし、必要に応じてごまかすことができます。

手に赤い錠剤？よし、こっち向いて。

スタックをヒープに交換する方法はいくつかあります。たとえば、関数内で再帰呼び出しを行う代わりに、評価時に呼び出しを行う遅延データ構造を返すようにします。その後、Java の for-construct を使用して「スタック」を巻き戻すことができます。例を挙げて説明します。次の Haskell コードを検討してください。

map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = (f x) : map f xs

この関数はリストの末尾を評価しないことに注意してください。したがって、関数は実際には再帰呼び出しを行う必要はありません。Haskell では、実際にはテールのサンクを返します。これは、必要な場合に呼び出されます。Java でも同じことができます (これはFunctional Javaのクラスを使用します)。

public <B> Stream<B> map(final F<A, B> f, final Stream<A> as)
  {return as.isEmpty()
     ? nil()
     : cons(f.f(as.head()), new P1<Stream<A>>()
         {public Stream<A> _1()
           {return map(f, as.tail);}});}

type の値と、_1() が呼び出されたときにストリームの残りを返すサンクのようなtype のStream<A>値で構成されることに注意してください。確かに再帰のように見えますが、マップへの再帰呼び出しは行われず、Stream データ構造の一部になります。AP1

これは、通常の for-construct で巻き戻すことができます。

for (Stream<B> b = bs; b.isNotEmpty(); b = b.tail()._1())
  {System.out.println(b.head());}

Project Euler について話していたので、別の例を次に示します。このプログラムは相互に再帰的な関数を使用しており、数百万回の呼び出しでもスタックを破壊しません:

import fj.*; import fj.data.Natural;
import static fj.data.Enumerator.naturalEnumerator;
import static fj.data.Natural.*; import static fj.pre.Ord.naturalOrd;
import fj.data.Stream; import fj.data.vector.V2;
import static fj.data.Stream.*; import static fj.pre.Show.*;

public class Primes
  {public static Stream<Natural> primes()
    {return cons(natural(2).some(), new P1<Stream<Natural>>()
       {public Stream<Natural> _1()
         {return forever(naturalEnumerator, natural(3).some(), 2)
                 .filter(new F<Natural, Boolean>()
                   {public Boolean f(final Natural n)
                      {return primeFactors(n).length() == 1;}});}});}

   public static Stream<Natural> primeFactors(final Natural n)
     {return factor(n, natural(2).some(), primes().tail());}

   public static Stream<Natural> factor(final Natural n, final Natural p,
                                        final P1<Stream<Natural>> ps)
     {for (Stream<Natural> ns = cons(p, ps); true; ns = ns.tail()._1())
          {final Natural h = ns.head();
           final P1<Stream<Natural>> t = ns.tail();
           if (naturalOrd.isGreaterThan(h.multiply(h), n))
              return single(n);
           else {final V2<Natural> dm = n.divmod(h);
                 if (naturalOrd.eq(dm._2(), ZERO))
                    return cons(h, new P1<Stream<Natural>>()
                      {public Stream<Natural> _1()
                        {return factor(dm._1(), h, t);}});}}}

   public static void main(final String[] a)
     {streamShow(naturalShow).println(primes().takeWhile
       (naturalOrd.isLessThan(natural(Long.valueOf(a[0])).some())));}}

スタックをヒープに交換するためにできるもう 1 つの方法は、複数のスレッドを使用することです。再帰呼び出しを行う代わりに、呼び出しを行うサンクを作成し、このサンクを新しいスレッドに渡し、現在のスレッドが関数を終了できるようにするという考え方です。これは Stackless Python などの背後にある考え方です。

以下は Java での例です。import static句なしで見るのが少し不透明であることをお詫びします。

public static <A, B> Promise<B> foldRight(final Strategy<Unit> s,
                                          final F<A, F<B, B>> f,
                                          final B b,
                                          final List<A> as)
  {return as.isEmpty()
     ? promise(s, P.p(b))
     : liftM2(f).f
         (promise(s, P.p(as.head()))).f
         (join(s, new P1<Promise<B>>>()
            {public Promise<B> _1()
              {return foldRight(s, f, b, as.tail());}}));}

Strategy<Unit> sはスレッド プールに支えられており、promise関数はサンクをスレッド プールに渡し、 を返しますPromise。これは によく似ていますがjava.util.concurrent.Future、より優れています。こちらをご覧ください。要点は、上記のメソッドが O(1) stackで右再帰データ構造を右に折り畳むことです。これには通常、末尾呼び出しの削除が必要です。そのため、多少の複雑さと引き換えに、TCE を効果的に達成しました。この関数を次のように呼び出します。

Strategy<Unit> s = Strategy.simpleThreadStrategy();
int x = foldRight(s, Integers.add, List.nil(), range(1, 10000)).claim();
System.out.println(x); // 49995000

この後者の手法は、非線形再帰に対して完全にうまく機能することに注意してください。つまり、末尾呼び出しを持たないアルゴリズムでも一定のスタックで実行されます。

他にできることは、トランポリンと呼ばれるテクニックを使用することです。トランポリンは、データ構造として具体化された、ステップ実行可能な計算です。Functional Java ライブラリーには、私が作成したデータ型が含まれています。Trampolineこれにより、あらゆる関数呼び出しを末尾呼び出しに効果的に変換できます。例として、一定のスタックで右に折りたたむトランポリンを次に示します。foldRightC

public final <B> Trampoline<B> foldRightC(final F2<A, B, B> f, final B b)
  {return Trampoline.suspend(new P1<Trampoline<B>>()
    {public Trampoline<B> _1()
      {return isEmpty()
         ? Trampoline.pure(b)
         : tail().foldRightC(f, b).map(f.f(head()));}});}

これは、複数のスレッドを使用する場合と同じ原理ですが、各ステップを独自のスレッドで呼び出すのではなく、 を使用するのと非常によく似た方法でヒープ上に各ステップを構築し、 を使用してStreamすべてのステップを 1 つのループで実行しますTrampoline.run。

于 2009-05-14T03:14:04.237 に答える
40

これらのパラメーターを使用できると思います

-ss Stacksize を使用してネイティブ スタック サイズを増やすか、

-oss Stacksize を使用して Java スタック サイズを増やします。

デフォルトのネイティブ スタック サイズは 128k で、最小値は 1000 バイトです。デフォルトの Java スタック サイズは 400k で、最小値は 1000 バイトです。

http://edocs.bea.com/wls/docs61/faq/java.html#251197

編集：

最初のコメント (Chuck's) を読んだ後、質問を読み直し、別の回答を読んだ後、質問を単に「スタックサイズを増やす」と解釈したことを明確にしたいと思います。関数型プログラミング (私がその表面をなぞっただけのプログラミング パラダイム) のように、無限のスタックを持つことができると言うつもりはありませんでした。

于 2009-05-13T21:38:32.490 に答える
24

末尾再帰を使用するかどうかは JVM 次第です。それらのいずれかが使用するかどうかはわかりませんが、それに依存するべきではありません。特に、実際に使用する再帰のレベル数に厳しい制限があり、それぞれが占有するスタック スペースを正確に把握していない限り、スタック サイズの変更が正しいことはほとんどありません。非常に壊れやすい。

基本的に、無制限再帰用に構築されていない言語では、無制限再帰を使用しないでください。残念ながら、代わりに反復を使用する必要があります。そして、はい、それは時々ちょっとした痛みになることがあります:(

于 2009-05-13T21:38:40.417 に答える
9

質問する必要がある場合は、おそらく何か間違ったことをしている可能性があります。

さて、Java でデフォルトのスタックを増やす方法をおそらく見つけることができますが、増やしたスタックに頼るのではなく、やりたいことを行う別の方法を本当に見つける必要があるという点で、私の 2 セントを追加さ​​せてください。

Java 仕様では、JVM が末尾再帰最適化手法を実装することを必須とはしていないため、この問題を回避する唯一の方法は、保持する必要があるローカル変数/パラメーターの数を減らすことによって、スタック プレッシャーを軽減することです。追跡するか、理想的には再帰のレベルを大幅に減らすか、再帰をまったく使用せずに書き直すだけです。

于 2009-05-13T21:39:46.513 に答える
8

ほとんどの関数型言語は末尾再帰をサポートしています。ただし、ほとんどの Java コンパイラはこれをサポートしていません。代わりに、別の関数呼び出しを行います。これは、実行できる再帰呼び出しの数に常に上限があることを意味します (最終的にはスタック領域が不足するため)。

末尾再帰では、再帰している関数のスタック フレームを再利用するため、スタックに同じ制約がありません。

于 2009-05-13T21:38:40.137 に答える
7

Java VM 上で動作する Clojure は、テール コールの最適化を実装したいと考えていますが、JVM バイトコードの制限により実装できません (詳細はわかりません)。結果として、適切な末尾再帰から期待されるいくつかの基本的な機能を実装する特別な「再帰」形式でのみ、それ自体を助けることができます。

とにかく、これは、JVM が現在テール コールの最適化をサポートできないことを意味します。JVM で一般的なループ構造として再帰を使用しないことを強くお勧めします。私の個人的な見解では、Java は十分に高度な言語ではありません。

于 2009-05-13T23:46:55.370 に答える
7

これはコマンドラインで設定できます。

Java -Xss8M クラス

于 2009-05-13T21:40:25.263 に答える
1 
public static <A, B> Promise<B> foldRight(final Strategy<Unit> s,
                                          final F<A, F<B, B>> f,
                                          final B b,
                                          final List<A> as)
{
    return as.isEmpty() ? promise(s, P.p(b))
    : liftM2(f).f(promise(s, P.p(as.head())))
      .f(join(s, new F<List<A>, P1<Promise<B>>>()
        {
             public Promise<B> f(List<A> l)
             {
                 return foldRight(s, f, b, l);
             }
         }.f(as.tail())));
}
于 2011-01-13T08:21:37.267 に答える
0

私は同じ問題に遭遇し、再帰を for ループに書き直すことになり、それでうまくいきました。

于 2013-11-27T09:36:53.140 に答える
-1

Eclipse を使用している場合は、-xss2mを vm 引数として設定します。

また

-xss2m コマンドラインで直接。

java -xss2m classname
于 2012-03-02T12:17:16.670 に答える