[sicpelago] / scheme.py

"""This module implements the core Scheme interpreter functions, including the
eval/apply mutual recurrence, environment model, and read-eval-print loop.
"""

if __name__ == '__main__':
    __path__ = ["."]

from .scheme_primitives import *
from .scheme_reader import *
from .ucb import main, trace

import itertools

##############
# Eval/Apply #
##############

def scheme_eval(expr, env):
    """Evaluate Scheme expression EXPR in environment ENV.

    >>> expr = read_line("(+ 2 2)")
    >>> expr
    Pair('+', Pair(2, Pair(2, nil)))
    >>> scheme_eval(expr, create_global_frame())
    4
    """
    if expr is None:
        raise SchemeError("Cannot evaluate an undefined expression.")

    # Evaluate Atoms
    if scheme_symbolp(expr):
        return env.lookup(expr)
    elif scheme_atomp(expr) or scheme_stringp(expr) or expr is okay:
        return expr

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

    procedure = scheme_eval(first, env)

    # Evaluate Combinations
    if isinstance(procedure, SpecialForm):
        return procedure.impl(rest, env)
    else:
        args = rest.map(lambda operand: scheme_eval(operand, env))
        return scheme_apply(procedure, args, env)


def scheme_apply(procedure, args, env):
    """Apply Scheme PROCEDURE to argument values ARGS in environment ENV."""
    if isinstance(procedure, PrimitiveProcedure):
        return apply_primitive(procedure, args, env)
    elif isinstance(procedure, LambdaProcedure):
        frame = procedure.env.make_call_frame(procedure.formals, args)
        return scheme_eval(do_begin_form(procedure.body, frame), frame)
    elif isinstance(procedure, MuProcedure):
        raise SchemeError("not part of this project")
    else:
        raise SchemeError("Cannot call {0}".format(str(procedure)))

def apply_primitive(procedure, args, env):
    """Apply PrimitiveProcedure PROCEDURE to a Scheme list of ARGS in ENV.

    >>> env = create_global_frame()
    >>> plus = env.bindings["+"]
    >>> twos = Pair(2, Pair(2, nil))
    >>> apply_primitive(plus, twos, env)
    4
    """
    if procedure.use_env:
        args = itertools.chain(args, (env,))
    try:
        return procedure.fn(*args)
    except TypeError:
        raise SchemeError("invalid call to " + (procedure.name or str(procedure)))

################
# Environments #
################

class Frame:
    """An environment frame binds Scheme symbols to Scheme values."""

    def __init__(self, parent):
        """An empty frame with a PARENT frame (that may be None)."""
        self.bindings = {}
        self.parent = parent

    def __repr__(self):
        if self.parent is None:
            return "<Global Frame>"
        else:
            s = sorted('{0}: {1}'.format(k,v) for k,v in self.bindings.items())
            return "<{{{0}}} -> {1}>".format(', '.join(s), repr(self.parent))

    def lookup(self, symbol):
        """Return the value bound to SYMBOL.  Errors if SYMBOL is not found."""
        if symbol in self.bindings:
            return self.bindings[symbol]
        if self.parent is not None:
            return self.parent.lookup(symbol)
        raise SchemeError("unknown identifier: {0}".format(str(symbol)))


    def global_frame(self):
        """The global environment at the root of the parent chain."""
        e = self
        while e.parent is not None:
            e = e.parent
        return e

    def make_call_frame(self, formals, vals):
        """Return a new local frame whose parent is SELF, in which the symbols
        in the Scheme formal parameter list FORMALS are bound to the Scheme
        values in the Scheme value list VALS. Raise an error if too many or too
        few arguments are given.

        >>> env = create_global_frame()
        >>> formals, vals = read_line("(a b c)"), read_line("(1 2 3)")
        >>> env.make_call_frame(formals, vals)
        <{a: 1, b: 2, c: 3} -> <Global Frame>>
        """
        frame = Frame(self)
        while formals != nil:
            if not isinstance(formals, Pair):
                frame.bindings[formals] = vals
                vals = None
                break
            frame.bindings[formals.first] = vals.first
            formals = formals.second
            vals = vals.second
        return frame

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


def _force_promise(self):
    if self.value is None:
        self.value = scheme_eval(self.body, self.env)
    return self.value

Promise.force = _force_promise

#################
# Special forms #
#################

class SpecialForm:
    def __init__(self, name, impl):
        self.impl = impl
        self.name = name

    def __str__(self):
        return '#[form ' + self.name + ']'

class LogicForm(SpecialForm):
    def __init__(self, name, impl):
        super().__init__(name, lambda vals, env: scheme_eval(impl(vals, env), env))

