eighty-twenty news feed for tag "research"2024-01-24T14:37:46+00:00http://eighty-twenty.org/tag/research/index.atomtonygmikebPurely Functional Operating Systems2022-06-23T11:02:53+00:00http://eighty-twenty.org/2022/06/23/henderson-functional-operating-systems-1982tonyg<p>Apparently Peter Henderson’s 1982 paper “Purely Functional Operating Systems” is hard to find
online. Some years ago, during my PhD research, I scanned the paper from a physical copy in the
university library. <a href="/files/Henderson - 1982 - Purely Functional Operating Systems.pdf">Here’s the scan I made</a>.</p>
<blockquote>
<p><a href="/files/Henderson - 1982 - Purely Functional Operating Systems.pdf">Henderson, Peter. “Purely Functional Operating Systems.” In Functional Programming and Its Applications, edited by J. Darlington, P. Henderson, and D. Turner, 177–92. Cambridge University Press, 1982.</a></p>
</blockquote>
New System-layer Syndicate project2021-05-17T10:28:04+00:00http://eighty-twenty.org/2021/05/17/new-system-layer-projecttonyg<p><strong>Part of a series:</strong> <a href="/tag/squeak-phone">#squeak-phone</a></p>
<hr />
<p>I’m proud to announce
<a href="https://syndicate-lang.org/projects/2021/system-layer/">a new project on using the Syndicated Actor model and dataspaces to implement a <em>system layer</em></a>.</p>
<p class="center"><a href="https://syndicate-lang.org/projects/2021/system-layer/"><code class="language-plaintext highlighter-rouge">https://syndicate-lang.org/projects/2021/system-layer/</code></a></p>
<p>The project will be investigating the question</p>
<blockquote>
<p>Could dataspaces be a suitable system layer foundation, perhaps
replacing software like systemd and D-Bus?</p>
</blockquote>
<p>Concretely, it will produce a prototype system layer implementation
building on <a href="/tag/squeak-phone/">my existing “squeak-on-a-cellphone” prototyping work</a>.</p>
<p>I’m very grateful for project sponsorship from the NLnet Foundation, as
part of the NGI Zero PET programme.</p>
New Syndicate website2021-05-17T10:16:47+00:00http://eighty-twenty.org/2021/05/17/new-syndicate-websitetonyg<p>I’ve just published a
<a href="https://syndicate-lang.org/">completely revamped and massively expanded Syndicate project website</a>:</p>
<p class="center"><a href="https://syndicate-lang.org/"><code class="language-plaintext highlighter-rouge">https://syndicate-lang.org/</code></a></p>
<p>Hooray!</p>
<p>A big part of the change is to fix the confusing terminology used in
the project. From now on, I’ll try to stick to the following:</p>
<ul>
<li>
<p><em>Syndicated actors</em>, and the <em>Syndicated Actor model</em>: Like regular
actors, but with replicated state, i.e. assertions connecting peers
rather than just messages.</p>
</li>
<li>
<p>The notion of a <em>dataspace</em>: A particular kind of behaviour of a
syndicated actor: tracks assertions made to it, and reacts to
assertions of interest by responding with previously-learned facts.</p>
</li>
<li>
<p>Structuring of a syndicated actor via <em>conversational concurrency</em>
and <em>facets</em>: Programming actors, syndicated or not, gets to be a
bit of a mess if you’re restricted to using a monolithic behaviour
function. Facets let you split up an actor’s behaviour into
reusable composable pieces. Conversational concurrency guides you
in how to carve it up.</p>
</li>
<li>
<p>Language support for syndicated actors and conversational
concurrency: the <em>Syndicate DSL</em>.</p>
</li>
</ul>
#lang something: An alternative syntax for Racket2019-07-21T16:03:42+00:00http://eighty-twenty.org/2019/07/21/indentation-syntax-for-rackettonyg<p>Recent discussions (e.g.
<a href="https://groups.google.com/forum/#!topic/racket-users/HiC7z3A5O-k">1</a>,
<a href="https://groups.google.com/forum/#!topic/racket-users/3aIPOGbGgmc">2</a>)
about potentially revising Racket syntax for Racket2 have reminded me
I never properly announced <a href="https://github.com/tonyg/racket-something"><code class="language-plaintext highlighter-rouge">#lang something</code></a>,
an experiment from back in 2016.</p>
<p>The main idea is S-expressions, but with usually-implicit parentheses
and support for prefix/infix/postfix operators. Indentation for
grouping is explicitly represented in the S-expression returned from
the reader.</p>
<ul>
<li>(+) keeps a semi-structured input format: reader yields ordinary syntax</li>
<li>(+) macros Just Work</li>
<li>(+) you can do “if … then … else …”: <a href="https://github.com/tonyg/racket-something/blob/4a00a9a6d37777f5aab4f28b03c53555b87e21d7/examples/if-then-else.rkt">an example</a></li>
<li>(+) you can do “… where …”: <a href="https://github.com/tonyg/racket-something/blob/4a00a9a6d37777f5aab4f28b03c53555b87e21d7/examples/where.rkt">an example</a></li>
<li>(-) uses indentation (though it doesn’t have to; see for example <a href="https://github.com/tonyg/racket-something/blob/4a00a9a6d37777f5aab4f28b03c53555b87e21d7/src/something/shell2.rkt">this module</a>)</li>
<li>(-) the function syntax isn’t <code class="language-plaintext highlighter-rouge">function(arg, ...)</code></li>
</ul>
<p>(More links at the bottom of this post.)</p>
<p>In addition to the reader, <code class="language-plaintext highlighter-rouge">#lang something</code> provides a small
selection of special forms that take advantage of the new syntax, and
<code class="language-plaintext highlighter-rouge">#lang something/shell</code> adds Unix-shell-like behaviour and a few
associated utilities.</p>
<p>This program:</p>
<figure class="highlight"><pre><code class="language-racket" data-lang="racket"><span class="o">#</span><span class="nv">lang</span> <span class="nv">something</span>
<span class="nv">for</span> <span class="p">{</span> <span class="nv">x:</span> <span class="mi">1</span> <span class="o">..</span> <span class="mi">10</span> <span class="p">}</span>
<span class="nv">def</span> <span class="nv">y:</span> <span class="nv">x</span> <span class="nv">+</span> <span class="mi">1</span>
<span class="nv">printf</span> <span class="s">"x ~a y ~a\n"</span> <span class="nv">x</span> <span class="nv">y</span></code></pre></figure>
<p>… reads as this S-expression:</p>
<figure class="highlight"><pre><code class="language-racket" data-lang="racket"><span class="p">(</span><span class="k">module</span> <span class="nv">something-module</span> <span class="nv">something/base</span>
<span class="p">(</span><span class="nf">#%rewrite-body</span>
<span class="p">(</span><span class="nf">for</span> <span class="p">(</span><span class="nf">block</span> <span class="p">(</span><span class="nf">x</span> <span class="p">(</span><span class="nf">block</span> <span class="p">(</span><span class="nf">1</span> <span class="o">..</span> <span class="mi">10</span><span class="p">))))</span>
<span class="p">(</span><span class="nf">block</span> <span class="p">(</span><span class="nf">def</span> <span class="nv">y</span> <span class="p">(</span><span class="nf">block</span> <span class="p">(</span><span class="nf">x</span> <span class="nv">+</span> <span class="mi">1</span><span class="p">)))</span>
<span class="p">(</span><span class="nb">printf</span> <span class="s">"x ~a y ~a\n"</span> <span class="nv">x</span> <span class="nv">y</span><span class="p">)))))</span></code></pre></figure>
<p>The <code class="language-plaintext highlighter-rouge">#%rewrite-body</code> macro, together with its companion
<code class="language-plaintext highlighter-rouge">#%rewrite-infix</code>, consults an operator table, extendable via the
<code class="language-plaintext highlighter-rouge">def-operator</code> macro, to rewrite infix syntax into standard prefix
S-expressions using a Pratt parser.</p>
<p>The <code class="language-plaintext highlighter-rouge">block</code> syntax has many different interpretations. It has a macro
binding that turns it into a Racket <code class="language-plaintext highlighter-rouge">match-lambda*</code>, and it is used as
literal syntax as input to other macro definitions.</p>
<p>For example, here’s one possible implementation of that <code class="language-plaintext highlighter-rouge">for</code> syntax:</p>
<figure class="highlight"><pre><code class="language-racket" data-lang="racket"><span class="o">#</span><span class="nv">lang</span> <span class="nv">something</span>
<span class="nv">provide</span>
<span class="nv">for</span>
<span class="nv">require</span>
<span class="nv">for-syntax</span> <span class="nv">something/base</span>
<span class="nv">prefix-in</span> <span class="nv">base_</span> <span class="nv">racket/base</span>
<span class="nv">def-syntax</span> <span class="nv">for</span> <span class="nv">stx</span>
<span class="nv">syntax-case</span> <span class="nv">stx</span> <span class="p">(</span><span class="nf">block</span><span class="p">)</span>
<span class="nv">_</span> <span class="p">(</span><span class="nf">block</span> <span class="p">(</span><span class="nf">v</span> <span class="p">(</span><span class="nf">block</span> <span class="nv">exp</span><span class="p">))</span> <span class="o">...</span><span class="p">)</span> <span class="p">(</span><span class="nf">block</span> <span class="nv">body</span> <span class="o">...</span><span class="p">)</span>
<span class="p">(</span><span class="k">syntax</span> <span class="p">(</span><span class="nf">base_for</span> <span class="p">((</span><span class="nf">v</span> <span class="nv">exp</span><span class="p">)</span> <span class="o">...</span><span class="p">)</span> <span class="nv">body</span> <span class="o">...</span><span class="p">))</span>
<span class="nv">def-operator</span> <span class="o">..</span> <span class="mi">10</span> <span class="nv">nonassoc</span> <span class="nv">in-range</span></code></pre></figure>
<p>Notice how the <code class="language-plaintext highlighter-rouge">block</code> S-expressions are rewritten into a normal
S-expression compatible with the underlying <code class="language-plaintext highlighter-rouge">for</code> from <code class="language-plaintext highlighter-rouge">racket/base</code>.</p>
<p>Generally, all of these forms are equivalent</p>
<figure class="highlight"><pre><code class="language-text" data-lang="text">x y z x y z: x y z { a; b }
a a
b b</code></pre></figure>
<p>and they are read as</p>
<figure class="highlight"><pre><code class="language-racket" data-lang="racket"><span class="p">(</span><span class="nf">x</span> <span class="nv">y</span> <span class="nv">z</span> <span class="p">(</span><span class="nf">block</span> <span class="nv">a</span> <span class="nv">b</span><span class="p">))</span></code></pre></figure>
<p>and are then made available to the normal macro-expansion process
(which involves a new infix-rewriting semi-phase).</p>
<p>Colons are optional to indicate a following suite at the end of an
indentation-sensitive line. Indentation-sensitivity is disabled inside
parentheses. If inside a parenthesised expression,
indentation-sensitivity can be reenabled with a colon at the end of a
line:</p>
<figure class="highlight"><pre><code class="language-racket" data-lang="racket"><span class="nv">a</span> <span class="nv">b</span> <span class="p">(</span><span class="nf">c</span> <span class="nv">d:</span>
<span class="nv">e</span>
<span class="nv">f</span><span class="p">)</span>
<span class="nv">=</span> <span class="p">(</span><span class="nf">a</span> <span class="nv">b</span> <span class="p">(</span><span class="nf">c</span> <span class="nv">d</span> <span class="p">(</span><span class="nf">block</span> <span class="nv">e</span> <span class="nv">f</span><span class="p">)))</span>
<span class="nv">a</span> <span class="nv">b</span> <span class="p">(</span><span class="nf">c</span> <span class="nv">d</span>
<span class="nv">e</span>
<span class="nv">f</span><span class="p">)</span>
<span class="nv">=</span> <span class="p">(</span><span class="nf">a</span> <span class="nv">b</span> <span class="p">(</span><span class="nf">c</span> <span class="nv">d</span> <span class="nv">e</span> <span class="nv">f</span><span class="p">))</span></code></pre></figure>
<p>Conversely, long lines may be split up and logically continued over
subsequent physical lines with a trailing <code class="language-plaintext highlighter-rouge">\</code>:</p>
<figure class="highlight"><pre><code class="language-racket" data-lang="racket"><span class="nv">a</span> <span class="nv">b</span> <span class="nv">c</span> <span class="nv">\</span>
<span class="nv">d</span> <span class="nv">\</span>
<span class="nv">e</span>
<span class="nv">=</span> <span class="p">(</span><span class="nf">a</span> <span class="nv">b</span> <span class="nv">c</span> <span class="nv">d</span> <span class="nv">e</span><span class="p">)</span></code></pre></figure>
<p>Semicolons may also appear in vertically-laid-out suites; these two
are equivalent:</p>
<figure class="highlight"><pre><code class="language-text" data-lang="text">x y z
a
b; c
d
x y z { a; b; c; d }</code></pre></figure>
<p>Suites may begin on the same line as their colon. Any indented
subsequent lines become children of the portion after the colon,
rather than the portion before.</p>
<p>This example:</p>
<figure class="highlight"><pre><code class="language-racket" data-lang="racket"><span class="nv">x</span> <span class="nv">y</span> <span class="nv">z:</span> <span class="nv">a</span> <span class="nv">b</span>
<span class="nv">c</span> <span class="nv">d</span>
<span class="nv">e</span></code></pre></figure>
<p>reads as</p>
<figure class="highlight"><pre><code class="language-racket" data-lang="racket"><span class="p">(</span><span class="nf">x</span> <span class="nv">y</span> <span class="nv">z</span> <span class="p">(</span><span class="nf">block</span> <span class="p">(</span><span class="nf">a</span> <span class="nv">b</span> <span class="p">(</span><span class="nf">block</span> <span class="p">(</span><span class="nf">c</span> <span class="nv">d</span><span class="p">)</span> <span class="nv">e</span><span class="p">))))</span></code></pre></figure>
<p>Square brackets are syntactic sugar for a <code class="language-plaintext highlighter-rouge">#%seq</code> macro:</p>
<figure class="highlight"><pre><code class="language-text" data-lang="text">[a; b; c; d e f] → (#%seq a b c (d e f))
[ → (#%seq a (b (block c)) (d e f))
a
b
c
d e f
]</code></pre></figure>
<p>Forms starting with <code class="language-plaintext highlighter-rouge">block</code> in expression context expand into
<code class="language-plaintext highlighter-rouge">match-lambda*</code> like this:</p>
<figure class="highlight"><pre><code class="language-racket" data-lang="racket"><span class="p">{</span>
<span class="nv">pat1a</span> <span class="nv">pat1b</span>
<span class="nv">exp1a</span>
<span class="nv">exp1b</span>
<span class="nv">pat2a</span>
<span class="nv">exp2</span>
<span class="p">}</span>
<span class="nv">→</span> <span class="p">(</span><span class="nf">match-lambda*</span>
<span class="p">[(</span><span class="nb">list</span> <span class="nv">pat1a</span> <span class="nv">pat1b</span><span class="p">)</span> <span class="nv">exp1a</span> <span class="nv">exp1b</span><span class="p">]</span>
<span class="p">[(</span><span class="nb">list</span> <span class="nv">pat2a</span><span class="p">)</span> <span class="nv">exp2</span><span class="p">])</span></code></pre></figure>
<p>The <code class="language-plaintext highlighter-rouge">map*</code> function exported from <code class="language-plaintext highlighter-rouge">something/base</code> differs from <code class="language-plaintext highlighter-rouge">map</code>
in <code class="language-plaintext highlighter-rouge">racket/base</code> in that it takes its arguments in the opposite order,
permitting maps to be written</p>
<figure class="highlight"><pre><code class="language-text" data-lang="text">map* [1; 2; 3; 4]
item:
item + 1
map* [1; 2; 3; 4]
item: item + 1
map* [1; 2; 3; 4]: item: item + 1
map* [1; 2; 3; 4] { item: item + 1 }</code></pre></figure>
<p>A nice consequence of all of the above is that curried functions have
an interesting appearance:</p>
<figure class="highlight"><pre><code class="language-text" data-lang="text">def curried x:: y:: z:
[x; y; z]
require rackunit
check-equal? (((curried 1) 2) 3) [1; 2; 3]</code></pre></figure>
<p>A few more links:</p>
<ul>
<li>
<p><a href="https://github.com/tonyg/racket-something">The repository</a></p>
</li>
<li><code class="language-plaintext highlighter-rouge">#lang something/shell</code> in action: <a href="https://asciinema.org/a/83450">https://asciinema.org/a/83450</a></li>
<li><a href="https://github.com/tonyg/racket-something/blob/4a00a9a6d37777f5aab4f28b03c53555b87e21d7/src/something/shell.rkt">Implementation of <code class="language-plaintext highlighter-rouge">#lang something/shell</code></a></li>
<li><a href="https://github.com/tonyg/racket-something/blob/4a00a9a6d37777f5aab4f28b03c53555b87e21d7/examples/sh.rkt">An example “shell script”</a></li>
</ul>
<p>Another small example “shell script”, which I used while working on the module today:</p>
<figure class="highlight"><pre><code class="language-racket" data-lang="racket"><span class="o">#</span><span class="nv">lang</span> <span class="nv">something/shell</span>
<span class="nv">def</span> <span class="nv">in-hashlang?</span> <span class="nv">re</span> <span class="nv">::</span> <span class="nv">source-filename</span>
<span class="nv">zero?</span> <span class="p">(</span><span class="nf">cat</span> <span class="nv">source-filename</span> <span class="nv">|</span> <span class="nv">grep</span> <span class="nv">-Eq</span> <span class="p">(</span><span class="nb">format</span> <span class="s">"^#lang.*(~a).*"</span> <span class="nv">re</span><span class="p">))</span>
<span class="p">(</span><span class="nf">find</span> <span class="s">"."</span> <span class="nv">-iname</span> <span class="s">"*.rkt"</span>
<span class="nv">|</span> <span class="nv">port->lines</span>
<span class="nv">|></span> <span class="nv">filter</span> <span class="p">(</span><span class="nf">in-hashlang?</span> <span class="s">"something"</span><span class="p">)</span>
<span class="nv">|></span> <span class="nv">ag</span> <span class="nv">-F</span> <span class="s">"parameterize"</span><span class="p">)</span></code></pre></figure>
No royal road to optics: Functor, Applicative, Monoidal2018-12-30T11:21:40+00:00http://eighty-twenty.org/2018/12/30/typeclassopediatonyg<p>Yesterday, I became inspired to learn about the kinds of generalized,
pure-functional getters and setters that the FP community calls
“<a href="http://hackage.haskell.org/package/lens">optics</a>”: Lenses, Prisms,
Folds, Traversals, and so on.</p>
<p>I quickly realised that I needed to brush up on some of the core
typeclasses involved, namely Functor and Applicative. I spent the rest
of the day reading up on the laws and definitions involved.</p>
<p>Brent Yorgey’s
<a href="https://wiki.haskell.org/Typeclassopedia">Typeclassopedia</a> and Miran
Lipovača’s
<a href="http://learnyouahaskell.com/functors-applicative-functors-and-monoids">Learn You A Haskell</a>
were both great starting points. The latter for the basics, some good
examples, and lots of context-setting and motivation, and the former
for completeness, concision, and connections to the other foundational
ideas in the Haskell standard library.</p>
<h3 id="applicative-laws-vs-monoidal-laws">Applicative laws vs. Monoidal laws</h3>
<p>The
<a href="https://wiki.haskell.org/Typeclassopedia#Laws_2">laws for Applicative functors</a>
are complicated, and have obscure, largely unhelpful<sup id="fnref:to-programmers-anyway" role="doc-noteref"><a href="#fn:to-programmers-anyway" class="footnote" rel="footnote">1</a></sup> names like
“homomorphism” and “interchange”.</p>
<p>The
<a href="https://wiki.haskell.org/Typeclassopedia#Alternative_formulation">laws for Monoidal functors</a>
are simple and familiar: just left and right identity, and an
associativity law.</p>
<p>However, each set of laws implies the other!</p>
<p>The two formulations are equivalent. I spent most of yesterday evening
proving this, as suggested by
<a href="https://wiki.haskell.org/Typeclassopedia#Alternative_formulation">the exercises</a>
in the Typeclassopedia section dealing with Monoidal functors.</p>
<p>The main thing I learned from this exercise is that <em>the Applicative
laws are self-contained</em>. They imply the Functor laws, the Monoidal
laws, and the “naturality” law all by themselves. By contrast, the
Monoidal laws are <em>not</em> self-contained: in order to derive the
Applicative laws, you need appeal to the Functor and “naturality” laws
from time to time.</p>
<p>On the one hand, the Applicative laws are ugly, but self-contained. On
the other hand, the Monoidal laws are cleanly factored and separate
from the Functor laws. But on the gripping hand, programming with
Applicative is reported to be much less of a pain than programming
with Monoidal. I believe it!</p>
<p>All this suggests that choosing the Applicative formulation over the
Monoidal one makes sense when designing a language’s standard library.</p>
<p>After all, proving that an instance of Applicative respects the laws
can be done either in terms of the Applicative laws or the
Functor+Monoidal laws, meaning that not only does the programmer have
the better API, but the implementor has a free choice of “proof API”
when discharging their proof obligations.</p>
<h3 id="a-handy-lemma">A handy lemma</h3>
<p>Another result of working through the proofs was discovery of this
handy lemma:</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>pure f <*> u <*> pure h = pure (flip f) <*> pure h <*> u
</code></pre></div></div>
<p>It’s intuitively obvious, and something that I think many users of
Applicative will rely on, but it took a bit of thinking to realise I
needed it, and a little more thinking to get the proof to go through.</p>
<p>(Exercise: Imagine replacing <code class="language-plaintext highlighter-rouge">pure h</code> with <code class="language-plaintext highlighter-rouge">v</code>. Why does the new
statement not hold?)</p>
<h3 id="onward-to-foldable-traversable-lens-and-prism">Onward to Foldable, Traversable, Lens and Prism</h3>
<p>I think today I’ll read the rest of the Typeclassopedia, with
particular focus on Foldable and Traversable. If I have time, I’ll get
started on Lens.</p>
<div class="footnotes" role="doc-endnotes">
<ol>
<li id="fn:to-programmers-anyway" role="doc-endnote">
<p>The names make sense in light of their
category-theoretic origins. I’m not well-versed in this stuff, so
for me they are only vaguely suggestive. <a href="#fnref:to-programmers-anyway" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
</ol>
</div>
Lying to TCP makes it a best-effort streaming protocol2018-02-01T11:51:18+00:00http://eighty-twenty.org/2018/02/01/lying-to-tcptonyg<p>In
<a href="http://allthingslinguistic.com/post/170321247615">this All Things Linguistic post</a>
Gretchen and Lauren introduce a model dialogue:</p>
<blockquote>
<p>G: “Would you like some coffee?”<br />
L: “Coffee would keep me awake.”</p>
</blockquote>
<p>This might mean Lauren wants coffee—or that she doesn’t want coffee!
Her reply on its own is ambiguous. It must be interpreted in a wider
context. The <a href="http://allthingslinguistic.com/post/170321247615">post</a> digs into the dialogue more
deeply.</p>
<p>In linguistics, the
<a href="https://en.wikipedia.org/wiki/Cooperative_principle">Cooperative Principle</a>
can be used to set up a frame within which utterances like these can
be interpreted.</p>
<p><strong>Network protocols are just the same.</strong> Utterances—packets sent
along the wire—must be interpreted using a similar <em>assumption of
cooperation</em>. And, just as in human conversation, an utterance can
have a deeper, more ambiguous meaning than it seems on its face.</p>
<h3 id="acknowledgements-in-tcp">Acknowledgements in TCP</h3>
<p>In TCP, the “ack” field contains a sequence number that is supposed to
be used by a receiving peer to signal the sending peer that bytes
up-to-but-not-including that sequence number have been safely received.</p>
<p>If it’s used that way, it makes TCP a reliable, in-order protocol.</p>
<h3 id="lying-to-the-sending-tcp">Lying to the sending TCP</h3>
<p>But imagine a receiver that didn’t very much care about reliability
beyond that offered by the underlying transport. For example, a VOIP
receiver, where delayed or lost voice packets are useless, and in fact
harmful if carried over TCP because they delay packets travelling
behind them, causing the whole conversation to get more and more
delayed.</p>
<p>That receiver could <em>lie</em>. It could use the “ack” sequence number field
to indicate which bytes it <em>no longer cared about</em>.</p>
<p>In effect, it would ignore lost packets, and use the “ack” field to
tell the sender not to bother retransmitting them.<sup id="fnref:fiddly-details" role="doc-noteref"><a href="#fn:fiddly-details" class="footnote" rel="footnote">1</a></sup></p>
<p>That decision would make TCP a best-effort, in-order protocol.</p>
<h3 id="is-it-really-a-lie">Is it really a lie?</h3>
<p>Seen one way, this abuse of the “ack” field isn’t a lie. In both cases,
the receiver doesn’t care about the bytes anymore: on the one hand,
because they’ve been received successfully; on the other, because
they’re irrelevant now.</p>
<p>It’s similar to the ambiguity about the coffee in the example above.</p>
<p>The surface meaning is clear. The deeper meaning depends on knowledge
about the wider context that isn’t carried in the utterance itself.</p>
<h3 id="we-can-assume-cooperation-without-assuming-motivation">We can assume cooperation without assuming motivation</h3>
<p>The statement “Don’t send me bytes numbered lower than X” can be
interpreted either as “I have received all bytes numbered lower than X”
or “I no longer care about bytes numbered lower than X”. Only context
can tell them apart.</p>
<p>.</p>
<p>.</p>
<hr />
<p>PS. My dissertation proposes <a href="http://syndicate-lang.org/">Syndicate</a>,
a design for new programming language features for concurrency.
Syndicate incorporates ideas about conversation and cooperativity like
those discussed here. (See, in particular,
<a href="http://syndicate-lang.org/tonyg-dissertation/html/#CHAP:PHILOSOPHY-AND-OVERVIEW">chapter 2</a>
of the dissertation.) It’s still early days, but I’ve put up a
resource page at <a href="http://syndicate-lang.org/tonyg-dissertation/">http://syndicate-lang.org/tonyg-dissertation/</a> that
has the dissertation itself, a video of the defense talk I gave, and a
few other resources.</p>
<div class="footnotes" role="doc-endnotes">
<ol>
<li id="fn:fiddly-details" role="doc-endnote">
<p>Of course, I’m ignoring fiddly details like
segment boundaries, interactions between this strategy and flow-
and congestion-control, and so on. It’d take a lot of work to
really do this! <a href="#fnref:fiddly-details" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
</ol>
</div>
PhD Dissertation: Conversational Concurrency2018-01-24T12:57:22+00:00http://eighty-twenty.org/2018/01/24/conversational-concurrencytonyg<p>I’ve put up a webpage,
<a href="http://syndicate-lang.org/tonyg-dissertation/">http://syndicate-lang.org/tonyg-dissertation/</a>, which gathers
together a number of resources related to my recently-completed PhD
project:</p>
<ul>
<li>The dissertation itself, in both PDF and online HTML;</li>
<li>A video recording of my dissertation defense talk;</li>
<li>The slides I used for my talk;</li>
<li>A source code snapshot of the Syndicate implementations and examples; and</li>
<li>The proof scripts accompanying the dissertation.</li>
</ul>
<p>Syndicate is a programming language design taking a new approach to
communication and coordination in a concurrent setting.</p>
<p>It can be seen as a hybrid between Actor-style message-passing and
tuplespace-style shared-blackboard communication, with some
characteristics of each plus a few unique ones of its own.</p>
<p><a href="http://syndicate-lang.org/tonyg-dissertation/">Click through</a> for the
abstract from the dissertation.</p>
History of Actors2016-10-18T19:30:38+00:00http://eighty-twenty.org/2016/10/18/actors-hopltonyg<p>Yesterday, I presented the history of actors to Christos Dimoulas’
<a href="http://www.seas.harvard.edu/courses/cs252/2016fa/">History of Programming Languages</a>
class.</p>
<p>Here are the written-out talk notes I prepared beforehand. There is an
annotated bibliography at the end.</p>
<hr />
<h2 id="introduction">Introduction</h2>
<p>Today I’m going to talk about the actor model. I’ll first put the
model in context, and then show three different styles of actor
language, including two that aim to be realistic programming systems.</p>
<p>I’m going to draw on a few papers:</p>
<ul>
<li>
<p>2016 survey by Joeri De Koster, Tom Van Cutsem, and Wolfgang De
Meuter, for taxonomy and common terminology (SPLASH AGERE 2016)</p>
</li>
<li>
<p>1990 overview by Gul Agha, who has contributed hugely to the study
of actors (Comm. ACM 1990)</p>
</li>
<li>
<p>1997 operational semantics for actors by Gul Agha, Ian Mason, Scott
Smith, and Carolyn Talcott.</p>
</li>
<li>
<p>brief mention of some of the content of the original 1973 paper by
Carl Hewitt, Peter Bishop, and Richard Steiger. (IJCAI 1973)</p>
</li>
<li>
<p>Joe Armstrong’s 2003 dissertation on Erlang.</p>
</li>
<li>
<p>2005 paper on the language E by Mark Miller, Dean Tribble, and
Jonathan Shapiro. (TGC 2005)</p>
</li>
</ul>
<p>I’ve put an annotated bibliography at the end of this file.</p>
<h2 id="actors-in-context-approaches-to-concurrent-programming">Actors in context: Approaches to concurrent programming</h2>
<p>One way of classifying approaches is along a spectrum of private vs.
shared state.</p>
<ul>
<li>Shared memory, threads, and locking: very limited private state, almost all shared</li>
<li>Tuple spaces and my own research, Syndicate: some shared, some private and isolated</li>
<li>Actors: almost all private and isolated, just enough shared to do routing</li>
</ul>
<p>Pure functional “data parallelism” doesn’t fit on this chart - it
lacks shared mutable state entirely.</p>
<h2 id="the-actor-model">The actor model</h2>
<p>The actor model, then is</p>
<ul>
<li>asynchronous message passing between entities (actors)
<ul>
<li>with guaranteed delivery</li>
<li>addressing of messages by actor identity</li>
</ul>
</li>
<li>a thing called the “ISOLATED TURN PRINCIPLE”
<ul>
<li>no shared mutable state; strong encapsulation; no global mutable state</li>
<li>no interleaving; process one message at a time; serializes state access</li>
<li>liveness; no blocking</li>
</ul>
</li>
</ul>
<p>In the model, each actor performs “turns” one after the other: a turn
is taking a waiting message, interpreting it, and deciding on both a
state update for the actor and a collection of actions to take in
response, perhaps sending messages or creating new actors.</p>
<p>A turn is a sequential, atomic block of computation that happens in
response to an incoming message.</p>
<p>What the actor model buys you:</p>
<ul>
<li>
<p>modular reasoning about state in the overall system, and modular
reasoning about local state change within an actor, because state
is private, and access is serialized; only have to consider
interleavings of messages</p>
</li>
<li>
<p>no “deadlocks” or data races (though you can get “datalock” and
other global non-progress in some circumstances, from logical
inconsistency and otherwise)</p>
</li>
<li>
<p>flexible, powerful capability-based security</p>
</li>
<li>
<p>failure isolation and fault tolerance</p>
</li>
</ul>
<p>It’s worth remarking that actor-like concepts have sprung up several
times independently. Hewitt and many others invented and developed
actors in the 1970s, but there are two occasions where actors seem to
have been independently reinvented, as far as I know.</p>
<p>One is work on a capability-based operating system, KeyKOS, in the
1980s which involved a design very much like Hewitt’s actors, feeding
into research which led ultimately to the language E.</p>
<p>The other is work on highly fault-tolerant designs for telephone
switches, also in the 1980s, which culminated in the language Erlang.</p>
<p>Both languages are clearly actor languages, and in both cases,
apparently the people involved were unaware of Hewitt’s actor model at
the time.</p>
<h2 id="terminology">Terminology</h2>
<p>There are two kinds of things in the actor model: <em>messages</em>, which
are data sent across some medium of communication, and <em>actors</em>, which
are stateful entities that can only affect each other by sending
messages back and forth.</p>
<p>Messages are completely immutable data, passed by copy, which may
contain references to other actors.</p>
<p>Each actor has</p>
<ul>
<li>private state; analogous to instance variables</li>
<li>an interface; which messages it can respond to</li>
</ul>
<p>Together, the private state and the interface make up the actor’s
<em>behaviour</em>, a key term in the actor literature.</p>
<p>In addition, each actor has</p>
<ul>
<li>a mailbox; inbox, message queue</li>
<li>an address; denotes the mailbox</li>
</ul>
<p>Within this framework, there has been quite a bit of variety in how
the model appears as a concrete programming language.</p>
<p>De Koster et al. classify actor languages into</p>
<ul>
<li>The Classic Actor Model (create, send, become)</li>
<li>Active Objects (OO with a thread per object; copying of passive data between objects)</li>
<li>Processes (raw Erlang; receive, spawn, send)</li>
<li>Communicating Event-Loops (no passive data; E; near/far refs; eventual refs; batching)</li>
</ul>
<p>We see instances of the actor model all around us. The internet’s IP
network is one example: hosts are the actors, and datagrams the
messages. The web can be seen as another: a URL denotes an actor, and
an HTTP request a message. Seen in a certain light, even Unix
processes are actor-like (when they’re single threaded, if they only
use fds and not shm). It can be used as a structuring principle for a
system architecture even in languages like C or C++ that have no hope
of enforcing any of the invariants of the model.</p>
<h2 id="rest-of-the-talk">Rest of the talk</h2>
<p>For the rest of the talk, I’m going to cover the classic actor model
using Agha’s presentations as a guide; then I’ll compare it to E, a
communicating event-loop actor language, and to Erlang, a process
actor language.</p>
<h2 id="classic-actor-model">Classic Actor Model</h2>
<p>The original 1973 actor paper by Hewitt, Bishop and Steiger in the
International Joint Conference on Artificial Intelligence, is
incredibly far out!</p>
<p>It’s a position paper that lays out a broad and colourful research
vision. It’s packed with amazing ideas.</p>
<p>The heart of it is that Actors are proposed as a universal programming
language formalism ideally suited to building artificial intelligence.</p>
<p>The goal really was A.I., and actors and programming languages were a
means to that end.</p>
<p>It makes these claims that actors bring great benefits in a huge range
of areas:</p>
<ul>
<li>foundations of semantics</li>
<li>logic</li>
<li>knowledge-based programming</li>
<li>intentions (software contracts)</li>
<li>study of expressiveness of programming languages</li>
<li>teaching of computation</li>
<li>extensible, modular programming</li>
<li>privacy and protection</li>
<li>synchronization constructs</li>
<li>resource management</li>
<li>structured programming</li>
<li>computer architecture</li>
</ul>
<p>(It’s amazingly “full-stack”: computer architecture!?)</p>
<p>In each of these areas, you can see what they were going for. In some,
actors have definitely been useful; in others, the results have been
much more modest.</p>
<p>In the mid-to-late 70s, Hewitt and his students Irene Greif, Henry
Baker, and Will Clinger developed a lot of the basic theory of the
actor model, inspired originally by SIMULA and Smalltalk-71. Irene
Greif developed the first operational semantics for it as her
dissertation work and Will Clinger developed a denotational semantics
for actors.</p>
<p>In the late 70s through the 80s and beyond, Gul Agha made huge
contributions to the actor theory. His dissertation was published as a
book on actors in 1986 and has been very influential. He separated the
actor model from its A.I. roots and started treating it as a more
general programming model. In particular, in his 1990 Comm. ACM paper,
he describes it as a foundation for CONCURRENT OBJECT-ORIENTED
PROGRAMMING.</p>
<p>Agha’s formulation is based around the three core operations of the
classic actor model:</p>
<ul>
<li><code class="language-plaintext highlighter-rouge">create</code>: constructs a new actor from a template and some parameters</li>
<li><code class="language-plaintext highlighter-rouge">send</code>: delivers a message, asynchronously, to a named actor</li>
<li><code class="language-plaintext highlighter-rouge">become</code>: within an actor, replaces its behaviour (its state & interface)</li>
</ul>
<p>The classic actor model is a UNIFORM ACTOR MODEL, that is, everything
is an actor. Compare to uniform object models, where everything is an
object. By the mid-90s, that very strict uniformity had fallen out of
favour and people often worked with <em>two-layer</em> languages, where you
might have a functional core language, or an object-oriented core
language, or an imperative core language with the actor model part
being added in to the base language.</p>
<p>I’m going to give a simplified, somewhat informal semantics based on
his 1997 work with Mason, Smith and Talcott. I’m going to drop a lot
of details that aren’t relevant here so this really will be
simplified.</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>e := λx.e | e e | x | (e,e) | l | ... atoms, if, bool, primitive operations ...
| create e
| send e e
| become e
l labels, PIDs; we'll use them like symbols here
</code></pre></div></div>
<p>and we imagine convenience syntax</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>e1;e2 to stand for (λdummy.e2) e1
let x = e1 in e2 to stand for (λx.e2) e1
match e with p -> e, p -> e, ...
to stand for matching implemented with if, predicates, etc.
</code></pre></div></div>
<p>We forbid programs from containing literal process IDs.</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>v := λx.e | (v,v) | l
R := [] | R e | v R | (R,e) | (v,R)
| create R
| send R e | send v R
| become R
</code></pre></div></div>
<p>Configurations are a pair of a set of actors and a multiset of
messages:</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>m := l <-- v
A := (v)l | [e]l
C := < A ... | m ... >
</code></pre></div></div>
<p>The normal lambda-calculus-like reductions apply, like beta:</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code> < ... [R[(λx.e) v]]l ... | ... >
--> < ... [R[e{v/x} ]]l ... | ... >
</code></pre></div></div>
<p>Plus some new interesting ones that are actor specific:</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code> < ... (v)l ... | ... l <-- v' ... >
--> < ... [v v']l ... | ... ... >
< ... [R[create v]]l ... | ... >
--> < ... [R[l' ]]l (v)l' ... | ... > where l' fresh
< ... [R[send l' v]]l ... | ... >
--> < ... [R[l' ]]l ... | ... l' <-- v >
< ... [R[become v]]l ... | ... >
--> < ... [R[nil ]]l' (v)l ... | ... > where l' fresh
</code></pre></div></div>
<p>Whole programs <code class="language-plaintext highlighter-rouge">e</code> are started with</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>< [e]a | >
</code></pre></div></div>
<p>where <code class="language-plaintext highlighter-rouge">a</code> is an arbitrary label.</p>
<p>Here’s an example - a mutable cell.</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>Cell = λcontents . λmessage . match message with
(get, k) --> become (Cell contents);
send k contents
(put, v) --> become (Cell v)
</code></pre></div></div>
<p>Notice that when it gets a <code class="language-plaintext highlighter-rouge">get</code> message, it first performs a <code class="language-plaintext highlighter-rouge">become</code>
in order to quickly return to <code class="language-plaintext highlighter-rouge">ready</code> state to handle more messages.
The remainder of the code then runs alongside the ready actor. Actions
after a <code class="language-plaintext highlighter-rouge">become</code> can’t directly affect the state of the actor anymore,
so even though we have what looks like multiple concurrent executions
of the actor, there’s no sharing, and so access to the state is still
serialized, as needed for the isolated turn principle.</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>< [let c = create (Cell 0) in
send c (get, create (λv . send c (put, v + 1)))]a | >
< [let c = l1 in
send c (get, create (λv . send c (put, v + 1)))]a
(Cell 0)l1 | >
< [send l1 (get, create (λv . send l1 (put, v + 1)))]a
(Cell 0)l1 | >
< [send l1 (get, l2)]a
(Cell 0)l1
(λv . send l1 (put, v + 1))l2 | >
< [l1]a
(Cell 0)l1
(λv . send l1 (put, v + 1))l2 | l1 <-- (get, l2) >
< [l1]a
[Cell 0 (get, l2)]l1
(λv . send l1 (put, v + 1))l2 | >
< [l1]a
[become (Cell 0); send l2 0]l1
(λv . send l1 (put, v + 1))l2 | >
< [l1]a
[send l2 0]l3
(Cell 0)l1
(λv . send l1 (put, v + 1))l2 | >
< [l1]a
[l2]l3
(Cell 0)l1
(λv . send l1 (put, v + 1))l2 | l2 <-- 0 >
< [l1]a
[l2]l3
(Cell 0)l1
[send l1 (put, 0 + 1)]l2 | >
< [l1]a
[l2]l3
(Cell 0)l1
[l1]l2 | l1 <-- (put, 1) >
< [l1]a
[l2]l3
[Cell 0 (put, 1)]l1
[l1]l2 | >
< [l1]a
[l2]l3
[become (Cell 1)]l1
[l1]l2 | >
< [l1]a
[l2]l3
[nil]l4
(Cell 1)l1
[l1]l2 | >
</code></pre></div></div>
<p>(You could consider adding a garbage collection rule like</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code> < ... [v]l ... | ... >
--> < ... ... | ... >
</code></pre></div></div>
<p>to discard the final value at the end of an activation.)</p>
<p>Because at this level all the continuations are explicit, you can
encode patterns other than sequential control flow, such as fork-join.</p>
<p>For example, to start two long-running computations in parallel, and
collect the answers in either order, multiplying them and sending the
result to some actor k’, you could write</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>let k = create (λv1 . become (λv2 . send k' (v1 * v2))) in
send task1 (req1, k);
send task2 (req2, k)
</code></pre></div></div>
<p>Practically speaking, both Hewitt’s original actor language, PLASMA,
and the language Agha uses for his examples in the 1990 paper,
Rosette, have special syntax for ordinary RPC so the programmer
needn’t manipulate continuations themselves.</p>
<p>So that covers the classic actor model. Create, send and become.
Explicit use of actor addresses, and lots and lots of temporary actors
for inter-actor RPC continuations.</p>
<p>Before I move on to Erlang: remember right at the beginning I told you
the actor model was</p>
<ul>
<li>asynchronous message passing, and</li>
<li>the isolated turn principle</li>
</ul>
<p>?</p>
<p>The isolated turn principle requires <em>liveness</em> - you’re not allowed
to block indefinitely while responding to a message!</p>
<p>But here, we can:</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>let d = create (λc . send c c) in
send d d
</code></pre></div></div>
<p>Compare this with</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>letrec beh = (λc . become beh; send c c) in
let d = create beh in
send d d
</code></pre></div></div>
<p>These are both degenerate cases, but in different ways: the first
becomes inert very quickly and the actor <code class="language-plaintext highlighter-rouge">d</code> is never returned to an
idle/ready state, while the second spins uselessly forever.</p>
<p>Other errors we could make would be to fail to send an expected reply
to a continuation.</p>
<p>One thing the semantics here rules out is interaction with other
actors before doing a <code class="language-plaintext highlighter-rouge">become</code>; there’s no way to have a waiting
continuation perform the <code class="language-plaintext highlighter-rouge">become</code>, because by that time you’re in a
different actor. In this way, it sticks to the very letter of the
Isolated Turn Principle, by forbidding “blocking”, but there are other
kinds of things that can go wrong to destroy progress.</p>
<p>Even if we require our behaviour functions to be total, we can still
get <em>global</em> nontermination.</p>
<p>So saying that we “don’t have deadlock” with the actor model is very
much oversimplified, even at the level of simple formal models, let
alone when it comes to realistic programming systems.</p>
<p>In practice, programmers often need “blocking” calls out to other
actors before making a state update; with the classic actor model,
this can be done, but it is done with a complicated encoding.</p>
<h2 id="erlang-actors-for-fault-tolerant-systems">Erlang: Actors for fault-tolerant systems</h2>
<p>Erlang is an example of what De Koster et al. call a Process-based
actor language.</p>
<p>It has its origins in telephony, where it has been used to build
telephone switches with fabled “nine nines” of uptime. The research
process that led to Erlang concentrated on high-availability,
fault-tolerant software. The reasoning that led to such an actor-like
system was, in a nutshell:</p>
<ul>
<li>
<p>Programs have bugs. If part of the program crashes, it shouldn’t
corrupt other parts. Hence strong isolation and shared-nothing
message-passing.</p>
</li>
<li>
<p>If part of the program crashes, another part has to take up the
slack, one way or another. So we need crash signalling so we can
detect failures and take some action.</p>
</li>
<li>
<p>We can’t have all our eggs in one basket! If one machine fails at
the hardware level, we need to have a nearby neighbour that can
smoothly continue running. For that redundancy, we need
distribution, which makes the shared-nothing message passing extra
attractive as a unifying mechanism.</p>
</li>
</ul>
<p>Erlang is a two-level system, with a functional language core equipped
with imperative actions for asynchronous message send and spawning new
processes, like Agha’s system.</p>
<p>The difference is that it lacks <code class="language-plaintext highlighter-rouge">become</code>, and instead has a construct
called <code class="language-plaintext highlighter-rouge">receive</code>.</p>
<p>Erlang actors, called processes, are ultra lightweight threads that
run sequentially from beginning to end as little functional programs.
As it runs, no explicit temporary continuation actors are created: any
time it uses receive, it simply blocks until a matching message
appears.</p>
<p>After some initialization steps, these programs typically enter a
message loop. For example, here’s a mutable cell:</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>mainloop(Contents) ->
receive
{get, K} -> K ! Contents,
mainloop(Contents);
{put, V} -> mainloop(V)
end.
</code></pre></div></div>
<p>A client program might be</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>Cell = spawn(fun mainloop(0) end),
Cell ! {get, self()},
receive
V -> ...
end.
</code></pre></div></div>
<p>Instead of using <code class="language-plaintext highlighter-rouge">become</code>, the program performs a tail call which
returns to the <code class="language-plaintext highlighter-rouge">receive</code> statement as the last thing it does.</p>
<p>Because <code class="language-plaintext highlighter-rouge">receive</code> is a statement like any other, Erlang processes can
use it to enter substates:</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>mainloop(Service) ->
receive
{req, K} -> Service ! {subreq, self()},
receive
{subreply, Answer} -> K ! {reply, Answer},
mainloop(Service)
end
end.
</code></pre></div></div>
<p>While the process is blocked on the inner <code class="language-plaintext highlighter-rouge">receive</code>, it only processes
messages matching the patterns in that inner receive, and it isn’t
until it does the tail call back to <code class="language-plaintext highlighter-rouge">mainloop</code> that it starts waiting
for <code class="language-plaintext highlighter-rouge">req</code> messages again. In the meantime, non-matched messages queue
up waiting to be <code class="language-plaintext highlighter-rouge">receive</code>d later.</p>
<p>This is called “selective receive” and it is difficult to reason
about. It doesn’t <em>quite</em> violate the letter of the Isolated Turn
Principle, but it comes close. (<code class="language-plaintext highlighter-rouge">become</code> can be used in a similar
way.)</p>
<p>The goal underlying “selective receive”, namely changing the set of
messages one responds to and temporarily ignoring others, is important
for the way people think about actor systems, and a lot of research
has been done on different ways of selectively enabling message
handlers. See Agha’s 1990 paper for pointers toward this research.</p>
<p>One unique feature that Erlang brings to the table is crash
signalling. The jargon is “links” and “monitors”. Processes can ask
the system to make sure to send them a message if a monitored process
exits. That way, they can perform RPC by</p>
<ul>
<li>monitoring the server process</li>
<li>sending the request</li>
<li>if a reply message arrives, unmonitor the server process and continue</li>
<li>if an exit message arrives, the service has crashed; take some
corrective action.</li>
</ul>
<p>This general idea of being able to monitor the status of some other
process was one of the seeds of my own research and my language
Syndicate.</p>
<p>So while the classic actor model had create/send/become as primitives,
Erlang has spawn/send/receive, and actors are processes rather than
event-handler functions. The programmer still manipulates references
to actors/processes directly, but there are far fewer explicit
temporary actors created compared to the “classic model”; the ordinary
continuations of Erlang’s functional fragment take on those duties.</p>
<h2 id="e-actors-for-secure-cooperation">E: actors for secure cooperation</h2>
<p>The last language I want to show you, E, is an example of what De
Koster et al. call a Communicating Event-Loop language.</p>
<p>E looks and feels much more like a traditional object-oriented
language to the programmer than either of the variations we’ve seen so
far.</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>def makeCell (var contents) {
def getter {
to get() { return contents }
}
def setter {
to set(newContents) {
contents := newContents
}
}
return [getter, setter]
}
</code></pre></div></div>
<p>The mutable cell in E is interestingly different: It yields <em>two</em>
values. One specifically for setting the cell, and one for getting it.
E focuses on security and securability, and encourages the programmer
to hand out objects that have the minimum possible authority needed to
get the job done. Here, we can safely pass around references to
<code class="language-plaintext highlighter-rouge">getter</code> without risking unauthorized update of the cell.</p>
<p>E uses the term “vat” to describe the concept closest to the
traditional actor. A vat has not only a mailbox, like an actor, but
also a call stack, and a heap of local objects. As we’ll see, E
programmers don’t manipulate references to vats directly. Instead,
they pass around references to objects in a vat’s heap.</p>
<p>This is interesting because in the actor model messages are addressed
to a particular actor, but here we’re seemingly handing out references
to something finer grained: to individual objects <em>within</em> an actor or
vat.</p>
<p>This is the first sign that E, while it uses the basic
create/send/become-style model at its core, doesn’t expose that model
directly to the programmer. It layers a special E-specific protocol on
top, and only lets the programmer use the features of that upper layer
protocol.</p>
<p>There are two kinds of references available: near refs, which
definitely point to objects in the local vat, and far refs, which may
point to objects in a different vat, perhaps on another machine.</p>
<p>To go with these two kinds of refs, there are two kinds of method
calls: <em>immediate</em> calls, and <em>eventual</em> calls.</p>
<p>receiver.method(arg, …)</p>
<p>receiver <- method(arg, …)</p>
<p>It is an error to use an immediate call on a ref to an object in a
different vat, because it blocks during the current turn while the
answer is computed. It’s OK to use eventual calls on any ref at all,
though: it causes a message to be queued in the target vat (which
might be our own), and a <em>promise</em> is immediately returned to the
caller.</p>
<p>The promise starts off unresolved. Later, when the target vat has
computed and sent a reply, the promise will become resolved. A nifty
trick is that even an unresolved promise is useful: you can <em>pipeline</em>
them. For example,</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>def r1 := x <- a()
def r2 := y <- b()
def r3 := r1 <- c(r2)
</code></pre></div></div>
<p>would block and perform multiple network round trips in a traditional
simple RPC system; in E, there is a protocol layered on top of raw
message sending that discusses promise creation, resolution and use.
This protocol allows the system to send messages like</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>"Send a() to x, and name the resulting promise r1"
"Send b() to y, and name the resulting promise r2"
"When r1 is known, send c(r2) to it"
</code></pre></div></div>
<p>Crucial here is that the protocol, the language of discourse between
actors, allows the expression of concepts including the notion of a
send to happen at a future time, to a currently-unknown recipient.</p>
<p>The protocol and the E vat runtimes work together to make sure that
messages get to where they need to go efficiently, even in the face of
multiple layers of forwarding.</p>
<p>Each turn of an E vat involves taking one message off the message
queue, and dispatching it to the local object it denotes. Immediate
calls push stack frames on the stack as usual for object-oriented
programming languages; eventual calls push messages onto the message
queue. Execution continues until the stack is empty again, at which
point the turn concludes and the next turn starts.</p>
<p>One interesting problem with using promises to represent cross-vat
interactions is how to do control flow. Say we had</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>def r3 := r1 <- c(r2) // from earlier
if (r3) {
myvar := a();
} else {
myvar := b();
}
</code></pre></div></div>
<p>By the time we need to make a decision which way to go, the promise r3
may not yet be resolved. E handles this by making it an error to
depend immediately on the value of a promise for control flow;
instead, the programmer uses a <code class="language-plaintext highlighter-rouge">when</code> expression to install a handler
for the event of the resolution of the promise:</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>when (r3) -> {
if (r3) {
myvar := a();
} else {
myvar := b();
}
}
</code></pre></div></div>
<p>The test of r3 and the call to a() or b() and the update to myvar are
<em>delayed</em> until r3 has resolved to some value.</p>
<p>This looks like it violates the Isolated Turn Principle! It seems like
we now have some kind of interleaving. But what’s going on under the
covers is that promise resolution is done with an incoming message,
queued as usual, and when that message’s turn comes round, the when
clause will run.</p>
<p>Just like with classic actors and with Erlang, managing these
multiple-stage, stateful interactions in response to some incoming
message is generally difficult to do. It’s a question of finding a
balance between the Isolated Turn Principle, and its commitment to
availability, and encoding the necessary state transitions without
risking inconsistency or deadlock.</p>
<p>Turning to failure signalling, E’s vats are not just the units of
concurrency but also the units of partial failure. An uncaught
exception within a vat destroys the whole vat and invalidates all
remote references to objects within it.</p>
<p>While in Erlang, processes are directly notified of failures of other
processes as a whole, E can be more fine-grained. In E, the programmer
has a convenient value that represents the outcome of a transaction:
the promise. When a vat fails, or a network problem arises, any
promises depending on the vat or the network link are put into a
special state: they become <em>broken promises</em>. Interacting with a
broken promise causes the contained exception to be signalled; in this
way, broken promises propagate failure along causal chains.</p>
<p>If we look under the covers, E seems to have a “classic style” model
using create/send/become to manage and communicate between whole vats,
but these operations aren’t exposed to the programmer. The programmer
instead manipulates two-part “far references” which denote a vat along
with an object local to that vat. Local objects are created
frequently, like in regular object-oriented languages, but vats are
created much less frequently; and each vat’s stack takes on duties
performed in “classic” actor models by temporary actors.</p>
<h2 id="conclusion">Conclusion</h2>
<p>I’ve presented three different types of actor language: the classic
actor model, roughly as formulated by Agha et al.; the process actor
model, represented by Erlang; and the communicating event-loop model,
represented by E.</p>
<p>The three models take different approaches to reconciling the need to
have structured local data within each actor in addition to the more
coarse-grained structure relating actors to each other.</p>
<p>The classic model makes everything an actor, with local data largely
deemphasised; Erlang offers a traditional functional programming model
for handling local data; and E offers a smooth integration between an
imperative local OO model and an asynchronous, promise-based remote OO
model.</p>
<hr />
<h2 id="annotated-bibliography">Annotated Bibliography</h2>
<h3 id="early-work-on-actors">Early work on actors</h3>
<ul>
<li>
<p><strong>1973. Carl Hewitt, Peter Bishop, and Richard Steiger, “A universal modular ACTOR formalism for artificial intelligence,” in Proc. International Joint Conference on Artificial Intelligence</strong></p>
<p>This paper is a position paper from which we can understand the
motivation and intentions of the research into actors; it lays out a
very broad and colourful research vision that touches on a huge range
of areas from computer architecture up through programming language
design to teaching of computer science and approaches to artificial
intelligence.</p>
<p>The paper presents a <em>uniform actor model</em>; compare and contrast with
uniform object models offered by (some) OO languages. The original
application of the model is given as PLANNER-like AI languages.</p>
<p>The paper claims benefits of using the actor model in a huge range of areas:</p>
<ul>
<li>foundations of semantics</li>
<li>logic</li>
<li>knowledge-based programming</li>
<li>intentions (contracts)</li>
<li>study of expressiveness</li>
<li>teaching of computation</li>
<li>extensible, modular programming</li>
<li>privacy and protection</li>
<li>synchronization constructs</li>
<li>resource management</li>
<li>structured programming</li>
<li>computer architecture</li>
</ul>
<p>The paper sketches the idea of a contract (called an “intention”) for
ensuring that invariants of actors (such as protocol conformance) are
maintained; there seems to be a connection to modern work on
“monitors” and Session Types. The authors write:</p>
<blockquote>
<p>The intention is the CONTRACT that the actor has with the outside world.</p>
</blockquote>
<p>Everything is super meta! Actors can have intentions! Intentions are
actors! Intentions can have intentions! The paper presents the
beginnings of a reflective metamodel for actors. Every actor has a
scheduler and an “intention”, and may have monitors, a first-class
environment, and a “banker”.</p>
<p>The paper draws an explicit connection to capabilities (in the
security sense); Mark S. Miller at
<a href="http://erights.org/history/actors.html">http://erights.org/history/actors.html</a> says of the Actor work that
it included “prescient” statements about Actor semantics being “a
basis for confinement, years before Norm Hardy and the Key Logic
guys”, and remarks that “the Key Logic guys were unaware of Actors and
the locality laws at the time, [but] were working from the same
intuitions.”</p>
<p>There are some great slogans scattered throughout, such as “Control
flow and data flow are inseparable”, and “Global state considered
harmful”.</p>
<p>The paper does eventually turn to a more nuts-and-bolts description of
a predecessor language to PLASMA, which is more fully described in
Hewitt 1976.</p>
<p>When it comes to formal reasoning about actor systems, the authors
here define a partial order - PRECEDES - that captures some notion of
causal connection. Later, the paper makes an excursion into epistemic
modal reasoning.</p>
<p>Aside: the paper discusses continuations; Reynolds 1993 has the
concept of continuations as firmly part of the discourse by 1973,
having been rediscovered in a few different contexts in 1970-71 after
van Wijngaarden’s 1964 initial description of the idea. See J. C.
Reynolds, “The discoveries of continuations,” LISP Symb. Comput., vol.
6, no. 3–4, pp. 233–247, 1993.</p>
<p>In the “acknowledgements” section, we see:</p>
<blockquote>
<p>Alan Kay whose FLEX and SMALL TALK machines have influenced our
work. Alan emphasized the crucial importance of using intentional
definitions of data structures and of passing messages to them. This
paper explores the consequences of generalizing the message
mechanism of SMALL TALK and SIMULA-67; the port mechanism of Krutar,
Balzer, and Mitchell; and the previous CALL statement of PLANNER-71
to a universal communications mechanism.</p>
</blockquote>
</li>
<li>
<p><strong>1975. Irene Greif. PhD dissertation, MIT EECS.</strong></p>
<p>Specification language for actors; per Baker an “operational
semantics”. Discusses “continuations”.</p>
</li>
<li>
<p><strong>1976. C. Hewitt, “Viewing Control Structures as Patterns of Passing Messages,” AIM-410</strong></p>
<p>AI focus; actors as “agents” in the AI sense; recursive decomposition:
“each of the experts can be viewed as a society that can be further
decomposed in the same way until the primitive actors of the system
are reached.”</p>
<blockquote>
<p>We are investigating the nature of the <em>communication mechanisms</em>
[…] and the conventions of discourse</p>
</blockquote>
<p>More concretely, examines “how actor message passing can be used to
understand control structures as patterns of passing messages”.</p>
<blockquote>
<p>[…] there is no way to decompose an actor into its parts. An actor
is defined by its behavior; not by its physical representation!</p>
</blockquote>
<p>Discusses PLASMA (“PLAnner-like System Modeled on Actors”), and gives
a fairly detailed description of the language in the appendix.
Develops “event diagrams”.</p>
<p>Presents very Schemely factorial implementations in recursive and
iterative (tail-recursive accumulator-passing) styles. During
discussion of the iterative factorial implementation, Hewitt remarks
that <code class="language-plaintext highlighter-rouge">n</code> is not closed over by the <code class="language-plaintext highlighter-rouge">loop</code> actor; it is “not an
acquaintance” of <code class="language-plaintext highlighter-rouge">loop</code>. Is this the beginning of the line of thinking
that led to Clinger’s “safe-for-space” work?</p>
<p>Everything is an actor, but some of the actors are treated in an
awfully structural way: the trees, for example, in section V.4 on
Generators:</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>(non-terminal:
(non-terminal: (terminal: A) (terminal: B))
(terminal: C))
</code></pre></div> </div>
<p>Things written with this <code class="language-plaintext highlighter-rouge">keyword:</code> notation look like structures.
Their <em>reflections</em> are actors, but as structures, they are subject to
pattern-matching; I am unsure how the duality here was thought of by
the principals at the time, but see the remarks regarding “packages”
in the appendix.</p>
</li>
<li>
<p><strong>1977. C. Hewitt and H. Baker, “Actors and Continuous Functionals,” MIT A.I. Memo 436A</strong></p>
<p>Some “laws” for communicating processes; “plausible restrictions on
the histories of computations that are physically realizable.”
Inspired by physical intuition, discusses the history of a computation
in terms of a partial order of events, rather than a sequence.</p>
<blockquote>
<p>The actor model is a formalization of these ideas
[of Simula/Smalltalk/CLU-like active data processing messages] that
is independent of any particular programming language.</p>
</blockquote>
<blockquote>
<p>Instances of Simula and Smalltalk classes and CLU clusters are
actors”, but they are <em>non-concurrent</em>. The actor model is broader,
including concurrent message-passing behaviour.</p>
</blockquote>
<p>Laws about (essentially) lexical scope. Laws about histories (finitude
of activation chains; total ordering of messages inbound at an actor;
etc.), including four different ordering relations. “Laws of locality”
are what Miller was referring to on that erights.org page I mentioned
above; very close to the capability laws governing confinement.</p>
<p>Steps toward denotational semantics of actors.</p>
</li>
<li>
<p><strong>1977. Russell Atkinson and Carl Hewitt, “Synchronization in actor systems,” Proc. 4th ACM SIGACT-SIGPLAN Symp. Princ. Program. Lang., pp. 267–280.</strong></p>
<p>Introduces the concept of “serializers”, a “generalization and
improvement of the monitor mechanism of Brinch-Hansen and Hoare”.
Builds on Greif’s work.</p>
</li>
<li>
<p><strong>1981. Will Clinger’s PhD dissertation. MIT</strong></p>
</li>
</ul>
<h3 id="actors-as-concurrent-object-oriented-programming">Actors as Concurrent Object-Oriented Programming</h3>
<ul>
<li>
<p><strong>1986. Gul Agha’s book/dissertation.</strong></p>
</li>
<li>
<p><strong>1990. G. Agha, “Concurrent Object-Oriented Programming,” Commun. ACM, vol. 33, no. 9, pp. 125–141</strong></p>
<p>Agha’s work recast the early “classic actor model” work in terms of
<em>concurrent object-oriented programming</em>. Here, he defines actors as
“self-contained, interactive, independent components of a computing
system that communicate by asynchronous message passing”, and gives
the basic actor primitives as <code class="language-plaintext highlighter-rouge">create</code>, <code class="language-plaintext highlighter-rouge">send to</code>, and <code class="language-plaintext highlighter-rouge">become</code>.
Examples are given in the actor language Rosette.</p>
<p>This paper gives an overview and summary of many of the important
facets of research on actors that had been done at the time, including
brief discussion of: nondeterminism and fairness; patterns of
coordination beyond simple request/reply such as transactions;
visualization, monitoring and debugging; resource management in cases
of extremely high levels of potential concurrency; and reflection.</p>
<blockquote>
<p>The customer-passing style supported by actors is the concurrent
generalization of continuation-passing style supported in sequential
languages such as Scheme. In case of sequential systems, the object
must have completed processing a communication before it can process
another communication. By contrast, in concurrent systems it is
possible to process the next communication as soon as the
replacement behavior for an object is known.</p>
</blockquote>
<p>Note that the sequential-seeming portions of the language are defined
in terms of asynchronous message passing and construction of explicit
continuation actors.</p>
</li>
<li>
<p><strong>1997. G. A. Agha, I. A. Mason, S. F. Smith, and C. L. Talcott, “A Foundation for Actor Computation,” J. Funct. Program., vol. 7, no. 1, pp. 1–72</strong></p>
<p>Long paper that carefully and fully develops an operational semantics
for a concrete actor language based on lambda-calculus. Discusses
various equivalences and laws. An excellent starting point if you’re
looking to build on a modern approach to operational semantics for
actors.</p>
</li>
</ul>
<h3 id="erlang-actors-from-requirements-for-fault-tolerance--high-availability">Erlang: Actors from requirements for fault-tolerance / high-availability</h3>
<ul>
<li>
<p><strong>2003. J. Armstrong, “Making reliable distributed systems in the presence of software errors,” Royal Institute of Technology, Stockholm</strong></p>
<p>A good overview of Erlang: the language, its design intent, and the
underlying philosophy. Includes an evaluation of the language design.</p>
</li>
</ul>
<h3 id="e-actors-from-requirements-for-secure-interaction">E: Actors from requirements for secure interaction</h3>
<ul>
<li>
<p><strong>2005. M. S. Miller, E. D. Tribble, and J. Shapiro, “Concurrency Among Strangers,” in Proc. Int. Symp. on Trustworthy Global Computing, pp. 195–229.</strong></p>
<p>As I summarised this paper for a seminar class on distributed systems:
“The authors present E, a language designed to help programmers manage
<em>coordination</em> of concurrent activities in a setting of distributed,
mutually-suspicious objects. The design features of E allow
programmers to take control over concerns relevant to distributed
systems, without immediately losing the benefits of ordinary OO
programming.”</p>
<p>E is a canonical example of the “communicating event loops” approach
to Actor languages, per the taxonomy of the survey paper listed below.
It combines message-passing and isolation in an interesting way with
ordinary object-oriented programming, giving a two-level language
structure that has an OO flavour.</p>
<p>The paper does a great job of explaining the difficulties that arise
when writing concurrent programs in traditional models, thereby
motivating the actor model in general and the features of E in
particular as a way of making the programmer’s job easier.</p>
</li>
</ul>
<h3 id="taxonomy-of-actors">Taxonomy of actors</h3>
<ul>
<li>
<p><strong>2016. J. De Koster, T. Van Cutsem, and W. De Meuter, “43 Years of Actors: A Taxonomy of Actor Models and Their Key Properties,” Software Languages Lab, Vrije Universiteit Brussel, VUB-SOFT-TR-16-11</strong></p>
<p>A very recent survey paper that offers a taxonomy for classifying
actor-style languages. At its broadest, actor languages are placed in
one of four groups:</p>
<ul>
<li>The Classic Actor Model (create, send, become)</li>
<li>Active Objects (OO with a thread per object; copying of passive data between objects)</li>
<li>Processes (raw Erlang; receive, spawn, send)</li>
<li>Communicating Event-Loops (E; near and far references; eventual references; batching)</li>
</ul>
<p>Different kinds of “futures” or “promises” also appear in many of
these variations in order to integrate asynchronous message
<em>reception</em> with otherwise-sequential programming.</p>
</li>
</ul>
A Universal Modular ACTOR Formalism for Artificial Intelligence2016-10-12T19:53:45+00:00http://eighty-twenty.org/2016/10/12/hewitt-bishop-steiger-ijcai-1973tonyg<p>I have scanned the original IJCAI 1973 proceedings print version of</p>
<blockquote>
<p><a href="/files/Hewitt, Bishop, Steiger - 1973 - A universal modular ACTOR formalism for artificial intelligence.pdf">Carl Hewitt, Peter Bishop, and Richard Steiger, “A universal modular ACTOR formalism for artificial intelligence,” in Proc. International Joint Conference on Artificial Intelligence, 1973, pp. 235–245.</a></p>
</blockquote>
<p>The <a href="/files/Hewitt, Bishop, Steiger - 1973 - A universal modular ACTOR formalism for artificial intelligence.pdf">scanned PDF is available to download</a> for
anyone interested in seeing the paper as it looked in print.</p>
<hr />
<p>As part of my research, I’ve been digging through the literature. I
couldn’t find a good PDF version of the above, which is one of the
original papers on Actors. All I could find were links to
<a href="http://worrydream.com/refs/Hewitt-ActorModel.pdf">this OCRed version</a>,
which doesn’t show me the actual paper, just an ugly rendition of the
OCRed text. Even the
<a href="http://ijcai.org/proceedings/1973">IJCAI official online archive</a>
only has
<a href="http://ijcai.org/Proceedings/73/Papers/027B.pdf">the OCRed version</a>.</p>
<p>So I went looking for the original print IJCAI 1973 proceedings in the
university library. Lo and behold, it was there!</p>
<p>So I have scanned it and uploaded it here.</p>
Minimart and Network Calculus at (fourth Racketcon)2014-09-28T13:53:57+00:00http://eighty-twenty.org/2014/09/28/racketcon-minimart-talktonyg<p>Here’s me giving a talk about my research on Minimart and Network
Calculus at <a href="http://con.racket-lang.org/"><code class="language-plaintext highlighter-rouge">(fourth Racketcon)</code></a> on the
20th of September, 2014:</p>
<div class="video-wrapper"><iframe width="640" height="360" src="https://www.youtube-nocookie.com/embed/LIJHb8E4Mhk?rel=0" frameborder="0" allowfullscreen=""></iframe></div>