def do_let_form(vals, env):
    """Evaluate a let form with parameters VALS in environment ENV."""
    check_form(vals, 2)
    bindings = vals[0]
    exprs = vals.second
    if not scheme_listp(bindings):
        raise SchemeError("bad bindings list in let form")

    # Add a frame containing bindings
    names, values = nil, nil
    "*** YOUR CODE HERE ***"
    new_env = env.make_call_frame(names, values)

    for key_val in bindings:
        key = scheme_car(key_val)
        val = scheme_car(scheme_cdr(key_val))

        val = scheme_eval(val, env)        
        new_env.bindings[key] = val

    # Evaluate all but the last expression after bindings, and return the last
    last = len(exprs)-1
    for i in range(0, last):
        scheme_eval(exprs[i], new_env)
    return exprs[last], new_env

def do_cond_form(vals, env):
    """Evaluate cond form with parameters VALS in environment ENV."""
    num_clauses = len(vals)
    for i, clause in enumerate(vals):
        check_form(clause, 1)
        if clause.first is else_sym:
            if i < num_clauses-1:
                raise SchemeError("else must be last")
            test = scheme_true
            if clause.second is nil:
                raise SchemeError("badly formed else clause")
        else:
            test = scheme_eval(clause.first, env)
        if test:
            "*** YOUR CODE HERE ***"
            while len(vals) > 0:
                if vals.first.first == intern('else'):
                    return (scheme_eval(vals.first.second.first, env), None)
                else:
                    condition = scheme_eval(vals.first.first, env)
                    if condition:
                        if len(vals.first) == 1:
                            return (condition, None)
                        elif len(vals.first) == 2:
                            return (scheme_eval(vals.first.second.first, env), None)
                        else:
                            return (scheme_eval(Pair('begin', vals.first.second), env), None)
                    else:
                        vals = vals.second
    return okay, None

def do_cond_form(vals, env):
    """Evaluate cond form with parameters VALS in environment ENV."""
    num_clauses = len(vals)
    for i, clause in enumerate(vals):
        check_form(clause, 1)
        if clause.first is else_sym:
            if i < num_clauses-1:
                raise SchemeError("else must be last")
            test = scheme_true
            if clause.second is nil:
                raise SchemeError("badly formed else clause")
        else:
            test = scheme_eval(clause.first, env)
        if test:
            "*** YOUR CODE HERE ***"
            if clause.second is nil:
                return test, None

            elif clause.second.length() == 1:
                expr = clause.second.first
            else:
                expr = Pair(intern('begin'), clause.second )
    
            return scheme_eval(expr, env), None

    return okay, None

def do_let_form(vals, env):
    """Evaluate a let form with parameters VALS in environment ENV."""
    check_form(vals, 2)
    bindings = vals[0]
    exprs = vals.second
    if not scheme_listp(bindings):
        raise SchemeError("bad bindings list in let form")

    # Add a frame containing bindings
    names, values = nil, nil
    "*** YOUR CODE HERE ***"    
    names_lst = []
    values_lst = []
    for val in bindings:
        if len(val) > 2:
            raise SchemeError("bad bindings")
        values_lst.append(scheme_eval(val[1], env))
        names_lst.append(val.first)
    new_env = env.make_call_frame(names_lst, values_lst)

    # Evaluate all but the last expression after bindings, and return the last
    last = len(exprs)-1
    for i in range(0, last):
        scheme_eval(exprs[i], new_env)
    return exprs[last], new_env

def do_begin_form(vals, env):
    """Evaluate begin form with parameters VALS in environment ENV."""
    check_form(vals, 0)
    if scheme_nullp(vals):
        return okay, None
    length = len(vals)
    for i in range(length - 1):
        scheme_eval(vals[i], env)
    return vals[length-1], env

def do_begin_form(vals, env):
    """Evaluate begin form with parameters VALS in environment ENV."""
    check_form(vals, 0)
    if scheme_nullp(vals):
        return okay, None
    "*** YOUR CODE HERE ***"
    for expr in range (len(vals)-1):
        scheme_eval(vals[expr],env)
    return vals[(len(vals)-1)],env

