I detta dokument presenteras en ny statisk analys för att härleda övre gränser för den förväntade resursförbrukningen av probabilistiska program. Analysen är helt automatisk och härleder symboliska gränser som är multivariata polynomials i ingångarna. Den nya tekniken kombinerar manuell state-of-theart resonemang tekniker för probabilistiska program med en effektiv metod för automatisk resursbunden analys av deterministiska program. Det kan ses som båda, en utvidgning av automatisk amortiserad resursanalys (AARA) till probabilistiska program och en automatisering av manuellt resonemang för probabilistiska program som är baserade på svagaste förutsättningar. En fördel med tekniken är att den kombinerar klarheten och kompositionaliteten hos en svagast förkonditionerad analys med den effektiva automatiseringen av AARA. Som ett resultat kan bunden slutsats reduceras till off-the-shelf LP-lösning i många fall och automatiskt härledda gränser kan interaktivt utökas med standardprogramlogik om automatiseringen misslyckas. Med utgångspunkt i det befintliga arbetet kan analysens sundhet bevisas med avseende på en operationell semantik som bygger på Markovs beslutsprocesser. Teknikens effektivitet demonstreras med en prototypimplementation som används för att automatiskt analysera 39 utmanande probabilistiska program och randomiserade algoritmer. Experiment visar att de härledda konstanta faktorerna i gränserna är mycket exakta och till och med optimala för vissa program. CCS-koncept · Programvara och dess ingenjörskonst → Allmänna programmeringsspråk; · Sociala och professionella ämnen → Programspråkens historia;
Det mest relevanta resultatet ges i REF som presenterar en kompositionsstrategi för att härleda resursgränser för probabilistiska program.
Bounded expectations: resource analysis for probabilistic programs
{'venue': 'PLDI 2018', 'journal': None, 'mag_field_of_study': ['Computer Science']}