Opportunistically Parallel Lambda Calculus
summary
Proposes an evaluation strategy and core calculus (Opportunistic Lambda Calculus) that dispatches independent external calls as holes, resolves them incrementally using Church-encoded partial data, and streams results; implemented as Opal embedded in a Python subset with symbolic-extraction and small-step semantics. Proves confluence and eventual execution of external calls. Evaluates on five LLM-heavy scripts, showing up to 6.2× total-time speedup and 12.7× latency improvement over sequential Python, with 1.3%–18.5% overhead versus hand-tuned async Rust.
AI-written summary · about
chapters (11)
- 0:00Compound AI systems intro
- 1:45Glue script bottlenecks
- 3:33Manual parallelization challenges
- 4:57Opportunistic lambda calculus core
- 8:25Lambda O assumptions and theorems
- 9:05Opportunistic evaluation strategy
- 9:45Church encodings for partial data
- 10:29Opel scripting language
- 10:49Experimental results
- 11:52Conclusion and future work
- 12:12Q&A
related talks
01h 06mProject Lambda: Simplifying Concurrent Programming in Java SE 8
30mCalculating Compilers for Concurrency
40mWhen magic meets multicore - OCaml and its elegant era of parallelism
48m“Is Parallel Programming still hard? PART 2 of 2”
53mProgramming with Futures, Lattices and Quiescence
26mHigher-Order Leak and Deadlock Free Locks
01h 01mThe Future of Concurrency and Parallelism
35mAutomatic Parallelism Management