def do_if_form(vals, env):
    """Evaluate if form with parameters VALS in environment ENV."""
    check_form(vals, 2, 3)
    "*** YOUR CODE HERE ***"
    if scheme_eval(vals[0], env):
        return scheme_eval(vals[1],env), None
    elif len(vals) == 2:
        return okay, None
    return scheme_eval(vals[2],env), None

def scheme_eval(expr, env):
    """Evaluate Scheme expression EXPR in environment ENV. If ENV is None,
    simply returns EXPR as its value without further evaluation.
    >>> expr = read_line("(+ 2 2)")
    >>> expr
    Pair('+', Pair(2, Pair(2, nil)))
    >>> scheme_eval(expr, create_global_frame())
    scnum(4)
    """

    while env is not None:
        # Note: until extra-credit problem 22 is complete, env will
        # always be None on the second iteration of the loop, so that
        # the value of EXPR is returned at that point.
        print(expr,env)
        if env.parent!=None:
            print (env.bindings)
        if expr is None:
            raise SchemeError("Cannot evaluate an undefined expression.")

        # Evaluate Atoms
        if scheme_symbolp(expr):
            expr, env = env.lookup(expr).get_actual_value(), None
        elif scheme_atomp(expr):
            env = None

        # All non-atomic expressions are lists.
        elif not scheme_listp(expr):
            raise SchemeError("malformed list: {0}".format(str(expr)))
        else:
            first, rest = scheme_car(expr), scheme_cdr(expr)

            # Evaluate Combinations
            if (scheme_symbolp(first) # first might be unhashable
                and first in SPECIAL_FORMS):
                if proper_tail_recursion:
                    "*** YOUR CODE HERE ***"
                    expr, env = SPECIAL_FORMS[first](rest, env)
                else:
                    expr, env = SPECIAL_FORMS[first](rest, env)
                    expr, env = scheme_eval(expr, env), None



            else:
                procedure = scheme_eval(first, env)
                args = procedure.evaluate_arguments(rest, env)
                if proper_tail_recursion:
                    "*** YOUR CODE HERE ***"
                    expr, env = procedure.apply(args, env)
                else:
                    # UPDATED 4/14/2014 @ 19:08
                    expr = scheme_apply(procedure, args, env)
                    expr, env = scheme_apply(procedure, args, env), None

    return expr

def do_and_form(vals, env):
    """Evaluate short-circuited and with parameters VALS in environment ENV."""
    "*** YOUR CODE HERE ***"
    if len(vals) == 0:
        return (scheme_true, None)
    while len(vals) > 1:
        if not scheme_eval(vals.first, env):
            return (scheme_false, None)
        vals = vals.second
    return (scheme_eval(vals.first, env), None)

def do_begin_form(vals, env):
    """Evaluate begin form with parameters VALS in environment ENV."""
    check_form(vals, 0)
    if scheme_nullp(vals):
        return okay, None
    "*** YOUR CODE HERE ***"
    last = len(vals) - 1
    for i in range(0, last):
        scheme_eval(vals[i], env)
    return (vals[last],env)

def do_begin_form(vals, env):
    """Evaluate begin form with parameters VALS in environment ENV."""
    check_form(vals, 0)
    if scheme_nullp(vals):
        return okay, None
    "*** YOUR CODE HERE ***"
    last_one = vals[len(vals) - 1]
    for index in range(0, len(vals) - 1):
        scheme_eval(vals[index], env)
    return (scheme_eval(last_one, env), None)

def do_or_form(vals, env):
    """Evaluate short-circuited or with parameters VALS in environment ENV."""
    "*** YOUR CODE HERE ***"
    if len(vals) == 0:
        return (scheme_false, None)
    while len(vals) > 1:
        cond = scheme_eval(vals.first, env)
        if cond:
            return (cond, None)
        vals = vals.second
    return (scheme_eval(vals.first, env), None)

def do_or_form(vals, env):
    """Evaluate short-circuited or with parameters VALS in environment ENV."""
    "*** YOUR CODE HERE ***"

    if len(vals) == 0:
        return scheme_false, None
    for op in range(0, len(vals) - 1):
        x = scheme_eval(vals[op], env)
        if x:
            return x, None
    return scheme_eval(vals[len(vals) - 1], env), None

