📄 ch04s03.html
字号:
<html><head> <meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1"> <title>3. 在Java上实现Continuation：基于heap法</title><link rel="stylesheet" href="html.css" type="text/css"><meta name="generator" content="DocBook XSL Stylesheets V1.69.1"><link rel="start" href="index.html" title="Java网络程序员看Continuation"><link rel="up" href="ch04.html" title="Chapter 4. Continuation的实现"><link rel="prev" href="ch04s02.html" title="2. 在Java上实现Continuation：基于stack法"><link rel="next" href="ch05.html" title="Chapter 5. RIFE简介"></head><body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">3. 在Java上实现Continuation：基于heap法</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="ch04s02.html">Prev</a> </td><th width="60%" align="center">Chapter 4. Continuation的实现</th><td width="20%" align="right"> <a accesskey="n" href="ch05.html">Next</a></td></tr></table><hr></div><div class="section" lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="d0e591"></a>3. 在Java上实现Continuation：基于heap法</h2></div></div></div><p>我们刚才讲到用heap的方法也是可能的，所以接下来我们就介绍一个这样的例子。您的第一个问题是，这可能吗？我们怎么可能让JVM把stack放到heap中去呢？给您一个暗示：CPS。记得我们之前讲过用CPS时需要自己实现stack吗？因为CPS中函数永远不会返回，所以JVM维持的stack事实上完全没有用处。事实上，如果runtime足够聪明的话，它就能发现它其实不用维持stack，这个优化叫做tail-call优化。一般情况下要我们不用语言提供的stack而是自己写是很讨厌的一件事，但是现在我们真是求之不得了，因为这样我们可以轻易地把stack放到heap里。来看例子：</p><pre class="programlisting">public class Fib { private static int fib(int n) { if (n <= 1) { System.out.println("Fib(" + n + ") = " + n); return n; } else { int f1 = fib(n - 1); int f2 = fib(n - 2); int f = f1 + f2; System.out.println("Fib(" + n + ") = " + f); return f; } } public static void main(String[] args) { fib(5); }}</pre><p>这时一个很简单的算fibonacci数列的例子，其输出为：</p><pre class="screen">Fib(1) = 1Fib(0) = 0Fib(2) = 1Fib(1) = 1Fib(3) = 2Fib(1) = 1Fib(0) = 0Fib(2) = 1Fib(4) = 3Fib(1) = 1Fib(0) = 0Fib(2) = 1Fib(1) = 1Fib(3) = 2Fib(5) = 5</pre><p>现在我们把fib函数改为CPS模式。假设fib()，加法和System.out.print()都是CPS函数，我们则需要把fib()函数在调用上述函数处断开，并把余下的部分变成一个新的函数。我们发现我们需要如下函数：fib，retN，fibAddPrnRetF，addPrnRetF，prnRetF和retF。每个函数的名称是它表示的操作的缩写，例如fibAddPrnRetF表示计算fib，把结果相加，输出，最后返回f。事实上，fibAddPrnRetF自己只会调用fib，但它会把addPrnRetF作为continuation传给fib；而addPrnRetF自己只会调用add，但它会把prnRetF作为continuation传给add；如此等等。</p><p>整个程序变成CPS如下：</p><pre class="programlisting">class Continuation { Continuation nextOp; StackFrame sf; void go(int n) { go(); void go() { throw new RuntimeException(); } Continuation(StackFrame sf) { this.sf = sf; } Continuation prepend(Continuation cont) { cont.nextOp = this; return cont; }}class StackFrame { StackFrame nextFrame; StackFrame prepend(StackFrame sf) { sf.nextFrame = this; return sf; }}class FibStackFrame extends StackFrame { int n, f1, f2, f;}class TerminateCont extends Continuation { TerminateCont(StackFrame sf) { super(sf); } void go(int n) {} void go() {}}class FibCont extends Continuation { FibCont(StackFrame sf) { super(sf); } void go(int n) { CpsFib.fib(n, sf, nextOp); }}class RetNCont extends Continuation { RetNCont(StackFrame sf) { super(sf); } void go() { CpsFib.retN(sf, nextOp); }}class FibAddPrnRetFCont extends Continuation { FibAddPrnRetFCont(StackFrame sf) { super(sf); } void go(int n) { CpsFib.fibAddPrnRetF(n, sf, nextOp); }}class AddPrnRetFCont extends Continuation { AddPrnRetFCont(StackFrame sf) { super(sf); } void go(int n) { CpsFib.addPrnRetF(n, sf, nextOp); }}class PrnRetFCont extends Continuation { PrnRetFCont(StackFrame sf) { super(sf); } void go(int n) {⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -