Vi inför ett ramverk som gör det möjligt för domänexperter att manipulera beräknings termer i syfte att härleda bättre och effektivare implementeringar. Den använder avdragsgilla resonemang för att generera bevisligen korrekt effektiva implementeringar från en mycket hög nivå specifikation av en algoritm, och induktiva begränsningar-baserad syntes för att förbättra automatisering. Semantisk information är kodad till programtermer genom användning av förfining typer. I detta dokument utvecklar vi tekniken inom ramen för ett system som heter Bellmania som använder lösare-stödda taktik för att härleda parallella split-and-conquer implementeringar av dynamiska programmeringsalgoritmer som har bättre lokalitet och är betydligt effektivare än traditionella loop-baserade implementationer. Bellmania innehåller ett språk på hög nivå för att specificera dynamiska programmeringsalgoritmer och en kalkyl som underlättar gradvis omvandling av dessa specifikationer till effektiva implementationer. Dessa omvandlingar formaliserar split-and-conquer teknik; ett visualiseringsgränssnitt hjälper användare att interaktivt styra processen, medan en SMT-baserad back-end verifierar varje steg och tar hand om låg nivå resonemang som krävs för parallellism. Vi har använt systemet för att generera bevisligen korrekta implementationer av flera algoritmer, inklusive några viktiga algoritmer från beräkningsbiologi, och visa att prestandan är jämförbar med den bästa manuellt optimerade koden.
Nyligen, en delmängd av författarna till den nuvarande artikeln utvecklat ett annat system som heter Bellmania REF som använder lösare-stödda taktik för att härleda parallella rekursiva splitter-och-konquer implementeringar av DP algoritmer.
Deriving divide-and-conquer dynamic programming algorithms using solver-aided transformations
{'venue': 'OOPSLA 2016', 'journal': None, 'mag_field_of_study': ['Computer Science']}