Skip to content

Instantly share code, notes, and snippets.

@prophile
Last active August 29, 2015 14:19
Show Gist options
  • Save prophile/089bd3f86e007b7055e4 to your computer and use it in GitHub Desktop.
Save prophile/089bd3f86e007b7055e4 to your computer and use it in GitHub Desktop.
A quick Scheme implementation in Python, as a programming exercise
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment