from parser import *

class EvaluatorException(Exception):
    pass

def eval(exp, env):
    # symbols are names to be left unevaluated.
    if isinstance(exp, NameExp):
        raise EvaluatorException("unbound variable: " + exp.body)
    if isinstance(exp, LambdaExp):
        # no change
        return exp
    if isinstance(exp, ApplyExp):
        # We're lazy, so we apply before evaluating the argument.
        # We do of course need to evaluate the function.
        rator = eval(exp.rator, env)
        rand = exp.rand
        return apply(rator, rand, env)
    if isinstance(exp, StringExp):
        import sys
        sys.stdout.write(exp.line)
        return LambdaExp('x', NameExp('x')) # i.e. the identity function
    if isinstance(exp, SpecialExp):
        if exp.body == '#list':
            # list all definitions in the environment
            import sys
            defs = env.keys()
            defs.sort()
            sys.stdout.write('[' + ' '.join(defs) + ']')
        return exp
    raise EvaluatorException("Unknown expression type for evaluation")

def substitute(exp, name, value):
    if isinstance(exp, StringExp):
        return exp
    if isinstance(exp, NameExp):
        if exp.body == name:
            return value
        return exp
    if isinstance(exp, ApplyExp):
        return ApplyExp(substitute(exp.rator, name, value), substitute(exp.rand, name, value))
    if isinstance(exp, SpecialExp):
        return exp
    if isinstance(exp, LambdaExp):
        # lambda can shadow the name
        if name == exp.arg:
            return exp
        return LambdaExp(exp.arg, substitute(exp.body, name, value))
    print exp
    raise EvaluatorException("Unknown expression type for substitution")

def apply(rator, rand, env):
    # since we're lazy, rand is unevaluated, so it might be anything
    # Rator, on the other hand ought to be a lambda or a special word
    if isinstance(rator, LambdaExp):
        # okay, now we actually have to do stuff
        # first we substitute all instances of the first named parameter
        # of the lambda with the rand.
        body = substitute(rator.body, rator.arg, rand)
        return eval(body, env)
    if isinstance(rator, SpecialExp):
        if rator.body == '#show':
            # first evaluates the operand, then shows it, returns the result of the evaluation
            import sys
            rand = eval(rand, env)
            sys.stdout.write(str(rand))
            return rand
        else:
            raise EvaluatorException("Unknown special word: " + rator.body)
    raise EvaluatorException("Trying to apply something that isn't a lambda")