I haven't done this for a while, but once upon a graduate program I wrote a compiler from a made-up-language (MUP) to C. MUP had some strange control structures, and if C did not have "goto", it would have been a lot more difficult to implement those structures. Since then, I have always thought languages should have a "goto" statement that human-written code is not allowed to use. :)
(I don't recall whether the borrow checker actually depends on the control flow being reducible, but some of the possible future improvements we've talked about with "non-lexical lifetimes" definitely do. There are also nasty interactions between RAII and irreducible control flow…)
The benefits are enough that data structure and algorithm designs in the JVM compiler world often take advantage of assuming reducible control flow even though Java bytecode can express irreducible CFGs. Instead, such programs are left to the interpreter.
Most problems on reducible graphs are not easier than for general graphs, because you can always compute a loop forest (for generalized loops, not natural loops with a single entry point) and just consider a derived acyclic graph.
> you can always compute a loop forest
It's easier to not have to.
https://pp.info.uni-karlsruhe.de/uploads/publikationen/braun...
In the case of irreducible control-flow it may produce redundant cyclic phis, but those can be eliminated with a pretty simple post-pass.
https://github.com/rust-lang/rfcs/pull/396
It does have the effect of picking a single dominating entry point for a loop with multiple entry points, but if you want a single-entry region that's necessarily true. Multiple-entry regions are probably possible, but they could be counterintuitive and produce even stranger error messages than the current region system.
The borrow checker is based on dataflow analyses that should work on arbitrary CFGs, assuming an appropriately generalized notion of region.
True, but only in node-splitting approaches. If you use a label threading variable (as emscripten's relooper does), there is a guaranteed reasonable limit on code size increase (at the cost of performance).
"Just recently, however, Hoare has shown that there is, in fact, a rather simple way to give an axiomatic definition of go to statements; indeed, he wishes quite frankly that it hadn't been quite so simple....
"Informally, α(L) represents the desired state of affairs at label L; this definition says essentially that a program is correct if α(L) holds at L and before all "go to L" statements, and that control never "falls through" a go to statement to the following text. Stating the assertions α(L) is analogous to formulating loop invariants. Thus, it is not difficult to deal formally with tortuous program structure if it turns out to be necessary; all we need to know is the "meaning" of each label."
I think goto should be in almost every language. It's one of the most primitive instructions, why shouldn't it be available when needed? Yes, it can be misused, just like any other feature in the language, but it can also be used to great benefit. State machines, for example, can make good use of gotos.
Hell, look at any unix library your machine uses every day. The ones you don't even think about. Start with libncurses: I promise there's a few gotos where needed.
$ find ~/ncurses-5.9 -name '*.c' -print0 | xargs -0 grep goto | wc -l
70
Oh, here's tmux, if you're interested (one of the most beautifully written C programs): https://github.com/tmux/tmux/search?utf8=%E2%9C%93&q=goto
I see what you're saying, though I don't find this a compelling argument. By this logic, why not allow direct register access in all languages?
Just because something is a primitive operation doesn't mean you want to include it, especially not if it's more difficult to enforce guarantees your language would like to make about valid programs.
What if I just avoid contributing to the ncurses codebase? I've used plenty of useful tools with absolutely horrific codebases that I'd never want to touch in a million years. Not sure if ncurses is one of them.
The whole "it gets used, ergo it must be a good idea" argument doesn't hold much traction with me - even if I think using it when in C, to enforce single exit style, to work around the lack of RAII constructs, goto is the lesser evil.
I started with GOTO in BASIC. I used it a lot. It structured my initial reasoning about control flow. Despite this, in the past few years, I've used a naked goto maybe once or twice, and in all cases later rewrote it without the goto, which in my opinion increased it's readability. (I generally always have the option of C++ over C, and choose it, rendering single exit style 'useless'.)
> Oh, here's tmux, if you're interested (one of the most beautifully written C programs): https://github.com/tmux/tmux/search?utf8=%E2%9C%93&q=goto
Most of those are single exit style gotos. Those that aren't, do cause some concern, despite being "one of the most beautifully written C programs", even to their original author from the looks of it:
if (errno == ENOMEM)
goto retry; /* possible infinite loop? */
I've encountered worse edge cases before, however, and I'd really prefer my programs crash properly, instead of hanging when they do.
> State machines, for example, can make good use of gotos.
The performance complaints about an additional branch misprediction when using the "for(;;) switch(...)" style without gotos, is one of the few arguments that moves me, if only slightly. That seems like a case your standard optimizing compiler really should be able to handle, however. I'll assume they don't, as I'm too lazy to test if this is merely hearsay...
That said, I'll even use "goto case" in C# on occasion where I'd use case fallthrough in C++, if I'm feeling particularly lazy and don't want to turn things into proper method calls that can simply call each other just yet. I usually clean it up before I start to confuse myself.
It's not something I'd miss if it were gone, however. It's something I use only rarely, and only as a crutch to stave off cleanup. Not exactly a ringing endorsement.
EDIT: Code formatting, proper insertion of subject...
Anyways, exceptions are sort of gotos or at least they can behave that way.
It does, yes, although many Lisps got a pretty limited backend for this sort of things. My preferred metaprogramming environment must have a fallthrough mode for allowing generating low-level code where Lisp semantics is not sufficient. Rust seems like a very good target platform in this sense, so the lack of goto really hurts.
> It doesn't have goto.
Of course they do (tagbody in Common Lisp, for example). And when they don't, it's often relatively easy to add one.
I was wrong, however it is much more limited than the goto everywhere from C, as where the labels are located is clearly defined in the tagbody and not in every possible statement.
I don't plan to stop using ncurses in particular, but one of the reasons I am supportive of Rust is that I would like to stop using all C software sometime in my lifetime.
Note that a union of two pointer-containing structs is safe as long as the pointers line up, having the same type and offset in each struct.
https://github.com/rust-lang/rfcs/pull/724
If you really need them, you can implement them in a library by declaring a suitably sized byte array and having methods that return casted pointers to it. This would be illegal in C due to strict aliasing, but IIRC Rust does not have a strict aliasing rule (because almost all pointers being the equivalent of 'restrict' drastically reduces the benefit).
There are issues with size_of not being a constant expression and such (at least in stable), but those are definitely going to be fixed.
The main advantage of using higher-level languages is that you can talk about manipulations of data. Goto doesn't manipulate data, it manipulates the machine. And if you want to _really_ manipulate the machine, you're going to want more than just goto.
>Raise your hand if you plan to stop using ncurses because of how opposed to how "harmful" goto statements are.
Goto statements are not harmful to computers or to code. Ncurses isn't what is harmed by goto, nor does "using ncurses" imply any interaction with goto at all.
Muhammad Ali was a good boxer. He was Muslim. Am I to conclude that one must be Muslim to be a good boxer, now?
Yes, ncurses is a good program. Yes it uses goto. But that doesn't imply that goto is necessary to it being a good program. Or that it is even a mildy efficient way of doing well. (Especially not when there is a whole universe of alternatives.)
If you're going to defend goto (and there are reasons to do this) you should probably do so without employing such blatant logical fallacies. It's irresponsible and detracts from your point.
In C it would still have use in the implementation of orderly error handling -- the pattern where you hand-implement exception handling in C by putting an on_error: label at the end of the function that is goto'd on error. The addition of some orderly construct for this in C would eliminate that case, leaving no real role for goto there either.
In 20 years of using C/C++, I've found one use for "goto" that's hard to substitute: simulating coroutines that yield to an outer context. (Similar to C# yield return).
A "break label" gets you out of a loop. I needed to use "goto" to jump back into the middle of a loop to resume where the "coroutine" previously left off. The keywords "break/setjmp/longjmp" wouldn't have been substitutes for this particular use case.
Here's the base code without gotos:
typedef enum { ADD, MUL, ..., END } opcode;
void run() {
opcode ins;
while (1) {
ins = fetch_next_inst();
switch (ins) {
case ADD:
perform_addition();
break;
case MUL:
perform_multiplication();
break;
...
case END:
wrap_up();
return;
}
}
}
typedef enum { ADD, MUL, ..., END } opcode;
void run() {
opcode ins;
start:
ins = fetch_next_inst();
switch (ins) {
case ADD:
perform_addition();
goto start;
case MUL:
perform_multiplication();
goto start;
...
case END:
wrap_up();
return;
}
}
typedef enum { ADD, MUL, ..., END } opcode;
#define NEXT() \
do { \
ins = fetch_next_inst(); \
goto *jump_table[ins]; \
} while(0)
void run() {
opcode ins;
static void *jump_table[] = { &&add_l, &&mul_l, ..., &&end_l };
NEXT();
add_l:
perform_addition();
NEXT();
mul_l:
perform_multiplication();
NEXT();
...
end_l:
wrap_up();
return;
}
Granted, this is not the kind of code you write everyday. But sometimes speed matters, and good luck writing this without gotos.
But assuming a sufficiently smart compiler when you depend on your code being fast tends to cause issues. Especially if you expect it to run on a bunch of platforms with compilers of varying qualities. Last time I saw code last this, we certainly couldn't rely on compilers being particularly smart, and we did care about speed.
Do you have a pointer to the relevant part of OCaml's source? The whole thing is probably worth a read, but don't think I can set aside enough time for that soon, and it could take me a while to find the right part.
See the "Next" macro definition.
To be fair, I've seen code like this exactly once.
static void* address = &address;
This is helpful for things that take void* context pointers that you want to match with logical equality.
In my practice these exceptions are ubiquitous. Multiple tiny interpreted DSLs (which cannot be compiled more efficiently for the latency reasons), efficient protocols, all that stuff. System programming, in other words, and it's exactly the stuff Rust was supposed to be designed for.
> But it's definitely not the rule and the speed difference between the one and the other is so small
2-4 times difference is not "small" in system-level programming.
> Even the inner loop of an interpreter usually calls routines
These are too high level interpreters for the too dynamic languages, they're beyond any hope in terms of performance, by design. I'm talking about some simpler and better designed things (like OCaml, for example).
In your example:
void (*[10])() function_table = {
&perform_addition,
&perform_multiplication,
...
}
while(1) {
ins = fetch_next_inst();
*(function_table[ins])();
}
If you were to inline all of the perform functions in the GOTO version vs putting a macro at the end of each function, you're right that there's some function overhead, but I think it's as small as a single instruction to put the return address on the stack. Maybe that would be optimized away, maybe not.
To your point: My argument isn't that you can't do the GOTO version. With optimizations, it's essentially identical. My point is, that is a lot more hard-to-grok code to maintain for something that can be achieved in a simpler way.
Sometimes this can be optimized away, but not always.
Over time it tends to evolve into ever messier and harder to understand versions of the initial run after which a future maintainer will end up losing sleep and or hair chasing some production bug.
Consider this (slower!) much clearer alternative, and consider too that if you need to eliminate one goto for speed reasons that you're most likely doing something wrong:
typedef enum { ADD, MUL, ..., END } opcode;
int process_instruction(opcode ins) {
switch (ins) {
case ADD:
perform_addition();
break;
case MUL:
perform_multiplication();
break;
...
case END:
return FALSE;
}
return TRUE;
}
void run() {
do {
} while (process_instruction(fetch_next_instruction());
wrap_up();
}
It would be interesting to see what the actual difference is in speed when comparing those two versions, I suspect that the contents of 'perform_addition' and 'perform_multiplication' are going to be the key here, not whether or not the loop uses a short-cut or an instruction (or two) less. Oh, and you could have eliminated that 'ins' variable.
In summary, the assembly of the goto version is much shorter and there's a 10% speedup over SPEC JVM98. The optimization works out because: a) instruction bodies are often short; b) instruction dispatch is the hottest code path of any interpreter; c) it's orthogonal to all or almost all other optimizations.
Exactly. And stop-gap measures are fine if and when they're followed up by a proper solution. Unfortunately stop-gap measures tend to be a lot more permanent than originally intended in practice.
I like the way this is handled in Go with the defer keyword: https://blog.golang.org/defer-panic-and-recover
This construct gives you most of the power of C++ RAII without the overhead. Except that you can't use it to cleanup resources after exiting an anonymous block—it strictly defers to function exit.
In all other cases (which is almost all usages), it is semantically equivalent to RAII, so the language doesn't force any runtime overhead. The only difference is that the compiler is less mature than an average C++ compiler, but this is an implementation problem, not a design problem.
RAII has no overhead because it is a pattern designed within the context of a zero-overhead language. defer allows you to implement a superset of cases that RAII handles, including those with runtime overhead.
I hadn't considered the type of overhead you're talking about, which is admittedly more important for the kind of software that tends to get written in C.
But it leaves out the most useful part: in C++ releasing the resources is completely implicit:
{
std::ifstream in(fn);
// Do something with 'in'
} // Released
Sure, it's an improvement over languages where you have to cover every possible scope exit, but it definitely doesn't give you 'most of the power' of C++ RAII.
static int foo_impl(int arg, int **resource1, int **resource2) {
*resource1 = (int *)malloc(sizeof(**resource1));
if (*resource1 == NULL) return EXIT_FAILURE;
/* Do something with resource1 (omitted)... */
*resource2 = (int *)malloc(sizeof(**resource2));
if (*resource2 == NULL) return EXIT_FAILURE;
/* Do something with resource1 and resource2 (e.g.,
stick them in a global hash table as key/value pairs,
or whatever, omitted)... */
return EXIT_SUCCESS;
}
int foo(int arg) {
int *resource1;
int *resource2;
int ret;
resource1 = resource2 = NULL;
ret = foo_impl(arg, &resource1, &resource2);
if (ret != EXIT_SUCCESS) {
free(resource2);
free(resource1);
}
return ret;
}
A way to fix it would be to return different failures for every allocation and to use a switch without a break to clean up, something like:
switch (ret) {
case EXIT_SUCCESS:
free(resource2);
case EXIT_FAILURE2:
free(resource1);
case EXIT_FAILURE1:
break;
}
EDIT2: fixed a bug in the fix. C is hard, let's go shopping.
EDIT3: the explanation for the bug was also wrong. It is not a memory leak for but freeing a null pointer. Fixed too.
Although the concern of a memory leak is valid. I would have expected the resources to be free'd regardless of the result.
Seems to be a common misconception [1], thanks for pointing out, that makes the GGP code correct in all counts and my switch redundant.
Two things about goto and jmp instructions. Most people have no idea how badly they were abused back in old days. For instance to jump into the middle of a subroutine. Yay just saved 9!!! words of core memory!!! And most people forget that old computer scientists were obsessed with creating grammars that you could write formal proofs for.
It's an interesting idea.
The problem I see is that users can get around it by wrapping goto in the simplest possible macro. Then the idea has backfired: we now have goto under as many names as there are goto-using programmers. :)
All its use cases are better served by other language constructs.
Then again, C is a portable macro assembler.