Partial Evaluation of Reversible Flowchart Programs
summary
Presents a fully formalized specializer for a reversible flowchart language (RL), implemented and published on GitHub, with concrete fixes: uniform binding-time analysis to avoid non‑injective specialization, forcing mutated outputs to dynamic when needed, and emitting assertions to preserve comfrom semantics. Experiments specialize a symmetric encryption routine and a reversible Turing‑machine interpreter (Bennett style), demonstrate the first inversion projection (specializing the inverted interpreter to produce an inverted program), and report residual code bloat from unrolled loops and runtime improvements up to 6.5x speedup when redundant assertions are removed.
AI-written summary · about
chapters (17)
- 0:00Partial evaluation introduction
- 1:45Goals and contributions
- 2:25RL language overview
- 4:56Challenges in reversible PE
- 9:12Solutions for PE issues
- 9:33Specialization demo: partition
- 11:20Experiments: Turing machine interpreters
- 13:56Performance analysis
- 14:58Conclusion and future work
- 15:40Q&A: Speed-up comparisons
- 16:22Q&A: Linearity in pattern matching
- 17:25Q&A: RL target users
- 18:51Q&A: Speed-up basis in TM examples
- 19:37Q&A: Thesis future work
- 20:43Q&A: Testing reversible programs
- 22:07Q&A: Diagram vs translation differences
- 24:55Q&A: RL reversibility vs Janus
related talks
29mA Flow-Insensitive-Complete Program Representation
19mCompiling Probabilistic Programs for Variable Elimination with Information Flow
01h 01mA partial history of partial evaluation
23mAn Abstract Interpretation for SPMD Divergence on Reducible Control Flow Graphs
20mSemantic Reification: A New Paradigm for Random Program Generation
16mMulti-stage Relational Programming
09mCompilers for nothing, executables for free!
21mFlow-Analysis-Based Closure Optimization