From 8ba9830401e3e02fb1f60f53b714e55881115559 Mon Sep 17 00:00:00 2001 From: David Kerkeslager Date: Mon, 30 May 2016 16:44:20 -0400 Subject: [PATCH] Adding my first attempt at writing a lisp --- mini/.gitignore | 2 + mini/README.md | 15 + mini/examples/01-hello.mini | 1 + mini/examples/02-prompt.mini | 1 + mini/examples/03-cmd.mini | 3 + mini/mini.mini | 7 + mini/mini.py | 921 +++++++++++++++++++++++++++++++++++ mini/mini.py-unit-tests.mini | 262 ++++++++++ mini/predefineds.mini | 71 +++ 9 files changed, 1283 insertions(+) create mode 100644 mini/.gitignore create mode 100644 mini/README.md create mode 100644 mini/examples/01-hello.mini create mode 100644 mini/examples/02-prompt.mini create mode 100644 mini/examples/03-cmd.mini create mode 100644 mini/mini.mini create mode 100644 mini/mini.py create mode 100644 mini/mini.py-unit-tests.mini create mode 100644 mini/predefineds.mini diff --git a/mini/.gitignore b/mini/.gitignore new file mode 100644 index 0000000..85118b7 --- /dev/null +++ b/mini/.gitignore @@ -0,0 +1,2 @@ +.env +*.pyc diff --git a/mini/README.md b/mini/README.md new file mode 100644 index 0000000..23c3365 --- /dev/null +++ b/mini/README.md @@ -0,0 +1,15 @@ +mini +==== + +A minimal lisp + +Usage +----- +To run unit tests: `python mini.py source-file-name.mini` + +References +---------- +This implementation is influenced by John Shutt's work on +the Kernel programming language, especially the way it evaluates +(arguments don't evaluate by default). The relevant dissertation +can be found [here](https://www.wpi.edu/Pubs/ETD/Available/etd-090110-124904/unrestricted/jshutt.pdf). diff --git a/mini/examples/01-hello.mini b/mini/examples/01-hello.mini new file mode 100644 index 0000000..edeb148 --- /dev/null +++ b/mini/examples/01-hello.mini @@ -0,0 +1 @@ +(print "Hello, world") diff --git a/mini/examples/02-prompt.mini b/mini/examples/02-prompt.mini new file mode 100644 index 0000000..cd774dc --- /dev/null +++ b/mini/examples/02-prompt.mini @@ -0,0 +1 @@ +(prompt ">>> ") diff --git a/mini/examples/03-cmd.mini b/mini/examples/03-cmd.mini new file mode 100644 index 0000000..d620540 --- /dev/null +++ b/mini/examples/03-cmd.mini @@ -0,0 +1,3 @@ +(if (= __arguments__ nil) + (print "No arguments given") + (print (car __arguments__))) diff --git a/mini/mini.mini b/mini/mini.mini new file mode 100644 index 0000000..bc1977a --- /dev/null +++ b/mini/mini.mini @@ -0,0 +1,7 @@ +(define repl (function () (print "repl"))) + +(define run-file (function (file args) (print (read-file file)))) + +(if (= __arguments__ nil) + (repl) + (run-file (car __arguments__) (cdr __arguments__))) diff --git a/mini/mini.py b/mini/mini.py new file mode 100644 index 0000000..2c716dd --- /dev/null +++ b/mini/mini.py @@ -0,0 +1,921 @@ +from __future__ import print_function + +import re +import traceback + +class MiniObject(object): + def __init__(self, py_object, **meta): + ( "The following python types map to the following mini types:\n" + " bool -> boolean\n" + " str -> string\n" + " int -> integer\n" + " float -> float\n" + " tuple -> list (may contain different types)\n" + " list -> vector (may only contain one type)\n" + " dict -> map\n" + " MiniSymbol -> symbol\n" + " Pair -> pair" + "mini vectors and maps should be treated as though immutable" + "s-expressions should be parsed as tuples" + ) + self.py_object = py_object + self.meta = meta + + def __repr__(self): + if self.py_object == None: + return 'nil' + + if isinstance(self.py_object,bool): + return 'true' if self.py_object else 'false' + + return repr(self.py_object) + + def __str__(self): + if isinstance(self.py_object,str): + return self.py_object + + return repr(self) + +class Identifier(object): + def __init__(self,symbol,**kwargs): + assert isinstance(symbol,str) + + self.symbol = symbol + + self.start = kwargs.get('start') + self.end = kwargs.get('end') + + def __repr__(self): + return ''.format(self.symbol) + +def is_identifier(mini_object): + assert isinstance(mini_object, MiniObject) + if isinstance(mini_object.py_object, Identifier): + return TRUE + return FALSE + +SYMBOLS = {} + +class MiniSymbol(object): + def __init__(self,string): + self.string = string + + def __eq__(self,other): + return self is other + + def __repr__(self): + return ''.format(self.string) + +class MiniPair(object): + def __init__(self, car, cdr): + assert isinstance(car, MiniObject) + assert isinstance(cdr, MiniObject) + + self.car = car + self.cdr = cdr + + def __repr__(self): + return ''.format(self.car, self.cdr) + +def evaluate_arguments(arguments_cons_list, environment): + if arguments_cons_list == NIL: + return NIL + + return cons( + evaluate(car(arguments_cons_list), environment), + evaluate_arguments(cdr(arguments_cons_list), environment)) + +class MiniEnvironment(MiniObject): + 'This acts like a dict in Python code and a cons-dict in mini code' + def __init__(self): + super(self.__class__, self).__init__(None) + + def __getitem__(self,key): + assert isinstance(key,str) + key_symbol = create_symbol(key) + + return cons_dict_get(self,key_symbol) + + def __setitem__(self,key,value): + assert isinstance(key,str) + key_symbol = create_symbol(key) + + assert isinstance(value, MiniObject) + self.py_object = cons_dict_set(self,key_symbol,value).py_object + + def __contains__(self,key): + assert isinstance(key,str) + key_symbol = create_symbol(key) + + return cons_dict_has_key(self,key_symbol) == TRUE + + def get(self,key): + assert isinstance(key,str) + + if key in self: + return self[key] + + return None + +def dict_to_environment(dictionary): + result = MiniEnvironment() + + for key,value in dictionary.iteritems(): + result[key] = value + + return result + +class MiniApplicative(object): + def __init__(self, operative): + assert callable(operative) + self.operative = operative + + def __call__(self, pattern, environment): + assert isinstance(pattern, MiniObject) + + return self.operative(pattern, environment) + +class MiniWrapper(object): + def __init__(self, operative): + assert isinstance(operative,MiniObject) + assert isinstance(operative.py_object, MiniApplicative) or isinstance(operative.py_object, MiniWrapper) + + self.operative = operative + + def __call__(self, pattern, environment): + assert isinstance(pattern, MiniObject) + + return self.operative.py_object(evaluate_arguments(pattern, environment), environment) + + def __repr__(self): + return "".format(repr(self.operative)) + +def wrap(thing): + return MiniObject(MiniWrapper(thing)) + +def unwrap(thing): + if isinstance(thing.py_object, MiniWrapper): + return thing.py_object.operative + + raise Exception('UnwrapError') + +def create_symbol(string,**kwargs): + if string in SYMBOLS: + return SYMBOLS[string] + + k = MiniObject(MiniSymbol(string), **kwargs) + SYMBOLS[string] = k + return k + +def create_cons_collection(py_collection): + result = NIL + + for item in reversed(py_collection): + result = MiniObject(MiniPair(item, result)) + + return result + +def cons_collection_to_py_collection(cons_collection): + while cons_collection != NIL: + yield car(cons_collection) + cons_collection = cdr(cons_collection) + +token_regex = re.compile(r'''(?mx) + (\s*|\#.*?\n)*(?: + (?P\()| + (?P\))| + (?P\-?\d+\.\d+|\-?\d+)| + (?P"[^"]*")| + (?P[_A-Za-z\?\-\+\*/=\>\<]+)| + (?P\:[_A-Za-z\?\-\+\*/=\>\<]*) + )''') + +def parse_all(source): + def parse(matches, index_holder): + match = matches[index_holder[0]] + index_holder[0] += 1 + + if match.group('open_parenthese'): + r = [] + + while index_holder[0] < len(matches) and not matches[index_holder[0]].group('close_parenthese'): + r.append(parse(matches, index_holder)) + + if index_holder[0] == len(matches): + raise Exception('Unmatched parenthese (') + + index_holder[0] += 1 + return create_cons_collection(r) + + if match.group('close_parenthese'): + raise Exception("Unmatched parenthese )") + + if match.group('number'): + v = float(match.group('number')) + if v.is_integer(): v = int(v) + + return MiniObject( + v, + start = match.start('number'), + end = match.end('number')) + + if match.group('string'): + return MiniObject( + match.group('string')[1:-1], + start = match.start('string'), + end = match.end('string')) + + if match.group('identifier'): + return MiniObject(Identifier( + match.group('identifier'), + start = match.start('identifier'), + end = match.end('identifier'))) + + if match.group('symbol'): + return create_symbol( + match.group('symbol')[1:], + start = match.start('symbol'), + end = match.end('symbol')) + + assert False, "I'm not sure how this happened" + + def parse_all_internal(matches, index_holder): + if index_holder[0] == len(matches): + return NIL + + parsed_atom = parse(matches, index_holder) + + return cons(parsed_atom, parse_all_internal(matches, index_holder)) + + matches = list(token_regex.finditer(source)) + match_index_wrapped = [0] + + return parse_all_internal(matches, match_index_wrapped) + +NIL = MiniObject(None) + +class Boolean(MiniObject): + def __init__(self, py_object, **kwargs): + super(Boolean,self).__init__(py_object, **kwargs) + +TRUE = Boolean(True) +FALSE = Boolean(False) + +def is_number(arg): + if isinstance(arg, float): + return True + + # isinstance(True, int) returns True + return isinstance(arg, int) and not isinstance(arg, bool) + +def py_to_mini(py_object): + assert callable(py_object) + + def wrapped(pattern, environment): + result = py_object(*cons_collection_to_py_collection(pattern)) + + if is_number(result) or isinstance(result,MiniPair): + return MiniObject(result) + + if isinstance(result,str): + return MiniObject(result) + + return { + True : TRUE, + False : FALSE, + None : NIL, + }.get(result, result) + + return MiniObject(MiniWrapper(MiniObject(MiniApplicative(wrapped)))) + +def apply(applicative, pattern, environment): + assert isinstance(applicative, MiniObject) + + return applicative.py_object(pattern, environment) + +def evaluate(expression, environment): + assert isinstance(expression, MiniObject) + + if isinstance(expression.py_object, str) or is_number(expression.py_object): + return expression + + if isinstance(expression.py_object, MiniSymbol): + return expression + + if isinstance(expression.py_object, MiniPair): + applicative = evaluate(car(expression), environment) + arguments = cdr(expression) + + assert isinstance(applicative, MiniObject) + assert isinstance(arguments, MiniObject) + + if isinstance(applicative.py_object, MiniApplicative) or isinstance(applicative.py_object, MiniWrapper): + return apply(applicative, arguments, environment) + + raise Exception("Expected applicative, got {}".format(applicative.py_object)) + + if isinstance(expression.py_object, Identifier): + parent_symbol = create_symbol('__parent__') + + while environment != None: + if cons_dict_has_key(environment, create_symbol(expression.py_object.symbol)) == TRUE: + return cons_dict_get(environment, create_symbol(expression.py_object.symbol)) + + if cons_dict_has_key(environment, parent_symbol) == TRUE: + environment = cons_dict_get(environment, create_symbol('__parent__')) + else: + raise Exception('UndefinedIdentifierError: Undefined identifier {}'.format(expression.py_object.symbol)) + +def length(string): + assert isinstance(string, MiniObject) + + if isinstance(string.py_object, str): + return len(string.py_object) + + raise Exception("TypeError") + +def concatenate(l,r): + # TODO Implement ropes: http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.14.9450&rep=rep1&type=pdf + # TODO Apply this to other collection types + if isinstance(l.py_object,str) and isinstance(r.py_object, str): + return MiniObject(l.py_object + r.py_object) + + raise Exception('TypeError') + +def is_integer(arg): + return isinstance(arg, int) and not isinstance(arg, bool) + +def slice(string, start, end): + if not isinstance(string.py_object, str): + raise Exception('TypeError') + + py_string = string.py_object + + if is_integer(start.py_object): + py_start = start.py_object + + elif start.py_object == None: + py_start = 0 + + else: + raise Exception('TypeError') + + if is_integer(end.py_object): + py_end = end.py_object + + elif end.py_object == None: + py_end = len(py_string) + + else: + raise Exception('TypeError') + + return MiniObject(py_string[py_start:py_end]) + +def _assert(pattern, environment): + def assert_internal(*arguments): + if len(arguments) == 0: + raise Exception("ArgumentError: assert expects 1 or more arguments, received none") + + if len(arguments) == 1: + description = 'assertion failed' + assertion = arguments + + else: + description = arguments[0].py_object + assertion = arguments[1:] + + if not isinstance(assertion[-1].py_object, bool): + raise Exception("TypeError: `assert` expected Boolean assertion but received {} {}".format(type(assertion[-1].py_object), assertion[-1])) + + if assertion[-1] is TRUE: + return None + + if assertion[-1] is FALSE: + raise Exception("AssertionError: {}".format(description)) + + assert False + + # Execute in nested scope + return py_to_mini(assert_internal).py_object(pattern, nest(environment)) + +def throws(pattern, environment): + if cons_collection_len(pattern) != 2: + raise Exception("throws? expects 2 argument, received {}".format(len(pattern))) + + expression = car(pattern) + exception = evaluate(car(cdr(pattern)), environment) + + if not isinstance(exception.py_object, str): + raise Exception('throws? expects a string as the second argument') + + try: + evaluate(expression, environment) + return FALSE + + except Exception as e: + if ':' in e.message: + exception_type, message = e.message.split(':',1) + else: + exception_type = e.message + + if exception_type == exception.py_object: + return TRUE + + raise + +def _not(argument): + if not isinstance(argument, Boolean): + raise Exception('TypeError: Expected Boolean but received {}'.format(type(argument))) + + if argument == TRUE: + return FALSE + + if argument == FALSE: + return TRUE + + assert False + +def evaluate_expressions(expressions, environment): + result = NIL + + while expressions != NIL: + result = evaluate(car(expressions), environment) + expressions = cdr(expressions) + + return result + +def cons_collection_len(cons_collection): + result = 0 + + while cons_collection != NIL: + result += 1 + cons_collection = cdr(cons_collection) + + return result + +def define(pattern, environment): + if cons_collection_len(pattern) < 2: + raise Exception('DefineError: `define` expected two arguments, received {}'.format(cons_collection_len(pattern))) + + head = car(pattern) + body = cdr(pattern) + + if isinstance(head.py_object, Identifier): + identifier = head.py_object.symbol + + if is_defined(head, environment) == TRUE: + raise Exception('AlreadyDefinedError: the identifier {} is already defined'.format(identifier)) + + environment[identifier] = evaluate_expressions(body, environment) + + return NIL + + elif isinstance(head.py_object, MiniPair): + raise Exception('NotImplementedError: Defining patterns is not yet implemented') + + else: + raise Exception("DefineError") + +def defined_p(pattern, environment): + if cons_collection_len(pattern) != 1: + raise Exception("ArgumentError: `defined?` expects 1 argument, received {}".format(len(pattern))) + + if not isinstance(car(pattern).py_object, Identifier): + raise Exception("TypeError: Expected Identifier but got {}".format(type(car(pattern).py_object))) + + return is_defined(car(pattern), environment) + +def is_defined(identifier, environment): + assert isinstance(identifier, MiniObject) + assert isinstance(environment, MiniObject) + + identifier_symbol = identifier_to_symbol(identifier) + parent_symbol = create_symbol('__parent__') + + while True: + if cons_dict_has_key(environment, identifier_symbol) == TRUE: + return TRUE + + elif cons_dict_has_key(environment, parent_symbol) == TRUE: + environment = cons_dict_get(environment, parent_symbol) + + else: + return FALSE + +def _if(pattern, environment): + if not cons_collection_len(pattern) in [2,3]: + raise Exception("ArgumentError") + + condition = car(pattern) + if_result_true = car(cdr(pattern)) + if_result_false = car(cdr(cdr(pattern))) + + result = evaluate(condition, environment) + + if result is TRUE: + return evaluate(if_result_true, environment) + if result is FALSE: + return evaluate(if_result_false, environment) + + raise Exception("TypeError: `if` expects boolean, received {}".format(type(result))) + +def nest(environment): + isinstance(environment,MiniEnvironment) + + result = MiniEnvironment() + result['__parent__'] = environment + return result + +# This is vau from John N. Shutt's seminal paper +# https://www.wpi.edu/Pubs/ETD/Available/etd-090110-124904/unrestricted/jshutt.pdf +# While Greek letters are appropriate for an academic, theoretical context, they make for +# poor variable names, so this is tentatively named `operative` +def operative(pattern, defining_environment): + argument_list_identifier = None + argument_identifiers = None + + calling_environment_identifier = car(cdr(pattern)).py_object.symbol + + if isinstance(car(pattern).py_object, Identifier): + argument_list_identifier = car(pattern).py_object.symbol + + if calling_environment_identifier == argument_list_identifier: + raise Exception("ArgumentError: Argument list identifier `{}` may not be the same as calling environment identifier".format(ai)) + + elif car(pattern).py_object == None or isinstance(car(pattern).py_object, MiniPair): + if not all([isinstance(arg.py_object, Identifier) for arg in cons_collection_to_py_collection(car(pattern))]): + raise Exception("ArgumentError: Unexpected {} {}".format(type(arg),arg)) + + argument_identifiers = [ai.py_object.symbol for ai in cons_collection_to_py_collection(car(pattern))] + + existing = set() + for ai in argument_identifiers: + if ai in existing: + raise Exception("ArgumentError: Argument `{}` already defined".format(ai)) + + if calling_environment_identifier == ai: + raise Exception("ArgumentError: Argument `{}` may not be the same as calling environment identifier".format(ai)) + + existing.add(ai) + + else: + raise Exception("ArgumentError: `operative` expected identifier or cons-list as first argument, received {}".format(type(car(pattern).py_object))) + + if not isinstance(car(cdr(pattern)).py_object,Identifier): + raise Exception("ArgumentError: The second argument to `operative` should be an identifer") + + def result(calling_pattern, calling_environment): + local_environment = nest(defining_environment) + + assert (argument_list_identifier == None) != (argument_identifiers == None) + if argument_list_identifier != None: + local_environment[argument_list_identifier] = calling_pattern + + if argument_identifiers != None: + if not cons_collection_len(calling_pattern) == len(argument_identifiers): + raise Exception("ArgumentError: operative expected {} arguments, received {}".format(len(argument_identifiers),len(calling_pattern))) + + calling_pattern = list(cons_collection_to_py_collection(calling_pattern)) + + for i in range(len(argument_identifiers)): + local_environment[argument_identifiers[i]] = calling_pattern[i] + + local_environment[calling_environment_identifier] = calling_environment + + return evaluate_expressions(cdr(cdr(pattern)), local_environment) + + return MiniObject(MiniApplicative(result)) + +def read_file(filename): + assert isinstance(filename, MiniObject) + + with open(filename.py_object, 'r') as f: + return f.read() + +def write_file(filename, string): + assert isinstance(filename, MiniObject) + assert isinstance(string, MiniObject) + + with open(filename.py_object, 'w') as f: + f.write(string.py_object) + +def add(l,r): + if isinstance(l, MiniObject) and isinstance(r, MiniObject): + l = l.py_object + r = r.py_object + + if is_number(l) and is_number(r): + return l + r + + raise Excepion('TypeError') + +def subtract(l,r): + if isinstance(l, MiniObject) and isinstance(r, MiniObject): + l = l.py_object + r = r.py_object + + if is_number(l) and is_number(r): + return l - r + + raise Excepion('TypeError') + +def multiply(l,r): + if isinstance(l, MiniObject) and isinstance(r, MiniObject): + l = l.py_object + r = r.py_object + + if is_number(l) and is_number(r): + return l * r + + raise Excepion('TypeError') + +def divide(l,r): + if isinstance(l, MiniObject) and isinstance(r, MiniObject): + l = l.py_object + r = r.py_object + + if is_number(l) and is_number(r): + if isinstance(l,int) and isinstance(r,int) and l % r != 0: + l = float(l) + + return l / r + + raise Excepion('TypeError') + +def idivide(l,r): + if isinstance(l, MiniObject) and isinstance(r, MiniObject): + l = l.py_object + r = r.py_object + + if is_number(l) and is_number(r): + return l // r + + raise Excepion('TypeError') + +def mod(l,r): + if isinstance(l, MiniObject) and isinstance(r, MiniObject): + l = l.py_object + r = r.py_object + + if is_number(l) and is_number(r): + return l % r + + raise Excepion('TypeError') + +def eq(l,r): + assert isinstance(l,MiniObject) + assert isinstance(r,MiniObject) + + return l.py_object == r.py_object + +def lt(l,r): + assert isinstance(l,MiniObject) + assert isinstance(r,MiniObject) + + if is_number(l.py_object) and is_number(r.py_object): + return l.py_object < r.py_object + + if isinstance(l.py_object,str) and isinstance(r.py_object,str): + return l.py_object < r.py_object + + if isinstance(l.py_object,MiniSymbol) and isinstance(r.py_object,MiniSymbol): + return l.py_object.string < r.py_object.string + + raise TypeError('`<` expected number or string, received {} and {}'.format(l.py_object, r.py_object)) + +def gt(l,r): + assert isinstance(l,MiniObject) + assert isinstance(r,MiniObject) + + if is_number(l.py_object) and is_number(r.py_object): + return l.py_object > r.py_object + + if isinstance(l.py_object,str) and isinstance(r.py_object,str): + return l.py_object > r.py_object + + if isinstance(l.py_object,MiniSymbol) and isinstance(r.py_object,MiniSymbol): + return l.py_object.string > r.py_object.string + + raise TypeError('`>` expected number or string, received {} and {}'.format(l.py_object, r.py_object)) + +def le(l,r): + return lt(l,r) or eq(l,r) + +def ge(l,r): + return gt(l,r) or eq(l,r) + +def cons(l,r): + return MiniObject(MiniPair(l,r)) + +def car(p): + return p.py_object.car + +def cdr(p): + return p.py_object.cdr + +def is_cons_list(mini_object): + assert isinstance(mini_object,MiniObject) + + if eq(mini_object,NIL) or isinstance(mini_object.py_object,MiniPair): + return TRUE + + return FALSE + +def cons_dict_set(dictionary,key,value): + assert isinstance(dictionary,MiniObject) + assert isinstance(key,MiniObject) + assert isinstance(value,MiniObject) + + if eq(dictionary,NIL): + return cons(cons(key,value),cons(NIL,NIL)) + + current_node_key = car(car(dictionary)) + + if lt(key,current_node_key): + return cons( + car(dictionary), + cons( + cons_dict_set(car(cdr(dictionary)), key, value), + cdr(cdr(dictionary)))) + + if gt(key,current_node_key): + return cons( + car(dictionary), + cons( + car(cdr(dictionary)), + cons_dict_set(cdr(cdr(dictionary)), key, value))) + + if eq(key,current_node_key): + return cons(cons(key,value), cdr(dictionary)) + + assert False + +def cons_dict_get(dictionary,key): + assert isinstance(dictionary, MiniObject) + assert isinstance(key, MiniObject) + + if eq(dictionary,NIL): + raise Exception('KeyError: Dictionary does not contain key "{}"'.format(key)) + + current_node_key = car(car(dictionary)) + + if lt(key, current_node_key): + return cons_dict_get(car(cdr(dictionary)), key) + + if gt(key, current_node_key): + return cons_dict_get(cdr(cdr(dictionary)), key) + + if eq(key, current_node_key): + return cdr(car(dictionary)) + +def cons_dict_has_key(dictionary,key): + assert isinstance(dictionary, MiniObject) + assert isinstance(key, MiniObject) + + if eq(dictionary,NIL): + return FALSE + + current_node_key = car(car(dictionary)) + + if lt(key, current_node_key): + return cons_dict_has_key(car(cdr(dictionary)), key) + + if gt(key, current_node_key): + return cons_dict_has_key(cdr(cdr(dictionary)), key) + + if eq(key, current_node_key): + return TRUE + +def identifier_to_symbol(identifier): + assert isinstance(identifier, MiniObject) + + if not isinstance(identifier.py_object, Identifier): + raise Exception('`identifier->symbol` expected identifier, received {}'.format(type(identifier.py_object))) + + return create_symbol(identifier.py_object.symbol) + +def read(string): + assert isinstance(string,MiniObject) + + if not isinstance(string.py_object,str): + raise Exception("TypeError: `read` expected string, got {}".format(type(strin.py_object))) + + result = parse_all(string.py_object) + + assert cdr(result) == NIL + + return car(result) + +builtins = { + # Builtin constants + 'true' : TRUE, + 'false' : FALSE, + 'nil' : NIL, + + # Builtin comparison functions + '=' : py_to_mini(eq), + '<' : py_to_mini(lt), + '>' : py_to_mini(gt), + '<=' : py_to_mini(le), + '>=' : py_to_mini(ge), + + # Builtin conversion functions + 'identifier->symbol' : py_to_mini(identifier_to_symbol), + + # Builtin type test functions + 'cons-list?' : py_to_mini(is_cons_list), + 'identifier?' : py_to_mini(is_identifier), + + # Builtin general functions + 'evaluate' : py_to_mini(evaluate), + 'evaluate-expressions' : py_to_mini(evaluate_expressions), + 'print' : py_to_mini(print), + 'prompt' : py_to_mini(raw_input), + 'read-file' : py_to_mini(read_file), + 'write-file' : py_to_mini(write_file), + 'read' : py_to_mini(read), + 'wrap' : py_to_mini(wrap), + 'unwrap' : py_to_mini(unwrap), + + # Builtin number functions + '+' : py_to_mini(add), + '-' : py_to_mini(subtract), + '*' : py_to_mini(multiply), + '/' : py_to_mini(divide), + '//' : py_to_mini(idivide), + 'mod' : py_to_mini(mod), + + # Builtin pair functions + 'cons' : py_to_mini(cons), + 'car' : py_to_mini(car), + 'cdr' : py_to_mini(cdr), + + # Builtin cons dictionary functions + 'cons-dict-set' : py_to_mini(cons_dict_set), + 'cons-dict-get' : py_to_mini(cons_dict_get), + + # Builtin string functions + 'concatenate' : py_to_mini(concatenate), + 'length' : py_to_mini(length), + 'slice' : py_to_mini(slice), + + # Builtin boolean functions + 'not' : py_to_mini(_not), + + # Builtin special forms + 'assert' : MiniObject(MiniApplicative(_assert)), + 'define' : MiniObject(MiniApplicative(define)), + 'defined?' : MiniObject(MiniApplicative(defined_p)), + 'if' : MiniObject(MiniApplicative(_if)), + 'operative' : MiniObject(MiniApplicative(operative)), + 'throws?' : MiniObject(MiniApplicative(throws)), +} + +builtins = dict_to_environment(builtins) + +if __name__ == '__main__': + import os.path + import sys + + arguments = sys.argv[1:] + + predefineds = nest(builtins) + predefineds_filename = os.path.join(os.path.dirname(os.path.realpath(__file__)), 'predefineds.mini') + + with open(predefineds_filename, 'r') as predefineds_file: + predefineds_source = predefineds_file.read() + + try: + evaluate_expressions(parse_all(predefineds_source), predefineds) + + except: + traceback.print_exc() + + if len(arguments) == 0: + environment = nest(predefineds) + + while True: + source = raw_input('>>> ') + + try: + print(evaluate_expressions(parse_all(source), environment)) + + except: + traceback.print_exc() + + else: + filename = arguments[0] + arguments = arguments[1:] + + environment = nest(predefineds) + environment['__file__'] = MiniObject(os.path.join(os.path.realpath(filename))) + environment['__arguments__'] = create_cons_collection(map(MiniObject,arguments)) + + with open(filename,'r') as f: + source = f.read() + + try: + print(evaluate_expressions(parse_all(source), environment)) + + except: + traceback.print_exc() diff --git a/mini/mini.py-unit-tests.mini b/mini/mini.py-unit-tests.mini new file mode 100644 index 0000000..2b80731 --- /dev/null +++ b/mini/mini.py-unit-tests.mini @@ -0,0 +1,262 @@ +# feature tests: variables +(assert "Evaluating undefined variable throws exception" + (throws? undefined-identifier "UndefinedIdentifierError")) + +# pair tests +(assert "`car` retrieves first argument to `cons`" + (car (cons true false))) +(assert "`cdr` retrieves first argument to `cons`" + (cdr (cons false true))) + +# `=` tests +(assert "`=` returns true for equal numbers" (= 0 0)) +(assert "`=` returns false for non-equal numbers" (not (= 0 1))) +(assert "`=` returns true for equal strings" (= "Hello, world" "Hello, world")) +(assert "`=` returns false for non-equal strings" (not (= "Hello, world" "Goodnight, moon"))) +(assert "`=` returns true for equal true values" (= true true)) +(assert "`=` returns true for equal false values" (= false false)) +(assert "`=` returns true for nils" (= nil nil)) +(assert "`=` returns true for equal symbols" (= :symbol :symbol)) +(assert "`=` returns false for non-equal symbols" (not (= :symbol :not-the-same))) +(assert "`=` returns false for symbol-to-string comparison (string first)" + (not (= :symbol ":symbol"))) +(assert "`=` returns false for symbol-to-string comparison (symbol first)" + (not (= ":symbol" :symbol))) + +# `+` tests +(assert "`+` adds" (= (+ 1 2) 3)) + +# `-` tests +(assert "`-` subtracts" (= (- 3 2) 1)) + +# `*` tests +(assert "`*` divides" (= (* 2 3) 6)) + +# `/` tests +(assert "`/` divides evenly" (= (/ 6 3) 2)) +(assert "`/` divides fractionally" (= (/ 7 2) 3.5)) + +# `//` tests +(assert "`//` divides evenly" (= (// 6 3) 2)) +(assert "`//` divides integrally" (= (// 7 2) 3)) + +# `and` tests +(assert "`and` returns false for both false" (not (and false false))) +(assert "`and` returns false for left false and right true" (not (and false true))) +(assert "`and` returns false for left true and right false" (not (and true false))) +(assert "`and` returns true for both true" (and true true)) +(assert "`and` doesn't evalueate second argument if first is false" (not (and false (/ 1 0)))) + +# `assert` tests +(assert "`assert` executes without exception for true assertion" true) +(assert "`assert` returns nil for true assertion" (= (assert true) nil)) +(assert "`assert` throws AssertionError for false assertion" + (throws? (assert false) "AssertionError")) +(assert "`assert` throws TypeError for non-boolean assertion" + (throws? (assert 1) "TypeError")) +(assert "`assert` can take multiple arguments" false true) +(assert "`assert` executes assertion in a nested scope" + (assert "define identifier in nested scope" + (define identifier-in-nested-scope true) + true) + (not (defined? identifier-in-nested-scope))) + +# `merge-association-list-with-cons-dict` tests +(assert "merge-association-list-with-cons-dict returns cons-dict" + (= :value + (cons-dict-get (merge-association-list-with-cons-dict (cons-list-zip (cons-list :key) (cons-list :value)) + nil) + :key))) + +# `concatenate` tests +(assert "`concatenate` concatenates strings" + (= (concatenate "Hello, " "world") + "Hello, world")) + +# `cond` tests +(assert "`cond` returns nil for no conditions" + (= (cond) nil)) +(assert "`cond` returns nil for no true conditions" + (= (cond (false :not-returned) + (false :also-not-returned)) + nil)) +(assert "`cond` returns true when pair evaluates to true" + (= (cond (false :not-returned) + (true :returned) + (false :also-not-returned)) + :returned)) +(assert "`cond` does not execute bodies for false conditions" + (= (cond (false (/ 1 0)) + (true :returned)) + :returned)) + +# `cons-dict` tests +(assert "`cons-dict-get` returns association created by `cons-dict-set`" + (cons-dict-get (cons-dict-set nil :key true) :key)) + +# `cons-list` tests +(assert "`cons-list` first argument is first item" + (car (cons-list true))) +(assert "`cons-list` terminated by null cdr" + (= (cdr (cons-list false)) nil)) + +# `cons-list?` tests +(assert "`cons-list?` returns true for nil" + (cons-list? nil)) +(assert "`cons-list?` returns true for cons-list" + (cons-list? (cons-list 1 2 3))) +(assert "`cons-list?` returns false for non cons-list" + (not (cons-list? 1))) + +# `cons-list-map` tests +(assert "`cons-list-map` returns empty list for empty list" + (= (cons-list-map identifier->symbol nil) nil)) +(assert "`cons-list-map` calls mapping function on items" + (define inc (wrap (operative (i) _ (+ i 1)))) + (define mapped (cons-list-map inc (cons-list 1 2))) + (and (= 2 (car mapped)) + (= 3 (car (cdr mapped))))) + +# `cons-list-zip` tests +(assert "`cons-list-zip` returns nil for empty lists" + (= (cons-list-zip nil nil) nil)) +(assert "`cons-list-zip` returns association list" + (define a-list (cons-list-zip (cons-list :a) (cons-list :b))) + (and (= :a (car (car a-list))) + (= :b (cdr (car a-list))))) + +# `define` tests +(assert "`define` adds identifier to environment" + (define previously-undefined-identifier true) + previously-undefined-identifier) +(assert "`define` throws exception for already-defined variable" + (define already-defined-identifier :value) + (throws? (define already-defined-identifier :another-value) "AlreadyDefinedError")) + +# `defined?` tests +(assert "`defined?` returns true for defined identifier" + (define identifier :value) + (defined? identifier)) +(assert "`defined?` returns false for undefined identifier" + (not (defined? undefined-identifier))) + +# `function` tests +(assert "`function` creates function that returns body" + ((function _ true))) +(assert "`function` closes around defining environment" + (define defining-environment-identifier true) + ((function _ defining-environment-identifier))) +(assert "`function` with an identifier arg binding receives list" + (and (= ((function args (car args)) :arg) :arg) + (= ((function args (cdr args)) :arg) nil))) +(assert "`function` with an s-expression arg binding receives arguments bound to names" + (and (= ((function (foo bar) foo) :baz :qux) :baz) + (= ((function (foo bar) bar) :baz :qux) :qux))) +(assert "`function` can recurse" + (define factorial (function (n) (if (= n 1) 1 (* n (factorial (- n 1)))))) + (and (= 6 (factorial 3)) + (= 120 (factorial 5)))) + +# `get-current-environment` tests +(assert "`get-current-environment` contains local variables as symbols" + (define local-identifier true) + (cons-dict-get (get-current-environment) :local-identifier)) +(assert "`get-current-environment` contains parent scope under :__parent__" + (define parent-identifier true) + (assert (cons-dict-get (cons-dict-get (get-current-environment) :__parent__) :parent-identifier)) + true) + +# `identifier->symbol` tests +(assert "`identifier->symbol` returns a symbol when given an identifier" + (= (identifier->symbol (quote identifier)) :identifier)) + +# `identifier?` tests +(assert "`identifier?` returns true for identifier" + (identifier? (quote identifier))) +(assert "`identifier?` returns false for non-identifier" + (not (identifier? 1))) + +# `if` tests +(assert "`if` returns second argument for true condition" + (if true true false)) +(assert "`if` returns third argument for false condition" + (if false false true)) +(assert "`if` doesn't execute third argument for true condition" + (if true true undefined-identifier)) +(assert "`if` doesn't execute second argument for false condition" + (if false undefined-identifier true)) + +# `length` tests +(assert "`length` returns length of string" + (= 12 (length "Hello, world"))) + +# `not` tests +(assert "`not` returns false for true" (= (not true) false)) +(assert "`not` returns true for false" (= (not false) true)) +(assert "`not` throws TypeError for non-boolean argument" + (throws? (not 1) "TypeError")) + +# `operative` tests +(assert "`operative` creates callable operative" + ((operative () env true))) +(assert "`operative` receives the environment" + (define receives-environment (operative () env (evaluate (quote true-identifier) env))) + (define true-identifier true) + (receives-environment)) +(assert "`operative` receives arguments" + ((operative (arg) env (evaluate arg env)) true)) +(assert "`operative` executes in its own environment" + ((operative () env + (define should-not-be-defined false))) + (not (defined? should-not-be-defined))) +(assert "`operative` doesn't evaluate its arguments" + ((operative (arg) env true) (/ 1 0))) +(assert "`operative` with a symbol argument receives a cons-linked-list" + (and (= ((operative argument-list env (car argument-list)) 1) 1) + (= ((operative argument-list env (cdr argument-list)) 1) nil))) +(assert "`operative` argument lists nest" + (and (= ((operative argument-list env (car (car argument-list))) (1)) 1) + (= ((operative argument-list env (cdr (car argument-list))) (1)) nil))) +(assert "`operative` with an s-expression argument still receives lists" + (and (= ((operative (arg) env (car arg)) (1)) 1) + (= ((operative (arg) env (cdr arg)) (1)) nil))) +(assert "`operative` executes body in a nested scope" + ((operative () env + (define defined-in-nested-scope :value) + (assert (defined? defined-in-nested-scope)))) + (not (defined? defined-in-nested-scope))) +(assert "`operative` with no args receives nil" + (= ((operative args-list _ args-list)) nil)) + +# `or` tests +(assert "`or` returns false for both false" (not (or false false))) +(assert "`or` returns true for left false and right true" (or false true)) +(assert "`or` returns true for left true and right false" (or true false)) +(assert "`or` returns true for both true" (or true true)) +(assert "`or` doesn't evalueate second argument if first is true" (or true (/ 1 0))) + +# `read` tests +(assert "`read` reads identifiers" + (= (identifier->symbol (read "identifier")) :identifier)) + +# `slice` tests +(assert "`slice` returns a slice of a string" + (= (slice "Hello, world" 1 11) "ello, worl")) +(assert "`slice` uses start of string if start index is nil" + (= (slice "Hello, world" nil 11) "Hello, worl")) +(assert "`slice` uses end of string if end index is nil" + (= (slice "Hello, world" 1 nil) "ello, world")) +(assert "`slice` counts backward if start or end is negative" + (= (slice "Hello, world" -11 -1) "ello, worl")) + +# `throws?` tests +(assert "`throws?` returns false when no exception is thrown" + (not (throws? (assert true) "AssertionError"))) +(assert "`throws?` returns true when the correct exception is thrown" + (throws? (assert false) "AssertionError")) +(assert "`throws?` doesn't catch when the wrong exception is thrown" + (throws? (throws? (assert false) "TypeError") "AssertionError")) + +# `wrap` tests +(assert "`wrap` evaluates arguments to wrapped operative" + ((wrap (operative (input) _ input)) (= 1 1))) diff --git a/mini/predefineds.mini b/mini/predefineds.mini new file mode 100644 index 0000000..c72f85e --- /dev/null +++ b/mini/predefineds.mini @@ -0,0 +1,71 @@ +(define cond + (operative cases env + (define cond-internal + (wrap (operative (cases-list) _ + (if (= cases-list nil) + nil + (if (evaluate (car (car cases-list)) env) + (evaluate (car (cdr (car cases-list))) env) + (cond-internal (cdr cases-list))))))) + (cond-internal cases))) + +(define cons-list-zip + (wrap (operative (left right) _ + (cond ((and (= left nil) (= right nil)) nil) + ((= left nil) (assert false)) + ((= right nil) (assert false)) + (true (cons (cons (car left) (car right)) + (cons-list-zip (cdr left) (cdr right)))))))) + +# Maybe environments should have been association lists +(define merge-association-list-with-cons-dict + (wrap (operative (a-list cons-dict) _ + (if (= a-list nil) + cons-dict + (merge-association-list-with-cons-dict + (cdr a-list) + (cons-dict-set cons-dict (car (car a-list)) (cdr (car a-list)))))))) + +(define cons-list-map + (wrap (operative (f xs) _ + (if (= xs nil) + nil + (cons (f (car xs)) (cons-list-map f (cdr xs))))))) + +(define function + (operative outer-args outer-env + (define arg-binding (car outer-args)) + (define function-body (cdr outer-args)) + + (define initial-function-env (cons-dict-set nil :__parent__ outer-env)) + + (wrap (operative inner-args inner-env + (define function-env + (cond ((identifier? arg-binding) (cons-dict-set initial-function-env + (identifier->symbol arg-binding) + inner-args)) + ((cons-list? arg-binding) (merge-association-list-with-cons-dict (cons-list-zip (cons-list-map identifier->symbol arg-binding) inner-args) + initial-function-env)) + (true (assert "Must be an identifier or a cons-list" false)))) + (evaluate-expressions function-body function-env))))) + +(define and (operative (left right) env + (if (evaluate left env) + (evaluate right env) + false))) + +(define or (operative (left right) env + (if (evaluate left env) + true + (evaluate right env)))) + +(define quote (operative (quoted-expression) _ quoted-expression)) + +(define nil? (operative (expression) env + (= (evaluate expression env) nil))) + +(define get-current-environment + (wrap (operative () env env))) + +(define cons-list + (wrap (operative items _ items))) -- 2.20.1