A quick Scheme implementation in Python, as a programming exercise

scheme.py

from functools import wraps
from collections import namedtuple
from collections.abc import MutableMapping
import string
import operator
import sys
import numbers

class Parser(object):
    __slots__ = ('parse',)

    def __init__(self, parse):
        self.parse = parse

    def run(self, input):
        result = self.parse(input, 0)
        if result is None:
            raise ValueError('Parse error')
        elif result[1] != len(input):
            raise ValueError('Incomplete parse, residue: {0!r}'.format(input[result[1]:]))
        else:
            return result[0]

    def __truediv__(self, other_parser):
        this_parse = self.parse
        other_parse = other_parser.parse
        def sub_parse(source, index):
            left_try = this_parse(source, index)
            if left_try is None:
                return other_parse(source, index)
            else:
                return left_try
        return Parser(sub_parse)

    def repeat(self, minimum_entries=0):
        this_parse = self.parse
        def sub_parse(source, index):
            entries = []
            while True:
                parse_result = this_parse(source, index)
                if parse_result is None:
                    if len(entries) >= minimum_entries:
                        return entries, index
                    else:
                        return None
                value, index = parse_result
                entries.append(value)
        return Parser(sub_parse)

    def optional(self, default=None):
        this_parse = self.parse
        def sub_parse(source, index):
            base_result = this_parse(source, index)
            if base_result is None:
                return default, index
            else:
                return base_result
        return Parser(sub_parse)

    @classmethod
    def zero(cls):
        return cls(lambda source, index: None)

    @classmethod
    def pure(cls, value):
        return cls(lambda source, index: (value, index))

    @classmethod
    def dot(cls):
        return cls(lambda source, index: (source[index], index + 1)
                                            if index < len(source)
                                            else None)

    @classmethod
    def eof(cls):
        return cls(lambda source, index: () if index == len(source) else None)

    def map(self, fn):
        this_parse = self.parse
        def mapped_parse(source, index):
            parse_result = this_parse(source, index)
            if parse_result is None:
                return None
            else:
                return fn(parse_result[0]), parse_result[1]
        return Parser(mapped_parse)

    def peek(self):
        this_parse = self.parse
        def peeked_parse(source, index):
            parse_result = this_parse(source, index)
            if parse_result is None:
                return None
            else:
                return parse_result[0], index
        return Parser(peeked_parse)

    def filter(self, fn):
        this_parse = self.parse
        def filtered_parse(source, index):
            parse_result = this_parse(source, index)
            if parse_result is None:
                return None
            elif not fn(parse_result[0]):
                return None
            else:
                return parse_result
        return Parser(filtered_parse)

    @classmethod
    def char(cls, characters):
        return cls.dot().filter(lambda c: c in characters)

    @classmethod
    def span(cls, characters, minimum_length=0):
        def spanner(source, index):
            base = index
            limit = len(source)
            while index < limit and source[index] in characters:
                index += 1
            if index - base >= minimum_length:
                return source[base:index], index
            else:
                return None
        return Parser(spanner)

    @classmethod
    def unspan(cls, characters, minimum_length=0):
        def spanner(source, index):
            base = index
            limit = len(source)
            while index < limit and source[index] not in characters:
                index += 1
            if index - base >= minimum_length:
                return source[base:index], index
            else:
                return None
        return Parser(spanner)

    @classmethod
    def literal(cls, string, space=None):
        def getter(source, index):
            end = index + len(string)
            if source[index:end] == string:
                return string, end
            else:
                return None
        parser = Parser(getter)
        if space is not None:
            parser <<= space
        return parser

    def __rshift__(self, other_parser):
        this_parse = self.parse
        other_parse = other_parser.parse
        def compound_parser(source, index):
            result_one = this_parse(source, index)
            if result_one is None:
                return None
            index = result_one[1]
            return other_parse(source, index)
        return Parser(compound_parser)

    def __lshift__(self, other_parser):
        this_parse = self.parse
        other_parse = other_parser.parse
        def compound_parser(source, index):
            result_one = this_parse(source, index)
            if result_one is None:
                return None
            index = result_one[1]
            result_two = other_parse(source, index)
            if result_two is None:
                return None
            return result_one[0], result_two[1]
        return Parser(compound_parser)

    @classmethod
    def forward(cls, getter):
        def parse(source, index):
            actual_parser = getter()
            return actual_parser.parse(source, index)
        return Parser(parse)

def parser(fn):
    def generator(source, index):
        genny = fn()
        try:
            sub_parser = next(genny)
            while True:
                parse_result = sub_parser.parse(source, index)
                if parse_result is None:
                    return None
                value, index = parse_result
                sub_parser = genny.send(value)
        except StopIteration as e:
            return e.value, index
    return Parser(generator)


@parser
def comment():
    yield Parser.char(';')
    yield Parser.unspan('\n')
    yield Parser.char('\n').optional()

whitespace = Parser.char(' \t\n')

space = (comment / whitespace).repeat()

symbol_characters = string.ascii_letters + string.digits + '_+-*/=?!~<>\''

atom = ((Parser.span('0123456789', 1).map(int) << space) /
        (Parser.span(symbol_characters, 1).map(sys.intern) << space) /
        (Parser.literal('#t', space) >> Parser.pure(True)) /
        (Parser.literal('#f', space) >> Parser.pure(False)))

@parser
def lst():
    yield Parser.char('(')
    yield space
    elements = yield sexp.repeat()
    yield Parser.char(')')
    yield space
    return elements

@parser
def quotation():
    yield Parser.char("'")
    yield space
    value = yield sexp
    return ['quote', value]

sexp = quotation / atom / lst


