<p>Say I have the following construct in an interpreted language that uses an AST tree walker:</p>
<pre><code>for (int i in range(1, 1000)) {
  // do stuff
  if (i % 6 == 0) { continue }
  // do more stuff
  if (i == 872) { break }
}
</code></pre>
<p>How do I best tell my interpreter to jump to the next loop iteration or exit the loop altogether? Is there some sort of common pattern used or some other best practice?</p>
<p>Note that this could also apply to a while loop.</p>

<loops><tree-walker><interpreters>
How do I Interpret a Continue/Break Statement in a Loop?
CC BY-SA 4.0
2023-05-29T14:52:58.887Z
@lyxal Yeah the JVM implements loops exactly that way, using gotos, iirc (it's a proper instruction in bytecode, now I'm just waiting for Java itself to support gotos)
user
CC BY-SA 4.0
2023-05-16T22:21:13.070Z
Do you mean a tree-walking interpreter, or a bytecode interpreter? The answer for the latter is much closer to how a compiler would have to do it, since bytecode interpreters tend to convert control-flow instructions into jumps at the compilation stage.
kaya3
CC BY-SA 4.0
2023-05-16T22:22:16.057Z
@kaya3 I mean a tree walking interpreter - I'll edit that in
lyxal
CC BY-SA 4.0
2023-05-16T22:24:25.340Z
@kaya3 yeah I figured a byte code interpreter would be able to just jump to a different memory address using something analogous to a GOTO statement
lyxal
<p>What do you do on a regular iteration, how do, after the end of the last instruction, get back to the first, in the block of the for loop (actually, before that, to execute the increment and check the condition or progress the iterator, but not repeat the initialization)? Typically, wouldn't you insert (or rather, internally store the reference/address of that AST node on your internal stack or for the current loop) a jump target label of some sort, and if encountering the continue, you jump to that (or, if modifying the AST, replace the continue with a jump to this hard address/target)? Similar with break, jumps to the next spot after the end of the block that belongs to for (if it's a tree, unwinding/upwards till getting back to for, and then continuing with next).</p>

CC BY-SA 4.0
2024-06-12T22:38:32.763Z
2024-06-12T22:38:32.763Z
skreutzer
<p>Typically, you need to distinguish between what it means for a statement or expression to &quot;complete normally&quot; or &quot;complete abruptly&quot; (borrowing terminology from the <a href="https://docs.oracle.com/javase/specs/jls/se19/html/jls-15.html#jls-15.6" rel="noreferrer">Java Language Specification</a>). An expression which evalutes to a value &quot;completes normally&quot;, as does a statement which executes in a normal sequence. On the other hand, a statement or expression which has some effect on the surrounding control-flow &quot;completes abruptly&quot;.</p>
<p>A statement or expression could complete abruptly if it:</p>
<ul>
<li>Returns a value from the enclosing function.</li>
<li>Throws an exception.</li>
<li>Breaks from or continues an enclosing loop.</li>
</ul>
<p>So generally speaking, these are all handled the same way. A typical solution is to represent the result of a statement or expression as a discriminated union of these possibilities, for example in Rust you might write:</p>
<pre><code>enum EvalResult {
    Normal(Value),
    Return(Value),
    Throw(Value),
    Break,
    Continue,
}
</code></pre>
<p>(If you have labelled breaks and continues, or you allow constructs like <code>let foo = loop { break 5; }</code>, then your enum will need to account for those, too.)</p>
<p>Your &quot;eval&quot; function, which evaluates an AST node, returns a result like this. Then when evaluating a loop, you would check for these results and handle them appropriately:</p>
<pre><code>match ast_node {
    // ...
    WhileLoop(cond, body) =&gt; {
        loop {
            let cond_result = eval(cond);
            match cond_result {
                Normal(v) =&gt; if !v.is_truthy() { break; },
                _ =&gt; return cond_result,
            }
            
            let body_result = eval(body);
            match body_result {
                Normal(_) | Continue =&gt; continue,
                Break =&gt; break,
                Return(_) | Throw(_) =&gt; return body_result,
            }
        }
        return Normal(VOID_UNIT);
    },
    // ...
}
</code></pre>
<p>Here I'm assuming <code>is_truthy()</code> converts a <code>Value</code> to a native Boolean in the host language, and <code>VOID_UNIT</code> is the value resulting from a statement which doesn't produce a &quot;proper&quot; value.</p>
<p>Note how we <code>return cond_result</code> or <code>return body_result</code> directly when it is necessary to propagate a control-flow effect that this loop isn't supposed to handle itself, for example if the loop body contains a <code>return</code> or <code>throw</code> statement. The same propagation will have to be done elsewhere, e.g. when you add two numbers together, you'll have to propagate control-flow effects from <code>left_result</code> and <code>right_result</code>, in order for those control-flow effects to end up being handled by the <code>eval</code> function for the correct AST node.</p>

CC BY-SA 4.0
2023-05-16T22:37:51.637Z
2023-05-16T22:43:27.937Z
2023-05-16T22:43:27.937Z
kaya3
<h1>Throw an exception</h1>
<p>For a simple tree-walking interpreter in a language with catchable exceptions, both <code>break</code> and <code>continue</code> statements can be implemented as throwing a specific exception, while the loop sets up a try-catch to detect and handle them.</p>
<p>Consider this pseudocode implementation:</p>
<pre><code>interpret_while(condition, body):
    try {
        while (evaluate(condition) is True):
            try {
                evaluate(body)
            } catch (Continue) {
                // do nothing, just go to next iteration
            }
    } catch (Break) {
       // also do nothing, have already left the loop
    }

interpret_continue():
    raise Continue
interpret_break():
    raise Break
</code></pre>
<p>We have two exception types and two try-catches, one inside the loop for <code>continue</code> and one outside for <code>break</code>. If there are nested loops, the innermost one will automatically catch the exception and produce the right semantics. The exception-handling system already innately deals with the necessary stack unwinding, exiting each layer of recursion until you get back to the right place.</p>
<p>This can also allow for <em>labelled</em> breaks: include the label in the exception, and test and re-throw if it doesn't match until it reaches the appropriate surrounding loop.</p>
<p>This is not going to be the most efficient or performant approach, but it's very straightforward to get moving with and leverages the functionality of the host system. A similar approach can be used to implement non-local returns or exception handling <em>within</em> the interpreted language, and those will fit in comfortably with one another.</p>

CC BY-SA 4.0
2023-05-16T22:34:30.117Z
2023-05-16T22:34:30.117Z
Michael Homer
# How do I Interpret a Continue/Break Statement in a Loop?
Posted by: username_0 on 2023-05-16
Say I have the following construct in an interpreted language that uses an AST tree walker:
for (int i in range(1, 1000)) {
  // do stuff
  if (i % 6 == 0) { continue }
  // do more stuff
  if (i == 872) { break }
}

How do I best tell my interpreter to jump to the next loop iteration or exit the loop altogether? Is there some sort of common pattern used or some other best practice?
Note that this could also apply to a while loop.
**Tags:** loops tree-walker interpreters
> **Comments:**
> **username_2**: Do you mean a tree-walking interpreter, or a bytecode interpreter? The answer for the latter is much closer to how a compiler would have to do it, since bytecode interpreters tend to convert control-flow instructions into jumps at the compilation stage.  
> **username_0**: @kaya3 I mean a tree walking interpreter - I'll edit that in  
> **username_0**: @kaya3 yeah I figured a byte code interpreter would be able to just jump to a different memory address using something analogous to a GOTO statement  
> **username_1**: @lyxal Yeah the JVM implements loops exactly that way, using gotos, iirc (it's a proper instruction in bytecode, now I'm just waiting for Java itself to support gotos)  
---
## 3 answers
### Answer by username_2 on 2023-05-16. Score: 12
Typically, you need to distinguish between what it means for a statement or expression to "complete normally" or "complete abruptly" (borrowing terminology from the Java Language Specification). An expression which evalutes to a value "completes normally", as does a statement which executes in a normal sequence. On the other hand, a statement or expression which has some effect on the surrounding control-flow "completes abruptly".
A statement or expression could complete abruptly if it:

