Conversational Concurrency
Tony Garnock-JonesPhD Dissertation Defense
December 8th, 2017
more than one thing to do
Concurrency
vs.
Parallelism
progress on more than one at once
more than one thing to do
Concurrency
vs.
Parallelism
progress on more than one at once
Simon Marlow:
Concurrency is [...] for structuring your program as a collection of interacting agents. Parallelism, on the other hand, is just about making your programs go faster.
more than one interacting thing
Concurrency
vs.
Parallelism
progress on more than one at once
more than one interacting thing
Concurrency
more than one interacting thing
Concurrency
is about
- groups of components
- working together
- to achieve some shared goal.
more than one interacting thing
Concurrency
is about
cooperation.
Coordinate
- arrange to take turns performing helpful tasks
- via communication
Communicate
- build shared understanding
- of relevant knowledge
- required to achieve the shared goal
= manage conversational state
Coordinate
- arrange to take turns performing helpful tasks
- via communication
Communicate
- build shared understanding
- of relevant knowledge
- required to achieve the shared goal
= manage conversational state
Coordinate
- arrange to take turns performing helpful tasks
- via communication
Communicate
- build shared understanding
- of relevant knowledge
- required to achieve the shared goal
= manage conversational state
Coordinate
- arrange to take turns performing helpful tasks
- via communication
Communicate
- build shared understanding
- of relevant knowledge
- required to achieve the shared goal
= manage conversational state
Coordinate
- arrange to take turns performing helpful tasks
- via communication
Communicate
- build shared understanding
- of relevant knowledge
- required to achieve the shared goal
= manage conversational state
(dissertation fig. 2)
| Concurrency is about | cooperation |
| through | communication |
| of | conversational state |
Unpredictability
- ✓ pure, total functions
- ✗ effects
- ✗ coroutines
- ✗ threads & shared memory
- ✗ network conditions
| Concurrency is about | cooperation |
| through | communication |
| of | conversational state |
| in an | unpredictable setting |
Syndicate provides a new, effective, realizable linguistic mechanism for sharing state in a concurrent setting.
Roadmap
- Dataspace model and assertion tries
- Reifying conversations
- Programming experience with Syndicate
- Evaluation
- Conclusion & future work
Roadmap
- Dataspace model and assertion tries
- Reifying conversations
- Programming experience with Syndicate
- Evaluation
- Conclusion & future work
Dataspace model
Dataspace model
Tuplespace model
Actions: eval, out, rd, in
Tuplespace model
Actions: eval, out, rd, in
Tuplespace model
Actions: eval, out, rd, in
Tuplespace model
Actions: eval, out, rd, in
(out (balance 'account1 123.0))
Tuplespace model
Actions: eval, out, rd, in
(out (balance 'account1 123.0))
Tuplespace model
Actions: eval, out, rd, in
Tuplespace model
Actions: eval, out, rd, in
(rd (balance 'account1 _))
Tuplespace model
Actions: eval, out, rd, in
Tuplespace model
Actions: eval, out, rd, in
(in 'lock)
Tuplespace model
Actions: eval, out, rd, in
(in 'lock)
Tuplespace model
Actions: eval, out, rd, in
Tuplespace model
Actions: eval, out, rd, in
Tuplespace model
Actions: eval, out, rd, in
Dataspace model
Dataspace model
Dataspace model
Dataspace model
Dataspace model
Dataspace model
(observe P)
Assertion of interest in P
(color 'boat 'blue)
"The color of the boat is blue"
(observe (color 'boat _))
"Interest exists in the color of the boat being anything at all"
(observe P)
Assertion of interest in P
(color 'boat 'blue)
"The color of the boat is blue"
(observe (color 'boat _))
"Interest exists in the color of the boat being anything at all"
(observe P)
Assertion of interest in P
(color 'boat 'blue)
"The color of the boat is blue"
(observe (color 'boat _))
"Interest exists in the color of the boat being anything at all"
Figure 11, chapter 4
Figure 13, chapter 4
Figure 14, chapter 4
| Actor | Event transducer |
|---|---|
| Actions | Spawn new actor
Replace assertions Message |
| Events | Dataspace has changed
Message |
Reduction rules: deliver events; gather actions; interpret actions; step contained actors
(struct dns-entry (name address))
(dns-entry "localhost" "127.0.0.1")
"The address of localhost is 127.0.0.1"
(observe (dns-entry "localhost" _))
"Interest exists in the address of localhost"
(observe (observe (dns-entry _ _)))
"Interest exists in interest in dns-entry records"
(struct dns-entry (name address))
(dns-entry "localhost" "127.0.0.1")
"The address of localhost is 127.0.0.1"
(observe (dns-entry "localhost" _))
"Interest exists in the address of localhost"
(observe (observe (dns-entry _ _)))
"Interest exists in interest in dns-entry records"
(struct dns-entry (name address))
(dns-entry "localhost" "127.0.0.1")
"The address of localhost is 127.0.0.1"
(observe (dns-entry "localhost" _))
"Interest exists in the address of localhost"
(observe (observe (dns-entry _ _)))
"Interest exists in interest in dns-entry records"
(struct dns-entry (name address))
(dns-entry "localhost" "127.0.0.1")
"The address of localhost is 127.0.0.1"
(observe (dns-entry "localhost" _))
"Interest exists in the address of localhost"
(observe (observe (dns-entry _ _)))
"Interest exists in interest in dns-entry records"
| Client |
|
| Server |
|
| Cache |
|
| Client |
|
| Server |
|
| Cache |
|
| Client |
|
| Server |
|
| Cache |
|
| Client |
|
| Server |
|
| Cache |
|
| Client |
|
| Server |
|
| Cache |
|
| Client |
|
| Server |
|
| Cache |
|
| Client |
|
| Server |
|
| Cache |
|
| Client |
|
| Server |
|
| Cache |
|
| Client |
|
| Server |
|
| Cache |
|
| Client |
|
| Server |
|
| Cache |
|
| Client |
|
| Server |
|
| Cache |
|
| Client |
|
| Server |
|
| Cache |
|
| Client |
|
| Server |
|
| Cache |
|
| Client |
|
| Server |
|
| Cache |
|
| Client |
|
| Server |
|
| Cache |
|
| Client |
|
| Server |
|
| Cache |
|
| Client |
|
| Server |
|
| Cache |
|
| Client |
|
| Server |
|
| Cache |
|
| Client |
|
| Server |
|
| Cache |
|
| Client |
|
| Server |
|
| Cache |
|
| Client |
|
| Server |
|
| Cache |
|
| Client |
|
| Server |
|
| Cache |
|
| Client |
|
| Server |
|
| Cache |
|
| Client |
|
| Server |
|
| Cache |
|
| Client |
|
| Server |
|
| Cache |
|
| Client |
|
| Server |
|
| Cache |
|
| Client |
|
| Server |
|
| Cache |
|
- Supports S-expression-like data and wildcards well
- Closed under ∪, ∩, −
- Reasonably efficient ∪, ∩, −
- Reasonably compact
- Gives efficient routing of assertions and messages
Properties
- ✓ No errors and stuck-free
- ✓ Deterministic
- ✓ Order-preserving
- ✓ Conversational "soundness", "completeness"
- actions correctly interpreted
- an event for every relevant change
- every event is
- truthful,
- relevant, and
- complete.
- ✓ No errors and stuck-free
- ✓ Deterministic
- ✓ Order-preserving
- ✓ Conversational "soundness", "completeness"
- actions correctly interpreted
- an event for every relevant change
- every event is
- truthful,
- relevant, and
- complete.
- ✓ No errors and stuck-free
- ✓ Deterministic
- ✓ Order-preserving
- ✓ Conversational "soundness", "completeness"
- actions correctly interpreted
- an event for every relevant change
- every event is
- truthful,
- relevant, and
- complete.
Roadmap
- Dataspace model and assertion tries
- Reifying conversations
- Programming experience with Syndicate
- Evaluation
- Conclusion & future work
Facet
- Assertions
- Local fields
- Data flow → control flow
- Control flow → data flow
- Local data → shared data
- Shared data → local data
- Subfacets
(react (field [field-name expr] ...)
endpoint-expr ...)
endpoint-expr
= (assert expr)
| (on (asserted pattern) expr ...)
| (on (retracted pattern) expr ...)
| (on (message pattern) expr ...)
| (on-start expr ...)
| (on-stop expr ...)(stop-when E expr ...)
= (on E (stop-facet (current-facet-id) expr ...))
(during pattern endpoint-expr ...)
= (on (asserted pattern)
(react (stop-when (retracted pattern′))
endpoint-expr ...))(react (field [field-name expr] ...)
endpoint-expr ...)
endpoint-expr
= (assert expr)
| (on (asserted pattern) expr ...)
| (on (retracted pattern) expr ...)
| (on (message pattern) expr ...)
| (on-start expr ...)
| (on-stop expr ...)(stop-when E expr ...)
= (on E (stop-facet (current-facet-id) expr ...))
(during pattern endpoint-expr ...)
= (on (asserted pattern)
(react (stop-when (retracted pattern′))
endpoint-expr ...))(react (field [field-name expr] ...)
endpoint-expr ...)
endpoint-expr
= (assert expr)
| (on (asserted pattern) expr ...)
| (on (retracted pattern) expr ...)
| (on (message pattern) expr ...)
| (on-start expr ...)
| (on-stop expr ...)(stop-when E expr ...)
= (on E (stop-facet (current-facet-id) expr ...))
(during pattern endpoint-expr ...)
= (on (asserted pattern)
(react (stop-when (retracted pattern′))
endpoint-expr ...))(react (field [field-name expr] ...)
endpoint-expr ...)
endpoint-expr
= (assert expr)
| (on (asserted pattern) expr ...)
| (on (retracted pattern) expr ...)
| (on (message pattern) expr ...)
| (on-start expr ...)
| (on-stop expr ...)(stop-when E expr ...)
= (on E (stop-facet (current-facet-id) expr ...))
(during pattern endpoint-expr ...)
= (on (asserted pattern)
(react (stop-when (retracted pattern′))
endpoint-expr ...))(react (field [field-name expr] ...)
endpoint-expr ...)
endpoint-expr
= (assert expr)
| (on (asserted pattern) expr ...)
| (on (retracted pattern) expr ...)
| (on (message pattern) expr ...)
| (on-start expr ...)
| (on-stop expr ...)(stop-when E expr ...)
= (on E (stop-facet (current-facet-id) expr ...))
(during pattern endpoint-expr ...)
= (on (asserted pattern)
(react (stop-when (retracted pattern′))
endpoint-expr ...))(react (field [field-name expr] ...)
endpoint-expr ...)
endpoint-expr
= (assert expr)
| (on (asserted pattern) expr ...)
| (on (retracted pattern) expr ...)
| (on (message pattern) expr ...)
| (on-start expr ...)
| (on-stop expr ...)(stop-when E expr ...)
= (on E (stop-facet (current-facet-id) expr ...))
(during pattern endpoint-expr ...)
= (on (asserted pattern)
(react (stop-when (retracted pattern′))
endpoint-expr ...))(react (field [field-name expr] ...)
endpoint-expr ...)
endpoint-expr
= (assert expr)
| (on (asserted pattern) expr ...)
| (on (retracted pattern) expr ...)
| (on (message pattern) expr ...)
| (on-start expr ...)
| (on-stop expr ...)(stop-when E expr ...)
= (on E (stop-facet (current-facet-id) expr ...))
(during pattern endpoint-expr ...)
= (on (asserted pattern)
(react (stop-when (retracted pattern′))
endpoint-expr ...))(react (field [field-name expr] ...)
endpoint-expr ...)
endpoint-expr
= (assert expr)
| (on (asserted pattern) expr ...)
| (on (retracted pattern) expr ...)
| (on (message pattern) expr ...)
| (on-start expr ...)
| (on-stop expr ...)(stop-when E expr ...)
= (on E (stop-facet (current-facet-id) expr ...))
(during pattern endpoint-expr ...)
= (on (asserted pattern)
(react (stop-when (retracted pattern′))
endpoint-expr ...))(react (field [field-name expr] ...)
endpoint-expr ...)
endpoint-expr
= (assert expr)
| (on (asserted pattern) expr ...)
| (on (retracted pattern) expr ...)
| (on (message pattern) expr ...)
| (on-start expr ...)
| (on-stop expr ...)(stop-when E expr ...)
= (on E (stop-facet (current-facet-id) expr ...))
(during pattern endpoint-expr ...)
= (on (asserted pattern)
(react (stop-when (retracted pattern′))
endpoint-expr ...))(react (field [field-name expr] ...)
endpoint-expr ...)
endpoint-expr
= (assert expr)
| (on (asserted pattern) expr ...)
| (on (retracted pattern) expr ...)
| (on (message pattern) expr ...)
| (on-start expr ...)
| (on-stop expr ...)(stop-when E expr ...)
= (on E (stop-facet (current-facet-id) expr ...))
(during pattern endpoint-expr ...)
= (on (asserted pattern)
(react (stop-when (retracted pattern′))
endpoint-expr ...))| Client |
|
| |
| Server |
|
| |
| Cache |
|
| |
| Client |
|
| |
| Server |
|
| |
| Cache |
|
| |
| Client |
|
| |
| Server |
|
| |
| Cache |
|
| |
| Client |
|
| |
| Server |
|
| |
| Cache |
|
| |
| Client |
|
| |
| Server |
|
| |
| Cache |
|
| |
| Client |
|
| |
| Server |
|
| |
| Cache |
|
| |
| Client |
|
| |
| Server |
|
| |
| Cache |
|
| |
| Client |
|
| |
| Server |
|
| |
| Cache |
|
| |
| Client |
|
| |
| Server |
|
| |
| Cache |
|
| |
| Client |
|
| |
| Server |
|
| |
| Cache |
|
| |
| Client |
|
| |
| Server |
|
| |
| Cache |
|
| |
| Client |
|
| |
| Server |
|
| |
| Cache |
|
| |
Figures 16 & 17, chapter 5
Figures 19 & 20, chapter 5
Figure 23, chapter 5
Roadmap
- Dataspace model and assertion tries
- Reifying conversations
- Programming experience with Syndicate
- Evaluation
- Conclusion & future work
Syndicate/js
In-browser and node.js implementation
Assertions can place DOM elements on the page
DOM events generate Syndicate/js messages
Websocket protocol connects browser to Syndicate/rkt
function todoListItemModel(initialId, initialTitle, initialCompleted) {
spawn {
field this.id = initialId;
field this.title = initialTitle;
field this.completed = initialCompleted;
stop on message deleteTodo(this.id);
assert todo(this.id, this.title, this.completed);
on message setCompleted(this.id, $v) { this.completed = v; }
on message setAllCompleted($v) { this.completed = v; }
on message setTitle(this.id, $v) { this.title = v; }
on message clearCompletedTodos() {
if (this.completed) :: deleteTodo(this.id);
}
}
}
- IRC Server
- TCP/IP Stack
- Collaborative text editor server
- Broker: embeds Syndicate/js in Syndicate/rkt
- Web-based chat application
- Many, many, many smaller examples
Roadmap
- Dataspace model and assertion tries
- Reifying conversations
- Programming experience with Syndicate
- Evaluation
- Conclusion & future work
How should we evaluate a language design idea?
| Quantitatively? | ✗ Benchmark suites ✗ Error rates ✗ Programmer productivity |
| Qualitatively | ✓ Simplification of programs ✓ Asymptotic performance |
How should we evaluate a language design idea?
| Quantitatively? | ✗ Benchmark suites ✗ Error rates ✗ Programmer productivity |
| Qualitatively | ✓ Simplification of programs ✓ Asymptotic performance |
How should we evaluate a language design idea?
| Quantitatively? | ✗ Benchmark suites ✗ Error rates ✗ Programmer productivity |
| Qualitatively | ✓ Simplification of programs ✓ Asymptotic performance |
How should we evaluate a language design idea?
| Quantitatively? | ✗ Benchmark suites ✗ Error rates ✗ Programmer productivity |
| Qualitatively | ✓ Simplification of programs ✓ Asymptotic performance |
How should we evaluate a language design idea?
| Quantitatively? | ✗ Benchmark suites ✗ Error rates ✗ Programmer productivity |
| Qualitatively | ✓ Simplification of programs ✓ Asymptotic performance |
How should we evaluate a language design idea?
| Quantitatively? | ✗ Benchmark suites ✗ Error rates ✗ Programmer productivity |
| Qualitatively | ✓ Simplification of programs ✓ Asymptotic performance |
How should we evaluate a language design idea?
| Quantitatively? | ✗ Benchmark suites ✗ Error rates ✗ Programmer productivity |
| Qualitatively | ✓ Simplification of programs ✓ Asymptotic performance |
How should we evaluate a language design idea?
| Quantitatively? | ✗ Benchmark suites ✗ Error rates ✗ Programmer productivity |
| Qualitatively | ✓ Simplification of programs ✓ Asymptotic performance |
Patterns
Simplify by eliminating patterns.
Patterns
Programming Pattern [Felleisen 1991]
Design Pattern [Gamma et al. 1994]
Informal → Formal → Invisible
[Norvig 1996]
- Event Broadcast (encoding)
- The "Observer" Pattern [Gamma et al. 1994]
- State Replication Pattern
- The "State" Pattern [Gamma et al. 1994]
- The "Cancellation" Pattern [Russell et al. 2016]
State Replication
| Event broadcasting | Observer pattern | State replication | |
| Smalltalk | informal/invisible | formal | informal |
|---|---|---|---|
| Ruby | informal/invisible | formal | informal |
| Java | informal/invisible | informal | informal |
| Erlang/OTP | informal/invisible | informal | informal |
| Syndicate | invisible | invisible | invisible |
"State" Pattern
| Java | informal |
|---|---|
| Syndicate | invisible |
"Cancellation" Pattern
| JavaScript | informal |
|---|---|
| Syndicate | invisible |
(struct service-a (request response))
(struct service-b (request response))
(spawn (during (service-a 'request-from-a $response)
(on-start (printf "Response: ~v\n" response))))
(spawn (during (observe (service-a $req-a _))
(during (service-b 'request-from-b $resp-b)
(assert (service-a req-a (make-answer resp-b))))))Asymptotic performance
Message routing & delivery, sec/event vs k
 Unicast: Õ(1) |  Broadcast: Õ(1/k + 1) |
Asymptotic performance
Assertion set update cost, sec/event vs k
 k-independent: Õ(1) |  k-dependent: Õ(1) |
Asymptotic performance
TCP echo server, sec/conn vs k
 Marginal cost of additional connection: Õ(1) |
Roadmap
- Dataspace model and assertion tries
- Reifying conversations
- Programming experience with Syndicate
- Evaluation
- Conclusion & future work
Future Work
- Enhancements to the formal models
types; names; grouping & relaying; formal properties - System model
performance; tool support; generic protocols; process management;
stdio; contracts; security; persistence; polyglot - Distributed systems
unpredictable latency & scheduling; message loss; subnets
Thank you!
Committee: Thank You for Signing my Dissertation! :-)Future Work
- Enhancements to the formal models
types; names; grouping & relaying; formal properties - System model
performance; tool support; generic protocols; process management;
stdio; contracts; security; persistence; polyglot - Distributed systems
unpredictable latency & scheduling; message loss; subnets
Thank you!
Committee: Thank You for Signing my Dissertation! :-)Backup
| New expressions: | |
| Field access: | |
| Field update: | |
| New expressions: | |
| Field access: | |
| Field update: | |
| New expressions: | |
| Field access: | |
| Field update: | |
| New expressions: | |
| Field access: | |
| Field update: | |
| New expressions: | |
| Field access: | |
| Field update: | |
| New expressions: | |
| Field access: | |
| Field update: | |
| New expressions: | |
| Field access: | |
| Field update: | |
| New expressions: | |
| Field access: | |
| Field update: | |
| New expressions: | |
| Field access: | |
| Field update: | |
(struct set-box (new-value))
(struct box-state (value))
(spawn (field [current-value 0])
(assert (box-state (current-value)))
(on (message (set-box $new-value))
(current-value new-value)))
(spawn (on (asserted (box-state $v))
(send! (set-box (+ v 1)))))(struct set-box (new-value))
(struct box-state (value))
(spawn (field [current-value 0])
(assert (box-state (current-value)))
(on (message (set-box $new-value))
(current-value new-value)))
(spawn (on (asserted (box-state $v))
(send! (set-box (+ v 1)))))(struct set-box (new-value))
(struct box-state (value))
(spawn (field [current-value 0])
(assert (box-state (current-value)))
(on (message (set-box $new-value))
(current-value new-value)))
(spawn (on (asserted (box-state $v))
(send! (set-box (+ v 1)))))(struct set-box (new-value))
(struct box-state (value))
(spawn (field [current-value 0])
(assert (box-state (current-value)))
(on (message (set-box $new-value))
(current-value new-value)))
(spawn (on (asserted (box-state $v))
(send! (set-box (+ v 1)))))(struct set-box (new-value))
(struct box-state (value))
(spawn (field [current-value 0])
(assert (box-state (current-value)))
(on (message (set-box $new-value))
(current-value new-value)))
(spawn (on (asserted (box-state $v))
(send! (set-box (+ v 1)))))(struct set-box (new-value))
(struct box-state (value))
(spawn (field [current-value 0])
(assert (box-state (current-value)))
(on (message (set-box $new-value))
(current-value new-value)))
(spawn (on (asserted (box-state $v))
(send! (set-box (+ v 1)))))(struct set-box (new-value))
(struct box-state (value))
(spawn (field [current-value 0])
(assert (box-state (current-value)))
(on (message (set-box $new-value))
(current-value new-value)))
(spawn (on (asserted (box-state $v))
(send! (set-box (+ v 1)))))(struct set-box (new-value))
(struct box-state (value))
(spawn (field [current-value 0])
(assert (box-state (current-value)))
(on (message (set-box $new-value))
(current-value new-value)))
(spawn (on (asserted (box-state $v))
(send! (set-box (+ v 1)))))(struct set-box (new-value))
(struct box-state (value))
(spawn (field [current-value 0])
(assert (box-state (current-value)))
(on (message (set-box $new-value))
(current-value new-value)))
(spawn (on (asserted (box-state $v))
(send! (set-box (+ v 1)))))(struct set-box (new-value))
(struct box-state (value))
(spawn (field [current-value 0])
(assert (box-state (current-value)))
(on (message (set-box $new-value))
(current-value new-value)))
(spawn (on (asserted (box-state $v))
(send! (set-box (+ v 1)))))(struct set-box (new-value))
(struct box-state (value))
(spawn (field [current-value 0])
(assert (box-state (current-value)))
(on (message (set-box $new-value))
(current-value new-value)))
(spawn (on (asserted (box-state $v))
(send! (set-box (+ v 1)))))