"""Stutter

An interpreter for the stutter language (a subset of the Scheme programming
language) using prefix-order call syntax.  Operator expressions must be simple
operator names or symbols.  Operand expressions are separated by commas.

Examples:
    stutter> (* 1 2 3)
    6
    stutter> (+)
    0
    stutter> (+ 2 (/ 4 8))
    2.5
    stutter> +
    SyntaxError: unexpected +
    stutter> (/ 5)
    TypeError: / requires exactly 2 arguments
    stutter> (/ 1 0)
    ZeroDivisionError: division by zero
    stutter> ^DCalculation completed.
"""

from ucb import trace, main, interact
from functools import reduce
from operator import mul, eq, gt, lt
from pair import EmptyList, Pair, make_stutter_list, append_stutter_lists
try:
    import readline  # Enables access to previous expressions in the REPL
except ImportError:
    pass # Readline is not necessary; it's just a convenience

def read_eval_print_loop():
    """Run a read-eval-print loop for stutterulator."""
    while True:
        try:
            expression_tree = stutter_parse(input('stutter> '))
            print(stutter_eval(expression_tree))
        except (SyntaxError, TypeError, ZeroDivisionError) as err:
            print(type(err).__name__ + ':', err)
        except (KeyboardInterrupt, EOFError):  # <Control>-D, etc.
            print('Calculation completed.')
            return

# Eval & Apply

class Exp(object):
    """A call expression in Stutter.
    
    >>> Exp('+', [1, 2])
    Exp('+', [1, 2])
    >>> str(Exp('+', [1, Exp('*', [2, 3])]))
    '(+ 1 (* 2 3))'
    """

    def __init__(self, operator, operands):
        self.operator = operator
        self.operands = operands

    def __repr__(self):
        return 'Exp({0}, {1})'.format(repr(self.operator), repr(self.operands))

    def __str__(self):
        operand_strs = ' '.join(map(str, self.operands))
        return '({0} {1})'.format(self.operator, operand_strs)

class LambdaExp(object):
    """A lambda expression in Stutter.

    >>> LambdaExp(['x', 'y'], Exp('*', [2, Exp('+', ['x', 'y'])]))
    LambdaExp(['x', 'y'], Exp('*', [2, Exp('+', ['x', 'y'])]))
    >>> str(LambdaExp(['x', 'y'], Exp('*', [2, Exp('+', ['x', 'y'])])))
    '(lambda (x y) (* 2 (+ x y)))'
    """

    def __init__(self, arguments, body):
        self.args = arguments
        self.body = body

    def __repr__(self):
        return 'LambdaExp({0}, {1})'.format(repr(self.args), repr(self.body))

    def __str__(self):
        args_strs = ' '.join(map(str, self.args))
        return '(lambda ({0}) {1})'.format(args_strs, str(self.body))


def substitute(exp, param_vals, bound):
    """Return the equivalent expression with each name in params replaced by
    the corresponding value given in args.

    exp -- the expression to do the replacement in
    param_vals -- dictionary mapping names to values for replacement
    bound -- these are variable names that should NOT be replaced (this
    is for handling cases like:
        ((lambda (x y)
           ((lambda (x) (+ x y))
            (* x y)))
         5 8)
    Which is equivalent to:
        ((lambda (x) (+ x 8)) (* 5 8))
    AND NOT: 
        ((lambda (5) (+ 5 8)) (* 5 8))

    >>> substitute(Exp('+', ['x', 'y']), {'x': 5, 'y': 6}, [])
    Exp('+', [5, 6])
    """
    if type(exp) == LambdaExp:
        new_body = substitute(exp.body, params_vals, bound + exp.args)
        return LambdaExp(exp.args, new_body)
    elif type(exp) == Exp:
        new_operator = substitute(exp.operator, param_vals, bound)
        new_operands = [substitute(e, param_vals, bound) for e in exp.operands]
        return Exp(new_operator, new_operands)
    elif exp in param_vals and exp not in bound:
        return param_vals[exp]
    else:
        return exp


def stutter_eval(exp):
    """Evaluate a Calculator expression.

    >>> stutter_eval(Exp('+', [2, Exp('*', [4, 6])]))
    26
    """
    if type(exp) in (int, float) or exp in ('#t', '#f'):
        return exp
    if type(exp) == Exp:
        # handle special forms first, then normal function calls in the else case
        if exp.operator == "if":
            return handle_if(exp)
        else:
            # normal function call
            arguments = list(map(stutter_eval, exp.operands))
            return stutter_apply(exp.operator, arguments)

def handle_if(exp):
    truth = stutter_eval(exp.operands[0])
    if truth != "#f":
        return stutter_eval(exp.operands[1])
    else:
        return stutter_eval(exp.operands[2])

