Hacker News Reader

Comment by mjd | Hacker News Reader

This is my all-time favorite paper. It's so easy to read, and there's so much to think about, so much that still applies to everyday programming and language dedign.

Also there's Knuth admitting he avoids GO TO because he is afraid of being scolded by Edsger Dijkstra.

https://pic.plover.com/knuth-GOTO.pdf

View on HN

Reading Knuth is always a pleasure.

From the paper:

"It is clearly better to write programs in a language that reveals the control structure, even if we are intimately conscious of the hardware at each step; and therefore I will be discussing a structured assembly language called PL/MIX in the fifth volume of The art of computer programming"

Looking forward to that!

thank you, that's an incredible paper !

This statement in the introduction applies to so many things in CS:

  I have the
  uncomfortable feeling that others are making
  a religion out of it, as if the conceptual
  problems of programming could be solved by
  a single trick, by a simple form of coding
  discipline!

Like Brooks said: No Silver Bullets

Yeah, it's one of my favourites as well. And it weirds me out that the "premature optimization" bit is the most quoted piece of that paper — arguably, that's the least interesting part of it, compared to the musings on the language design and (semi)automatic transformation of algorithms!

I personally find that "break/continue" with (optionally labelled) loops cover about 95% of GOTO's use cases today (including "one-and-a-half" loops), although e.g. Rust and Zig, with their expression-oriented design (and support for sum types) offer an option to experiment with Zahn's event mechanism... but usually factoring an inner loop body into a separate function is a more clear-to-read approach (as for efficiency? Hopefully you have a decent inliner idk).

The only thing I truly miss, occasionally, is a way to concisely write an one-and-a-half range/FOR loop. Something like this:

    for key, value in enumerate(obj):
        emit(f'{key}={value}')
    between:
        emit(',')

When you have a generic "while True:" loop, conditional "break" works fine enough, but here? Ugh.

I might be missing something, but how would `goto` improve matters on that for-loop? It seems to me that the fundamental problem here is rather than there's no easy way to check whether this is the last iteration or not, but that is orthogonal to goto vs break.

Well, what you actually need is to make the first iteration special — generally, you can detect whether the iteration was last only after you've already finished it, but special-casing the very first iteration can be done. You put the "between" block at the beginning of the loop body, but start the loop by jumping over it into the middle. It works even better with "for" loops, they desugar into:

        i = START;
        if (i > END) goto _after_loop;
        goto _loop_body;
        while (1) {
            BETWEEN;
    _loop_body:
            BODY;
    _loop_test:  // "continue" would desugar into "goto _loop_test".
            i++;
            if (i > END) break;
        }
    _after_loop:
        ...

which, if you throw away the "BETWEEN" part, is a standard way to compile for-loops, with pre-test and loop inversion. But writing this by hand is just... no. I'd rather add either a boolean flag, or throw in "if i > 0: ..." or "if i != END: ..." guard. Sometimes those even get optimized away, see e.g. [0] — both of loops there desugar into pretty much this; but it's brittle, changing "if (i > START)" into "if (i != START)" in the second function duplicates the loop body, and if you make it sufficient larger than a single function call, the elided conditional branch rematerializes again.

But yes, the goto doesn't help much with

    it = iter(...)
    try: loop_var = next(it) except StopIteration: return
    body(loop_var)
    while True:
        try: loop_var = next(it) except StopIteration: break
        between(loop_var)
        body(loop_var)

loop where you must crank the iterator before every iteration; there you have to either duplicate some code, or count your iterations and check the current number.

[0] https://godbolt.org/z/Y4hv4oYdP

Sather had a very interesting approach to extensible looping constructs that allows for this kind of flexibility:

https://www.gnu.org/software/sather/docs-1.2/tutorial/iterat...

With this machinery, you could declare an iterator like so:

  first!(): BOOL is
    yield true;
    loop
      yield false;
    end;
  end;

And then the case that you describe would be something like:

  a: ARRAY{INT} := |1,2,3|;
  loop
     if not first! then
       emit(',');
     end;
     x := a.aelt!; 
     emit(x);
  end;

Which in practice amounts to the same thing as an explicit boolean flag - it's just hidden inside the internal state of first! that the loop has to maintain - but it sure is a lot clearer.

In Python and the likes, I suppose you could do the same with zip() if you aren't already using enumerate():

   def first_or_not():
       yield True
       while True: yield False:

   for value, is_first in zip(obj, first_or_not()):
        if not is_first:
           emit(',')
        emit(f'{key}={value}')

But this gets unnecessary verbose compared to Sather's implicit zip.

Regarding the ability to optimize away the version with an index check or equivalent, I was curious if C++ compilers these days are up to snuff if you choose to do something similar to Python. Turns out that Clang can indeed turn this:

  void emit_array(span<char*> xs) {
      for (auto [x, i] : views::zip(xs, views::iota(0))) {
          if (i) {
              emit(",");
          }
          emit(x);
      }
  }

into optimized assembly that doesn't perform the check inside the loop. But it does it by duplicating emit(x) so that it always runs once before the first iteration, and then checking for >1 item and only looping then. Ditto for this Rust code:

  fn emit_array(xs: &[String]) {
      for (i, x) in xs.into_iter().enumerate() {
          if i != 0 {
              emit(",");
          }
          emit(&x);
      }
  }

Unfortunately both g++ and MSVC struggle to optimize this equally well; both end up using a flag that is repeatedly checked in loop body.

(https://godbolt.org/z/bb79jW87Y)

Reply on news.ycombinator.com