<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<title>~/Desktop/s/mu/061channel.mu</title>
<meta name="Generator" content="Vim/7.4">
<meta name="plugin-version" content="vim7.4_v1">
<meta name="syntax" content="none">
<meta name="settings" content="use_css,pre_wrap,no_foldcolumn,expand_tabs,prevent_copy=">
<meta name="colorscheme" content="minimal">
<style type="text/css">
<!--
pre { white-space: pre-wrap; font-family: monospace; color: #d0d0d0; background-color: #000000; }
body { font-family: monospace; color: #d0d0d0; background-color: #000000; }
* { font-size: 1em; }
.CommentedCode { color: #6c6c6c; }
.Delimiter { color: #c000c0; }
.Comment { color: #8080ff; }
.Constant { color: #008080; }
.Special { color: #ff6060; }
.Identifier { color: #008080; }
.SalientComment { color: #00ffff; }
-->
</style>
<script type='text/javascript'>
<!--
-->
</script>
</head>
<body>
<pre id='vimCodeElement'>
<span class="Comment"># Mu synchronizes using channels rather than locks, like Erlang and Go.</span>
<span class="Comment">#</span>
<span class="Comment"># The two ends of a channel will usually belong to different routines, but</span>
<span class="Comment"># each end should only be used by a single one. Don't try to read from or</span>
<span class="Comment"># write to it from multiple routines at once.</span>
<span class="Comment">#</span>
<span class="Comment"># The key property of channels is that writing to a full channel or reading</span>
<span class="Comment"># from an empty one will put the current routine in 'waiting' state until the</span>
<span class="Comment"># operation can be completed.</span>
scenario channel [
run [
1:address:channel<span class="Special"> <- </span>init-channel <span class="Constant">3:literal/capacity</span>
1:address:channel<span class="Special"> <- </span>write 1:address:channel, <span class="Constant">34:literal</span>
2:number, 1:address:channel<span class="Special"> <- </span>read 1:address:channel
]
memory-should-contain [
2<span class="Special"> <- </span>34
]
]
container channel [
<span class="Comment"># To avoid locking, writer and reader will never write to the same location.</span>
<span class="Comment"># So channels will include fields in pairs, one for the writer and one for the</span>
<span class="Comment"># reader.</span>
first-full:number <span class="Comment"># for write</span>
first-free:number <span class="Comment"># for read</span>
<span class="Comment"># A circular buffer contains values from index first-full up to (but not</span>
<span class="Comment"># including) index first-empty. The reader always modifies it at first-full,</span>
<span class="Comment"># while the writer always modifies it at first-empty.</span>
data:address:array:location
]
<span class="Comment"># result:address:channel <- init-channel capacity:number</span>
recipe init-channel [
default-space:address:array:location<span class="Special"> <- </span>new location:type, <span class="Constant">30:literal</span>
<span class="Comment"># result = new channel</span>
result:address:channel<span class="Special"> <- </span>new channel:type
<span class="Comment"># result.first-full = 0</span>
full:address:number<span class="Special"> <- </span>get-address result:address:channel/deref, first-full:offset
full:address:number/deref<span class="Special"> <- </span>copy <span class="Constant">0:literal</span>
<span class="Comment"># result.first-free = 0</span>
free:address:number<span class="Special"> <- </span>get-address result:address:channel/deref, first-free:offset
free:address:number/deref<span class="Special"> <- </span>copy <span class="Constant">0:literal</span>
<span class="Comment"># result.data = new location[ingredient+1]</span>
capacity:number<span class="Special"> <- </span>next-ingredient
capacity:number<span class="Special"> <- </span>add capacity:number, <span class="Constant">1:literal</span> <span class="Comment"># unused slot for 'full?' below</span>
dest:address:address:array:location<span class="Special"> <- </span>get-address result:address:channel/deref, data:offset
dest:address:address:array:location/deref<span class="Special"> <- </span>new location:type, capacity:number
<span class="Identifier">reply</span> result:address:channel
]
<span class="Comment"># chan:address:channel <- write chan:address:channel, val:location</span>
recipe write [
default-space:address:array:location<span class="Special"> <- </span>new location:type, <span class="Constant">30:literal</span>
chan:address:channel<span class="Special"> <- </span>next-ingredient
val:location<span class="Special"> <- </span>next-ingredient
<span class="Delimiter">{</span>
<span class="Comment"># block if chan is full</span>
full:boolean<span class="Special"> <- </span>channel-full? chan:address:channel
<span class="Identifier">break-unless</span> full:boolean
full-address:address:number<span class="Special"> <- </span>get-address chan:address:channel/deref, first-full:offset
wait-for-location full-address:address:number/deref
<span class="Delimiter">}</span>
<span class="Comment"># store val</span>
circular-buffer:address:array:location<span class="Special"> <- </span>get chan:address:channel/deref, data:offset
free:address:number<span class="Special"> <- </span>get-address chan:address:channel/deref, first-free:offset
dest:address:location<span class="Special"> <- </span>index-address circular-buffer:address:array:location/deref, free:address:number/deref
dest:address:location/deref<span class="Special"> <- </span>copy val:location
<span class="Comment"># increment free</span>
free:address:number/deref<span class="Special"> <- </span>add free:address:number/deref, <span class="Constant">1:literal</span>
<span class="Delimiter">{</span>
<span class="Comment"># wrap free around to 0 if necessary</span>
len:number<span class="Special"> <- </span>length circular-buffer:address:array:location/deref
at-end?:boolean<span class="Special"> <- </span>greater-or-equal free:address:number/deref, len:number
<span class="Identifier">break-unless</span> at-end?:boolean
free:address:number/deref<span class="Special"> <- </span>copy <span class="Constant">0:literal</span>
<span class="Delimiter">}</span>
<span class="Identifier">reply</span> chan:address:channel/same-as-ingredient:0
]
<span class="Comment"># result:location, chan:address:channel <- read chan:address:channel</span>
recipe read [
default-space:address:array:location<span class="Special"> <- </span>new location:type, <span class="Constant">30:literal</span>
chan:address:channel<span class="Special"> <- </span>next-ingredient
<span class="Delimiter">{</span>
<span class="Comment"># block if chan is empty</span>
empty:boolean<span class="Special"> <- </span>channel-empty? chan:address:channel
<span class="Identifier">break-unless</span> empty:boolean
free-address:address:number<span class="Special"> <- </span>get-address chan:address:channel/deref, first-free:offset
wait-for-location free-address:address:number/deref
<span class="Delimiter">}</span>
<span class="Comment"># read result</span>
full:address:number<span class="Special"> <- </span>get-address chan:address:channel/deref, first-full:offset
circular-buffer:address:array:location<span class="Special"> <- </span>get chan:address:channel/deref, data:offset
result:location<span class="Special"> <- </span>index circular-buffer:address:array:location/deref, full:address:number/deref
<span class="Comment"># increment full</span>
full:address:number/deref<span class="Special"> <- </span>add full:address:number/deref, <span class="Constant">1:literal</span>
<span class="Delimiter">{</span>
<span class="Comment"># wrap full around to 0 if necessary</span>
len:number<span class="Special"> <- </span>length circular-buffer:address:array:location/deref
at-end?:boolean<span class="Special"> <- </span>greater-or-equal full:address:number/deref, len:number
<span class="Identifier">break-unless</span> at-end?:boolean
full:address:number/deref<span class="Special"> <- </span>copy <span class="Constant">0:literal</span>
<span class="Delimiter">}</span>
<span class="Identifier">reply</span> result:location, chan:address:channel/same-as-ingredient:0
]
recipe clear-channel [
default-space:address:address:array:location<span class="Special"> <- </span>new location:type, <span class="Constant">30:literal</span>
chan:address:channel<span class="Special"> <- </span>next-ingredient
<span class="Delimiter">{</span>
empty?:boolean<span class="Special"> <- </span>channel-empty? chan:address:channel
<span class="Identifier">break-if</span> empty?:boolean
_, chan:address:channel<span class="Special"> <- </span>read chan:address:channel
<span class="Delimiter">}</span>
<span class="Identifier">reply</span> chan:address:channel/same-as-ingredient:0
]
scenario channel-initialization [
run [
1:address:channel<span class="Special"> <- </span>init-channel <span class="Constant">3:literal/capacity</span>
2:number<span class="Special"> <- </span>get 1:address:channel/deref, first-full:offset
3:number<span class="Special"> <- </span>get 1:address:channel/deref, first-free:offset
]
memory-should-contain [
2<span class="Special"> <- </span>0 <span class="Comment"># first-full</span>
3<span class="Special"> <- </span>0 <span class="Comment"># first-free</span>
]
]
scenario channel-write-increments-free [
run [
1:address:channel<span class="Special"> <- </span>init-channel <span class="Constant">3:literal/capacity</span>
1:address:channel<span class="Special"> <- </span>write 1:address:channel, <span class="Constant">34:literal</span>
2:number<span class="Special"> <- </span>get 1:address:channel/deref, first-full:offset
3:number<span class="Special"> <- </span>get 1:address:channel/deref, first-free:offset
]
memory-should-contain [
2<span class="Special"> <- </span>0 <span class="Comment"># first-full</span>
3<span class="Special"> <- </span>1 <span class="Comment"># first-free</span>
]
]
scenario channel-read-increments-full [
run [
1:address:channel<span class="Special"> <- </span>init-channel <span class="Constant">3:literal/capacity</span>
1:address:channel<span class="Special"> <- </span>write 1:address:channel, <span class="Constant">34:literal</span>
_, 1:address:channel<span class="Special"> <- </span>read 1:address:channel
2:number<span class="Special"> <- </span>get 1:address:channel/deref, first-full:offset
3:number<span class="Special"> <- </span>get 1:address:channel/deref, first-free:offset
]
memory-should-contain [
2<span class="Special"> <- </span>1 <span class="Comment"># first-full</span>
3<span class="Special"> <- </span>1 <span class="Comment"># first-free</span>
]
]
scenario channel-wrap [
run [
<span class="Comment"># channel with just 1 slot</span>
1:address:channel<span class="Special"> <- </span>init-channel <span class="Constant">1:literal/capacity</span>
<span class="Comment"># write and read a value</span>
1:address:channel<span class="Special"> <- </span>write 1:address:channel, <span class="Constant">34:literal</span>
_, 1:address:channel<span class="Special"> <- </span>read 1:address:channel
<span class="Comment"># first-free will now be 1</span>
2:number<span class="Special"> <- </span>get 1:address:channel/deref, first-free:offset
3:number<span class="Special"> <- </span>get 1:address:channel/deref, first-free:offset
<span class="Comment"># write second value, verify that first-free wraps</span>
1:address:channel<span class="Special"> <- </span>write 1:address:channel, <span class="Constant">34:literal</span>
4:number<span class="Special"> <- </span>get 1:address:channel/deref, first-free:offset
<span class="Comment"># read second value, verify that first-full wraps</span>
_, 1:address:channel<span class="Special"> <- </span>read 1:address:channel
5:number<span class="Special"> <- </span>get 1:address:channel/deref, first-full:offset
]
memory-should-contain [
2<span class="Special"> <- </span>1 <span class="Comment"># first-free after first write</span>
3<span class="Special"> <- </span>1 <span class="Comment"># first-full after first read</span>
4<span class="Special"> <- </span>0 <span class="Comment"># first-free after second write, wrapped</span>
5<span class="Special"> <- </span>0 <span class="Comment"># first-full after second read, wrapped</span>
]
]
<span class="SalientComment">## helpers</span>
<span class="Comment"># An empty channel has first-empty and first-full both at the same value.</span>
recipe channel-empty? [
default-space:address:array:location<span class="Special"> <- </span>new location:type, <span class="Constant">30:literal</span>
chan:address:channel<span class="Special"> <- </span>next-ingredient
<span class="Comment"># return chan.first-full == chan.first-free</span>
full:number<span class="Special"> <- </span>get chan:address:channel/deref, first-full:offset
free:number<span class="Special"> <- </span>get chan:address:channel/deref, first-free:offset
result:boolean<span class="Special"> <- </span>equal full:number, free:number
<span class="Identifier">reply</span> result:boolean
]
<span class="Comment"># A full channel has first-empty just before first-full, wasting one slot.</span>
<span class="Comment"># (Other alternatives: <a href="https://en.wikipedia.org/wiki/Circular_buffer#Full_.2F_Empty_Buffer_Distinction)">https://en.wikipedia.org/wiki/Circular_buffer#Full_.2F_Empty_Buffer_Distinction)</a></span>
recipe channel-full? [
default-space:address:array:location<span class="Special"> <- </span>new location:type, <span class="Constant">30:literal</span>
chan:address:channel<span class="Special"> <- </span>next-ingredient
<span class="Comment"># tmp = chan.first-free + 1</span>
tmp:number<span class="Special"> <- </span>get chan:address:channel/deref, first-free:offset
tmp:number<span class="Special"> <- </span>add tmp:number, <span class="Constant">1:literal</span>
<span class="Delimiter">{</span>
<span class="Comment"># if tmp == chan.capacity, tmp = 0</span>
len:number<span class="Special"> <- </span>channel-capacity chan:address:channel
at-end?:boolean<span class="Special"> <- </span>greater-or-equal tmp:number, len:number
<span class="Identifier">break-unless</span> at-end?:boolean
tmp:number<span class="Special"> <- </span>copy <span class="Constant">0:literal</span>
<span class="Delimiter">}</span>
<span class="Comment"># return chan.first-full == tmp</span>
full:number<span class="Special"> <- </span>get chan:address:channel/deref, first-full:offset
result:boolean<span class="Special"> <- </span>equal full:number, tmp:number
<span class="Identifier">reply</span> result:boolean
]
<span class="Comment"># result:number <- channel-capacity chan:address:channel</span>
recipe channel-capacity [
default-space:address:array:location<span class="Special"> <- </span>new location:type, <span class="Constant">30:literal</span>
chan:address:channel<span class="Special"> <- </span>next-ingredient
q:address:array:location<span class="Special"> <- </span>get chan:address:channel/deref, data:offset
result:number<span class="Special"> <- </span>length q:address:array:location/deref
<span class="Identifier">reply</span> result:number
]
scenario channel-new-empty-not-full [
run [
1:address:channel<span class="Special"> <- </span>init-channel <span class="Constant">3:literal/capacity</span>
2:boolean<span class="Special"> <- </span>channel-empty? 1:address:channel
3:boolean<span class="Special"> <- </span>channel-full? 1:address:channel
]
memory-should-contain [
2<span class="Special"> <- </span>1 <span class="Comment"># empty?</span>
3<span class="Special"> <- </span>0 <span class="Comment"># full?</span>
]
]
scenario channel-write-not-empty [
run [
1:address:channel<span class="Special"> <- </span>init-channel <span class="Constant">3:literal/capacity</span>
1:address:channel<span class="Special"> <- </span>write 1:address:channel, <span class="Constant">34:literal</span>
2:boolean<span class="Special"> <- </span>channel-empty? 1:address:channel
3:boolean<span class="Special"> <- </span>channel-full? 1:address:channel
]
memory-should-contain [
2<span class="Special"> <- </span>0 <span class="Comment"># empty?</span>
3<span class="Special"> <- </span>0 <span class="Comment"># full?</span>
]
]
scenario channel-write-full [
run [
1:address:channel<span class="Special"> <- </span>init-channel <span class="Constant">1:literal/capacity</span>
1:address:channel<span class="Special"> <- </span>write 1:address:channel, <span class="Constant">34:literal</span>
2:boolean<span class="Special"> <- </span>channel-empty? 1:address:channel
3:boolean<span class="Special"> <- </span>channel-full? 1:address:channel
]
memory-should-contain [
2<span class="Special"> <- </span>0 <span class="Comment"># empty?</span>
3<span class="Special"> <- </span>1 <span class="Comment"># full?</span>
]
]
scenario channel-read-not-full [
run [
1:address:channel<span class="Special"> <- </span>init-channel <span class="Constant">1:literal/capacity</span>
1:address:channel<span class="Special"> <- </span>write 1:address:channel, <span class="Constant">34:literal</span>
_, 1:address:channel<span class="Special"> <- </span>read 1:address:channel
2:boolean<span class="Special"> <- </span>channel-empty? 1:address:channel
3:boolean<span class="Special"> <- </span>channel-full? 1:address:channel
]
memory-should-contain [
2<span class="Special"> <- </span>1 <span class="Comment"># empty?</span>
3<span class="Special"> <- </span>0 <span class="Comment"># full?</span>
]
]
<span class="Comment"># helper for channels of characters in particular</span>
<span class="Comment"># out:address:channel <- buffer-lines in:address:channel, out:address:channel</span>
recipe buffer-lines [
default-space:address:address:array:location<span class="Special"> <- </span>new location:type, <span class="Constant">30:literal</span>
<span class="CommentedCode">#? $print [buffer-lines: aaa</span>
<span class="CommentedCode">#? ]</span>
in:address:channel<span class="Special"> <- </span>next-ingredient
out:address:channel<span class="Special"> <- </span>next-ingredient
<span class="Comment"># repeat forever</span>
<span class="Delimiter">{</span>
line:address:buffer<span class="Special"> <- </span>init-buffer, <span class="Constant">30:literal</span>
<span class="Comment"># read characters from 'in' until newline, copy into line</span>
<span class="Delimiter">{</span>
<span class="Identifier"> +next-character</span>
c:character, in:address:channel<span class="Special"> <- </span>read in:address:channel
<span class="Comment"># drop a character on backspace</span>
<span class="Delimiter">{</span>
<span class="Comment"># special-case: if it's a backspace</span>
backspace?:boolean<span class="Special"> <- </span>equal c:character, <span class="Constant">8:literal</span>
<span class="Identifier">break-unless</span> backspace?:boolean
<span class="Comment"># drop previous character</span>
<span class="CommentedCode">#? return-to-console #? 2</span>
<span class="CommentedCode">#? $print [backspace! #? 1</span>
<span class="CommentedCode">#? ] #? 1</span>
<span class="Delimiter">{</span>
buffer-length:address:number<span class="Special"> <- </span>get-address line:address:buffer/deref, length:offset
buffer-empty?:boolean<span class="Special"> <- </span>equal buffer-length:address:number/deref, <span class="Constant">0:literal</span>
<span class="Identifier">break-if</span> buffer-empty?:boolean
<span class="CommentedCode">#? $print [before: ], buffer-length:address:number/deref, [ </span>
<span class="CommentedCode">#? ] #? 1</span>
buffer-length:address:number/deref<span class="Special"> <- </span>subtract buffer-length:address:number/deref, <span class="Constant">1:literal</span>
<span class="CommentedCode">#? $print [after: ], buffer-length:address:number/deref, [ </span>
<span class="CommentedCode">#? ] #? 1</span>
<span class="Delimiter">}</span>
<span class="CommentedCode">#? $exit #? 2</span>
<span class="Comment"># and don't append this one</span>
<span class="Identifier">loop</span><span class="Identifier"> +next-character</span>:label
<span class="Delimiter">}</span>
<span class="Comment"># append anything else</span>
<span class="CommentedCode">#? $print [buffer-lines: appending ], c:character, [ </span>
<span class="CommentedCode">#? ]</span>
line:address:buffer<span class="Special"> <- </span>buffer-append line:address:buffer, c:character
line-done?:boolean<span class="Special"> <- </span>equal c:character, <span class="Constant">10:literal/newline</span>
<span class="Identifier">break-if</span> line-done?:boolean
<span class="Comment"># stop buffering on eof (currently only generated by fake keyboard)</span>
empty-fake-keyboard?:boolean<span class="Special"> <- </span>equal c:character, <span class="Constant">0:literal/eof</span>
<span class="Identifier">break-if</span> empty-fake-keyboard?:boolean
<span class="Identifier">loop</span>
<span class="Delimiter">}</span>
<span class="CommentedCode">#? return-to-console #? 1</span>
<span class="Comment"># copy line into 'out'</span>
<span class="CommentedCode">#? $print [buffer-lines: emitting</span>
<span class="CommentedCode">#? ]</span>
i:number<span class="Special"> <- </span>copy <span class="Constant">0:literal</span>
line-contents:address:array:character<span class="Special"> <- </span>get line:address:buffer/deref, data:offset
max:number<span class="Special"> <- </span>get line:address:buffer/deref, length:offset
<span class="Delimiter">{</span>
done?:boolean<span class="Special"> <- </span>greater-or-equal i:number, max:number
<span class="Identifier">break-if</span> done?:boolean
c:character<span class="Special"> <- </span>index line-contents:address:array:character/deref, i:number
out:address:channel<span class="Special"> <- </span>write out:address:channel, c:character
<span class="CommentedCode">#? $print [writing ], i:number, [: ], c:character, [ </span>
<span class="CommentedCode">#? ] #? 1</span>
i:number<span class="Special"> <- </span>add i:number, <span class="Constant">1:literal</span>
<span class="Identifier">loop</span>
<span class="Delimiter">}</span>
<span class="CommentedCode">#? $dump-trace #? 1</span>
<span class="CommentedCode">#? $exit #? 1</span>
<span class="Identifier">loop</span>
<span class="Delimiter">}</span>
<span class="Identifier">reply</span> out:address:channel/same-as-ingredient:1
]
scenario buffer-lines-blocks-until-newline [
run [
1:address:channel/stdin<span class="Special"> <- </span>init-channel <span class="Constant">10:literal/capacity</span>
2:address:channel/buffered-stdin<span class="Special"> <- </span>init-channel <span class="Constant">10:literal/capacity</span>
3:boolean<span class="Special"> <- </span>channel-empty? 2:address:channel/buffered-stdin
assert 3:boolean, [
F buffer-lines-blocks-until-newline: channel should be empty after init]
<span class="Comment"># buffer stdin into buffered-stdin, try to read from buffered-stdin</span>
4:number/buffer-routine<span class="Special"> <- </span>start-running buffer-lines:recipe, 1:address:channel/stdin, 2:address:channel/buffered-stdin
wait-for-routine 4:number/buffer-routine
5:boolean<span class="Special"> <- </span>channel-empty? 2:address:channel/buffered-stdin
assert 5:boolean, [
F buffer-lines-blocks-until-newline: channel should be empty after buffer-lines bring-up]
<span class="Comment"># write 'a'</span>
1:address:channel<span class="Special"> <- </span>write 1:address:channel, <span class="Constant">97:literal/a</span>
restart 4:number/buffer-routine
wait-for-routine 4:number/buffer-routine
6:boolean<span class="Special"> <- </span>channel-empty? 2:address:channel/buffered-stdin
assert 6:boolean, [
F buffer-lines-blocks-until-newline: channel should be empty after writing<span class="Identifier"> 'a</span>']
<span class="Comment"># write 'b'</span>
1:address:channel<span class="Special"> <- </span>write 1:address:channel, <span class="Constant">98:literal/b</span>
restart 4:number/buffer-routine
wait-for-routine 4:number/buffer-routine
7:boolean<span class="Special"> <- </span>channel-empty? 2:address:channel/buffered-stdin
assert 7:boolean, [
F buffer-lines-blocks-until-newline: channel should be empty after writing<span class="Identifier"> 'b</span>']
<span class="Comment"># write newline</span>
1:address:channel<span class="Special"> <- </span>write 1:address:channel, <span class="Constant">10:literal/newline</span>
restart 4:number/buffer-routine
wait-for-routine 4:number/buffer-routine
8:boolean<span class="Special"> <- </span>channel-empty? 2:address:channel/buffered-stdin
9:boolean/completed?<span class="Special"> <- </span>not 8:boolean
assert 9:boolean/completed?, [
F buffer-lines-blocks-until-newline: channel should contain data after writing newline]
trace <span class="Constant">[test]</span>, <span class="Constant">[reached end]</span>
]
trace-should-contain [
test: reached end
]
]
</pre>
</body>
</html>
<!-- vim: set foldmethod=manual : -->