kth.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Suspension Analysis and Selective Continuation-Passing Style for Universal Probabilistic Programming Languages
Oracle, Stockholm, Sweden.
KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Software and Computer systems, SCS. (Digital Futures)ORCID iD: 0009-0003-9325-8405
Department of Data Science and Analytics, BI Norwegian Business School, Oslo, Norway.
KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Software and Computer systems, SCS. (Digital Futures)ORCID iD: 0009-0001-0678-549X
Show 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

Available from: 2024-05-16 Created: 2024-05-16 Last updated: 2024-09-12Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Hummelgren, LarsEriksson, OscarBroman, David

Search in DiVA

By author/editor
Hummelgren, LarsEriksson, OscarBroman, David
By organisation
Software and Computer systems, SCS
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 44 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf