Hacker News Reader

Comment by nickdrozd | Hacker News Reader

The "states" (A, B, C) correspond to goto targets. The "colors" (0, 1, 2, 3) are runtime data. At each state, the current color is read, and an instruction is executed (print some color, move left or right, goto some state) based on which color is there. Transliterated into C it looks like this:

  #include "machine.h"
  
  int main(void)
  {
   A:
    switch (SCAN) {
      case 0:
        WRITE(1); RIGHT; goto B;
  
      case 1:
        WRITE(3); LEFT; goto B;
  
      case 2:
        WRITE(1); RIGHT; goto H;
  
      case 3:
        WRITE(2); RIGHT; goto A;
    }
  
   B:
    switch (SCAN) {
      case 0:
        WRITE(2); LEFT; goto C;
  
      case 1:
        WRITE(3); RIGHT; goto B;
  
      case 2:
        WRITE(1); LEFT; goto C;
  
      case 3:
        WRITE(2); RIGHT; goto A;
    }
  
   C:
    switch (SCAN) {
      case 0:
        WRITE(3); RIGHT; goto B;
  
      case 1:
        WRITE(1); LEFT; goto B;
  
      case 2:
        WRITE(3); LEFT; goto C;
  
      case 3:
        WRITE(2); RIGHT; goto C;
    }
  
   H:
    HALT;
  }

Question: are there any opportunities to rewrite this logic in a more "structured" style, or to make any other optimizations?

View on HN

I love these puzzles. GNU C supports a label as value for computed goto. This is useful for direct threaded dispatch. You trade off a branch instruction for an address lookup, but it makes the code more structured.

  int main(void) {
    void* A[] = {&&A0, &&A1, &&A2, &&A3};
    void* B[] = {&&B0, &&B1, &&B2, &&B3};
    void* C[] = {&&C0, &&C1, &&C2, &&C3};
    goto *A[SCAN];
    A0: WRITE(1); RIGHT; goto *B[SCAN];
    A1: WRITE(3); LEFT ; goto *B[SCAN];
    A2: WRITE(1); RIGHT; HALT; return 0;
    A3: WRITE(2); RIGHT; goto *A[SCAN];
    B0: WRITE(2); LEFT ; goto *C[SCAN];
    B1: WRITE(3); RIGHT; goto *B[SCAN];
    B2: WRITE(1); LEFT ; goto *C[SCAN];
    B3: WRITE(2); RIGHT; goto *A[SCAN];
    C0: WRITE(3); RIGHT; goto *B[SCAN];
    C1: WRITE(1); LEFT ; goto *B[SCAN];
    C2: WRITE(3); LEFT ; goto *C[SCAN];
    C3: WRITE(2); RIGHT; goto *C[SCAN];
  }

> GNU C supports a label as value for computed goto.

Why doesn't any modern C standard like C23 include this? Seems like a glaring omission.

Sometimes, the fact that one implementation includes it can make it actually more difficult to standardize, if there are some implementation details that are disagreeable (see GNU's nested functions)

> Question: are there any opportunities to rewrite this logic in a more "structured" style, or to make any other optimizations?

Because A and C only jump to B it is possible to structure this using only loops and one boolean. Let us use Rust to demonstrate as it lacks GOTO:

    let mut a = true;
    loop {
        loop {
            if a { // state A
                match scan() {
                    0 => { write(1); right(); break }
                    1 => { write(3); left(); break }
                    2 => { write(1); right(); return }
                    3 => { write(2); right() }
                }
            } else { // state C
                match scan() {
                    0 => { write(3); right(); break }
                    1 => { write(1); left(); break }
                    2 => { write(3); left() }
                    3 => { write(2); right() }
                }
            }
        }

        a = loop { // state B
            match scan() {
                0 => { write(2); left(); break false }
                1 => { write(3); right() }
                2 => { write(1); left(); break false }
                3 => { write(2); right(); break true }
            }
        }
    }

Of course it is possible to rewrite this as a single loop if you are willing to accept two bits of extra state rather than one.

Wow! I don't know if I would call that "structured", but it's pretty clever. And horrifying. Well-done!

What's the initial state supposed to be?

Infinite tape of zeros.

Zero is neither A nor B or C...?

The start state is A.

The initial state is A, the tape is full of 0 (on both sides).

My understanding is that the states are conventionally listed in order, so A would be the initial state:

> A TM string is in lexical normal form iff the following conditions obtain: …The non-initial active states first occur in ascending order…

Reply on news.ycombinator.com