<p>Implicit Complexity has taught us that (some) complexity classes can be classified by type systems, in the sense that there are type systems that only accept polynomial programs, for example. One more practical-minded offshoot of this research is <a href="http://raml.tcs.ifi.lmu.de/documentation/papers">RAML</a> (Resource Aware ML), a functional programming language with a type system that will give you precise information of the running times of its programs. It is more precise, in fact, than big-O complexity, are constant factors are also included, parametrized by a cost model for the base operations.</p>

<p>You may think that this is cheating: surely some algorithms have a complexity that is very hard to compute precisely, so how could this language easily determine the complexity of its programs? The trick is that there are many ways to express a given algorithm, some which the type-system will reject (it rejects some fine programs), and some, maybe, that it accept. So the user doesn't get the world for free: he or she doesn't have to compute cost estimations anymore, but need to figure how to express code in a way that is accepted by the system.</p>

<p>(It is always the same trick, as with programming languages with only terminating computations, or provable security properties, etc.)</p>

CC BY-SA 3.0
2013-12-27T17:00:17.807Z
Thanks, this is a very interesting answer. I will take a closer look at RAML.
manoj
CC BY-SA 3.0
2013-12-26T20:51:50.997Z
2013-12-26T23:27:09.763Z
2013-12-26T23:27:09.763Z
gasche
<p>The <a href="http://costa.ls.fi.upm.es/~costa/costa/costa.php">COSTA tool</a> developed by the <a href="http://costa.ls.fi.upm.es/web/">COSTA research group</a> does exactly what you want. Given a program (in Java bytecode format), the tool produces a cost equation based on a cost model provided by the programmer. The cost model can involve entities such as runtime, memory usage, or billable events (such as sending text messages). The runtime equation is then solved using a dedicated tool to produce a closed form, worst-case upper bound of the cost model.</p>

<p>Naturally, the tool does not work in all cases, either by failing to produce a runtime equation or by failing to find a closed form. This is not surprising.</p>

CC BY-SA 3.0
2013-12-27T20:40:27.547Z
2013-12-27T20:40:27.547Z
Dave Clarke
<p>I actually thought about the same question a while ago. Here is the train of thought I had:</p>

<p>As you said the halting problem is an issue. To avoid this we need a language which only allows programs that always halt. On the other hand our language needs to be expressive enough to deal with  most common problems(e.g. it should at least capture all of the complexity class EXP). </p>

<p>So, let's look at LOOP programs. A LOOP program always halts and its expressiveness is way beyond EXP - to get a better idea: you can simulate any TM for which the runtime function can be expressed as LOOP program. </p>

<p>Now, we can look at the nesting depth and the magnitude of the number of repetitions for every loop from a syntactic point of view and we have a starting point(dont know how far this takes us though). However, consider the following problem:</p>

<p>We want to implement the function $f(n)$:</p>

<p>$f(n) = y$ such that $y$ is the first prime number after $n$ with $y &gt; n$</p>

<p>Let's assume we have a function $p(n)$ which tells us whether a number $n$ is prime or not. Then to implement $f(n)$ most of us would probably write something like:</p>

<pre><code>y := n + 1
while not prime(y) 
    y++
return y
</code></pre>

<p>Now, how are we going to do this with only bounded loops? The problem now becomes to think about an upper bound for the range of numbers we have to search.</p>

<p>But that was what we wanted our compiler to tell us in some sense! So, we just shifted the problem of pondering about time complexiy to the programmer. By the way, the following sentence gives us the upper bound for our problem:
$$ \forall \text{ prime } p \phantom{a} \exists \text{ prime } p' : p &lt; p' \leq p! + 1 $$</p>

<p>My intuition here is that the only information a compiler can give you is from carefully analyzing the syntax which in the end is provided by the programmer. So, enabling the compiler to make any meaningful statement about the time complexity of a program means to force the programmer to incorporate this information into the program. </p>

<p>However, the last paragraph is subjective and there certainly might be other possible approaches which yield interesting results. I just wanted to give an idea of what not to expect when going down this road.</p>

CC BY-SA 3.0
2013-12-27T08:39:11.340Z
The nesting depth of loops is the main issue here, and the complexity ranges over the primitive recursive functions, see _The Complexity of loop programs_, Meyer & Ritchie, ACM '67 Conference, http://dx.doi.org/10.1145/800196.806014.
Sylvain
CC BY-SA 3.0
2013-12-27T17:01:02.683Z
Thanks. I think you make a fine point here. There is a problem if I'm going to run loops of the type

while(predicate = true)
   do something