def do_lambda_form(vals, env):
    """Evaluate a lambda form with parameters VALS in environment ENV."""
    check_form(vals, 2)
    formals = vals.first
    check_formals(formals)
    return LambdaProcedure(formals, vals.second, env)

def do_mu_form(vals, env):
    """Evaluate a mu form with parameters VALS."""
    check_form(vals, 2)
    formals = vals[0]
    check_formals(formals)
    "*** YOUR CODE HERE ***"

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)
        value = scheme_eval(vals[1], env)
    elif isinstance(target, Pair) and scheme_symbolp(target.first):
        (target, args) = (target.first, target.second)
        value = do_lambda_form(Pair(args, vals.second), env)
    else:
        raise SchemeError("bad argument to define")
    if target.startswith('#'):
        raise SchemeError("can't override builtins starting with '#'")
    env.define(target, value)
    return target

def do_quote_form(vals, env):
    """Evaluate a quote form with parameters VALS."""
    check_form(vals, 1, 1)
    return vals[0]


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
    while bindings is not nil:
        next_pair = bindings.first
        check_form(next_pair, 2, 2)
        if not scheme_symbolp(next_pair[0]):
            raise SchemeError("bad name in bindings list in let")
        names = Pair(next_pair[0], names)
        values = Pair(scheme_eval(next_pair[1], env), values)
        bindings = bindings.second
    new_env = env.make_call_frame(names, values)

    # 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_delay_form(vals, env):
    check_form(vals, 1, 1)
    return Promise(vals[0], env)


def do_cons_stream_form(vals, env):
    check_form(vals, 2, 2)
    first = scheme_eval(vals[0], env)
    rest = do_delay_form(vals.second, env)
    return Pair(first, rest)


#########################
# Logical Special Forms #
#########################

def do_if_form(vals, env):
    """Evaluate if form with parameters VALS in environment ENV."""
    check_form(vals, 2, 3)
    if scheme_true(scheme_eval(vals[0], env)):
        return vals[1]
    elif len(vals) == 3:
        return vals[2]
    else:
        return False

def do_and_form(vals, env):
    """Evaluate short-circuited and with parameters VALS in environment ENV."""
    check_form(vals, 0)
    if vals is nil:
        return True
    first = scheme_eval(vals.first, env)
    if scheme_false(first) or vals.second is nil:
        return quote(first)
    return do_and_form(vals.second, env)

def quote(value):
    """Return a Scheme expression quoting the Scheme VALUE.

    >>> s = quote('hello')
    >>> print(s)
    (quote hello)
    >>> scheme_eval(s, Frame(None))  # "hello" is undefined in this frame.
    'hello'
    """
    return Pair("quote", Pair(value, nil))

