java 8を使用したテール再帰の設計

Question

私は、talkで次の例を試して、java8の末尾再帰を理解していました。ここでTailCall

public class TailCalls { 
    public static <T> TailCall<T> call(final TailCall<T> nextcall) { 
     return nextcall; 
    } 

    public static <T> TailCall<T> done(final T value) { 
     return new TailCall<T>() { 
      @Override 
      public boolean isComplete() { 
       return true; 
      } 

      @Override 
      public T result() { 
       return value; 
      } 

      @Override 
      public TailCall<T> apply() { 
       throw new Error("not implemented."); 
      } 
     }; 
    } 
} 

を使用する

@FunctionalInterface 
public interface TailCall<T> { 
    TailCall<T> apply(); 

    default boolean isComplete() { 
     return false; 
    } 

    default T result() { 
     throw new Error("not implemented"); 
    } 

    default T get() { 
     return Stream.iterate(this, TailCall::apply).filter(TailCall::isComplete) 
               .findFirst().get().result(); 
    } 
} 

ユーティリティクラスは、末尾再帰の使用は、次のとおりです。

public class Main { 

    public static TailCall<Integer> factorial(int fact, int n) { 
     if (n == 1) { 
      return TailCalls.done(fact); 
     } else { 
      return TailCalls.call(factorial(fact * n, n-1)); 
     } 
    } 

    public static void main(String[] args) { 
     System.out.println(factorial(1, 5).get()); 
     } 
} 

それは正しく働いたが、我々は必要としないような気がしますTailCall::getを使用して結果を計算します。私の理解あたりとして、我々は直接使用して結果を計算することができます

System.out.println(factorial(1, 5).result()); 

の代わり：

System.out.println(factorial(1, 5).get()); 

を私はTailCall::getの要旨をしないのです場合は私に知らせてください。

Answer 1

この例では間違いがあります。テールコールの最適化を行わずに単純な再帰を実行します。あなたは、基本ケースにThread.dumpStackを追加することで、これを見ることができます：あなたはfactorialへの複数の呼び出しがある見ることができるように

java.lang.Exception: Stack trace 
    at java.lang.Thread.dumpStack(Thread.java:1333) 
    at test.Main.factorial(Main.java:14) 
    at test.Main.factorial(Main.java:18) 
    at test.Main.factorial(Main.java:18) 
    at test.Main.factorial(Main.java:18) 
    at test.Main.factorial(Main.java:18) 
    at test.Main.main(Main.java:8) 

：

if (n == 1) { 
    Thread.dumpStack(); 
    return TailCalls.done(fact); 
} 

スタックトレースは次のようになります。これは、テールコールの最適化を行わずにプレーンな再帰が行われることを意味します。その場合、getを呼び出すことには意味がありません。TailCallオブジェクトから戻ってくるのは、factorialから返された結果です。

---

これを実装するための正しい方法は、実際の呼び出しを延期する新しいTailCallオブジェクトを返すことです：あなたはまた、追加した場合

public static TailCall<Integer> factorial(int fact, int n) { 
    if (n == 1) { 
     return TailCalls.done(fact); 
    } 

    return() -> factorial(fact * n, n-1); 
} 

Thread.dumpStackがあるだろう唯一の1コールfactorialへ：

java.lang.Exception: Stack trace 
    at java.lang.Thread.dumpStack(Thread.java:1333) 
    at test.Main.factorial(Main.java:14) 
    at test.Main.lambda$0(Main.java:18) 
    at java.util.stream.Stream$1.next(Stream.java:1033) 
    at java.util.Spliterators$IteratorSpliterator.tryAdvance(Spliterators.java:1812) 
    at java.util.stream.ReferencePipeline.forEachWithCancel(ReferencePipeline.java:126) 
    at java.util.stream.AbstractPipeline.copyIntoWithCancel(AbstractPipeline.java:498) 
    at java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:485) 
    at java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:471) 
    at java.util.stream.FindOps$FindOp.evaluateSequential(FindOps.java:152) 
    at java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:234) 
    at java.util.stream.ReferencePipeline.findFirst(ReferencePipeline.java:464) 
    at test.TailCall.get(Main.java:36) 
    at test.Main.main(Main.java:9)