Synthesizing DSLs for Few-Shot Learning
summary
Constructs a precise formulation: given a base language L, a complexity measure (parse tree depth), and a metagrammar of candidate DSLs, decides whether a grammar exists that makes solutions to few‑shot training examples also solve held‑out tests. Proves decidable for depth‑based complexity when semantics admit a finite evaluator, reduces synthesis to tree automaton emptiness, shows solvable DSLs form a regular set of trees, handles macro grammars and an “adequate” variant, leaves parse‑tree‑size decidability and practical algorithms open.
AI-written summary · about
chapters (11)
- 0:00Few-shot symbolic learning intro
- 1:25Domain understanding for few-shot learning
- 2:50DSLs for few-shot synthesis
- 4:35DSL synthesis as learning
- 7:49Formalizing DSL synthesis
- 8:52Decidability in DSL learning
- 11:43Future work
- 12:26Summary
- 12:47Q&A: Genetic programming
- 13:30Q&A: ARC and DSL discovery
- 14:14Q&A: Few-shot learning role
related talks
18mLanguages with Decidable Learning: A Meta-theorem
30mYin-Yang: Concealing the Deep Embedding of DSLs (Most Influential Paper)
01h 01mChallenges in the Design and Implementation of Teaching Languages for EDSLs
31mLetting users do the undecidable: lessons from program synthesis
17mSynthesizing MILP Constraints for Efficient and Robust Optimization
14mOne Down, 699 to Go: or, synthesising compositional desugarings
21mSynthesizing Formal Semantics from Executable Interpreters
35mDesigning Domain-Specific Languages: A Comparison of Three Approaches by Example