10
$\begingroup$

Suppose I am writing a source-to-source compiler (also called a transpiler) from one high-level imperative language to another, where the source language allows labelled statements to be targeted by break and continue, while the target language doesn't. For example, from Javascript to Python.

Manual translation is possible by inserting a flag variable, but there may be many other places besides the loop conditions where this flag will need to be checked, so it is not as simple as just including the flag in the loop condition. For example:

// Javascript code
outer:
while(cond1) {
    foo();
    while(cond2) {
        bar();
        if(cond3) {
            break outer;
        }
        baz();
    }
    qux();
}
# Translated Python code
flag = True
while flag and cond1:
    foo()
    while flag and cond2:
        bar()
        if cond3:
            flag = False
        if flag:
            baz()
    if flag:
        qux()

How can a program transformation like the above be done automatically ─ either by inserting a flag variable or otherwise? Answers which make use of single-level break/continue in the target language are fine, but answers which can eliminate break/continue entirely are even better.

Ideally I would like to preserve the original code structure as much as possible, so e.g. replacing the whole outer loop with a loop-and-switch state machine is not a preferred solution.


This question is distinct from What are the different options for breaking out of an inner loop? as that question is about alternatives to labelled break and continue when designing a language, whereas this question is about how to transpile between existing languages.

$\endgroup$

4 Answers 4

8
$\begingroup$

Here's a method using unlabelled break/continue. I'll use slightly different JS code:

outer:
while (cond) {
    foo();
    inner:
    while (cond) {
        bar();
        while (cond) {
            if (cond) {
                break outer;
            } else if (cond) {
                continue inner;
            }
        }
        if (cond) break;
    }
    baz();
}

The idea is, rather than using just a boolean flag, to include enough information to fully describe what you're doing with which loop.

  1. Construct a map labelDepths from labels to their loops’ nesting depth. In this example, if the translator is written in JS, our map might be the object {"outer": 0, "inner": 1}.
  2. Within each function declaration in the output, write two local variable declarations (with unique names), e.g. depth=0 and action=None. These will control, respectively, break/continue propagation and which action to take at the end of propagation.
  3. For each labelled break/continue statement in the input, replace the statement in the output with depth=_D_; action=_A_; break, where _D_ is the value of labelDepths[label] and _A_ is either "break" or "continue". For example, break inner; would become depth=1;action="continue";break. Write unlabelled break/continue statements to the output normally.
  4. For each loop statement with depth greater than 0, append the following as the next sibling of the loop statement, replacing _D_ with (the depth of the loop) - 1:
if action != None:
    if depth < _D_:
        break
    if action == "continue":
        action = None
        continue
    action = None
    break

Our JS example then ends up as the following Python code:

action = None
depth = 0

# outer:
while cond: # depth = 0
    foo()
    # inner:
    while cond: # depth = 1
        bar()
        while cond: # depth = 2
            if cond:
                # break outer
                depth=0;action="break";break
            elif cond:
                # continue inner
                depth=1;action="continue";break
        if action != None:
            if depth < 1:
                break
            if action == "continue":
                action = None
                continue
            action = None
            break
        if cond:
            break
    if action != None:
        if depth < 0:
            break
        if action == "continue":
            action = None
            continue
        action = None
        break
    baz()

There are a few ways we could make the output more efficient, such as using integers for the action constants or only including propagation code after loops that transitively contain labelled break/continue statements, but hopefully this gives you the basic idea.

$\endgroup$
3
  • $\begingroup$ This results in output code that is a bit more verbose than you'd get by hand, but it has the advantage that it doesn't require transforming any other kinds of statement than the loops, break and continue statements themselves. Nice one! (also welcome!) $\endgroup$
    – kaya3
    May 22, 2023 at 7:20
  • $\begingroup$ @kaya3 Thanks! I figure a little extra verbosity isn't a big deal in translated code. If you're worried about readability, though, it would probably help to add some simple comments to the output. $\endgroup$ May 22, 2023 at 7:34
  • $\begingroup$ Readability isn't super-important, just one consideration among many. $\endgroup$
    – kaya3
    May 22, 2023 at 7:35
8
$\begingroup$

One possible transpilation, if the language supports exceptions, is to rely on those, producing:

class BreakOuter(BaseException):pass
try: 
   while cond1:
      foo()
      while cond2:
         bar()
         if cond3:
             raise BreakOuter()
         baz()
except BreakOuter:
    pass

This, while a bit verbose, has the advantage that code only needs to get added in one place (the outer loop at the end of the break), making transpilation only require replacing that while loop with a verbose but constant bit of boilerplate and no analysis of the code inside the loop.

For a multi-level continue, you swap the order of the try and the outer while loop.

while cond1:
   try: 
      ...
   except ContinueOuter:
     pass

If the base code has multiple nested breaks, then they can use different exception classes for each label.

$\endgroup$
3
  • 6
    $\begingroup$ This would work but throwing and catching exceptions is usually quite slow, I don't really see what benefit this would have over the flag setting approach. Still +1 for the novel idea $\endgroup$
    – mousetail
    May 21, 2023 at 19:40
  • 2
    $\begingroup$ One upside of this approach is that it barely changes the structure of the code. Python in particular also uses exceptions to terminate for loops, because iterators are supposed to throw StopIteration to signal when they have no more elements; so the performance implications in Python aren't that significant. $\endgroup$
    – kaya3
    May 24, 2023 at 19:19
  • $\begingroup$ @mousetail - the performance varies depending on the language implementation. The question asked about both Javascript and Python, and while I wouldn't recommend this for Javascript as most JS virtual machines aren't optimized for it, CPython and most other Python implementations have very fast exception handling, so it would be sensible to use it there. $\endgroup$
    – occipita
    Aug 5, 2023 at 14:38
5
$\begingroup$

A simple solution would be to extract the (outer) loop into a function and return early. The function could take all variables that the loops needs as parameters. If it needs to modify any of the variables it can take pointers or references to them, or, if your target language does not support those, return the modified value and assign that to the original variable.

Your example would result in the following code:

mutated_variable = ...

def outer(mutated_var):
    while cond1:
        foo()
        while cond2:
            bar()
            # mutated_var is passed as a parameter, 
            # mutated and returned
            mutated_var += 1 
            if cond3:
                return mutated_var
            baz()
        qux()
    return mutated_var

mutated_variable = outer(mutated_variable)

Only if your target language does not support mutating references or multiple return values this approach won't work when multiple variables are mutated in the loop. But then you can still group them in a struct or similar.

$\endgroup$
5
  • $\begingroup$ I have no idea if this is idiomatic or even correct python, but I hope it gets the point across $\endgroup$
    – chrysante
    May 22, 2023 at 17:47
  • $\begingroup$ To mutate variables, closures or inner functions could be used $\endgroup$
    – Seggan
    May 22, 2023 at 18:01
  • $\begingroup$ Given the clarification, this is a good answer, since it does work fine for many target languages (particularly in Python, the nonlocal keyword is enough to modify variables from the outer scope), and it doesn't change the structure of the code very much. $\endgroup$
    – kaya3
    May 24, 2023 at 15:48
  • $\begingroup$ This works well for break... but what about continue? $\endgroup$ Aug 8, 2023 at 12:06
  • 1
    $\begingroup$ @MatthieuM. For continue you would extract the body of the outer loop into a function and return early. It is a good point though because for a loop that has both break and continue statements this solution breaks down and you would have to resort to flags. $\endgroup$
    – chrysante
    Aug 8, 2023 at 15:38
2
$\begingroup$

If your target language lacks labelled breaks but has goto (for example, if the target language is C), you could transpile loops of this form:

outer: while cond {
  ...
}

to loops of this form:

while (cond) {
  ...
  continue_outer:
}
break_outer:

Then, continue outer and break outer become goto continue_outer and goto break_outer respectively. Depending on your target language, you may have to be careful not to generate two labels of the same name in the same file.

$\endgroup$
3
  • 2
    $\begingroup$ Do any languages exist that lack labeled break but do have goto? Good answer otherwise $\endgroup$
    – mousetail
    May 21, 2023 at 15:28
  • 4
    $\begingroup$ C and its immediate family don't have labelled break. $\endgroup$
    – Bbrk24
    May 21, 2023 at 15:29
  • $\begingroup$ @mousetail APL has goto but no labelled break. $\endgroup$
    – Adám
    May 24, 2023 at 16:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .