机会主义的并行Lambda演算

《Proceedings of the ACM on Programming Languages》：Opportunistically Parallel Lambda Calculus

针对脚本语言外部调用等待时间长的问题，本文提出基于核心λ演算的机会评估策略，自动并行分发并流式处理外部调用，确保执行完整且保持程序原意。实验表明，该策略在调用LLMs和API时，较Python提速6.2倍，接近手动优化的Rust实现，Tree-of-Thoughts场景提升6.2倍。

　　

摘要

脚本语言被广泛用于执行诸如调用本地库和网络服务等外部操作。在这些脚本中，执行时间往往大部分被等待外部操作所消耗，这使得传统的单一语言优化方法变得无效。为了解决这个问题，我们提出了一种基于核心lambda演算的新的机会主义评估策略，该策略能够自动并行调度独立的外部调用并流式处理其结果。我们证明了我们的方法是收敛的（即最终能够完成所有操作），同时确保了程序员的原始意图得到保留，并且最终能够执行每一个外部调用。我们在一种名为Opal的脚本语言中实现了这一策略。我们通过使用大型语言模型（LLMs）和其他API来演示Opal的灵活性和性能。在五个示例脚本中，我们将Opal与几种最先进的基线算法进行了比较，结果显示：与标准的顺序Python相比，机会主义评估方法显著提高了总运行时间（最多提高了6.2倍）和延迟（最多提高了12.7倍），同时与手工优化的异步Rust相比，运行时间开销仅增加了1.3%到18.5%。对于Tree-of-Thoughts这种流行的LLM推理方法，我们的实现性能提升了6.2倍，优于原作者的实现。