Abstrakt. Hofmann och Jost har presenterat en hög rymdanalys [1] som finner linjära rymdgränser för många funktionella program. Den använder en amorterad analys: att tilldela hypotetiska mängder fritt utrymme (så kallad potential) till datastrukturer i proportion till deras storlek med hjälp av typanteckningar. Restriktioner på dessa kommentarer i typsystemet säkerställer att den totala potential som tilldelas inmatningen är en övre gräns på det totala minne som krävs för att uppfylla alla tilldelningar. Vi beskriver ett relaterat system för att begränsa stacken utrymmeskrav som använder djupet av datastrukturer, genom att uttrycka potential i termer av maxima samt summor. Detta uppnås genom att lägga till extra struktur till skriva sammanhang (inspirerad av O'Hearns klumpade maskinskrivning [2] ) för att beskriva formen av gränserna. Vi kommer också att presentera de extra steg som måste tas för att konstruera en maskinskrivning under analysen. Att erhålla gränser för programmens resursbehov kan vara avgörande för att säkerställa att de har tillförlitlighet och säkerhetsegenskaper, särskilt för användning i begränsade system som mobiltelefoner, smartkort och inbyggda system. Hofmann och Jost har presenterat en typbaserad avskrivningarad analys för att hitta övre gränser på högminnet som krävs för program i ett enkelt funktionellt programmeringsspråk [1]. Formen för dessa gränser är begränsad till linjära funktioner med avseende på storleken på programmets ingång. Lyckligtvis är detta tillräckligt för en mängd olika intressanta program. Dessutom användes analysen med framgång för att certifiera sådana gränser i ett system för bevisbärande kod [3]. Men det är också viktigt att binda stacken utrymme krav, särskilt för funktionella program där det är lätt att orsaka överdriven stack användning av misstag. Hofmann-Jost analysen har tidigare anpassats för att mäta stack utrymme [4, 5], men formen av gränserna var återigen begränsad till linjära funktioner i termer av den totala storleken på inmatningen. I detta arbete presenterar vi en liknande analys där gränser ges som max-plus uttryck på djupet av datastrukturer. Detta är mycket mer exakt för program som arbetar med trädstrukturerade data. Liksom Hofmann-Jost består vår analys av två delar: ett typsystem som intygar att en given gräns verkligen är en övre gräns på stackens minneskrav, och en inferensprocedur baserad på linjär programmering för att
Campbell REF ger nyligen en typbaserad metod för att stapla rymdanalys.
Amortised memory analysis using the depth of data structures
{'venue': 'In Proceedings of ESOP 2009: European Symposium on Programming, LNCS 5502', 'journal': None, 'mag_field_of_study': ['Computer Science']}