Returns a value from the enclosing function.
Throws an exception.
Breaks from or continues an enclosing loop.

So generally speaking, these are all handled the same way. A typical solution is to represent the result of a statement or expression as a discriminated union of these possibilities, for example in Rust you might write:
enum EvalResult {
    Normal(Value),
    Return(Value),
    Throw(Value),
    Break,
    Continue,
}

(If you have labelled breaks and continues, or you allow constructs like let foo = loop { break 5; }, then your enum will need to account for those, too.)
Your "eval" function, which evaluates an AST node, returns a result like this. Then when evaluating a loop, you would check for these results and handle them appropriately:
match ast_node {
    // ...
    WhileLoop(cond, body) => {
        loop {
            let cond_result = eval(cond);
            match cond_result {
                Normal(v) => if !v.is_truthy() { break; },
                _ => return cond_result,
            }
            
            let body_result = eval(body);
            match body_result {
                Normal(_) | Continue => continue,
                Break => break,
                Return(_) | Throw(_) => return body_result,
            }
        }
        return Normal(VOID_UNIT);
    },
    // ...
}

Here I'm assuming is_truthy() converts a Value to a native Boolean in the host language, and VOID_UNIT is the value resulting from a statement which doesn't produce a "proper" value.
Note how we return cond_result or return body_result directly when it is necessary to propagate a control-flow effect that this loop isn't supposed to handle itself, for example if the loop body contains a return or throw statement. The same propagation will have to be done elsewhere, e.g. when you add two numbers together, you'll have to propagate control-flow effects from left_result and right_result, in order for those control-flow effects to end up being handled by the eval function for the correct AST node.
---
### Answer by username_4 on 2023-05-16. Score: 11
Throw an exception
For a simple tree-walking interpreter in a language with catchable exceptions, both break and continue statements can be implemented as throwing a specific exception, while the loop sets up a try-catch to detect and handle them.
Consider this pseudocode implementation:
interpret_while(condition, body):
    try {
        while (evaluate(condition) is True):
            try {
                evaluate(body)
            } catch (Continue) {
                // do nothing, just go to next iteration
            }
    } catch (Break) {
       // also do nothing, have already left the loop
    }

interpret_continue():
    raise Continue
interpret_break():
    raise Break

We have two exception types and two try-catches, one inside the loop for continue and one outside for break. If there are nested loops, the innermost one will automatically catch the exception and produce the right semantics. The exception-handling system already innately deals with the necessary stack unwinding, exiting each layer of recursion until you get back to the right place.
This can also allow for labelled breaks: include the label in the exception, and test and re-throw if it doesn't match until it reaches the appropriate surrounding loop.
This is not going to be the most efficient or performant approach, but it's very straightforward to get moving with and leverages the functionality of the host system. A similar approach can be used to implement non-local returns or exception handling within the interpreted language, and those will fit in comfortably with one another.
---
### Answer by username_3 on 2024-06-12. Score: 0
What do you do on a regular iteration, how do, after the end of the last instruction, get back to the first, in the block of the for loop (actually, before that, to execute the increment and check the condition or progress the iterator, but not repeat the initialization)? Typically, wouldn't you insert (or rather, internally store the reference/address of that AST node on your internal stack or for the current loop) a jump target label of some sort, and if encountering the continue, you jump to that (or, if modifying the AST, replace the continue with a jump to this hard address/target)? Similar with break, jumps to the next spot after the end of the block that belongs to for (if it's a tree, unwinding/upwards till getting back to for, and then continuing with next).
---
