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
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
|
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport"
content="width=device-width, initial-scale=1.0, maximum-scale=1.0, minimum-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">
<meta name="author" content="韩暮秋">
<meta name="subtitle" content="暮秋小屋">
<meta name="description" content="这里是暮秋小屋，思念和灵感的寄存处">
<meta name="keywords" content="韩暮秋,MuqiuHan,'Muqiu Han', 'muqiu han', muqiuhan">
<title>隐藏一些OCaml Effect的机制，让其语法在精神上更接近delimcc | 暮秋小屋</title>
<link rel="icon" href="/favicon.ico">
<style>
@import url('https://fonts.googleapis.com/css2?family=Inter:wght@300;400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&family=Roboto+Mono&display=swap');
</style>
<!-- stylesheets list from _config.yml -->
<link rel="stylesheet" href="/css/style.css">
<!-- scripts list from _config.yml -->
<script src="/js/frame.js"></script>
<script src="https://polyfill.alicdn.com/polyfill.js?features=es6"></script>
<script id="MathJax-script" async src="https://lf6-cdn-tos.bytecdntp.com/cdn/expire-1-M/mathjax/3.2.0/es5/tex-mml-chtml.js"></script>
<meta name="generator" content="Hexo 6.3.0"></head>
<body>
<div class="mask-border">
</div>
<div class="wrapper">
<div class="header">
<div class="flex-container">
<div class="header-inner">
<div class="site-brand-container">
<a href="/">
暮秋小屋
</a>
</div>
<div id="menu-btn" class="menu-btn" onclick="toggleMenu()">
Menu
</div>
<nav class="site-nav">
<ul class="menu-list">
<li class="menu-item">
<a href="/">主页</a>
</li>
<li class="menu-item">
<a href="/categories/gallery/">日记本</a>
</li>
<li class="menu-item">
<a href="/tags/Medicine/">医学</a>
</li>
<li class="menu-item">
<a href="/tags/Technique/">计算机科学</a>
</li>
<li class="menu-item">
<a href="/tags/Life/">生活</a>
</li>
<li class="menu-item">
<a href="/about">关于</a>
</li>
<li class="menu-item search-btn">
<a href="#">Search</a>
</li>
</ul>
</nav>
</div>
</div>
</div>
<script src="/js/menu.js"></script>
<div class="main">
<div class="flex-container">
<article id="post">
<div class="post-head">
<div class="post-info">
<div class="tag-list">
<span class="post-tag">
<a href="/tags/Technique/">
Technique
</a>
</span>
</div>
<div class="post-title">
隐藏一些OCaml Effect的机制，让其语法在精神上更接近delimcc
</div>
<span class="post-date">
Jun 28, 2023
</span>
</div>
<div class="post-img">
<div class="h-line-primary"></div>
</div>
</div>
<div class="post-content">
<p><a target="_blank" rel="noopener" href="https://github.com/kayceesrk/delimcc_of_fxhandler">delimcc_of_fxhandler这个库</a>在OCaml5的effect handlers上实现了一些delimcc原语(shift/reset, control/prompt这些)：</p>
<figure class="highlight ocaml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span> p = new_prompt <span class="literal">()</span> <span class="keyword">in</span></span><br><span class="line"><span class="keyword">assert</span> (<span class="literal">[]</span> = push_prompt p (<span class="keyword">fun</span> <span class="literal">()</span> -></span><br><span class="line"> <span class="number">1</span>::<span class="number">2</span>::take_subcont p (<span class="keyword">fun</span> _k -> <span class="literal">[]</span>)));</span><br><span class="line"><span class="keyword">assert</span> ([<span class="number">1</span>;<span class="number">2</span>] = push_prompt p (<span class="keyword">fun</span> <span class="literal">()</span> -></span><br><span class="line"> <span class="number">1</span>::<span class="number">2</span>::take_subcont p (<span class="keyword">fun</span> k -> push_subcont k <span class="literal">[]</span>)));</span><br><span class="line"><span class="keyword">assert</span> (<span class="number">135</span> =</span><br><span class="line"> <span class="keyword">let</span> p1 = new_prompt <span class="literal">()</span> <span class="keyword">in</span></span><br><span class="line"> <span class="keyword">let</span> p2 = new_prompt <span class="literal">()</span> <span class="keyword">in</span></span><br><span class="line"> <span class="keyword">let</span> p3 = new_prompt <span class="literal">()</span> <span class="keyword">in</span></span><br><span class="line"> <span class="keyword">let</span> pushtwice sk =</span><br><span class="line"> sk (<span class="keyword">fun</span> <span class="literal">()</span> -></span><br><span class="line"> sk (<span class="keyword">fun</span> <span class="literal">()</span> -></span><br><span class="line"> shift0 p2 (<span class="keyword">fun</span> sk2 -> sk2 (<span class="keyword">fun</span> <span class="literal">()</span> -></span><br><span class="line"> sk2 (<span class="keyword">fun</span> <span class="literal">()</span> -> <span class="number">3</span>))) <span class="literal">()</span>))</span><br><span class="line"> <span class="keyword">in</span></span><br><span class="line"> push_prompt p1 (<span class="keyword">fun</span> <span class="literal">()</span> -></span><br><span class="line"> push_prompt p2 (<span class="keyword">fun</span> <span class="literal">()</span> -></span><br><span class="line"> push_prompt p3 (<span class="keyword">fun</span> <span class="literal">()</span> -> shift0 p1 pushtwice <span class="literal">()</span>) + <span class="number">10</span>) + <span class="number">1</span>) + <span class="number">100</span>);</span><br><span class="line"></span><br><span class="line">print_endline <span class="string">"Success!"</span></span><br></pre></td></tr></table></figure>
<p>另外， <a target="_blank" rel="noopener" href="https://github.com/avsm/ocaml/commits/effect-syntax">avsm这里</a>可以看到一些OCaml的Effect Syntax进展。</p>
<p>还有 <a target="_blank" rel="noopener" href="https://github.com/dhil/ocaml-multicont">multi-shot continuations in OCaml</a>，在这个仓库里面还讨论了一些有趣的问题，例如，OCaml 编译器和runtime会做出一些假设从而进行一些优化，这些优化在使用multi-shot continutation时是不可取的（或完全错误的）。编译器优化导致错误的一个例子是堆到栈的转换，例如:</p>
<figure class="highlight ocaml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">(* An illustration of how the heap to stack optimisation is broken.</span></span><br><span class="line"><span class="comment"> * This example is adapted from de Vilhena and Pottier (2021).</span></span><br><span class="line"><span class="comment"> * file: heap2stack.ml</span></span><br><span class="line"><span class="comment"> * compile: ocamlopt -I $(opam var lib)/multicont multicont.cmxa heap2stack.ml</span></span><br><span class="line"><span class="comment"> * run: ./a.out *)</span></span><br><span class="line"></span><br><span class="line"><span class="comment">(* We first require a little bit of setup. The following declares an</span></span><br><span class="line"><span class="comment"> operation `Twice' which we use to implement multiple returns. *)</span></span><br><span class="line"><span class="keyword">type</span> _ <span class="type">Effect</span>.t += <span class="type">Twice</span> : <span class="built_in">unit</span> <span class="type">Effect</span>.t</span><br><span class="line"></span><br><span class="line"><span class="comment">(* The handler `htwice' interprets `Twice' by simply invoking its</span></span><br><span class="line"><span class="comment"> continuation twice. *)</span></span><br><span class="line"><span class="keyword">let</span> htwice : (<span class="built_in">unit</span>, <span class="built_in">unit</span>) <span class="type">Effect</span>.<span class="type">Deep</span>.handler</span><br><span class="line"> = { retc = (<span class="keyword">fun</span> x -> x)</span><br><span class="line"> ; exnc = (<span class="keyword">fun</span> e -> raise e)</span><br><span class="line"> ; effc = (<span class="keyword">fun</span> (<span class="keyword">type</span> a) (eff : a <span class="type">Effect</span>.t) -></span><br><span class="line"> <span class="keyword">let</span> <span class="keyword">open</span> <span class="type">Effect</span>.<span class="type">Deep</span> <span class="keyword">in</span></span><br><span class="line"> <span class="keyword">match</span> eff <span class="keyword">with</span></span><br><span class="line"> | <span class="type">Twice</span> -> <span class="type">Some</span> (<span class="keyword">fun</span> (k : (a, _) continuation) -></span><br><span class="line"> continue (<span class="type">Multicont</span>.<span class="type">Deep</span>.clone_continuation k) <span class="literal">()</span>;</span><br><span class="line"> continue k <span class="literal">()</span>)</span><br><span class="line"> | _ -> <span class="type">None</span>) }</span><br><span class="line"></span><br><span class="line"><span class="comment">(* Now for the interesting stuff. In the code below, the compiler will</span></span><br><span class="line"><span class="comment"> perform an escape analysis on the reference `i' and deduce that it</span></span><br><span class="line"><span class="comment"> does not escape the local scope, because it is unaware of the</span></span><br><span class="line"><span class="comment"> semantics of `perform Twice', hence the optimiser will transform</span></span><br><span class="line"><span class="comment"> `i' into an immediate on the stack to save a heap allocation. As a</span></span><br><span class="line"><span class="comment"> consequence, the assertion `(!i = 1)' will succeed twice, whereas</span></span><br><span class="line"><span class="comment"> it should fail after the second return of `perform Twice'. *)</span></span><br><span class="line"><span class="keyword">let</span> heap2stack <span class="literal">()</span> =</span><br><span class="line"> <span class="type">Effect</span>.<span class="type">Deep</span>.match_with</span><br><span class="line"> (<span class="keyword">fun</span> <span class="literal">()</span> -></span><br><span class="line"> <span class="keyword">let</span> i = <span class="built_in">ref</span> <span class="number">0</span> <span class="keyword">in</span></span><br><span class="line"> <span class="type">Effect</span>.perform <span class="type">Twice</span>;</span><br><span class="line"> i := !i + <span class="number">1</span>;</span><br><span class="line"> <span class="type">Printf</span>.printf <span class="string">"i = %d\n%!"</span> !i;</span><br><span class="line"> <span class="keyword">assert</span> (!i = <span class="number">1</span>))</span><br><span class="line"> <span class="literal">()</span> htwice</span><br><span class="line"></span><br><span class="line"><span class="comment">(* The following does not trigger an assertion failure. *)</span></span><br><span class="line"><span class="keyword">let</span> _ = heap2stack <span class="literal">()</span></span><br><span class="line"></span><br><span class="line"><span class="comment">(* To fix this issue, we can wrap reference allocations in an instance</span></span><br><span class="line"><span class="comment"> of `Sys.opaque_identity'. However, this is not really a viable fix</span></span><br><span class="line"><span class="comment"> in general, as we may not have access to the client code that</span></span><br><span class="line"><span class="comment"> allocates the reference! *)</span></span><br><span class="line"><span class="keyword">let</span> heap2stack' <span class="literal">()</span> =</span><br><span class="line"> <span class="type">Effect</span>.<span class="type">Deep</span>.match_with</span><br><span class="line"> (<span class="keyword">fun</span> <span class="literal">()</span> -></span><br><span class="line"> <span class="keyword">let</span> i = <span class="type">Sys</span>.opaque_identity (<span class="built_in">ref</span> <span class="number">0</span>) <span class="keyword">in</span></span><br><span class="line"> <span class="type">Effect</span>.perform <span class="type">Twice</span>;</span><br><span class="line"> i := !i + <span class="number">1</span>;</span><br><span class="line"> <span class="type">Printf</span>.printf <span class="string">"i = %d\n%!"</span> !i;</span><br><span class="line"> <span class="keyword">assert</span> (!i = <span class="number">1</span>))</span><br><span class="line"> <span class="literal">()</span> htwice</span><br><span class="line"></span><br><span class="line"><span class="comment">(* The following triggers an assertion failure. *)</span></span><br><span class="line"><span class="keyword">let</span> _ = heap2stack' <span class="literal">()</span></span><br></pre></td></tr></table></figure>
</div>
<script>
window.onload = detectors();
</script>
<div class="post-footer">
<div class="h-line-primary"></div>
<nav class="post-nav">
<div class="prev-item">
<div class="icon arrow-left"></div>
<div class="post-link">
<a href="/2023/06/29/%E4%BA%8C%E3%80%87%E4%BA%8C%E4%B8%89%E5%B9%B4%E5%85%AD%E6%9C%88%E4%BA%8C%E5%8D%81%E4%B9%9D%E6%97%A5/">Prev</a>
</div>
</div>
<div class="next-item">
<div class="icon arrow-right"></div>
<div class="post-link">
<a href="/2023/06/28/caml-release-runtime-system%E5%AF%BC%E8%87%B4%E7%9A%84%E6%AD%BB%E9%94%81%E9%97%AE%E9%A2%98/">Next</a>
</div>
</div>
</nav>
</div>
<div class="post-comment">
</div>
</article>
</div>
</div>
<div class="footer">
<div class="flex-container">
<div class="footer-text">
|
希望路过的人可以添点柴火让这里暖和点
</div>
</div>
</div>
</div>
<div class="search-popup">
<div class="search-popup-overlay">
</div>
<div class="search-popup-window" >
<div class="search-header">
<div class="search-input-container">
<input autocomplete="off" autocapitalize="off" maxlength="80"
placeholder="Search Anything" spellcheck="false"
type="search" class="search-input">
</div>
<div class="search-close-btn">
<div class="icon close-btn"></div>
</div>
</div>
<div class="search-result-container">
</div>
</div>
</div>
<script>
const searchConfig = {
path : "/search.xml",
top_n_per_article: "1",
unescape : "false",
trigger: "auto",
preload: "false"
}
</script>
<script src="https://cdn.jsdelivr.net/npm/[email protected]/dist/search.js"></script>
<script src="/js/search.js"></script>
</body>
</html>
|
