Sometimes, I dream that I am compiling something and the compiler
tells me: “be careful, function F has complexity >= O(n^2)”.
Let’s assume that we have a static analyzer for OCaml code.
Would this analyzis possible?
Sometimes, I dream that I am compiling something and the compiler
tells me: “be careful, function F has complexity >= O(n^2)”.
Let’s assume that we have a static analyzer for OCaml code.
Would this analyzis possible?
You should have a look at RAML (http://raml.co). It is I believe the state of the art for automatic analysis of the complexity of OCaml-like programs. You can play with it online. Of course, because the tool is fully automatic, it cannot infer bounds for every programs; AFAIR it is currently limited to (multivariate) polynomial bounds.