TRACE = False

class Context(MutableMapping):
    def __init__(self, parent):
        self.parent = parent
        self.override = {}

    def __getitem__(self, key):
        if key in self.override:
            return self.override[key]
        else:
            return self.parent[key]

    def __setitem__(self, key, value):
        self.override[key] = value

    def __delitem__(self, key):
        del self.override[key]

    def keys(self):
        keyset = set(self.override.keys())
        keyset.update(self.parent.keys())
        return keyset

    def __iter__(self):
        return iter(self.keys())

    def __len__(self):
        return len(self.keys())

    def set_bang(self, key, value):
        if key in self.override:
            self.override[key] = value
        else:
            self.parent.set_bang(key, value)

def evaluate(value, context):
    if value is None:
        return None
    if isinstance(value, int):
        return value
    if isinstance(value, str):
        return context[value]
    if isinstance(value, list):
        callee = value[0]
        if callee == 'lambda':
            args = value[1]
            body = value[2]
            def lambda_expr(*arguments):
                new_context = Context(context)
                for name, argument in zip(args, arguments):
                    new_context[name] = argument
                return evaluate(body, new_context)
            return lambda_expr
        elif callee == 'if':
            guard = value[1]
            subsequent = value[2]
            if len(value) > 4:
                alternate = value[3]
            else:
                alternate = None
            guarded_value = evaluate(guard, context)
            if guarded_value:
                return evaluate(subsequent, context)
            elif alternate is None:
                return []
            else:
                return evaluate(alternate, context)
        elif callee == 'cond':
            for case, body in value[1:]:
                guard_value = evaluate(case, context)
                if case == 'else':
                    guard_value = True
                else:
                    guard_value = evaluate(case, context)
                if guard_value:
                    return evaluate(body, context)
            return None
        elif callee == 'begin':
            result = None
            for statement in value[1:]:
                result = evaluate(statement, context)
            return result
        elif callee == 'define':
            name = value[1]
            body = value[2]
            if isinstance(name, list):
                # Syntactic sugar
                return evaluate(['define', name[0], ['lambda', name[1:], body]],
                                context)
            body_value = evaluate(body, context)
            context[name] = body_value
            return body_value
        elif callee == 'set!':
            name = value[1]
            body = value[2]
            body_value = evaluate(body, context)
            context.set_bang(name, body_value)
            return body_value
        elif callee == 'let':
            new_context = Context(context)
            for name, binding in value[1]:
                binding_value = evaluate(binding, context)
                new_context[name] = binding_value
            return evaluate(value[2], new_context)
        elif callee == 'let*':
            for name, binding in value[1]:
                binding_value = evaluate(binding, context)
                context = Context(context)
                context[name] = binding_value
            return evaluate(value[2], context)
        elif callee == 'quote':
            return value[1]
        elif callee == 'or':
            body_value = False
            for body in value[1:]:
                body_value = evaluate(body, context)
                if body_value:
                    break
            return body_value
        elif callee == 'and':
            body_value = True
            for body in value[1:]:
                body_value = evaluate(body, context)
                if not body_value:
                    break
            return body_value
        elif callee == 'letrec':
            new_context = Context(context)
            for name, binding in value[1]:
                binding_value = evaluate(binding, new_context)
                new_context[name] = binding_value
            return evaluate(value[2], new_context)
        else:
            callee_value = evaluate(callee, context)
            arguments = [evaluate(arg, context) for arg in value[1:]]
            if callable(callee_value):
                if TRACE:
                    print('CALL', callee_value.__name__, *arguments)
                return callee_value(*arguments)
            else:
                raise ValueError('cannot evaluate non-function-liek')

builtins = {}

def builtin(fn):
    builtins[fn.__name__.replace('_q', '?')] = fn
    return fn

builtins['display'] = print

@builtin
def read():
    return input()

builtins['list'] = lambda *args: args

@builtin
def car(value):
    return value[0]

@builtin
def cdr(value):
    return value[1:]

@builtin
def null_q(value):
    return value == []

@builtin
def pair_q(value):
    return instanceof(value, list) and len(value) > 0

@builtin
def append(*lists):
    return sum(lists, [])

@builtin
def reverse(l):
    return list(reversed(l))

@builtin
def apply(callee, args):
    callee(*args)

builtins['else'] = True
builtins['eq?'] = operator.is_
builtins['eqv?'] = operator.eq
builtins['equal?'] = operator.eq
builtins['not'] = operator.not_
builtins['='] = operator.eq
builtins['!='] = operator.ne
builtins['<'] = operator.lt
builtins['<='] = operator.le
builtins['>'] = operator.gt
builtins['>='] = operator.ge
builtins['abs'] = abs
builtins['length'] = len
def plus(*args):
    return sum(args)
builtins['+'] = plus
def minus(*args):
    if len(args) == 1:
        return -args[0]
    elif len(args) == 2:
        return args[0] - args[1]
    else:
        raise ValueError('wrong number of arguments')
builtins['-'] = minus
builtins['*'] = operator.mul
builtins['/'] = operator.truediv
builtins['write'] = sys.stdout.write

@builtin
def number_q(x):
    return isinstance(x, numbers.Real)

@builtin
def symbol_q(x):
    return isinstance(x, str)

@builtin
def newline():
    print()

@builtin
def cons(x, xs):
    return [x] + xs

root_context = Context(builtins)

if sys.argv[1] == '-':
    program = sys.stdin.read()
else:
    with open(sys.argv[1]) as f:
        program = f.read()

commands = (space >> sexp.repeat()).run(program)
for command in commands:
    result = evaluate(command, root_context)
if result is not None:
    print('>', result)