#9207: Detect obvious cases of infinite recursion. ------------------------------------+-------------------------------------- Reporter: mrugiero | Owner: Type: feature request | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: invalid | Keywords: infinite recursion Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: None/Unknown | Blocked By: Test Case: | Related Tickets: Blocking: | ------------------------------------+-------------------------------------- Comment (by altaic): Replying to [comment:7 mrugiero]:
Those papers certainly sound interesting.
Whoops, missed your comment, sorry! Here are the papers I have that are related to static complexity analysis, in no particular order: * Elvira Albert, Puri Arenas, Samir Genaim, Germán Puebla. ''Cost Relation Systems: A Language-Independent Target Language for Cost Analysis'' * Nao Hirokawa. ''Automated Complexity Analysis Based on the Dependency Pair Method'' * Jan Hoffmann and Zhong Shao. ''Type-Based Amortized Resource Analysis with Integers and Arrays'' * Jan Hoffmann and Martin Hofmann. ''Amortized Resource Analysis with Polymorphic Recursion and Partial Big-Step Operational Semantics'' * Jan Hoffmann and Martin Hofmann. ''Amortized Resource Analysis with Polynomial Potential: A Static Inference of Polynomial Bounds for Functional Programs (Extended Version)'' * Jennifer Paykin. ''Automated Cost Analysis of a Higher-Order Language in Coq'' * Lars Noschinski, Fabian Emmes, and Jürgen Giesl. ''A Dependency Pair Framework for Innermost Complexity Analysis of Term Rewrite Systems'' * Sumit Gulwani. ''SPEED: Symbolic Complexity Bound Analysis'' * Edward Z. Yang, David Mazières. ''Resource Limits for Haskell'' * Jan Hoffmann, Klaus Aehlig, and Martin Hofmann. ''Resource Aware ML'' * Jan Hoffmann, Klaus Aehlig, and Martin Hofmann. ''Multivariate Amortized Resource Analysis'' * Jan Hoffmann. ''Types with Potential: Polynomial Resource Bounds via Automatic Amortized Analysis'' * Martin Avanzini, Georg Moser, and Andreas Schnabl. ''Automated Implicit Computational Complexity Analysis (System Description)'' * Aart Middeldorp, Georg Moser, Friedrich Neurauter, Johannes Waldmann, and Harald Zankl. ''Joint Spectral Radius Theory for Automated Complexity Analysis of Rewrite Systems'' * Chris Okasaki. ''Purely Functional Data Structures'' * Alessandra Di Pierro and Herbert Wiklicky. ''Probabilistic Analysis of Programs: A Weak Limit Approach'' * R. M. Amadio, N. Ayache, F. Bobot, J. P. Boender, B. Campbell, I. Garnier, A. Madet, J. McKinna, D. P. Mulligan, M. Piccolo, R. Pollack, Y. R ́egis-Gianas, C. Sacerdoti Coen, I. Stark, and P. Tranquilli. ''Certified Complexity (CerCo)'' * M. Brockschmidt, F. Emmes, S. Falke, C. Fuhs, and J. Giesl. ''Alternating Runtime and Size Complexity Analysis of Integer Programs'' * Wolf Zimmermann. ''Automatic Worst Case Complexity Analysis of Parallel Programs'' * Jean-Pierre Jouannaud and Weiwen Xu. ''Automatic Complexity Analysis for Programs Extracted from Coq Proof'' * Sébastian Pop. ''Analysis of induction variables using chains of recurrences: extensions'' * François Pottier. ''Types for complexity-checking'' (presentation) * Michael Kruse. ''Perfrewrite: Memory and Time Complexity Analysis via Source Code Instrumentation'' * Flemming Nielson, Hanne Riis Nielson, and Helmut Seidl. ''Automatic Complexity Analysis'' -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9207#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler