Lets build a simple interpreter from scratch in python, pt.09: Function Call, Return

# This is required for returning without primitives
class Empty:
    pass

class Interpreter:

    # Updated constructor for holding our functions

    def __init__(self):
        self.scope= [{}]
        self.loop_stack=[]
        self.funcs = {}

    #....(previous code)....

    # Updated to check if we returned or not
    def If(self,xs):
        _,cond,trueblock,elseblock=xs
        if self.eval(cond):
            if isinstance(trueblock[0],list):
                for x in trueblock:
                    self.eval(x)
                    # Return check
                    if "retval" in self.scope[-1]:
                        return                        
            else:
                self.eval(trueblock)
        else:
            if elseblock:
                if isinstance(elseblock[0],list):
                    for x in elseblock:
                        self.eval(x)
                        # Return check
                        if "retval" in self.scope[-1]:
                            return                        
                else:
                    self.eval(elseblock)



    # Updated:        
    def While(self,xs):
        self.loop_stack.append({"break":False,"continue":False})
        _ , cond , block = xs
        while self.eval(cond):
            if isinstance(block[0],list):
                for x in block:
                    self.eval(x)
                    # Return check
                    if "retval" in self.scope[-1]:
                        self.loop_stack.pop()
                        return                        
                    if self.loop_stack[-1]["break"]:
                        self.loop_stack.pop()
                        return
                    if self.loop_stack[-1]["continue"]:
                        self.loop_stack[-1]["continue"]=False
                        break
            else:
                self.eval(block)
        self.loop_stack.pop()

    # Updated:
    def For(self,xs):
        self.loop_stack.append({"break":False,"continue":False})        
        _, inits, cond, increments, block = xs
        for x in inits: 
            self.eval(x)
        while self.eval(cond):
            if isinstance(block[0],list):
                for x in block:
                    self.eval(x)
                    # Return check
                    if "retval" in self.scope[-1]:
                        self.loop_stack.pop()
                        return                                            
                    if self.loop_stack[-1]["break"]:
                        self.loop_stack.pop()
                        return
                    if self.loop_stack[-1]["continue"]:
                        self.loop_stack[-1]["continue"]=False
                        break
            else:
                self.eval(block) 
            for x in increments:
                self.eval(x)
        self.loop_stack.pop()

    #New: Define a function
    def Function(self,xs):
        _, name, params, block = xs
        self.funcs[name]={"params":params,"block":block}

    #New:
    def Return(self,xs):
        if len(self.scope)<2: # we are in global scope
            print("error: 'return' must be in function")
            exit(1)
        # Return with value
        if len(xs)>1:
            self.scope[-1]["retval"]=self.eval(xs[1])
        # Return without value
        else:
            self.scope[-1]["retval"]=Empty()

    # New:
    def Call(self,xs):
        _, funcname, params = xs
        # Before adding scope to scope list,
        scope={}
        func=self.funcs[funcname]
        # we must evaluate function params in current scope,
        for i,p in enumerate(func["params"]):
            scope[p]=self.eval(params[i])
        self.scope.append(scope)
        # now we are in new scope,
        for x in func["block"]:
            self.eval(x)
            if "retval" in self.scope[-1]:
                break
        retval=self.scope[-1]["retval"]
        self.scope.pop()
        return retval

code=[

    ["Function","fibonacci",["n"], [

        ["If",["Lte",["Get","n"],1], 
            ["Return",["Get","n"]],[]
        ],

        ["Return",
            ["Add",
                ["Call","fibonacci",[["Sub",["Get","n"],1]]],
                ["Call","fibonacci",[["Sub",["Get","n"],2]]]
            ]
        ]
    ]],

    ["Print","fibonacci(15) = ", ["Call","fibonacci",[15]]],

    ["Return"]
]

interpreter=Interpreter()

interpreter.run(code)

fibonacci(15) = 610
error: 'return' must be in function