import sys

class StackEntry(object):
    def __init__(self, var_map):
        self.var_map = var_map

    @classmethod
    def empty(cls):
        return StackEntry(dict())

class Stack(object):
    def __init__(self):
        self.entries = [StackEntry.empty()]

    def push(self, entry):
        self.entries.append(entry)

    def pop(self):
        return self.entries.pop()

    def define_name(self, name, val):
        self.entries[-1].var_map[name] = val

    def lookup_name(self, name):
        """Dynamic scope"""

        # Look up the stack
        for e in reversed(self.entries):
            if name in e.var_map:
                return e.var_map[name]


class Function(object):
    def __init__(self, params, body):
        self.params = params
        self.body = body

    def stack_entry(self, args):
        return StackEntry(dict(zip(self.params, args)))



# Expressions
class Expression(object):
    pass

class FunCallExpr(Expression):
    def __init__(self, function_name, args):
        self.function_name = function_name
        self.args = args

    def evaluate(self, stack):
        func = stack.lookup_name(self.function_name)
        stack.push(func.stack_entry(self.args))
        return run_body(stack, func.body)

class LiteralExpr(Expression):
    def __init__(self, literal):
        self.literal = literal

    def evaluate(self, stack):
        return self.literal
class VariableExpr(Expression):
    def __init__(self, name):
        self.name = name

    def evaluate(self, stack):
        return stack.lookup_name(self.name)

class OperatorExpr(Expression):
    def __init__(self, operator, opArgExprs):
        self.operator = operator
        self.opArgExprs = opArgExprs

    def evaluate(self, stack):
        return self.operator(*[e.evaluate(stack) for e in self.opArgExprs])

# Statements
class Command(object):
    pass

class EvalCmd(Command):
    def __init__(self, expr):
        self.expr = expr

    def run(self, stack):
        self.expr.evaluate(stack)

class PrintCmd(Command):
    def __init__(self, expr):
        self.expr = expr

    def run(self, stack):
        print("Stdout:", self.expr.evaluate(stack))

class DefineCmd(Command):
    def __init__(self, name, expr):
        self.name = name
        self.expr = expr

    def run(self, stack):
        stack.define_name(self.name, self.expr.evaluate(stack))

class ReturnCmd(Command):
    def __init__(self, return_value):
        self.return_value = return_value


def run_body(stack, body):
    for cmd in body:
        if isinstance(cmd, ReturnCmd):
            return cmd.return_value

        cmd.run(stack)


# Shorthands
def lit(l):
    return LiteralExpr(l)

def add(l,r):
    return OperatorExpr(lambda x,y: x + y, [l, r])

def pr(exp):
    return PrintCmd(exp)

def defun(name, args, *body):
    return DefineCmd(name, LiteralExpr(Function(args, body)))

def var(name):
    return VariableExpr(name)

def ret(expr):
    return ReturnCmd(expr)

def funcall(name, *args):
    return FunCallExpr(name, args)

def ev(expr):
    return EvalCmd(expr)

if __name__ == "__main__":
    run_body(Stack(), [
        # define a function f
        defun("f", ["x"],
              # That prints it's argument incremented
              pr(add(lit(1), var("x")))),

        # Evaluate call to the funxtion
        ev(funcall("f", 2))])