Suspension Analysis and Selective Continuation-Passing Style for Universal Probabilistic Programming LanguagesShow others and affiliations
2024 (English)In: Programming Languages and Systems - 33rd European Symposium on Programming, ESOP 2024, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2024, Proceedings, Springer Nature , 2024, Vol. 14577, p. 302-330Conference paper, Published paper (Refereed)
Abstract [en]
Universal probabilistic programming languages (PPLs) make it relatively easy to encode and automatically solve statistical inference problems. To solve inference problems, PPL implementations often apply Monte Carlo inference algorithms that rely on execution suspension. State-of-the-art solutions enable execution suspension either through (i) continuation-passing style (CPS) transformations or (ii) efficient, but comparatively complex, low-level solutions that are often not available in high-level languages. CPS transformations introduce overhead due to unnecessary closure allocations—a problem the PPL community has generally overlooked. To reduce overhead, we develop a new efficient selective CPS approach for PPLs. Specifically, we design a novel static suspension analysis technique that determines parts of programs that require suspension, given a particular inference algorithm. The analysis allows selectively CPS transforming the program only where necessary. We formally prove the correctness of the analysis and implement the analysis and transformation in the Miking CorePPL compiler. We evaluate the implementation for a large number of Monte Carlo inference algorithms on real-world models from phylogenetics, epidemiology, and topic modeling. The evaluation results demonstrate significant improvements across all models and inference algorithms.
Place, publisher, year, edition, pages
Springer Nature , 2024. Vol. 14577, p. 302-330
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 14577
Keywords [en]
Continuation-passing style, Probabilistic programming, Static analysis
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-346543DOI: 10.1007/978-3-031-57267-8_12ISI: 001281762600012Scopus ID: 2-s2.0-85192176283OAI: oai:DiVA.org:kth-346543DiVA, id: diva2:1858459
Conference
33rd European Symposium on Programming, ESOP 2024, held as part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2024, Luxembourg City, Luxembourg, Apr 6 2024 - Apr 11 2024
Note
QC 20240521
Part of ISBN 978-303157266-1
2024-05-162024-05-162024-09-12Bibliographically approved