📄 ch04s01.html
字号:
<html><head> <meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1"> <title>1. Continuation的常规实现方法</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="ch04.html" title="Chapter 4. Continuation的实现"><link rel="next" href="ch04s02.html" title="2. 在Java上实现Continuation:基于stack法"></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">1. Continuation的常规实现方法</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="ch04.html">Prev</a> </td><th width="60%" align="center">Chapter 4. Continuation的实现</th><td width="20%" align="right"> <a accesskey="n" href="ch04s02.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="d0e510"></a>1. Continuation的常规实现方法</h2></div></div></div><p>虽然大多数程序员都没有太多接触过continuation,但是continuation其实是一个很重要的研究领域。如本文开头所说,研究compiler优化技术的“科学怪人”们想出了continuation各种各样的实现方法,这里我们只介绍其中两种最基本的,基于heap和基于stack。</p><p>首先我们需要想想,从语言实现的角度讲,continuation到底是什么?它是程序的一个状态。程序的状态包括什么?简单地讲,程序的状态是由stack和程序指针(program counter)组成的。有了程序指针,我们就知道程序运行到哪里了;有了stack,我们就知道函数返回去哪里,以及所有有效的本地变量的值。</p><p>程序指针只是一个值,处理起来非常简单。支持continuation最特别的地方可能就在于对stack的处理了。一个典型的C stack由若干stack frame组成,每个stack frame保存了一个函数一次调用的本地变量和少量别的信息。函数返回时其stack frame从stack上收回,这时母函数就会继续运行。</p><p>Stack是类似C和Java等语言的核心结构,不过它是基于这样一个假设的,那就是在函数返回后其本地变量不会再被用到。在C/Java中这显然是没问题的,不过在Ruby中呢?</p><pre class="programlisting">def function i = 1 puts i callcc { |cc| return cc } i += 1 puts i exitendaCC = functionaCC.call</pre><p>上面是一个非常简单的continuation程序。我们调用function时,它会输出“1”,并在return cc处返回。该continuation纪录在aCC中。然后我们调用aCC.call。这时我们又跳回function当中,把i设为2,输出2并退出。</p><p>这个例子虽然简单,但是它说明一个问题,当function在return cc处返回时我们不能立刻回收本地变量i,因为我们以后还有可能再返回到该函数当中,并且再次用到i的值。这就是为什么基于堆的语言,如Java,很难支持continuation。</p><p>如果用传统的stack不方便,那么自然的选择就是把stack frame放在heap中。(这个名称很有些奇怪,我们是不是应该改叫heap frame呢?)这正是基于heap的continuation方案的做法。在这种做法下,heap中保存的各个stack frame组成若干个逻辑上的stack,如下图所示。下图中有两个逻辑stack,蓝色的是当前正在运行的stack,红色的则是aCC这个continuation中纪录的stack。</p><div class="screenshot"><div class="mediaobject"><img src="resources/heap-based.png"></div></div><p>虚拟机永远会保持一个指针指向当前stack的顶端(该指针也保证仍在当前stack上的stack frame不会被回收),但同时每个continuation,例如aCC,也保持了一个逻辑上的stack。当一个函数返回时,它的stack frame不会立即回收。不过,如果一个stack frame不在任何一个stack中(包括当前stack或任何一个continuation需要的stack),那么在heap垃圾回收(garbage collection)时该stack frame就会自动被回收。例如上面,如果我们把aCC的值重定为NULL,那么红色区域的两个stack frame就会被垃圾回收掉。</p><p>基于heap的解决方案有很多变种,主要区别在于针对这种具体情况优化垃圾回收效率,在这里我们就不详细介绍了。不介意追随科学怪人步伐的读者可以自己察看相关文献。</p><p>用heap支持continuation逻辑上非常干净,它最大的坏处就是即使不用continuation的程序或者一个程序中不用continuation的部分也要放弃传统的stack改用heap,因此效率上会受到影响。基于stack的解决方案就没有这个问题。在基于stack的方案中,我们平常仍然使用传统的stack,其优点是如果不使用continuation的话,程序运行就完全不用考虑对continuation的支持。其缺点是,每次我们获取一个continuation时,当前的stack必须拷贝一份,该拷贝成为continuation的一部分。调用continuation时,我们需要删除当前stack,然后把continuation里带的stack拷贝变成当前stack。目前大部分支持continuation的运行环境使用的是都是基于stack方案的一些变种。</p><p>基于stack和基于heap的实现可以看成两个极端情况,还有很多方法试图结合两者的优点,以提供更有效率的continuation支持。不过,效率可能并不是我们最关心的。我们现在真正关心的是,有没有办法在Java平台上实现continuation?</p></div><div class="navfooter"><hr><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="ch04.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="ch04.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="ch04s02.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Chapter 4. Continuation的实现 </td><td width="20%" align="center"><a accesskey="h" href="index.html">Home</a></td><td width="40%" align="right" valign="top"> 2. 在Java上实现Continuation:基于stack法</td></tr></table></div></body></html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -