8
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ This is a possible duplicate of the following question: cstheory.stackexchange.com/questions/12585/… $\endgroup$ – cody Dec 26 '13 at 19:12
  • $\begingroup$ 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... $\endgroup$ – vzn Dec 26 '13 at 21:13
  • $\begingroup$ 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? (assuming the programming language is expressive enough, i.e. we can simulate another given program for a given number of steps). $\endgroup$ – Kaveh Dec 27 '13 at 1:21
  • 3
    $\begingroup$ @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. $\endgroup$ – manoj Dec 27 '13 at 17:19
  • 2
    $\begingroup$ When I was young and naive I tried to write complexity analyzer using gcov. It gives you number of times each line was executed. :) Good question! $\endgroup$ – Pratik Deoghare Dec 28 '13 at 1:45
8
$\begingroup$

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 (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.)

$\endgroup$
  • $\begingroup$ Thanks, this is a very interesting answer. I will take a closer look at RAML. $\endgroup$ – manoj Dec 27 '13 at 17:00
7
$\begingroup$

The COSTA tool developed by the COSTA research group 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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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, dx.doi.org/10.1145/800196.806014. $\endgroup$ – Sylvain Dec 27 '13 at 8:39
  • $\begingroup$ 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. $\endgroup$ – manoj Dec 27 '13 at 17:01
  • 1
    $\begingroup$ 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: dx.doi.org/10.1145/346048.346051. $\endgroup$ – Sylvain Dec 28 '13 at 17:00
  • $\begingroup$ 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! $\endgroup$ – manoj Dec 29 '13 at 8:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.