I den här artikeln presenteras ett resursanalyssystem för OCaml-program. Systemet härleder automatiskt värsta tänkbara resursgränser för högre-order polymorfa program med användardefinierade induktiva typer. Tekniken är parametrisk i resursen och kan härleda gränser för tid, minnesfördelning och energianvändning. De härledda gränserna är multivariat resurs polynomials som är funktioner av olika storlek parametrar som beror på standard OCaml typer. Bound inference är helt automatisk och reduceras till ett linjärt optimeringsproblem som överförs till en off-the-shelf LP lösare. Tekniskt är analyssystemet baserat på en ny multivariat automatisk avskrivningarad resursanalys (AARA). Den bygger på befintligt arbete på linjär AARA för högre ordningsprogram med användardefinierade induktiva typer och på multivariat AARA för första ordningens program med inbyggda listor och binära träd. Detta är den första amorterade analysen, som automatiskt härleder polynomiska gränser för högre funktioner och polynomiska gränser som beror på användardefinierade induktiva typer. Dessutom hanterar analysen en begränsad form av biverkningar och överträffar till och med den linjära inferensen hos tidigare system. Samtidigt bevarar den expressiviteten och effektiviteten hos befintliga AARA-tekniker. Det praktiska i analyssystemet visas med en implementering och integration med Inrias OCaml kompilator. Implementeringen används för att automatiskt härleda resursgränser för 411 funktioner och 6018 rader kod härledda från OCaml bibliotek, CompCert kompilatorn, och implementationer av läroboksalgoritmer. I en fallstudie begränsar systemet antalet frågor som skickas av OCaml program till DynamoDB, en kommersiell NoSQL moln databastjänst. 1. Vad är det för fel på dig? Vi presenterar det första genomförandet av en AARA som är integrerad med en industriell hållfasthetskompilator. 2. Utgångspunkten är följande: Vi utvecklar den första automatiska resursanalys som leder till multivariata polynomgränser som beror på storleksparametrar för användardefinierade trädliknande datastrukturer. 3. Vad är det som händer? Vi presenterar den första AARA som härleder polynomiska gränser för högre ordningsfunktioner. De tekniker vi utvecklar är inte knutna till en viss resurs utan är parametriska i den resurs av intresse. RAML härleder snäva gränser
I nyare arbete REF, metoden har lyfts till högre ordning fall och RAML kan nu gränssnitt med Inrias OCaml kompilator.
Towards automatic resource bound analysis for OCaml
{'venue': 'POPL 2017', 'journal': None, 'mag_field_of_study': ['Computer Science']}