Analysing the complexity of functional programs: higher-order meets first-order

DOI10.1145/2784731.2784753MaRDI QIDQ2981952zbMATH OpenOpenAlexFDO

Authors Martin Avanzini, Ugo Dal Lago, Georg Moser

Publication date 10 May 2017

Published in Proceedings of the 20th ACM SIGPLAN International Conference on Functional Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1506.05043, https://hal.inria.fr/hal-01231809/file/paper.pdf

zbMATH Keywords

defunctionalisationresource analysisterm rewritingtermination

Mathematics Subject Classification ID

Functional programming and lambda calculus (68N18) Grammars and rewriting systems (68Q42)

Abstract: We show how the complexity of higher-order functional programs can be analysed automatically by applying program transformations to a defunctionalized versions of them, and feeding the result to existing tools for the complexity analysis of first-order term rewrite systems. This is done while carefully analysing complexity preservation and reflection of the employed transformations such that the complexity of the obtained term rewrite system reflects on the complexity of the initial program. Further, we describe suitable strategies for the application of the studied transformations and provide ample experimental data for assessing the viability of our method.

Recommendations

• Higher-order interpretations and program complexity
• Higher-order interpretations and program complexity
• scientific article; zbMATH DE number 512849
• Static complexity analysis of higher order programs
• A complexity analysis of functional interpretations
• Programming Languages and Systems
• Application of complexity metrics in functional languages
• Flow analysis of lazy higher-order functional programs
• Adapting functional programs to higher order logic

Cited in

(22)

• From Jinja bytecode to term rewriting: a complexity reflecting transformation
• Automated higher-order complexity analysis
• Mechanisation of the AKS algorithm
• Runtime complexity analysis of logically constrained rewriting
• Automated complexity analysis of Nuprl extracted programs
• Higher-order interpretations and program complexity
• Reachability analysis of innermost rewriting
• A Transformational Approach to Polyvariant BTA of Higher-Order Functional Programs
• scientific article; zbMATH DE number 4106261 (Why is no real title available?)
• scientific article; zbMATH DE number 177794 (Why is no real title available?)
• On the enumeration of closures and environments with an application to random generation
• Counting environments and closures
• Kruskal's tree theorem for acyclic term graphs
• Denotational semantics as a foundation for cost recurrence extraction for functional languages
• scientific article; zbMATH DE number 7204445 (Why is no real title available?)
• Static complexity analysis of higher order programs
• Type-based analysis of logarithmic amortised complexity
• Type-based complexity analysis of probabilistic functional programs
• Data-driven runtime complexity analysis
• Automating approximation analysis for Nash equilibria algorithms in two-player games
• Worst-case input generation for concurrent programs under non-monotone resource metrics
• ATLAS: automated amortised complexity analysis of self-adjusting data structures

This page was built for publication: Analysing the complexity of functional programs: higher-order meets first-order

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2981952)