OpenEuphoria

Re: Kat's goto

• Posted by David Cuny <dcuny at LANSET.COM> Feb 07, 2002
• 460 views

My issues with the GOTO are purely a matter of implemention. The basic idea 
behind coding the goto is fairly simple. You have a table that holds the 
position of the goto. I'll use line numbers here for convenience:

 10 foo:

will get you a table like this:

	goto	at
	foo:	10

When you reference the GOTO, you just look it up in the table:

 10 foo:
 20 print "endless loop"
 30 goto foo:

becomes (more or less)

 10 rem foo:
 20 print "endless loop"
 30 goto 10

If you reference a GOTO before that label is defined, you need to set up a 
backpatch table, so once the GOTO is defined, you can fill it in. For example:

 10: goto bar:

creates an entry into the backpatch table:

	bar	10

and an instruction:

 10: goto -1

when bar: is finally encountered:

  20: bar:

the backpatch table is searched to see if there are any addresses that need 
to be patched. There are, and the code becomes:

 10: goto 20
 20: rem bar:

If, during runtime, you encounter a:

 goto -1

you know you've reached an undefined GOTO, and searching the backpatch table 
will tell you what that GOTO was. At the end of compilation, you have any 
values left in your backpatch table, it's a similar error.

So, on a conceptual basis, implementing GOTO is fairly easy. The issue is 
whether the language itself will support it. I'll give a few non-Euphoria 
examples to show how the language might not allow a GOTO.

First of all, the language might not compile to bytecodes. For example, Awk 
and a number of other languages store the program in data structures - 
typically a binary tree:

   struct {
      opcode
      data
      left_node
      right_node
   }

So a 'while' loop:

   while <some test>
      <some code>
   wend

might be encoded:

   { OP_WHILE, NULL, <some test>, <some code> }

There's no way to implement a GOTO in this kind of environment. And even if 
you had bytecodes, there is no guarantee that a GOTO could be coded. For 
example, the WHILE loop might be implemented as:

   <WHILE TEST> <ADDRESS OF CODE>

with a JUMP to the WHILE block, instead of inlining the code (see, for 
example, the demo interperter in "The Unix Programming Environment", by Brian 
W. Kernighan and Rob Pike).

Finally, there are stack issues. I'll use FORTH loops as an example. FORTH 
has two stack: a DATA stack to hold values, and a RETURN stack to hold the 
address to return to. The FOR loop looks something like this:

   1 10 DO
      ." Hello, world!"
   +LOOP

This prints "Hello, world!" 10 times. The way it works is a bit tricky: FORTH 
sticks the loop values on the RETURN stack for convenience. As a result, if 
you just did a GOTO out of the loop, you would end up with garbage on the 
stack. Leaving junk on the DATA stack is bad enough, but leaving it on the 
RETURN stack is fatal, since it will try to jump to that address.

So implementing a GOTO isn't really an issue of philosophy as it is language 
design. There may be design issues in Euphoria which make it next to 
impossible to implement a GOTO.

I suspect that a GOTO could be supported by keeping track of the nesting 
level that the label was on. When a GOTO was called, it would then EXIT until 
the correct nesting level had been arrived at, and then JUMP to the code.

This would mean modifying the code for all the block structures (for, while) 
to support the new EXIT, adding code to keep track of how deep the nesting 
was at interpret and runtime, and tables for backpatching, etc. Not entirely 
trivial.

-- David Cuny