How do I implement a return statement in a toy language?

Question

I recently made a toy programming language using C, Bison, Flex, and this post as a starting point. It looks a lot like Python except there's no colons or whitespace rules.

The code is here, but it's less important than the concept/algorithm I'm stuck on.

I designed my abstract syntax tree just like Rudi did in the post linked above.

The trick is, I can't think of a great way to return from user-defined functions, or break out of loops. If I require only a single return statement at the end of a user-defined function, it's doable (actually this is what currently works for user-defined functions).

Example:

i = 0
while 1 do
  if i > 15 then
     break
  end
done

Example 2:

def mean(somelist)
  if len(list) == 0 then
    return 0  # throw error
  else
    return sum(somelist) / len(somelist)
  end
end

Answer 1

Some popular stack-based languages push a value onto the stack which is then popped by the calling function. That might work for you.

Of course, this relies on having a function with a known return type. Python returns PyNone if the function is 'void' (i.e. returns nothing). A Python function returns only one value (which could be None, or an object or a tuple or whatever).

C-type languages also return only one value from a function.

I think the point is that in a strong-typed language you always have a return value and you must always return one. In a weak typed language where you might or might return a value, you have one nonetheless.

Answer 2

The answer to that one depends a lot on the internals of how your code works.

When I wrote my Mote Compiler (a VB-like compiler), I called MoteEngine.prototype.runFuncStart, when a function started. I created a new object to hold all local variables and then I pushed that onto my stack.

MoteEngine.prototype.runFuncEnd cleaned up the stack.

Answer 3

Well, it depends heavily on HOW exactly you implement your execution engine. If you follow Rudi's suggestion of implementing the execution engine with functions that recursively call each other to traverse the AST, then to implement a break or return, you need to return through several levels of C call stack. You can do this with setjmp/longjmp. So for example your code might look something like:

struct ExecEnviron {
    /* other contents of ExecEnviron, we're just adding a bit */
    jmp_buf *break_context;  /* where a 'break' or 'continue' should jump to */
    jmp_buf *return_context; /* where a 'return' should jump to */
};

void ExecWhile(ExecEnviron *e, AstElement *a) {
    jmp_buf local, *old = e->break_context;
    e->break_context = &local;

    if (setjmp(&local) != 1)
        while (dispatchExpression(a->whileStmt.cond))
            dispatchStatement(a->whileStmt.body);
    e->break_context = old;
}
void ExecBreak((ExecEnviron *e, AstElement *a) {
    longjmp(e->break_context, 1);
}
void ExecContinue((ExecEnviron *e, AstElement *a) {
    longjmp(e->break_context, 2);
}

Setjmp/longjmp work adequately well for breaking OUT of nested context, but won't work for general label/goto handling (as those allow for jumping INTO the middle of a loop). If you want to deal with that, you'll have to use a completely different execution engine, and transform the AST into something more linear like bytecode or threaded code.