import re
import sys
import traceback
from io import StringIO
from ucb import main, trace
from scheme_tokens import *
from scheme_utils import *
from scheme_primitives import *

# Name of file containing Scheme definitions.
SCHEME_PRELUDE_FILE = "scheme_prelude.scm"

class PrimitiveFunction(SchemeValue):
    """A Scheme function implemented directly in Python."""

    def __init__(self, func):
        """The function that applies Python function FUNC to its operands."""
        self.func = func

    def type_name(self):
        return "primitive procedure"

    def apply_step(self, args, evaluation):
        "*** YOUR CODE HERE ***"
        evaluation.set_value(FALSE)

    def __repr__(self):
        return "PrimitiveFunction({0})".format(repr(self.func))

class LambdaFunction(SchemeValue):
    """A function defined by lambda expression or the complex define form."""

    def __init__(self, formals, body, env):
        """A function whose formal parameter list is FORMALS (in Scheme format),
        whose body is the single Scheme expression BODY, and whose environment
        is the EnvironFrame ENV.  A lambda expression containing multiple expressions,
        such as (lambda (x) (set! y x) (+ x 1)) can be handled by
        using (begin (set! y x) (+ x 1)) as the body."""
        self.formals = formals
        self.body = body
        self.env = env

    def type_name(self):
        return "closure"

    def apply_step(self, args, evaluation):
        "*** YOUR CODE HERE ***"
        evaluation.set_expr(FALSE)

    def write(self, out):
        print("<(lambda ", file=out, end='')
        self.formals.write(out)
        print(" ", end='', file=out)
        self.body.write(out)
        print("), {0}>".format(repr(self.env)), file=out, end='')

    def __repr__(self):
        return "LambdaFunction({0}, {1}, {2})" \
               .format(repr(self.formals), repr(self.body), repr(self.env))

class EnvironFrame:

    """An environment frame, representing a mapping from Scheme symbols to
    Scheme values, possibly enclosed within another frame."""

    def __init__(self, enclosing):
        """An empty frame that is attached to the frame ENCLOSING."""
        self.inner = {}
        self.enclosing = enclosing

    def __getitem__(self, sym):
        return self.find(sym).inner[sym]

    def __setitem__(self, sym, val):
        self.find(sym).inner[sym] = val

    def __repr__(self):
        if self.enclosing is None:
            return "<Global frame at {0}>".format(hex(id(self)))
        else: 
            return "<Frame at {0} --> {1}>".format(hex(id(self)),
                                                   repr(self.enclosing))

    def find(self, sym):
        """The environment frame at or enclosing SELF that defined SYM.  It
        is an error if it does not exist."""
        e = self
        while e is not None:
            if sym in e.inner:
                return e
            e = e.enclosing
        raise SchemeError("unknown identifier: {0}".format(str(sym)))

    def make_call_frame(self, formals, vals):
        """A new local frame attached to SELF in which the symbols in
        the Scheme formal parameter list FORMALS are bound to the
        Scheme values in the Python list VALS.  FORMALS has either of the
        formats allowed by the Evaluation.check_formals method.  If
        the last cdr in FORMALS is a null list (that is, if FORMALS is
        an ordinary Scheme list), then the number of formals must be the same
        as the number of VALS, and each symbol in FORMALS is bound to the
        corresponding value in VALS.  If the last cdr in FORMALS is a
        symbol, then the number of values in VALS  must be at least as large as
        the number of preceding ("normal") formal symbols, and the last
        formal symbol is bound to a Scheme list containing the remaining
        values in VALS (which may be 0)."""
        "*** YOUR CODE HERE ***"
        return EnvironFrame(self)

    def define(self, sym, val):
        """Define Scheme symbol SYM to have value VAL in SELF."""
        self.inner[sym] = val

class Evaluation:
    """An Evaluation represents the information needed to evaluate an
    expression: the expression and the environment in which it is to be
    evaluated.  The step method performs at least part of the evaluation of
    the expression, either leaving behind the final value, or else another
    intermediate expression and environment to be further evaluated."""

    def __init__(self, expr, env):
        """An evaluation of EXPR in the environment ENV."""
        self.expr = expr
        self.env = env
        self.value = None

    def set_value(self, value):
        """Set the value of SELF to VALUE, completing the evaluation."""
        assert value is not None
        self.expr = None
        self.value = value

    def set_expr(self, expr, env = None):
        """Replace SELF's expression with EXPR.  If ENV is non-null, replace
        the environment in which EXPR is being evaluated with ENV."""
        self.expr = expr
        if env is not None:
            self.env = env

    def evaluated(self):
        """True iff this evaluation is finished."""
        return self.value is not None

    def step(self):
        """Either complete SELF's computation, causing all remaining
        side effects and producing a value, or else partially perform the
        remaining computation, leaving SELF with an expression and environment
        that denote the remaining computation."""
        expr = self.expr
        if expr.symbolp():
            "*** YOUR CODE HERE ***"
            self.set_value(FALSE)
        elif expr.atomp():
            self.set_value(expr)
        elif not scm_listp(expr):
            raise SchemeError("malformed list: {0}".format(str(self)))
        else:
            op = expr.car
            if op.symbolp():
                Evaluation.SPECIAL_FORMS.get(op, Evaluation.do_call_form)(self)
            else:
                self.do_call_form()

    def full_eval(self, expr, env = None):
        """The value of EXPR when evaluated in environment ENV (SELF.env by
        default."""
        return Evaluation(expr, env or self.env).step_to_value()

    def step_to_value(self):
        """Perform evaluation steps on SELF until a value is reached."""
        while not self.evaluated():
            self.step()
        return self.value

    # Special forms.  Each of these methods is called when
    # SELF.expr apparently contains the kind of special form the method
    # handles.  It checks the syntactic validity of the form, and partially 
    # evaluates it, either leaving the final value or an expression
    # that carries out the rest of the computation.

    def do_quote_form(self):
        self.check_form(2, 2)
        self.set_value(self.expr.cdr.car)

    def do_lambda_form(self):
        self.check_form(3)
        self.check_formals(self.expr.cdr.car)
        "*** YOUR CODE HERE ***"
        self.set_value(FALSE)

    def do_if_form(self):
        self.check_form(4, 4)
        cond = self.full_eval(self.expr.cdr.car)
        "*** YOUR CODE HERE ***"
        self.set_expr(FALSE)
                        
  
    def do_and_form(self):
        self.check_form(1)

        if self.expr.length() == 1:
            self.set_value(TRUE)
            return

        "*** YOUR CODE HERE ***"
        self.set_expr(FALSE)

    def do_or_form(self):
        self.check_form(1)

        if self.expr.length() == 1:
            self.set_value(FALSE)
            return

        "*** YOUR CODE HERE ***"
        self.set_expr(FALSE)

    def do_cond_form(self):
        self.check_form(1)
        num_clauses = self.expr.length()
        for i in range(1, num_clauses):
            clause = self.expr.nth(i)
            self.check_form(1, expr = clause)
            if clause.car is self._ELSE_SYM and i == num_clauses-1:
                test = TRUE
                if clause.cdr.nullp():
                    raise SchemeError("badly formed else clause")
            else:
                "*** YOUR CODE HERE ***"
                test = FALSE
            if test:
                if clause.length() == 1:
                    self.set_value(test)
                elif clause.cdr.car is self._ARROW_SYM:
                    "*** YOUR CODE HERE ***"
                    self.set_expr(FALSE)
                else:
                    for i in range(1, clause.length() - 1):
                        self.full_eval(clause.nth(i))
                    self.set_expr(clause.nth(clause.length()-1))
                return
        self.set_value(UNSPEC)

    def do_set_bang_form(self):
        self.check_form(3, 3)
        "*** YOUR CODE HERE ***"
        self.set_value(UNSPEC)
        
    def do_define_form(self):
        self.check_form(3)
        target = self.expr.nth(1)
        if target.symbolp():
            self.check_form(3,3)
            "*** YOUR CODE HERE ***"
            self.set_value(UNSPEC)
        elif not target.pairp():
            raise SchemeError("bad argument to define")
        else:
            self.check_formals(target.cdr)
            "*** YOUR CODE HERE ***"
            self.set_value(UNSPEC)

    def do_begin_form(self):
        self.check_form(2)
        for k in range(1, self.expr.length()-1):
            self.full_eval(self.expr.nth(k))
        self.set_expr(self.expr.nth(self.expr.length()-1))

    def do_let_form(self):
        self.check_form(3)
        bindings = self.expr.cdr.car
        exprs = self.expr.cdr.cdr
        if not scm_listp(bindings):
            raise SchemeError("bad bindings list in let form")
        symbols = NULL
        vals = []
        "*** YOUR CODE HERE ***"
        let_frame = self.env.make_call_frame(symbols, vals)
        for i in range(0, exprs.length()-1):
            self.full_eval(exprs.car, let_frame)
            exprs = exprs.cdr
        self.set_expr(exprs.car, let_frame)

    # Extra credit
    def do_let_star_form(self):
        self.check_form(3)
        "*** YOUR CODE HERE ***"
        self.set_value(UNSPEC)

    def do_case_form(self):
        self.check_form(2)
        "*** YOUR CODE HERE ***"
        self.set_value(UNSPEC)

    # Symbols that are used in special forms.

    _AND_SYM = Symbol.string_to_symbol("and")
    _ARROW_SYM = Symbol.string_to_symbol("=>")
    _BEGIN_SYM = Symbol.string_to_symbol("begin")
    _CASE_SYM = Symbol.string_to_symbol("case")
    _COND_SYM = Symbol.string_to_symbol("cond")
    _DEFINE_SYM = Symbol.string_to_symbol("define")
    _ELSE_SYM = Symbol.string_to_symbol("else")
    _IF_SYM = Symbol.string_to_symbol("if")
    _LAMBDA_SYM = Symbol.string_to_symbol("lambda")
    _LET_SYM = Symbol.string_to_symbol("let")
    _LET_STAR_SYM = Symbol.string_to_symbol("let*")
    _OR_SYM = Symbol.string_to_symbol("or")
    _QUOTE_SYM = Symbol.string_to_symbol("quote")
    _SET_BANG_SYM = Symbol.string_to_symbol("set!")

    # Mapping of symbols that introduce special forms to the methods that
    # handle the forms.
    SPECIAL_FORMS = {
        _AND_SYM :     do_and_form,
        _BEGIN_SYM :   do_begin_form,
        _CASE_SYM :    do_case_form,
        _COND_SYM :    do_cond_form,
        _DEFINE_SYM :  do_define_form,
        _IF_SYM :      do_if_form,
        _LAMBDA_SYM :  do_lambda_form,
        _LET_SYM :     do_let_form,
        _LET_STAR_SYM: do_let_star_form,
        _OR_SYM :      do_or_form,
        _QUOTE_SYM  :  do_quote_form,
        _SET_BANG_SYM: do_set_bang_form,
    }

    # Function calls

    def do_call_form(self):
        self.check_form(1)
        op = self.full_eval(self.expr.car)
        "*** YOUR CODE HERE ***"
        op.apply_step([], self)

    # Utility methods for checking the structure of Scheme values that
    # represent programs.

    def check_form(self, min, max = None, expr = None):
        """Check EXPR (default SELF.expr) is a proper list whose length is
        at least MIN and no more than MAX (default: no maximum). Raises
        a SchemeError if this is not the case."""
        if expr is None:
            expr = self.expr
        if not scm_listp(expr):
            raise SchemeError("badly formed expression")
        L = expr.length()
        if L < min:
            raise SchemeError("too few operands in form")
        elif max is not None and L > max:
            raise SchemeError("too many operands in form")

    @staticmethod
    def check_formals(formal_list):
        """Check that FORMAL_LIST is a valid parameter list having either 
        the form (sym1 sym2 ... symn) or else (sym1 sym2 ... symn . symrest),
        where each symx is a distinct symbol."""
        "*** YOUR CODE HERE ***"
        pass