def do_or_form(vals, env):
    """Evaluate short-circuited or with parameters VALS in environment ENV."""
    check_form(vals, 0)
    if vals is nil:
        return False
    first = scheme_eval(vals.first, env)
    if scheme_true(first):
        return quote(first)
    return do_or_form(vals.second, 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 == "else":
            if i < num_clauses-1:
                raise SchemeError("else must be last")
            test = True
            if clause.second is nil:
                raise SchemeError("badly formed else clause")
        else:
            test = scheme_eval(clause.first, env)
        if scheme_true(test):
            if clause.second is nil:
                return quote(test)
            return Pair("begin", clause.second)
    return okay

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

LOGIC_FORMS = {
        "and": do_and_form,
        "or": do_or_form,
        "if": do_if_form,
        "cond": do_cond_form,
        "begin": do_begin_form,
        }

# Utility methods for checking the structure of Scheme programs

def check_form(expr, min, max = 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 not scheme_listp(expr):
        raise SchemeError("badly formed expression: " + str(expr))
    length = len(expr)
    if length < min:
        raise SchemeError("too few operands in form: " + str(expr))
    elif max is not None and length > max:
        raise SchemeError("too many operands in form: " + str(expr))

def check_formals(formals):
    """Check that FORMALS is a valid parameter list, a Scheme list of symbols
    in which each symbol is distinct. Raise a SchemeError if the list of formals
    is not a well-formed list of symbols or if any symbol is repeated.

    >>> check_formals(read_line("(a b c)"))
    """
    if scheme_symbolp(formals):
        # "Dotted-tail notation" with no positional params.
        return

    idents = set()
    original_formals = formals
    while formals is not nil:
        if not isinstance(formals, Pair) or not scheme_symbolp(formals.first):
            raise SchemeError("invalid argument list: " + str(original_formals))
        if formals.first in idents:
            raise SchemeError("parameter '" + formals.first + "' appears multiple times")
        idents.add(formals.first)
        if scheme_symbolp(formals.second):
            if formals.second in idents:
                raise SchemeError("parameter '" + formals.second + "' appears multiple times")
            return
        formals = formals.second

##################
# Tail Recursion #
##################

def scheme_optimized_eval(expr, env):
    """Evaluate Scheme expression EXPR in environment ENV."""
    while True:
        if expr is None:
            raise SchemeError("Cannot evaluate an undefined expression.")

        # Evaluate Atoms
        if scheme_symbolp(expr):
            return env.lookup(expr)
        elif scheme_atomp(expr) or scheme_stringp(expr) or expr is okay:
            return expr

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

        # Evaluate Combinations
        if (scheme_symbolp(first) # first might be unhashable
            and first in LOGIC_FORMS):
            "*** YOUR CODE HERE ***"
        elif first == "lambda":
            return do_lambda_form(rest, env)
        elif first == "mu":
            return do_mu_form(rest)
        elif first == "define":
            return do_define_form(rest, env)
        elif first == "quote":
            return do_quote_form(rest)
        elif first == "let":
            "*** YOUR CODE HERE ***"
        else:
            "*** YOUR CODE HERE ***"

################################################################
# Uncomment the following line to apply tail call optimization #
################################################################
# scheme_eval = scheme_optimized_eval


################
# Input/Output #
################

def scheme_format(value):
    if value is True:
        return "#t"
    if value is False:
        return "#f"
    return str(value)

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(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:
                    print(scheme_format(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 scheme_load(*args):
    """Load a Scheme source file. ARGS should be of the form (SYM, ENV) or (SYM,
    QUIET, ENV). The file named SYM is loaded in environment ENV, with verbosity
    determined by QUIET (default true)."""
    if not (2 <= len(args) <= 3):
        vals = args[:-1]
        raise SchemeError("wrong number of arguments to load: {0}".format(vals))
    sym = args[0]
    quiet = args[1] if len(args) > 2 else True
    env = args[-1]
    if (scheme_stringp(sym)):
        sym = eval(sym)
    check_type(sym, scheme_symbolp, 0, "load")
    with scheme_open(sym) as infile:
        lines = infile.readlines()
    args = (lines, None) if quiet else (lines,)
    def next_line():
        return buffer_lines(*args)
    read_eval_print_loop(next_line, env.global_frame(), quiet=quiet)
    return okay

def scheme_open(filename):
    """If either FILENAME or FILENAME.scm is the name of a valid file,
    return a Python file opened to it. Otherwise, raise an error."""
    try:
        return open(filename)
    except IOError as exc:
        if filename.endswith('.scm'):
            raise SchemeError(str(exc))
    try:
        return open(filename + '.scm')
    except IOError as exc:
        raise SchemeError(str(exc))

def create_global_frame():
    """Initialize and return a single-frame environment with built-in names."""
    env = Frame(None)
    env.define("nil", nil)
    env.define("eval", PrimitiveProcedure(scheme_eval, True))
    env.define("apply", PrimitiveProcedure(scheme_apply, True))
    env.define("load", PrimitiveProcedure(scheme_load, True))

    add_primitives(env)

    env.define("define", SpecialForm("define", do_define_form))
    env.define("lambda", SpecialForm("lambda", do_lambda_form))
    env.define("quote", SpecialForm("quote", do_quote_form))
    env.define("let", SpecialForm("let", lambda args, env: scheme_eval(*do_let_form(args, env))))

    env.define("delay", SpecialForm("delay", do_delay_form))
    env.define("cons-stream", SpecialForm("cons-stream", do_cons_stream_form))

    env.define("if", LogicForm("if", do_if_form))
    env.define("cond", LogicForm("cond", do_cond_form))
    env.define("or", LogicForm("or", do_or_form))
    env.define("and", LogicForm("and", do_and_form))
    env.define("begin", LogicForm("begin", do_begin_form))

    return env

@main
def run(*argv):
    next_line = buffer_input
    interactive = True
    load_files = ()
    if argv:
        try:
            filename = argv[0]
            if filename == '-load':
                load_files = argv[1:]
            else:
                input_file = open(argv[0])
                lines = input_file.readlines()
                def next_line():
                    return buffer_lines(lines)
                interactive = False
        except IOError as err:
            print(err)
            sys.exit(1)
    read_eval_print_loop(next_line, create_global_frame(), startup=True,
                         interactive=interactive, load_files=load_files)