How to implement a return * statement in C?

Question

I was reading about recursive ascent-descent parsers here.

In section 2.1, they describe a return * statement,

Our C extension occurs with return statements. We have used the notation return * k to indicate that a k-level function return is to be made. That is, return * 1 is identical to the normal C return statement and simply returns control to the caller of the current function; return * 2 means that control is to be returned to the caller of the caller, and so on. Finally, return * 0 is to be interpreted as a null statement. We leave emulation of the return * k construct in languages that lack this operation as a simple exercise for the reader.

How can I implement such return* statements in my own code or emulate this behavior using goto statements or/and pointer? Are there any languages that provide this functionality by default?

Answer 1

The setjmp solution suggested by @Shawn should work, as long as it doesn't overflow the setjmp stack (and remember that recursive ascent parsers may require a reasonably large stack), but it imposes a pretty significant overhead on every call in order to slightly optimise returns which skip over a few stack frames.

In the recursive ascent model, the number of frames skipped is small, often 0. So the overhead will be large and the savings small.

You could write a somewhat faster solution using libunwind (see unw_step() and unw_resume()), but note that unw_step treats the call stack as a linked list (which is what it is), and therefore can only step over a single stack frame at a time. So you end up with a loop around unw_step calls. Also, you'd have to make sure that no function call was inlined.

A much simpler and faster solution is to simply wrap CALL and RETURN in macros, as @shawn suggests, and use the otherwise-unused return value to count unwinds: (Slightly modified to use variadic macros)

#include <stdio.h>

int sp = 0;

#define CALL(f, ...)                            \
  do {                                          \
    ++sp;                                       \
    RETLEVEL(f(__VA_ARGS__));                   \
  } while (0)

#define RETLEVEL(n)                             \
  for ( int n__ = n; n__ > 0 && sp > 0; ) {     \
    --sp;                                       \
    return n__ - 1;                             \
  }
#define RETURN RETLEVEL(1)

int f3(void) {
  printf("In f3(), sp is %d, returning back 2 levels\n", sp);
  RETLEVEL(2);
}

int f2(void) {
  printf("In f2(), calling f3(), sp is %d\n", sp);
  CALL(f3);
  printf("Returning from f2(), sp is %d\n", sp);
  RETURN;
}

int f1(void) {
  printf("In f1(), calling f2(), sp is %d\n", sp);
  CALL(f2);
  printf("Returning from f1(), sp is %d\n", sp);
  RETURN;
}

int main(void) {
  printf("In main(), calling f1(), sp is %d\n", sp);
  CALL(f1);
  printf("Returning from main(), sp is now %d\n", sp);
  return 0;
}

Answer 2

You can use setjmp() and longjmp() to emulate this multi-level return, as long as you take care to maintain a stack of jmp_bufs every time you call a function.

Example:

#include <stdio.h>
#include <setjmp.h>
#include <assert.h>

#define MAXDEPTH 10
jmp_buf stack[MAXDEPTH];
int sp = 0;

#define CALL(f)                                                                \
  do {                                                                         \
    assert(sp < MAXDEPTH);                                                     \
    if (setjmp(stack[sp++]) == 0) {                                            \
      f;                                                                       \
    }                                                                          \
  } while (0)
#define RETLEVEL(n)                                                            \
  do {                                                                         \
    if ((n) > 0) {                                                             \
      sp -= (n);                                                               \
      assert(sp >= 0 && sp < MAXDEPTH);                                        \
      longjmp(stack[sp], 1);                                                   \
    }                                                                          \
  } while (0)
#define RETURN                                                                 \
  do {                                                                         \
    sp -= 1;                                                                   \
    assert(sp >= 0);                                                           \
    return;                                                                    \
  } while (0)

void f3(void) {
  printf("In f3(), sp is %d, returning back 2 levels\n", sp);
  RETLEVEL(2);
}

void f2(void) {
  printf("In f2(), calling f3(), sp is %d\n", sp);
  CALL(f3());
  printf("Returning from f2(), sp is %d\n", sp);
  RETURN;
}

void f1(void) {
  printf("In f1(), calling f2(), sp is %d\n", sp);
  CALL(f2());
  printf("Returning from f1(), sp is %d\n", sp);
  RETURN;
}

int main(void) {
  printf("In main(), calling f1(), sp is %d\n", sp);
  CALL(f1());
  printf("Returning from main(), sp is now %d\n", sp);
  return 0;
}

When compiled and run, this outputs:

In main(), calling f1(), sp is 0
In f1(), calling f2(), sp is 1
In f2(), calling f3(), sp is 2
In f3(), sp is 3, returning back 2 levels
Returning from f1(), sp is 1
Returning from main(), sp is now 0

Read up on those functions, though, as they come with a few caveats about local variables holding their values between setjmp() returns.

---

As for languages that have a built-in multi level return... tcl comes to mind with return -level N. Any language with continuations, like scheme, or coroutines can probably emulate it easily, though.