def scm_eval(sexpr):
    # To begin with, this function simply returns SEXPR unchanged, without
    # doing any evaluation.  This allows you to test your solution to
    # problem 1: the interpreter will just echo all the expressions in your
    # input when you type
    #    python3 scheme.py tests.scm
    # (or other file full of Scheme expressions).  When you are finished
    # with Problem 1, replace the return statement below with 
    #    return Evaluation(sexpr, the_global_environment).step_to_value()
    # which is what evaluation is supposed to do.

    return sexpr

def scm_apply(func, arg0, *other_args):
    """If OTHER_ARGS is empty, apply the function value FUNC to the argument 
    list in ARG0 (a Scheme list).  Otherwise, the values of ARG0 and all but
    the last value in OTHER_ARGS are first added (with scm_cons) to
    the beginning of the last argument in OTHER_ARGS (which must be 
    a Scheme list), and then passed to the value of FUNC."""
    if other_args:
        check_type(other_args[-1], scm_listp, len(other_args), 'apply')
        args = [arg0]
        for i in range(len(other_args)-1):
            args.append(other_args[i])
        rest = other_args[-1]
    else:
        check_type(arg0, scm_listp, 0, 'apply')
        args = []
        rest = arg0

    while not rest.nullp():
        args.append(rest.car)
        rest = rest.cdr
    
    evaluation = Evaluation(None, None)
    func.apply_step(args, evaluation)
    return evaluation.step_to_value()


