<p>There is a <a href="https://langdev.stackexchange.com/q/2015/">nice answer</a> here providing an exposition of Felleisen's definition of expressiveness.  But there is a missing piece for me.</p>
<p>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).</p>
<p>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?</p>

<untagged>
Is there a way to define expressiveness that includes a notion of computational complexity?
CC BY-SA 4.0
2023-10-02T07:32:34.847Z
Or we just use a real machine and a stopwatch :)
feldentm
CC BY-SA 4.0
2023-10-02T15:43:07.457Z
This question seems like it would be more appropriate for [cs.se].
Barmar
CC BY-SA 4.0
2023-10-02T17:44:19.287Z
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.
kaya3
CC BY-SA 4.0
2023-10-02T21:49:11.920Z
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.
supercat
CC BY-SA 4.0
2023-10-11T20:23:17.877Z
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](https://cstheory.stackexchange.com/questions/21821/how-can-i-prove-formally-semantic-equivalence-of-programming-languages) as a starting point?
Martin Berger
<p>In effect, you propose to order languages by efficiency of their generated code assuming that all are otherwise turing complete. <a href="https://benchmarksgame-team.pages.debian.net/benchmarksgame/box-plot-summary-charts.html" rel="nofollow noreferrer">Here</a> is an example of such a comparison. I'd expect that this has more impact in practice than an artificial scientific approach.</p>
<p>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.</p>
<p>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.</p>
<p>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.</p>

CC BY-SA 4.0
2023-10-02T07:31:52.233Z
2023-10-02T07:31:52.233Z
feldentm
CC BY-SA 4.0
2023-10-02T17:41:39.840Z
This isn't really about the language's expressiveness, though, and that's what the question is about.
kaya3
CC BY-SA 4.0
2023-10-03T13:36:58.897Z
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.
feldentm
<p>I think there are modern efforts to understand semantics in a fine-grained way that includes notions of computational complexity.</p>
<p>One might want to glance at some of Bob Harper's recent work, e.g. this talk: <a href="https://www.cs.cmu.edu/%7Erwh/talks/calco-mfps-2023.pdf" rel="nofollow noreferrer">Integrating Cost and Behavior in Type Theory</a>.</p>

CC BY-SA 4.0
2023-10-10T21:45:15.920Z
2023-10-10T21:45:15.920Z
cody
# Is there a way to define expressiveness that includes a notion of computational complexity?
Posted by: username_0 on 2023-10-02
There is a [nice answer](https://langdev.stackexchange.com/q/2015/) 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?
**Tags:** untagged
> **Comments:**
> **username_1**: Or we just use a real machine and a stopwatch :)  
> **username_2**: This question seems like it would be more appropriate for [cs.se].  
> **username_3**: 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.  
> **username_4**: 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.  
> **username_5**: 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](https://cstheory.stackexchange.com/questions/21821/how-can-i-prove-formally-semantic-equivalence-of-programming-languages) as a starting point?  
---
## 2 answers
### Answer by username_6 on 2023-10-10. Score: 3
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](https://www.cs.cmu.edu/%7Erwh/talks/calco-mfps-2023.pdf).
---
### Answer by username_1 on 2023-10-02. Score: 0
In effect, you propose to order languages by efficiency of their generated code assuming that all are otherwise turing complete. [Here](https://benchmarksgame-team.pages.debian.net/benchmarksgame/box-plot-summary-charts.html) 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.
> **Comments:**
> **username_3** (2023-10-02): This isn't really about the language's expressiveness, though, and that's what the question is about.  
> **username_1** (2023-10-03): 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.  
---