because then I have to argue about the first time the predicate becomes false. To rephrase my question within the context you have set, I wonder if one can design a bunch of primitives, with a well-defined running time, which can be composed in simple ways to write interesting programs, and obtain running-time bounds for them. Perhaps RAML already does some of this, as pointed out by the first answer.
manoj
CC BY-SA 3.0
2013-12-28T17:00:40.340Z
To give more pointers of this sort, Cobham's _The intrinsic computational difficulty of functions_ is often cited as one of the earliest works on implicit complexity: it characterizes FP by means of recursion schemes.  You will find more recent work along this line by Bellatoni & Cook in _A new recursion-theoretic characterization of the polytime functions_, Computational Complexity 1992.  See also a survey by Hofmann in SIGACT News 31(1): 31--42, 2000: http://dx.doi.org/10.1145/346048.346051.
Sylvain
CC BY-SA 3.0
2013-12-29T08:57:47.217Z
Thanks Sylvain, I'm taking a look at the survey! I have been aware of this area of implicit complexity theory, but have never really bothered to study it, owing to a lack of appreciation of what is the basic question they are trying to answer. Now I have more motivation to understand these ideas!
manoj
CC BY-SA 3.0
2013-12-26T20:22:25.913Z
2013-12-26T20:22:25.913Z
John D.
<p>Has anyone thought about the possibility of a programming language, and a compiler, such that the compiler can automatically do worst-case asymptotic analysis? The use case I have in mind is a programming language where I write code, and compile. The compiler tells me that my code runs in O(n^2) (for example). It does this by doing what the smart people who do algorithmic analysis do, possibly counting loops and so on.</p>

<ul>
<li><p>Because of halting problem issues, and since one can have programs that work by dovetailing, for example Levin's algorithm for SAT that runs in polynomial time iff P=NP, I suspect that one may have to design the programming language to be sufficiently restrictive to allow something like this. Are there negative results, which rule out certain kinds of programming languages from having such compilers.</p></li>
<li><p>I would also be interested in systems that give not an exact asymptotic analysis, but an "interesting" upper bound. </p></li>
<li><p>I am specifically <em>NOT</em> interested in black box and statistical methods that sample from inputs of particular length, and find out how long the program takes. These methods are very interesting, but they are not what I'm looking for. I am interested in <em>exact</em> methods that may give <em>approximate</em> bounds. </p></li>
</ul>

<p>I would be very grateful if someone could point me to some references on work in this direction.</p>

