Exact Recursive Probabilistic Programming

on YouTube ↗16m

" summary

A probabilistic programming compiler called Purple expresses unbounded recursion and then eliminates recursive data types using defunctionalization and refunctionalization, verified by a linear type system. It translates programs to systems of equations and solves least fixed points for exact inference, automatically recovering polynomial algorithms (e.g., CYK-like cubic parsing) from naively exponential descriptions. A greedy search finds a valid sequence of transformations when one exists. Benchmarks show Purple outperforms WebPPL and Dice, handling string lengths up to ~400.

AI-written summary · about

" chapters (11)

1. 0:00Exact recursive PP intro
2. 1:17Motivation for probabilistic programming languages
3. 3:24Example of a probabilistic context-free grammar
4. 5:29Denotational semantics for exact inference
5. 7:54Recursive data in PPLs
6. 9:37Defunctionalization techniques
7. 11:23Linear types for performance
8. 12:27Purple’s unique features
9. 12:49Q&A on non-termination
10. 13:54Comparison with Sai PPL
11. 14:17Ambiguity in grammar programs