def call_with_input_file(filename, proc):
    """Temporarily set the current input port to the file named by FILENAME,
    (a string) and call PROC.  Always restores the input port when done."""
    with scheme_open(filename) as inp:
        call_with_input_source(inp, proc)

def call_with_input_source(source, proc):
    """Temporarily set the current input port to read lines from the
    SOURCE (an iterator returning lines or a string).  Always restores
    the input port when done."""
    global input_port
    input_port0 = input_port
    try:
        input_port = Buffer(tokenize_lines(source))
        proc()
    finally:
        input_port = input_port0
    
def read_eval_print(prompt = None):
    """Read and evaluate from the current input port until the end of file.
    If PROMPT is not None, use it to prompt for input and print values of
    each expression."""
    while True:
        try:
            if prompt is not None:
                print(prompt, end = "")
            sys.stdout.flush()
            expr = scm_read()
            if expr is THE_EOF_OBJECT:
                return
            val = scm_eval(expr)
            if prompt is not None and val is not UNSPEC:
                scm_write(val)
                scm_newline()
        except SchemeError as exc:
            if not exc.args[0]:
                print("Error", file=sys.stderr)
            else:
                print("Error: {0}".format(exc.args[0]), file=sys.stderr)
            sys.stderr.flush()

def scm_read():
    def read_tail():
        """Assuming that input is positioned inside a Scheme list or pair,
        immediately before a final parenthesis or another item in the list,
        return the remainder of the list from that point.  Thus, returns
        (2 3) when positioned at the carat in "(1 ^ 2 3)", returns
        () when positioned at the carat in "(1 2 3 ^ )", and returns
        the pair (2 . 3) when positioned at the carat in (1 ^ 2 . 3)."""
        if input_port.current is None:
            raise SchemeError("unexpected EOF")
        syntax, val = input_port.current
        "*** YOUR CODE HERE ***"
        input_port.pop(); return NULL
        return Pair(first, rest)

    if input_port.current is None:
        return THE_EOF_OBJECT

    syntax, val = input_port.pop()

    if syntax == NUMERAL:
        return Number(val)
    elif syntax == BOOLEAN:
        return boolify(val)
    elif syntax == SYMBOL:
        return Symbol.string_to_symbol(val)
    elif syntax == "'":
        "*** YOUR CODE HERE ***"
        return FALSE
    elif syntax == "(":
        return read_tail()
    else:
        raise SchemeError("unexpected token: {0}".format(repr(val)))