CC BY-SA 3.0
2013-12-26T19:12:45.723Z
This is a possible duplicate of the following question: http://cstheory.stackexchange.com/questions/12585/to-what-extent-can-an-algorithm-predict-the-time-complexity-an-arbitrary-input-p
cody
CC BY-SA 3.0
2013-12-26T21:13:34.930Z
the obvious languages that can be ruled out are Turing complete as the undecidable halting problem is in any such language. then this leads to the question, what is a language more limited than Turing complete for which this is possible? but arguably, a language is not a "programming language" unless it is Turing complete. therefore, roughly, such a goal is basically theoretically impossible... there may be some mitigating ideas for limited complexity languages however...
vzn
CC BY-SA 3.0
2013-12-27T01:21:16.327Z
The answer is no, we cannot algorithmically distinguish even between the case that the program runs in time $n^2$ and $n^3$. See [Are runtime bounds in P decidable?](http://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable-answer-no/5006#5006) (assuming the programming language is expressive enough, i.e. we can simulate another given program for a given number of steps).
Kaveh
CC BY-SA 3.0
2013-12-27T01:24:56.050Z
I am virtually voting to close as duplicate for [Are runtime bounds in P decidable?](http://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable-answer-no/5006#5006)
Kaveh
CC BY-SA 3.0
2013-12-27T17:10:42.823Z
@cody, thanks for the link to the other question. There are some very nice answers there!
manoj
CC BY-SA 3.0
2013-12-27T17:14:06.087Z
@vzn "but arguably, a language is not a "programming language" unless it is Turing complete." As you point out, I would argue with that :-) I do not mean programming language in the sense of some acceptable enumeration of all the partial recursive functions, but in the more informal sense of a language you can write code in, and write a compiler for. In this weaker sense, finite state automata are also a programming language for me. Thanks for forcing me to clarify.
manoj
CC BY-SA 3.0
2013-12-27T17:19:49.847Z
@Kaveh I disagree that my question is a duplicate of "Are runtime bounds in P decidable?". I already knew how to prove that is impossible. Nevertheless, thank you for bringing this thread also to my attention!

However, it is possible that my question *is* a duplicate question, as pointed out by cody.
manoj
CC BY-SA 3.0
2013-12-27T21:00:07.747Z
also relevant as a "barrier", [rices theorem](http://en.wikipedia.org/wiki/Rice's_theorem)
vzn
CC BY-SA 3.0
2013-12-28T01:45:12.927Z
When I was young and naive I tried to write complexity analyzer using [gcov](http://linux.die.net/man/1/gcov). It gives you number of times each line was executed. :) Good question!
Pratik Deoghare
CC BY-SA 3.0
2014-01-25T21:39:04.593Z
You might be interested [in this question](http://cstheory.stackexchange.com/q/5120/1037) as well, for the case where you only want to write efficient programs.
Artem Kaznatcheev
<reference-request><pl.programming-languages><time-complexity><compilers><program-analysis>
Can one automate algorithmic analysis?
manoj
# Can one automate algorithmic analysis?

(Asked by: username_0 on 2013-12-26)

Has anyone thought about the possibility of a programming language, and a compiler, such that the compiler can automatically do worst-case asymptotic analysis? The use case I have in mind is a programming language where I write code, and compile. The compiler tells me that my code runs in O(n^2) (for example). It does this by doing what the smart people who do algorithmic analysis do, possibly counting loops and so on.

* Because of halting problem issues, and since one can have programs that work by dovetailing, for example Levin's algorithm for SAT that runs in polynomial time iff P=NP, I suspect that one may have to design the programming language to be sufficiently restrictive to allow something like this. Are there negative results, which rule out certain kinds of programming languages from having such compilers.
* I would also be interested in systems that give not an exact asymptotic analysis, but an "interesting" upper bound.
* I am specifically *NOT* interested in black box and statistical methods that sample from inputs of particular length, and find out how long the program takes. These methods are very interesting, but they are not what I'm looking for. I am interested in *exact* methods that may give *approximate* bounds.

I would be very grateful if someone could point me to some references on work in this direction.

**Tags:** reference-request, pl.programming-languages, time-complexity, compilers, program-analysis
> **Comments:**
> **username_1**: This is a possible duplicate of the following question: http://cstheory.stackexchange.com/questions/12585/to-what-extent-can-an-algorithm-predict-the-time-complexity-an-arbitrary-input-p  
> **username_2**: the obvious languages that can be ruled out are Turing complete as the undecidable halting problem is in any such language. then this leads to the question, what is a language more limited than Turing complete for which this is possible? but arguably, a language is not a "programming language" unless it is Turing complete. therefore, roughly, such a goal is basically theoretically impossible... there may be some mitigating ideas for limited complexity languages however...  
> **username_3**: The answer is no, we cannot algorithmically distinguish even between the case that the program runs in time $n^2$ and $n^3$. See [Are runtime bounds in P decidable?](http://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable-answer-no/5006#5006) (assuming the programming language is expressive enough, i.e. we can simulate another given program for a given number of steps).  
> **username_3**: I am virtually voting to close as duplicate for [Are runtime bounds in P decidable?](http://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable-answer-no/5006#5006)  
> **username_0**: @cody, thanks for the link to the other question. There are some very nice answers there!  
> **username_0**: @vzn "but arguably, a language is not a "programming language" unless it is Turing complete." As you point out, I would argue with that :-) I do not mean programming language in the sense of some acceptable enumeration of all the partial recursive functions, but in the more informal sense of a language you can write code in, and write a compiler for. In this weaker sense, finite state automata are also a programming language for me. Thanks for forcing me to clarify.  
> **username_0**: @Kaveh I disagree that my question is a duplicate of "Are runtime bounds in P decidable?". I already knew how to prove that is impossible. Nevertheless, thank you for bringing this thread also to my attention!  However, it is possible that my question *is* a duplicate question, as pointed out by cody.  
> **username_2**: also relevant as a "barrier", [rices theorem](http://en.wikipedia.org/wiki/Rice's_theorem)  
> **username_4**: When I was young and naive I tried to write complexity analyzer using [gcov](http://linux.die.net/man/1/gcov). It gives you number of times each line was executed. :) Good question!  
> **username_5**: You might be interested [in this question](http://cstheory.stackexchange.com/q/5120/1037) as well, for the case where you only want to write efficient programs.  

---

## 3 answers

### Answer by username_6 on 2013-12-26. Score: 8 | Accepted answer

Implicit Complexity has taught us that (some) complexity classes can be classified by type systems, in the sense that there are type systems that only accept polynomial programs, for example. One more practical-minded offshoot of this research is [RAML](http://raml.tcs.ifi.lmu.de/documentation/papers) (Resource Aware ML), a functional programming language with a type system that will give you precise information of the running times of its programs. It is more precise, in fact, than big-O complexity, are constant factors are also included, parametrized by a cost model for the base operations.

You may think that this is cheating: surely some algorithms have a complexity that is very hard to compute precisely, so how could this language easily determine the complexity of its programs? The trick is that there are many ways to express a given algorithm, some which the type-system will reject (it rejects some fine programs), and some, maybe, that it accept. So the user doesn't get the world for free: he or she doesn't have to compute cost estimations anymore, but need to figure how to express code in a way that is accepted by the system.

(It is always the same trick, as with programming languages with only terminating computations, or provable security properties, etc.)

> **Comments:**
> **username_0**: Thanks, this is a very interesting answer. I will take a closer look at RAML.  

---

### Answer by username_7 on 2013-12-27. Score: 7

The [COSTA tool](http://costa.ls.fi.upm.es/~costa/costa/costa.php) developed by the [COSTA research group](http://costa.ls.fi.upm.es/web/) does exactly what you want. Given a program (in Java bytecode format), the tool produces a cost equation based on a cost model provided by the programmer. The cost model can involve entities such as runtime, memory usage, or billable events (such as sending text messages). The runtime equation is then solved using a dedicated tool to produce a closed form, worst-case upper bound of the cost model.

Naturally, the tool does not work in all cases, either by failing to produce a runtime equation or by failing to find a closed form. This is not surprising.


---

### Answer by username_8 on 2013-12-26. Score: 2

I actually thought about the same question a while ago. Here is the train of thought I had:
As you said the halting problem is an issue. To avoid this we need a language which only allows programs that always halt. On the other hand our language needs to be expressive enough to deal with  most common problems(e.g. it should at least capture all of the complexity class EXP). 
So, let's look at LOOP programs. A LOOP program always halts and its expressiveness is way beyond EXP - to get a better idea: you can simulate any TM for which the runtime function can be expressed as LOOP program. 
Now, we can look at the nesting depth and the magnitude of the number of repetitions for every loop from a syntactic point of view and we have a starting point(dont know how far this takes us though). However, consider the following problem:
We want to implement the function $f(n)$:
$f(n) = y$ such that $y$ is the first prime number after $n$ with $y > n$
Let's assume we have a function $p(n)$ which tells us whether a number $n$ is prime or not. Then to implement $f(n)$ most of us would probably write something like:
y := n + 1
while not prime(y) 
    y++
return y

Now, how are we going to do this with only bounded loops? The problem now becomes to think about an upper bound for the range of numbers we have to search.
But that was what we wanted our compiler to tell us in some sense! So, we just shifted the problem of pondering about time complexiy to the programmer. By the way, the following sentence gives us the upper bound for our problem:
$$ \forall \text{ prime } p \phantom{a} \exists \text{ prime } p' : p < p' \leq p! + 1 $$
My intuition here is that the only information a compiler can give you is from carefully analyzing the syntax which in the end is provided by the programmer. So, enabling the compiler to make any meaningful statement about the time complexity of a program means to force the programmer to incorporate this information into the program. 
However, the last paragraph is subjective and there certainly might be other possible approaches which yield interesting results. I just wanted to give an idea of what not to expect when going down this road.

> **Comments:**
> **username_9**: The nesting depth of loops is the main issue here, and the complexity ranges over the primitive recursive functions, see _The Complexity of loop programs_, Meyer & Ritchie, ACM '67 Conference, http://dx.doi.org/10.1145/800196.806014.  
> **username_0**: Thanks. I think you make a fine point here. There is a problem if I'm going to run loops of the type  while(predicate = true)    do something  because then I have to argue about the first time the predicate becomes false. To rephrase my question within the context you have set, I wonder if one can design a bunch of primitives, with a well-defined running time, which can be composed in simple ways to write interesting programs, and obtain running-time bounds for them. Perhaps RAML already does some of this, as pointed out by the first answer.  
> **username_9**: To give more pointers of this sort, Cobham's _The intrinsic computational difficulty of functions_ is often cited as one of the earliest works on implicit complexity: it characterizes FP by means of recursion schemes.  You will find more recent work along this line by Bellatoni & Cook in _A new recursion-theoretic characterization of the polytime functions_, Computational Complexity 1992.  See also a survey by Hofmann in SIGACT News 31(1): 31--42, 2000: http://dx.doi.org/10.1145/346048.346051.  
> **username_0**: Thanks Sylvain, I'm taking a look at the survey! I have been aware of this area of implicit complexity theory, but have never really bothered to study it, owing to a lack of appreciation of what is the basic question they are trying to answer. Now I have more motivation to understand these ideas!  

---

