Step in Tine: Forking Processes in Functional Choreographies
Choreographic programming guarantees deadlock freedom by compiling one global program into per-process code. Existing functional choreographic languages cannot dynamically fork new processes, a core concurrency primitive.
The authors define λ⋔, a functional choreographic calculus extending λqc. It supports process spawning alongside higher-order functions, process polymorphism, multiply-located values and first-class process names. They define a network language and endpoint projection, and introduce divergence-weakened soundness to handle multiply-located computations. All theorems and a bidirectional type inference/elaboration pass are formalized in Lean 4 with Mathlib. AI tools (Aristotle, Claude) generated the artifact from human-written paper proofs, and the authors corrected flaws before completing the formalization.
λ⋔ is proven deadlock-free, and the projection of a typed choreography never deadlocks. The Lean artifact, available on Zenodo, depends only on Lean's three standard axioms. It types, projects and runs examples such as a dynamically sized ring scheduler.
