En central metod för att analysera asymptotic komplexiteten i ett funktionellt program är att extrahera och sedan lösa en upprepning som uttrycker utvärderingskostnader i termer av input storlek. Det relevanta begreppet inmatningsstorlek är ofta specifikt för en datatyp, med åtgärder som inkluderar längden på en lista, det maximala elementet i en lista, och höjden på ett träd. I detta arbete ger vi en formell redogörelse för utvinningen av kostnad och storlek upprepningar från högre ordning funktionella program över induktiva datatyper. Vår strategi möjliggör ett brett spektrum av programmerare specificerade begrepp av storlek, och ser till att de extraherade upprepningar korrekt förutsäga utvärderingskostnader. För att extrahera en upprepning från ett program, gör vi först kostnader explicit genom att tillämpa en monadisk översättning från källspråket till ett komplext språk, och sedan abstrakta datatyp värden som storlekar. Size abstraction kan göras semantiskt, arbeta i modeller av komplexitetsspråket, eller syntactically, genom att lägga till regler till en förhandsbedömning. Vi ger flera olika modeller av komplexitetsspråket, som stöder olika begrepp av storlek. Dessutom bevisar vi genom en logisk relation argumentet att upprepningar som extraheras genom denna process är övre gränser för utvärderingskostnader; beviset är helt syntaktisk och därför gäller för alla de modeller vi anser.
Slutligen definierar REF en utveckling från ett källspråk till ett komplicerat språk från vilket kostnadsåterkommanden kan extraheras.
Denotational cost semantics for functional languages with inductive types
{'venue': 'ICFP 2015', 'journal': None, 'mag_field_of_study': ['Computer Science']}