Detta dokument presenterar en ny teknik för typstyrd värsta-fall-generering för funktionella program. Tekniken bygger på automatisk avskrivningarad resursanalys (AARA), en typbaserad teknik för att härleda symboliska gränser för resursanvändning av funktioner. Värst möjliga indatagenerering utförs av en algoritm som tar som indata en funktion, dess resursannoterade typ härledning i AARA, och ett skelett som beskriver formen och storleken på den indata som ska genereras. Om framgång, algoritmen fyller i heltal, booleaner och data strukturer för att producera ett värde av den form som ges av skelettet. Ljudets teorem anger att det genererade värdet uppvisar den högsta kostnaden bland alla argument för de funktioner som har formen av skelettet. Denna kostnad motsvarar exakt det värsta fall som fastställts av typen härledning. På detta sätt, ett framgångsrikt slutförande av algoritmen bevisar att bundet är tight för ingångar av den givna formen. Motsvarande, en relativ fullständig teorem bevisas visa att algoritmen lyckas om och endast om härledd värsta-fall bundna är tight. Teorem är relativt eftersom det beror på ett beslutsförfarande för begränsningslösning. Den tekniska utvecklingen presenteras för ett enkelt första ordningens språk med linjära resursgränser. Tekniken skalar dock till och har implementerats för Resource Aware ML, en implementering av AARA för ett fragment av OCaml med högre orderfunktioner, användardefinierade datatyper och typer för polynomgränser. Experiment visar att tekniken fungerar effektivt och kan härleda värsta fall ingångar med hundratals heltal för sortering algoritmer, operationer på sökträd, och inför i hash tabeller.
Tillvägagångssättet från REF kan syntetisera värsta fall ingångar, men storleken på indata måste fastställas a priori.
Type-guided worst-case input generation
{'venue': 'PACMPL', 'journal': None, 'mag_field_of_study': ['Computer Science']}