def stutter_apply(operator, args):
    """Apply the named operator to a list of args.
    
    >>> stutter_apply('+', [1, 2, 3])
    6
    >>> stutter_apply('-', [10, 1, 2, 3])
    4
    >>> stutter_apply('*', [])
    1
    >>> stutter_apply('/', [40, 5])
    8.0
    """
    if type(operator) == LambdaExp:
        param_vals = {p : v for p, v in zip(operator.args, args)}
        equiv_exp = substitute(operator.body, param_vals, [])
        return stutter_eval(equiv_exp)
    if operator == '+':
        return sum(args)
    if operator == '-':
        if len(args) == 0:
            raise TypeError(operator + 'requires at least 1 argument')
        if len(args) == 1:
            return -args[0]
        return sum(args[:1] + [-arg for arg in args[1:]])
    if operator == '*':
        return reduce(mul, args, 1)
    if operator == '/':
        if len(args) != 2:
            raise TypeError(operator + ' requires exactly 2 arguments')
        numer, denom = args
        return numer/denom
    if operator == '=':
        if len(args) == 0:
            raise TypeError(operator + ' requires at least 1 argument')
        for i in range(len(args) - 1):
            if not args[i] == args[i+1]:
                return "#f"
        return "#t"
    if operator == '<':
        if len(args) == 0:
            raise TypeError(operator + ' requires at least 1 arugment')
        for i in range(len(args) - 1):
            if not args[i] < args[i+1]:
                return "#f"
        return "#t"
    if operator == '>':
        if len(args) == 0:
            raise TypeError(operator + ' requires at least 1 argument')
        for i in range(len(args) - 1):
            if not args[i] > args[i+1]:
                return "#f"
        return "#t"
    if operator == 'cons':
        if len(args) != 2:
            raise TypeError(operator + ' requires exactly 2 arguments')
        car, cdr = args
        return Pair(car, cdr)
    if operator == 'list':
        return make_stutter_list(args)
    if operator == 'append':
        return append_stutter_lists(args)

# Parsing

def stutter_parse(line):
    """Parse a line of stutter input and return an expression tree."""
    tokens = tokenize(line)
    expression_tree = analyze(tokens)
    if len(tokens) > 0:
        raise SyntaxError('Extra token(s): ' + ' '.join(tokens))
    return expression_tree

def tokenize(line):
    """Convert a string into a list of tokens.
    
    >>> tokenize('(+ 2 (* 4 6))')
    ['(', '+', '2', '(', '*', '4', '6', ')', ')']
    """
    spaced = line.replace('(',' ( ').replace(')',' ) ')
    return spaced.strip().split()

known_operators = ['+', '-', '*', '/', 'cons', 'list', 'append']

def analyze(tokens):
    """Create a tree of nested lists from a sequence of tokens.

    Operand expressions can be separated by commas, spaces, or both.
    
    >>> analyze(tokenize('(+ 2 (* 4 6))'))
    Exp('+', [2, Exp('*', [4, 6])])
    >>> analyze(tokenize('(* (+ 2 (* 4 6)) (+ 3 5))'))
    Exp('*', [Exp('+', [2, Exp('*', [4, 6])]), Exp('+', [3, 5])])
    >>> analyze(tokenize('(lambda (x y) (+ x y))'))
    LambdaExp(['x', 'y'], Exp('+', ['x', 'y']))
    """
    assert_non_empty(tokens)
    token = analyze_token(tokens.pop(0))
    if token == '(':
        if len(tokens) == 0 or tokens[-1] != ')':
            raise SyntaxError('unmatched open parenthesis')
        token = analyze(tokens)
        if token == 'lambda':
            if tokens.pop(0) != '(':
                raise SyntaxError('malformed lambda')
            params = []
            while len(tokens) > 0 and tokens[0] != ')':
                params.append(tokens.pop(0))
            if len(tokens) == 0:
                raise SyntaxError('malformed lambda')
            tokens.pop(0) # Remove )
            body = analyze(tokens)
            tokens.pop(0) # Remove )
            return LambdaExp(params, body)
        return Exp(token, analyze_operands(tokens))
    else:
        return token

def analyze_operands(tokens):
    """Analyze a sequence of comma-separated operands."""
    assert_non_empty(tokens)
    operands = []
    while tokens[0] != ')':
        operands.append(analyze(tokens))
        assert_non_empty(tokens)
    tokens.pop(0)  # Remove )
    return operands

def assert_non_empty(tokens):
    """Raise an exception if tokens is empty."""
    if len(tokens) == 0:
        raise SyntaxError('unexpected end of line')

def analyze_token(token):
    """Return the value of token if it can be analyzed as a number, or token.
    
    >>> analyze_token('12')
    12
    >>> analyze_token('7.5')
    7.5
    >>> analyze_token('+')
    '+'
    """
    try:
        return int(token)
    except (TypeError, ValueError):
        try:
            return float(token)
        except (TypeError, ValueError):
            return token

@main
def run():
    read_eval_print_loop()