Loop fusion-ett program omvandling för att sammanfoga flera på varandra följande loopar till en enda en-har studerats främst för kompilatoroptimering. I detta dokument, föreslår vi en ny slinga fusionsstrategi, som kan förena alla slingor-jämn slingor med databeroende-och visa att det är användbart för programverifiering eftersom det kan förenkla slingor invarianter. Kruxet i vår slinga fusion är följande observation: om tillståndet efter den första slingan var känt, de två slinga kropparna kunde beräknas samtidigt utan att lida av databeroende genom att döpa om programvariabler. Vår slinga fusion producerar ett program som gissar det okända tillståndet efter den första slingan icke-deterministiskt, utför den sammanslagna slingan där variabler döps om, jämför det gissade tillståndet och det tillstånd som faktiskt beräknas av den sammanslagna slingan, och, om de inte matchar, divergerar. De två sista stegen i jämförelse och divergens är avgörande för att delvis bevara korrektheten. Vi kallar vår strategi "Gissa-och-assume" eftersom, förutom det första steget att gissa, de två sista stegen kan uttryckas genom pseudo-instruktion antagande, som används i programverifiering. Vi formaliserar vår slinga fusion för ett enkelt tvingande språk och bevisa att det bevarar partiell korrekthet. Vi utökar vidare tekniken "Gsess-and-assume" till att vända genomförandet av slingor, vilket är användbart för att verifiera en viss typ av på varandra följande slingor. Slutligen bekräftar vi genom experiment att våra omvandlingstekniker verkligen är effektiva för toppmoderna modellkontroller att verifiera några små program som de inte kunde.
Liknande idéer för loopfusion har använts för andra ändamål, t.ex. att förenkla loopinvarianter i ett enda program och för programoptimering REF.
A guess-and-assume approach to loop fusion for program verification
{'venue': "PEPM '18", 'journal': None, 'mag_field_of_study': ['Computer Science']}