Abstract tolkning är en teknik för att utveckla statiska analyser. Men att bevisa abstrakta tolkar ljud är utmanande för intressanta analyser, på grund av den höga bevis komplexitet och bevisarbete. För att minska komplexiteten och ansträngningen föreslår vi en ram för abstrakta tolkar som gör deras soliditet till bevis på komposition. Nyckeln till vår strategi är att fånga likheterna mellan konkreta och abstrakta tolkar i en enda gemensam tolk, parameteriserad över ett pilbaserat gränssnitt. I vårt ramverk reduceras ett sundhetsbevis till att visa återanvändbar ljudstyrka lemmas över de konkreta och abstrakta instanserna av detta gränssnitt; ljudligheten hos de övergripande tolkarna följer av ett generiskt teorem. För att ytterligare minska bevisinsatsen utforskar vi förhållandet mellan ljud och parametrikitet. Parametricitet ger oss inte bara användbara riktlinjer för hur man utformar icke-bladiga gränssnitt för delade tolkar, utan ger oss också sundhet av delade rena funktioner som fria teorem. Vi implementerade vårt ramverk i Haskell och utvecklade en k-CFA-analys för PCF och en trädformsanalys för Stratego. Vi kunde bevisa båda analyserna ljudkompositionellt med hanterbar komplexitet och ansträngning, jämfört med en konventionell ljudstyrka. 1 INLEDNING Abstrakt tolkning [Cousot och Cousot 1979] är ett förhållningssätt till statisk analys med sundhet i hjärtat: En abstrakt tolk måste approximera beteendet hos ett program som föreskrivs av en betongtolk. Detta soundness proposition kan vägleda utformningen av abstrakta tolkar [Cousot 1999] och föreskriver vad som behöver bevisas om analysen. Tyvärr är det mycket mindre tydligt hur man ska bevisa ett abstrakt tolkljud och i synnerhet hur man ska bryta ner sundhetsbeviset till beviskrav av hanterbar storlek. Ändå är det viktigt att bevisa att det är sunt i sammansättningen när man utvecklar verifierade abstrakta tolkar för verkliga språk för att minska bevisens komplexitet och bevisinsats.
REF presenterade en modulär, pilbaserad abstrakt tolk som gör det möjligt att konstruera ljudkorrektur.
Compositional soundness proofs of abstract interpreters
{'venue': 'PACMPL', 'journal': None, 'mag_field_of_study': ['Computer Science']}