Automatic and Efficient Variability-Aware Lifting of Functional Programs

on YouTube ↗15m

" summary

Implements a variability-aware extension of a PCF-like functional language (pattern matching, polymorphic lists and pairs) and a Haskell variability library plus a program rewriter; compares shallow lifting (Applicative-style cross-product black box) to deep lifting (rewrite that pushes lifted application into function bodies to share work). Evaluates six analyses on BusyBox (504 C files); shallow beats brute force after ~5 variants, deep beats both after ~30–40 and reaches about 100× speedup at ~900 variants and up to ~1000× at ~3000 variants.

AI-written summary · about

" chapters (11)

1. 0:00AUTOMATIC AND EFFICIENT VARIABILITY-AWARE LIFTING OF FUNCTIONAL PROGRAMS
2. 1:50ANNOTATIVE SPL EXAMPLE - INSTANTIATION
3. 3:06PRODUCT LINE ANALYSIS – BRUTE FORCE
4. 3:48PRODUCT LINE ANALYSIS – LIFTING INDIVIDUAL ANALYSIS
5. 4:56PRODUCT LINE ANALYSIS – LIFTING INTERPRETATION
6. 5:42BEYOND DATALOG?
7. 6:55LIFTING TYPES AND VALUES
8. 8:11LIFTED FUNCTIONS
9. 9:37SHALLOW LIFTING
10. 10:48DEEP LIFTING
11. 12:00EVALUATION - CASE TERMINATION BENCHMARK

" related talks

• 41mEvolving Functional Programming LanguagesErik Osheim · Lambda World 2016
• 36mConcrete Functional ProgrammingKamila Szewczyk · Lambda World 2024
• 45mAPLicative Programming with Naperian FunctorsJeremy Gibbons · Lambda World 2017
• 30mModularity, Code Specialization, and Zero-Cost Abstractions for Program Verifica...Aymeric Fromherz, Jonathan Protzenko, Son Ho · ICFP 2023
• 30mFP²: Fully in-Place Functional ProgrammingAnton Lorenzen, Daan Leijen, Wouter Swierstra · ICFP 2023
• 44mFunctional Programming You Already KnowKevlin Henney · Codemotion Rome 2015
• 26mInfinite PossibilitiesEgon Elbre · GopherCon AU 2023
• 52mFunctional Patterns for the Object OrientedØystein Kolsrud · NDC Oslo 2019