En viktig utmaning i programsyntesen handlar om hur man effektivt söker efter det önskade programmet i utrymmet för möjliga program. Vi föreslår en allmän strategi för att påskynda sökning-baserad programsyntes genom att partiska sökningen mot troliga program. Vår strategi är inriktad på en standardformulering, syntaxstyrd syntes (SyGuS), genom att utöka grammatiken för möjliga program med en probabilistisk modell som dikterar sannolikheten för varje program. Vi utvecklar en viktad sökalgoritm för att effektivt räkna upp program efter deras sannolikhet. Vi föreslår också en metod baserad på överföringslärande som gör det möjligt att effektivt lära sig en kraftfull modell, så kallad probabilistisk högre ordningens grammatik, från kända lösningar inom en domän. Vi har implementerat vår strategi i ett verktyg som kallas Euphony och utvärdera det på SyGuS benchmarking problem från en mängd olika domäner. Vi visar att Euphony kan lära sig bra modeller med hjälp av lättillgängliga lösningar och uppnå betydande prestandavinster jämfört med befintliga allmänna ändamål samt domänspecifika synthesizers.
Euphony REF utför en viktad räknande sökning med hjälp av A*-sökalgoritmen, där vikterna kommer från en probabilistisk högre ordningen grammatik (PHOG).
Accelerating search-based program synthesis using learned probabilistic models
{'venue': 'PLDI 2018', 'journal': None, 'mag_field_of_study': ['Computer Science']}