# Is there a way to define expressiveness that includes a notion of computational complexity?

There is a nice answer here providing an exposition of Felleisen's definition of expressiveness. But there is a missing piece for me.

It feels like adding tail calls to a language that lacks any mechanism for unstructured control flow increases the expressiveness of that language, because it is non-local and it allows me to usefully express and compose algorithms in ways I couldn't before. But semantically speaking, a tail call is equivalent to a regular call, so in some sense it should always behave the same. So Felleisen's definition, applied naively, would seem to consider it an inexpressive addition (or, rather, a complete non-addition).

We can imagine specifying an abstract machine with bounded space, where space exhaustion is an error. In that case, adding tail calls will take some programs that used to error due to space exhaustion and make them instead give meaningful results, increasing expressiveness. But this is an unsatisfying way to cast the problem, because what I'm really trying to get at is asymptotic space usage, which this doesn't seem to capture. Is there an alternate approach?

• Or we just use a real machine and a stopwatch :) Commented Oct 2, 2023 at 7:32
• This question seems like it would be more appropriate for Computer Science. Commented Oct 2, 2023 at 15:43
• I think there is a foundational problem with this question ─ a language specification rarely imposes any bounds on the performance of implemented programs, let alone lower bounds (i.e. "this operation must be at least this slow"). Even if your language doesn't specify that tail calls must be optimised, does it make sense to say that the algorithm which takes advantage of tail calls can't be expressed in that language? After all, that algorithm can be written in that language, and it will have the advertised complexity if the implementation provides for it. Commented Oct 2, 2023 at 17:44
• A semantic difference between a tail call and a typical function call is that nesting limitations which would generally apply to ordinary function calls should never apply to tail calls. Tail-call nesting should be, by specification, unbounded. Commented Oct 2, 2023 at 21:49
• The critical phrase is "semantically speaking" ... why not make run-time (for example) an observable of your programs? Anyway, Felleisen's work was pioneering, but it is now well-understood that it is not expressive enough to classify languages by their expressivity. Can I recommend my reply here as a starting point? Commented Oct 11, 2023 at 20:23

I think there are modern efforts to understand semantics in a fine-grained way that includes notions of computational complexity.

One might want to glance at some of Bob Harper's recent work, e.g. this talk: Integrating Cost and Behavior in Type Theory.

In effect, you propose to order languages by efficiency of their generated code assuming that all are otherwise turing complete. Here is an example of such a comparison. I'd expect that this has more impact in practice than an artificial scientific approach.

One downside of this approach is that it mixes judgement of compiler implementation with language design. Most of the performance will come from good optimizations that may exist because the language is wide-spread and not because it is particularly good for implementing such optimizations.

Another downside is that all languages that can express the assembly of the best solution are somehow equally good. So, there should be a rule in the comparison that excludes such tricks to get the desired result.

The upside is that it gives you an estimate on the hardware cost part of your product's TCO. This is a lot more valuable than any artificial comparison.

• This isn't really about the language's expressiveness, though, and that's what the question is about. Commented Oct 2, 2023 at 17:41
• I know, but still think that this is the answer to the question. I think expressiveness makes little sense in general, but that's another discussion. Commented Oct 3, 2023 at 13:36