def scm_load(sym):
    check_type(sym, scm_symbolp, 0, "load")
    call_with_input_file(str(sym), read_eval_print)
    return UNSPEC

##
## Initialization
##

_PRIMITIVES = (
    ("eqv?", scm_eqvp),
    ("eq?", scm_eqp),
    ("equal?", scm_equalp),
    ("atom?", scm_atomp),

    ("pair?", scm_pairp),
    ("null?", scm_nullp),
    ("list?", scm_listp),
    ("cons", scm_cons),
    ("car", scm_car),
    ("cdr", scm_cdr),
    ("length", scm_length),
    ("set-car!", scm_set_car),
    ("set-cdr!", scm_set_cdr),
    ("list", scm_list),
    ("append", scm_append),

    ("integer?", scm_integerp),
    ("+", scm_add),
    ("-", scm_sub),
    ("*", scm_mul),
    ("/", scm_div),
    ("quotient", scm_quo),
    ("modulo", scm_modulo),
    ("remainder", scm_remainder),
    ("floor", scm_floor),
    ("ceil", scm_ceil),
    ("<", scm_lt),
    (">", scm_gt),
    ("=", scm_eq),
    ("<=", scm_le),
    (">=", scm_ge),

    ("boolean?", scm_booleanp),
    ("not", scm_not),
    ("symbol?", scm_symbolp),

    ("write", scm_write),
    ("display", scm_display),
    ("newline", scm_newline),
    ("read", scm_read),
    ("load", scm_load),

    ("eval", scm_eval),
    ("apply", scm_apply),

    ("error", scm_error),
    (["exit", "bye"], scm_exit),

    ("word", sscm_word),
    ("first", sscm_first),
    (["bf", "butfirst"], sscm_butfirst),
    ("last", sscm_last),
    (["bl", "butlast"], sscm_butlast),
    (["sentence", "se"], sscm_sentence),

    (['forward', 'fd'], tscm_forward),
    (['backward', 'back', 'bk'], tscm_backward),
    (['right', 'rt'], tscm_right),
    (['left', 'lt'], tscm_left),
    ('circle', tscm_circle),
    (['setpos', 'setposition', 'goto'], tscm_setposition),
    (['seth', 'setheading'], tscm_setheading),
    (['penup', 'pu'], tscm_penup),
    (['pendown', 'pd'], tscm_pendown),
    (['showturtle', 'st'], tscm_showturtle),
    (['hideturtle', 'ht'], tscm_hideturtle),
    ('clear', tscm_clear),
    ('color', tscm_color),
    ('begin_fill', tscm_begin_fill),
    ('end_fill', tscm_end_fill),
    ('exitonclick', tscm_exitonclick),
    ('speed', tscm_speed),
)

def define_primitives(frame, bindings):
    """Enter each of the (name, function) bindings in BINDINGS into FRAME,
    an environment frame."""
    for names, func in bindings:
        if type(names) is str:
            names = (names,)
        for name in names:
            frame.define(Symbol.string_to_symbol(name),
                         PrimitiveFunction(func))

def create_global_environment():
    """Initialize the_global_environment to a fresh environment defining the
    predefined names."""
    global the_global_environment

    the_global_environment = EnvironFrame(None)
    
    # Uncomment the following line after you finish with Problem 4.
    # scm_load(Symbol.string_to_symbol(SCHEME_PRELUDE_FILE))
    define_primitives(the_global_environment, _PRIMITIVES)

input_port = None

@main
def run(*argv):
    global input_port

    if argv:
        try:
            input_file = open(argv[0])
        except IOError as exc:
            print("could not open {0}: {1}".format(argv[0], exc.args[0]),
                  file=sys.stderr)
            sys.exit(1)
    else:
        input_file = sys.stdin
        
    input_port = Buffer(tokenize_lines(input_file))
    create_global_environment()
    read_eval_print("scm> ")