It doesn’t necessarily change the semantics, but it does change what kind of programs are sure to crash your machine, and what kind are going to run fast, which is also an important property of programming languages.
Yeah, this is exactly what I meant. The semantics of the language are the same regardless (i.e. the meanings of programs doesn’t change), but in practice it makes a huge difference.
You'd have a point if they were talking about implementation semantics, but they're talking about language semantics. A Scheme program can assume TCE, a CL program can not, an SBCL program can.
SBCL will only perform TCO at specific optimization levels, so you can't even rely on it in SBCL.
The former will run on other implementations.
Other language standards keep this from affecting the semantics of the language by simply leaving it out of the semantics of the language. When the expected behavior is undefined, the implementors can do anything they want without, strictly speaking, affecting the semantics of the language.
In python, it's mostly visible through exception objects.
In Tcl and R, it's in common use because it is standard practice to do things in your caller's scope instead of your own.
In C++ (and any language with destructors), many routines are invisibly not TCEable because the language semantics require the destructor to run after the tail call returns - which means that a change to a different part of the code determines if a specific function is TCEable or not.
So, despite your claim being technically true, it is in practice often informally specified by the language or standard library.
Inlining doesn't change what a call stack looks like - the call stack frames are still there, yes possibly just a metadata annotations on real call stack frames and recovered when needed.
With tail calls, the call stack frames are completely gone, and cannot be recovered.
Try this thought experiment - can you implement tail calls in Java and meet the same language specification? I think you cannot. Therefore it is not an optimisation. If you can please email me how and I will implement it and you can publish the paper and get the glory!
Is this because Java exposes stack traces in a way most languages don't?
But I don't think it's unusual for a language to expose call stacks? Ruby, Python, C#, etc all do it.
(I haven’t looked, but I would expect modern Java implementations already make up quite a bit of the stack trace only when it is needed, for example when inlining calls)
And, traditionally, it _is_ unusual to expose call stacks to calling programs for Algol-style languages (implementations typically dumped a call stack and might add a way for a program to walk its stack, but that would be implementation-dependent)
Without exceptions or a repl, where would you use them, other than in a crash dump?
Yes they do. But they can't make up the stack for tail calls because the information is simply gone. If you've got a set of mutually functions that are tail calling, and you suddenly need to generate a stack trace, how do you know how many times the functions have been called and which order they were called? That info was never recorded - it's just done. Inlining is static info and much simpler - it is recorded and isn't gone.
But I assume that kind of information is probably not enough for Java.
Now, whether that’s worth the implementation effort, of course, would depend on whether the construct is used a lot, and that’s a catch-22.
For functions jumping into other functions, I guess that, when the program counter says you’re in baz while the first stack frame says foo got called, you could infer that foo called bar and bar called baz from metadata that the compiler would have to add.
Now, if foo can get into baz along multiple routes, you would have to record something, but I would guess there are plenty of those simpler cases. For those, the main challenge would be to infer recursion count for a recursive call.
[0] https://www.hanselman.com/blog/release-is-not-debug-64bit-op... , ctrl-f for this stack trace is showing the runtime reality.
You can absolutely record these things under TCO, in much the same way you'd record virtual stackframes when inlining.
If you think it is, then you should go ahead and publish it because you've discovered a new language implementation technique.
You seem to have a very Java-centered view of the universe, because it is absolutely not true in most languages that inlined calls preserve call stacks. Call stacks are debug information, and there’s absolutely no requirement for compilers to preserve debug information while doing optimization. Requiring that would be lunacy, and it would prohibit a huge number of optimizations (or require costly bookkeeping).
I don’t know what the situation is in Java-land, but if Java preserves inlining information in call stacks using bookkeeping, then good for it, I guess. It can’t come for free, so you’re taking a performance hit for that pleasure. It’s certainly not something that is common, or commonly understood as a requirement for optimization.
Add another record where? On some kind of stack of records from calls? That will grow linearly with the number of calls? So that's a call-stack is it? The whole point of TCO was to eliminate the stack and you've re-invented it there! If you have an infinite tail-call (like a web server accepting requests in a loop) you'll have an infinitely long list of records with your idea.
> It’s certainly not something that is common, or commonly understood as a requirement for optimization.
In many languages (Python, Ruby, Java, etc) they are not debug information - they're part of the program semantics and (from experience!) if you change them you'll break programs.
Is the debugger part of the language specification? No.
When I say 'can you observe the difference as a programmer' you can mentally expand that to 'can you observe the difference as a programmer who is working off a copy of the language specification'. Otherwise someone armed with a debugger can look at the machine code and then we might as well say all implementation decisions are observable by the user, and then I think we're being a bit silly.
> you won't be able to access the first variable
I'm not familiar with this part of JavaScript off the top of my head sorry - do you mean using a debugger again here?
Neither is "the stack trace".
(I've worked professionally with multiple language specifications and implementing them.)
Of course, the optimizer is still constrained by the spec in the obvious ways: copy operations can only be elided when the compiler can show that they are redundant (in some precise sense that the spec presumably lays out).
It follows of course that this 'optimisation' may impact observable behaviour. This makes some sense as C++ code shouldn't be doing 'real work' in copy-constructors, but it's still a rather ugly concession to pragmatism. edit Which, come to think it, describes the whole C++ language ;-P
[0] https://stackoverflow.com/a/12953129/
[1] https://en.wikipedia.org/wiki/Copy_elision#Return_value_opti...
For example, they don't mention stack overflows at all. But since standards compliant compilers spit out code that suffers from them, I assume they are allowed.
So I assume you could make a standard compliant compiler that doesn't nothing but immediately overflows the stack.
Interesting thought. I imagine just about every language spec (with the possible exception of assembly languages) states something like If memory is exhausted, a handler is executed or If memory is exhausted, the behaviour is undefined, and it's always going to be up to the compiler/interpreter to make reasonable use of the available memory on the specific target platform.
Would a C compiler be non-compliant if it generated code that used 100x the memory that would be used by code generated by typical C compiler? How about 1,000,000,000x so that its generated programs always failed immediately?
Java is an interesting case for this, as it famously doesn't require that a garbage collector needs to be included at all (unlike .Net which does). In Java, not only are you permitted to have a conservative GC, you're permitted to have no GC whatsoever (something OpenJDK now offers [0]). Apparently [1] Java requires that the collector (if it exists) will run before the JVM throws OutOfMemoryError.
I imagine the formal methods folks must have done some thinking on this topic, as their whole field is about doing better than just go ahead and test it out. Could a standards-compliant C compiler used in a safety-critical domain generate code that, only very occasionally, uses a billion times the memory it typically uses?
Somewhat related: one of the motivations behind the Zig language seems to have been a frustration with clumsy handling of memory-exhaustion. [2][3]
[0] https://openjdk.java.net/jeps/318
[1] https://www.kdgregory.com/index.php?page=java.outOfMemory
I would have expected some words to those effects, but extensive browsing and grepping in the C++ spec did not reveal such language. (They do not mention the call stack at all, which is a fair enough decision.)
I was first looking into this, because I had hoped the standard would specify a way to check for whether the next call would blow up the stack before you actually engaged in the call.
> Would a C compiler be non-compliant if it generated code that used 100x the memory that would be used by code generated by typical C compiler? How about 1,000,000,000x so that its generated programs always failed immediately?
You could ask the same for speed of execution. I think it would be standards compliant, but not very useful. Standard compliance ain't the only thing people look for in a compiler.
In practice, you could make a C++ compiler that does the standard compliant thing to virtually all of people's programs, by just emitting the nethack executable regardless of input. After all, virtually all real world C++ programs have undefined behaviour somewhere, and undefined behaviour is allowed to 'travel backwards in time'. (Ie undefined behaviour anywhere makes the whole execution undefined, not just after it is encountered.)
Hey, you could even just start nethack instead of producing any files with your compiler at all. Enough undefined behaviour goes all the way to compile time, like eg not closing your quotes, I think.
> I imagine the formal methods folks must have done some thinking on this topic, as their whole field is about doing better than just go ahead and test it out. Could a standards-compliant C compiler used in a safety-critical domain generate code that, only very occasionally, uses a billion times the memory it typically uses?
I think for safety-critical code, you solve this conundrum by relying on extra guarantees that your compiler implementation makes, not just on the standard.
As for the standards, the drafts are public and usually 98% like the final ones.
The missing 2% are clarifications only relevant for compiler vendors and language lawyers, whose employers can afford sponsoring ISO work anyway.
Yes, but other instances of copy-elision are still at the discretion of the compiler, right?
So even if move semantics aren't supported for the specific type, the target type gets built inplace.
The most fundamental is whether we can write a program which halts in one case and doesn't in the other.
An alternative is whether we can write an if/then/else branch to distinguish between the two cases. Note that this is less general than the above, since we can always use an if/then/else to implement a halt/no-halt program, but we can't always go the other way (due to the Halting Problem). This definition is useful, since if/then/else can cause arbitrarily-large changes to a program's behaviour; whereas we can't "use" a difference which affect halting.
Another definition, which is more subjective, is whether we can do the above "reliably". For example, any optimisation that makes a program faster could be observed by a language which allows access to a clock. Whilst hackers and debuggers might find these useful, it's not the sort of thing that a "reasonable" programmer would do (i.e. code which relies on this sort of thing shouldn't pass code review). I'd probably count inspecting stack traces, or running a debugger on ourselves, in this category.
The messy subjectivness of the latter is why I like to limit the capabilities of what I'm developing with: I don't have to care about timing altering the behaviour of a program which can't access a clock.
And you can tell if you blew up the stack by setting up an exception handler (or lisp condition or whatever equivalent).
That only works if there's some way to tell whether the stack blew up (as you say: catching exceptions, lisp conditions, or whatever equivalent). I'd put those language features in the 'messy' category: useful on occasion; not used by most code; makes all code harder to reason about (hence the subjective "reasonably-unobservable" category above)
> I'd probably count inspecting stack traces, or running a debugger on ourselves, in this category.
I would put such things in the "unreliable" category, since it's the sort of thing that may vary between compilers (including future versions), and may depend on internal details of dependencies which are subject to change.
I certainly wouldn't let them through code review; it can be hard trying to understand 'foo(bar)' in terms of 'the function "foo" applied to the input "bar"', I'd rather avoid the extra complications of having to think about 'pushing a fresh stack frame, clearing registers A, setting the instruction pointer to B, adding C instructions to the ALU's adder pipeline, forcing a flush of D cache lines, ...'
I wouldn't consider the memory layout of something like a stack to be part of the semantics of the language, unless that language actually includes features to directly refer to the stack (get its contents or size, etc).
But the 1s and 0s are not specified by the language (in almost all cases.) They're out of scope.
The line is: what has been formally specified by the language spec as being part of the language.