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?

The article says "The corresponding recursive ascent-descent parser, coded using a small extension to C, is shown in Figure 1. " This reads like they change the C compiler. The code example in "Figure 1" of that article really shows return * 1; I fear you need that changed C compiler to follow the approach. — harper
– harper, Commented Mar 22, 2020 at 8:45

Shawn · Accepted Answer · 2020-03-22 10:37:24Z

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.

This is going to be super slow. If you're happy to wrap all calls and returns in macros there's a much simpler solution.

rici · Accepted Answer · 2020-03-22 16:17:05Z

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; }

Collectives™ on Stack Overflow

How to implement a return * statement in C?

2 Answers 2

1 Comment

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Related