Trampolining:java开发人员的实用指南

16-11-17 banq
Trampolining是每个java程序员应该知道的概念,它代表计算的两个状态之一,一个代表计算完成有结果,另外一个指向计算下一步reminder,有点类似java.util.Supplier 所做的。这就为实现递归计算提供了可能,无需使用堆栈Stack,也无需使用线程硬编码实现函数的交替执行。

无需Stack的递归计算

Trampolining是一个具有两个具体实现的接口,其中一个简单地表示结果,另一个表示计算的下一阶段。

通过将计算分解成单独的步骤,我们获得了很多好处。其中之一是递归计算而不需要堆栈 。 我们可以移动任何递归调用在调用方法之外执行,从而将递归转换为迭代。

斐波纳契生成:

import static com.aol.cyclops.control.Trampoline.done;
import static com.aol.cyclops.control.Trampoline.more;

public void fib() {
    for(int i=0;i<100_000;i++)
       System.out.println(fibonacci(i, 0l, 1l).get());
}

public Trampoline<Long> fibonacci(Integer count, Long a, Long b) {
     return  count==0 ?  done(a) : more(()->fibonacci (count - 1, b, a + b));
}
<p>

当调用Trampoline的return语句时,内部遍历调用随着核心实例返回是More就不断增加,一旦返回实例是Done就停止,基本上,我们通过基于循环的递归转换为迭代,关键的启用机制是Trampoline.more是一个惰性操作。

无线程并发

Trampolines另一个好处是能够在同一个线程上交错执行两个或多个函数。一个实现案例我们内部的cyclops-react,使用先进的并行流类型LazyFutureStream.,能让数据消费者在没有数据可用时切换为数据生产者。

消费者与生产者的协同

让我们展示如何使用Trampolines创建协同例程co-routines,在同一个线程上运行的交错函数。

在下面的示例中,我们有一个bog标准JDK队列,填充倒入某个单值。 我们想读取三个值,但是我们不想发生任何读取失败情况。 如果没有数据可用,我们希望我们的阅读者也就是消费者能够处理这种情况并产生一些数据。

交织功能的最简单的方法是简单地(硬编码)写在一起。 这是简单但不灵活,它会捆绑到一个特定的实现。我们可以传入一个Trampolines,如果没有存在数据,那么它会让数据使用者产生数据。 因为我们的代码库足够灵活,可以处理未来的其他策略(也许消费者应该休眠一段时间?或者当前线程不断检查新数据是否到达)。

Queue<String> data = QueueX.of("hello");

    public void consumerToProducer(){
        System.out.println(nextData(produceToConsume()));
        System.out.println(nextData(produceToConsume()));
        System.out.println(nextData(produceToConsume()));
      /*
         hello
         world
         world   
       */
    }
    private Trampoline<String> produceToConsume(){
        return Trampoline.more( ()->{
            produce();
            return done(consume());
        });
        
    }
    public String nextData(Trampoline<String> noDataHandler){
        return getData(noDataHandler).get();
    }
    private Trampoline<String> getData(Trampoline<String> noDataHandler){
        return data.size()>0 ? done(consume()) : noDataHandler;
    }
    private String consume(){
        return data.poll();
    }
   
    public void produce(){
        data.offer("world");
    }

<p>

当队列为空时,将执行noDataHandler Trampoline,因此,新数据被添加到队列以供消费者使用。

LazyFutureStream

我们的项目cyclops引入了FutureStream概念,这是每个数据点嵌入一个Future的数据流,户端不直接操作Future,而是像普通一样定义(高级)Stream操作,由库包管理Futures的流水线和它们的并行执行。

此外可以将Trampolines构建入API:实现Eval、map / flatMap 尾递归、Maybe、模式匹配等功能。详细见原文:

Trampolining: a practical guide for awesome Java D

                   

猜你喜欢