tag:blogger.com,1999:blog-6967193071530900382024-03-05T14:49:23.686-05:00Struggling Through ProblemsOwenhttp://www.blogger.com/profile/09697040246092989242noreply@blogger.comBlogger59125tag:blogger.com,1999:blog-696719307153090038.post-36843435813640597452021-01-15T00:17:00.002-05:002021-01-15T00:17:59.431-05:00Can we have anti-lambdas please?<p>Aren’t you tired of flattening your code to avoid repeated computation:</p>
<pre class=" language-scala"><code class="prism language-scala"><span class="token keyword">val</span> x <span class="token operator">=</span> longComputation<span class="token punctuation">(</span><span class="token punctuation">)</span>
ls map <span class="token punctuation">{</span> y <span class="token keyword">=></span>
<span class="token punctuation">(</span>x<span class="token punctuation">,</span> y<span class="token punctuation">)</span>
<span class="token punctuation">}</span>
</code></pre>
<p>when you’d rather write</p>
<pre class=" language-scala"><code class="prism language-scala">ls map <span class="token punctuation">{</span> y <span class="token keyword">=></span>
<span class="token punctuation">(</span>
longComputation<span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span>
y
<span class="token punctuation">)</span>
<span class="token punctuation">}</span>
</code></pre>
<p>because it’s more compact, but if you had an anti-lambda you could write</p>
<pre class=" language-scala"><code class="prism language-scala">ls map <span class="token punctuation">{</span> y <span class="token keyword">=></span>
<span class="token punctuation">(</span>
<span class="token operator"><=</span> y <span class="token punctuation">(</span> longComputation<span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">,</span>
y
<span class="token punctuation">)</span>
<span class="token punctuation">}</span>
</code></pre>
<p>where the anti-lambda <code><= y ( ... )</code> cancels out the parameter <code>y</code> making <code>longComputation()</code> constant and evaluated only once (essentially making it part of the closure’s local environment).</p>
Owenhttp://www.blogger.com/profile/09697040246092989242noreply@blogger.com0tag:blogger.com,1999:blog-696719307153090038.post-67009701944232792682020-11-28T23:48:00.000-05:002020-11-28T23:48:31.689-05:00So you want to write a udev rule<p>I too once thought as you did.</p>
<p>It began with wanting to run a program every time a keyboard was plugged in. "That should be simple," I thought. "I'll just write a udev rule." And so it began.</p>
<p>But what should the udev rule trigger on? What "KERNEL"? What "SUBSYSTEM"? What even <em>is</em> a keyboard?</p>
<p>Like all great systemd mysteries, this one has an unsatisfying solution. Just plug in your keyboard and run</p>
<pre style="overflow-x: scroll;">$ sudo udevadm info -a -n /dev/input/event19
...
looking at device '/devices/pci0000:00/0000:00:14.0/usb1/1-1/1-1:1.0/0003:413C:2107.0009/input/input39/event19':
KERNEL=="event19"
SUBSYSTEM=="input"
DRIVER==""
ATTR{power/async}=="disabled"
ATTR{power/control}=="auto"
ATTR{power/runtime_active_kids}=="0"
ATTR{power/runtime_active_time}=="0"
ATTR{power/runtime_enabled}=="disabled"
ATTR{power/runtime_status}=="unsupported"
ATTR{power/runtime_suspended_time}=="0"
ATTR{power/runtime_usage}=="0"
looking at parent device '/devices/pci0000:00/0000:00:14.0/usb1/1-1/1-1:1.0/0003:413C:2107.0009/input/input39':
KERNELS=="input39"
SUBSYSTEMS=="input"
DRIVERS==""
ATTRS{capabilities/abs}=="0"
ATTRS{capabilities/ev}=="120013"
ATTRS{capabilities/ff}=="0"
ATTRS{capabilities/key}=="1000000000007 ff9f207ac14057ff febeffdfffefffff fffffffffffffffe"
ATTRS{capabilities/led}=="7"
ATTRS{capabilities/msc}=="10"
ATTRS{capabilities/rel}=="0"
ATTRS{capabilities/snd}=="0"
...
</pre>
<p>(with many, many lines omitted for brevity)</p>
<p>Then guess which of those attributes makes a keyboard. Is it the <code>ATTRS{capabilities/ev}</code> The <code>ATTRS{idProduct}</code> No, it must be the <code>ATTRS{bcdDevice}</code>.</p>
<p>I'll spare you the 23 permutations I tried. In the end, there is nothing that identifies a keyboard.</p>
<p>(Well, that's not <em>quite</em> true. A USB keyboard can be identified by <code>bInterfaceClass</code> and <code>bInterfaceSubClass</code>. But my laptop has a builtin as well as USB keyboard, and who knows, maybe someday I'll have PS/2 keyboard for good measure. So I wanted a more accurate solution.)</p>
<p>You see, Linux input devices are very general things. What you humans call a "keyboard", Linux sees as an input device that happens to have a lot of keys. But it's not the only device with keys: your power button has a key. Your lid switch has a key or two. Your media buttons might have a few keys as well. The difference is your keyboard has a <em>lot</em> of keys.</p>
<p>Miraculously, putting a <code>*</code> in the KERNEL parameter is a valid wildcard, so the following rule matches any input device:</p>
<p><code>KERNEL=="event*", ACTION=="add", RUN+="/usr/bin/totalmapper remap --only-if-keyboard --dev-file <a href="https://linux.die.net/man/7/udev">%N"</a></code></p>
<p>Then it's up to the invoked program to decide whether the input device is keyboardy enough to qualify.</p>
<p>Ok, but how do you do <em>that</em>? Will it involve an obscure <code>ioctl</code> on the device file?</p>
<p>Mabye, but there's another way. In <code>/proc/bus/input/devices</code> is a list of your input devices along with a bitmask specifying which keys they have (the <code>B: KEY=</code> line):</p>
<pre>I: Bus=0019 Vendor=0000 Product=0001 Version=0000
N: Name="Power Button"
P: Phys=PNP0C0C/button/input0
S: Sysfs=/devices/LNXSYSTM:00/LNXSYBUS:00/PNP0C0C:00/input/input0
U: Uniq=
H: Handlers=kbd event0
B: PROP=0
B: EV=3
B: KEY=10000000000000 0
I: Bus=0011 Vendor=0001 Product=0001 Version=ab54
N: Name="AT Translated Set 2 keyboard"
P: Phys=isa0060/serio0/input0
S: Sysfs=/devices/platform/i8042/serio0/input/input2
U: Uniq=
H: Handlers=sysrq kbd event2 leds
B: PROP=0
B: EV=120013
B: KEY=402000000 3803078f800d001 feffffdfffefffff fffffffffffffffe
B: MSC=10
B: LED=7</pre>
<p>Count up the 1 bits, and then decide how many keys is enough to count as a keyboard (10 was enough to exclude my lid switch, but 5 was too few).</p>
<p>This worked great, until a new problem arose.</p>
<p>The invoked program was supposed to keep running so that it could keep remapping keys. But it would quickly die.</p>
<p>"Ok," I thought. "udev must not like blocking processes. I'll just fork() a child."</p>
<p>But the process kept dying.</p>
<p>Ah, of course! I need to <code>signal(SIGHUP, SIG_IGN)</code> to ignore the signal generated when the parent terminates.</p>
<p>But the process kept dying.</p>
<p>Oh, that's it! I need to redirect stdout and stderr so the process doesn't get a broken pipe!</p>
<p>But the process kept dying.</p>
<p>It was late at night when I stumbled across this beautiful sentence from the udev manpage:</p>
<blockquote>Starting daemons or other long-running processes is not allowed; the forked processes, detached or not, will be unconditionally killed after the event handling has finished.</blockquote>
<p>"unconditionally".</p>
<p>Well, that settles that. It's "not allowed." So what's the solution?</p>
<p>Helpfully, the same manpage suggests using the udev rule to start a systemd service. And it turns out it's possible to make a "template" systemd service using an '@' sign in the filename as a wildcard. So, I made the following udev rule:</p>
<p><code>KERNEL=="event*", ACTION=="add", TAG+="systemd", ENV{SYSTEMD_WANTS}="totalmapper@%N.service"</code></p>
<p>And the following service in <code>/etc/systemd/system/totalmapper@.service</code>:</p>
<p style="white-space: pre-wrap;"><code>[Unit]
StopWhenUnneeded=true
Description=Totalmapper
[Service]
Type=simple
User=nobody
Group=input
ExecStart=/usr/bin/totalmapper remap --layout-file /etc/totalmapper.json --only-if-keyboard --dev-file %I</code></p>
<p>(The <code>%I</code> flag provides the template parameter, which in this case was the device file.)</p>
<p>It was at this point that my problems shifted from annoying to catastrophic. You see, the keyboard remapping utility works by creating a synthetic keyboard device through <code>/dev/uinput</code> that it can use to send key events. But udev picks up on <em>that</em> keyboard device, and starts a another systemd service for it, starting another keyboard mapper, and so on...</p>
<p>How many input devices can you have on Linux? I <em>think</em> the answer is 1000. At least, it stopped making new keyboad devices after that.</p>
<p>Ok. So. In addition to checking whether the device is a keyboard, the mapping tool needs to check whether it is a physical device or synthetic, and only remap it if it's a physical device. But how do you do <em>that</em>?</p>
<p>Well, back in our trusty <code>/proc/bus/input/devices</code> is a line <code>S: Sysfs=</code>, which gives the path to the device under <code>/sys</code>. Non-physical keyboards have a sysfs path that begins <code>/devices/virtual</code>.</p>
<p>And now it works.</p>
Owenhttp://www.blogger.com/profile/09697040246092989242noreply@blogger.com1tag:blogger.com,1999:blog-696719307153090038.post-53866039118651746692020-11-28T18:13:00.000-05:002020-11-28T18:13:34.023-05:00Remapping keys<p>Keyboards are more complicated than they first appear.</p>
<p>For example, suppose I want to map <kbd>Shift</kbd> + <kbd>A</kbd> to <kbd>=</kbd>.</p>
<p>I press <kbd>Shift</kbd>. A <kbd>Shift</kbd> keycode should be generated (the mapping isn't triggered yet). I press <kbd>A</kbd>. Now:</p>
<ul>
<li>The <kbd>A</kbd> keycode should <em>not</em> be generated—the mapping consumes it.</li>
<li>The <kbd>=</kbd> keycode should be generated, because the mapping produced it.</li>
</ul>
<p>But wait—there's another step. <kbd>Shift</kbd> is still down, and <kbd>Shift</kbd> + <kbd>=</kbd> gives a '+' sign. So before the <kbd>=</kbd> keycode is generated, the <kbd>Shift</kbd> needs to be released.</p>
<p>Now I release the <kbd>A</kbd> key. The <kbd>=</kbd> keycode should be released. But the <kbd>Shift</kbd> (physical key) is still down. Should the <kbd>Shift</kbd> keycode be reinstated now that it's no longer consumed by the mapping?</p>
<p>No, that's (for some reason) not how keyboards behave. Only pressing a key can cause a new keycode to be pressed, even where key combinations are used.</p>
<p>Try it with your <kbd>Fn</kbd> key: Hold down <kbd>Fn</kbd>, then press <kbd>F1</kbd>, then release <kbd>Fn</kbd>. This does not trigger an <kbd>F1</kbd> keycode.</p>
<p>After puzzling over this logic for awhile, I eventually created <a href="https://github.com/ellbur/totalmapper">a tool</a> that let's you remap keys using rules like the following:</p>
<pre>[
{ "from": [ "CAPSLOCK" ], "to": [] },
{ "from": [ "CAPSLOCK", "J" ], "to": [ "LEFT" ] },
{ "from": [ "CAPSLOCK", "I" ], "to": [ "UP" ] },
{ "from": [ "CAPSLOCK", "K" ], "to": [ "DOWN" ] },
{ "from": [ "CAPSLOCK", "L" ], "to": [ "RIGHT" ] },
{ "from": [ "CAPSLOCK", "H" ], "to": [ "HOME" ] },
{ "from": [ "CAPSLOCK", "SEMICOLON" ], "to": [ "END" ] },
{ "from": [ "CAPSLOCK", "U" ], "to": [ "PAGEUP" ] },
{ "from": [ "CAPSLOCK", "M" ], "to": [ "PAGEDOWN" ] },
{ "from": [ "CAPSLOCK", "N" ], "to": [ "LEFTCTRL", "LEFT" ] },
{ "from": [ "CAPSLOCK", "COMMA" ], "to": [ "LEFTCTRL", "RIGHT" ] }
]</pre>
<p>Don't you wish any key could be a modifier? Now it can.</p>
Owenhttp://www.blogger.com/profile/09697040246092989242noreply@blogger.com0tag:blogger.com,1999:blog-696719307153090038.post-32508434628777316832020-08-02T18:00:00.000-04:002020-08-02T18:00:04.983-04:00Digital circuits in two-dimensional time<p>Time appears to be one-dimensional. But does it have to be that way?</p>
<p>For example, here is a simulation of a ball bouncing in two dimensions of time, <code>t<sub>x</sub></code> and <code>t<sub>y</sub></code>:</p>
<p style="text-align: center;"><img height="400" src="https://d35yeutfwbbcir.cloudfront.net/hosting/2020-08-02/0yoxdim6w5/ball-height-annotated.svg" width="400" /></p>
<p>The ball's velocity is an orientation (tangent plane or normal vector) in <code>(t<sub>x</sub>, t<sub>y</sub>, h)</code> space, and its acceleration (from gravity) is the local curvature of the surface.</p>
<p>But suppose you built a digital circuit in a universe with two time dimensions. Specifically, a synchronous digital circuit, whose discrete state <code>S</code> is a function of two discrete time variables, <code>i<sub>x</sub></code> and <code>i<sub>y</sub></code>:</p>
<p style="text-align: center;"><img src="https://d35yeutfwbbcir.cloudfront.net/hosting/2020-08-02/0qvg63blcv/grid-1.svg" /></p>
<p>State changes are driven by a pair of two-dimensional clocks:</p><p><br /></p>
<p style="text-align: center;"><img src="https://d35yeutfwbbcir.cloudfront.net/hosting/2020-08-02/nxq1k0z7oj/grid-2.svg"/></p>
<p>As the system crosses over a clock edge, it transitions according to a pair of rules:</p>
<p style="text-align: center;"><code>S<sub>i<sub>x</sub>,i<sub>y</sub></sub></code> = f<sub>x</sub>(<code>S<sub>i<sub>x</sub>-1,i<sub>y</sub></sub></code>)<br/>
<code>S<sub>i<sub>x</sub>,i<sub>y</sub></sub></code> = f<sub>y</sub>(<code>S<sub>i<sub>x</sub>,i<sub>y</sub>-1</sub></code>)</p>
But wait! This creates a potential inconsistency:
<p style="text-align: center;"><img src="https://d35yeutfwbbcir.cloudfront.net/hosting/2020-08-02/f2ang6rh2b/diamond.svg"/></p>
<p>Such state transitions only avoid a race condition at the intersection of rising edges if <code>f<sub>x</sub> · f<sub>y</sub> = f<sub>y</sub> · f<sub>x</sub></code>.</p>
<p>Well, that's possible. For example, the following state transitions satisfy the above consistency criterion:</p>
<style>
table.fx-fy-table {
border-collapse: collapse;
}
table.fx-fy-table td {
width: 3em;
text-align: center;
}
table.fx-fy-table th {
width: 3em;
border-bottom: 1px solid black;
text-align: center;
}
table.fx-fy-table th:nth-child(1) {
border-right: 1px solid black;
}
table.fx-fy-table td:nth-child(1) {
border-right: 1px solid black;
}
</style>
<table class="fx-fy-table">
<tr>
<th>S</th>
<th>f<sub>x</sub>(S)</th>
<th>f<sub>y</sub>(S)</th>
</tr>
<tr>
<td>A</td>
<td>B</td>
<td>C</td>
</tr>
<tr>
<td>B</td>
<td>A</td>
<td>D</td>
</tr>
<tr>
<td>C</td>
<td>D</td>
<td>A</td>
</tr>
<tr>
<td>D</td>
<td>C</td>
<td>B</td>
</tr>
</table>
<p>The problem is, if <code>f<sub>x</sub> · f<sub>y</sub> = f<sub>y</sub> · f<sub>x</sub></code>, then any sequence</p>
<p style="text-align: center;"><code>f<sub>x</sub> · ... · f<sub>y</sub> · ... · f<sub>y</sub> · ... · f<sub>x</sub></code></p>
<p>is just</p>
<p style="text-align: center;"><code>f<sub>x</sub> · ... · f<sub>x</sub> (n times) · f<sub>y</sub> · ... · f<sub>y</sub> (m times)</code>.</p>
<p>That is, there is no interaction between the two time dimensions. The system is, for all intents and purposes, two independent systems, each with one-dimensional time. And, if you lived in such a universe, you would never know, because each version of "you" would have no way of knowing about the other.</p>
<p>And so it would be just like the world we know.</p>
Owenhttp://www.blogger.com/profile/09697040246092989242noreply@blogger.com0tag:blogger.com,1999:blog-696719307153090038.post-12205384571001779012017-07-23T11:11:00.000-04:002017-07-23T11:14:33.351-04:00redo-signals: Breaking cycles<p>Consider a slider/text-field:</p>
<p><img src="http://d35yeutfwbbcir.cloudfront.net/slider-text-field.svg"/></p>
<p>When the user edits one, the other should update to match:</p>
<p><img src="http://d35yeutfwbbcir.cloudfront.net/slider-text-field-3.svg"/></p>
<p>Can we express this in FRP-style?</p>
<pre style="background-color: rgb(255, 255, 255); font-family: "DejaVu Sans Mono"; font-size: 12pt;"><span style="color:#000080;font-weight:bold;">val </span>textField <span style="color:#a23364;">= </span><span style="color:#000080;font-weight:bold;">new </span>JTextField<span style="color:#6a762a;">(</span><span style="color:#008000;font-weight:bold;">"50"</span>, <span style="color:#0000ff;">6</span><span style="color:#6a762a;">)<br></span><span style="color:#000080;font-weight:bold;">val </span>slider <span style="color:#a23364;">= </span><span style="color:#000080;font-weight:bold;">new </span>JSlider<br><br><span style="color:#000080;font-weight:bold;">val </span>win <span style="color:#a23364;">= </span><span style="color:#000080;font-weight:bold;">new </span>JFrame<span style="color:#6a762a;">(</span><span style="color:#008000;font-weight:bold;">"Test"</span><span style="color:#6a762a;">)<br></span>win.setDefaultCloseOperation<span style="color:#6a762a;">(</span>JFrame.EXIT_ON_CLOSE<span style="color:#6a762a;">)<br></span>win.setLayout<span style="color:#6a762a;">(</span><span style="color:#000080;font-weight:bold;">new </span>FlowLayout<span style="color:#6a762a;">)<br></span>win.add<span style="color:#6a762a;">(</span>textField<span style="color:#6a762a;">)<br></span>win.add<span style="color:#6a762a;">(</span>slider<span style="color:#6a762a;">)<br></span>win.pack<span style="color:#6a762a;">()<br></span>win.setLocationRelativeTo<span style="color:#6a762a;">(</span><span style="color:#000080;font-weight:bold;">null</span><span style="color:#6a762a;">)<br></span>win.setVisible<span style="color:#6a762a;">(</span><span style="color:#000080;font-weight:bold;">true</span><span style="color:#6a762a;">)<br></span><span style="color:#6a762a;"><br></span>textField.text.foreachDelayed <span style="color:#a92b58;">{ </span>text => <span style="color:#000080;font-weight:bold;">implicit </span>u =><br> slider.value.updateLater<span style="color:#6a762a;">(</span>text map <span style="color:#a92b58;">{ </span>text =><br> Try<span style="color:#6a762a;">(</span>text.toInt<span style="color:#6a762a;">) </span><span style="color:#000080;font-weight:bold;">match </span><span style="color:#a92b58;">{<br></span><span style="color:#a92b58;"> </span><span style="color:#000080;font-weight:bold;">case </span>Failure<span style="color:#6a762a;">(</span>_<span style="color:#6a762a;">) </span>=> slider.value.now<br> <span style="color:#000080;font-weight:bold;">case </span>Success<span style="color:#6a762a;">(</span>value<span style="color:#6a762a;">) </span>=> value<br> <span style="color:#a92b58;">}<br></span><span style="color:#a92b58;"> }</span><span style="color:#6a762a;">)<br></span><span style="color:#a92b58;">} </span><span style="color:#6a762a;">(</span>slider.value.redoObserving<span style="color:#6a762a;">)<br></span><span style="color:#6a762a;"><br></span>slider.value.foreachDelayed <span style="color:#a92b58;">{ </span>value => <span style="color:#000080;font-weight:bold;">implicit </span>u =><br> textField.text.updateLater<span style="color:#6a762a;">(</span>value map <span style="color:#6a762a;">(</span>_.toString<span style="color:#6a762a;">))<br></span><span style="color:#a92b58;">} </span><span style="color:#6a762a;">(</span>textField.text.redoObserving<span style="color:#6a762a;">)</span></pre>
<p>It turns out we can. But the code looks cyclical... how does it not produce an infinite loop?</p>
<p><code>foreachDelayed</code> comes to the rescue. It runs on the invalidation sweep. A signal can only be invalidated once before it is recalculated. So, the invalidation sweep can never produce an infinite loop; it simply traverses the graph of signals and invalidates each one it hits.</p>Owenhttp://www.blogger.com/profile/09697040246092989242noreply@blogger.com0tag:blogger.com,1999:blog-696719307153090038.post-62261602349644251662017-07-22T19:52:00.000-04:002017-07-22T19:52:41.774-04:00redo-signals: Planting imperative trees in a declarative forest<p><a href="https://github.com/ellbur/redo-signals-core"><code>redo-signals</code></a> is a Scala library for <a href="https://infoscience.epfl.ch/record/176887/files/DeprecatingObservers2012.pdf">functional reactive programming</a>. With <code>redo-signals</code>, you write declarative code:</p>
<pre style="background-color: rgb(255, 255, 255); font-family: "DejaVu Sans Mono"; font-size: 12pt;"><span style="color:#000080;font-weight:bold;">val </span>x <span style="color:#a23364;">= </span><span style="color:#000080;font-weight:bold;">new </span>Source[Int]<span style="color:#6a762a;">(</span><span style="color:#0000ff;">0</span><span style="color:#6a762a;">)<br></span><span style="color:#000080;font-weight:bold;">val </span>y <span style="color:#a23364;">= </span><span style="color:#000080;font-weight:bold;">new </span>Source[Int]<span style="color:#6a762a;">(</span><span style="color:#0000ff;">0</span><span style="color:#6a762a;">)<br></span><span style="color:#6a762a;"><br></span><span style="color:#000080;font-weight:bold;">val </span>z <span style="color:#a23364;">= </span>tracking <span style="color:#a92b58;">{ </span><span style="color:#000080;font-weight:bold;">implicit </span>t =><br> x.track + y.track<br><span style="color:#a92b58;">}</span></pre>
<p><img src="http://d35yeutfwbbcir.cloudfront.net/xy.svg" /></p>
<p>But some behavior is poorly suited to declarative style. Consider the following set of rules:</p>
<ol>
<li>For every element of <code>sourceList1</code>, ensure there exists a <code>Type1Worker</code> worker in <code>workerList</code>.</li>
<li>For every element of <code>sourceList2</code>, ensure there exists a <code>Type2Worker</code> worker in <code>workerList</code>.</li>
<li>Don't remove or re-create workers.</li>
</ol>
<p>You could write these rules declaratively, but they are more natural as imperative code:</p>
<pre style="background-color: rgb(255, 255, 255); font-family: "DejaVu Sans Mono"; font-size: 12pt;">sourceList1.zipWithStalenessFrom<span style="color:#6a762a;">(</span><span style="color:#660e7a;font-style:italic;">Seq</span><span style="color:#6a762a;">())</span>.foreach <span style="color:#a92b58;">{ </span><span style="color:#000080;font-weight:bold;">case </span><span style="color:#6a762a;">(</span>oldXs, newXs<span style="color:#6a762a;">) </span>=><br> workerList<span style="color:#6a762a;">() </span><span style="color:#a23364;">= </span>workerList.now ++ <span style="color:#6a762a;">((</span>newXs.toSet -- oldXs.toSet<span style="color:#6a762a;">) </span>map <span style="color:#6a762a;">(</span><span style="color:#000080;font-weight:bold;">new </span>Type1Worker<span style="color:#6a762a;">(</span>_<span style="color:#6a762a;">)))<br></span><span style="color:#a92b58;">}<br></span><span style="color:#a92b58;"><br></span>sourceList2.zipWithStalenessFrom<span style="color:#6a762a;">(</span><span style="color:#660e7a;font-style:italic;">Seq</span><span style="color:#6a762a;">())</span>.foreach <span style="color:#a92b58;">{ </span><span style="color:#000080;font-weight:bold;">case </span><span style="color:#6a762a;">(</span>oldXs, newXs<span style="color:#6a762a;">) </span>=><br> workerList<span style="color:#6a762a;">() </span><span style="color:#a23364;">= </span>workerList.now ++ <span style="color:#6a762a;">((</span>newXs.toSet -- oldXs.toSet<span style="color:#6a762a;">) </span>map <span style="color:#6a762a;">(</span><span style="color:#000080;font-weight:bold;">new </span>Type2Worker<span style="color:#6a762a;">(</span>_<span style="color:#6a762a;">)))<br></span><span style="color:#a92b58;">}</span></pre>
<p>But this introduces an unintended consequence. Supposing <code>sourceList1</code> and <code>sourceList2</code> originate from the same source. Upon every change in the source data, each <code>foreach()</code> will execute once, resulting in two updates to <code>workerList</code>, when there should be only one.</p>
<p>Consider the following complete example:</p>
<pre style="background-color: rgb(255, 255, 255); font-family: "DejaVu Sans Mono"; font-size: 12pt;"><span style="color:#000080;font-weight:bold;">case class </span>Payload<span style="color:#6a762a;">(</span>name: <span style="color:#20999d;">String</span><span style="color:#6a762a;">)<br></span><span style="color:#000080;font-weight:bold;">trait </span>Worker<br><span style="color:#000080;font-weight:bold;">class </span>Type1Worker<span style="color:#6a762a;">(</span><span style="color:#000080;font-weight:bold;">val </span>payload: Payload<span style="color:#6a762a;">) </span><span style="color:#000080;font-weight:bold;">extends </span>Worker<br><span style="color:#000080;font-weight:bold;">class </span>Type2Worker<span style="color:#6a762a;">(</span><span style="color:#000080;font-weight:bold;">val </span>payload: Payload<span style="color:#6a762a;">) </span><span style="color:#000080;font-weight:bold;">extends </span>Worker<br><br><span style="color:#000080;font-weight:bold;">val </span>rootSourceList <span style="color:#a23364;">= </span><span style="color:#000080;font-weight:bold;">new </span>Source[<span style="color:#20999d;">Seq</span>[Payload]]<span style="color:#6a762a;">(</span><span style="color:#660e7a;font-style:italic;">Seq</span><span style="color:#6a762a;">())<br></span><span style="color:#6a762a;"><br></span><span style="color:#000080;font-weight:bold;">val </span>sourceList1 <span style="color:#a23364;">= </span>rootSourceList map <span style="color:#6a762a;">(</span>_ filter <span style="color:#6a762a;">(</span>_.name.startsWith<span style="color:#6a762a;">(</span><span style="color:#008000;font-weight:bold;">"a"</span><span style="color:#6a762a;">)))<br></span><span style="color:#000080;font-weight:bold;">val </span>sourceList2 <span style="color:#a23364;">= </span>rootSourceList map <span style="color:#6a762a;">(</span>_ filter <span style="color:#6a762a;">(</span>_.name.startsWith<span style="color:#6a762a;">(</span><span style="color:#008000;font-weight:bold;">"b"</span><span style="color:#6a762a;">)))<br></span><span style="color:#6a762a;"><br></span><span style="color:#000080;font-weight:bold;">val </span>workerList <span style="color:#a23364;">= </span><span style="color:#000080;font-weight:bold;">new </span>Source[<span style="color:#20999d;">Seq</span>[Worker]]<span style="color:#6a762a;">(</span><span style="color:#660e7a;font-style:italic;">Seq</span><span style="color:#6a762a;">()</span>, debugName <span style="color:#a23364;">= </span>Some<span style="color:#6a762a;">(</span><span style="color:#008000;font-weight:bold;">"workerList"</span><span style="color:#6a762a;">))<br></span><span style="color:#6a762a;"><br></span>sourceList1.zipWithStalenessFrom<span style="color:#6a762a;">(</span><span style="color:#660e7a;font-style:italic;">Seq</span><span style="color:#6a762a;">())</span>.foreach <span style="color:#a92b58;">{ </span><span style="color:#000080;font-weight:bold;">case </span><span style="color:#6a762a;">(</span>oldXs, newXs<span style="color:#6a762a;">) </span>=><br> workerList<span style="color:#6a762a;">() </span><span style="color:#a23364;">= </span>workerList.now ++ <span style="color:#6a762a;">((</span>newXs.toSet -- oldXs.toSet<span style="color:#6a762a;">) </span>map <span style="color:#6a762a;">(</span><span style="color:#000080;font-weight:bold;">new </span>Type1Worker<span style="color:#6a762a;">(</span>_<span style="color:#6a762a;">)))<br></span><span style="color:#a92b58;">} </span><span style="color:#6a762a;">(</span>workerList.<span style="color:#660e7a;font-style:italic;">redoObserving</span><span style="color:#6a762a;">)<br></span><span style="color:#6a762a;"><br></span>sourceList2.zipWithStalenessFrom<span style="color:#6a762a;">(</span><span style="color:#660e7a;font-style:italic;">Seq</span><span style="color:#6a762a;">())</span>.foreach <span style="color:#a92b58;">{ </span><span style="color:#000080;font-weight:bold;">case </span><span style="color:#6a762a;">(</span>oldXs, newXs<span style="color:#6a762a;">) </span>=><br> workerList<span style="color:#6a762a;">() </span><span style="color:#a23364;">= </span>workerList.now ++ <span style="color:#6a762a;">((</span>newXs.toSet -- oldXs.toSet<span style="color:#6a762a;">) </span>map <span style="color:#6a762a;">(</span><span style="color:#000080;font-weight:bold;">new </span>Type2Worker<span style="color:#6a762a;">(</span>_<span style="color:#6a762a;">)))<br></span><span style="color:#a92b58;">} </span><span style="color:#6a762a;">(</span>workerList.<span style="color:#660e7a;font-style:italic;">redoObserving</span><span style="color:#6a762a;">)<br></span><span style="color:#6a762a;"><br></span>workerList foreach <span style="color:#a92b58;">{ </span>workers =><br> println<span style="color:#6a762a;">(</span><span style="color:#008000;font-weight:bold;">s"Now have </span><span style="color:#00b8bb;font-weight:bold;">$</span><span style="color:#a92b58;">{</span>workers.length<span style="color:#a92b58;">}</span><span style="color:#008000;font-weight:bold;"> workers"</span><span style="color:#6a762a;">)<br></span><span style="color:#a92b58;">}<br></span><span style="color:#a92b58;"><br></span><span style="color:#808080;font-style:italic;">// One update<br></span>rootSourceList<span style="color:#6a762a;">() </span><span style="color:#a23364;">= </span><span style="color:#660e7a;font-style:italic;">Seq</span><span style="color:#6a762a;">(</span>Payload<span style="color:#6a762a;">(</span><span style="color:#008000;font-weight:bold;">"a 1"</span><span style="color:#6a762a;">)</span>, Payload<span style="color:#6a762a;">(</span><span style="color:#008000;font-weight:bold;">"b 1"</span><span style="color:#6a762a;">))</span></pre>
<p>This prints</p>
<pre>Now have 0 workers
Now have 1 workers
Now have 2 workers</pre>
<p>Two updates appear in output: from 0 to 1, and from 1 to 2. How can we merge these into a single update?</p>
<p>The solution is to use <code>foreachDelayed</code>:</p>
<pre style="background-color: rgb(255, 255, 255); font-family: "DejaVu Sans Mono"; font-size: 12pt;">sourceList1.zipWithStalenessFrom<span style="color:#6a762a;">(</span><span style="color:#660e7a;font-style:italic;">Seq</span><span style="color:#6a762a;">())</span>.foreachDelayed <span style="color:#a92b58;">{ </span>xs => <span style="color:#000080;font-weight:bold;">implicit </span>u =><br> workerList.updateLater <span style="color:#a92b58;">{<br></span><span style="color:#a92b58;"> </span>xs map <span style="color:#a92b58;">{ </span><span style="color:#000080;font-weight:bold;">case </span><span style="color:#6a762a;">(</span>oldXs, newXs<span style="color:#6a762a;">) </span>=><br> workerList.now ++ <span style="color:#6a762a;">((</span>newXs.toSet -- oldXs.toSet<span style="color:#6a762a;">) </span>map <span style="color:#6a762a;">(</span><span style="color:#000080;font-weight:bold;">new </span>Type1Worker<span style="color:#6a762a;">(</span>_<span style="color:#6a762a;">)))<br></span><span style="color:#6a762a;"> </span><span style="color:#a92b58;">}<br></span><span style="color:#a92b58;"> }<br></span><span style="color:#a92b58;">}</span><span style="color:#6a762a;">(</span>workerList.redoObserving<span style="color:#6a762a;">)<br></span><span style="color:#6a762a;"><br></span>sourceList2.zipWithStalenessFrom<span style="color:#6a762a;">(</span>Seq<span style="color:#6a762a;">())</span>.foreachDelayed <span style="color:#a92b58;">{ </span>xs => <span style="color:#000080;font-weight:bold;">implicit </span>u =><br> workerList.updateLater <span style="color:#a92b58;">{<br></span><span style="color:#a92b58;"> </span>xs map <span style="color:#a92b58;">{ </span><span style="color:#000080;font-weight:bold;">case </span><span style="color:#6a762a;">(</span>oldXs, newXs<span style="color:#6a762a;">) </span>=><br> workerList.now ++ <span style="color:#6a762a;">((</span>newXs.toSet -- oldXs.toSet<span style="color:#6a762a;">) </span>map <span style="color:#6a762a;">(</span><span style="color:#000080;font-weight:bold;">new </span>Type2Worker<span style="color:#6a762a;">(</span>_<span style="color:#6a762a;">)))<br></span><span style="color:#6a762a;"> </span><span style="color:#a92b58;">}<br></span><span style="color:#a92b58;"> }<br></span><span style="color:#a92b58;">}</span><span style="color:#6a762a;">(</span>workerList.redoObserving<span style="color:#6a762a;">)</span></pre>
<p>How does this work? In <code>redo-signals</code>, changes to the state of the world are made in two sweeps: the first sweeps invalidates all signals, and the second sweep executes listeners, which, in the process, often re-evaluate signals, causing them to become valid. <code>foreachDelayed</code> and <code>updateLater</code> allow the user to tap in to this procedure, by scheduling code to run on either the first or second sweep.</p>
<p>The body of the function passed to <code>foreachDelayed</code> runs on the first sweep -- the invalidation sweep. This means that it is guaranteed to run exactly once per update. However, because it is on the invalidation sweep, it's not allowed to look at the state of any signals, because any signal is at risk of being invalid.</p>
<p>So, it passes the work on to <code>updateLater</code>. <code>updateLater</code> is the complement to <code>foreachDelayed</code>. It schedules an update to run on the second sweep, execution sweep, at which time it may evaluate <code>xs</code> and <code>workerList.now</code>.</p>
<p>The result is that you can write imperative code that executes like declarative code -- no more than it has to. The various parts are schedules to run on the correct sweeps, and signals change their values exactly as many times as their are root changes to the system. And so imperative code mixes seamlessly into the declarative world.</p>
Owenhttp://www.blogger.com/profile/09697040246092989242noreply@blogger.com1tag:blogger.com,1999:blog-696719307153090038.post-68244192653052144172017-07-22T17:55:00.001-04:002017-07-22T17:55:48.491-04:00Peaks<p><img with="300" height="300" src="http://d35yeutfwbbcir.cloudfront.net/some-peaks-2.svg"/></p>Owenhttp://www.blogger.com/profile/09697040246092989242noreply@blogger.com0tag:blogger.com,1999:blog-696719307153090038.post-51395132460266051962017-06-04T18:02:00.002-04:002017-06-04T18:02:53.397-04:00The ∞ levels of programming<p>At the 0th level are functions. Functions operate on data. Data like 1 or 2 or "three".</p>
<pre>def f(x):
return x + 1</pre>
<p>At the 1th level are meta-functions, what you might call macros. Meta-functions operate on code.</p>
<pre><b>def reapply(</b>c<b>):</b>
<b>return apply(</b>c<b>.func, </b>c<b>)</b></pre>
<p><code><b>reapply(</b>f(2)<b>)</b></code> → <code>f(f(2))</code> → <code>4</code></p>
<p>There is of course meta-data as well, and a meta-function can operate on meta-data:<p>
<pre><b>map(reapply, [</b>f(2)<b>, </b>f(3)<b>, </b>f(4)<b>])</b></p></pre>
<p>At the 2th level are meta-meta-functions, that operate on meta-functions and meta-meta-data.</p>
<pre><u><b>def reapply(</b></u><b>c</b><u><b>):</b></u>
<u><b>return apply(</b></u><b>c</b><u><b>.func,</b></u> <b>c</b><u><b>)</b></u></pre>
<p><code><u><b>reapply(</b></u><b>reapply(</b>f(2)<b>)</b><u><b>)</b></u></code> → <code><b>reapply(reapply(</b>f(2)<b>))</b></code> → <code><b>reapply(</b>f(f(2)<b>)</b></code> → <code>f(f(f(2)))</code> → <code>5</code></p>
<p>And so on.</p>
<p>What the ∞ levels of programming give you is precision. Remember Scala continuations? Remember how <a href="https://stackoverflow.com/a/2218589/371739">you couldn't use <code>shift</code> inside a <code>map</code> or a <code>foreach</code></a>? Well that was because <code>shift</code> was a meta-function, and <code>map</code> was a function, and functions can't operate on meta-functions.</p>
<p>Or more concretely, <code>shift</code> tears apart the code itself. But when <code>shift</code> is mapped, you don't know yet--at compile time--where it will land. So you can't pull the code apart.</p>
<p>But with a meta-meta-map, and a meta-meta-list, you could meta-meta-map your shift over your meta-meta-list.</p>
<p>There's some analogy to <a href="chrome-extension://oemmndcbldboiebfnladdacbdfmadadm/https://www.tcs.ifi.lmu.de/lehre/ss-2012/fun/folien/skript-15-types-and-universes-in-agda">universes in type systems</a>, that the way to clarify statements about statements is to separate them by levels. When code may only refer to the level below it, a multitude of paradoxes go away.</p>
<p>And then the puzzle is how to compile it efficiently.</p>
Owenhttp://www.blogger.com/profile/09697040246092989242noreply@blogger.com0tag:blogger.com,1999:blog-696719307153090038.post-15176793808345402582017-03-13T12:40:00.001-04:002017-03-13T12:40:55.699-04:00My computer is haunted<p>After my computer sleeps, in certain GTK+ 3 applications, specific colors will not appear:</p>
<p><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhnKYt_JWBl081sI3OS4TY9nM5-kiwH1qH_C4NPz0deh7uSphADOSwPOUqJYQc_O0H85BhfUkRavtr95s8a1v1TdTlLu4uH0-dcNUUKhtCx3wP9v_JX61qHpT0LsMmGQy6vVdAsyY88SmI/s1600/Selection_177.png" /></p>
<p><small>(Note the blank spaces)</small></p>
<p>After causing enough unique colors to be drawn, the problem goes away.</p>
<p>Some googling around suggests that this <a href="https://bugzilla.redhat.com/show_bug.cgi?id=1323762"> may be related</a> <a href="https://bugzilla.novell.com/show_bug.cgi?id=913425">to the <code>i915</code> driver for Intel graphics cards</a>, at which point it became apparent that this was the kind of problem that will literally never be fixed.</p>
<p>It was suggested either to add the following incantation to <a href="https://xkcd.com/963/"><code>/etc/X11/xorg.conf.d/50-device.conf</code></a>:</p>
<pre>Section "Device"
Identifier "Default Device"
Driver "intel"
Option "AccelMethod" "UXA"
EndSection</pre>
<p>or the following in <code>/etc/environment</code>:</p>
<pre>COGL_ATLAS_DEFAULT_BLIT_MODE=framebuffer</pre>
<p>neither of which, of course, made any difference.</p>
<p>Or, instead of waiting for the impossible to happen I can just run this bit of code:</p>
<pre>for i in $(seq 0 255) ; do
bash -c 'echo -n $'"'"'\033[38;5;'"$i"'mhi\033[0m'" '"
done
echo</pre>
<p><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi2be_5RIgt6w1G8akZY3LA7RWbcwZleQ1NxzsjCcVFEirMjEDmsplPgZdoAXefvTQC1SWg3tOvISNnwaKycHxw9T1rEVTNYRueQAD6G9ckTqtgzcrzH0hnegHFK6h2gfbtTh3CyUFYX1U/s1600/Selection_178.png" /></p>
<p>and then everything is good.</p>Owenhttp://www.blogger.com/profile/09697040246092989242noreply@blogger.com0tag:blogger.com,1999:blog-696719307153090038.post-7283558858541950102016-11-21T10:37:00.004-05:002016-11-21T10:52:02.694-05:00The ∞ arrows of version control<p>At the 0th level is a point:</p>
<p><img border="0" height="240" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhgu2PUU4pvhva2Yznh_18qRZv0Z2aKujL-AMxYpF1rOAMSesE9qdGvpQ2-gQC-Am2cIb3uCVvLhJxyrAExbz84xYxCFLn42bXhcUudyqRiHXNfYFF0Ny47dx0G4T4iU2vP7n8wiktHF_w/s320/points.png" width="320" /></p>
<p>The point is the current state of your source code.</p>
<p>At the 1th level are the arrows:</p>
<p><img border="0" height="240" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgc_k6XiZcUrRHsUWEJZRexMbOsrvNN4rWO9YUiU1j1Qi6mLI9MVqAZKzOzeW8Q55n5Dj6n6NrJI-j50ItTCrrETV0UOvDyqw8V71qvYhkdMPcQ2F3BzAW9IIfR_Due5lTaldO4TejCzQ4/s320/arrows.png" width="320" /></p>
<p>These are your commits, connected by history.</p>
<p>At the 2th level are the arrows between arrows:</p>
<p><img border="0" height="240" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh56c3wtNXegmOkt1vaOkqa0DowogJyWTF5PVQiuAt9iv9Jnxx-ISqwXAo2wlHs6qIH_Y_W_vDjknKY6Ajp-_UYpvhHUak0XeQwYm4yaefa_Fuxvr8j4lgUHbMxb-NubaXTTXNnQannKXg/s320/arrows-2.png" width="320" /></p>
<p>Every time you make a change to your history, such as by creating a new commit, or deleting a commit, you create a new history, linked to the old history with a 2-level arrow.</p>
<p>Most VCSs don't keep track of 2-level arrows, but they could.</p>
<p>At the 3th level are the arrows between 2-level arrows:</p>
<p><img border="0" height="240" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhb5LyE9Hc4VZ3PGj4lXMjH78RiDOhTlHWtjQWTHFBDBnug12Aaa3YRJYYEiMJw9ijXBTdwhyphenhyphen9kWGI-Y4cwQWeo6L3jHN64C7Xg70tdVjHzPjrWx3F1zy-A3TVyjzQVejU4QKix0By1rmo/s320/arrows-3.png" width="320" /></p>
<p>You may not see the need for 3-level arrows, but that's because you never work with 2-level arrows. You like 1-level arrows because you work with points, and 1-level arrows help you keep track of your points. You don't use 2-level arrows, but you can probably see why they are useful. Everyone knows that you should never git amend after a git push. But if git kept track of 2-level arrows, you could do a 2-level push, and sync your local amend with a remote amend. You could do a 2-level revert to undo your amend. And once you start working with 2-level arrows, you need 3-level arrows to keep track of those.</p>
<p>There are ∞ levels of arrows.</p>
<p><img border="0" height="240" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg-7Bb7LjfbEcZ7sTkiE3J2uWVHfUhg_NZcdJabB3S6UzpboNd_yf_62JYaDDXhK_yOm0qQU-kklPMl7Z4UKx0pVM3YvpwtAbC8NznChHNQidiw6GsQrBd9MzfvNuxKpptNKLQJV8wiujs/s320/arrows-4.png" width="320" /></p>
<p>How can the computer store ∞ levels of arrows? Won't they take up ∞ space? Just one commit creates a 1-arrow, a 2-arrow, a 3-arrow, ... and so on.</p>
<p>But most 2-arrows are uniquely determined by a single 1-arrow, and uniquely determine their 3-arrow. Most n-arrows are degenerate, representing only the addition of a single (n-1)-arrow. At any time, only finitely many arrows require their own representation in memory.</p>
<p>Can a human mind keep track of 20 levels of arrows, let alone ∞ levels? That is hard to say, because no one has tried.</p>
Owenhttp://www.blogger.com/profile/09697040246092989242noreply@blogger.com0tag:blogger.com,1999:blog-696719307153090038.post-12332162549876133702016-10-14T15:51:00.001-04:002016-10-14T15:51:54.277-04:00Building OpenCV with Java on Linux<span style="font-family: inherit;">This command worked for me:</span><br />
<blockquote class="tr_bq">
<span style="font-family: Courier New, Courier, monospace;">cmake .. -DJAVA_INCLUDE_PATH=/usr/lib/jvm/java-8-oracle/include/ -DJAVA_INCLUDE_PATH2=/usr/lib/jvm/java-8-oracle/include/linux</span></blockquote>
<span style="font-family: inherit;">It was </span><b style="font-family: inherit;">not</b><span style="font-family: inherit;"> necessary to set </span><span style="background-color: white;"><span style="font-family: Courier New, Courier, monospace;">BUILD_SHARED_LIBS</span></span><span style="background-color: white; font-family: inherit;"> to false</span><span style="font-family: inherit;"> </span><a href="http://docs.opencv.org/3.1.0/d7/d9f/tutorial_linux_install.html" style="font-family: inherit;">as described on opencv.org</a><span style="font-family: inherit;">. That would be rather undesirable to lose the ability to use shared libs just because you also want to use Java!</span><br />
<span style="font-family: inherit;"><br /></span>
<span style="font-family: inherit;"><b>**HOWEVER**,</b> because </span><span style="background-color: white;"><span style="font-family: Courier New, Courier, monospace;">BUILD_SHARED_LIBS</span></span><span style="background-color: white; font-family: inherit;"> is set, </span><span style="font-family: "Courier New", Courier, monospace;">libopencv_java310.so</span><span style="font-family: inherit;"> will have dependencies.</span><span style="background-color: white; font-family: inherit;"> It will be necessary to load </span><span style="font-family: Courier New, Courier, monospace;">libopencv_core.so.3.1</span> among others into the JVM at runtime, AND THEN to have <span style="font-family: Courier New, Courier, monospace;">libopencv_java310.so</span> see those symbols. This is tricky in Java! If you don't want to go through this pain, you can go and unset <span style="font-family: Courier New, Courier, monospace;">BUILD_SHARED_LIBS</span>; I won't judge you.<br />
<br />
Essentially, what you need is a way to set <span style="font-family: Courier New, Courier, monospace;"><a href="http://pubs.opengroup.org/onlinepubs/7908799/xsh/dlopen.html">RTLD_GLOBAL</a></span> when loading the library. This can be accomplished using <a href="https://github.com/java-native-access/jna">JNA</a>:<br />
<blockquote class="tr_bq">
<span style="font-family: Courier New, Courier, monospace;"><a href="https://jna.java.net/javadoc/com/sun/jna/NativeLibrary.html">NativeLibrary</a>.getInstance(path);<br />System.load(path);</span></blockquote>
Then you should be able to use OpenCV.Owenhttp://www.blogger.com/profile/09697040246092989242noreply@blogger.com2tag:blogger.com,1999:blog-696719307153090038.post-44193510256900811452016-06-19T21:19:00.001-04:002016-06-19T21:19:55.765-04:00Example of using WebWorkers in ScalaJS<a href="https://github.com/ellbur/scalajs-webworker-test">https://github.com/ellbur/scalajs-webworker-test</a><br />
<br />
In case you were curious.<br />
<br />
The biggest disadvantage of webworkers is that, at least, Chrome browser does not consider functions to be translatable from one webworker to another.
This in theory should be possible, as a function can be represented as code+environment, and both of these are by themselves translatable.
Owenhttp://www.blogger.com/profile/09697040246092989242noreply@blogger.com0tag:blogger.com,1999:blog-696719307153090038.post-68265671153510440902013-06-26T04:40:00.000-04:002013-06-26T04:40:51.052-04:00I'm sick of tools<style type="text/css">
/*
:Author: David Goodger (goodger@python.org)
:Id: $Id$
:Copyright: This stylesheet has been placed in the public domain.
Default cascading style sheet for the HTML output of Docutils.
See http://docutils.sf.net/docs/howto/html-stylesheets.html for how to
customize this style sheet.
*/
/* used to remove borders from tables and images */
.borderless, table.borderless td, table.borderless th {
border: 0 }
table.borderless td, table.borderless th {
/* Override padding for "table.docutils td" with "! important".
The right padding separates the table cells. */
padding: 0 0.5em 0 0 ! important }
.first {
/* Override more specific margin styles with "! important". */
margin-top: 0 ! important }
.last, .with-subtitle {
margin-bottom: 0 ! important }
.hidden {
display: none }
a.toc-backref {
text-decoration: none ;
color: black }
blockquote.epigraph {
margin: 2em 5em ; }
dl.docutils dd {
margin-bottom: 0.5em }
object[type="image/svg+xml"], object[type="application/x-shockwave-flash"] {
overflow: hidden;
}
/* Uncomment (and remove this text!) to get bold-faced definition list terms
dl.docutils dt {
font-weight: bold }
*/
div.abstract {
margin: 2em 5em }
div.abstract p.topic-title {
font-weight: bold ;
text-align: center }
div.admonition, div.attention, div.caution, div.danger, div.error,
div.hint, div.important, div.note, div.tip, div.warning {
margin: 2em ;
border: medium outset ;
padding: 1em }
div.admonition p.admonition-title, div.hint p.admonition-title,
div.important p.admonition-title, div.note p.admonition-title,
div.tip p.admonition-title {
font-weight: bold ;
font-family: sans-serif }
div.attention p.admonition-title, div.caution p.admonition-title,
div.danger p.admonition-title, div.error p.admonition-title,
div.warning p.admonition-title {
color: red ;
font-weight: bold ;
font-family: sans-serif }
/* Uncomment (and remove this text!) to get reduced vertical space in
compound paragraphs.
div.compound .compound-first, div.compound .compound-middle {
margin-bottom: 0.5em }
div.compound .compound-last, div.compound .compound-middle {
margin-top: 0.5em }
*/
div.dedication {
margin: 2em 5em ;
text-align: center ;
font-style: italic }
div.dedication p.topic-title {
font-weight: bold ;
font-style: normal }
div.figure {
margin-left: 2em ;
margin-right: 2em }
div.footer, div.header {
clear: both;
font-size: smaller }
div.line-block {
display: block ;
margin-top: 1em ;
margin-bottom: 1em }
div.line-block div.line-block {
margin-top: 0 ;
margin-bottom: 0 ;
margin-left: 1.5em }
div.sidebar {
margin: 0 0 0.5em 1em ;
border: medium outset ;
padding: 1em ;
background-color: #ffffee ;
width: 40% ;
float: right ;
clear: right }
div.sidebar p.rubric {
font-family: sans-serif ;
font-size: medium }
div.system-messages {
margin: 5em }
div.system-messages h1 {
color: red }
div.system-message {
border: medium outset ;
padding: 1em }
div.system-message p.system-message-title {
color: red ;
font-weight: bold }
div.topic {
margin: 2em }
h1.section-subtitle, h2.section-subtitle, h3.section-subtitle,
h4.section-subtitle, h5.section-subtitle, h6.section-subtitle {
margin-top: 0.4em }
h1.title {
text-align: center }
h2.subtitle {
text-align: center }
hr.docutils {
width: 75% }
img.align-left, .figure.align-left, object.align-left {
clear: left ;
float: left ;
margin-right: 1em }
img.align-right, .figure.align-right, object.align-right {
clear: right ;
float: right ;
margin-left: 1em }
img.align-center, .figure.align-center, object.align-center {
display: block;
margin-left: auto;
margin-right: auto;
}
.align-left {
text-align: left }
.align-center {
clear: both ;
text-align: center }
.align-right {
text-align: right }
/* reset inner alignment in figures */
div.align-right {
text-align: inherit }
/* div.align-center * { */
/* text-align: left } */
ol.simple, ul.simple {
margin-bottom: 1em }
ol.arabic {
list-style: decimal }
ol.loweralpha {
list-style: lower-alpha }
ol.upperalpha {
list-style: upper-alpha }
ol.lowerroman {
list-style: lower-roman }
ol.upperroman {
list-style: upper-roman }
p.attribution {
text-align: right ;
margin-left: 50% }
p.caption {
font-style: italic }
p.credits {
font-style: italic ;
font-size: smaller }
p.label {
white-space: nowrap }
p.rubric {
font-weight: bold ;
font-size: larger ;
color: maroon ;
text-align: center }
p.sidebar-title {
font-family: sans-serif ;
font-weight: bold ;
font-size: larger }
p.sidebar-subtitle {
font-family: sans-serif ;
font-weight: bold }
p.topic-title {
font-weight: bold }
pre.address {
margin-bottom: 0 ;
margin-top: 0 ;
font: inherit }
pre.literal-block, pre.doctest-block, pre.math {
margin-left: 2em ;
margin-right: 2em }
span.classifier {
font-family: sans-serif ;
font-style: oblique }
span.classifier-delimiter {
font-family: sans-serif ;
font-weight: bold }
span.interpreted {
font-family: sans-serif }
span.option {
white-space: nowrap }
span.pre {
white-space: pre }
span.problematic {
color: red }
span.section-subtitle {
/* font-size relative to parent (h1..h6 element) */
font-size: 80% }
table.citation {
border-left: solid 1px gray;
margin-left: 1px }
table.docinfo {
margin: 2em 4em }
table.docutils {
margin-top: 0.5em ;
margin-bottom: 0.5em }
table.footnote {
border-left: solid 1px black;
margin-left: 1px }
table.docutils td, table.docutils th,
table.docinfo td, table.docinfo th {
padding-left: 0.5em ;
padding-right: 0.5em ;
vertical-align: top }
table.docutils th.field-name, table.docinfo th.docinfo-name {
font-weight: bold ;
text-align: left ;
white-space: nowrap ;
padding-left: 0 }
h1 tt.docutils, h2 tt.docutils, h3 tt.docutils,
h4 tt.docutils, h5 tt.docutils, h6 tt.docutils {
font-size: 100% }
ul.auto-toc {
list-style-type: none }
</style>
<style type="text/css">
.file-header {
color: #999;
font-weight: bold;
}
.run-output {
white-space: pre;
font-family: monospace;
background-color: #fff;
border: 1px solid #eee;
margin: 10px 0px 0px 0px;
padding: 5px 10px 5px 10px;
}
.code {
white-space: pre;
font-family: monospace;
background-color: #dec;
border: none;
border-radius: 10px;
padding: 10px 10px 5px 3px;
margin: 5px 0px 0px 0px;
margin-left: 0px;
margin-right: 0px;
}
pre.literal-block {
margin: 5px 0px 0px 0px;
}
.code p {
padding: 0px 0px 0px 0px;
margin: 0px 0px 0px 0px;
overflow: visible;
}
.run-output p {
padding: 0px 0px 0px 0px;
margin: 0px 0px 0px 0px;
overflow: visible;
}
.interactive-input {
white-space: pre;
font-family: monospace;
}
.interactive-output {
white-space: pre;
font-family: monospace;
}
.interactive-session {
background-color: #fff;
border: 1px solid #eee;
margin: 10px 0px 0px 0px;
padding: 0px 0px 0px 5px;
overflow: visible;
}
.c { color: #408080; font-style: italic } /* Comment */
.err { border: 1px solid #FF0000 } /* Error */
.k { color: #008000; font-weight: bold } /* Keyword */
.o { color: #4444ee } /* Operator */
.cm { color: #408080; font-style: italic } /* Comment.Multiline */
.cp { color: #BC7A00 } /* Comment.Preproc */
.c1 { color: #408080; font-style: italic } /* Comment.Single */
.cs { color: #408080; font-style: italic } /* Comment.Special */
.gd { color: #A00000 } /* Generic.Deleted */
.ge { font-style: italic } /* Generic.Emph */
.gr { color: #FF0000 } /* Generic.Error */
.gh { color: #000080; font-weight: bold } /* Generic.Heading */
.gi { color: #00A000 } /* Generic.Inserted */
.go { color: #808080 } /* Generic.Output */
.gp { color: #000080; font-weight: bold } /* Generic.Prompt */
.gs { font-weight: bold } /* Generic.Strong */
.gu { color: #800080; font-weight: bold } /* Generic.Subheading */
.gt { color: #0040D0 } /* Generic.Traceback */
.kc { color: #008000; font-weight: bold } /* Keyword.Constant */
.kd { color: #008000; font-weight: bold } /* Keyword.Declaration */
.kn { color: #008000; font-weight: bold } /* Keyword.Namespace */
.kp { color: #008000 } /* Keyword.Pseudo */
.kr { color: #008000; font-weight: bold } /* Keyword.Reserved */
.kt { color: #B00040 } /* Keyword.Type */
.m { color: #666666 } /* Literal.Number */
.s { color: #BA2121 } /* Literal.String */
.na { color: #7D9029 } /* Name.Attribute */
.nb { color: #008000 } /* Name.Builtin */
.nc { color: #0000FF; font-weight: bold } /* Name.Class */
.no { color: #880000 } /* Name.Constant */
.nd { color: #AA22FF } /* Name.Decorator */
.ni { color: #999999; font-weight: bold } /* Name.Entity */
.ne { color: #D2413A; font-weight: bold } /* Name.Exception */
.nf { color: #0000FF } /* Name.Function */
.nl { color: #A0A000 } /* Name.Label */
.nn { color: #0000FF; font-weight: bold } /* Name.Namespace */
.nt { color: #008000; font-weight: bold } /* Name.Tag */
.nv { color: #19177C } /* Name.Variable */
.ow { color: #AA22FF; font-weight: bold } /* Operator.Word */
.p { color: #11aa11 } /* Parenthesis */
.w { color: #bbbbbb } /* Text.Whitespace */
.mf { color: #666666 } /* Literal.Number.Float */
.mh { color: #666666 } /* Literal.Number.Hex */
.mi { color: #666666 } /* Literal.Number.Integer */
.mo { color: #666666 } /* Literal.Number.Oct */
.sb { color: #BA2121 } /* Literal.String.Backtick */
.sc { color: #BA2121 } /* Literal.String.Char */
.sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */
.s2 { color: #BA2121 } /* Literal.String.Double */
.se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */
.sh { color: #BA2121 } /* Literal.String.Heredoc */
.si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */
.sx { color: #008000 } /* Literal.String.Other */
.sr { color: #BB6688 } /* Literal.String.Regex */
.s1 { color: #BA2121 } /* Literal.String.Single */
.ss { color: #19177C } /* Literal.String.Symbol */
.bp { color: #008000 } /* Name.Builtin.Pseudo */
.vc { color: #19177C } /* Name.Variable.Class */
.vg { color: #19177C } /* Name.Variable.Global */
.vi { color: #19177C } /* Name.Variable.Instance */
.il { color: #666666 } /* Literal.Number.Integer.Long */
.lineno { color: #bbb }
.run-output-weaver {
white-space: normal;
font-family: default;
background-color: ;
border: 3px solid #eee;
margin: 10px 0px 0px 0px;
padding: 5px 10px 5px 10px;
}
.code-weaver {
border: 3px solid #efe;
}
</style><!-- I'm sick of tools -->
<p>Synonym's for "tool" include "framework" and "system". So for example "build tool", "build system", "web framework", "message-passing system", "text processing system", "dependency injection framework" etc.</p>
<p>The problem with a tool is that it takes control away from the client code. <a class="reference external" href="http://www.gnu.org/software/make/">make</a> ("Make is a tool", begins the intro) will plan your build from start to finish <a class="footnote-reference" href="#id2" id="id1">[1]</a>; <a class="reference external" href="http://sphinx-doc.org/">sphinx</a> (also a self-described tool) starts in control and relinquishes it through plugins; <a class="reference external" href="http://maven.apache.org/">maven</a> takes usurping control to a whole new level.</p>
<p>I am not bashing the merits of these programs; Sphinx produces beautiful output and there simply isn't a substitute for Maven right now. I am rather noting that to the extent that these programs are infuriating (<a class="reference external" href="http://stackoverflow.com/a/861618/371739">"Maven is a device for reducing grown men to sobbing masses of absolute terror"</a>) it is because they assume too much control over the process flow.</p>
<p>But what mystifies me in retrospect is that I did not always feel this way. I used to feel insecure over my dislike of tools. In the same way that a novice C++ programmer when quickly shot down for their ignorance of sequence points is unlikely to question the philosophical rationale of even having sequence points, I assumed that the reason for my dislike of tools was due to my lack of mastery with tools, my lack of strength in the face of tools, and my lack of knowledge for the design considerations behind tools.</p>
<p>And yet somehow, when I did master a tool, enough to build <a class="reference external" href="https://github.com/ellbur/rstweaver">my own tool around the tool</a>, I still didn't like the tool.</p>
<p>I didn't quite understand why; I thought I had simply bumped against architectural mistakes in docutils; I didn't realize that the problem was that it was a tool, and that by wrapping it in my own tool I was in fact making the situation worse.</p>
<p>The moral became apparent while I was drafting a Makefile to build some code that used to be managed by <a class="reference external" href="http://www.ti.com/tool/ccstudio">TI Code Composer Studio</a> (note the URL) and compiled with <a class="reference external" href="http://processors.wiki.ti.com/index.php/Code_Generation_Tools_FAQ">TI Code Generation Tools</a>. The compiler <tt class="docutils literal">cl6x</tt> for Code Generation Tools has perhaps the most mischievous command line interface I have ever encountered. Its rules for the naming of output files (which sometimes permit explicit overriding and sometimes not), which files must be built in a common invocation, and what must be the working directory are like carefully placed traps, and <tt class="docutils literal">make</tt> has a habit of stepping everywhere.</p>
<p>And then, I decided, I don't have to write a Makefile. Nor must I use make or Scons or CMake or redo or any build tool at all. I can write a Python script that invokes the appropriate commands, and that's it.</p>
<p>And I won't sacrifice incremental build, because I can add memoization, and I won't sacrifice selectable targets because I can use argparse for command line arguments, and I won't sacrifice wildcards and path substitutions because I can write a few Python functions for manipulating paths and that's all I need (<a class="reference external" href="http://docs.python.org/2/library/os.path.html">os.path</a> does most of the work).</p>
<p>A skilled Makefile writer will point out that the job would have been easy in <tt class="docutils literal">make</tt> if you knew what you were doing. That's probably true. But the lesson to be learned is that we no longer need to feel bad that we didn't know what we were doing with <tt class="docutils literal">make</tt>, we can get the job done in pure Python and nobody need ever know what they are doing, beyond what they are actually in reality <em>doing</em>.</p>
<p>Building on this philosophy I wrote <a class="reference external" href="https://github.com/ellbur/scooter">scooter</a>, which I think in retrospect contains some mistakes that bring it a little too close to being a tool (such as using exclusively <a class="reference external" href="http://pyinotify.sourceforge.net/">inotify</a> for dependency tracking), but it is at least a step in the right direction. The project <a class="reference external" href="https://github.com/ellbur/quickfiles">quickfiles</a> that came out of it is better.</p>
<p>As a tool-less conclusion I present you the <a class="reference external" href="https://github.com/ellbur/docmessy">simplest possible HTML document generator</a> for Python:</p>
<pre class="code code-file literal-block literal-block literal-block literal-block literal-block literal-block literal-block literal-block literal-block literal-block literal-block literal-block">
<span></span><span class="lineno"> 1 </span><span></span><span class="k">def</span><span> </span><span class="nf">surround_with</span><span class="p">(</span><span class="n">start</span><span class="p">,</span><span> </span><span class="n">end</span><span class="p">)</span><span class="p">:</span><span></span><span>
</span><span class="lineno"> 2 </span><span></span><span> </span><span class="k">def</span><span> </span><span class="nf">dec</span><span class="p">(</span><span class="n">f</span><span class="p">)</span><span class="p">:</span><span></span><span>
</span><span class="lineno"> 3 </span><span></span><span> </span><span class="k">print</span><span class="p">(</span><span class="n">start</span><span class="p">)</span><span></span><span>
</span><span class="lineno"> 4 </span><span></span><span> </span><span class="n">f</span><span class="p">(</span><span class="p">)</span><span></span><span>
</span><span class="lineno"> 5 </span><span></span><span> </span><span class="k">print</span><span class="p">(</span><span class="n">end</span><span class="p">)</span><span></span><span>
</span><span class="lineno"> 6 </span><span></span><span> </span><span class="k">return</span><span> </span><span class="n">dec</span><span></span><span>
</span><span></span>
</pre>
<p>Because that really is all you need, and does 50% of the work that docutils or Sphinx or LaTeX do, without requiring any new knowledge (everyone has to learn HTML at some point in their lives). Add in this function:</p>
<pre class="code code-file literal-block literal-block literal-block literal-block literal-block literal-block literal-block literal-block literal-block literal-block literal-block literal-block">
<span></span><span class="lineno"> 7 </span><span></span><span class="k">def</span><span> </span><span class="nf">pyplot_image</span><span class="p">(</span><span class="o">*</span><span class="o">*</span><span class="n">fig_attrs</span><span class="p">)</span><span class="p">:</span><span></span><span>
</span><span class="lineno"> 8 </span><span></span><span> </span><span class="kn">from</span><span> </span><span class="nn">matplotlib.pyplot</span><span> </span><span class="kn">import</span><span> </span><span class="n">figure</span><span></span><span>
</span><span class="lineno"> 9 </span><span></span><span> </span><span class="k">def</span><span> </span><span class="nf">dec</span><span class="p">(</span><span class="n">f</span><span class="p">)</span><span class="p">:</span><span></span><span>
</span><span class="lineno"> 10 </span><span></span><span> </span><span class="n">fig</span><span> </span><span class="o">=</span><span> </span><span class="n">figure</span><span class="p">(</span><span class="o">*</span><span class="o">*</span><span class="n">fig_attrs</span><span class="p">)</span><span></span><span>
</span><span class="lineno"> 11 </span><span></span><span> </span><span class="n">f</span><span class="p">(</span><span class="p">)</span><span></span><span>
</span><span class="lineno"> 12 </span><span></span><span> </span><span class="n">tmp</span><span> </span><span class="o">=</span><span> </span><span class="n">Path</span><span class="o">.</span><span class="n">mktemp</span><span class="p">(</span><span class="p">)</span><span class="o">.</span><span class="n">setext</span><span class="p">(</span><span class="s">'</span><span class="s">.png</span><span class="s">'</span><span class="p">)</span><span></span><span>
</span><span class="lineno"> 13 </span><span></span><span> </span><span class="n">fig</span><span class="o">.</span><span class="n">savefig</span><span class="p">(</span><span class="nb">str</span><span class="p">(</span><span class="n">tmp</span><span class="p">)</span><span class="p">)</span><span></span><span>
</span><span class="lineno"> 14 </span><span></span><span> </span><span class="n">data</span><span> </span><span class="o">=</span><span> </span><span class="n">b64encode</span><span class="p">(</span><span class="nb">open</span><span class="p">(</span><span class="nb">str</span><span class="p">(</span><span class="n">tmp</span><span class="p">)</span><span class="p">)</span><span class="o">.</span><span class="n">read</span><span class="p">(</span><span class="p">)</span><span class="p">)</span><span></span><span>
</span><span class="lineno"> 15 </span><span></span><span> </span><span class="k">print</span><span class="p">(</span><span class="s">'</span><span class="s"><img src=</span><span class="s">"</span><span class="s">data:image/png;base64,</span><span class="si">%s</span><span class="s">"</span><span class="s">/></span><span class="s">'</span><span> </span><span class="o">%</span><span> </span><span class="p">(</span><span class="n">data</span><span class="p">,</span><span class="p">)</span><span class="p">)</span><span></span><span>
</span><span class="lineno"> 16 </span><span></span><span> </span><span class="k">return</span><span> </span><span class="n">dec</span><span></span><span>
</span><span></span>
</pre>
<p>And you have everything you need to <a class="reference external" href="https://github.com/ellbur/docmessy">autogenerate</a> <a class="reference external" href="http://rawgithub.com/ellbur/docmessy/master/examples/plotting2.html">reports of analyses including plots</a>, as a standalone HTML document with no external dependencies, that you can email to someone, that will display in any browser.</p>
<table class="docutils footnote" frame="void" id="id2" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
<tr><td class="label"><a class="fn-backref" href="#id1">[1]</a></td><td>Otherwise <tt class="docutils literal">make <span class="pre">-n</span></tt> would be much harder.</td></tr>
</tbody>
</table>
Owenhttp://www.blogger.com/profile/09697040246092989242noreply@blogger.com2tag:blogger.com,1999:blog-696719307153090038.post-10787304123356139192013-06-25T04:31:00.001-04:002013-06-25T04:31:55.396-04:00Math?<br />
<a href="http://www.youtube.com/watch?v=xyowJZxrtbg">TEDxManhattanBeach - John Bennett - Why Math Instruction Is Unnecessary</a><br /><div style="-webkit-composition-fill-color: rgba(130, 98, 83, 0.0976563); -webkit-composition-frame-color: rgba(191, 107, 82, 0.496094); -webkit-tap-highlight-color: rgba(26, 26, 26, 0.296875); -webkit-text-size-adjust: auto; font-family: '.Helvetica NeueUI'; font-size: 18px; line-height: 24px;">
<br /></div>
<div style="-webkit-composition-fill-color: rgba(130, 98, 83, 0.0976563); -webkit-composition-frame-color: rgba(191, 107, 82, 0.496094); -webkit-tap-highlight-color: rgba(26, 26, 26, 0.296875); -webkit-text-size-adjust: auto; font-family: '.Helvetica NeueUI'; font-size: 18px; line-height: 24px;">
I don't do math on a typical day. I am an electrical engineer; I work on X-ray spectroscopy systems.</div>
<div style="-webkit-composition-fill-color: rgba(130, 98, 83, 0.0976563); -webkit-composition-frame-color: rgba(191, 107, 82, 0.496094); -webkit-tap-highlight-color: rgba(26, 26, 26, 0.296875); -webkit-text-size-adjust: auto; font-family: '.Helvetica NeueUI'; font-size: 18px; line-height: 24px;">
<br /></div>
<div style="-webkit-composition-fill-color: rgba(130, 98, 83, 0.0976563); -webkit-composition-frame-color: rgba(191, 107, 82, 0.496094); -webkit-tap-highlight-color: rgba(26, 26, 26, 0.296875); -webkit-text-size-adjust: auto; font-family: '.Helvetica NeueUI'; font-size: 18px; line-height: 24px;">
It is true that I do math sometimes, but maybe one day in twenty. It is sometimes quite sophisticated math (probability or signal processing), but it takes no more than half an hour.</div>
<div style="-webkit-composition-fill-color: rgba(130, 98, 83, 0.0976563); -webkit-composition-frame-color: rgba(191, 107, 82, 0.496094); -webkit-tap-highlight-color: rgba(26, 26, 26, 0.296875); -webkit-text-size-adjust: auto; font-family: '.Helvetica NeueUI'; font-size: 18px; line-height: 24px;">
<br /></div>
<div style="-webkit-composition-fill-color: rgba(130, 98, 83, 0.0976563); -webkit-composition-frame-color: rgba(191, 107, 82, 0.496094); -webkit-tap-highlight-color: rgba(26, 26, 26, 0.296875); -webkit-text-size-adjust: auto; font-family: '.Helvetica NeueUI'; font-size: 18px; line-height: 24px;">
I have studied a lot of math. I have studied groups, rings, fields, field extensions, vector spaces, modules, categories, monads, adjunctions, topologies, sets, logic, algorithms, derivatives, integrals, differential forms, complex numbers, matrices, differential equations, and Laplace transforms. But I don't think about those things much anymore. I mostly do a lot of coding.</div>
<div style="-webkit-composition-fill-color: rgba(130, 98, 83, 0.0976563); -webkit-composition-frame-color: rgba(191, 107, 82, 0.496094); -webkit-tap-highlight-color: rgba(26, 26, 26, 0.296875); -webkit-text-size-adjust: auto; font-family: '.Helvetica NeueUI'; font-size: 18px; line-height: 24px;">
<br /></div>
<div style="-webkit-composition-fill-color: rgba(130, 98, 83, 0.0976563); -webkit-composition-frame-color: rgba(191, 107, 82, 0.496094); -webkit-tap-highlight-color: rgba(26, 26, 26, 0.296875); -webkit-text-size-adjust: auto; font-family: '.Helvetica NeueUI'; font-size: 18px; line-height: 24px;">
Though I suppose my job would be harder without math. The 80/20 rule still applies; I do little math because I can get it done quickly and move on to something else. If I couldn't do math it might consume my whole day.</div>
<div style="-webkit-composition-fill-color: rgba(130, 98, 83, 0.0976563); -webkit-composition-frame-color: rgba(191, 107, 82, 0.496094); -webkit-tap-highlight-color: rgba(26, 26, 26, 0.296875); -webkit-text-size-adjust: auto; font-family: '.Helvetica NeueUI'; font-size: 18px; line-height: 24px;">
<br /></div>
<div style="-webkit-composition-fill-color: rgba(130, 98, 83, 0.0976563); -webkit-composition-frame-color: rgba(191, 107, 82, 0.496094); -webkit-tap-highlight-color: rgba(26, 26, 26, 0.296875); -webkit-text-size-adjust: auto; font-family: '.Helvetica NeueUI'; font-size: 18px; line-height: 24px;">
Though I still don't see myself factoring a polynomial.</div>
Owenhttp://www.blogger.com/profile/09697040246092989242noreply@blogger.com0tag:blogger.com,1999:blog-696719307153090038.post-24696287326397834832013-06-25T01:58:00.000-04:002013-06-25T01:58:50.949-04:00I never use logging frameworks<style type="text/css">
/*
:Author: David Goodger (goodger@python.org)
:Id: $Id$
:Copyright: This stylesheet has been placed in the public domain.
Default cascading style sheet for the HTML output of Docutils.
See http://docutils.sf.net/docs/howto/html-stylesheets.html for how to
customize this style sheet.
*/
/* used to remove borders from tables and images */
.borderless, table.borderless td, table.borderless th {
border: 0 }
table.borderless td, table.borderless th {
/* Override padding for "table.docutils td" with "! important".
The right padding separates the table cells. */
padding: 0 0.5em 0 0 ! important }
.first {
/* Override more specific margin styles with "! important". */
margin-top: 0 ! important }
.last, .with-subtitle {
margin-bottom: 0 ! important }
.hidden {
display: none }
a.toc-backref {
text-decoration: none ;
color: black }
blockquote.epigraph {
margin: 2em 5em ; }
dl.docutils dd {
margin-bottom: 0.5em }
object[type="image/svg+xml"], object[type="application/x-shockwave-flash"] {
overflow: hidden;
}
/* Uncomment (and remove this text!) to get bold-faced definition list terms
dl.docutils dt {
font-weight: bold }
*/
div.abstract {
margin: 2em 5em }
div.abstract p.topic-title {
font-weight: bold ;
text-align: center }
div.admonition, div.attention, div.caution, div.danger, div.error,
div.hint, div.important, div.note, div.tip, div.warning {
margin: 2em ;
border: medium outset ;
padding: 1em }
div.admonition p.admonition-title, div.hint p.admonition-title,
div.important p.admonition-title, div.note p.admonition-title,
div.tip p.admonition-title {
font-weight: bold ;
font-family: sans-serif }
div.attention p.admonition-title, div.caution p.admonition-title,
div.danger p.admonition-title, div.error p.admonition-title,
div.warning p.admonition-title {
color: red ;
font-weight: bold ;
font-family: sans-serif }
/* Uncomment (and remove this text!) to get reduced vertical space in
compound paragraphs.
div.compound .compound-first, div.compound .compound-middle {
margin-bottom: 0.5em }
div.compound .compound-last, div.compound .compound-middle {
margin-top: 0.5em }
*/
div.dedication {
margin: 2em 5em ;
text-align: center ;
font-style: italic }
div.dedication p.topic-title {
font-weight: bold ;
font-style: normal }
div.figure {
margin-left: 2em ;
margin-right: 2em }
div.footer, div.header {
clear: both;
font-size: smaller }
div.line-block {
display: block ;
margin-top: 1em ;
margin-bottom: 1em }
div.line-block div.line-block {
margin-top: 0 ;
margin-bottom: 0 ;
margin-left: 1.5em }
div.sidebar {
margin: 0 0 0.5em 1em ;
border: medium outset ;
padding: 1em ;
background-color: #ffffee ;
width: 40% ;
float: right ;
clear: right }
div.sidebar p.rubric {
font-family: sans-serif ;
font-size: medium }
div.system-messages {
margin: 5em }
div.system-messages h1 {
color: red }
div.system-message {
border: medium outset ;
padding: 1em }
div.system-message p.system-message-title {
color: red ;
font-weight: bold }
div.topic {
margin: 2em }
h1.section-subtitle, h2.section-subtitle, h3.section-subtitle,
h4.section-subtitle, h5.section-subtitle, h6.section-subtitle {
margin-top: 0.4em }
h1.title {
text-align: center }
h2.subtitle {
text-align: center }
hr.docutils {
width: 75% }
img.align-left, .figure.align-left, object.align-left {
clear: left ;
float: left ;
margin-right: 1em }
img.align-right, .figure.align-right, object.align-right {
clear: right ;
float: right ;
margin-left: 1em }
img.align-center, .figure.align-center, object.align-center {
display: block;
margin-left: auto;
margin-right: auto;
}
.align-left {
text-align: left }
.align-center {
clear: both ;
text-align: center }
.align-right {
text-align: right }
/* reset inner alignment in figures */
div.align-right {
text-align: inherit }
/* div.align-center * { */
/* text-align: left } */
ol.simple, ul.simple {
margin-bottom: 1em }
ol.arabic {
list-style: decimal }
ol.loweralpha {
list-style: lower-alpha }
ol.upperalpha {
list-style: upper-alpha }
ol.lowerroman {
list-style: lower-roman }
ol.upperroman {
list-style: upper-roman }
p.attribution {
text-align: right ;
margin-left: 50% }
p.caption {
font-style: italic }
p.credits {
font-style: italic ;
font-size: smaller }
p.label {
white-space: nowrap }
p.rubric {
font-weight: bold ;
font-size: larger ;
color: maroon ;
text-align: center }
p.sidebar-title {
font-family: sans-serif ;
font-weight: bold ;
font-size: larger }
p.sidebar-subtitle {
font-family: sans-serif ;
font-weight: bold }
p.topic-title {
font-weight: bold }
pre.address {
margin-bottom: 0 ;
margin-top: 0 ;
font: inherit }
pre.literal-block, pre.doctest-block, pre.math {
margin-left: 2em ;
margin-right: 2em }
span.classifier {
font-family: sans-serif ;
font-style: oblique }
span.classifier-delimiter {
font-family: sans-serif ;
font-weight: bold }
span.interpreted {
font-family: sans-serif }
span.option {
white-space: nowrap }
span.pre {
white-space: pre }
span.problematic {
color: red }
span.section-subtitle {
/* font-size relative to parent (h1..h6 element) */
font-size: 80% }
table.citation {
border-left: solid 1px gray;
margin-left: 1px }
table.docinfo {
margin: 2em 4em }
table.docutils {
margin-top: 0.5em ;
margin-bottom: 0.5em }
table.footnote {
border-left: solid 1px black;
margin-left: 1px }
table.docutils td, table.docutils th,
table.docinfo td, table.docinfo th {
padding-left: 0.5em ;
padding-right: 0.5em ;
vertical-align: top }
table.docutils th.field-name, table.docinfo th.docinfo-name {
font-weight: bold ;
text-align: left ;
white-space: nowrap ;
padding-left: 0 }
h1 tt.docutils, h2 tt.docutils, h3 tt.docutils,
h4 tt.docutils, h5 tt.docutils, h6 tt.docutils {
font-size: 100% }
ul.auto-toc {
list-style-type: none }
</style>
<style type="text/css">
.file-header {
color: #999;
font-weight: bold;
}
.run-output {
white-space: pre;
font-family: monospace;
background-color: #fff;
border: 1px solid #eee;
margin: 10px 0px 0px 0px;
padding: 5px 10px 5px 10px;
}
.code {
white-space: pre;
font-family: monospace;
background-color: #dec;
border: none;
border-radius: 10px;
padding: 10px 10px 5px 3px;
margin: 5px 0px 0px 0px;
margin-left: 0px;
margin-right: 0px;
}
pre.literal-block {
margin: 5px 0px 0px 0px;
}
.code p {
padding: 0px 0px 0px 0px;
margin: 0px 0px 0px 0px;
overflow: visible;
}
.run-output p {
padding: 0px 0px 0px 0px;
margin: 0px 0px 0px 0px;
overflow: visible;
}
.interactive-input {
white-space: pre;
font-family: monospace;
}
.interactive-output {
white-space: pre;
font-family: monospace;
}
.interactive-session {
background-color: #fff;
border: 1px solid #eee;
margin: 10px 0px 0px 0px;
padding: 0px 0px 0px 5px;
overflow: visible;
}
.c { color: #408080; font-style: italic } /* Comment */
.err { border: 1px solid #FF0000 } /* Error */
.k { color: #008000; font-weight: bold } /* Keyword */
.o { color: #4444ee } /* Operator */
.cm { color: #408080; font-style: italic } /* Comment.Multiline */
.cp { color: #BC7A00 } /* Comment.Preproc */
.c1 { color: #408080; font-style: italic } /* Comment.Single */
.cs { color: #408080; font-style: italic } /* Comment.Special */
.gd { color: #A00000 } /* Generic.Deleted */
.ge { font-style: italic } /* Generic.Emph */
.gr { color: #FF0000 } /* Generic.Error */
.gh { color: #000080; font-weight: bold } /* Generic.Heading */
.gi { color: #00A000 } /* Generic.Inserted */
.go { color: #808080 } /* Generic.Output */
.gp { color: #000080; font-weight: bold } /* Generic.Prompt */
.gs { font-weight: bold } /* Generic.Strong */
.gu { color: #800080; font-weight: bold } /* Generic.Subheading */
.gt { color: #0040D0 } /* Generic.Traceback */
.kc { color: #008000; font-weight: bold } /* Keyword.Constant */
.kd { color: #008000; font-weight: bold } /* Keyword.Declaration */
.kn { color: #008000; font-weight: bold } /* Keyword.Namespace */
.kp { color: #008000 } /* Keyword.Pseudo */
.kr { color: #008000; font-weight: bold } /* Keyword.Reserved */
.kt { color: #B00040 } /* Keyword.Type */
.m { color: #666666 } /* Literal.Number */
.s { color: #BA2121 } /* Literal.String */
.na { color: #7D9029 } /* Name.Attribute */
.nb { color: #008000 } /* Name.Builtin */
.nc { color: #0000FF; font-weight: bold } /* Name.Class */
.no { color: #880000 } /* Name.Constant */
.nd { color: #AA22FF } /* Name.Decorator */
.ni { color: #999999; font-weight: bold } /* Name.Entity */
.ne { color: #D2413A; font-weight: bold } /* Name.Exception */
.nf { color: #0000FF } /* Name.Function */
.nl { color: #A0A000 } /* Name.Label */
.nn { color: #0000FF; font-weight: bold } /* Name.Namespace */
.nt { color: #008000; font-weight: bold } /* Name.Tag */
.nv { color: #19177C } /* Name.Variable */
.ow { color: #AA22FF; font-weight: bold } /* Operator.Word */
.p { color: #11aa11 } /* Parenthesis */
.w { color: #bbbbbb } /* Text.Whitespace */
.mf { color: #666666 } /* Literal.Number.Float */
.mh { color: #666666 } /* Literal.Number.Hex */
.mi { color: #666666 } /* Literal.Number.Integer */
.mo { color: #666666 } /* Literal.Number.Oct */
.sb { color: #BA2121 } /* Literal.String.Backtick */
.sc { color: #BA2121 } /* Literal.String.Char */
.sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */
.s2 { color: #BA2121 } /* Literal.String.Double */
.se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */
.sh { color: #BA2121 } /* Literal.String.Heredoc */
.si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */
.sx { color: #008000 } /* Literal.String.Other */
.sr { color: #BB6688 } /* Literal.String.Regex */
.s1 { color: #BA2121 } /* Literal.String.Single */
.ss { color: #19177C } /* Literal.String.Symbol */
.bp { color: #008000 } /* Name.Builtin.Pseudo */
.vc { color: #19177C } /* Name.Variable.Class */
.vg { color: #19177C } /* Name.Variable.Global */
.vi { color: #19177C } /* Name.Variable.Instance */
.il { color: #666666 } /* Literal.Number.Integer.Long */
.lineno { color: #bbb }
.run-output-weaver {
white-space: normal;
font-family: default;
background-color: ;
border: 3px solid #eee;
margin: 10px 0px 0px 0px;
padding: 5px 10px 5px 10px;
}
.code-weaver {
border: 3px solid #efe;
}
</style><!-- Why I don't use logging frameworks. -->
<p>Logging frameworks are not respectful of the 80/20 rule. A logging framework will make 80% of your logging needs easier, but they make the extra 20% harder.</p>
<p>That extra 20% consists of cases where you are in doubt as to whether logging messages can get through at all, such as starting a new project, moving to a new platform, <a class="reference external" href="http://stackoverflow.com/questions/1140358/how-to-initialize-log4j-properly">misconfiguring the logging framework</a>, long-forgotten bits of code overriding the configuration, <a class="reference external" href="https://www.assembla.com/wiki/show/liftweb/Logging">layered logging frameworks</a> that <a class="reference external" href="https://github.com/robey/configgy">delegate to each other</a>, <a class="reference external" href="https://java.net/bugzilla/show_bug.cgi?id=3387">missing write permissions on a log file</a>, <a class="reference external" href="http://stackoverflow.com/search?q=log4j">etc</a>.</p>
<p>It is a special case of the 80/20 rule that the hardest part of any task is verifying whether an event <em>ever happens at all</em>. Are all my unit tests passing, or are they simply not being run? Did this assertion pass or are assertions disabled? Did the program succeed or was it never invoked? Is it still working or is it waiting for input, or did it hang? Is this logging statement never reached or is logging disabled, or the output redirected, or logging for this particular class disabled, or a filter applied to the log messages, or a dependency missing causing a <a class="reference external" href="http://www.slf4j.org/manual.html">default to no logging</a>, or a buffer not yet flushed? Does the new version still work, or am I running an old version? Did he not send the email or did my spam filter reject it, or the SMTP server bounce it for being too large? Did she not call because everything was ok or because she was already passed out? Is he cool with me and Ryan last night or is he too pissed for words?</p>
<p>I never use logging frameworks. I debug by <tt class="docutils literal">printf</tt>, and then delete the <tt class="docutils literal">printf</tt>. What if I forget to delete it? That's what github is for. All of my projects are either <a class="reference external" href="http://strugglingthroughproblems.blogspot.com/2011/08/welcome-to-my-github-world.html">small and open source</a>, or GUI applications used by non-programmers where spamming stdout is a non-issue.</p>
Owenhttp://www.blogger.com/profile/09697040246092989242noreply@blogger.com0tag:blogger.com,1999:blog-696719307153090038.post-12274996729734064152013-06-03T00:15:00.000-04:002013-06-03T00:15:35.734-04:00Proving type equality in a Scala pattern match<style type="text/css">
/*
:Author: David Goodger (goodger@python.org)
:Id: $Id$
:Copyright: This stylesheet has been placed in the public domain.
Default cascading style sheet for the HTML output of Docutils.
See http://docutils.sf.net/docs/howto/html-stylesheets.html for how to
customize this style sheet.
*/
/* used to remove borders from tables and images */
.borderless, table.borderless td, table.borderless th {
border: 0 }
table.borderless td, table.borderless th {
/* Override padding for "table.docutils td" with "! important".
The right padding separates the table cells. */
padding: 0 0.5em 0 0 ! important }
.first {
/* Override more specific margin styles with "! important". */
margin-top: 0 ! important }
.last, .with-subtitle {
margin-bottom: 0 ! important }
.hidden {
display: none }
a.toc-backref {
text-decoration: none ;
color: black }
blockquote.epigraph {
margin: 2em 5em ; }
dl.docutils dd {
margin-bottom: 0.5em }
object[type="image/svg+xml"], object[type="application/x-shockwave-flash"] {
overflow: hidden;
}
/* Uncomment (and remove this text!) to get bold-faced definition list terms
dl.docutils dt {
font-weight: bold }
*/
div.abstract {
margin: 2em 5em }
div.abstract p.topic-title {
font-weight: bold ;
text-align: center }
div.admonition, div.attention, div.caution, div.danger, div.error,
div.hint, div.important, div.note, div.tip, div.warning {
margin: 2em ;
border: medium outset ;
padding: 1em }
div.admonition p.admonition-title, div.hint p.admonition-title,
div.important p.admonition-title, div.note p.admonition-title,
div.tip p.admonition-title {
font-weight: bold ;
font-family: sans-serif }
div.attention p.admonition-title, div.caution p.admonition-title,
div.danger p.admonition-title, div.error p.admonition-title,
div.warning p.admonition-title {
color: red ;
font-weight: bold ;
font-family: sans-serif }
/* Uncomment (and remove this text!) to get reduced vertical space in
compound paragraphs.
div.compound .compound-first, div.compound .compound-middle {
margin-bottom: 0.5em }
div.compound .compound-last, div.compound .compound-middle {
margin-top: 0.5em }
*/
div.dedication {
margin: 2em 5em ;
text-align: center ;
font-style: italic }
div.dedication p.topic-title {
font-weight: bold ;
font-style: normal }
div.figure {
margin-left: 2em ;
margin-right: 2em }
div.footer, div.header {
clear: both;
font-size: smaller }
div.line-block {
display: block ;
margin-top: 1em ;
margin-bottom: 1em }
div.line-block div.line-block {
margin-top: 0 ;
margin-bottom: 0 ;
margin-left: 1.5em }
div.sidebar {
margin: 0 0 0.5em 1em ;
border: medium outset ;
padding: 1em ;
background-color: #ffffee ;
width: 40% ;
float: right ;
clear: right }
div.sidebar p.rubric {
font-family: sans-serif ;
font-size: medium }
div.system-messages {
margin: 5em }
div.system-messages h1 {
color: red }
div.system-message {
border: medium outset ;
padding: 1em }
div.system-message p.system-message-title {
color: red ;
font-weight: bold }
div.topic {
margin: 2em }
h1.section-subtitle, h2.section-subtitle, h3.section-subtitle,
h4.section-subtitle, h5.section-subtitle, h6.section-subtitle {
margin-top: 0.4em }
h1.title {
text-align: center }
h2.subtitle {
text-align: center }
hr.docutils {
width: 75% }
img.align-left, .figure.align-left, object.align-left {
clear: left ;
float: left ;
margin-right: 1em }
img.align-right, .figure.align-right, object.align-right {
clear: right ;
float: right ;
margin-left: 1em }
img.align-center, .figure.align-center, object.align-center {
display: block;
margin-left: auto;
margin-right: auto;
}
.align-left {
text-align: left }
.align-center {
clear: both ;
text-align: center }
.align-right {
text-align: right }
/* reset inner alignment in figures */
div.align-right {
text-align: inherit }
/* div.align-center * { */
/* text-align: left } */
ol.simple, ul.simple {
margin-bottom: 1em }
ol.arabic {
list-style: decimal }
ol.loweralpha {
list-style: lower-alpha }
ol.upperalpha {
list-style: upper-alpha }
ol.lowerroman {
list-style: lower-roman }
ol.upperroman {
list-style: upper-roman }
p.attribution {
text-align: right ;
margin-left: 50% }
p.caption {
font-style: italic }
p.credits {
font-style: italic ;
font-size: smaller }
p.label {
white-space: nowrap }
p.rubric {
font-weight: bold ;
font-size: larger ;
color: maroon ;
text-align: center }
p.sidebar-title {
font-family: sans-serif ;
font-weight: bold ;
font-size: larger }
p.sidebar-subtitle {
font-family: sans-serif ;
font-weight: bold }
p.topic-title {
font-weight: bold }
pre.address {
margin-bottom: 0 ;
margin-top: 0 ;
font: inherit }
pre.literal-block, pre.doctest-block, pre.math {
margin-left: 2em ;
margin-right: 2em }
span.classifier {
font-family: sans-serif ;
font-style: oblique }
span.classifier-delimiter {
font-family: sans-serif ;
font-weight: bold }
span.interpreted {
font-family: sans-serif }
span.option {
white-space: nowrap }
span.pre {
white-space: pre }
span.problematic {
color: red }
span.section-subtitle {
/* font-size relative to parent (h1..h6 element) */
font-size: 80% }
table.citation {
border-left: solid 1px gray;
margin-left: 1px }
table.docinfo {
margin: 2em 4em }
table.docutils {
margin-top: 0.5em ;
margin-bottom: 0.5em }
table.footnote {
border-left: solid 1px black;
margin-left: 1px }
table.docutils td, table.docutils th,
table.docinfo td, table.docinfo th {
padding-left: 0.5em ;
padding-right: 0.5em ;
vertical-align: top }
table.docutils th.field-name, table.docinfo th.docinfo-name {
font-weight: bold ;
text-align: left ;
white-space: nowrap ;
padding-left: 0 }
h1 tt.docutils, h2 tt.docutils, h3 tt.docutils,
h4 tt.docutils, h5 tt.docutils, h6 tt.docutils {
font-size: 100% }
ul.auto-toc {
list-style-type: none }
</style>
<style type="text/css">
.file-header {
color: #999;
font-weight: bold;
}
.run-output {
white-space: pre;
font-family: monospace;
background-color: #fff;
border: 1px solid #eee;
margin: 10px 0px 0px 0px;
padding: 5px 10px 5px 10px;
}
.code {
white-space: pre;
font-family: monospace;
background-color: #dec;
border: none;
border-radius: 10px;
padding: 10px 10px 5px 3px;
margin: 5px 0px 0px 0px;
margin-left: 0px;
margin-right: 0px;
}
pre.literal-block {
margin: 5px 0px 0px 0px;
}
.code p {
padding: 0px 0px 0px 0px;
margin: 0px 0px 0px 0px;
overflow: visible;
}
.run-output p {
padding: 0px 0px 0px 0px;
margin: 0px 0px 0px 0px;
overflow: visible;
}
.interactive-input {
white-space: pre;
font-family: monospace;
}
.interactive-output {
white-space: pre;
font-family: monospace;
}
.interactive-session {
background-color: #fff;
border: 1px solid #eee;
margin: 10px 0px 0px 0px;
padding: 0px 0px 0px 5px;
overflow: visible;
}
.c { color: #408080; font-style: italic } /* Comment */
.err { border: 1px solid #FF0000 } /* Error */
.k { color: #008000; font-weight: bold } /* Keyword */
.o { color: #4444ee } /* Operator */
.cm { color: #408080; font-style: italic } /* Comment.Multiline */
.cp { color: #BC7A00 } /* Comment.Preproc */
.c1 { color: #408080; font-style: italic } /* Comment.Single */
.cs { color: #408080; font-style: italic } /* Comment.Special */
.gd { color: #A00000 } /* Generic.Deleted */
.ge { font-style: italic } /* Generic.Emph */
.gr { color: #FF0000 } /* Generic.Error */
.gh { color: #000080; font-weight: bold } /* Generic.Heading */
.gi { color: #00A000 } /* Generic.Inserted */
.go { color: #808080 } /* Generic.Output */
.gp { color: #000080; font-weight: bold } /* Generic.Prompt */
.gs { font-weight: bold } /* Generic.Strong */
.gu { color: #800080; font-weight: bold } /* Generic.Subheading */
.gt { color: #0040D0 } /* Generic.Traceback */
.kc { color: #008000; font-weight: bold } /* Keyword.Constant */
.kd { color: #008000; font-weight: bold } /* Keyword.Declaration */
.kn { color: #008000; font-weight: bold } /* Keyword.Namespace */
.kp { color: #008000 } /* Keyword.Pseudo */
.kr { color: #008000; font-weight: bold } /* Keyword.Reserved */
.kt { color: #B00040 } /* Keyword.Type */
.m { color: #666666 } /* Literal.Number */
.s { color: #BA2121 } /* Literal.String */
.na { color: #7D9029 } /* Name.Attribute */
.nb { color: #008000 } /* Name.Builtin */
.nc { color: #0000FF; font-weight: bold } /* Name.Class */
.no { color: #880000 } /* Name.Constant */
.nd { color: #AA22FF } /* Name.Decorator */
.ni { color: #999999; font-weight: bold } /* Name.Entity */
.ne { color: #D2413A; font-weight: bold } /* Name.Exception */
.nf { color: #0000FF } /* Name.Function */
.nl { color: #A0A000 } /* Name.Label */
.nn { color: #0000FF; font-weight: bold } /* Name.Namespace */
.nt { color: #008000; font-weight: bold } /* Name.Tag */
.nv { color: #19177C } /* Name.Variable */
.ow { color: #AA22FF; font-weight: bold } /* Operator.Word */
.p { color: #11aa11 } /* Parenthesis */
.w { color: #bbbbbb } /* Text.Whitespace */
.mf { color: #666666 } /* Literal.Number.Float */
.mh { color: #666666 } /* Literal.Number.Hex */
.mi { color: #666666 } /* Literal.Number.Integer */
.mo { color: #666666 } /* Literal.Number.Oct */
.sb { color: #BA2121 } /* Literal.String.Backtick */
.sc { color: #BA2121 } /* Literal.String.Char */
.sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */
.s2 { color: #BA2121 } /* Literal.String.Double */
.se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */
.sh { color: #BA2121 } /* Literal.String.Heredoc */
.si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */
.sx { color: #008000 } /* Literal.String.Other */
.sr { color: #BB6688 } /* Literal.String.Regex */
.s1 { color: #BA2121 } /* Literal.String.Single */
.ss { color: #19177C } /* Literal.String.Symbol */
.bp { color: #008000 } /* Name.Builtin.Pseudo */
.vc { color: #19177C } /* Name.Variable.Class */
.vg { color: #19177C } /* Name.Variable.Global */
.vi { color: #19177C } /* Name.Variable.Instance */
.il { color: #666666 } /* Literal.Number.Integer.Long */
.lineno { color: #bbb }
.run-output-weaver {
white-space: normal;
font-family: default;
background-color: ;
border: 3px solid #eee;
margin: 10px 0px 0px 0px;
padding: 5px 10px 5px 10px;
}
.code-weaver {
border: 3px solid #efe;
}
</style><!-- Proving type equality in a Scala pattern match -->
<p>Finally got this to work. Here's the infuriating code:</p>
<pre class="code code-file literal-block literal-block literal-block literal-block">
<span></span><span class="lineno"> 1 </span><span></span><span class="k">sealed</span><span> </span><span class="k">trait</span><span> </span><span class="nc">Two</span><span class="o">[</span><span class="kt">A</span><span>,</span><span class="kt">B</span><span class="o">]</span><span></span><span>
</span><span class="lineno"> 2 </span><span></span><span class="nc">case</span><span> </span><span class="k">class</span><span> </span><span class="nc">One</span><span class="o">[</span><span class="kt">A</span><span class="o">]</span><span class="o">(</span><span class="o">)</span><span> </span><span class="k">extends</span><span> </span><span class="nc">Two</span><span class="o">[</span><span class="kt">A</span><span>,</span><span class="kt">A</span><span class="o">]</span><span></span><span>
</span><span class="lineno"> 3 </span><span></span><span></span><span>
</span><span class="lineno"> 4 </span><span></span><span class="k">def</span><span> </span><span class="n">convert</span><span class="o">[</span><span class="kt">A</span><span>,</span><span class="kt">B</span><span class="o">]</span><span class="o">(</span><span class="n">x</span><span class="k">:</span><span> </span><span class="kt">A</span><span class="o">,</span><span> </span><span class="n">t</span><span class="k">:</span><span> </span><span class="kt">Two</span><span class="o">[</span><span class="kt">A</span><span>,</span><span class="kt">B</span><span class="o">]</span><span class="o">)</span><span class="k">:</span><span> </span><span class="kt">B</span><span> </span><span class="o">=</span><span> </span><span class="n">t</span><span> </span><span class="k">match</span><span> </span><span class="o">{</span><span></span><span>
</span><span class="lineno"> 5 </span><span></span><span> </span><span class="k">case</span><span> </span><span class="nc">One</span><span class="o">(</span><span class="o">)</span><span> </span><span class="k">=></span><span> </span><span class="n">x</span><span></span><span>
</span><span class="lineno"> 6 </span><span></span><span class="o">}</span><span></span><span>
</span><span></span>
</pre>
<p>which of course gives:</p>
<pre class="literal-block">
type mismatch;
found : x.type (with underlying type A)
required: B
case One() => x
^
</pre>
<p>You would think that Scala might introduce a constraint that <tt class="docutils literal">A =:= B</tt>, but apparently not. Of course you could just make the <tt class="docutils literal">=:=</tt> yourself</p>
<pre class="code code-file literal-block literal-block literal-block literal-block">
<span></span><span class="lineno"> 7 </span><span></span><span class="k">sealed</span><span> </span><span class="k">trait</span><span> </span><span class="nc">Two</span><span class="o">[</span><span class="kt">A</span><span>,</span><span class="kt">B</span><span class="o">]</span><span></span><span>
</span><span class="lineno"> 8 </span><span></span><span class="nc">case</span><span> </span><span class="k">class</span><span> </span><span class="nc">One</span><span class="o">[</span><span class="kt">A</span><span>,</span><span class="kt">B</span><span class="o">]</span><span class="o">(</span><span class="n">pf</span><span class="k">:</span><span> </span><span class="kt">A</span><span> </span><span class="o">=</span><span class="o">:=</span><span> </span><span class="n">B</span><span class="o">)</span><span> </span><span class="k">extends</span><span> </span><span class="nc">Two</span><span class="o">[</span><span class="kt">A</span><span>,</span><span class="kt">B</span><span class="o">]</span><span></span><span>
</span><span></span>
</pre>
<p>except that that is much more cluttered and not how people usually write and use case classes.</p>
<p>It turns out that the working solution is to use a matched (lower-case) type variable:</p>
<pre class="code code-file literal-block literal-block">
<span></span><span class="lineno"> 9 </span><span> </span><span class="k">def</span><span> </span><span class="n">convert</span><span class="o">[</span><span class="kt">A</span><span>,</span><span class="kt">B</span><span class="o">]</span><span class="o">(</span><span class="n">x</span><span class="k">:</span><span> </span><span class="kt">A</span><span class="o">,</span><span> </span><span class="n">t</span><span class="k">:</span><span> </span><span class="kt">Two</span><span class="o">[</span><span class="kt">A</span><span>,</span><span class="kt">B</span><span class="o">]</span><span class="o">)</span><span class="k">:</span><span> </span><span class="kt">B</span><span> </span><span class="o">=</span><span> </span><span class="n">t</span><span> </span><span class="k">match</span><span> </span><span class="o">{</span><span></span><span>
</span><span class="lineno"> 10 </span><span></span><span> </span><span class="k">case</span><span> </span><span class="n">o</span><span class="k">:</span><span> </span><span class="kt">One</span><span class="o">[</span><span class="kt">a</span><span class="o">]</span><span> </span><span class="k">=></span><span></span><span>
</span><span class="lineno"> 11 </span><span></span><span> </span><span class="n">x</span><span class="k">:</span><span> </span><span class="kt">a</span><span></span><span>
</span><span class="lineno"> 12 </span><span></span><span> </span><span class="o">}</span><span></span><span>
</span><span></span>
</pre>
<p>So, the <tt class="docutils literal">match</tt> is not as pretty as it could be, but the <tt class="docutils literal">case</tt> class definition is clean and we never explicitly mentioned <tt class="docutils literal">=:=</tt>, which is always a good thing.</p>
<p>(What's going on is that Scala is introducing two implicit <tt class="docutils literal">=:=</tt> s, one linking <tt class="docutils literal">a</tt> to <tt class="docutils literal">A</tt> and one linking <tt class="docutils literal">a</tt> to <tt class="docutils literal">B</tt>, but doesn't chain implicits).</p>
Owenhttp://www.blogger.com/profile/09697040246092989242noreply@blogger.com1tag:blogger.com,1999:blog-696719307153090038.post-9686708530289298242013-06-01T03:17:00.000-04:002013-06-01T03:17:32.519-04:00Using continuations to reorder type inference, or, a lesson in literal program design<style type="text/css">
/*
:Author: David Goodger (goodger@python.org)
:Id: $Id$
:Copyright: This stylesheet has been placed in the public domain.
Default cascading style sheet for the HTML output of Docutils.
See http://docutils.sf.net/docs/howto/html-stylesheets.html for how to
customize this style sheet.
*/
/* used to remove borders from tables and images */
.borderless, table.borderless td, table.borderless th {
border: 0 }
table.borderless td, table.borderless th {
/* Override padding for "table.docutils td" with "! important".
The right padding separates the table cells. */
padding: 0 0.5em 0 0 ! important }
.first {
/* Override more specific margin styles with "! important". */
margin-top: 0 ! important }
.last, .with-subtitle {
margin-bottom: 0 ! important }
.hidden {
display: none }
a.toc-backref {
text-decoration: none ;
color: black }
blockquote.epigraph {
margin: 2em 5em ; }
dl.docutils dd {
margin-bottom: 0.5em }
object[type="image/svg+xml"], object[type="application/x-shockwave-flash"] {
overflow: hidden;
}
/* Uncomment (and remove this text!) to get bold-faced definition list terms
dl.docutils dt {
font-weight: bold }
*/
div.abstract {
margin: 2em 5em }
div.abstract p.topic-title {
font-weight: bold ;
text-align: center }
div.admonition, div.attention, div.caution, div.danger, div.error,
div.hint, div.important, div.note, div.tip, div.warning {
margin: 2em ;
border: medium outset ;
padding: 1em }
div.admonition p.admonition-title, div.hint p.admonition-title,
div.important p.admonition-title, div.note p.admonition-title,
div.tip p.admonition-title {
font-weight: bold ;
font-family: sans-serif }
div.attention p.admonition-title, div.caution p.admonition-title,
div.danger p.admonition-title, div.error p.admonition-title,
div.warning p.admonition-title {
color: red ;
font-weight: bold ;
font-family: sans-serif }
/* Uncomment (and remove this text!) to get reduced vertical space in
compound paragraphs.
div.compound .compound-first, div.compound .compound-middle {
margin-bottom: 0.5em }
div.compound .compound-last, div.compound .compound-middle {
margin-top: 0.5em }
*/
div.dedication {
margin: 2em 5em ;
text-align: center ;
font-style: italic }
div.dedication p.topic-title {
font-weight: bold ;
font-style: normal }
div.figure {
margin-left: 2em ;
margin-right: 2em }
div.footer, div.header {
clear: both;
font-size: smaller }
div.line-block {
display: block ;
margin-top: 1em ;
margin-bottom: 1em }
div.line-block div.line-block {
margin-top: 0 ;
margin-bottom: 0 ;
margin-left: 1.5em }
div.sidebar {
margin: 0 0 0.5em 1em ;
border: medium outset ;
padding: 1em ;
background-color: #ffffee ;
width: 40% ;
float: right ;
clear: right }
div.sidebar p.rubric {
font-family: sans-serif ;
font-size: medium }
div.system-messages {
margin: 5em }
div.system-messages h1 {
color: red }
div.system-message {
border: medium outset ;
padding: 1em }
div.system-message p.system-message-title {
color: red ;
font-weight: bold }
div.topic {
margin: 2em }
h1.section-subtitle, h2.section-subtitle, h3.section-subtitle,
h4.section-subtitle, h5.section-subtitle, h6.section-subtitle {
margin-top: 0.4em }
h1.title {
text-align: center }
h2.subtitle {
text-align: center }
hr.docutils {
width: 75% }
img.align-left, .figure.align-left, object.align-left {
clear: left ;
float: left ;
margin-right: 1em }
img.align-right, .figure.align-right, object.align-right {
clear: right ;
float: right ;
margin-left: 1em }
img.align-center, .figure.align-center, object.align-center {
display: block;
margin-left: auto;
margin-right: auto;
}
.align-left {
text-align: left }
.align-center {
clear: both ;
text-align: center }
.align-right {
text-align: right }
/* reset inner alignment in figures */
div.align-right {
text-align: inherit }
/* div.align-center * { */
/* text-align: left } */
ol.simple, ul.simple {
margin-bottom: 1em }
ol.arabic {
list-style: decimal }
ol.loweralpha {
list-style: lower-alpha }
ol.upperalpha {
list-style: upper-alpha }
ol.lowerroman {
list-style: lower-roman }
ol.upperroman {
list-style: upper-roman }
p.attribution {
text-align: right ;
margin-left: 50% }
p.caption {
font-style: italic }
p.credits {
font-style: italic ;
font-size: smaller }
p.label {
white-space: nowrap }
p.rubric {
font-weight: bold ;
font-size: larger ;
color: maroon ;
text-align: center }
p.sidebar-title {
font-family: sans-serif ;
font-weight: bold ;
font-size: larger }
p.sidebar-subtitle {
font-family: sans-serif ;
font-weight: bold }
p.topic-title {
font-weight: bold }
pre.address {
margin-bottom: 0 ;
margin-top: 0 ;
font: inherit }
pre.literal-block, pre.doctest-block, pre.math {
margin-left: 2em ;
margin-right: 2em }
span.classifier {
font-family: sans-serif ;
font-style: oblique }
span.classifier-delimiter {
font-family: sans-serif ;
font-weight: bold }
span.interpreted {
font-family: sans-serif }
span.option {
white-space: nowrap }
span.pre {
white-space: pre }
span.problematic {
color: red }
span.section-subtitle {
/* font-size relative to parent (h1..h6 element) */
font-size: 80% }
table.citation {
border-left: solid 1px gray;
margin-left: 1px }
table.docinfo {
margin: 2em 4em }
table.docutils {
margin-top: 0.5em ;
margin-bottom: 0.5em }
table.footnote {
border-left: solid 1px black;
margin-left: 1px }
table.docutils td, table.docutils th,
table.docinfo td, table.docinfo th {
padding-left: 0.5em ;
padding-right: 0.5em ;
vertical-align: top }
table.docutils th.field-name, table.docinfo th.docinfo-name {
font-weight: bold ;
text-align: left ;
white-space: nowrap ;
padding-left: 0 }
h1 tt.docutils, h2 tt.docutils, h3 tt.docutils,
h4 tt.docutils, h5 tt.docutils, h6 tt.docutils {
font-size: 100% }
ul.auto-toc {
list-style-type: none }
</style>
<style type="text/css">
.file-header {
color: #999;
font-weight: bold;
}
.run-output {
white-space: pre;
font-family: monospace;
background-color: #fff;
border: 1px solid #eee;
margin: 10px 0px 0px 0px;
padding: 5px 10px 5px 10px;
}
.code {
white-space: pre;
font-family: monospace;
background-color: #dec;
border: none;
border-radius: 10px;
padding: 10px 10px 5px 3px;
margin: 5px 0px 0px 0px;
margin-left: 0px;
margin-right: 0px;
}
pre.literal-block {
margin: 5px 0px 0px 0px;
}
.code p {
padding: 0px 0px 0px 0px;
margin: 0px 0px 0px 0px;
overflow: visible;
}
.run-output p {
padding: 0px 0px 0px 0px;
margin: 0px 0px 0px 0px;
overflow: visible;
}
.interactive-input {
white-space: pre;
font-family: monospace;
}
.interactive-output {
white-space: pre;
font-family: monospace;
}
.interactive-session {
background-color: #fff;
border: 1px solid #eee;
margin: 10px 0px 0px 0px;
padding: 0px 0px 0px 5px;
overflow: visible;
}
.c { color: #408080; font-style: italic } /* Comment */
.err { border: 1px solid #FF0000 } /* Error */
.k { color: #008000; font-weight: bold } /* Keyword */
.o { color: #4444ee } /* Operator */
.cm { color: #408080; font-style: italic } /* Comment.Multiline */
.cp { color: #BC7A00 } /* Comment.Preproc */
.c1 { color: #408080; font-style: italic } /* Comment.Single */
.cs { color: #408080; font-style: italic } /* Comment.Special */
.gd { color: #A00000 } /* Generic.Deleted */
.ge { font-style: italic } /* Generic.Emph */
.gr { color: #FF0000 } /* Generic.Error */
.gh { color: #000080; font-weight: bold } /* Generic.Heading */
.gi { color: #00A000 } /* Generic.Inserted */
.go { color: #808080 } /* Generic.Output */
.gp { color: #000080; font-weight: bold } /* Generic.Prompt */
.gs { font-weight: bold } /* Generic.Strong */
.gu { color: #800080; font-weight: bold } /* Generic.Subheading */
.gt { color: #0040D0 } /* Generic.Traceback */
.kc { color: #008000; font-weight: bold } /* Keyword.Constant */
.kd { color: #008000; font-weight: bold } /* Keyword.Declaration */
.kn { color: #008000; font-weight: bold } /* Keyword.Namespace */
.kp { color: #008000 } /* Keyword.Pseudo */
.kr { color: #008000; font-weight: bold } /* Keyword.Reserved */
.kt { color: #B00040 } /* Keyword.Type */
.m { color: #666666 } /* Literal.Number */
.s { color: #BA2121 } /* Literal.String */
.na { color: #7D9029 } /* Name.Attribute */
.nb { color: #008000 } /* Name.Builtin */
.nc { color: #0000FF; font-weight: bold } /* Name.Class */
.no { color: #880000 } /* Name.Constant */
.nd { color: #AA22FF } /* Name.Decorator */
.ni { color: #999999; font-weight: bold } /* Name.Entity */
.ne { color: #D2413A; font-weight: bold } /* Name.Exception */
.nf { color: #0000FF } /* Name.Function */
.nl { color: #A0A000 } /* Name.Label */
.nn { color: #0000FF; font-weight: bold } /* Name.Namespace */
.nt { color: #008000; font-weight: bold } /* Name.Tag */
.nv { color: #19177C } /* Name.Variable */
.ow { color: #AA22FF; font-weight: bold } /* Operator.Word */
.p { color: #11aa11 } /* Parenthesis */
.w { color: #bbbbbb } /* Text.Whitespace */
.mf { color: #666666 } /* Literal.Number.Float */
.mh { color: #666666 } /* Literal.Number.Hex */
.mi { color: #666666 } /* Literal.Number.Integer */
.mo { color: #666666 } /* Literal.Number.Oct */
.sb { color: #BA2121 } /* Literal.String.Backtick */
.sc { color: #BA2121 } /* Literal.String.Char */
.sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */
.s2 { color: #BA2121 } /* Literal.String.Double */
.se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */
.sh { color: #BA2121 } /* Literal.String.Heredoc */
.si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */
.sx { color: #008000 } /* Literal.String.Other */
.sr { color: #BB6688 } /* Literal.String.Regex */
.s1 { color: #BA2121 } /* Literal.String.Single */
.ss { color: #19177C } /* Literal.String.Symbol */
.bp { color: #008000 } /* Name.Builtin.Pseudo */
.vc { color: #19177C } /* Name.Variable.Class */
.vg { color: #19177C } /* Name.Variable.Global */
.vi { color: #19177C } /* Name.Variable.Instance */
.il { color: #666666 } /* Literal.Number.Integer.Long */
.lineno { color: #bbb }
.run-output-weaver {
white-space: normal;
font-family: default;
background-color: ;
border: 3px solid #eee;
margin: 10px 0px 0px 0px;
padding: 5px 10px 5px 10px;
}
.code-weaver {
border: 3px solid #efe;
}
</style><!-- Using continuations to reorder type inference. -->
<p>Consider the following definition for a chain of computations:</p>
<pre class="code code-file literal-block literal-block literal-block literal-block literal-block literal-block literal-block literal-block">
<span></span><span class="lineno"> 1 </span><span></span><span class="k">sealed</span><span> </span><span class="k">trait</span><span> </span><span class="nc">Chain</span><span class="o">[</span><span class="kt">-</span><span class="kt">A</span><span>,</span><span class="kt">+</span><span class="kt">B</span><span class="o">]</span><span></span><span>
</span><span class="lineno"> 2 </span><span></span><span class="nc">case</span><span> </span><span class="k">class</span><span> </span><span class="nc">End</span><span class="o">[</span><span class="kt">A</span><span class="o">]</span><span class="o">(</span><span class="o">)</span><span> </span><span class="k">extends</span><span> </span><span class="nc">Chain</span><span class="o">[</span><span class="kt">A</span><span>,</span><span class="kt">A</span><span class="o">]</span><span></span><span>
</span><span class="lineno"> 3 </span><span></span><span class="k">trait</span><span> </span><span class="nc">Chaining</span><span class="o">[</span><span class="kt">A</span><span>,</span><span class="kt">B</span><span class="o">]</span><span> </span><span class="nc">extends</span><span> </span><span class="nc">Chain</span><span class="o">[</span><span class="kt">A</span><span>,</span><span class="kt">B</span><span class="o">]</span><span> </span><span class="o">{</span><span></span><span>
</span><span class="lineno"> 4 </span><span></span><span> </span><span class="k">type</span><span> </span><span class="kt">I</span><span></span><span>
</span><span class="lineno"> 5 </span><span></span><span> </span><span class="k">val</span><span> </span><span class="n">first</span><span class="k">:</span><span> </span><span class="kt">A</span><span> </span><span class="o">=></span><span> </span><span class="n">I</span><span></span><span>
</span><span class="lineno"> 6 </span><span></span><span> </span><span class="k">val</span><span> </span><span class="n">rest</span><span class="k">:</span><span> </span><span class="kt">Chain</span><span class="o">[</span><span class="kt">I</span><span>,</span><span class="kt">B</span><span class="o">]</span><span></span><span>
</span><span class="lineno"> 7 </span><span></span><span class="o">}</span><span></span><span>
</span><span></span>
</pre>
<p>It is much like the <tt class="docutils literal">List</tt> type, except that there is a hidden (existential) dependency between adjacent elements.</p>
<p>The "nestedness" of the structure is chosen to be like the <tt class="docutils literal">List</tt> type for a very specific reason: when you go to use a <tt class="docutils literal">Chain</tt>, you will perform the first computation first, so it should be the least nested; the last computation should be the most nested.</p>
<p><tt class="docutils literal">List</tt> defines a right-associative <tt class="docutils literal">::</tt> operator for building. Let us define such an operator:</p>
<pre class="code code-file literal-block literal-block">
<span></span><span class="lineno"> 8 </span><span></span><span class="k">sealed</span><span> </span><span class="k">trait</span><span> </span><span class="nc">Chain</span><span class="o">[</span><span class="kt">-</span><span class="kt">A</span><span>,</span><span class="kt">+</span><span class="kt">B</span><span class="o">]</span><span> </span><span class="o">{</span><span></span><span>
</span><span class="lineno"> 9 </span><span></span><span> </span><span class="k">def</span><span> </span><span class="o">:->:</span><span class="o">[</span><span class="kt">A2</span><span class="k"><:</span><span class="kt">A</span><span>,</span><span class="kt">P</span><span class="o">]</span><span class="o">(</span><span class="n">f</span><span class="k">:</span><span> </span><span class="kt">P</span><span> </span><span class="o">=></span><span> </span><span class="n">A2</span><span class="o">)</span><span class="k">:</span><span> </span><span class="kt">Chain</span><span class="o">[</span><span class="kt">P</span><span>,</span><span class="kt">B</span><span class="o">]</span><span> </span><span class="k">=</span><span> </span><span class="k">new</span><span> </span><span class="nc">Chaining</span><span class="o">[</span><span class="kt">P</span><span>,</span><span class="kt">B</span><span class="o">]</span><span> </span><span class="o">{</span><span></span><span>
</span><span class="lineno"> 10 </span><span></span><span> </span><span class="k">type</span><span> </span><span class="kt">I</span><span> </span><span class="o">=</span><span> </span><span class="n">A</span><span></span><span>
</span><span class="lineno"> 11 </span><span></span><span> </span><span class="k">val</span><span> </span><span class="n">first</span><span> </span><span class="k">=</span><span> </span><span class="n">f</span><span></span><span>
</span><span class="lineno"> 12 </span><span></span><span> </span><span class="k">val</span><span> </span><span class="n">rest</span><span> </span><span class="k">=</span><span> </span><span class="nc">Chain</span><span class="o">.</span><span class="k">this</span><span></span><span>
</span><span class="lineno"> 13 </span><span></span><span> </span><span class="o">}</span><span></span><span>
</span><span class="lineno"> 14 </span><span></span><span class="o">}</span><span></span><span>
</span><span></span>
</pre>
<p>But we see we have a type inference problem:</p>
<pre class="code code-file literal-block literal-block">
<span></span><span class="lineno"> 15 </span><span></span><span class="c1">// Note the type annotation needed for second stage.</span><span>
</span><span class="lineno"> 16 </span><span class="c1"></span><span class="k">val</span><span> </span><span class="n">pipeline</span><span> </span><span class="k">=</span><span> </span><span class="o">(</span><span></span><span>
</span><span class="lineno"> 17 </span><span></span><span> </span><span class="o">{</span><span> </span><span class="o">(</span><span class="n">i</span><span class="k">:</span><span> </span><span class="kt">Int</span><span class="o">)</span><span> </span><span class="k">=></span><span> </span><span class="n">i</span><span class="o">.</span><span class="n">toString</span><span> </span><span class="o">}</span><span></span><span>
</span><span class="lineno"> 18 </span><span></span><span> </span><span class="o">:->:</span><span> </span><span class="o">{</span><span> </span><span class="o">(</span><span class="n">s</span><span class="k">:</span><span> </span><span class="kt">String</span><span class="o">)</span><span> </span><span class="k">=></span><span> </span><span class="n">s</span><span> </span><span class="o">++</span><span> </span><span class="n">s</span><span> </span><span class="o">}</span><span></span><span>
</span><span class="lineno"> 19 </span><span></span><span> </span><span class="o">:->:</span><span> </span><span class="nc">End</span><span class="o">(</span><span class="o">)</span><span></span><span>
</span><span class="lineno"> 20 </span><span></span><span class="o">)</span><span></span><span>
</span><span></span>
</pre>
<p>We might be tempted to think that the problem arises with Scala insisting that infix operators be members -- this does seem to be a likely explanation, since <cite>:->:</cite> being a member means that Scala must deduce the type of the right-hand operand first, which is the opposite of the direction in which we would like type information to flow. But you will find that the following non-member function fairs no better:</p>
<pre class="code code-file literal-block literal-block">
<span></span><span class="lineno"> 21 </span><span></span><span class="k">def</span><span> </span><span class="n">c</span><span class="o">[</span><span class="kt">A</span><span>,</span><span class="kt">B</span><span>,</span><span class="kt">C</span><span class="o">]</span><span class="o">(</span><span class="n">f</span><span class="k">:</span><span> </span><span class="kt">A</span><span> </span><span class="o">=></span><span> </span><span class="n">B</span><span class="o">,</span><span> </span><span class="n">rest</span><span class="k">:</span><span> </span><span class="kt">Chain</span><span class="o">[</span><span class="kt">B</span><span>,</span><span class="kt">C</span><span class="o">]</span><span class="o">)</span><span class="k">:</span><span> </span><span class="kt">Chain</span><span class="o">[</span><span class="kt">A</span><span>,</span><span class="kt">C</span><span class="o">]</span><span> </span><span class="k">=</span><span> </span><span class="n">f</span><span> </span><span class="o">:->:</span><span> </span><span class="n">rest</span><span></span><span>
</span><span></span>
</pre>
<p>But we can learn something from the areas where Scala's type inference does seem to work very well, namely chains of list operations, <tt class="docutils literal">map</tt>, <tt class="docutils literal">filter</tt>, <tt class="docutils literal">grouBy</tt>, etc, where you almost never need to annotate types. The reason is that any stage of a list-operation chain is itself an "incomplete operation chain" (ie we are (potentially) not done the computation yet), which can be extended to another incomplete chain by way of the next <tt class="docutils literal">map</tt> or <tt class="docutils literal">filter</tt>.</p>
<p>So what we need is a representation of an "incomplete <tt class="docutils literal">Chain</tt>".</p>
<p>The most obvious meaning of an "incomplete <tt class="docutils literal">Chain</tt>" is "something that can be turned into a complete chain by providing the following steps".</p>
<p><strong>Principle rule of functional programming design: when you can say plainly and succinctly what something "is", translate that sentence literally into code, and there is your design.</strong></p>
<p>Do not use tricks, do not use fancy types: simply turn sentences into their most literal meaning.</p>
<p>(Analogously in imperative code, you are looking to say what something "does").</p>
<p>Let us apply the rule as literally as we can:</p>
<pre class="code code-file literal-block literal-block">
<span></span><span class="lineno"> 22 </span><span></span><span class="k">trait</span><span> </span><span class="nc">ChainBuilder</span><span class="o">[</span><span class="kt">A</span><span>,</span><span class="kt">B</span><span class="o">]</span><span> </span><span class="o">{</span><span> </span><span class="n">outer</span><span> </span><span class="k">=></span><span></span><span>
</span><span class="lineno"> 23 </span><span></span><span> </span><span class="k">def</span><span> </span><span class="n">build</span><span class="o">[</span><span class="kt">C</span><span class="o">]</span><span class="o">(</span><span class="n">rest</span><span class="k">:</span><span> </span><span class="kt">Chain</span><span class="o">[</span><span class="kt">B</span><span>,</span><span class="kt">C</span><span class="o">]</span><span class="o">)</span><span class="k">:</span><span> </span><span class="kt">Chain</span><span class="o">[</span><span class="kt">A</span><span>,</span><span class="kt">C</span><span class="o">]</span><span></span><span>
</span><span class="lineno"> 24 </span><span></span><span class="o">}</span><span></span><span>
</span><span></span>
</pre>
<p>Our "incomplete <tt class="docutils literal">Chain</tt>" is, unsurprisingly, a kind of continuation, since a continuation is the most basic form of an incomplete computation.</p>
<p>We can then define the incremental building operations:</p>
<pre class="code code-file literal-block literal-block">
<span></span><span class="lineno"> 25 </span><span></span><span class="k">trait</span><span> </span><span class="nc">ChainBuilder</span><span class="o">[</span><span class="kt">A</span><span>,</span><span class="kt">B</span><span class="o">]</span><span> </span><span class="o">{</span><span> </span><span class="n">outer</span><span> </span><span class="k">=></span><span></span><span>
</span><span class="lineno"> 26 </span><span></span><span> </span><span class="k">def</span><span> </span><span class="n">build</span><span class="o">[</span><span class="kt">C</span><span class="o">]</span><span class="o">(</span><span class="n">rest</span><span class="k">:</span><span> </span><span class="kt">Chain</span><span class="o">[</span><span class="kt">B</span><span>,</span><span class="kt">C</span><span class="o">]</span><span class="o">)</span><span class="k">:</span><span> </span><span class="kt">Chain</span><span class="o">[</span><span class="kt">A</span><span>,</span><span class="kt">C</span><span class="o">]</span><span></span><span>
</span><span class="lineno"> 27 </span><span></span><span></span><span>
</span><span class="lineno"> 28 </span><span></span><span> </span><span class="k">def</span><span> </span><span class="n">and</span><span class="o">[</span><span class="kt">C</span><span class="o">]</span><span class="o">(</span><span class="n">f</span><span class="k">:</span><span> </span><span class="kt">B</span><span> </span><span class="o">=></span><span> </span><span class="n">C</span><span class="o">)</span><span> </span><span class="k">=</span><span> </span><span class="k">new</span><span> </span><span class="nc">ChainBuilder</span><span class="o">[</span><span class="kt">A</span><span>,</span><span class="kt">C</span><span class="o">]</span><span> </span><span class="o">{</span><span></span><span>
</span><span class="lineno"> 29 </span><span></span><span> </span><span class="k">def</span><span> </span><span class="n">build</span><span class="o">[</span><span class="kt">D</span><span class="o">]</span><span class="o">(</span><span class="n">rest</span><span class="k">:</span><span> </span><span class="kt">Chain</span><span class="o">[</span><span class="kt">C</span><span>,</span><span class="kt">D</span><span class="o">]</span><span class="o">)</span><span> </span><span class="k">=</span><span> </span><span class="n">outer</span><span class="o">.</span><span class="n">build</span><span class="o">(</span><span class="n">f</span><span> </span><span class="o">:->:</span><span> </span><span class="n">rest</span><span class="o">)</span><span></span><span>
</span><span class="lineno"> 30 </span><span></span><span> </span><span class="o">}</span><span></span><span>
</span><span class="lineno"> 31 </span><span></span><span> </span><span class="k">def</span><span> </span><span class="n">done</span><span> </span><span class="k">=</span><span> </span><span class="n">build</span><span class="o">(</span><span class="nc">End</span><span class="o">(</span><span class="o">)</span><span class="o">)</span><span></span><span>
</span><span class="lineno"> 32 </span><span></span><span class="o">}</span><span></span><span>
</span><span class="lineno"> 33 </span><span></span><span></span><span>
</span><span class="lineno"> 34 </span><span></span><span class="k">def</span><span> </span><span class="n">start</span><span class="o">[</span><span class="kt">A</span><span class="o">]</span><span> </span><span class="k">=</span><span> </span><span class="k">new</span><span> </span><span class="nc">ChainBuilder</span><span class="o">[</span><span class="kt">A</span><span>,</span><span class="kt">A</span><span class="o">]</span><span> </span><span class="o">{</span><span></span><span>
</span><span class="lineno"> 35 </span><span></span><span> </span><span class="k">def</span><span> </span><span class="n">build</span><span class="o">[</span><span class="kt">B</span><span class="o">]</span><span class="o">(</span><span class="n">rest</span><span class="k">:</span><span> </span><span class="kt">Chain</span><span class="o">[</span><span class="kt">A</span><span>,</span><span class="kt">B</span><span class="o">]</span><span class="o">)</span><span> </span><span class="k">=</span><span> </span><span class="n">rest</span><span></span><span>
</span><span class="lineno"> 36 </span><span></span><span class="o">}</span><span></span><span>
</span><span></span>
</pre>
<p>And now everything works:</p>
<pre class="code code-file literal-block literal-block">
<span></span><span class="lineno"> 37 </span><span></span><span class="k">val</span><span> </span><span class="n">pipeline3</span><span> </span><span class="k">=</span><span> </span><span class="o">(</span><span class="n">start</span><span class="o">[</span><span class="kt">Int</span><span class="o">]</span><span></span><span>
</span><span class="lineno"> 38 </span><span></span><span> </span><span class="n">and</span><span> </span><span class="o">{</span><span> </span><span class="n">i</span><span> </span><span class="k">=></span><span> </span><span class="n">i</span><span class="o">.</span><span class="n">toString</span><span> </span><span class="o">}</span><span></span><span>
</span><span class="lineno"> 39 </span><span></span><span> </span><span class="n">and</span><span> </span><span class="o">{</span><span> </span><span class="n">s</span><span> </span><span class="k">=></span><span> </span><span class="n">s</span><span> </span><span class="o">++</span><span> </span><span class="n">s</span><span> </span><span class="o">}</span><span class="o">)</span><span class="o">.</span><span class="n">done</span><span></span><span>
</span><span></span>
</pre>
<p>I feel there may be something more useful here than merely getting better type inference but I haven't yet figured out what.</p>
Owenhttp://www.blogger.com/profile/09697040246092989242noreply@blogger.com0tag:blogger.com,1999:blog-696719307153090038.post-75000148625832065862013-05-31T00:55:00.000-04:002013-05-31T00:55:10.535-04:00Avoiding state machines in an Actor by passing continuations<style type="text/css">
/*
:Author: David Goodger (goodger@python.org)
:Id: $Id$
:Copyright: This stylesheet has been placed in the public domain.
Default cascading style sheet for the HTML output of Docutils.
See http://docutils.sf.net/docs/howto/html-stylesheets.html for how to
customize this style sheet.
*/
/* used to remove borders from tables and images */
.borderless, table.borderless td, table.borderless th {
border: 0 }
table.borderless td, table.borderless th {
/* Override padding for "table.docutils td" with "! important".
The right padding separates the table cells. */
padding: 0 0.5em 0 0 ! important }
.first {
/* Override more specific margin styles with "! important". */
margin-top: 0 ! important }
.last, .with-subtitle {
margin-bottom: 0 ! important }
.hidden {
display: none }
a.toc-backref {
text-decoration: none ;
color: black }
blockquote.epigraph {
margin: 2em 5em ; }
dl.docutils dd {
margin-bottom: 0.5em }
object[type="image/svg+xml"], object[type="application/x-shockwave-flash"] {
overflow: hidden;
}
/* Uncomment (and remove this text!) to get bold-faced definition list terms
dl.docutils dt {
font-weight: bold }
*/
div.abstract {
margin: 2em 5em }
div.abstract p.topic-title {
font-weight: bold ;
text-align: center }
div.admonition, div.attention, div.caution, div.danger, div.error,
div.hint, div.important, div.note, div.tip, div.warning {
margin: 2em ;
border: medium outset ;
padding: 1em }
div.admonition p.admonition-title, div.hint p.admonition-title,
div.important p.admonition-title, div.note p.admonition-title,
div.tip p.admonition-title {
font-weight: bold ;
font-family: sans-serif }
div.attention p.admonition-title, div.caution p.admonition-title,
div.danger p.admonition-title, div.error p.admonition-title,
div.warning p.admonition-title {
color: red ;
font-weight: bold ;
font-family: sans-serif }
/* Uncomment (and remove this text!) to get reduced vertical space in
compound paragraphs.
div.compound .compound-first, div.compound .compound-middle {
margin-bottom: 0.5em }
div.compound .compound-last, div.compound .compound-middle {
margin-top: 0.5em }
*/
div.dedication {
margin: 2em 5em ;
text-align: center ;
font-style: italic }
div.dedication p.topic-title {
font-weight: bold ;
font-style: normal }
div.figure {
margin-left: 2em ;
margin-right: 2em }
div.footer, div.header {
clear: both;
font-size: smaller }
div.line-block {
display: block ;
margin-top: 1em ;
margin-bottom: 1em }
div.line-block div.line-block {
margin-top: 0 ;
margin-bottom: 0 ;
margin-left: 1.5em }
div.sidebar {
margin: 0 0 0.5em 1em ;
border: medium outset ;
padding: 1em ;
background-color: #ffffee ;
width: 40% ;
float: right ;
clear: right }
div.sidebar p.rubric {
font-family: sans-serif ;
font-size: medium }
div.system-messages {
margin: 5em }
div.system-messages h1 {
color: red }
div.system-message {
border: medium outset ;
padding: 1em }
div.system-message p.system-message-title {
color: red ;
font-weight: bold }
div.topic {
margin: 2em }
h1.section-subtitle, h2.section-subtitle, h3.section-subtitle,
h4.section-subtitle, h5.section-subtitle, h6.section-subtitle {
margin-top: 0.4em }
h1.title {
text-align: center }
h2.subtitle {
text-align: center }
hr.docutils {
width: 75% }
img.align-left, .figure.align-left, object.align-left {
clear: left ;
float: left ;
margin-right: 1em }
img.align-right, .figure.align-right, object.align-right {
clear: right ;
float: right ;
margin-left: 1em }
img.align-center, .figure.align-center, object.align-center {
display: block;
margin-left: auto;
margin-right: auto;
}
.align-left {
text-align: left }
.align-center {
clear: both ;
text-align: center }
.align-right {
text-align: right }
/* reset inner alignment in figures */
div.align-right {
text-align: inherit }
/* div.align-center * { */
/* text-align: left } */
ol.simple, ul.simple {
margin-bottom: 1em }
ol.arabic {
list-style: decimal }
ol.loweralpha {
list-style: lower-alpha }
ol.upperalpha {
list-style: upper-alpha }
ol.lowerroman {
list-style: lower-roman }
ol.upperroman {
list-style: upper-roman }
p.attribution {
text-align: right ;
margin-left: 50% }
p.caption {
font-style: italic }
p.credits {
font-style: italic ;
font-size: smaller }
p.label {
white-space: nowrap }
p.rubric {
font-weight: bold ;
font-size: larger ;
color: maroon ;
text-align: center }
p.sidebar-title {
font-family: sans-serif ;
font-weight: bold ;
font-size: larger }
p.sidebar-subtitle {
font-family: sans-serif ;
font-weight: bold }
p.topic-title {
font-weight: bold }
pre.address {
margin-bottom: 0 ;
margin-top: 0 ;
font: inherit }
pre.literal-block, pre.doctest-block, pre.math {
margin-left: 2em ;
margin-right: 2em }
span.classifier {
font-family: sans-serif ;
font-style: oblique }
span.classifier-delimiter {
font-family: sans-serif ;
font-weight: bold }
span.interpreted {
font-family: sans-serif }
span.option {
white-space: nowrap }
span.pre {
white-space: pre }
span.problematic {
color: red }
span.section-subtitle {
/* font-size relative to parent (h1..h6 element) */
font-size: 80% }
table.citation {
border-left: solid 1px gray;
margin-left: 1px }
table.docinfo {
margin: 2em 4em }
table.docutils {
margin-top: 0.5em ;
margin-bottom: 0.5em }
table.footnote {
border-left: solid 1px black;
margin-left: 1px }
table.docutils td, table.docutils th,
table.docinfo td, table.docinfo th {
padding-left: 0.5em ;
padding-right: 0.5em ;
vertical-align: top }
table.docutils th.field-name, table.docinfo th.docinfo-name {
font-weight: bold ;
text-align: left ;
white-space: nowrap ;
padding-left: 0 }
h1 tt.docutils, h2 tt.docutils, h3 tt.docutils,
h4 tt.docutils, h5 tt.docutils, h6 tt.docutils {
font-size: 100% }
ul.auto-toc {
list-style-type: none }
</style>
<style type="text/css">
.file-header {
color: #999;
font-weight: bold;
}
.run-output {
white-space: pre;
font-family: monospace;
background-color: #fff;
border: 1px solid #eee;
margin: 10px 0px 0px 0px;
padding: 5px 10px 5px 10px;
}
.code {
white-space: pre;
font-family: monospace;
background-color: #dec;
border: none;
border-radius: 10px;
padding: 10px 10px 5px 3px;
margin: 5px 0px 0px 0px;
margin-left: 0px;
margin-right: 0px;
}
pre.literal-block {
margin: 5px 0px 0px 0px;
}
.code p {
padding: 0px 0px 0px 0px;
margin: 0px 0px 0px 0px;
overflow: visible;
}
.run-output p {
padding: 0px 0px 0px 0px;
margin: 0px 0px 0px 0px;
overflow: visible;
}
.interactive-input {
white-space: pre;
font-family: monospace;
}
.interactive-output {
white-space: pre;
font-family: monospace;
}
.interactive-session {
background-color: #fff;
border: 1px solid #eee;
margin: 10px 0px 0px 0px;
padding: 0px 0px 0px 5px;
overflow: visible;
}
.c { color: #408080; font-style: italic } /* Comment */
.err { border: 1px solid #FF0000 } /* Error */
.k { color: #008000; font-weight: bold } /* Keyword */
.o { color: #4444ee } /* Operator */
.cm { color: #408080; font-style: italic } /* Comment.Multiline */
.cp { color: #BC7A00 } /* Comment.Preproc */
.c1 { color: #408080; font-style: italic } /* Comment.Single */
.cs { color: #408080; font-style: italic } /* Comment.Special */
.gd { color: #A00000 } /* Generic.Deleted */
.ge { font-style: italic } /* Generic.Emph */
.gr { color: #FF0000 } /* Generic.Error */
.gh { color: #000080; font-weight: bold } /* Generic.Heading */
.gi { color: #00A000 } /* Generic.Inserted */
.go { color: #808080 } /* Generic.Output */
.gp { color: #000080; font-weight: bold } /* Generic.Prompt */
.gs { font-weight: bold } /* Generic.Strong */
.gu { color: #800080; font-weight: bold } /* Generic.Subheading */
.gt { color: #0040D0 } /* Generic.Traceback */
.kc { color: #008000; font-weight: bold } /* Keyword.Constant */
.kd { color: #008000; font-weight: bold } /* Keyword.Declaration */
.kn { color: #008000; font-weight: bold } /* Keyword.Namespace */
.kp { color: #008000 } /* Keyword.Pseudo */
.kr { color: #008000; font-weight: bold } /* Keyword.Reserved */
.kt { color: #B00040 } /* Keyword.Type */
.m { color: #666666 } /* Literal.Number */
.s { color: #BA2121 } /* Literal.String */
.na { color: #7D9029 } /* Name.Attribute */
.nb { color: #008000 } /* Name.Builtin */
.nc { color: #0000FF; font-weight: bold } /* Name.Class */
.no { color: #880000 } /* Name.Constant */
.nd { color: #AA22FF } /* Name.Decorator */
.ni { color: #999999; font-weight: bold } /* Name.Entity */
.ne { color: #D2413A; font-weight: bold } /* Name.Exception */
.nf { color: #0000FF } /* Name.Function */
.nl { color: #A0A000 } /* Name.Label */
.nn { color: #0000FF; font-weight: bold } /* Name.Namespace */
.nt { color: #008000; font-weight: bold } /* Name.Tag */
.nv { color: #19177C } /* Name.Variable */
.ow { color: #AA22FF; font-weight: bold } /* Operator.Word */
.p { color: #11aa11 } /* Parenthesis */
.w { color: #bbbbbb } /* Text.Whitespace */
.mf { color: #666666 } /* Literal.Number.Float */
.mh { color: #666666 } /* Literal.Number.Hex */
.mi { color: #666666 } /* Literal.Number.Integer */
.mo { color: #666666 } /* Literal.Number.Oct */
.sb { color: #BA2121 } /* Literal.String.Backtick */
.sc { color: #BA2121 } /* Literal.String.Char */
.sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */
.s2 { color: #BA2121 } /* Literal.String.Double */
.se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */
.sh { color: #BA2121 } /* Literal.String.Heredoc */
.si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */
.sx { color: #008000 } /* Literal.String.Other */
.sr { color: #BB6688 } /* Literal.String.Regex */
.s1 { color: #BA2121 } /* Literal.String.Single */
.ss { color: #19177C } /* Literal.String.Symbol */
.bp { color: #008000 } /* Name.Builtin.Pseudo */
.vc { color: #19177C } /* Name.Variable.Class */
.vg { color: #19177C } /* Name.Variable.Global */
.vi { color: #19177C } /* Name.Variable.Instance */
.il { color: #666666 } /* Literal.Number.Integer.Long */
.lineno { color: #bbb }
.run-output-weaver {
white-space: normal;
font-family: default;
background-color: ;
border: 3px solid #eee;
margin: 10px 0px 0px 0px;
padding: 5px 10px 5px 10px;
}
.code-weaver {
border: 3px solid #efe;
}
</style><!-- Passing continuations in an Actor -->
<p>This example shows the use of continuation-passing style to offload a long-running computation
in an Actor without unrolling the code into an unwieldy state machine:</p>
<script src="https://gist.github.com/ellbur/5682980.js"></script><p>You're probably not supposed to use Actors this way.</p>
<p>It avoids a growing stack because <tt class="docutils literal">react()</tt> clobbers the stack at each call (essentially forcing
a tail-call). So for example the following program does not stack overflow:</p>
<script src="https://gist.github.com/ellbur/5682993.js"></script>Owenhttp://www.blogger.com/profile/09697040246092989242noreply@blogger.com0tag:blogger.com,1999:blog-696719307153090038.post-70866631211612322582013-05-29T01:21:00.000-04:002013-05-29T01:21:55.524-04:00Cooperation<style type="text/css">
/*
:Author: David Goodger (goodger@python.org)
:Id: $Id$
:Copyright: This stylesheet has been placed in the public domain.
Default cascading style sheet for the HTML output of Docutils.
See http://docutils.sf.net/docs/howto/html-stylesheets.html for how to
customize this style sheet.
*/
/* used to remove borders from tables and images */
.borderless, table.borderless td, table.borderless th {
border: 0 }
table.borderless td, table.borderless th {
/* Override padding for "table.docutils td" with "! important".
The right padding separates the table cells. */
padding: 0 0.5em 0 0 ! important }
.first {
/* Override more specific margin styles with "! important". */
margin-top: 0 ! important }
.last, .with-subtitle {
margin-bottom: 0 ! important }
.hidden {
display: none }
a.toc-backref {
text-decoration: none ;
color: black }
blockquote.epigraph {
margin: 2em 5em ; }
dl.docutils dd {
margin-bottom: 0.5em }
object[type="image/svg+xml"], object[type="application/x-shockwave-flash"] {
overflow: hidden;
}
/* Uncomment (and remove this text!) to get bold-faced definition list terms
dl.docutils dt {
font-weight: bold }
*/
div.abstract {
margin: 2em 5em }
div.abstract p.topic-title {
font-weight: bold ;
text-align: center }
div.admonition, div.attention, div.caution, div.danger, div.error,
div.hint, div.important, div.note, div.tip, div.warning {
margin: 2em ;
border: medium outset ;
padding: 1em }
div.admonition p.admonition-title, div.hint p.admonition-title,
div.important p.admonition-title, div.note p.admonition-title,
div.tip p.admonition-title {
font-weight: bold ;
font-family: sans-serif }
div.attention p.admonition-title, div.caution p.admonition-title,
div.danger p.admonition-title, div.error p.admonition-title,
div.warning p.admonition-title {
color: red ;
font-weight: bold ;
font-family: sans-serif }
/* Uncomment (and remove this text!) to get reduced vertical space in
compound paragraphs.
div.compound .compound-first, div.compound .compound-middle {
margin-bottom: 0.5em }
div.compound .compound-last, div.compound .compound-middle {
margin-top: 0.5em }
*/
div.dedication {
margin: 2em 5em ;
text-align: center ;
font-style: italic }
div.dedication p.topic-title {
font-weight: bold ;
font-style: normal }
div.figure {
margin-left: 2em ;
margin-right: 2em }
div.footer, div.header {
clear: both;
font-size: smaller }
div.line-block {
display: block ;
margin-top: 1em ;
margin-bottom: 1em }
div.line-block div.line-block {
margin-top: 0 ;
margin-bottom: 0 ;
margin-left: 1.5em }
div.sidebar {
margin: 0 0 0.5em 1em ;
border: medium outset ;
padding: 1em ;
background-color: #ffffee ;
width: 40% ;
float: right ;
clear: right }
div.sidebar p.rubric {
font-family: sans-serif ;
font-size: medium }
div.system-messages {
margin: 5em }
div.system-messages h1 {
color: red }
div.system-message {
border: medium outset ;
padding: 1em }
div.system-message p.system-message-title {
color: red ;
font-weight: bold }
div.topic {
margin: 2em }
h1.section-subtitle, h2.section-subtitle, h3.section-subtitle,
h4.section-subtitle, h5.section-subtitle, h6.section-subtitle {
margin-top: 0.4em }
h1.title {
text-align: center }
h2.subtitle {
text-align: center }
hr.docutils {
width: 75% }
img.align-left, .figure.align-left, object.align-left {
clear: left ;
float: left ;
margin-right: 1em }
img.align-right, .figure.align-right, object.align-right {
clear: right ;
float: right ;
margin-left: 1em }
img.align-center, .figure.align-center, object.align-center {
display: block;
margin-left: auto;
margin-right: auto;
}
.align-left {
text-align: left }
.align-center {
clear: both ;
text-align: center }
.align-right {
text-align: right }
/* reset inner alignment in figures */
div.align-right {
text-align: inherit }
/* div.align-center * { */
/* text-align: left } */
ol.simple, ul.simple {
margin-bottom: 1em }
ol.arabic {
list-style: decimal }
ol.loweralpha {
list-style: lower-alpha }
ol.upperalpha {
list-style: upper-alpha }
ol.lowerroman {
list-style: lower-roman }
ol.upperroman {
list-style: upper-roman }
p.attribution {
text-align: right ;
margin-left: 50% }
p.caption {
font-style: italic }
p.credits {
font-style: italic ;
font-size: smaller }
p.label {
white-space: nowrap }
p.rubric {
font-weight: bold ;
font-size: larger ;
color: maroon ;
text-align: center }
p.sidebar-title {
font-family: sans-serif ;
font-weight: bold ;
font-size: larger }
p.sidebar-subtitle {
font-family: sans-serif ;
font-weight: bold }
p.topic-title {
font-weight: bold }
pre.address {
margin-bottom: 0 ;
margin-top: 0 ;
font: inherit }
pre.literal-block, pre.doctest-block, pre.math {
margin-left: 2em ;
margin-right: 2em }
span.classifier {
font-family: sans-serif ;
font-style: oblique }
span.classifier-delimiter {
font-family: sans-serif ;
font-weight: bold }
span.interpreted {
font-family: sans-serif }
span.option {
white-space: nowrap }
span.pre {
white-space: pre }
span.problematic {
color: red }
span.section-subtitle {
/* font-size relative to parent (h1..h6 element) */
font-size: 80% }
table.citation {
border-left: solid 1px gray;
margin-left: 1px }
table.docinfo {
margin: 2em 4em }
table.docutils {
margin-top: 0.5em ;
margin-bottom: 0.5em }
table.footnote {
border-left: solid 1px black;
margin-left: 1px }
table.docutils td, table.docutils th,
table.docinfo td, table.docinfo th {
padding-left: 0.5em ;
padding-right: 0.5em ;
vertical-align: top }
table.docutils th.field-name, table.docinfo th.docinfo-name {
font-weight: bold ;
text-align: left ;
white-space: nowrap ;
padding-left: 0 }
h1 tt.docutils, h2 tt.docutils, h3 tt.docutils,
h4 tt.docutils, h5 tt.docutils, h6 tt.docutils {
font-size: 100% }
ul.auto-toc {
list-style-type: none }
</style>
<style type="text/css">
.file-header {
color: #999;
font-weight: bold;
}
.run-output {
white-space: pre;
font-family: monospace;
background-color: #fff;
border: 1px solid #eee;
margin: 10px 0px 0px 0px;
padding: 5px 10px 5px 10px;
}
.code {
white-space: pre;
font-family: monospace;
background-color: #dec;
border: none;
border-radius: 10px;
padding: 10px 10px 5px 3px;
margin: 5px 0px 0px 0px;
margin-left: 0px;
margin-right: 0px;
}
pre.literal-block {
margin: 5px 0px 0px 0px;
}
.code p {
padding: 0px 0px 0px 0px;
margin: 0px 0px 0px 0px;
overflow: visible;
}
.run-output p {
padding: 0px 0px 0px 0px;
margin: 0px 0px 0px 0px;
overflow: visible;
}
.interactive-input {
white-space: pre;
font-family: monospace;
}
.interactive-output {
white-space: pre;
font-family: monospace;
}
.interactive-session {
background-color: #fff;
border: 1px solid #eee;
margin: 10px 0px 0px 0px;
padding: 0px 0px 0px 5px;
overflow: visible;
}
.c { color: #408080; font-style: italic } /* Comment */
.err { border: 1px solid #FF0000 } /* Error */
.k { color: #008000; font-weight: bold } /* Keyword */
.o { color: #4444ee } /* Operator */
.cm { color: #408080; font-style: italic } /* Comment.Multiline */
.cp { color: #BC7A00 } /* Comment.Preproc */
.c1 { color: #408080; font-style: italic } /* Comment.Single */
.cs { color: #408080; font-style: italic } /* Comment.Special */
.gd { color: #A00000 } /* Generic.Deleted */
.ge { font-style: italic } /* Generic.Emph */
.gr { color: #FF0000 } /* Generic.Error */
.gh { color: #000080; font-weight: bold } /* Generic.Heading */
.gi { color: #00A000 } /* Generic.Inserted */
.go { color: #808080 } /* Generic.Output */
.gp { color: #000080; font-weight: bold } /* Generic.Prompt */
.gs { font-weight: bold } /* Generic.Strong */
.gu { color: #800080; font-weight: bold } /* Generic.Subheading */
.gt { color: #0040D0 } /* Generic.Traceback */
.kc { color: #008000; font-weight: bold } /* Keyword.Constant */
.kd { color: #008000; font-weight: bold } /* Keyword.Declaration */
.kn { color: #008000; font-weight: bold } /* Keyword.Namespace */
.kp { color: #008000 } /* Keyword.Pseudo */
.kr { color: #008000; font-weight: bold } /* Keyword.Reserved */
.kt { color: #B00040 } /* Keyword.Type */
.m { color: #666666 } /* Literal.Number */
.s { color: #BA2121 } /* Literal.String */
.na { color: #7D9029 } /* Name.Attribute */
.nb { color: #008000 } /* Name.Builtin */
.nc { color: #0000FF; font-weight: bold } /* Name.Class */
.no { color: #880000 } /* Name.Constant */
.nd { color: #AA22FF } /* Name.Decorator */
.ni { color: #999999; font-weight: bold } /* Name.Entity */
.ne { color: #D2413A; font-weight: bold } /* Name.Exception */
.nf { color: #0000FF } /* Name.Function */
.nl { color: #A0A000 } /* Name.Label */
.nn { color: #0000FF; font-weight: bold } /* Name.Namespace */
.nt { color: #008000; font-weight: bold } /* Name.Tag */
.nv { color: #19177C } /* Name.Variable */
.ow { color: #AA22FF; font-weight: bold } /* Operator.Word */
.p { color: #11aa11 } /* Parenthesis */
.w { color: #bbbbbb } /* Text.Whitespace */
.mf { color: #666666 } /* Literal.Number.Float */
.mh { color: #666666 } /* Literal.Number.Hex */
.mi { color: #666666 } /* Literal.Number.Integer */
.mo { color: #666666 } /* Literal.Number.Oct */
.sb { color: #BA2121 } /* Literal.String.Backtick */
.sc { color: #BA2121 } /* Literal.String.Char */
.sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */
.s2 { color: #BA2121 } /* Literal.String.Double */
.se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */
.sh { color: #BA2121 } /* Literal.String.Heredoc */
.si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */
.sx { color: #008000 } /* Literal.String.Other */
.sr { color: #BB6688 } /* Literal.String.Regex */
.s1 { color: #BA2121 } /* Literal.String.Single */
.ss { color: #19177C } /* Literal.String.Symbol */
.bp { color: #008000 } /* Name.Builtin.Pseudo */
.vc { color: #19177C } /* Name.Variable.Class */
.vg { color: #19177C } /* Name.Variable.Global */
.vi { color: #19177C } /* Name.Variable.Instance */
.il { color: #666666 } /* Literal.Number.Integer.Long */
.lineno { color: #bbb }
.run-output-weaver {
white-space: normal;
font-family: default;
background-color: ;
border: 3px solid #eee;
margin: 10px 0px 0px 0px;
padding: 5px 10px 5px 10px;
}
.code-weaver {
border: 3px solid #efe;
}
</style><p>Things I have learned about cooperation:</p>
<ul class="simple">
<li>If you tell IntelliJ to add Maven support to a Scala project, it will reorganize your *.scala sources and rename them to *.java sources.</li>
<li>If I run XP in a VM, it will alert me when my battery goes low, and its solution is to hibernate itself.</li>
<li>If I keep back the (since removed) GHDL package to run my VHDL tests, I must keep back gcc in turn preventing me from compiling drivers for the kernel I have installed.</li>
<li>If you tell IE running under wine to make itself your default browser, it will do so, even if it can't fully start without crashing, and become your default PNG viewer.</li>
</ul>
<p>I think this is a good world.</p>
Owenhttp://www.blogger.com/profile/09697040246092989242noreply@blogger.com0tag:blogger.com,1999:blog-696719307153090038.post-69697160755708912352013-05-28T02:57:00.001-04:002013-05-28T02:57:25.582-04:00Pushing and pulling<style type="text/css">
/*
:Author: David Goodger (goodger@python.org)
:Id: $Id$
:Copyright: This stylesheet has been placed in the public domain.
Default cascading style sheet for the HTML output of Docutils.
See http://docutils.sf.net/docs/howto/html-stylesheets.html for how to
customize this style sheet.
*/
/* used to remove borders from tables and images */
.borderless, table.borderless td, table.borderless th {
border: 0 }
table.borderless td, table.borderless th {
/* Override padding for "table.docutils td" with "! important".
The right padding separates the table cells. */
padding: 0 0.5em 0 0 ! important }
.first {
/* Override more specific margin styles with "! important". */
margin-top: 0 ! important }
.last, .with-subtitle {
margin-bottom: 0 ! important }
.hidden {
display: none }
a.toc-backref {
text-decoration: none ;
color: black }
blockquote.epigraph {
margin: 2em 5em ; }
dl.docutils dd {
margin-bottom: 0.5em }
object[type="image/svg+xml"], object[type="application/x-shockwave-flash"] {
overflow: hidden;
}
/* Uncomment (and remove this text!) to get bold-faced definition list terms
dl.docutils dt {
font-weight: bold }
*/
div.abstract {
margin: 2em 5em }
div.abstract p.topic-title {
font-weight: bold ;
text-align: center }
div.admonition, div.attention, div.caution, div.danger, div.error,
div.hint, div.important, div.note, div.tip, div.warning {
margin: 2em ;
border: medium outset ;
padding: 1em }
div.admonition p.admonition-title, div.hint p.admonition-title,
div.important p.admonition-title, div.note p.admonition-title,
div.tip p.admonition-title {
font-weight: bold ;
font-family: sans-serif }
div.attention p.admonition-title, div.caution p.admonition-title,
div.danger p.admonition-title, div.error p.admonition-title,
div.warning p.admonition-title {
color: red ;
font-weight: bold ;
font-family: sans-serif }
/* Uncomment (and remove this text!) to get reduced vertical space in
compound paragraphs.
div.compound .compound-first, div.compound .compound-middle {
margin-bottom: 0.5em }
div.compound .compound-last, div.compound .compound-middle {
margin-top: 0.5em }
*/
div.dedication {
margin: 2em 5em ;
text-align: center ;
font-style: italic }
div.dedication p.topic-title {
font-weight: bold ;
font-style: normal }
div.figure {
margin-left: 2em ;
margin-right: 2em }
div.footer, div.header {
clear: both;
font-size: smaller }
div.line-block {
display: block ;
margin-top: 1em ;
margin-bottom: 1em }
div.line-block div.line-block {
margin-top: 0 ;
margin-bottom: 0 ;
margin-left: 1.5em }
div.sidebar {
margin: 0 0 0.5em 1em ;
border: medium outset ;
padding: 1em ;
background-color: #ffffee ;
width: 40% ;
float: right ;
clear: right }
div.sidebar p.rubric {
font-family: sans-serif ;
font-size: medium }
div.system-messages {
margin: 5em }
div.system-messages h1 {
color: red }
div.system-message {
border: medium outset ;
padding: 1em }
div.system-message p.system-message-title {
color: red ;
font-weight: bold }
div.topic {
margin: 2em }
h1.section-subtitle, h2.section-subtitle, h3.section-subtitle,
h4.section-subtitle, h5.section-subtitle, h6.section-subtitle {
margin-top: 0.4em }
h1.title {
text-align: center }
h2.subtitle {
text-align: center }
hr.docutils {
width: 75% }
img.align-left, .figure.align-left, object.align-left {
clear: left ;
float: left ;
margin-right: 1em }
img.align-right, .figure.align-right, object.align-right {
clear: right ;
float: right ;
margin-left: 1em }
img.align-center, .figure.align-center, object.align-center {
display: block;
margin-left: auto;
margin-right: auto;
}
.align-left {
text-align: left }
.align-center {
clear: both ;
text-align: center }
.align-right {
text-align: right }
/* reset inner alignment in figures */
div.align-right {
text-align: inherit }
/* div.align-center * { */
/* text-align: left } */
ol.simple, ul.simple {
margin-bottom: 1em }
ol.arabic {
list-style: decimal }
ol.loweralpha {
list-style: lower-alpha }
ol.upperalpha {
list-style: upper-alpha }
ol.lowerroman {
list-style: lower-roman }
ol.upperroman {
list-style: upper-roman }
p.attribution {
text-align: right ;
margin-left: 50% }
p.caption {
font-style: italic }
p.credits {
font-style: italic ;
font-size: smaller }
p.label {
white-space: nowrap }
p.rubric {
font-weight: bold ;
font-size: larger ;
color: maroon ;
text-align: center }
p.sidebar-title {
font-family: sans-serif ;
font-weight: bold ;
font-size: larger }
p.sidebar-subtitle {
font-family: sans-serif ;
font-weight: bold }
p.topic-title {
font-weight: bold }
pre.address {
margin-bottom: 0 ;
margin-top: 0 ;
font: inherit }
pre.literal-block, pre.doctest-block, pre.math {
margin-left: 2em ;
margin-right: 2em }
span.classifier {
font-family: sans-serif ;
font-style: oblique }
span.classifier-delimiter {
font-family: sans-serif ;
font-weight: bold }
span.interpreted {
font-family: sans-serif }
span.option {
white-space: nowrap }
span.pre {
white-space: pre }
span.problematic {
color: red }
span.section-subtitle {
/* font-size relative to parent (h1..h6 element) */
font-size: 80% }
table.citation {
border-left: solid 1px gray;
margin-left: 1px }
table.docinfo {
margin: 2em 4em }
table.docutils {
margin-top: 0.5em ;
margin-bottom: 0.5em }
table.footnote {
border-left: solid 1px black;
margin-left: 1px }
table.docutils td, table.docutils th,
table.docinfo td, table.docinfo th {
padding-left: 0.5em ;
padding-right: 0.5em ;
vertical-align: top }
table.docutils th.field-name, table.docinfo th.docinfo-name {
font-weight: bold ;
text-align: left ;
white-space: nowrap ;
padding-left: 0 }
h1 tt.docutils, h2 tt.docutils, h3 tt.docutils,
h4 tt.docutils, h5 tt.docutils, h6 tt.docutils {
font-size: 100% }
ul.auto-toc {
list-style-type: none }
</style>
<style type="text/css">
.file-header {
color: #999;
font-weight: bold;
}
.run-output {
white-space: pre;
font-family: monospace;
background-color: #fff;
border: 1px solid #eee;
margin: 10px 0px 0px 0px;
padding: 5px 10px 5px 10px;
}
.code {
white-space: pre;
font-family: monospace;
background-color: #dec;
border: none;
border-radius: 10px;
padding: 10px 10px 5px 3px;
margin: 5px 0px 0px 0px;
margin-left: 0px;
margin-right: 0px;
}
pre.literal-block {
margin: 5px 0px 0px 0px;
}
.code p {
padding: 0px 0px 0px 0px;
margin: 0px 0px 0px 0px;
overflow: visible;
}
.run-output p {
padding: 0px 0px 0px 0px;
margin: 0px 0px 0px 0px;
overflow: visible;
}
.interactive-input {
white-space: pre;
font-family: monospace;
}
.interactive-output {
white-space: pre;
font-family: monospace;
}
.interactive-session {
background-color: #fff;
border: 1px solid #eee;
margin: 10px 0px 0px 0px;
padding: 0px 0px 0px 5px;
overflow: visible;
}
.c { color: #408080; font-style: italic } /* Comment */
.err { border: 1px solid #FF0000 } /* Error */
.k { color: #008000; font-weight: bold } /* Keyword */
.o { color: #4444ee } /* Operator */
.cm { color: #408080; font-style: italic } /* Comment.Multiline */
.cp { color: #BC7A00 } /* Comment.Preproc */
.c1 { color: #408080; font-style: italic } /* Comment.Single */
.cs { color: #408080; font-style: italic } /* Comment.Special */
.gd { color: #A00000 } /* Generic.Deleted */
.ge { font-style: italic } /* Generic.Emph */
.gr { color: #FF0000 } /* Generic.Error */
.gh { color: #000080; font-weight: bold } /* Generic.Heading */
.gi { color: #00A000 } /* Generic.Inserted */
.go { color: #808080 } /* Generic.Output */
.gp { color: #000080; font-weight: bold } /* Generic.Prompt */
.gs { font-weight: bold } /* Generic.Strong */
.gu { color: #800080; font-weight: bold } /* Generic.Subheading */
.gt { color: #0040D0 } /* Generic.Traceback */
.kc { color: #008000; font-weight: bold } /* Keyword.Constant */
.kd { color: #008000; font-weight: bold } /* Keyword.Declaration */
.kn { color: #008000; font-weight: bold } /* Keyword.Namespace */
.kp { color: #008000 } /* Keyword.Pseudo */
.kr { color: #008000; font-weight: bold } /* Keyword.Reserved */
.kt { color: #B00040 } /* Keyword.Type */
.m { color: #666666 } /* Literal.Number */
.s { color: #BA2121 } /* Literal.String */
.na { color: #7D9029 } /* Name.Attribute */
.nb { color: #008000 } /* Name.Builtin */
.nc { color: #0000FF; font-weight: bold } /* Name.Class */
.no { color: #880000 } /* Name.Constant */
.nd { color: #AA22FF } /* Name.Decorator */
.ni { color: #999999; font-weight: bold } /* Name.Entity */
.ne { color: #D2413A; font-weight: bold } /* Name.Exception */
.nf { color: #0000FF } /* Name.Function */
.nl { color: #A0A000 } /* Name.Label */
.nn { color: #0000FF; font-weight: bold } /* Name.Namespace */
.nt { color: #008000; font-weight: bold } /* Name.Tag */
.nv { color: #19177C } /* Name.Variable */
.ow { color: #AA22FF; font-weight: bold } /* Operator.Word */
.p { color: #11aa11 } /* Parenthesis */
.w { color: #bbbbbb } /* Text.Whitespace */
.mf { color: #666666 } /* Literal.Number.Float */
.mh { color: #666666 } /* Literal.Number.Hex */
.mi { color: #666666 } /* Literal.Number.Integer */
.mo { color: #666666 } /* Literal.Number.Oct */
.sb { color: #BA2121 } /* Literal.String.Backtick */
.sc { color: #BA2121 } /* Literal.String.Char */
.sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */
.s2 { color: #BA2121 } /* Literal.String.Double */
.se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */
.sh { color: #BA2121 } /* Literal.String.Heredoc */
.si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */
.sx { color: #008000 } /* Literal.String.Other */
.sr { color: #BB6688 } /* Literal.String.Regex */
.s1 { color: #BA2121 } /* Literal.String.Single */
.ss { color: #19177C } /* Literal.String.Symbol */
.bp { color: #008000 } /* Name.Builtin.Pseudo */
.vc { color: #19177C } /* Name.Variable.Class */
.vg { color: #19177C } /* Name.Variable.Global */
.vi { color: #19177C } /* Name.Variable.Instance */
.il { color: #666666 } /* Literal.Number.Integer.Long */
.lineno { color: #bbb }
.run-output-weaver {
white-space: normal;
font-family: default;
background-color: ;
border: 3px solid #eee;
margin: 10px 0px 0px 0px;
padding: 5px 10px 5px 10px;
}
.code-weaver {
border: 3px solid #efe;
}
</style><!-- Pulling and pushing -->
<p>I'm mystified. The following definition of a program is efficient to execute:</p>
<pre class="literal-block">
sealed trait Program[A]
case class Result[A](x: A) extends Program[A]
case class NeedsInput[A](f: String => Program[A]) extends Program[A]
</pre>
<p>and in fact has a not bad definition of <tt class="docutils literal">order()</tt>:</p>
<pre class="literal-block">
def order[A1,A2](p1: Program[A1], p2: Program[A2]):
Program[Either[(A1,Program[A2]),(A2,Program[A1])]] =
p1 match {
case Result(x) => Result(Left(x, p2))
case NeedsInput(f) => p2 match {
case Result(x) => Result(Right(x, p1))
case NeedsInput(g) =>
NeedsInput { s =>
order(f(s), g(s))
}
}
}
</pre>
<p>but if you define <tt class="docutils literal">map</tt>, <tt class="docutils literal">flatMap</tt>, etc these turn out to be ineffecient (left as an exercise to the
reader).</p>
<p>Programs represented in "pull style" (the preceding are essentially "push style") are not so efficient to execute (in the obvious way):</p>
<pre class="literal-block">
sealed trait Event[A]
case class Instantly[A](x: A) extends Event[A]
case object Input extends Event[String]
case class Computation[A,B](ev: Event[A], f: A => B) extends Event[B]
case class Chaining[A](ev: Event[Event[A]]) extends Event[A]
case class Ordering[A1,A2](ev1: Event[A1], ev2: Event[A2]) extends Event[Either[(A1,Event[A2]),(A2,Event[A1])]]
</pre>
<p>Wouldn't I love to be able to define</p>
<pre class="literal-block">
def compile[A](ev: Event[A], cc: ): Program[A] = ???
</pre>
<p>but I haven't thought how to do that.</p>
<p>What gives? Why is it so hard to achieve both the memory managing benefits of pull programs and the lack of wasted computation of push programs?</p>
<p>This is still puzzling me.</p>
Owenhttp://www.blogger.com/profile/09697040246092989242noreply@blogger.com0tag:blogger.com,1999:blog-696719307153090038.post-17932717000619775112013-05-27T01:38:00.000-04:002013-05-27T01:38:13.489-04:00Redo-style signals<style type="text/css">
/*
:Author: David Goodger (goodger@python.org)
:Id: $Id$
:Copyright: This stylesheet has been placed in the public domain.
Default cascading style sheet for the HTML output of Docutils.
See http://docutils.sf.net/docs/howto/html-stylesheets.html for how to
customize this style sheet.
*/
/* used to remove borders from tables and images */
.borderless, table.borderless td, table.borderless th {
border: 0 }
table.borderless td, table.borderless th {
/* Override padding for "table.docutils td" with "! important".
The right padding separates the table cells. */
padding: 0 0.5em 0 0 ! important }
.first {
/* Override more specific margin styles with "! important". */
margin-top: 0 ! important }
.last, .with-subtitle {
margin-bottom: 0 ! important }
.hidden {
display: none }
a.toc-backref {
text-decoration: none ;
color: black }
blockquote.epigraph {
margin: 2em 5em ; }
dl.docutils dd {
margin-bottom: 0.5em }
object[type="image/svg+xml"], object[type="application/x-shockwave-flash"] {
overflow: hidden;
}
/* Uncomment (and remove this text!) to get bold-faced definition list terms
dl.docutils dt {
font-weight: bold }
*/
div.abstract {
margin: 2em 5em }
div.abstract p.topic-title {
font-weight: bold ;
text-align: center }
div.admonition, div.attention, div.caution, div.danger, div.error,
div.hint, div.important, div.note, div.tip, div.warning {
margin: 2em ;
border: medium outset ;
padding: 1em }
div.admonition p.admonition-title, div.hint p.admonition-title,
div.important p.admonition-title, div.note p.admonition-title,
div.tip p.admonition-title {
font-weight: bold ;
font-family: sans-serif }
div.attention p.admonition-title, div.caution p.admonition-title,
div.danger p.admonition-title, div.error p.admonition-title,
div.warning p.admonition-title {
color: red ;
font-weight: bold ;
font-family: sans-serif }
/* Uncomment (and remove this text!) to get reduced vertical space in
compound paragraphs.
div.compound .compound-first, div.compound .compound-middle {
margin-bottom: 0.5em }
div.compound .compound-last, div.compound .compound-middle {
margin-top: 0.5em }
*/
div.dedication {
margin: 2em 5em ;
text-align: center ;
font-style: italic }
div.dedication p.topic-title {
font-weight: bold ;
font-style: normal }
div.figure {
margin-left: 2em ;
margin-right: 2em }
div.footer, div.header {
clear: both;
font-size: smaller }
div.line-block {
display: block ;
margin-top: 1em ;
margin-bottom: 1em }
div.line-block div.line-block {
margin-top: 0 ;
margin-bottom: 0 ;
margin-left: 1.5em }
div.sidebar {
margin: 0 0 0.5em 1em ;
border: medium outset ;
padding: 1em ;
background-color: #ffffee ;
width: 40% ;
float: right ;
clear: right }
div.sidebar p.rubric {
font-family: sans-serif ;
font-size: medium }
div.system-messages {
margin: 5em }
div.system-messages h1 {
color: red }
div.system-message {
border: medium outset ;
padding: 1em }
div.system-message p.system-message-title {
color: red ;
font-weight: bold }
div.topic {
margin: 2em }
h1.section-subtitle, h2.section-subtitle, h3.section-subtitle,
h4.section-subtitle, h5.section-subtitle, h6.section-subtitle {
margin-top: 0.4em }
h1.title {
text-align: center }
h2.subtitle {
text-align: center }
hr.docutils {
width: 75% }
img.align-left, .figure.align-left, object.align-left {
clear: left ;
float: left ;
margin-right: 1em }
img.align-right, .figure.align-right, object.align-right {
clear: right ;
float: right ;
margin-left: 1em }
img.align-center, .figure.align-center, object.align-center {
display: block;
margin-left: auto;
margin-right: auto;
}
.align-left {
text-align: left }
.align-center {
clear: both ;
text-align: center }
.align-right {
text-align: right }
/* reset inner alignment in figures */
div.align-right {
text-align: inherit }
/* div.align-center * { */
/* text-align: left } */
ol.simple, ul.simple {
margin-bottom: 1em }
ol.arabic {
list-style: decimal }
ol.loweralpha {
list-style: lower-alpha }
ol.upperalpha {
list-style: upper-alpha }
ol.lowerroman {
list-style: lower-roman }
ol.upperroman {
list-style: upper-roman }
p.attribution {
text-align: right ;
margin-left: 50% }
p.caption {
font-style: italic }
p.credits {
font-style: italic ;
font-size: smaller }
p.label {
white-space: nowrap }
p.rubric {
font-weight: bold ;
font-size: larger ;
color: maroon ;
text-align: center }
p.sidebar-title {
font-family: sans-serif ;
font-weight: bold ;
font-size: larger }
p.sidebar-subtitle {
font-family: sans-serif ;
font-weight: bold }
p.topic-title {
font-weight: bold }
pre.address {
margin-bottom: 0 ;
margin-top: 0 ;
font: inherit }
pre.literal-block, pre.doctest-block, pre.math {
margin-left: 2em ;
margin-right: 2em }
span.classifier {
font-family: sans-serif ;
font-style: oblique }
span.classifier-delimiter {
font-family: sans-serif ;
font-weight: bold }
span.interpreted {
font-family: sans-serif }
span.option {
white-space: nowrap }
span.pre {
white-space: pre }
span.problematic {
color: red }
span.section-subtitle {
/* font-size relative to parent (h1..h6 element) */
font-size: 80% }
table.citation {
border-left: solid 1px gray;
margin-left: 1px }
table.docinfo {
margin: 2em 4em }
table.docutils {
margin-top: 0.5em ;
margin-bottom: 0.5em }
table.footnote {
border-left: solid 1px black;
margin-left: 1px }
table.docutils td, table.docutils th,
table.docinfo td, table.docinfo th {
padding-left: 0.5em ;
padding-right: 0.5em ;
vertical-align: top }
table.docutils th.field-name, table.docinfo th.docinfo-name {
font-weight: bold ;
text-align: left ;
white-space: nowrap ;
padding-left: 0 }
h1 tt.docutils, h2 tt.docutils, h3 tt.docutils,
h4 tt.docutils, h5 tt.docutils, h6 tt.docutils {
font-size: 100% }
ul.auto-toc {
list-style-type: none }
</style>
<style type="text/css">
.file-header {
color: #999;
font-weight: bold;
}
.run-output {
white-space: pre;
font-family: monospace;
background-color: #fff;
border: 1px solid #eee;
margin: 10px 0px 0px 0px;
padding: 5px 10px 5px 10px;
}
.code {
white-space: pre;
font-family: monospace;
background-color: #dec;
border: none;
border-radius: 10px;
padding: 10px 10px 5px 3px;
margin: 5px 0px 0px 0px;
margin-left: 0px;
margin-right: 0px;
}
pre.literal-block {
margin: 5px 0px 0px 0px;
}
.code p {
padding: 0px 0px 0px 0px;
margin: 0px 0px 0px 0px;
overflow: visible;
}
.run-output p {
padding: 0px 0px 0px 0px;
margin: 0px 0px 0px 0px;
overflow: visible;
}
.interactive-input {
white-space: pre;
font-family: monospace;
}
.interactive-output {
white-space: pre;
font-family: monospace;
}
.interactive-session {
background-color: #fff;
border: 1px solid #eee;
margin: 10px 0px 0px 0px;
padding: 0px 0px 0px 5px;
overflow: visible;
}
.c { color: #408080; font-style: italic } /* Comment */
.err { border: 1px solid #FF0000 } /* Error */
.k { color: #008000; font-weight: bold } /* Keyword */
.o { color: #4444ee } /* Operator */
.cm { color: #408080; font-style: italic } /* Comment.Multiline */
.cp { color: #BC7A00 } /* Comment.Preproc */
.c1 { color: #408080; font-style: italic } /* Comment.Single */
.cs { color: #408080; font-style: italic } /* Comment.Special */
.gd { color: #A00000 } /* Generic.Deleted */
.ge { font-style: italic } /* Generic.Emph */
.gr { color: #FF0000 } /* Generic.Error */
.gh { color: #000080; font-weight: bold } /* Generic.Heading */
.gi { color: #00A000 } /* Generic.Inserted */
.go { color: #808080 } /* Generic.Output */
.gp { color: #000080; font-weight: bold } /* Generic.Prompt */
.gs { font-weight: bold } /* Generic.Strong */
.gu { color: #800080; font-weight: bold } /* Generic.Subheading */
.gt { color: #0040D0 } /* Generic.Traceback */
.kc { color: #008000; font-weight: bold } /* Keyword.Constant */
.kd { color: #008000; font-weight: bold } /* Keyword.Declaration */
.kn { color: #008000; font-weight: bold } /* Keyword.Namespace */
.kp { color: #008000 } /* Keyword.Pseudo */
.kr { color: #008000; font-weight: bold } /* Keyword.Reserved */
.kt { color: #B00040 } /* Keyword.Type */
.m { color: #666666 } /* Literal.Number */
.s { color: #BA2121 } /* Literal.String */
.na { color: #7D9029 } /* Name.Attribute */
.nb { color: #008000 } /* Name.Builtin */
.nc { color: #0000FF; font-weight: bold } /* Name.Class */
.no { color: #880000 } /* Name.Constant */
.nd { color: #AA22FF } /* Name.Decorator */
.ni { color: #999999; font-weight: bold } /* Name.Entity */
.ne { color: #D2413A; font-weight: bold } /* Name.Exception */
.nf { color: #0000FF } /* Name.Function */
.nl { color: #A0A000 } /* Name.Label */
.nn { color: #0000FF; font-weight: bold } /* Name.Namespace */
.nt { color: #008000; font-weight: bold } /* Name.Tag */
.nv { color: #19177C } /* Name.Variable */
.ow { color: #AA22FF; font-weight: bold } /* Operator.Word */
.p { color: #11aa11 } /* Parenthesis */
.w { color: #bbbbbb } /* Text.Whitespace */
.mf { color: #666666 } /* Literal.Number.Float */
.mh { color: #666666 } /* Literal.Number.Hex */
.mi { color: #666666 } /* Literal.Number.Integer */
.mo { color: #666666 } /* Literal.Number.Oct */
.sb { color: #BA2121 } /* Literal.String.Backtick */
.sc { color: #BA2121 } /* Literal.String.Char */
.sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */
.s2 { color: #BA2121 } /* Literal.String.Double */
.se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */
.sh { color: #BA2121 } /* Literal.String.Heredoc */
.si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */
.sx { color: #008000 } /* Literal.String.Other */
.sr { color: #BB6688 } /* Literal.String.Regex */
.s1 { color: #BA2121 } /* Literal.String.Single */
.ss { color: #19177C } /* Literal.String.Symbol */
.bp { color: #008000 } /* Name.Builtin.Pseudo */
.vc { color: #19177C } /* Name.Variable.Class */
.vg { color: #19177C } /* Name.Variable.Global */
.vi { color: #19177C } /* Name.Variable.Instance */
.il { color: #666666 } /* Literal.Number.Integer.Long */
.lineno { color: #bbb }
.run-output-weaver {
white-space: normal;
font-family: default;
background-color: ;
border: 3px solid #eee;
margin: 10px 0px 0px 0px;
padding: 5px 10px 5px 10px;
}
.code-weaver {
border: 3px solid #efe;
}
</style><!-- Redo-style signals -->
<p>Let's say I have signals <tt class="docutils literal">a</tt>, <tt class="docutils literal">b</tt>, <tt class="docutils literal">c</tt>, <tt class="docutils literal">d</tt> with dependencies</p>
<pre class="literal-block">
Inputs ~> a ~> b ~> c ~> d ~> Real World
</pre>
<p>The signal '<tt class="docutils literal">a</tt>' occasionally changes (due to inputs), which in turn changes the valid values of '<tt class="docutils literal">b</tt>', '<tt class="docutils literal">c</tt>' and '<tt class="docutils literal">d</tt>'. The value of '<tt class="docutils literal">d</tt>' is occasionally read and used to update some real-world object that the user can see. Maybe '<tt class="docutils literal">a</tt>' is set more often than '<tt class="docutils literal">d</tt>' is read; maybe it's the other way around; we're not sure.</p>
<p>The question is, when should the computations of '<tt class="docutils literal">b</tt>' '<tt class="docutils literal">c</tt>' and '<tt class="docutils literal">d</tt>' be performed? Should it be done in "push style", ie, every time '<tt class="docutils literal">a</tt>' changes, or "pull style", every time '<tt class="docutils literal">d</tt>' is read? In the first case we may waste a lot of computation if '<tt class="docutils literal">a</tt>' is set more frequently than '<tt class="docutils literal">d</tt>' is read. In the second, we do not waste computation, but we require a full check of the dependency tree every time we read '<tt class="docutils literal">d</tt>', just to see if something has changed in the meantime.</p>
<p>Well it turns out that the conceptual solution to this problem was already solved by Avery Pennarun in his program <a class="reference external" href="https://github.com/apenwarr/redo">redo</a>:</p>
<blockquote>
<p>Dependencies are tracked in a persistent .redo database so that redo can check them later. If a file needs to be rebuilt, it re-executes the whatever.do script and regenerates the dependencies. If a file doesn't need to be rebuilt, redo can calculate that just using its persistent .redo database, without re-running the script. And it can do that check just once right at the start of your project build.</p>
<p>redo is based on the following simple insight: you don't actually care what the dependencies are before you build the target; if the target doesn't exist, you obviously need to build it. Then, the build script itself can provide the dependency information however it wants; unlike in make, you don't need a special dependency syntax at all. You can even declare some of your dependencies after building, which makes C-style autodependencies much simpler.</p>
</blockquote>
<p>A signal's value is either up to date or obsolete. When the value is requested, if it is up to date, it returns that value immediately, not checking the dependency tree. If it's obsolete, it does a full recalculation.</p>
<p>Then, when a source value like '<tt class="docutils literal">a</tt>' changes, it simply asks the question: Who is currently relying on the correct value of this signal? In the case of '<tt class="docutils literal">a</tt>', that would be '<tt class="docutils literal">b</tt>', so '<tt class="docutils literal">a</tt>' notifies '<tt class="docutils literal">b</tt>' that the value is now obsolete (but without providing the new value), who notifies '<tt class="docutils literal">c</tt>', who notifies '<tt class="docutils literal">d</tt>'. After that notification chain is sent, no one is relying on the correct value for anything, so the next time '<tt class="docutils literal">a</tt>' changes, nothing happens; no notifications are done.</p>
<p>There is another benefit to this system. Say the dependency tree actually looks like</p>
<pre class="literal-block">
d
/ \
b c
\ /
a
</pre>
<p>With push-style signals, every time '<tt class="docutils literal">a</tt>' changes, '<tt class="docutils literal">d</tt>' gets updated twice, which is wasteful. With pull-style signals, '<tt class="docutils literal">d</tt>', would be updated once, but <tt class="docutils literal">a</tt> would be consulted twice every time <tt class="docutils literal">d</tt> is read. Redo-style signals get the benefit of push-style signals without having to consult the whole tree at each update.</p>
<p><a class="reference external" href="https://github.com/ellbur/redo-signals">Code</a></p>
Owenhttp://www.blogger.com/profile/09697040246092989242noreply@blogger.com1tag:blogger.com,1999:blog-696719307153090038.post-20924885791931267802013-05-06T23:54:00.000-04:002013-05-06T23:54:47.132-04:00Justices Alito and Kennedy on Monads vs Applicatives<style type="text/css">
/*
:Author: David Goodger (goodger@python.org)
:Id: $Id$
:Copyright: This stylesheet has been placed in the public domain.
Default cascading style sheet for the HTML output of Docutils.
See http://docutils.sf.net/docs/howto/html-stylesheets.html for how to
customize this style sheet.
*/
/* used to remove borders from tables and images */
.borderless, table.borderless td, table.borderless th {
border: 0 }
table.borderless td, table.borderless th {
/* Override padding for "table.docutils td" with "! important".
The right padding separates the table cells. */
padding: 0 0.5em 0 0 ! important }
.first {
/* Override more specific margin styles with "! important". */
margin-top: 0 ! important }
.last, .with-subtitle {
margin-bottom: 0 ! important }
.hidden {
display: none }
a.toc-backref {
text-decoration: none ;
color: black }
blockquote.epigraph {
margin: 2em 5em ; }
dl.docutils dd {
margin-bottom: 0.5em }
object[type="image/svg+xml"], object[type="application/x-shockwave-flash"] {
overflow: hidden;
}
/* Uncomment (and remove this text!) to get bold-faced definition list terms
dl.docutils dt {
font-weight: bold }
*/
div.abstract {
margin: 2em 5em }
div.abstract p.topic-title {
font-weight: bold ;
text-align: center }
div.admonition, div.attention, div.caution, div.danger, div.error,
div.hint, div.important, div.note, div.tip, div.warning {
margin: 2em ;
border: medium outset ;
padding: 1em }
div.admonition p.admonition-title, div.hint p.admonition-title,
div.important p.admonition-title, div.note p.admonition-title,
div.tip p.admonition-title {
font-weight: bold ;
font-family: sans-serif }
div.attention p.admonition-title, div.caution p.admonition-title,
div.danger p.admonition-title, div.error p.admonition-title,
div.warning p.admonition-title {
color: red ;
font-weight: bold ;
font-family: sans-serif }
/* Uncomment (and remove this text!) to get reduced vertical space in
compound paragraphs.
div.compound .compound-first, div.compound .compound-middle {
margin-bottom: 0.5em }
div.compound .compound-last, div.compound .compound-middle {
margin-top: 0.5em }
*/
div.dedication {
margin: 2em 5em ;
text-align: center ;
font-style: italic }
div.dedication p.topic-title {
font-weight: bold ;
font-style: normal }
div.figure {
margin-left: 2em ;
margin-right: 2em }
div.footer, div.header {
clear: both;
font-size: smaller }
div.line-block {
display: block ;
margin-top: 1em ;
margin-bottom: 1em }
div.line-block div.line-block {
margin-top: 0 ;
margin-bottom: 0 ;
margin-left: 1.5em }
div.sidebar {
margin: 0 0 0.5em 1em ;
border: medium outset ;
padding: 1em ;
background-color: #ffffee ;
width: 40% ;
float: right ;
clear: right }
div.sidebar p.rubric {
font-family: sans-serif ;
font-size: medium }
div.system-messages {
margin: 5em }
div.system-messages h1 {
color: red }
div.system-message {
border: medium outset ;
padding: 1em }
div.system-message p.system-message-title {
color: red ;
font-weight: bold }
div.topic {
margin: 2em }
h1.section-subtitle, h2.section-subtitle, h3.section-subtitle,
h4.section-subtitle, h5.section-subtitle, h6.section-subtitle {
margin-top: 0.4em }
h1.title {
text-align: center }
h2.subtitle {
text-align: center }
hr.docutils {
width: 75% }
img.align-left, .figure.align-left, object.align-left {
clear: left ;
float: left ;
margin-right: 1em }
img.align-right, .figure.align-right, object.align-right {
clear: right ;
float: right ;
margin-left: 1em }
img.align-center, .figure.align-center, object.align-center {
display: block;
margin-left: auto;
margin-right: auto;
}
.align-left {
text-align: left }
.align-center {
clear: both ;
text-align: center }
.align-right {
text-align: right }
/* reset inner alignment in figures */
div.align-right {
text-align: inherit }
/* div.align-center * { */
/* text-align: left } */
ol.simple, ul.simple {
margin-bottom: 1em }
ol.arabic {
list-style: decimal }
ol.loweralpha {
list-style: lower-alpha }
ol.upperalpha {
list-style: upper-alpha }
ol.lowerroman {
list-style: lower-roman }
ol.upperroman {
list-style: upper-roman }
p.attribution {
text-align: right ;
margin-left: 50% }
p.caption {
font-style: italic }
p.credits {
font-style: italic ;
font-size: smaller }
p.label {
white-space: nowrap }
p.rubric {
font-weight: bold ;
font-size: larger ;
color: maroon ;
text-align: center }
p.sidebar-title {
font-family: sans-serif ;
font-weight: bold ;
font-size: larger }
p.sidebar-subtitle {
font-family: sans-serif ;
font-weight: bold }
p.topic-title {
font-weight: bold }
pre.address {
margin-bottom: 0 ;
margin-top: 0 ;
font: inherit }
pre.literal-block, pre.doctest-block, pre.math {
margin-left: 2em ;
margin-right: 2em }
span.classifier {
font-family: sans-serif ;
font-style: oblique }
span.classifier-delimiter {
font-family: sans-serif ;
font-weight: bold }
span.interpreted {
font-family: sans-serif }
span.option {
white-space: nowrap }
span.pre {
white-space: pre }
span.problematic {
color: red }
span.section-subtitle {
/* font-size relative to parent (h1..h6 element) */
font-size: 80% }
table.citation {
border-left: solid 1px gray;
margin-left: 1px }
table.docinfo {
margin: 2em 4em }
table.docutils {
margin-top: 0.5em ;
margin-bottom: 0.5em }
table.footnote {
border-left: solid 1px black;
margin-left: 1px }
table.docutils td, table.docutils th,
table.docinfo td, table.docinfo th {
padding-left: 0.5em ;
padding-right: 0.5em ;
vertical-align: top }
table.docutils th.field-name, table.docinfo th.docinfo-name {
font-weight: bold ;
text-align: left ;
white-space: nowrap ;
padding-left: 0 }
h1 tt.docutils, h2 tt.docutils, h3 tt.docutils,
h4 tt.docutils, h5 tt.docutils, h6 tt.docutils {
font-size: 100% }
ul.auto-toc {
list-style-type: none }
</style>
<style type="text/css">
.file-header {
color: #999;
font-weight: bold;
}
.run-output {
white-space: pre;
font-family: monospace;
background-color: #fff;
border: 1px solid #eee;
margin: 10px 0px 0px 0px;
padding: 5px 10px 5px 10px;
}
.code {
white-space: pre;
font-family: monospace;
background-color: #dec;
border: none;
border-radius: 10px;
padding: 10px 10px 5px 3px;
margin: 5px 0px 0px 0px;
margin-left: 0px;
margin-right: 0px;
}
pre.literal-block {
margin: 5px 0px 0px 0px;
}
.code p {
padding: 0px 0px 0px 0px;
margin: 0px 0px 0px 0px;
overflow: visible;
}
.run-output p {
padding: 0px 0px 0px 0px;
margin: 0px 0px 0px 0px;
overflow: visible;
}
.interactive-input {
white-space: pre;
font-family: monospace;
}
.interactive-output {
white-space: pre;
font-family: monospace;
}
.interactive-session {
background-color: #fff;
border: 1px solid #eee;
margin: 10px 0px 0px 0px;
padding: 0px 0px 0px 5px;
overflow: visible;
}
.c { color: #408080; font-style: italic } /* Comment */
.err { border: 1px solid #FF0000 } /* Error */
.k { color: #008000; font-weight: bold } /* Keyword */
.o { color: #4444ee } /* Operator */
.cm { color: #408080; font-style: italic } /* Comment.Multiline */
.cp { color: #BC7A00 } /* Comment.Preproc */
.c1 { color: #408080; font-style: italic } /* Comment.Single */
.cs { color: #408080; font-style: italic } /* Comment.Special */
.gd { color: #A00000 } /* Generic.Deleted */
.ge { font-style: italic } /* Generic.Emph */
.gr { color: #FF0000 } /* Generic.Error */
.gh { color: #000080; font-weight: bold } /* Generic.Heading */
.gi { color: #00A000 } /* Generic.Inserted */
.go { color: #808080 } /* Generic.Output */
.gp { color: #000080; font-weight: bold } /* Generic.Prompt */
.gs { font-weight: bold } /* Generic.Strong */
.gu { color: #800080; font-weight: bold } /* Generic.Subheading */
.gt { color: #0040D0 } /* Generic.Traceback */
.kc { color: #008000; font-weight: bold } /* Keyword.Constant */
.kd { color: #008000; font-weight: bold } /* Keyword.Declaration */
.kn { color: #008000; font-weight: bold } /* Keyword.Namespace */
.kp { color: #008000 } /* Keyword.Pseudo */
.kr { color: #008000; font-weight: bold } /* Keyword.Reserved */
.kt { color: #B00040 } /* Keyword.Type */
.m { color: #666666 } /* Literal.Number */
.s { color: #BA2121 } /* Literal.String */
.na { color: #7D9029 } /* Name.Attribute */
.nb { color: #008000 } /* Name.Builtin */
.nc { color: #0000FF; font-weight: bold } /* Name.Class */
.no { color: #880000 } /* Name.Constant */
.nd { color: #AA22FF } /* Name.Decorator */
.ni { color: #999999; font-weight: bold } /* Name.Entity */
.ne { color: #D2413A; font-weight: bold } /* Name.Exception */
.nf { color: #0000FF } /* Name.Function */
.nl { color: #A0A000 } /* Name.Label */
.nn { color: #0000FF; font-weight: bold } /* Name.Namespace */
.nt { color: #008000; font-weight: bold } /* Name.Tag */
.nv { color: #19177C } /* Name.Variable */
.ow { color: #AA22FF; font-weight: bold } /* Operator.Word */
.p { color: #11aa11 } /* Parenthesis */
.w { color: #bbbbbb } /* Text.Whitespace */
.mf { color: #666666 } /* Literal.Number.Float */
.mh { color: #666666 } /* Literal.Number.Hex */
.mi { color: #666666 } /* Literal.Number.Integer */
.mo { color: #666666 } /* Literal.Number.Oct */
.sb { color: #BA2121 } /* Literal.String.Backtick */
.sc { color: #BA2121 } /* Literal.String.Char */
.sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */
.s2 { color: #BA2121 } /* Literal.String.Double */
.se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */
.sh { color: #BA2121 } /* Literal.String.Heredoc */
.si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */
.sx { color: #008000 } /* Literal.String.Other */
.sr { color: #BB6688 } /* Literal.String.Regex */
.s1 { color: #BA2121 } /* Literal.String.Single */
.ss { color: #19177C } /* Literal.String.Symbol */
.bp { color: #008000 } /* Name.Builtin.Pseudo */
.vc { color: #19177C } /* Name.Variable.Class */
.vg { color: #19177C } /* Name.Variable.Global */
.vi { color: #19177C } /* Name.Variable.Instance */
.il { color: #666666 } /* Literal.Number.Integer.Long */
.lineno { color: #bbb }
.run-output-weaver {
white-space: normal;
font-family: default;
background-color: ;
border: 3px solid #eee;
margin: 10px 0px 0px 0px;
padding: 5px 10px 5px 10px;
}
.code-weaver {
border: 3px solid #efe;
}
</style><!-- Justices Alito and Kennedy on Monads vs Applicatives -->
<p>From <a class="reference external" href="http://www.supremecourt.gov/oral_arguments/argument_transcripts/11-9335.pdf">the oral arguments in Alleyne v United States</a> (<a class="reference external" href="http://www.supremecourt.gov/oral_arguments/argument_audio_detail.aspx?argument=11-9335">audio</a>):</p>
<blockquote>
<p>JUSTICE ALITO: Now, if you were defending a case involving drug weight and your client maintained that he or she had nothing to do with these drugs, how would you proceed? Your argument would be: They're not my drugs, but if they were my drugs, they weren't -- they didn't weigh more than one kilo.</p>
<p>MS. MAGUIRE: Well, Justice Alito, those are strategical questions that come up in every trial case that we have. ... But those -- those strategic decisions exist whether or not the Court adopts this rule or doesn't adopt the rule.</p>
<p>...</p>
<p>JUSTICE KENNEDY: But -- but isn't it difficult for you to say he had nothing to do with the drugs, plus the drugs didn't weigh more than a certain amount?</p>
<p>MS. MAGUIRE: I don't believe that that is difficult, and I believe that those are decisions that you make in every case. ...</p>
<p>...</p>
<p>JUSTICE KENNEDY: Well, we're not getting very far with this. But one answer you could say is that, in order to preserve the constitutional right, you want us to have a bifurcated trial. I thought you were -- might say that.</p>
<p>MS. MAGUIRE: No, we are not -- we are not asking for a bifurcated trial. We are just asking that if there's one --</p>
<p>JUSTICE KENNEDY: That's good because that's an extra problem.</p>
</blockquote>
<p>A bifurcated trial is one in which the jury first decides on a subset of questions, then the trial continues, and the jury later decides the remaining questions.</p>
<p>Alito notices that the trial is set to proceed in applicative style, and sees that the defense will be in an awkward position, since they must prove facts about an incident they claim never took place. Kennedy then offers a bid for a monadic trial, where the result of the first verdict can drive the argument leading to the second. But Ms. Maguire resists, for the same reason Kennedy had in mind: in law as in programming, monadic style brings extra costs.</p>
<p>The cost of a bifurcated trial is that you must interrupt the trial, wait for the jury to deliberate, then wait for the lawyers to adapt their strategies to the verdict, wherein either the lawyers have planned for both outcomes (wasting effort) or the trial is delayed further. Analogously, if you have a monadic query library, every use of <tt class="docutils literal">>>=</tt> aka <tt class="docutils literal">flatMap</tt>:</p>
<pre class="literal-block">
val X : Column[Bool]
val Y : Column[Int]
val Z : Column[Int]
X flatMap { x =>
if (x)
Y
else
Z
}
</pre>
<p>requires the preliminary query to complete, return control and data back to the main program, execute some code, make a new query, send it <em>back</em> to the database again, and resume. <em>And</em> the query optimizer doesn't get the benefit of seeing the whole query at once. This is why LINQ is not strictly monadic (and can operate on <em>expressions</em>, not just higher order functions) and all monadic query languages have some really awkward spots where they try to avoid this problem.</p>
<p>The analogy to speculative planning by the lawyers would be speculative execution of the closure <tt class="docutils literal">{ x => <span class="pre">...}</span></tt> by the client environment, which is theoretically possible but I am aware of no software that actually does this.</p>
<p>(In this case it would seem that even if the court holds that the trial should proceed applicatively, Ms Maguire's client gets the benefit of a monadic trial because he started his appeal after the primary verdict had already been reached; but no other defendant to whom the ruling applies will get this accidental benefit. Perhaps this explains why Ms Maguire seems relatively unconcerned by the issue).</p>
Owenhttp://www.blogger.com/profile/09697040246092989242noreply@blogger.com0tag:blogger.com,1999:blog-696719307153090038.post-35673568463550218422013-04-30T22:18:00.000-04:002013-04-30T22:18:10.989-04:00Classical Fictions<style type="text/css">
/*
:Author: David Goodger (goodger@python.org)
:Id: $Id$
:Copyright: This stylesheet has been placed in the public domain.
Default cascading style sheet for the HTML output of Docutils.
See http://docutils.sf.net/docs/howto/html-stylesheets.html for how to
customize this style sheet.
*/
/* used to remove borders from tables and images */
.borderless, table.borderless td, table.borderless th {
border: 0 }
table.borderless td, table.borderless th {
/* Override padding for "table.docutils td" with "! important".
The right padding separates the table cells. */
padding: 0 0.5em 0 0 ! important }
.first {
/* Override more specific margin styles with "! important". */
margin-top: 0 ! important }
.last, .with-subtitle {
margin-bottom: 0 ! important }
.hidden {
display: none }
a.toc-backref {
text-decoration: none ;
color: black }
blockquote.epigraph {
margin: 2em 5em ; }
dl.docutils dd {
margin-bottom: 0.5em }
object[type="image/svg+xml"], object[type="application/x-shockwave-flash"] {
overflow: hidden;
}
/* Uncomment (and remove this text!) to get bold-faced definition list terms
dl.docutils dt {
font-weight: bold }
*/
div.abstract {
margin: 2em 5em }
div.abstract p.topic-title {
font-weight: bold ;
text-align: center }
div.admonition, div.attention, div.caution, div.danger, div.error,
div.hint, div.important, div.note, div.tip, div.warning {
margin: 2em ;
border: medium outset ;
padding: 1em }
div.admonition p.admonition-title, div.hint p.admonition-title,
div.important p.admonition-title, div.note p.admonition-title,
div.tip p.admonition-title {
font-weight: bold ;
font-family: sans-serif }
div.attention p.admonition-title, div.caution p.admonition-title,
div.danger p.admonition-title, div.error p.admonition-title,
div.warning p.admonition-title {
color: red ;
font-weight: bold ;
font-family: sans-serif }
/* Uncomment (and remove this text!) to get reduced vertical space in
compound paragraphs.
div.compound .compound-first, div.compound .compound-middle {
margin-bottom: 0.5em }
div.compound .compound-last, div.compound .compound-middle {
margin-top: 0.5em }
*/
div.dedication {
margin: 2em 5em ;
text-align: center ;
font-style: italic }
div.dedication p.topic-title {
font-weight: bold ;
font-style: normal }
div.figure {
margin-left: 2em ;
margin-right: 2em }
div.footer, div.header {
clear: both;
font-size: smaller }
div.line-block {
display: block ;
margin-top: 1em ;
margin-bottom: 1em }
div.line-block div.line-block {
margin-top: 0 ;
margin-bottom: 0 ;
margin-left: 1.5em }
div.sidebar {
margin: 0 0 0.5em 1em ;
border: medium outset ;
padding: 1em ;
background-color: #ffffee ;
width: 40% ;
float: right ;
clear: right }
div.sidebar p.rubric {
font-family: sans-serif ;
font-size: medium }
div.system-messages {
margin: 5em }
div.system-messages h1 {
color: red }
div.system-message {
border: medium outset ;
padding: 1em }
div.system-message p.system-message-title {
color: red ;
font-weight: bold }
div.topic {
margin: 2em }
h1.section-subtitle, h2.section-subtitle, h3.section-subtitle,
h4.section-subtitle, h5.section-subtitle, h6.section-subtitle {
margin-top: 0.4em }
h1.title {
text-align: center }
h2.subtitle {
text-align: center }
hr.docutils {
width: 75% }
img.align-left, .figure.align-left, object.align-left {
clear: left ;
float: left ;
margin-right: 1em }
img.align-right, .figure.align-right, object.align-right {
clear: right ;
float: right ;
margin-left: 1em }
img.align-center, .figure.align-center, object.align-center {
display: block;
margin-left: auto;
margin-right: auto;
}
.align-left {
text-align: left }
.align-center {
clear: both ;
text-align: center }
.align-right {
text-align: right }
/* reset inner alignment in figures */
div.align-right {
text-align: inherit }
/* div.align-center * { */
/* text-align: left } */
ol.simple, ul.simple {
margin-bottom: 1em }
ol.arabic {
list-style: decimal }
ol.loweralpha {
list-style: lower-alpha }
ol.upperalpha {
list-style: upper-alpha }
ol.lowerroman {
list-style: lower-roman }
ol.upperroman {
list-style: upper-roman }
p.attribution {
text-align: right ;
margin-left: 50% }
p.caption {
font-style: italic }
p.credits {
font-style: italic ;
font-size: smaller }
p.label {
white-space: nowrap }
p.rubric {
font-weight: bold ;
font-size: larger ;
color: maroon ;
text-align: center }
p.sidebar-title {
font-family: sans-serif ;
font-weight: bold ;
font-size: larger }
p.sidebar-subtitle {
font-family: sans-serif ;
font-weight: bold }
p.topic-title {
font-weight: bold }
pre.address {
margin-bottom: 0 ;
margin-top: 0 ;
font: inherit }
pre.literal-block, pre.doctest-block, pre.math {
margin-left: 2em ;
margin-right: 2em }
span.classifier {
font-family: sans-serif ;
font-style: oblique }
span.classifier-delimiter {
font-family: sans-serif ;
font-weight: bold }
span.interpreted {
font-family: sans-serif }
span.option {
white-space: nowrap }
span.pre {
white-space: pre }
span.problematic {
color: red }
span.section-subtitle {
/* font-size relative to parent (h1..h6 element) */
font-size: 80% }
table.citation {
border-left: solid 1px gray;
margin-left: 1px }
table.docinfo {
margin: 2em 4em }
table.docutils {
margin-top: 0.5em ;
margin-bottom: 0.5em }
table.footnote {
border-left: solid 1px black;
margin-left: 1px }
table.docutils td, table.docutils th,
table.docinfo td, table.docinfo th {
padding-left: 0.5em ;
padding-right: 0.5em ;
vertical-align: top }
table.docutils th.field-name, table.docinfo th.docinfo-name {
font-weight: bold ;
text-align: left ;
white-space: nowrap ;
padding-left: 0 }
h1 tt.docutils, h2 tt.docutils, h3 tt.docutils,
h4 tt.docutils, h5 tt.docutils, h6 tt.docutils {
font-size: 100% }
ul.auto-toc {
list-style-type: none }
</style>
<style type="text/css">
.file-header {
color: #999;
font-weight: bold;
}
.run-output {
white-space: pre;
font-family: monospace;
background-color: #fff;
border: 1px solid #eee;
margin: 10px 0px 0px 0px;
padding: 5px 10px 5px 10px;
}
.code {
white-space: pre;
font-family: monospace;
background-color: #dec;
border: none;
border-radius: 10px;
padding: 10px 10px 5px 3px;
margin: 5px 0px 0px 0px;
margin-left: 0px;
margin-right: 0px;
}
pre.literal-block {
margin: 5px 0px 0px 0px;
}
.code p {
padding: 0px 0px 0px 0px;
margin: 0px 0px 0px 0px;
overflow: visible;
}
.run-output p {
padding: 0px 0px 0px 0px;
margin: 0px 0px 0px 0px;
overflow: visible;
}
.interactive-input {
white-space: pre;
font-family: monospace;
}
.interactive-output {
white-space: pre;
font-family: monospace;
}
.interactive-session {
background-color: #fff;
border: 1px solid #eee;
margin: 10px 0px 0px 0px;
padding: 0px 0px 0px 5px;
overflow: visible;
}
.c { color: #408080; font-style: italic } /* Comment */
.err { border: 1px solid #FF0000 } /* Error */
.k { color: #008000; font-weight: bold } /* Keyword */
.o { color: #4444ee } /* Operator */
.cm { color: #408080; font-style: italic } /* Comment.Multiline */
.cp { color: #BC7A00 } /* Comment.Preproc */
.c1 { color: #408080; font-style: italic } /* Comment.Single */
.cs { color: #408080; font-style: italic } /* Comment.Special */
.gd { color: #A00000 } /* Generic.Deleted */
.ge { font-style: italic } /* Generic.Emph */
.gr { color: #FF0000 } /* Generic.Error */
.gh { color: #000080; font-weight: bold } /* Generic.Heading */
.gi { color: #00A000 } /* Generic.Inserted */
.go { color: #808080 } /* Generic.Output */
.gp { color: #000080; font-weight: bold } /* Generic.Prompt */
.gs { font-weight: bold } /* Generic.Strong */
.gu { color: #800080; font-weight: bold } /* Generic.Subheading */
.gt { color: #0040D0 } /* Generic.Traceback */
.kc { color: #008000; font-weight: bold } /* Keyword.Constant */
.kd { color: #008000; font-weight: bold } /* Keyword.Declaration */
.kn { color: #008000; font-weight: bold } /* Keyword.Namespace */
.kp { color: #008000 } /* Keyword.Pseudo */
.kr { color: #008000; font-weight: bold } /* Keyword.Reserved */
.kt { color: #B00040 } /* Keyword.Type */
.m { color: #666666 } /* Literal.Number */
.s { color: #BA2121 } /* Literal.String */
.na { color: #7D9029 } /* Name.Attribute */
.nb { color: #008000 } /* Name.Builtin */
.nc { color: #0000FF; font-weight: bold } /* Name.Class */
.no { color: #880000 } /* Name.Constant */
.nd { color: #AA22FF } /* Name.Decorator */
.ni { color: #999999; font-weight: bold } /* Name.Entity */
.ne { color: #D2413A; font-weight: bold } /* Name.Exception */
.nf { color: #0000FF } /* Name.Function */
.nl { color: #A0A000 } /* Name.Label */
.nn { color: #0000FF; font-weight: bold } /* Name.Namespace */
.nt { color: #008000; font-weight: bold } /* Name.Tag */
.nv { color: #19177C } /* Name.Variable */
.ow { color: #AA22FF; font-weight: bold } /* Operator.Word */
.p { color: #11aa11 } /* Parenthesis */
.w { color: #bbbbbb } /* Text.Whitespace */
.mf { color: #666666 } /* Literal.Number.Float */
.mh { color: #666666 } /* Literal.Number.Hex */
.mi { color: #666666 } /* Literal.Number.Integer */
.mo { color: #666666 } /* Literal.Number.Oct */
.sb { color: #BA2121 } /* Literal.String.Backtick */
.sc { color: #BA2121 } /* Literal.String.Char */
.sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */
.s2 { color: #BA2121 } /* Literal.String.Double */
.se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */
.sh { color: #BA2121 } /* Literal.String.Heredoc */
.si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */
.sx { color: #008000 } /* Literal.String.Other */
.sr { color: #BB6688 } /* Literal.String.Regex */
.s1 { color: #BA2121 } /* Literal.String.Single */
.ss { color: #19177C } /* Literal.String.Symbol */
.bp { color: #008000 } /* Name.Builtin.Pseudo */
.vc { color: #19177C } /* Name.Variable.Class */
.vg { color: #19177C } /* Name.Variable.Global */
.vi { color: #19177C } /* Name.Variable.Instance */
.il { color: #666666 } /* Literal.Number.Integer.Long */
.lineno { color: #bbb }
.run-output-weaver {
white-space: normal;
font-family: default;
background-color: ;
border: 3px solid #eee;
margin: 10px 0px 0px 0px;
padding: 5px 10px 5px 10px;
}
.code-weaver {
border: 3px solid #efe;
}
</style><blockquote>
<p>It seems there is a fundamental tension between exploiting the full
power of a constructive type theory and upholding the fictions of
classical mathematics.</p>
<p class="attribution">—<a class="reference external" href="https://lists.chalmers.se/pipermail/agda/2010/001536.html">Noam Zeilberger</a></p>
</blockquote>
<p>The desire not to be anti-classical puzzles me, because in my opinion the law of the excluded middle isn't just <em>unprovable</em> in automated proof assistants, it is really <em>wrong</em>; The statement (in Agda syntax):</p>
<pre class="literal-block">
∀ {p : Set} → p ⊎ (¬ p)
</pre>
<p>is usually read "for all statements p, p is true or p is false" but a more faithful translation (to the way the language actually behaves) would be "There exists a program, that, when given any statement, either proves that it is true or proves that it is false." Such a program is famously impossible.</p>
<p>But more than that, even if we could invoke the hand of God and introduce such a program as a postulate, we would still have an impossibility, since Gödel showed that there must be statements that can neither be proven true nor false -- in other words, the constructed law of the excluded middle is impossible even to God. Such a postulate isn't just wrong, it is one of the most widely known wrong things in math.</p>
<p>So it seems to me, that any language that is not anticlassical must be missing the benefit of a few assumptions. I would like to see</p>
<pre class="literal-block">
¬ (∀ {p : Set} → p ⊎ (¬ p))
</pre>
<p>to be provable, translated as "If you show me a program and claim it can prove or disprove any statement, I will analyze that program and find a case on which it fails."</p>
<p>The implementation of the above may involve pattern matching on functions (ie, inspecting to see what parts it is built of (lambda, application, constructor, ...)), which would violate extentionality, which I have no problem with because I think extentionality is <em>also</em> obviously untrue. Sure, you may define a</p>
<pre class="literal-block">
data ExtentionallyEqual {A B : Set} (f : A → B) (g : A → B) : Set where
ext-equal : (pf : ∀ {a} → f a ≡ g a) → ExtentionallyEqual f g
</pre>
<p>and reason about it (as you may construct a classical theory within an anticlassical language), but there's no need for all terms in the language to conform, especially when there exist extentionally equal terms with wildly different performance characteristics.</p>
<p>Plus, if you could pattern match on functions, then the compiler could be written as an ordinary function in the source language, <em>in the same execution environment</em>; there would be no need to treat compilation as a "magical" task that happens outside of the main program. And much of the distinction between macros and functions disappears, as all terms are open for inspection. Of course, the inspections would need to respect whatever level of equality the language generally aims to support, and I am thinking but I haven't thought about it too deeply that in Agda that would mean that all pattern matching on functions must only see closed normal forms (which is not unlike how pattern matching already behaves in Agda).</p>
Owenhttp://www.blogger.com/profile/09697040246092989242noreply@blogger.com0tag:blogger.com,1999:blog-696719307153090038.post-51162825085599066942013-04-20T16:52:00.000-04:002013-04-20T16:52:52.601-04:00Axiomatic FRP<style type="text/css">
/*
:Author: David Goodger (goodger@python.org)
:Id: $Id$
:Copyright: This stylesheet has been placed in the public domain.
Default cascading style sheet for the HTML output of Docutils.
See http://docutils.sf.net/docs/howto/html-stylesheets.html for how to
customize this style sheet.
*/
/* used to remove borders from tables and images */
.borderless, table.borderless td, table.borderless th {
border: 0 }
table.borderless td, table.borderless th {
/* Override padding for "table.docutils td" with "! important".
The right padding separates the table cells. */
padding: 0 0.5em 0 0 ! important }
.first {
/* Override more specific margin styles with "! important". */
margin-top: 0 ! important }
.last, .with-subtitle {
margin-bottom: 0 ! important }
.hidden {
display: none }
a.toc-backref {
text-decoration: none ;
color: black }
blockquote.epigraph {
margin: 2em 5em ; }
dl.docutils dd {
margin-bottom: 0.5em }
object[type="image/svg+xml"], object[type="application/x-shockwave-flash"] {
overflow: hidden;
}
/* Uncomment (and remove this text!) to get bold-faced definition list terms
dl.docutils dt {
font-weight: bold }
*/
div.abstract {
margin: 2em 5em }
div.abstract p.topic-title {
font-weight: bold ;
text-align: center }
div.admonition, div.attention, div.caution, div.danger, div.error,
div.hint, div.important, div.note, div.tip, div.warning {
margin: 2em ;
border: medium outset ;
padding: 1em }
div.admonition p.admonition-title, div.hint p.admonition-title,
div.important p.admonition-title, div.note p.admonition-title,
div.tip p.admonition-title {
font-weight: bold ;
font-family: sans-serif }
div.attention p.admonition-title, div.caution p.admonition-title,
div.danger p.admonition-title, div.error p.admonition-title,
div.warning p.admonition-title {
color: red ;
font-weight: bold ;
font-family: sans-serif }
/* Uncomment (and remove this text!) to get reduced vertical space in
compound paragraphs.
div.compound .compound-first, div.compound .compound-middle {
margin-bottom: 0.5em }
div.compound .compound-last, div.compound .compound-middle {
margin-top: 0.5em }
*/
div.dedication {
margin: 2em 5em ;
text-align: center ;
font-style: italic }
div.dedication p.topic-title {
font-weight: bold ;
font-style: normal }
div.figure {
margin-left: 2em ;
margin-right: 2em }
div.footer, div.header {
clear: both;
font-size: smaller }
div.line-block {
display: block ;
margin-top: 1em ;
margin-bottom: 1em }
div.line-block div.line-block {
margin-top: 0 ;
margin-bottom: 0 ;
margin-left: 1.5em }
div.sidebar {
margin: 0 0 0.5em 1em ;
border: medium outset ;
padding: 1em ;
background-color: #ffffee ;
width: 40% ;
float: right ;
clear: right }
div.sidebar p.rubric {
font-family: sans-serif ;
font-size: medium }
div.system-messages {
margin: 5em }
div.system-messages h1 {
color: red }
div.system-message {
border: medium outset ;
padding: 1em }
div.system-message p.system-message-title {
color: red ;
font-weight: bold }
div.topic {
margin: 2em }
h1.section-subtitle, h2.section-subtitle, h3.section-subtitle,
h4.section-subtitle, h5.section-subtitle, h6.section-subtitle {
margin-top: 0.4em }
h1.title {
text-align: center }
h2.subtitle {
text-align: center }
hr.docutils {
width: 75% }
img.align-left, .figure.align-left, object.align-left {
clear: left ;
float: left ;
margin-right: 1em }
img.align-right, .figure.align-right, object.align-right {
clear: right ;
float: right ;
margin-left: 1em }
img.align-center, .figure.align-center, object.align-center {
display: block;
margin-left: auto;
margin-right: auto;
}
.align-left {
text-align: left }
.align-center {
clear: both ;
text-align: center }
.align-right {
text-align: right }
/* reset inner alignment in figures */
div.align-right {
text-align: inherit }
/* div.align-center * { */
/* text-align: left } */
ol.simple, ul.simple {
margin-bottom: 1em }
ol.arabic {
list-style: decimal }
ol.loweralpha {
list-style: lower-alpha }
ol.upperalpha {
list-style: upper-alpha }
ol.lowerroman {
list-style: lower-roman }
ol.upperroman {
list-style: upper-roman }
p.attribution {
text-align: right ;
margin-left: 50% }
p.caption {
font-style: italic }
p.credits {
font-style: italic ;
font-size: smaller }
p.label {
white-space: nowrap }
p.rubric {
font-weight: bold ;
font-size: larger ;
color: maroon ;
text-align: center }
p.sidebar-title {
font-family: sans-serif ;
font-weight: bold ;
font-size: larger }
p.sidebar-subtitle {
font-family: sans-serif ;
font-weight: bold }
p.topic-title {
font-weight: bold }
pre.address {
margin-bottom: 0 ;
margin-top: 0 ;
font: inherit }
pre.literal-block, pre.doctest-block, pre.math {
margin-left: 2em ;
margin-right: 2em }
span.classifier {
font-family: sans-serif ;
font-style: oblique }
span.classifier-delimiter {
font-family: sans-serif ;
font-weight: bold }
span.interpreted {
font-family: sans-serif }
span.option {
white-space: nowrap }
span.pre {
white-space: pre }
span.problematic {
color: red }
span.section-subtitle {
/* font-size relative to parent (h1..h6 element) */
font-size: 80% }
table.citation {
border-left: solid 1px gray;
margin-left: 1px }
table.docinfo {
margin: 2em 4em }
table.docutils {
margin-top: 0.5em ;
margin-bottom: 0.5em }
table.footnote {
border-left: solid 1px black;
margin-left: 1px }
table.docutils td, table.docutils th,
table.docinfo td, table.docinfo th {
padding-left: 0.5em ;
padding-right: 0.5em ;
vertical-align: top }
table.docutils th.field-name, table.docinfo th.docinfo-name {
font-weight: bold ;
text-align: left ;
white-space: nowrap ;
padding-left: 0 }
h1 tt.docutils, h2 tt.docutils, h3 tt.docutils,
h4 tt.docutils, h5 tt.docutils, h6 tt.docutils {
font-size: 100% }
ul.auto-toc {
list-style-type: none }
</style>
<style type="text/css">
.file-header {
color: #999;
font-weight: bold;
}
.run-output {
white-space: pre;
font-family: monospace;
background-color: #fff;
border: 1px solid #eee;
margin: 10px 0px 0px 0px;
padding: 5px 10px 5px 10px;
}
.code {
white-space: pre;
font-family: monospace;
background-color: #dec;
border: none;
border-radius: 10px;
padding: 10px 10px 5px 3px;
margin: 5px 0px 0px 0px;
margin-left: 0px;
margin-right: 0px;
}
pre.literal-block {
margin: 5px 0px 0px 0px;
}
.code p {
padding: 0px 0px 0px 0px;
margin: 0px 0px 0px 0px;
overflow: visible;
}
.run-output p {
padding: 0px 0px 0px 0px;
margin: 0px 0px 0px 0px;
overflow: visible;
}
.interactive-input {
white-space: pre;
font-family: monospace;
}
.interactive-output {
white-space: pre;
font-family: monospace;
}
.interactive-session {
background-color: #fff;
border: 1px solid #eee;
margin: 10px 0px 0px 0px;
padding: 0px 0px 0px 5px;
overflow: visible;
}
.c { color: #408080; font-style: italic } /* Comment */
.err { border: 1px solid #FF0000 } /* Error */
.k { color: #008000; font-weight: bold } /* Keyword */
.o { color: #4444ee } /* Operator */
.cm { color: #408080; font-style: italic } /* Comment.Multiline */
.cp { color: #BC7A00 } /* Comment.Preproc */
.c1 { color: #408080; font-style: italic } /* Comment.Single */
.cs { color: #408080; font-style: italic } /* Comment.Special */
.gd { color: #A00000 } /* Generic.Deleted */
.ge { font-style: italic } /* Generic.Emph */
.gr { color: #FF0000 } /* Generic.Error */
.gh { color: #000080; font-weight: bold } /* Generic.Heading */
.gi { color: #00A000 } /* Generic.Inserted */
.go { color: #808080 } /* Generic.Output */
.gp { color: #000080; font-weight: bold } /* Generic.Prompt */
.gs { font-weight: bold } /* Generic.Strong */
.gu { color: #800080; font-weight: bold } /* Generic.Subheading */
.gt { color: #0040D0 } /* Generic.Traceback */
.kc { color: #008000; font-weight: bold } /* Keyword.Constant */
.kd { color: #008000; font-weight: bold } /* Keyword.Declaration */
.kn { color: #008000; font-weight: bold } /* Keyword.Namespace */
.kp { color: #008000 } /* Keyword.Pseudo */
.kr { color: #008000; font-weight: bold } /* Keyword.Reserved */
.kt { color: #B00040 } /* Keyword.Type */
.m { color: #666666 } /* Literal.Number */
.s { color: #BA2121 } /* Literal.String */
.na { color: #7D9029 } /* Name.Attribute */
.nb { color: #008000 } /* Name.Builtin */
.nc { color: #0000FF; font-weight: bold } /* Name.Class */
.no { color: #880000 } /* Name.Constant */
.nd { color: #AA22FF } /* Name.Decorator */
.ni { color: #999999; font-weight: bold } /* Name.Entity */
.ne { color: #D2413A; font-weight: bold } /* Name.Exception */
.nf { color: #0000FF } /* Name.Function */
.nl { color: #A0A000 } /* Name.Label */
.nn { color: #0000FF; font-weight: bold } /* Name.Namespace */
.nt { color: #008000; font-weight: bold } /* Name.Tag */
.nv { color: #19177C } /* Name.Variable */
.ow { color: #AA22FF; font-weight: bold } /* Operator.Word */
.p { color: #11aa11 } /* Parenthesis */
.w { color: #bbbbbb } /* Text.Whitespace */
.mf { color: #666666 } /* Literal.Number.Float */
.mh { color: #666666 } /* Literal.Number.Hex */
.mi { color: #666666 } /* Literal.Number.Integer */
.mo { color: #666666 } /* Literal.Number.Oct */
.sb { color: #BA2121 } /* Literal.String.Backtick */
.sc { color: #BA2121 } /* Literal.String.Char */
.sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */
.s2 { color: #BA2121 } /* Literal.String.Double */
.se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */
.sh { color: #BA2121 } /* Literal.String.Heredoc */
.si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */
.sx { color: #008000 } /* Literal.String.Other */
.sr { color: #BB6688 } /* Literal.String.Regex */
.s1 { color: #BA2121 } /* Literal.String.Single */
.ss { color: #19177C } /* Literal.String.Symbol */
.bp { color: #008000 } /* Name.Builtin.Pseudo */
.vc { color: #19177C } /* Name.Variable.Class */
.vg { color: #19177C } /* Name.Variable.Global */
.vi { color: #19177C } /* Name.Variable.Instance */
.il { color: #666666 } /* Literal.Number.Integer.Long */
.lineno { color: #bbb }
.run-output-weaver {
white-space: normal;
font-family: default;
background-color: ;
border: 3px solid #eee;
margin: 10px 0px 0px 0px;
padding: 5px 10px 5px 10px;
}
.code-weaver {
border: 3px solid #efe;
}
</style><!-- Axiomatic FRP -->
<p>OK so there's this thing called FRP</p>
<dl class="docutils">
<dt><a class="reference external" href="http://en.wikipedia.org/wiki/Functional_reactive_programming">Functional Reactive Programming</a></dt>
<dd>Building programs that vary in time out of Signals and Events</dd>
<dt>Signals, Events</dt>
<dd>these are objects that you can work with, and you have a set of combinators for making new signals out
of old signals, etc,</dd>
</dl>
<p>And existing implementations -- I haven't looked at every existing implementation, but the ones I have looked at -- either <em>don't</em> allow you to create Signals dynamically (ie all your signals are there at program initialization), or have problems with memory management.</p>
<p>and the problems with memory management come because you have Signals implemented in terms of callbacks, which must use weak pointers, so, even though you can't technically overflow the heap this way, you're relying on the underlying garbage collector to stop active behavior -- to stop events from firing.</p>
<p>So I was thinking, we can do better -- one way we can do better, at least -- is if we drop Signals and Event <em>streams</em> for now and focus on one-shot events, because these have a definite expiration attached to them -- once the one-shot has fired you no longer need to hold on to it, so that should improve the memory situation a little bit.</p>
<p>And in addition to that, we can write down a set of axioms that are <em>obviously true</em> of events, so that if we target an implementation to the axioms in a minimal way, we can limit ourselves to only <em>necessary</em> screw-ups, avoiding superfluous screw-ups not required be the axioms.</p>
<p>So, my first attempt goes,</p>
<pre class="code code-file literal-block literal-block literal-block literal-block literal-block literal-block">
<span class="file-header"> Events1.agda
</span><span class="lineno"> 1 </span><span>-- https://lists.chalmers.se/pipermail/agda/2010/002484.html</span><span>
</span><span class="lineno"> 2 </span><span>-- https://lists.chalmers.se/pipermail/agda/2010/002485.html</span><span>
</span><span class="lineno"> 3 </span><span>{-# OPTIONS --no-positivity-check #-}</span><span>
</span><span class="lineno"> 4 </span><span>{-# OPTIONS --no-termination-check #-}</span><span>
</span><span class="lineno"> 5 </span><span>{-# OPTIONS --type-in-type #-}</span><span>
</span><span class="lineno"> 6 </span><span></span><span>
</span><span class="lineno"> 7 </span><span>-- Compiled against standard library 0.6</span><span>
</span><span class="lineno"> 8 </span><span>module Events1 where</span><span>
</span><span class="lineno"> 9 </span><span></span><span>
</span><span class="lineno"> 10 </span><span>open import Data.Sum using (_⊎_; inj₁; inj₂)</span><span>
</span><span class="lineno"> 11 </span><span>open import Data.Product using (_×_; proj₁; proj₂; _,_)</span><span>
</span><span class="lineno"> 12 </span><span></span><span>
</span><span class="lineno"> 13 </span><span>record EventSystem : Set where</span><span>
</span><span class="lineno"> 14 </span><span> infixl 5 _map_</span><span>
</span><span class="lineno"> 15 </span><span> field</span><span>
</span><span class="lineno"> 16 </span><span> -- The type of a one-shot event, ie it does not repeat.</span><span>
</span><span class="lineno"> 17 </span><span> Event : (result-type : Set) → Set</span><span>
</span><span class="lineno"> 18 </span><span></span><span>
</span><span class="lineno"> 19 </span><span> -- Axioms of Events</span><span>
</span><span class="lineno"> 20 </span><span></span><span>
</span><span class="lineno"> 21 </span><span> -- Basic map.</span><span>
</span><span class="lineno"> 22 </span><span> _map_ : ∀ {r₁ r₂} (ev : Event r₁) (f : r₁ → r₂) → Event r₂</span><span>
</span><span class="lineno"> 23 </span><span></span><span>
</span><span class="lineno"> 24 </span><span> -- Wait for the latter of one or two events.</span><span>
</span><span class="lineno"> 25 </span><span> chain : ∀ {r} (ev : Event (r ⊎ Event r)) → Event r</span><span>
</span><span class="lineno"> 26 </span><span></span><span>
</span><span class="lineno"> 27 </span><span> -- For any two events, one of them happens first.</span><span>
</span><span class="lineno"> 28 </span><span> order : ∀ {r₁ r₂} (ev₁ : Event r₁) (ev₂ : Event r₂)</span><span>
</span><span class="lineno"> 29 </span><span> → Event ((r₁ × Event r₂) ⊎ (r₂ × Event r₁))</span><span>
</span><span></span>
</pre>
<p>and I believe -- and you can look at these and tell me if I'm right or not -- but I believe that these are obviously true -- in a single-threaded, non-relativistic world. The <tt class="docutils literal">order</tt> axiom is obviously not true in a multi-threaded world, where in waiting for the first of two events you may miss the second.</p>
<p>So. The first thing I notice, is that we're very <em>close</em> to having a monad, except we're missing <tt class="docutils literal">pure</tt>, and <tt class="docutils literal">chain</tt> aka <tt class="docutils literal">join</tt> has that funny union type.</p>
<p>Well, I had a very good reason for not including <tt class="docutils literal">pure</tt>. When I was writing this I was very worried about having a way to create an event in a side-effectless manner, which is what <tt class="docutils literal">pure</tt> is. I wanted every event to be <em>grounded</em> to another event, so you never had events as pure objects just floating around. I even considered a <tt class="docutils literal">cojoin</tt>-like definition</p>
<pre class="code code-file literal-block literal-block literal-block literal-block literal-block literal-block">
<span class="file-header"> main
</span><span class="lineno"> 1 </span><span>instantly : ∀ {r} → Event r → Event (Event r)</span><span>
</span><span></span>
</pre>
<p>except that that turned out not to be very useful for writing actual programs.</p>
<p>But anyway, I remembered after writing this that <a class="reference external" href="http://strugglingthroughproblems.blogspot.com/2013/04/applicatives-do-not-need-pure.html">applicatives don't need pure</a>, and you can see how you can use that same exact trick for monads, so we can forgive ourselves for writing it like this:</p>
<pre class="code code-file literal-block literal-block literal-block literal-block literal-block literal-block">
<span></span><span class="lineno"> 1 </span><span>record EventSystem : Set where</span><span>
</span><span class="lineno"> 2 </span><span> infixl 5 _map_</span><span>
</span><span class="lineno"> 3 </span><span> field</span><span>
</span><span class="lineno"> 4 </span><span> Event : (result-type : Set) → Set</span><span>
</span><span class="lineno"> 5 </span><span></span><span>
</span><span class="lineno"> 6 </span><span> instantly : ∀ {r} (x : r) → Event r</span><span>
</span><span class="lineno"> 7 </span><span></span><span>
</span><span class="lineno"> 8 </span><span> _map_ : ∀ {r₁ r₂} (ev : Event r₁) (f : r₁ → r₂) → Event r₂</span><span>
</span><span class="lineno"> 9 </span><span></span><span>
</span><span class="lineno"> 10 </span><span> chain : ∀ {r} (ev : Event (Event r)) → Event r</span><span>
</span><span class="lineno"> 11 </span><span></span><span>
</span><span class="lineno"> 12 </span><span> order : ∀ {r₁ r₂} (ev₁ : Event r₁) (ev₂ : Event r₂)</span><span>
</span><span class="lineno"> 13 </span><span> → Event ((r₁ × Event r₂) ⊎ (r₂ × Event r₁))</span><span>
</span><span></span>
</pre>
<p>Now, honestly, I like the first rules better. The first rules are <em>obviously true</em>, in my opinion, whereas with the second rules we have to do more self-convincing. But monads are ubiquitous and there's no use in fighting a monad when you have a monad, so we go with the monadic <tt class="docutils literal">Event</tt>, plus the <tt class="docutils literal">order</tt> axiom.</p>
<p>(Though we should remember, if we're ever going to implement these axioms, the fact that we had to use a disjoint union to convince ourselves that <tt class="docutils literal">instantly</tt> is valid is a clue that we will need to special-case constant signals).</p>
<p>Now these axioms, despite what I still insist is there <em>obvious trueness</em>, have a <em>serious problem</em>. Let's say I have two events</p>
<pre class="code code-file literal-block literal-block literal-block literal-block literal-block literal-block">
<span></span><span class="lineno"> 2 </span><span>x : Event ⊤</span><span>
</span><span class="lineno"> 3 </span><span>y : Event ⊤</span><span>
</span><span></span>
</pre>
<p>and I use the <tt class="docutils literal">Event</tt> axioms to derive</p>
<pre class="code code-file literal-block literal-block literal-block literal-block">
<span></span><span class="lineno"> 4 </span><span>xy = chain (x map (λ _ → y))</span><span>
</span><span class="lineno"> 5 </span><span>yx = chain (y map (λ _ → x))</span><span>
</span><span></span>
</pre>
<p>which intuitively mean "wait for x to happen, then wait for y to happen", and "wait for y to happen, then wait for x to happen." Now one of these must hang. Either x comes first or y comes first, and if x comes first and you wait for y, then wait for x, the second waiting will never occur.</p>
<p>Now I claim that this does not falsify the <tt class="docutils literal">Event</tt> axioms. An event that never returns is not illegitimate -- you could still have an event resulting in <tt class="docutils literal">⊤</tt> that never comes to pass in the same way you can have a function returning <tt class="docutils literal">⊤</tt> that goes into an infinite loop and never returns. It <em>would</em> result in <tt class="docutils literal">⊤</tt> if it ever resulted in anything.</p>
<p>So we have to ask ourselves a question. Is this a problem worth fixing? Because if we're going to fix it, we're going to have to introduce extra restrictions in the <tt class="docutils literal">Event</tt> axioms AND, critically, it will be <em>impossible</em> to make <tt class="docutils literal">Event</tt> a monad, since we used only monad combinators to derive a never-occurring event, so we'd be giving up on a good deal of friendly generality by giving up on the monad.</p>
<p>But if I just think back to how often my interactive programs hang up waiting for events in the wrong order, the answer is "a lot". This is actually a pretty common problem. This is actually something we could stand to benefit from in the <tt class="docutils literal">Event</tt> laws. Here is an attempted fix:</p>
<pre class="code code-file literal-block literal-block">
<span class="file-header"> SafeEvents.agda
</span><span class="lineno"> 1 </span><span>{-# OPTIONS --type-in-type #-}</span><span>
</span><span class="lineno"> 2 </span><span>{-# OPTIONS --no-positivity-check #-}</span><span>
</span><span class="lineno"> 3 </span><span>{-# OPTIONS --no-termination-check #-}</span><span>
</span><span class="lineno"> 4 </span><span></span><span>
</span><span class="lineno"> 5 </span><span>module SafeEvents where</span><span>
</span><span class="lineno"> 6 </span><span></span><span>
</span><span class="lineno"> 7 </span><span>open import Data.Sum using (_⊎_)</span><span>
</span><span class="lineno"> 8 </span><span>open import Data.Product using (_×_)</span><span>
</span><span class="lineno"> 9 </span><span></span><span>
</span><span class="lineno"> 10 </span><span>π : {T : Set} → (T → Set) → Set</span><span>
</span><span class="lineno"> 11 </span><span>π {T} A = (t : T) → A t</span><span>
</span><span class="lineno"> 12 </span><span></span><span>
</span><span class="lineno"> 13 </span><span>record EventSystem : Set where</span><span>
</span><span class="lineno"> 14 </span><span> field</span><span>
</span><span class="lineno"> 15 </span><span> -- Time is probably not going to be represented by a Double or Int. It's not a "time" so</span><span>
</span><span class="lineno"> 16 </span><span> -- much as a handle for getting at events.</span><span>
</span><span class="lineno"> 17 </span><span> Time : Set</span><span>
</span><span class="lineno"> 18 </span><span></span><span>
</span><span class="lineno"> 19 </span><span> -- We don't really care what this means.</span><span>
</span><span class="lineno"> 20 </span><span> min : Time → Time → Time</span><span>
</span><span class="lineno"> 21 </span><span></span><span>
</span><span class="lineno"> 22 </span><span> Event : (A : Time → Set) → (t : Time) → Set</span><span>
</span><span class="lineno"> 23 </span><span></span><span>
</span><span class="lineno"> 24 </span><span> -- An event that happens without delay.</span><span>
</span><span class="lineno"> 25 </span><span> instantly : ∀ {t A} (x : π A) → Event A t</span><span>
</span><span class="lineno"> 26 </span><span></span><span>
</span><span class="lineno"> 27 </span><span> -- This is like usual map, but be careful, you also get a time.</span><span>
</span><span class="lineno"> 28 </span><span> _map_ : ∀ {t A B} (ev : Event A t) (f : ∀ {t} → A t → B t) → Event B t</span><span>
</span><span class="lineno"> 29 </span><span></span><span>
</span><span class="lineno"> 30 </span><span> -- This represents waiting for the second of two events.</span><span>
</span><span class="lineno"> 31 </span><span> chain : ∀ {A t} → Event (Event A) t → Event A t</span><span>
</span><span class="lineno"> 32 </span><span></span><span>
</span><span class="lineno"> 33 </span><span> -- Total ordering: for any two events, one happens first, and the other second.</span><span>
</span><span class="lineno"> 34 </span><span> order : ∀ {A₁ A₂ t₁ t₂} (ev₁ : Event A₁ t₁) (ev₂ : Event A₂ t₂)</span><span>
</span><span class="lineno"> 35 </span><span> → Event (λ t → (A₁ t × Event A₂ t) ⊎ (A₂ t × Event A₁ t)) (min t₁ t₂)</span><span>
</span><span></span>
</pre>
<p>These axioms, I think, are not so obvious, so they require some explanation.</p>
<p>First, <tt class="docutils literal">Event</tt> now takes a <tt class="docutils literal">Time</tt> parameter in its type:</p>
<pre class="code code-file literal-block literal-block literal-block literal-block">
<span></span><span class="lineno"> 6 </span><span>Event : (A : Time → Set) → (t : Time) → Set</span><span>
</span><span></span>
</pre>
<p><tt class="docutils literal">t</tt> is not the time at which the event happens; it is some time before the event happens. ie, an <tt class="docutils literal">Event A t</tt> is an event that results in <tt class="docutils literal">A</tt> after time <tt class="docutils literal">t</tt>. So if <tt class="docutils literal">t₁</tt> comes before <tt class="docutils literal">t₂</tt>, for example (a property not describable by these axioms), an event <tt class="docutils literal">t₂</tt> could also plausibly be an event <tt class="docutils literal">t₁</tt> -- though we have no axioms to get at this concept.</p>
<p>Now, <tt class="docutils literal">instantly</tt> is written differently:</p>
<pre class="code code-file literal-block literal-block literal-block literal-block">
<span></span><span class="lineno"> 7 </span><span>instantly : ∀ {t A} (x : π A) → Event A t</span><span>
</span><span></span>
</pre>
<p>The <tt class="docutils literal">π</tt> is hiding some things; this could be written</p>
<pre class="code code-file literal-block literal-block literal-block literal-block">
<span></span><span class="lineno"> 8 </span><span>instantly : ∀ {t A} (x : (t : Time) → A t) → Event A t</span><span>
</span><span></span>
</pre>
<p>In other words, the argument you give to instantly should be a function taking a <tt class="docutils literal">Time</tt> as its argument, and returning a result whose type depends on that time. I say "should" rather than "must" because you can see that this is not actually a restriction on the caller -- <tt class="docutils literal">x</tt> is free to ignore the time and return the same result it would have anyway; this type of <tt class="docutils literal">instantly</tt> is actually more powerful and less general than the old one.</p>
<p>Here is how <tt class="docutils literal">_map_</tt> turned out:</p>
<pre class="code code-file literal-block literal-block literal-block literal-block">
<span></span><span class="lineno"> 9 </span><span>_map_ : ∀ {t A B} (ev : Event A t) (f : ∀ {t} → A t → B t) → Event B t</span><span>
</span><span></span>
</pre>
<p>There might be a more useful way to write <tt class="docutils literal">map</tt>, one that gave <tt class="docutils literal">f</tt> more access to the times, but I was worried that could create a problem, so I stuck pretty close to the usual <tt class="docutils literal">_map_</tt> definition.</p>
<p>But <tt class="docutils literal">chain</tt> holds the difference from the old <tt class="docutils literal">Event</tt> laws, and this <em>is</em> more restrictive on the caller:</p>
<pre class="code code-file literal-block literal-block literal-block literal-block">
<span></span><span class="lineno"> 10 </span><span>chain : ∀ {A t} → Event (Event A) t → Event A t</span><span>
</span><span></span>
</pre>
<p>Some of the parameters have been eta-removed, making it look suspiciously monadic, but this can be written as:</p>
<pre class="code code-file literal-block literal-block literal-block literal-block">
<span></span><span class="lineno"> 11 </span><span>chain : ∀ {A t} → Event (λ t′ → Event A t′) t → Event A t</span><span>
</span><span></span>
</pre>
<p>In other words, you can chain an event producing an event <em>provided that</em> the inner event is constructed <em>based on</em> any time. This is giving me some kind of hints that times need types associated with them -- maybe <tt class="docutils literal">Time</tt> actually represents an observable object -- but I'm not sure what to do about that right now.</p>
<p>And lastly, <tt class="docutils literal">order</tt> gives us the kind of useful information needed to call <tt class="docutils literal">chain</tt>:</p>
<pre class="code code-file literal-block literal-block literal-block literal-block">
<span></span><span class="lineno"> 12 </span><span>order : ∀ {A₁ A₂ t₁ t₂} (ev₁ : Event A₁ t₁) (ev₂ : Event A₂ t₂)</span><span>
</span><span class="lineno"> 13 </span><span> → Event (λ t → (A₁ t × Event A₂ t) ⊎ (A₂ t × Event A₁ t)) (min t₁ t₂)</span><span>
</span><span></span>
</pre>
<p>And we can verify that the necessary information is contained in <tt class="docutils literal">order</tt> by writing a <tt class="docutils literal">second</tt> function to get the second of two events:</p>
<pre class="code code-file literal-block literal-block literal-block literal-block">
<span></span><span class="lineno"> 14 </span><span>second : ∀ {r t₁ t₂} → Event r t₁ → Event r t₂ → Event r (min t₁ t₂)</span><span>
</span><span class="lineno"> 15 </span><span>second ev₁ ev₂ = chain (order ev₁ ev₂ map λ {</span><span>
</span><span class="lineno"> 16 </span><span> (inj₁ (r , next)) → next;</span><span>
</span><span class="lineno"> 17 </span><span> (inj₂ (r , next)) → next</span><span>
</span><span class="lineno"> 18 </span><span> })</span><span>
</span><span></span>
</pre>
<p>And that works. And now we have time-safe events.</p>
Owenhttp://www.blogger.com/profile/09697040246092989242noreply@blogger.com0tag:blogger.com,1999:blog-696719307153090038.post-31894801896869653042013-04-17T23:00:00.000-04:002013-04-17T23:00:34.926-04:00Applicatives do not need `pure`<style type="text/css">
/*
:Author: David Goodger (goodger@python.org)
:Id: $Id$
:Copyright: This stylesheet has been placed in the public domain.
Default cascading style sheet for the HTML output of Docutils.
See http://docutils.sf.net/docs/howto/html-stylesheets.html for how to
customize this style sheet.
*/
/* used to remove borders from tables and images */
.borderless, table.borderless td, table.borderless th {
border: 0 }
table.borderless td, table.borderless th {
/* Override padding for "table.docutils td" with "! important".
The right padding separates the table cells. */
padding: 0 0.5em 0 0 ! important }
.first {
/* Override more specific margin styles with "! important". */
margin-top: 0 ! important }
.last, .with-subtitle {
margin-bottom: 0 ! important }
.hidden {
display: none }
a.toc-backref {
text-decoration: none ;
color: black }
blockquote.epigraph {
margin: 2em 5em ; }
dl.docutils dd {
margin-bottom: 0.5em }
object[type="image/svg+xml"], object[type="application/x-shockwave-flash"] {
overflow: hidden;
}
/* Uncomment (and remove this text!) to get bold-faced definition list terms
dl.docutils dt {
font-weight: bold }
*/
div.abstract {
margin: 2em 5em }
div.abstract p.topic-title {
font-weight: bold ;
text-align: center }
div.admonition, div.attention, div.caution, div.danger, div.error,
div.hint, div.important, div.note, div.tip, div.warning {
margin: 2em ;
border: medium outset ;
padding: 1em }
div.admonition p.admonition-title, div.hint p.admonition-title,
div.important p.admonition-title, div.note p.admonition-title,
div.tip p.admonition-title {
font-weight: bold ;
font-family: sans-serif }
div.attention p.admonition-title, div.caution p.admonition-title,
div.danger p.admonition-title, div.error p.admonition-title,
div.warning p.admonition-title {
color: red ;
font-weight: bold ;
font-family: sans-serif }
/* Uncomment (and remove this text!) to get reduced vertical space in
compound paragraphs.
div.compound .compound-first, div.compound .compound-middle {
margin-bottom: 0.5em }
div.compound .compound-last, div.compound .compound-middle {
margin-top: 0.5em }
*/
div.dedication {
margin: 2em 5em ;
text-align: center ;
font-style: italic }
div.dedication p.topic-title {
font-weight: bold ;
font-style: normal }
div.figure {
margin-left: 2em ;
margin-right: 2em }
div.footer, div.header {
clear: both;
font-size: smaller }
div.line-block {
display: block ;
margin-top: 1em ;
margin-bottom: 1em }
div.line-block div.line-block {
margin-top: 0 ;
margin-bottom: 0 ;
margin-left: 1.5em }
div.sidebar {
margin: 0 0 0.5em 1em ;
border: medium outset ;
padding: 1em ;
background-color: #ffffee ;
width: 40% ;
float: right ;
clear: right }
div.sidebar p.rubric {
font-family: sans-serif ;
font-size: medium }
div.system-messages {
margin: 5em }
div.system-messages h1 {
color: red }
div.system-message {
border: medium outset ;
padding: 1em }
div.system-message p.system-message-title {
color: red ;
font-weight: bold }
div.topic {
margin: 2em }
h1.section-subtitle, h2.section-subtitle, h3.section-subtitle,
h4.section-subtitle, h5.section-subtitle, h6.section-subtitle {
margin-top: 0.4em }
h1.title {
text-align: center }
h2.subtitle {
text-align: center }
hr.docutils {
width: 75% }
img.align-left, .figure.align-left, object.align-left {
clear: left ;
float: left ;
margin-right: 1em }
img.align-right, .figure.align-right, object.align-right {
clear: right ;
float: right ;
margin-left: 1em }
img.align-center, .figure.align-center, object.align-center {
display: block;
margin-left: auto;
margin-right: auto;
}
.align-left {
text-align: left }
.align-center {
clear: both ;
text-align: center }
.align-right {
text-align: right }
/* reset inner alignment in figures */
div.align-right {
text-align: inherit }
/* div.align-center * { */
/* text-align: left } */
ol.simple, ul.simple {
margin-bottom: 1em }
ol.arabic {
list-style: decimal }
ol.loweralpha {
list-style: lower-alpha }
ol.upperalpha {
list-style: upper-alpha }
ol.lowerroman {
list-style: lower-roman }
ol.upperroman {
list-style: upper-roman }
p.attribution {
text-align: right ;
margin-left: 50% }
p.caption {
font-style: italic }
p.credits {
font-style: italic ;
font-size: smaller }
p.label {
white-space: nowrap }
p.rubric {
font-weight: bold ;
font-size: larger ;
color: maroon ;
text-align: center }
p.sidebar-title {
font-family: sans-serif ;
font-weight: bold ;
font-size: larger }
p.sidebar-subtitle {
font-family: sans-serif ;
font-weight: bold }
p.topic-title {
font-weight: bold }
pre.address {
margin-bottom: 0 ;
margin-top: 0 ;
font: inherit }
pre.literal-block, pre.doctest-block, pre.math {
margin-left: 2em ;
margin-right: 2em }
span.classifier {
font-family: sans-serif ;
font-style: oblique }
span.classifier-delimiter {
font-family: sans-serif ;
font-weight: bold }
span.interpreted {
font-family: sans-serif }
span.option {
white-space: nowrap }
span.pre {
white-space: pre }
span.problematic {
color: red }
span.section-subtitle {
/* font-size relative to parent (h1..h6 element) */
font-size: 80% }
table.citation {
border-left: solid 1px gray;
margin-left: 1px }
table.docinfo {
margin: 2em 4em }
table.docutils {
margin-top: 0.5em ;
margin-bottom: 0.5em }
table.footnote {
border-left: solid 1px black;
margin-left: 1px }
table.docutils td, table.docutils th,
table.docinfo td, table.docinfo th {
padding-left: 0.5em ;
padding-right: 0.5em ;
vertical-align: top }
table.docutils th.field-name, table.docinfo th.docinfo-name {
font-weight: bold ;
text-align: left ;
white-space: nowrap ;
padding-left: 0 }
h1 tt.docutils, h2 tt.docutils, h3 tt.docutils,
h4 tt.docutils, h5 tt.docutils, h6 tt.docutils {
font-size: 100% }
ul.auto-toc {
list-style-type: none }
</style>
<style type="text/css">
.file-header {
color: #999;
font-weight: bold;
}
.run-output {
white-space: pre;
font-family: monospace;
background-color: #fff;
border: 1px solid #eee;
margin: 10px 0px 0px 0px;
padding: 5px 10px 5px 10px;
}
.code {
white-space: pre;
font-family: monospace;
background-color: #dec;
border: none;
border-radius: 10px;
padding: 10px 10px 5px 3px;
margin: 5px 0px 0px 0px;
margin-left: 0px;
margin-right: 0px;
}
pre.literal-block {
margin: 5px 0px 0px 0px;
}
.code p {
padding: 0px 0px 0px 0px;
margin: 0px 0px 0px 0px;
overflow: visible;
}
.run-output p {
padding: 0px 0px 0px 0px;
margin: 0px 0px 0px 0px;
overflow: visible;
}
.interactive-input {
white-space: pre;
font-family: monospace;
}
.interactive-output {
white-space: pre;
font-family: monospace;
}
.interactive-session {
background-color: #fff;
border: 1px solid #eee;
margin: 10px 0px 0px 0px;
padding: 0px 0px 0px 5px;
overflow: visible;
}
.c { color: #408080; font-style: italic } /* Comment */
.err { border: 1px solid #FF0000 } /* Error */
.k { color: #008000; font-weight: bold } /* Keyword */
.o { color: #4444ee } /* Operator */
.cm { color: #408080; font-style: italic } /* Comment.Multiline */
.cp { color: #BC7A00 } /* Comment.Preproc */
.c1 { color: #408080; font-style: italic } /* Comment.Single */
.cs { color: #408080; font-style: italic } /* Comment.Special */
.gd { color: #A00000 } /* Generic.Deleted */
.ge { font-style: italic } /* Generic.Emph */
.gr { color: #FF0000 } /* Generic.Error */
.gh { color: #000080; font-weight: bold } /* Generic.Heading */
.gi { color: #00A000 } /* Generic.Inserted */
.go { color: #808080 } /* Generic.Output */
.gp { color: #000080; font-weight: bold } /* Generic.Prompt */
.gs { font-weight: bold } /* Generic.Strong */
.gu { color: #800080; font-weight: bold } /* Generic.Subheading */
.gt { color: #0040D0 } /* Generic.Traceback */
.kc { color: #008000; font-weight: bold } /* Keyword.Constant */
.kd { color: #008000; font-weight: bold } /* Keyword.Declaration */
.kn { color: #008000; font-weight: bold } /* Keyword.Namespace */
.kp { color: #008000 } /* Keyword.Pseudo */
.kr { color: #008000; font-weight: bold } /* Keyword.Reserved */
.kt { color: #B00040 } /* Keyword.Type */
.m { color: #666666 } /* Literal.Number */
.s { color: #BA2121 } /* Literal.String */
.na { color: #7D9029 } /* Name.Attribute */
.nb { color: #008000 } /* Name.Builtin */
.nc { color: #0000FF; font-weight: bold } /* Name.Class */
.no { color: #880000 } /* Name.Constant */
.nd { color: #AA22FF } /* Name.Decorator */
.ni { color: #999999; font-weight: bold } /* Name.Entity */
.ne { color: #D2413A; font-weight: bold } /* Name.Exception */
.nf { color: #0000FF } /* Name.Function */
.nl { color: #A0A000 } /* Name.Label */
.nn { color: #0000FF; font-weight: bold } /* Name.Namespace */
.nt { color: #008000; font-weight: bold } /* Name.Tag */
.nv { color: #19177C } /* Name.Variable */
.ow { color: #AA22FF; font-weight: bold } /* Operator.Word */
.p { color: #11aa11 } /* Parenthesis */
.w { color: #bbbbbb } /* Text.Whitespace */
.mf { color: #666666 } /* Literal.Number.Float */
.mh { color: #666666 } /* Literal.Number.Hex */
.mi { color: #666666 } /* Literal.Number.Integer */
.mo { color: #666666 } /* Literal.Number.Oct */
.sb { color: #BA2121 } /* Literal.String.Backtick */
.sc { color: #BA2121 } /* Literal.String.Char */
.sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */
.s2 { color: #BA2121 } /* Literal.String.Double */
.se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */
.sh { color: #BA2121 } /* Literal.String.Heredoc */
.si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */
.sx { color: #008000 } /* Literal.String.Other */
.sr { color: #BB6688 } /* Literal.String.Regex */
.s1 { color: #BA2121 } /* Literal.String.Single */
.ss { color: #19177C } /* Literal.String.Symbol */
.bp { color: #008000 } /* Name.Builtin.Pseudo */
.vc { color: #19177C } /* Name.Variable.Class */
.vg { color: #19177C } /* Name.Variable.Global */
.vi { color: #19177C } /* Name.Variable.Instance */
.il { color: #666666 } /* Literal.Number.Integer.Long */
.lineno { color: #bbb }
.run-output-weaver {
white-space: normal;
font-family: default;
background-color: ;
border: 3px solid #eee;
margin: 10px 0px 0px 0px;
padding: 5px 10px 5px 10px;
}
.code-weaver {
border: 3px solid #efe;
}
</style><!-- Applicatives do not need ``pure``. -->
<p>A few days ago I said:</p>
<blockquote>
Usually, applicatives are assigned a third power, which is the power to take a plain object and bring it into the functor in the simplest way possible, eg 2 becomes [ 2 ]. This power is essential to writing generic, recursive programs with applicatives.</blockquote>
<p>I take it back. I now believe that <em>nothing interesting you can do with an applicative functor requires `pure`.</em></p>
<p>Assumption: if the only practical difference between two programs is that one applies <tt class="docutils literal">pure</tt> <em>at the very end</em>, it is no more interesting than the other.</p>
<p>For example, <tt class="docutils literal">pure 3</tt> is not interesting, because it doesn't tell you anything that <tt class="docutils literal">3</tt> doesn't, and <tt class="docutils literal">(+) <$> (pure x) <*> (pure y)</tt> is not interesting because it is equivalent to <tt class="docutils literal">pure (x + y)</tt>.</p>
<p>I had been thinking of ways to represent events in FRP without bringing in memory issues that usually come with FRP. This meant I was spending a lot of time looking at different algebraic structures, and trying to peel off the assumptions that weren't needed. At one point I had a structure like the following:</p>
<pre class="code code-file literal-block literal-block literal-block literal-block">
<span class="file-header"> UnpureApplicatives.agda
</span><span class="lineno"> 1 </span><span>module UnpureApplicatives where</span><span>
</span><span class="lineno"> 2 </span><span></span><span>
</span><span class="lineno"> 3 </span><span>open import Level</span><span>
</span><span class="lineno"> 4 </span><span></span><span>
</span><span class="lineno"> 5 </span><span>-- Here is a definition of applicatives that does not include</span><span>
</span><span class="lineno"> 6 </span><span>-- a `pure` axiom.</span><span>
</span><span class="lineno"> 7 </span><span></span><span>
</span><span class="lineno"> 8 </span><span>record UnpureApplicative {l} (F : Set l → Set l) : Set (suc l ⊔ suc zero) where</span><span>
</span><span class="lineno"> 9 </span><span> field</span><span>
</span><span class="lineno"> 10 </span><span> -- The basic map axiom.</span><span>
</span><span class="lineno"> 11 </span><span> _ap\_ : ∀ {A B} (f : A → B) (x : F A) → F B</span><span>
</span><span class="lineno"> 12 </span><span></span><span>
</span><span class="lineno"> 13 </span><span> -- The combine axiom.</span><span>
</span><span class="lineno"> 14 </span><span> _/ap\_ : ∀ {A B} (f : F (A → B)) (x : F A) → F B</span><span>
</span><span></span>
</pre>
<p>which has <tt class="docutils literal">map</tt> and <tt class="docutils literal">ap</tt> (as all applicatives do) but lacks <tt class="docutils literal">pure</tt>, and provides no way of defining <tt class="docutils literal">pure</tt>.</p>
<p>But we can still define something that is <em>just as good as</em> <tt class="docutils literal">sequence</tt>:</p>
<pre class="code code-file literal-block literal-block literal-block literal-block">
<span class="file-header"> Test1.agda
</span><span class="lineno"> 1 </span><span>open import Level</span><span>
</span><span class="lineno"> 2 </span><span>open import UnpureApplicatives</span><span>
</span><span class="lineno"> 3 </span><span></span><span>
</span><span class="lineno"> 4 </span><span>module Test1 {l} (F : _) (applicative : UnpureApplicative {l} F) where</span><span>
</span><span class="lineno"> 5 </span><span> open import Data.List using (List; []; _∷_)</span><span>
</span><span class="lineno"> 6 </span><span> open import Data.Sum using (_⊎_; inj₁; inj₂)</span><span>
</span><span class="lineno"> 7 </span><span></span><span>
</span><span class="lineno"> 8 </span><span> open UnpureApplicative applicative</span><span>
</span><span class="lineno"> 9 </span><span></span><span>
</span><span class="lineno"> 10 </span><span> -- We can derive this from the other two.</span><span>
</span><span class="lineno"> 11 </span><span> -- Agda auto was actually able to solve this one.</span><span>
</span><span class="lineno"> 12 </span><span> _/ap_ : ∀ {B} {A : Set l} (f : F (A → B)) (x : A) → F B</span><span>
</span><span class="lineno"> 13 </span><span> _/ap_ f x = (λ z → z x) ap\ f</span><span>
</span><span class="lineno"> 14 </span><span></span><span>
</span><span class="lineno"> 15 </span><span> -- This is how sequence now looks.</span><span>
</span><span class="lineno"> 16 </span><span> -- It's ugly, but it gets the job done.</span><span>
</span><span class="lineno"> 17 </span><span> sequence : ∀ {A} → List (F A) → List A ⊎ F (List A)</span><span>
</span><span class="lineno"> 18 </span><span> sequence [] = inj₁ []</span><span>
</span><span class="lineno"> 19 </span><span> sequence (x ∷ list) with sequence list</span><span>
</span><span class="lineno"> 20 </span><span> ... | inj₁ plain = inj₂ ((_∷_ ap\ x) /ap plain)</span><span>
</span><span class="lineno"> 21 </span><span> ... | inj₂ appy = inj₂ ((_∷_ ap\ x) /ap\ appy)</span><span>
</span><span></span>
</pre>
<p>and the lack of pure is not "interesting" here because it may be applied at the end, by pattern matching on <tt class="docutils literal">⊎</tt>.</p>
<p>So what we've really done is use this "unpure" applicative to build a regular "pure" applicative:</p>
<pre class="code code-file literal-block literal-block literal-block literal-block">
<span class="file-header"> BuildFromUnpure.agda
</span><span class="lineno"> 1 </span><span>open import UnpureApplicatives</span><span>
</span><span class="lineno"> 2 </span><span></span><span>
</span><span class="lineno"> 3 </span><span>module BuildFromUnpure {l} (F : Set l → Set l) (Unpure : UnpureApplicative F) where</span><span>
</span><span class="lineno"> 4 </span><span> open import Data.Sum using (_⊎_; inj₁; inj₂)</span><span>
</span><span class="lineno"> 5 </span><span> open UnpureApplicative Unpure using (_ap\_; _/ap\_)</span><span>
</span><span class="lineno"> 6 </span><span></span><span>
</span><span class="lineno"> 7 </span><span> F' : Set l → Set l</span><span>
</span><span class="lineno"> 8 </span><span> F' A = A ⊎ F A</span><span>
</span><span class="lineno"> 9 </span><span></span><span>
</span><span class="lineno"> 10 </span><span> pure : ∀ {A} → A → F' A</span><span>
</span><span class="lineno"> 11 </span><span> pure = inj₁</span><span>
</span><span class="lineno"> 12 </span><span></span><span>
</span><span class="lineno"> 13 </span><span> _/ap'\_ : ∀ {A B} (f : F' (A → B)) (x : F' A) → F' B</span><span>
</span><span class="lineno"> 14 </span><span> inj₁ f /ap'\ inj₁ x = inj₁ (f x)</span><span>
</span><span class="lineno"> 15 </span><span> inj₁ f /ap'\ inj₂ x = inj₂ (f ap\ x)</span><span>
</span><span class="lineno"> 16 </span><span> inj₂ f /ap'\ inj₁ x = inj₂ ((λ f → f x) ap\ f)</span><span>
</span><span class="lineno"> 17 </span><span> inj₂ f /ap'\ inj₂ x = inj₂ (f /ap\ x)</span><span>
</span><span></span>
</pre>
<p>And I think it is clear that these two definitions are equally interesting, and, if a definition for <tt class="docutils literal">pure</tt> were supplied originally, it could always be applied at the end, and so would add nothing.</p>
<p>Also, you could take an unpure applicative, make it a regular applicative, then drop the <tt class="docutils literal">pure</tt>, and have something equivalent to the original unpure applicative.</p>
Owenhttp://www.blogger.com/profile/09697040246092989242noreply@blogger.com0