def do_if_form(vals, env):
    """Evaluate if form with parameters VALS in environment ENV."""
    check_form(vals, 2, 3)
    "*** YOUR CODE HERE ***"
    if len(vals) == 2:
        if (scheme_eval(vals.first, env)):
            return (scheme_eval(vals.second.first, env), None)
        else:
            return (okay, None)
    else:
        if (scheme_eval(vals.first, env)):
            return (scheme_eval(vals.second.first, env), None)
        else:
            return (scheme_eval(vals.second.second.first, env), None)

def _short_circuit_list_eval(list, env, empty_list_return_val, predicate):

    def _is_last_element(index):
        return index == list.length()

    if list.length() == 0:
        return empty_list_return_val, None

    for index, expr in enumerate(list, 1):
        if _is_last_element(index):
            return scheme_eval(expr, env), None

        result = scheme_eval(expr, env)
        if predicate(result):
            return result, None

def read_eval_print_loop(next_line, env, quiet=False, startup=False,
                         interactive=False, load_files=()):
    """Read and evaluate input until an end of file or keyboard interrupt."""
    if startup:
        for filename in load_files:
            scheme_load(scstr(filename), True, env)
    while True:
        try:
            src = next_line()
            while src.more_on_line:
                expression = scheme_read(src)
                result = scheme_eval(expression, env)
                if not quiet and result is not None:
                    scheme_print(result)
        except (SchemeError, SyntaxError, ValueError, RuntimeError) as err:
            if (isinstance(err, RuntimeError) and
                'maximum recursion depth exceeded' not in err.args[0]):
                raise
            print("Error:", err)
        except KeyboardInterrupt:  # <Control>-C
            if not startup:
                raise
            print("\nKeyboardInterrupt")
            if not interactive:
                return
        except EOFError:  # <Control>-D, etc.
            return

def do_define_form(vals, env):
    """Evaluate a define form with parameters VALS in environment ENV."""
    check_form(vals, 2)
    target = vals[0]
    if scheme_symbolp(target):
        check_form(vals, 2, 2)
        "*** YOUR CODE HERE ***"
        env.define(target, scheme_eval(vals[1], env))
        return (target, None)
    elif scheme_pairp(target):
        "*** YOUR CODE HERE ***"
        func = target[0]
        if scheme_symbolp(func):
            formals = target.second
            if len(vals) > 2:
                body = Pair('begin', vals.second)
            else:
                body = vals.second.first
            procedure = LambdaProcedure(formals, body, env)
            env.define(func, procedure)
            return (func, None)
        else:
            raise SchemeError("QA9")
    else:
        raise SchemeError("bad argument to define")

 def apply(self, args, env):
     if proper_tail_recursion:
         # Implemented in Question 22.
         
         return self.body, self.env.make_call_frame(self.formals, args)
     else:
         return scheme_eval(self.body, self.env.make_call_frame(self.formals, args)), None

def do_if_form(vals, env):
    """Evaluate if form with parameters VALS in environment ENV."""
    check_form(vals, 2, 3)
    if bool(scheme_eval(vals[0], env)):
        return vals[1], env
    else:
        return (okay, None) if len(vals) is 2 else (vals[2], env) 

def do_define_form(vals, env):
    """Evaluate a define form with parameters VALS in environment ENV."""
    check_form(vals, 2)
    target = vals[0]
    

    if scheme_symbolp(target):
        check_form(vals, 2, 2)
        
        "*** YOUR CODE HERE ***"

        # this took me a while to understand. the expression is entirly evaluated.
        # only the result is stored in the current environment
        expr = scheme_eval( vals.cdr().car(), env )
        env.bindings[target] = expr

        return (target, None)

    elif scheme_pairp(target):
        "*** YOUR CODE HERE ***"

        function_name = scheme_car( target )
        function_args = scheme_cdr( target )
        function_body = vals.second

        if scheme_numberp( function_name ):
            raise SchemeError("function name can't be a number")

        lambda_proc, tmp = do_lambda_form( Pair(function_args, function_body), env )
        env.bindings[ function_name ] = lambda_proc

        return function_name, None

    else:
        raise SchemeError("bad argument to define")