-
Notifications
You must be signed in to change notification settings - Fork 0
/
yieldDifferences.html
324 lines (294 loc) · 23.8 KB
/
yieldDifferences.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
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
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html;charset=utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<link rel="canonical" href="https://www.thanassis.space/yieldDifferences.html">
<meta name="author" content="Thanassis Tsiodras">
<meta name="author" content="Athanasios Tsiodras">
<meta name="author" content="ttsiod">
<meta name="author" content="ttsiodras">
<meta name="description" content="Yield: How it differs amongst languages">
<link type="text/css" rel="stylesheet" href="final-code-wavetheory-lightbox.css">
<link type="application/rss+xml" rel="alternate" href="rss.xml" title="Coding and administration articles by ttsiodras">
<title>Yield: How it differs amongst languages</title>
</head>
<body>
<div class="well" id="Page">
<div id="Banner">Yield: How it differs amongst languages</div>
<div id="MainContent">
<em>(November 2011)</em>
<p>
I first met <a href="yield.html">yield and coroutines</a> many years ago, when I was learning Python.
I quickly realized that this construct adds both power and elegance to a language; and since then,
one of the first things I check when working with a new language, is if it has support for
<tt>yield</tt>.
<p>
I am happy to say that most modern languages offer it - but there's a catch:
not all of them support it in the same way. This may lead to... unexpected results.
<p>
To demonstrate, I will use Python, C# and F#, in implementing the <a href="https://en.wikipedia.org/wiki/Fibonacci_number">Fibonacci sequence</a>.
<h2>In Python...</h2>
<div class='codegenWrapper'>
<pre><tt><span class="comment">#!/usr/bin/env python</span>
<span class="keyword">def</span><span class="normal"> </span><span class="function">fib</span><span class="symbol">():</span>
<span class="normal"> a0</span><span class="symbol">,</span><span class="normal"> a1 </span><span class="symbol">=</span><span class="normal"> </span><span class="number">1</span><span class="symbol">,</span><span class="normal"> </span><span class="number">1</span>
<span class="normal"> yield a0</span>
<span class="normal"> yield a1</span>
<span class="normal"> </span><span class="keyword">while</span><span class="normal"> a0</span><span class="symbol"><</span><span class="number">1000000</span><span class="symbol">:</span>
<span class="normal"> yield a0</span><span class="symbol">+</span><span class="normal">a1</span>
<span class="normal"> a0</span><span class="symbol">,</span><span class="normal"> a1 </span><span class="symbol">=</span><span class="normal"> a1</span><span class="symbol">,</span><span class="normal"> a0</span><span class="symbol">+</span><span class="normal">a1</span>
<span class="normal">fibonacciNumbersUpToMillion </span><span class="symbol">=</span><span class="normal"> </span><span class="function">fib</span><span class="symbol">()</span>
<span class="keyword">for</span><span class="normal"> i </span><span class="keyword">in</span><span class="normal"> fibonacciNumbersUpToMillion</span><span class="symbol">:</span>
<span class="normal"> </span><span class="keyword">print</span><span class="symbol">(</span><span class="normal">i</span><span class="symbol">)</span>
<span class="keyword">print</span><span class="symbol">(</span><span class="function">any</span><span class="symbol">(</span><span class="normal">i</span><span class="symbol">==</span><span class="number">10946</span><span class="normal"> </span><span class="keyword">for</span><span class="normal"> i </span><span class="keyword">in</span><span class="normal"> fibonacciNumbersUpToMillion</span><span class="symbol">))</span>
<span class="keyword">for</span><span class="normal"> i </span><span class="keyword">in</span><span class="normal"> fibonacciNumbersUpToMillion</span><span class="symbol">:</span>
<span class="normal"> </span><span class="keyword">print</span><span class="symbol">(</span><span class="normal">i</span><span class="symbol">)</span>
</tt></pre>
</div>
So...
<ul>
<li>We initialize a0 and a1 to the first two terms of the sequence
<li>Yield them back in sequence
<li>Then do a loop, calculating the next element and yielding it back
</ul>
Simple, and concise.<p>
But mathematicians will be surprised by the output of this program...
<pre class="o">
<b>bash$</b> python fib.py
1
1
2
3
5
8
13
...
1346269
2178309
False
<b>bash$</b>
</pre>
The <tt>fibonacciNumbersUpToMillion</tt> is a Python generator (since it invokes <tt>yield</tt>)
that indeed returns the Fibonacci sequence, until it passes one million...<p>
But only once!
<p>
When we call <tt>any</tt> to check if 10946 is part of the sequence, we get... <tt>False</tt>.
And the second iteration prints... nothing.
<p>
Why?<p>
Because Python has "exhausted" the generator with the print that was done before - the loop has ended,
there's no more data returned, StopIteration was raised, and the generator is now empty...
<h2>In C#</h2>
What about C#?
<div class='codegenWrapper'>
<pre><tt><span class="preproc">using</span><span class="normal"> System</span><span class="symbol">;</span>
<span class="preproc">using</span><span class="normal"> System</span><span class="symbol">.</span><span class="normal">Collections</span><span class="symbol">.</span><span class="normal">Generic</span><span class="symbol">;</span>
<span class="preproc">using</span><span class="normal"> System</span><span class="symbol">.</span><span class="normal">Linq</span><span class="symbol">;</span>
<span class="preproc">using</span><span class="normal"> System</span><span class="symbol">.</span><span class="normal">Text</span><span class="symbol">;</span>
<span class="keyword">namespace</span><span class="normal"> ConsoleApplication </span><span class="cbracket">{</span>
<span class="normal"> </span><span class="keyword">class</span><span class="normal"> </span><span class="classname">Program</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal"> </span><span class="keyword">static</span><span class="normal"> </span><span class="usertype">IEnumerable<int></span><span class="normal"> </span><span class="function">fib</span><span class="symbol">()</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal"> </span><span class="type">int</span><span class="normal"> a0 </span><span class="symbol">=</span><span class="normal"> </span><span class="number">1</span><span class="symbol">;</span>
<span class="normal"> </span><span class="type">int</span><span class="normal"> a1 </span><span class="symbol">=</span><span class="normal"> </span><span class="number">1</span><span class="symbol">;</span><span class="normal"> </span>
<span class="normal"> </span><span class="keyword">yield</span><span class="normal"> </span><span class="keyword">return</span><span class="normal"> a0</span><span class="symbol">;</span>
<span class="normal"> </span><span class="keyword">yield</span><span class="normal"> </span><span class="keyword">return</span><span class="normal"> a1</span><span class="symbol">;</span>
<span class="normal"> </span><span class="keyword">while</span><span class="normal"> </span><span class="symbol">(</span><span class="normal">a0</span><span class="symbol"><</span><span class="number">1000000</span><span class="symbol">)</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal"> </span><span class="keyword">yield</span><span class="normal"> </span><span class="keyword">return</span><span class="normal"> a0</span><span class="symbol">+</span><span class="normal">a1</span><span class="symbol">;</span>
<span class="normal"> </span><span class="usertype">var</span><span class="normal"> a2 </span><span class="symbol">=</span><span class="normal"> a0</span><span class="symbol">+</span><span class="normal">a1</span><span class="symbol">;</span><span class="normal"> </span>
<span class="normal"> a0 </span><span class="symbol">=</span><span class="normal"> a1</span><span class="symbol">;</span><span class="normal"> </span>
<span class="normal"> a1 </span><span class="symbol">=</span><span class="normal"> a2</span><span class="symbol">;</span>
<span class="normal"> </span><span class="cbracket">}</span>
<span class="normal"> </span><span class="cbracket">}</span>
<span class="normal"> </span><span class="keyword">static</span><span class="normal"> </span><span class="type">void</span><span class="normal"> </span><span class="function">Main</span><span class="symbol">(</span><span class="type">string</span><span class="symbol">[]</span><span class="normal"> args</span><span class="symbol">)</span><span class="normal"> </span><span class="cbracket">{</span>
<span class="normal"> </span><span class="usertype">var</span><span class="normal"> fibonacciNumbersUpToMillion </span><span class="symbol">=</span><span class="normal"> </span><span class="function">fib</span><span class="symbol">();</span>
<span class="normal"> </span><span class="keyword">foreach</span><span class="normal"> </span><span class="symbol">(</span><span class="normal">var x </span><span class="usertype">in</span><span class="normal"> fibonacciNumbersUpToMillion</span><span class="symbol">)</span>
<span class="normal"> Console</span><span class="symbol">.</span><span class="function">WriteLine</span><span class="symbol">(</span><span class="normal">x</span><span class="symbol">);</span>
<span class="normal"> Console</span><span class="symbol">.</span><span class="function">WriteLine</span><span class="symbol">(</span><span class="normal">fibonacciNumbersUpToMillion</span><span class="symbol">.</span><span class="function">Contains</span><span class="symbol">(</span><span class="number">10946</span><span class="symbol">));</span>
<span class="normal"> </span><span class="keyword">foreach</span><span class="normal"> </span><span class="symbol">(</span><span class="normal">var x </span><span class="usertype">in</span><span class="normal"> fibonacciNumbersUpToMillion</span><span class="symbol">)</span>
<span class="normal"> Console</span><span class="symbol">.</span><span class="function">WriteLine</span><span class="symbol">(</span><span class="normal">x</span><span class="symbol">);</span>
<span class="normal"> </span><span class="cbracket">}</span>
<span class="normal"> </span><span class="cbracket">}</span>
<span class="cbracket">}</span>
</tt></pre>
</div>
As you can see, the code closely follows what the Python code did (albeit with the mandatory namespaces and classes that C# requires).
But C# behaves differently:
<pre class="o">
<b>bash$</b> csc fib.cs
<b>bash$</b> ./fib.exe
1
1
2
3
...
1346269
2178309
True
1
1
2
3
...
2178309
<b>bash$</b>
</pre>
The <tt>fibonacciNumbersUpToMillion</tt> variable contains a sequence that will *always* carry what one would expect: all the Fibonacci numbers
up to a million.
<p>
How can C# do it? Why does Python fail to do so?
<p>
Because C# paid the price that this demands: When implementing <tt>yield</tt>, the C# compiler was instructed to perform a code transformation (generating a "magic" class) whenever it meets the construct. This transformation, in plain words, arranges so that the iteration state be kept at the *caller* side, not the *callee* side. In terms of our example above, you can think of iteration state as being managed in the "for" loop that prints - not in the fib() itself, as is done in Python.
<p>
If you want to avoid this in Python, make sure you NEVER assign the generator to a variable (in this case, <tt>fibonacciNumbersUpToMillion</tt>) - because the variable's state will be modified upon use. Instead, use the generator creator every time:
<div class='codegenWrapper'>
<pre><tt><span class="symbol">...</span>
<span class="keyword">for</span><span class="normal"> i </span><span class="keyword">in</span><span class="normal"> </span><span class="function">fib</span><span class="symbol">():</span>
<span class="normal"> </span><span class="keyword">print</span><span class="symbol">(</span><span class="normal">i</span><span class="symbol">)</span>
<span class="keyword">print</span><span class="symbol">(</span><span class="function">any</span><span class="symbol">(</span><span class="normal">i</span><span class="symbol">==</span><span class="number">10946</span><span class="normal"> </span><span class="keyword">for</span><span class="normal"> i </span><span class="keyword">in</span><span class="normal"> </span><span class="function">fib</span><span class="symbol">()))</span>
</tt></pre>
</div>
This way, you "start fresh" every time.
<h2>In F#</h2>
<div class='codegenWrapper'>
<pre><tt><span class="keyword">let</span><span class="normal"> </span><span class="function">fib</span><span class="normal"> </span><span class="symbol">()</span><span class="normal"> </span><span class="symbol">=</span>
<span class="normal"> seq </span><span class="cbracket">{</span>
<span class="normal"> </span><span class="keyword">let</span><span class="normal"> </span><span class="keyword">mutable</span><span class="normal"> a0 </span><span class="symbol">=</span><span class="normal"> </span><span class="number">1</span>
<span class="normal"> </span><span class="keyword">let</span><span class="normal"> </span><span class="keyword">mutable</span><span class="normal"> a1 </span><span class="symbol">=</span><span class="normal"> </span><span class="number">1</span>
<span class="normal"> yield a0</span>
<span class="normal"> yield a1</span>
<span class="normal"> </span><span class="keyword">while</span><span class="normal"> a0</span><span class="symbol"><</span><span class="number">1000000</span><span class="normal"> </span><span class="keyword">do</span>
<span class="normal"> </span><span class="usertype">yield</span><span class="normal"> a0</span><span class="symbol">+</span><span class="normal">a1</span>
<span class="normal"> </span><span class="keyword">let</span><span class="normal"> a2 </span><span class="symbol">=</span><span class="normal"> a0</span><span class="symbol">+</span><span class="normal">a1</span>
<span class="normal"> a0 </span><span class="symbol"><-</span><span class="normal"> a1</span>
<span class="normal"> a1 </span><span class="symbol"><-</span><span class="normal"> a2</span>
<span class="normal"> </span><span class="cbracket">}</span>
</tt></pre>
</div>
Ah, now this gets interesting:
<pre class="o">
<b>bash$</b> fsc.exe fib.fs
yield a1
--------^^^^^^^^
fib.fs(6,9): error FS0407: The mutable variable 'a0' is used in an invalid way.
Mutable variables cannot be captured by closures. Consider eliminating this use of mutation
or using a heap-allocated mutable reference cell via 'ref' and '!'.
</pre>
Listen to what F# says; "mutable variables cannot be captured by closures" - in plain words,
the body of <tt>fib</tt> has *state* inside it, which will be modified upon each iteration over it.
And it tells us that we can't do this... at least not with <tt>mutable</tt> variables.
<p>
F# is the descendant of a functional language (OCaml), and it wants its closures to be state-free.
In plain words, it wants readers of your code to reason about it in the same way mathematicians do :‑)
<p>
But F#, like her mother OCaml (and unlike her crazy aunt Haskell :‑), is practical. She knows that imperative constructs
are sometimes the way to go. And it allows you - if you want to - to do the dirty deed and keep state inside:
<div class='codegenWrapper'>
<pre><tt><span class="keyword">let</span><span class="normal"> </span><span class="function">fib</span><span class="normal"> </span><span class="symbol">()</span><span class="normal"> </span><span class="symbol">=</span>
<span class="normal"> seq </span><span class="cbracket">{</span>
<span class="normal"> </span><span class="keyword">let</span><span class="normal"> a0 </span><span class="symbol">=</span><span class="normal"> </span><span class="type">ref</span><span class="normal"> </span><span class="number">1</span>
<span class="normal"> </span><span class="keyword">let</span><span class="normal"> a1 </span><span class="symbol">=</span><span class="normal"> </span><span class="type">ref</span><span class="normal"> </span><span class="number">1</span>
<span class="normal"> yield </span><span class="symbol">!</span><span class="normal">a0</span>
<span class="normal"> yield </span><span class="symbol">!</span><span class="normal">a1</span>
<span class="normal"> </span><span class="keyword">while</span><span class="normal"> </span><span class="symbol">!</span><span class="normal">a0</span><span class="symbol"><</span><span class="number">1000000</span><span class="normal"> </span><span class="keyword">do</span>
<span class="normal"> yield </span><span class="symbol">!</span><span class="normal">a0 </span><span class="symbol">+</span><span class="normal"> </span><span class="symbol">!</span><span class="normal">a1</span>
<span class="normal"> </span><span class="keyword">let</span><span class="normal"> a2 </span><span class="symbol">=</span><span class="normal"> </span><span class="symbol">!</span><span class="normal">a0 </span><span class="symbol">+</span><span class="normal"> </span><span class="symbol">!</span><span class="normal">a1</span>
<span class="normal"> a0 </span><span class="symbol">:=</span><span class="normal"> </span><span class="symbol">!</span><span class="normal">a1</span>
<span class="normal"> a1 </span><span class="symbol">:=</span><span class="normal"> a2</span>
<span class="normal"> </span><span class="cbracket">}</span>
</tt></pre>
</div>
Which works just as C# does (i.e. you can assign this sequence to a variable and re-use it as many times as you want with no problems.
<h2>Conclusion</h2>
<tt>yield</tt> is a very useful language construct, and allows clear and concise code - but be careful of the differences of it's implementation amongst languages.
<br>
<hr>
<div style='margin-top:1em'>
<div style='float:left'>
<a target="_blank" href="https://stackoverflow.com/users/382050/ttsiodras">
<img src="382050.png" width="208" height="58" alt="profile for ttsiodras at Stack Overflow, Q&A for professional and enthusiast programmers" title="profile for ttsiodras at Stack Overflow, Q&A for professional and enthusiast programmers">
</a>
</div>
<div style='float:left; margin-left:1em'>
<a target="_blank" href="https://github.com/ttsiodras">
<img border="1" src="github.png" alt='GitHub member ttsiodras' title='GitHub member ttsiodras'>
</a>
</div>
<!--div style='float:left; margin-left:1em'>
<a target="_blank" href="https://projecteuler.net/profile/ttsiodras.png">
<img src="https://projecteuler.net/profile/ttsiodras.png" alt='Project Euler member ttsiodras' title='Project Euler member ttsiodras'>
</a>
</div-->
</div>
<div style='clear:both; margin-bottom:0.5em'></div>
<!-- Used to do this with float:right, but Opera Mini shows nothing with it... back to tables :-( -->
<table summary="Footer" width="100%" border="0"><tr><td> <br><a href="index.html">Index</a><br> </td><td> <br><a href="cv.pdf">CV</a><br> </td><td align="right"> <br><em>Updated: Sat Oct 8 12:33:59 2022</em><br> </td></tr></table>
<hr style="margin-bottom: 1em">
<p id="disqus_thread">
The comments on this website require the use of JavaScript. Perhaps your browser isn't
JavaScript capable; or the script is not being run for another reason. If you're
interested in reading the comments or leaving a comment behind please try again with a
different browser or from a different connection.
</p>
<script type="text/javascript">
/* * * CONFIGURATION VARIABLES: EDIT BEFORE PASTING INTO YOUR WEBPAGE * * */
var disqus_shortname = 'ttsiodras';
var disqus_identifier = '../content/yieldDifferences.content';
(function() {
'use strict';
/**
* This method will handle the click on the button to load the comments. It will remove the
* button and execute the original Disqus script for loading the comments.
*/
function button_clickHandler(event) {
// We need to get the button element, we could also use the target property of the event
// but this will do just as well
var button = document.getElementById('disqus_thread');
// Now we will have to recreate the div element we removed from the HTML. We will place
// it into the DOM like we did when we created the button
var disqusContainer = document.createElement('div');
button.parentNode.insertBefore(disqusContainer, button);
button.parentNode.removeChild(button);
// The div element will need to have the disqus_thread id as this is required for Disqus,
// it is the way their code identifies the element in which the comments can be displayed
disqusContainer.id = 'disqus_thread';
// Now we can execute the original Disqus code
var dsq = document.createElement('script');
dsq.type = 'text/javascript';
dsq.async = true;
dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
(document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
}
/**
* This method will initialize the module. It will replace the JavaScript dependency message
* with a button which will allow the visitor to load the comments.
*/
function init() {
// Try to get the element we used to display the message about the JavaScript dependency
var placeholder = document.getElementById('disqus_thread');
// If we didn't get the placeholder element we will stop setting up the button to load
// the comments
if (placeholder == null) {
return;
}
// The placeholder was found, now we can create the button which will allow the visitor to
// load the comments
var button = document.createElement('button');
button.appendChild(document.createTextNode('Click here to see the comments (powered by Disqus)'));
button.addEventListener('click', button_clickHandler.bind(this));
// We will insert the button before the placeholder and once the button has been placed in
// the DOM we will remove the placeholder
placeholder.parentNode.insertBefore(button, placeholder);
placeholder.parentNode.removeChild(placeholder);
// The placeholder used to have the id which can be reference by an anchor element, to make
// sure we don't break this functionality we will apply the id to our newly created button
button.id = 'disqus_thread';
}
// Setup the module
init();
})();
</script>
</div>
</div>
</body>
</html>