Why fork&join are fundamental to computation

Recently, I tried to write a Djot parser in Zig that made me want to write this article to explain why causality is a basic concept of computation and why lambda calculus disrespects causality. The causality operator was a part of algograph from the start, precisely because it is indispensible to a model of computation based on the reduction and rewriting of a graph.

To see why the concept of causal ordering is indispensible to computation, let’s look at the first section of the Djot syntax reference.

The task: turn Djot input …

_This is *regular_ not strong* emphasis

… into HTML output.

<p><em>This is *regular</em> not strong* emphasis</p>

Here’s the conundrum: after the algorithm has processed the second _ in the input, it will

1. process the next byte in the input ( )
2. emit a span (<em>) with the text content This is *regular

The question is, which first?

The answer: it is not the parser algorithm’s responsibility to decide which to do first, but rather a fundamental limitation of lambda calculus. The parser algorithm only cares about that both steps are done afterwards, not which is done first.

Guile famously have 7 layers of the language during compilation, each lowering to the next. I expect Djot to have 4: input byte stream, token stream, syntax event stream, output byte stream. I don’t want to decide on ordering that’s in no part the algorithm’s responsibility, so I stopped working on the parser only after completing the “Precedence” section of Djot syntax reference to write this article.

What is causal ordering

tl;dr

Causal ordering in algograph have two kinds: implicit and explicit.

Implicit causal ordering in algograph is like fork/join from Cilk, except it does not have its own syntax. The programmer draws the algorithm as a graph, and the runtime (compiler) takes care of the ordering.

equivalent of a fork point:

• Go’s go f() and phony
• Pony’s be f()

equivalent of a join point:

• C++’s std::barrier with multiple inputs carrying data

Explicit causal ordering in algograph is represented with an operator. A causality operator is like a one-time use semaphore, where one execution context waits on another.

If you find this explanation tedious to understand as much as I find it tedious to write, sorry. If you use an algorithmic language with causal ordering as a language-level feature, your imagination¹ will not be restricted by the flaw of lambda calculus.

Appendix: Heartbeat scheduling

Heartbeat scheduling has low overhead on CPU with branch prediction.
Zig: https://github.com/judofyr/spice
Rust: https://github.com/dragostis/chili

However, it requires every execution context to do a bit of scheduling. If used outside the pathological fork/join pattern, it may perform a bit worse.