> What if, instead of a GOTO, we want to implement a GOSUB — a call to an arbitrary location that can later return execution to where the call happened?
This is actually much simpler because you return back from where you made the call. That means you can look up the label in the symbol table, get a corresponding chunk of AST, evaluate it, and then continue execution from whenever you were — it literally translates into an "eval" function call.
The "GOTO", on the other hand, requires you to abandon your current continuation and replace it with an entirely different one which is impossible in a straightforward recursive tree-walking interpreter, as you've discovered. It can be done in a not-so-recursive tree-walking interpreter but it's still quite tricky: you basically have to maintain the stack and track the nesting of the nodes manually.
But at this point you'd be effectively doing an on-the-fly conversion to bytecode and its immediate execution so you may as well just bite the bullet and factor it out as a separate entity entirely.
This is actually much simpler because you return back from where you made the call. That means you can look up the label in the symbol table, get a corresponding chunk of AST, evaluate it, and then continue execution from whenever you were — it literally translates into an "eval" function call.
The "GOTO", on the other hand, requires you to abandon your current continuation and replace it with an entirely different one which is impossible in a straightforward recursive tree-walking interpreter, as you've discovered. It can be done in a not-so-recursive tree-walking interpreter but it's still quite tricky: you basically have to maintain the stack and track the nesting of the nodes manually.
But at this point you'd be effectively doing an on-the-fly conversion to bytecode and its immediate execution so you may as well just bite the bullet and factor it out as a separate entity entirely.