forked from ustcwpz/USTC-CS-Courses-Resource
-
Notifications
You must be signed in to change notification settings - Fork 0
/
150-engines.html
200 lines (181 loc) · 13.8 KB
/
150-engines.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
<!doctype html>
<html>
<head>
<meta charset="utf-8">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta http-equiv="Content-Language" content="zh-CN" />
<meta http-equiv="X-UA-Compatible" content="chrome=1">
<meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no">
<meta name="author" content="songjinghe" />
<meta name="Copyright" content="GNU Lesser General Public License" />
<meta name="description" content="Teach Yourself Scheme in Fixnum Days的简体中文译版" />
<meta name="keywords" content="scheme,教程" />
<title>第十五章 引擎</title>
<link rel="stylesheet" href="stylesheets/main.css">
<script>var _hmt=_hmt||[];(function(){var hm=document.createElement("script");hm.src="//hm.baidu.com/hm.js?379b64254bb382c4fa11fad6cb4e98de";var s=document.getElementsByTagName("script")[0];s.parentNode.insertBefore(hm,s);})();</script>
<script type="text/javascript">document.write(unescape("%3Cspan style='display:none' id='cnzz_stat_icon_1253043874'%3E%3C/span%3E%3Cscript src='http://s19.cnzz.com/z_stat.php%3Fid%3D1253043874' type='text/javascript'%3E%3C/script%3E"));</script>
</head>
<body>
<h1 id="-">第十五章 引擎</h1>
<p>引擎表示服从时间抢占的运算过程。换句话说，一个引擎下面的运算过程是普通的程序作为定时器可抢占的进程。</p>
<p>一个引擎用三个参数来调用：</p>
<ol>
<li>分配时间片（运行时间单元）的数目</li>
<li>成功过程</li>
<li>失败过程</li>
</ol>
<p>如果引擎的计算在分配的时间片内完成了，那么就把计算的结果作为参数来调用成功过程，如果没有计算完成，那么把未计算完的部分作为参数来调用失败过程。</p>
<p>比如，考虑一个引擎，其下的运算是一个循环，该循环打印非负整数的序列。该引擎用下面的<code>make-engine</code>过程（后面会定义该过程）创建，<code>make-engine</code>接受一个程序（即该引擎下面的计算过程）为参数，并返回对应的引擎。</p>
<pre><code class="lang-scheme">(define printn-engine
(make-engine
(lambda ()
(let loop ((i 0))
(display i)
(display " ")
(loop (+ i 1))))))
</code></pre>
<p>下面调用<code>pritn-engine</code>：</p>
<pre><code class="lang-scheme">(define *more* #f)
(printn-engine 50 list (lambda (ne) (set! *more* ne)))
=> 0 1 2 3 4 5 6 7 8 9
</code></pre>
<p>也就是循环打印到某个特定的数（这里是<code>9</code>）然后就失败(fail)了，因为时钟中断了。然而，我们定义的失败过程把fail掉的引擎赋值给了全局变量<code>*more*</code>。这样我们就可以从上个引擎中断的地方恢复：</p>
<pre><code class="lang-scheme">(*more* 50 list (lambda (ne) (set! *more* ne)))
=> 10 11 12 13 14 15 16 17 18 19
</code></pre>
<p>我们现在来构建引擎，使用<code>call/cc</code>来捕获一个失败引擎未完成的计算。首先我们会构造一个flat引擎，也就是说该引擎的计算中不能运行其他引擎。稍后我们会让代码更通用，实现nestable引擎，这样的引擎可以调用其他引擎。但是不管那种引擎，我们都需要一个定时的东西，时钟（clock）。</p>
<h2 id="15-1-">15.1 时钟</h2>
<p>我们的引擎假设有一个全局的时钟或可中断的定时器来记录程序运行的时间片。我们假设下面的时钟接口——你通常应该很容易把Scheme提供的时钟接口（如果有的话）打包成下面这种类型。（附录D用Scheme的Guile方言定义了一个时钟）</p>
<p>我们的<code>clock</code>过程的内部状态包括以下两项：</p>
<ol>
<li>剩余的时间片的数目，以及</li>
<li>一个中断处理器(handler)，当时钟的时间片用完了的时候被调用。</li>
</ol>
<p><code>clock</code>允许下面的操作：</p>
<ol>
<li><code>(clock 'set‑handler h)</code>设置中断处理器为<code>h</code>。</li>
<li><code>(clock 'set n)</code>把时钟的剩余时间片重置为<code>n</code>，返回之前的值。</li>
</ol>
<p><code>n</code>的取值范围是所有非负整数以及一个叫<code>*infinity*</code>的原子。一个时钟如果有<code>*infinity*</code>的时间片永远不会终止，所以也用不着设置中断处理器。这样的时钟总是“静止的”或“停止的”（定时器的工作就是：减到0并中断，而这样的时钟永远不会减到0并中断，所以处于“非工作”状态）。让一个时钟停止只要把时间片设为<code>*infinity*</code>即可。</p>
<p>时钟的处理器被设置为一个程序，比如：</p>
<pre><code class="lang-scheme">(clock 'set-handler
(lambda ()
(error "Say goodnight, cat!")))
(clock 'set 9)
</code></pre>
<p>这样<code>9</code>个时间片过去后会产生一个错误，并且显示的错误信息是<code>"Say goodnight, cat!"</code></p>
<h2 id="15-2-flat-">15.2 flat引擎</h2>
<p>我们将首先设置时钟的中断处理器。注意这个处理器只有在“工作”状态的时钟用完时间片后才会被调用。这只有引擎计算失败时才发生，因为只有引擎设置时钟。</p>
<p>处理器捕获当前的续延，也就是当前失败引擎的剩余计算部分。这个续延被保存到全局的<code>*engine-escape*</code>变量中。该变量存放当前引擎的续延。因此时钟处理器捕获失败引擎的剩余部分并把它发送到引擎代码的出口。这样所需的失败处理才能执行。</p>
<pre><code class="lang-scheme">(define *engine-escape* #f)
(define *engine-entrance* #f)
(clock 'set-handler
(lambda ()
(call/cc *engine-escape*)))
</code></pre>
<p>让我们来看一下引擎代码的内部。如上所述，<code>make-engine</code>接受一个程序并为之构造一个引擎：</p>
<pre><code class="lang-scheme">(define make-engine
(lambda (th)
(lambda (ticks success failure)
(let* ((ticks-left 0)
(engine-succeeded? #f)
(result
(call/cc
(lambda (k)
(set! *engine-escape* k)
(let ((result
(call/cc
(lambda (k)
(set! *engine-entrance* k)
(clock 'set ticks)
(let ((v (th)))
(*engine-entrance* v))))))
(set! ticks-left (clock 'set *infinity*))
(set! engine-succeeded? #t)
result)))))
(if engine-succeeded?
(success result ticks-left)
(failure
(make-engine
(lambda ()
(result 'resume)))))))))
</code></pre>
<p>首先我们引入变量<code>ticks-left</code>和<code>engine-succeeded?</code>。前者保存引擎的程序应该在多少时间片内完成。后者是一个标志，表示引擎是否成功。</p>
<p>我们接下来在两层对<code>call/cc</code>的调用中执行引擎的程序。第一个<code>call/cc</code>捕获的续延被失败引擎用来退出其引擎的计算。这个续延被保存到全局的<code>*engine-escape*</code>变量中。第二个<code>call/cc</code>捕获一个内部的续延，该续延会被<code>th</code>的返回值使用，如果<code>th</code>完成了的话。这个续延保存在全局的<code>*engine-entrance*</code>变量中。</p>
<p>查看上面的代码，我们能发现在捕获续延<code>*engine-escape*</code>和<code>*engine-entrance*</code>后，我们设置时钟的时间片为允许允许的时间并运行<code>th</code>。如果<code>th</code>成功了，其返回值<code>v</code>被发送到续延<code>*engine-escape*</code>，然后时钟就停止了，剩下的时间片的数量就确定了，并且标记<code>engine-succeeded?</code>被设置为真。我们现在略过(?)<code>*engine-escape*</code>续延，并执行最后一段选择语句：由于我们知道引擎成功了，我们以执行结果和剩余的时间片为参数调用<code>success</code>过程。</p>
<p>如果程序<code>th</code>没能在制定时间完成，就会被中断。这会调用时钟的中断处理器，来捕获当前失败程序的续延，并把它传给<code>*engine-escape*</code>变量。这样就把<code>result</code>变量设置为失败任务的续延，我们现在执行最后一个<code>if</code>语句，由于<code>engine-succeeded?</code>是<code>false</code>，我们以<code>result</code>构造一个新引擎并作为参数调用<code>failure</code>过程。</p>
<p>注意当一个失败的引擎被移除时，it will traverse the control path charted by the first run of the original engine.尽管如此，因为我们总是显式的使用保存在<code>*engine-entrance*</code>和<code>*engine-escape*</code>变量中的续延，而且我们总是在开启引擎计算前重新设置它们，我们能保证跳转总是会到当前执行的引擎代码。</p>
<h2 id="15-3-nestable-">15.3 交叠(nestable)的引擎</h2>
<p>为了让上面的代码更通用化，适应交叠的引擎，我们需要引入一些时间片管理的机制，来为交叠运行的所有引擎管理正确的时间片。</p>
<p>为了跑一个新引擎（子引擎），我们需要停止当前引擎（父引擎）。然后需要给子引擎分配适当的时间。这可不是直接在程序代码里设置那样，因为给子引擎分配比父引擎剩下的时间片更多的时间片是不对的。在子引擎跑完后我们还得更新父引擎剩余的时间片。如果子引擎在给定时间内跑完，所有它剩下的时间片都还给父引擎。如果子引擎要求的时间片被拒绝（因为父引擎的剩余时间片都无法满足），那么如果子引擎失败了，父引擎也会失败，但是必须记得在重启父引擎时也重启子引擎，其时间片仍然是之前需要的那些。</p>
<p>我们需要用<code>fluid-let</code>来声明全局的<code>*engine-escape*</code>和<code>*engine-entrance*</code>变量，因为每个引擎都必须有它自己的这两个做控制用的续延。当引擎退出时（不论是成功还是失败），<code>fluid-let</code>会保证其外层引擎会接管这个控制(sentinel)。</p>
<p>考虑到以上这些，可交叠引擎的代码应该像下面这样：</p>
<pre><code class="lang-scheme">(define make-engine
(lambda (th)
(lambda (ticks s f)
(let* ((parent-ticks
(clock 'set *infinity*))
;A child can't have more ticks than its parent's
;remaining ticks
(child-available-ticks
(clock-min parent-ticks ticks))
;A child's ticks must be counted against the parent
;too
(parent-ticks-left
(clock-minus parent-ticks child-available-ticks))
;If child was promised more ticks than parent could
;afford, remember how much it was short-changed by
(child-ticks-left
(clock-minus ticks child-available-ticks))
;Used below to store ticks left in clock
;if child completes in time
(ticks-left 0)
(engine-succeeded? #f)
(result
(fluid-let ((*engine-escape* #f)
(*engine-entrance* #f))
(call/cc
(lambda (k)
(set! *engine-escape* k)
(let ((result
(call/cc
(lambda (k)
(set! *engine-entrance* k)
(clock 'set child-available-ticks)
(let ((v (th)))
(*engine-entrance* v))))))
(set! ticks-left
(let ((n (clock 'set *infinity*)))
(if (eqv? n *infinity*) 0 n)))
(set! engine-succeeded? #t)
result))))))
;Parent can reclaim ticks that child didn't need
(set! parent-ticks-left
(clock-plus parent-ticks-left ticks-left))
;This is the true ticks that child has left --
;we include the ticks it was short-changed by
(set! ticks-left
(clock-plus child-ticks-left ticks-left))
;Restart parent with its remaining ticks
(clock 'set parent-ticks-left)
;The rest is now parent computation
(cond
;Child finished in time -- celebrate its success
(engine-succeeded? (s result ticks-left))
;Child failed because it ran out of promised time --
;call failure procedure
((= ticks-left 0)
(f (make-engine (lambda () (result 'resume)))))
;Child failed because parent didn't have enough time,
;ie, parent failed too. If so, when parent is
;resumed, its first order of duty is to resume the
;child with its fair amount of ticks
(else
((make-engine (lambda () (result 'resume)))
ticks-left s f)))))))
</code></pre>
<p>注意我们使用算术运算符<code>clock-min</code>，<code>clock-minus</code>和<code>clock-plus</code>替代了<code>min</code>，<code>-</code>和<code>+</code>。这是因为时钟算术的值除了整数之外还包含<code>*infinity*</code>。有些Scheme的方言在它们的算术运算中提供了<code>*infinity*</code>的值<sup><a href="#1" name="#foot-note1">1</a></sup>——如果这样的话，你就可以用这些通用的算术运算符了。如果没有的话，定义这几个增强运算符也是很简单的事情。</p>
<hr>
<a href="#1" name="foot-note1">1</a>在Guile中，你可以<code>(define *infinity* (/ 1 0))</code>。
</body>
</html>