AUTOMAP: Inferring Rank-Polymorphic Function Applications with Integer Linear Programming
summary
Automatic insertion of map/rep annotations reduces array boilerplate by encoding rank differences as constraints, linearizing them into integer linear programming and solving globally per top-level definition. A rule forbids mapping and replicating the same application, and the solver chooses the minimize maps and reps solution; ambiguous cases produce an error listing the minimal alternatives. Prototype in the Fuar compiler works end-to-end, most ILPs are tiny (one hit ~28k), and typechecking cost is about 2.5× with current unoptimized implementation.
AI-written summary · about
chapters (10)
- 0:00AUTOMAP introduction
- 1:03Rank polymorphism in Futhar
- 3:10Rank-polymorphic elaboration
- 5:20Disambiguating map/rep
- 9:33Rank inference with ILP
- 15:09Ambiguity handling
- 16:35Benchmarking results
- 17:59Comparison with systems
- 19:25Summary and future work
- 20:29Q&A
related talks
20mAUTOMAP: Inferring Rank-Polymorphic Function Applications with Integer Linear Programming
15mScaling Optimization Over Uncertainty via Compilation
08mCompiling pattern matching to in-place modifications
23mBetter Defunctionalization through Lambda Set Specialization
36mRank-Polymorphism for Shape-Guided Blocking
29mParallelism-preserving automatic differentiation for second-order array languages
23mPoseidon: Profile-Guided Numerical Rewriting at Full-Application Scale
47mLogic Programming à la Carte