Lyricdev
GitHub

Concurrency

Skeleton. Written with milestone M6 of the Lyric 5 plan, spec-first: each rule lands here with its conformance case before or with its implementation. Source of the decisions: 06 Concurrency, 01 Runtime L4/L6.

Scope

Coroutines and generators, tasks and TaskScope, parking, threads with one scheduler each, channels, select and timers, atomics and synchronization, the memory model.

1. Coroutines and generators

  1. A function whose declared result is Coroutine<Y, R> and whose body has a yield of its own — one outside every lambda in it — or returns no value is a coroutine function (08 D11; the review's M6-3): a body that yields through helpers only is one, and an empty body is the empty one. "Returns no value" is said of the body as it is written — no return v; and no value at its end —, not of where it can arrive: a body that only throws is one too, and its error arrives at the first pull, as every error of a coroutine function's body does. Coroutine<Y> is Coroutine<Y, void> (06 A1). A call of it runs nothing of its body: it returns a coroutine, suspended before the body's first statement and holding the call's arguments — a method's receiver among them, as an argument is held: a struct or an enum is a copy, and what a mut fn coroutine function writes to this stays in it (allowed, and warned about where it is declared, LYR-SEM0172; M6-1). A coroutine runs only when it is pulled. A coroutine function may be a method and may be generic; an instance is instantiated as any generic function is. A function that returns a value — return make(); — is an ordinary function, a factory: it returns a coroutine value as it returns any value.
  2. yield v; hands v to the puller and suspends the body until the next pull; v is checked against Y (LYR-SEM0001). yield; without a value belongs to a Coroutine<void> and is refused in any other coroutine (LYR-SEM0038). The body's locals live across its yields.
  3. The body's return gives the coroutine's result: return v; checks v against R and is refused where R is void (LYR-SEM0039); a bare return; is refused where R is not void (LYR-SEM0001). Where R is not void, every way out of the body returns a value (LYR-SEM0017) — a body that never ends needs none.
  4. next() runs the coroutine to its next yield or to the end of its body and answers ?Y: the value the yield handed over, or null once the body has ended — on that pull and on every pull after it. A Coroutine<?T>'s next() answers ??T, so a yielded null is told apart from the end (03 §3.1). A Coroutine<void>'s next() answers bool: whether the body stopped at a yield.
  5. result() answers ?R: what the body returned, null until it has returned; a coroutine whose R is void has no result() (LYR-SEM0012). isDone() answers whether the body has ended, without pulling. Whether a value follows only the body knows, by running: there is no hasNext.
  6. A coroutine function's throws clause belongs to the coroutine's type — Coroutine<Y, R> throws E — and so to its pulls, not to the call that makes the coroutine, which throws nothing: a next() of a throwing coroutine is marked like a call of a throwing function (06 §3, LYR-SEM0138). An error the body does not catch ends the body and comes out of the next() that ran into it. The coroutine is done then: its result() stays null, and every later next() answers null and throws nothing.
  7. A coroutine runs on a stack of its own, on the thread that first pulled it (13 §1.6). Pulling a coroutine that runs — from its own body, or from a coroutine it pulled — or one that runs on another thread panics with LYR-RT0014. A suspended coroutine that nothing references any more is collected with its stack, and nothing of its body runs again.
  8. resume is no word of the language: Lyric 4's resume co is co.next()!, and resume is a name like any other.
  9. close() ends a coroutine (06 A5). One that is done, or was never pulled, ends without running anything. One suspended at a yield of its body is continued to be unwound: that yield throws Cancelled — std.task's, an Error — so the body's defers and usings run on the way out (06 §5). The Cancelled ends at the close: close() does not throw it on. What a defer threw on the way out was suppressed into it (06 §7); close() throws the first of those, the rest suppressed into it (the review's M6-10) — dropped with the Cancelled, they were lost in silence. A body that catches it may still end with a result, but a yield after it panics with LYR-RT0014. What else escapes the body comes out of close(), which belongs to the coroutine's throws clause like its pulls: the close() of a throwing coroutine is marked (LYR-SEM0138). The coroutine is done afterwards; closing a coroutine that runs — itself, or one waiting on a coroutine it pulled — panics with LYR-RT0014.
  10. A coroutine is Closeable: using let c = gen(); closes it when the scope is left (06 §7). Unlike another Closeable it may also be dropped unclosed, without a warning: a suspended coroutine that nothing references any more runs nothing more — not its defers either (rule 7) — and the debug profile reports one whose body has a defer or a using when the collector takes it.
  11. A lambda whose body has a yield of its own is a generator lambda (08 F5): its type is fn(…) -> Coroutine<Y, R>, and calling it makes a coroutine over its arguments and its captures that runs nothing until it is pulled (rule 1). A context that expects a coroutine — the lambda's written result type, or the type of the place it is passed to — gives Y and R and checks the yields and the returns against them (LYR-SEM0001); without one, the types of the yields unify into Y (LYR-SEM0016), and those of the returns into R, or void where it returns none. A generator lambda whose R is not void returns on every path that ends its body (LYR-SEM0046). What its body throws belongs to its coroutine's pulls, as a coroutine function's clause does (rule 6): the set it writes, the one its context expects, or what escapes its body. A yield in a lambda nested in it belongs to that lambda.
  12. sequence { … } (08 Y11) is std.core's fn sequence<T>(body: fn() -> Coroutine<T>): Coroutine<T>, called with a trailing generator lambda — no syntax of its own.
  13. A yield outside a coroutine's own body — in a function a coroutine calls (06 §10a) — suspends the coroutine that runs, whoever called the function. Its value is typed as what it is and meets that coroutine's Y at run time: a value of another type — and two modules' types of one name are two types (04 §2 rule 9) — panics with LYR-RT0014, as does such a yield where no generator runs — on a thread's own stack, or in a task (§2). It throws Cancelled at close() as a body's yield does (rule 9), so its function covers it — throws Cancelled, or a clause (LYR-SEM0034) — and a coroutine's body covers it for the functions it calls, as it does for its own yields. A yield in a lambda is not of this kind: it makes the lambda a generator (rule 11).
  14. A coroutine is Identity (06 A7; N2d): == is same, and its hash is its address (05 §14 rule 8) — a Set or a Map of coroutines finds the same one twice, whatever its pulls throw. std.core gives it through one block on Coroutine<Y, R> (05 §13 rule 6).

2. Tasks

A task is a body that the scheduler of its thread runs on a stack of its own (06 N3–N6). Unlike a generator it yields nothing: it waits. A wait parks the task at its thread's scheduler wherever it stands (13 §1.6 rule 7), and the scheduler runs another task meanwhile. The functions this section names are std.task's.

  1. main is a task, on the main thread's scheduler (06 T6). The program ends when main's body returns: the tasks still ready or asleep then never run again, and none of their defers runs. (Informative: a program that never waits runs main on the thread's own stack; it cannot tell the difference.)
  2. A thread runs one of its tasks at a time, each until it waits (06 N8): the code between two waits runs with no other task of its thread in between. The tasks that are ready run in the order they became ready.
  3. spawnDetached(body) makes body a task of the running thread, ready behind the tasks ready before it (06 T5). Nobody waits for it, and nothing it throws reaches anyone: its type, fn() -> void throws Cancelled, lets only a cancellation end it early, so it handles every other error itself (LYR-SEM0034).
  4. yieldNow() puts the running task behind the tasks that are ready: they run before it goes on (06 N8).
  5. sleep(d) parks the running task until at least d has passed on the monotonic clock (06 K3; 13 §1.6 rule 8). d is a std.time.Duration, a span of whole nanoseconds (10 Q1). The sleepers whose time came wake in the order of their deadlines — of one deadline, in the order they fell asleep — behind the tasks already ready. A sleep of zero or less lets the ready tasks run first.
  6. A wait parks the whole task, also from within a generator the task pulls: once the task runs again, the generator goes on where it waited and yields to its puller as before.
  7. The waits — sleep, yieldNow, await — throw Cancelled where their task is cancelled (06 N9 X1): a function that waits covers it, with throws Cancelled or a clause (LYR-SEM0034). main covers it itself, as a coroutine function's body does (the review's M6-4): nobody above main answers a cancellation, so it says no throws Cancelled — the call that waits keeps its try, and a Cancelled that leaves main is reported as any error that leaves it is (06 §5).
  8. spawn(body) makes body a task of the running thread, ready behind the tasks ready before it, and gives its handle, a Task<T> throws E (06 T1): T is what the body returns — void too (03 §9.1 rule 7) — and E what it throws. The handle's type carries the error as a coroutine's carries what its pulls throw (05 E10); Task<T> throws nothing, and fits where a Task<T> throws E is expected, but not the reverse (LYR-SEM0001). throws after any other type than a coroutine or a task is refused (LYR-SEM0084). After a return type that is a task or a coroutine — with a ? before it or without — a throws could be the type's or the function's, and without parentheses it is refused (LYR-SEM0165): a function that returns a throwing task writes (Task<T> throws E), one that throws itself (Task<T>) throws E. So behind the return type of a lambda and of a function type. A generator writes none: its clause is its coroutine's (§1 rule 6). spawn is @MustUse (11 §1 rule 11): the handle alone carries the task's error, so a statement that drops it warns, under the lint unused-task (16 §5) — and so does one that drops Thread.spawn's; a scope's spawn is awaited by the scope. spawnDetached (rule 3) is the task nobody awaits.
  9. task.await() waits until the body has ended (06 T2) and gives its value, or throws its error: it throws what the handle's type says and, as every wait, Cancelled — marked and covered as any call that throws (LYR-SEM0138, LYR-SEM0034). The tasks waiting for one task run again in the order they began to wait.
  10. task.isDone() says whether the body has ended, with its value or its error (06 T3).
  11. task.status() says where the task stands, without waiting (06 T3): a TaskStatus<T> — Running; Done(value); Failed(error), the error an Error; Cancelled, when it ended with Cancelled; or Panicked(info) (§5), info a PanicInfo with the panic's code, message and trace.
  12. A wait nothing can end is a panic (LYR-RT0018; the review's M6-12). Where every task of a thread waits, none of them sleeps, none waits for the system — on a socket, a pipe, a channel signals gives (§12), which the system wakes —, and no other thread of the program lives that could wake one, no wait of that thread can end any more: one of its waiting tasks panics in its wait — deadlock: every task waits, and nothing can wake one, with the frames of the call that waits. It is the oldest task that waits for something other than a task's end — a channel, a lock: the wait that is the reason, not an await of it —, and where each waits for another, the oldest. It is that task's panic (§5): what awaits the task panics again with its frames, and main's ends the program. While another thread lives nothing is proven and nothing is said — two threads whose tasks wait for each other wait —; once it has ended, it is.

3. Cancellation

A task is cancelled cooperatively (06 N9): a cancel marks it, and its waits throw.

  1. task.cancel() marks the task cancelled (X1). From then on every wait in it throws Cancelled: the wait it is in ends at once, and every later wait throws before it waits (X5) — a task that catches Cancelled and waits again gets it again. A task that never waits is not cancelled (X2); a task that has ended stays as it ended.
  2. Cancelled unwinds the task as any error does — its defers and usings run — and the task ends with it unless its body catches it; await() on the handle then throws Cancelled (X1).
  3. A wait inside a generator the task pulls throws there: the generator unwinds and ends, its pull answers that it has ended, and the task's next wait throws Cancelled in turn.
  4. withTimeout(d, body) (X4) runs body as a task of its own and gives its value or throws its error — unless d passes first: then the body is cancelled, and once it has ended, TimedOut is thrown. It throws what the body throws, TimedOut and Cancelled (LYR-SEM0034). Whenever it returns, the body has ended: a cancel of the caller cancels the body, and waits for it.

4. Task scopes

The tasks of a scope end before the scope does (06 T5): structured concurrency.

  1. A TaskScope, made by TaskScope.new(), starts tasks with scope.spawn(body) — a spawn (§2 rule 8) whose task belongs to the scope. A scope is Closeable (06 §7): its close() waits until every task of the scope has ended, so under using let scope = TaskScope.new(); no task of it outlives the block.
  2. The first task of the scope that ends with an error other than Cancelled cancels the scope's other tasks (06 N9 X3), and close() throws that error once they have all ended; a task that ends with Cancelled is no failure of the scope. What close() throws is an Error, as Closeable says (LYR-SEM0034).
  3. scope.cancel() cancels every task of the scope that has not ended.
  4. A task cancelled while it waits in close() cancels the scope's tasks and still waits for them to end; then close() returns or throws as before.
  5. A closed scope takes no task (06 M6-27): scope.spawn once close() has returned or thrown is a panic (LYR-RT0008) — no close() would wait for it. A task given while close() waits is a task of the scope like any, and the wait takes it in.

5. Panics in tasks

A panic leaves the coroutine it happens in, without unwinding (05 E8; 13 §1.6 rule 10), and the task it belongs to takes it (06 T4).

  1. A panic in a task started by spawn — a scope's included — ends that task, not the program: the task is panicked, nothing more of it runs — no defer, no using — and the tasks waiting for it run again. A panic in a generator the task pulls passes to the task.
  2. await() on a panicked task panics again, with the panic's code, message and frames: a panic stays a bug. status() (§2 rule 11) looks without panicking.
  3. A task of a scope that panics cancels the scope's other tasks, as a failure does (§4 rule 2), and close() panics again with it once they have all ended.
  4. A panic in main, or in a task started by spawnDetached — which nobody can look at — ends the program with its report (13 §1.4).

6. Channels

A channel carries values from one task to another (06 N5 K1).

  1. A Channel<T>, made by Channel<T>.new(capacity) — 0, the default, for an unbuffered one — carries values from send to recv, in the order they were sent: between the tasks of one thread and across threads (§9). A send happens before the receive that gets its value (06 N7 P1).
  2. send(value) hands the value to a task waiting in recv, or puts it into the buffer while there is room; otherwise the sending task waits until a receiver takes it. On a closed channel, or when the channel closes while it waits, it throws ChannelClosed.
  3. recv() gives the next value: from the buffer — where the value of a waiting sender then takes the freed place — or from a task waiting in send; otherwise the receiving task waits for one. It answers null once the channel is closed and nothing is left in it.
  4. close() closes the channel: the tasks waiting in recv get null, those waiting in send throw ChannelClosed, and what is buffered can still be received. Closing a closed channel does nothing.
  5. send and recv are waits: in a cancelled task they throw Cancelled, and a cancel ends them (§3).

7. Select and timers

A select waits on several channels at once and goes on with the first that has something (06 N5 K2–K3). It is library, no statement: std.task's Select.on(c) { … } begins one, a Selection, whose .on(c) { … } adds a case, .timeout(d) { … } a timeout, and .run() runs it. The bodies are trailing lambdas (03 §8.2) or any function values of their types.

  1. A case on(c, body) receives from the channel c: body, a fn(?T) -> void throws Error for a Channel<T>, gets what recv() would give (§6 rule 3) — the value, or null once c is closed and nothing is left in it.

  2. run() runs the first case, in the order they were added, whose channel has a value or is closed: a receive from it would not wait. Is there none, the running task waits on all of them, and the first channel to get a value or to close runs its case. One body runs, once, and only its case receives: the other channels keep what they get for later receives.

  3. timeout(d, body) (K3): body runs when no case could go on before d passed. A d of zero or less runs it at once where no case can go on at once.

    (Informative: a select is biased to its first case. A case whose channel is closed can always go on — while it stays in a select, no case after it runs.)

  4. run() is a wait: in a cancelled task it throws Cancelled, and a cancel ends it (§3). It throws what the body that runs throws; its type says Error, which its caller covers (LYR-SEM0034).

  5. Timer.after(d) gives a Channel<void> that fires once, when d has passed: then it closes, so a recv() from it answers null and a case on it runs. The program does not wait for a timer (§2 rule 1).

8. Atomics

std.sync's Atomic<T> holds a value that every thread reads and writes in one step (06 G4, K6, N7).

  1. Atomic<T>.new(value) makes one. T is an AtomicValue: int, bool, a class, or an optional of a class (?Node) — a reference is one word, which the machine reads and writes in one step. The interface is sealed, so no other type becomes one (LYR-SEM0132), and an Atomic of another type — a string, a struct, an optional of anything but a class — is refused (LYR-SEM0028).
  2. load() gives the value, store(v) sets it, exchange(v) sets it and gives the value it replaced, and compareAndSet(expected, desired) sets desired where the value is expected and answers whether it did. Each is one step. For a class compareAndSet compares identity (03 §2.6): it sets where the value is the same object as expected (or both are null), whatever == would say.
  3. An Atomic<int> also adds: fetchAndAdd(n) gives the value before, addAndFetch(n) the value after. The sum wraps around, as +% does.
  4. Every operation is sequentially consistent (N7 P2): all threads see the operations in one order, and no read or write moves across one (P4). A store happens before a load that reads its value (P1).

9. Threads

A program runs on the threads it starts (06 G1–G3, N7). Each has a scheduler of its own, which runs that thread's tasks as §2 says, and a task never moves to another thread. Threads run at the same time. Thread is std.thread's (10 Q10; the module cut, M8b S1).

  1. Thread.spawn(body) starts a thread and runs body there as its first task. It gives that task's handle, a Task<T> throws E (§2 rule 8): await() on it waits from any thread, and cancel() cancels it from any thread (§3).
  2. A thread's handle is done when its first task has ended. The thread then cancels what still lives on it (§3; the review's M6-20b) — every task that has started and not ended, and each that starts from then on, as it starts — and runs until all of it has ended: their defers run, their handles are done, and a task of another thread that awaits one of them goes on. Only the program ends with its first task and leaves the rest where it stands (§2 rule 1): it does not wait for a thread either — when main ends, the program ends.
  3. A task that spawn starts runs on the thread of the task that started it.
  4. What a thread did before it started another happens before the new thread's first task (N7 P1), and what a task did before it ended happens before await() on it returns, on any thread.
  5. Two threads that use the same place, one of them writing, with no such order between them — a channel's (§6), an atomic's (§8), a lock's (§10) or a task's end (rule 4) — race: the program has an error, and the language makes no promise about what it then does (G3).

10. Locks

A lock hands a value to one task at a time (06 G4, K6, N10). The types are std.sync's (10 Q10; the module cut, M8b S1). A task that waits for a lock parks, as at every wait (§2): the other tasks of its thread run meanwhile — a lock is needed on one thread too, wherever a body waits.

  1. Mutex<T>, made by Mutex<T>.new(value): lock(body) runs body while the running task holds the mutex alone, and gives what body gives. The body takes the value's place (03 §2.3a rule 5a), m.lock { &n => n += 1; }: it reads and writes the value itself. The place is the call's — it ends with the body, and no closure in the body holds it (LYR-SEM0158) — so nothing reaches the value outside the lock.
  2. RwLock<T>, made by RwLock<T>.new(value): read(body) runs body with the value while no writer holds the lock — readers share it; write(body) runs body with the value's place (rule 1) while the task holds the lock alone. A writer that waits goes first: the readers that come after it wait for it.
  3. Once, made by Once.new(): run(body) runs body unless it has run to its end already; a call while another task runs it waits until that has ended. Where body throws, the error comes out of that call, and the next call runs body again.
  4. lock, read, write and run are waits: in a cancelled task they throw Cancelled (§3). They throw what their body throws.
  5. A lock orders (N7 P1): what a body did happens before what the next body that holds the lock does — the value one leaves is the value the next finds.
  6. A panic in a body poisons the lock (the review's M6-21). A panic unwinds nothing (§5 rule 1), so the body's lock would stay held: the scheduler releases what the panicked task held — newest first — and poisons it. From then on every lock, read, write and run on it is a panic, LYR-RT0019, lock poisoned by a panic: <code>: <message>, naming the first panic; a task that already waits for the lock wakes with the release and panics the same way. A Once whose body panicked is poisoned too. An error in a body — Cancelled among them — unwinds, the body's defer releases, and nothing is poisoned (rule 4).
  7. Semaphore, made by Semaphore.new(n) with n permits — a negative n panics (LYR-RT0008) —, is a waker (06 K4, the review's M6-31). acquire() takes a permit, waiting while none is left — a wait (rule 4). tryAcquire() takes one where one is left, says whether it did, and never waits. release() gives one back and wakes the tasks that wait: any task may, on any thread, and none needs to hold a permit. available() is the count now. A release orders as a lock does (rule 5): what a task did before release() happens before what a task does after the acquire() that takes that permit. A permit is no hold: a panic poisons no semaphore (rule 6).

11. Pools

A pool spreads tasks over threads of its own (06 G2, T1, P5). Pool is std.thread's (10 Q10; the module cut, M8b S1).

  1. Pool.new(n) starts n threads, one at least, each with a scheduler of its own (§9).
  2. pool.spawn(body) runs body as a task on one of the pool's threads, each in turn, and gives its handle (§2 rule 8): await() and cancel() work from any thread.
  3. pool.close() waits until every task given to the pool has ended, then ends its threads — each as a thread ends (§9 rule 2): what those tasks started there and left is cancelled, and has ended when close() returns. Closing a closed pool waits for nothing. close() is a wait (§3). A pool is Closeable (06 §7): under using let pool = Pool.new(4); no task of it outlives the block.
  4. A task given to a closed pool is a panic (LYR-RT0008). A task given while the pool closes is run or refused so — the check against the close and the hand-over to a thread are one step (the review's M6-27) —; none is left on a thread that has ended.
  5. parallelMap(xs, f) (06 P5) gives an array of f(x) for each element x of the view xs, in the elements' order. The calls run on the program's own pool — a thread for each processor, started at the first call, there until the program ends —, the first element's on the caller's thread. Where calls throw, parallelMap throws, once every call it started has ended, the error of the first element in order whose call throws: every element before it was called once, a later one perhaps not. It is a wait (§3): a cancelled caller cancels the calls it started and throws Cancelled.

12. Signals

A program learns of the system's signals through a channel (06 K5, 10 Q9). Signal and signals are std.os's (10 Q9, Q10; the module cut, M8b S1). No Lyric code runs in a signal handler.

  1. A Signal names a signal abstractly: Interrupt, Terminate, Hangup, Quit, User1, User2, WindowChange, or Other(n) — the system's number n. Windows knows Interrupt (Ctrl+C, Ctrl+Break) and Terminate (its console closes) only.
  2. signals(s…) gives a Channel<Signal> that the given signals come in on: from then on they no longer do what the system does with them — end the program, mostly — but arrive in the channel. Each comes to every channel that asked for it.
  3. A signal is no counter: two that come before the first went out may arrive as one, and one that finds a channel's buffer full — sixteen — is lost for that channel (the review's M6-28).
  4. Closing the channel ends its subscription at once (K5: the scheduler swallows no signal): a signal no channel asks for any more is the system's again from the close on — not from the next one, which was swallowed.
  5. KILL and STOP never come — the system does not deliver them — and neither do the faults (SEGV, BUS, FPE, ILL, ABRT), which end the program with a crash report, nor PIPE, CHLD and ALRM, which the runtime keeps. A runtime that a host starts without signal handlers catches none.