1 from __future__ import print_function
6 class MiniObject(object):
7 def __init__(self, py_object, **meta):
8 ( "The following python types map to the following mini types:\n"
13 " tuple -> list (may contain different types)\n"
14 " list -> vector (may only contain one type)\n"
16 " MiniSymbol -> symbol\n"
18 "mini vectors and maps should be treated as though immutable"
19 "s-expressions should be parsed as tuples"
21 self.py_object = py_object
25 if self.py_object == None:
28 if isinstance(self.py_object,bool):
29 return 'true' if self.py_object else 'false'
31 return repr(self.py_object)
34 if isinstance(self.py_object,str):
39 class Identifier(object):
40 def __init__(self,symbol,**kwargs):
41 assert isinstance(symbol,str)
45 self.start = kwargs.get('start')
46 self.end = kwargs.get('end')
49 return '<identifier {}>'.format(self.symbol)
51 def is_identifier(mini_object):
52 assert isinstance(mini_object, MiniObject)
53 if isinstance(mini_object.py_object, Identifier):
59 class MiniSymbol(object):
60 def __init__(self,string):
63 def __eq__(self,other):
67 return '<symbol :{}>'.format(self.string)
69 class MiniPair(object):
70 def __init__(self, car, cdr):
71 assert isinstance(car, MiniObject)
72 assert isinstance(cdr, MiniObject)
78 return '<pair {}, {}>'.format(self.car, self.cdr)
80 def evaluate_arguments(arguments_cons_list, environment):
81 if arguments_cons_list == NIL:
85 evaluate(car(arguments_cons_list), environment),
86 evaluate_arguments(cdr(arguments_cons_list), environment))
88 class MiniEnvironment(MiniObject):
89 'This acts like a dict in Python code and a cons-dict in mini code'
91 super(self.__class__, self).__init__(None)
93 def __getitem__(self,key):
94 assert isinstance(key,str)
95 key_symbol = create_symbol(key)
97 return cons_dict_get(self,key_symbol)
99 def __setitem__(self,key,value):
100 assert isinstance(key,str)
101 key_symbol = create_symbol(key)
103 assert isinstance(value, MiniObject)
104 self.py_object = cons_dict_set(self,key_symbol,value).py_object
106 def __contains__(self,key):
107 assert isinstance(key,str)
108 key_symbol = create_symbol(key)
110 return cons_dict_has_key(self,key_symbol) == TRUE
113 assert isinstance(key,str)
120 def dict_to_environment(dictionary):
121 result = MiniEnvironment()
123 for key,value in dictionary.iteritems():
128 class MiniApplicative(object):
129 def __init__(self, operative):
130 assert callable(operative)
131 self.operative = operative
133 def __call__(self, pattern, environment):
134 assert isinstance(pattern, MiniObject)
136 return self.operative(pattern, environment)
138 class MiniWrapper(object):
139 def __init__(self, operative):
140 assert isinstance(operative,MiniObject)
141 assert isinstance(operative.py_object, MiniApplicative) or isinstance(operative.py_object, MiniWrapper)
143 self.operative = operative
145 def __call__(self, pattern, environment):
146 assert isinstance(pattern, MiniObject)
148 return self.operative.py_object(evaluate_arguments(pattern, environment), environment)
151 return "<wrapper {}>".format(repr(self.operative))
154 return MiniObject(MiniWrapper(thing))
157 if isinstance(thing.py_object, MiniWrapper):
158 return thing.py_object.operative
160 raise Exception('UnwrapError')
162 def create_symbol(string,**kwargs):
163 if string in SYMBOLS:
164 return SYMBOLS[string]
166 k = MiniObject(MiniSymbol(string), **kwargs)
170 def create_cons_collection(py_collection):
173 for item in reversed(py_collection):
174 result = MiniObject(MiniPair(item, result))
178 def cons_collection_to_py_collection(cons_collection):
179 while cons_collection != NIL:
180 yield car(cons_collection)
181 cons_collection = cdr(cons_collection)
183 token_regex = re.compile(r'''(?mx)
185 (?P<open_parenthese>\()|
186 (?P<close_parenthese>\))|
187 (?P<number>\-?\d+\.\d+|\-?\d+)|
189 (?P<identifier>[_A-Za-z\?\-\+\*/=\>\<]+)|
190 (?P<symbol>\:[_A-Za-z\?\-\+\*/=\>\<]*)
193 def parse_all(source):
194 def parse(matches, index_holder):
195 match = matches[index_holder[0]]
198 if match.group('open_parenthese'):
201 while index_holder[0] < len(matches) and not matches[index_holder[0]].group('close_parenthese'):
202 r.append(parse(matches, index_holder))
204 if index_holder[0] == len(matches):
205 raise Exception('Unmatched parenthese (')
208 return create_cons_collection(r)
210 if match.group('close_parenthese'):
211 raise Exception("Unmatched parenthese )")
213 if match.group('number'):
214 v = float(match.group('number'))
215 if v.is_integer(): v = int(v)
219 start = match.start('number'),
220 end = match.end('number'))
222 if match.group('string'):
224 match.group('string')[1:-1],
225 start = match.start('string'),
226 end = match.end('string'))
228 if match.group('identifier'):
229 return MiniObject(Identifier(
230 match.group('identifier'),
231 start = match.start('identifier'),
232 end = match.end('identifier')))
234 if match.group('symbol'):
235 return create_symbol(
236 match.group('symbol')[1:],
237 start = match.start('symbol'),
238 end = match.end('symbol'))
240 assert False, "I'm not sure how this happened"
242 def parse_all_internal(matches, index_holder):
243 if index_holder[0] == len(matches):
246 parsed_atom = parse(matches, index_holder)
248 return cons(parsed_atom, parse_all_internal(matches, index_holder))
250 matches = list(token_regex.finditer(source))
251 match_index_wrapped = [0]
253 return parse_all_internal(matches, match_index_wrapped)
255 NIL = MiniObject(None)
257 class Boolean(MiniObject):
258 def __init__(self, py_object, **kwargs):
259 super(Boolean,self).__init__(py_object, **kwargs)
262 FALSE = Boolean(False)
265 if isinstance(arg, float):
268 # isinstance(True, int) returns True
269 return isinstance(arg, int) and not isinstance(arg, bool)
271 def py_to_mini(py_object):
272 assert callable(py_object)
274 def wrapped(pattern, environment):
275 result = py_object(*cons_collection_to_py_collection(pattern))
277 if is_number(result) or isinstance(result,MiniPair):
278 return MiniObject(result)
280 if isinstance(result,str):
281 return MiniObject(result)
287 }.get(result, result)
289 return MiniObject(MiniWrapper(MiniObject(MiniApplicative(wrapped))))
291 def apply(applicative, pattern, environment):
292 assert isinstance(applicative, MiniObject)
294 return applicative.py_object(pattern, environment)
296 def evaluate(expression, environment):
297 assert isinstance(expression, MiniObject)
299 if isinstance(expression.py_object, str) or is_number(expression.py_object):
302 if isinstance(expression.py_object, MiniSymbol):
305 if isinstance(expression.py_object, MiniPair):
306 applicative = evaluate(car(expression), environment)
307 arguments = cdr(expression)
309 assert isinstance(applicative, MiniObject)
310 assert isinstance(arguments, MiniObject)
312 if isinstance(applicative.py_object, MiniApplicative) or isinstance(applicative.py_object, MiniWrapper):
313 return apply(applicative, arguments, environment)
315 raise Exception("Expected applicative, got {}".format(applicative.py_object))
317 if isinstance(expression.py_object, Identifier):
318 parent_symbol = create_symbol('__parent__')
320 while environment != None:
321 if cons_dict_has_key(environment, create_symbol(expression.py_object.symbol)) == TRUE:
322 return cons_dict_get(environment, create_symbol(expression.py_object.symbol))
324 if cons_dict_has_key(environment, parent_symbol) == TRUE:
325 environment = cons_dict_get(environment, create_symbol('__parent__'))
327 raise Exception('UndefinedIdentifierError: Undefined identifier {}'.format(expression.py_object.symbol))
330 assert isinstance(string, MiniObject)
332 if isinstance(string.py_object, str):
333 return len(string.py_object)
335 raise Exception("TypeError")
337 def concatenate(l,r):
338 # TODO Implement ropes: http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.14.9450&rep=rep1&type=pdf
339 # TODO Apply this to other collection types
340 if isinstance(l.py_object,str) and isinstance(r.py_object, str):
341 return MiniObject(l.py_object + r.py_object)
343 raise Exception('TypeError')
346 return isinstance(arg, int) and not isinstance(arg, bool)
348 def slice(string, start, end):
349 if not isinstance(string.py_object, str):
350 raise Exception('TypeError')
352 py_string = string.py_object
354 if is_integer(start.py_object):
355 py_start = start.py_object
357 elif start.py_object == None:
361 raise Exception('TypeError')
363 if is_integer(end.py_object):
364 py_end = end.py_object
366 elif end.py_object == None:
367 py_end = len(py_string)
370 raise Exception('TypeError')
372 return MiniObject(py_string[py_start:py_end])
374 def _assert(pattern, environment):
375 def assert_internal(*arguments):
376 if len(arguments) == 0:
377 raise Exception("ArgumentError: assert expects 1 or more arguments, received none")
379 if len(arguments) == 1:
380 description = 'assertion failed'
381 assertion = arguments
384 description = arguments[0].py_object
385 assertion = arguments[1:]
387 if not isinstance(assertion[-1].py_object, bool):
388 raise Exception("TypeError: `assert` expected Boolean assertion but received {} {}".format(type(assertion[-1].py_object), assertion[-1]))
390 if assertion[-1] is TRUE:
393 if assertion[-1] is FALSE:
394 raise Exception("AssertionError: {}".format(description))
398 # Execute in nested scope
399 return py_to_mini(assert_internal).py_object(pattern, nest(environment))
401 def throws(pattern, environment):
402 if cons_collection_len(pattern) != 2:
403 raise Exception("throws? expects 2 argument, received {}".format(len(pattern)))
405 expression = car(pattern)
406 exception = evaluate(car(cdr(pattern)), environment)
408 if not isinstance(exception.py_object, str):
409 raise Exception('throws? expects a string as the second argument')
412 evaluate(expression, environment)
415 except Exception as e:
417 exception_type, message = e.message.split(':',1)
419 exception_type = e.message
421 if exception_type == exception.py_object:
427 if not isinstance(argument, Boolean):
428 raise Exception('TypeError: Expected Boolean but received {}'.format(type(argument)))
433 if argument == FALSE:
438 def evaluate_expressions(expressions, environment):
441 while expressions != NIL:
442 result = evaluate(car(expressions), environment)
443 expressions = cdr(expressions)
447 def cons_collection_len(cons_collection):
450 while cons_collection != NIL:
452 cons_collection = cdr(cons_collection)
456 def define(pattern, environment):
457 if cons_collection_len(pattern) < 2:
458 raise Exception('DefineError: `define` expected two arguments, received {}'.format(cons_collection_len(pattern)))
463 if isinstance(head.py_object, Identifier):
464 identifier = head.py_object.symbol
466 if is_defined(head, environment) == TRUE:
467 raise Exception('AlreadyDefinedError: the identifier {} is already defined'.format(identifier))
469 environment[identifier] = evaluate_expressions(body, environment)
473 elif isinstance(head.py_object, MiniPair):
474 raise Exception('NotImplementedError: Defining patterns is not yet implemented')
477 raise Exception("DefineError")
479 def defined_p(pattern, environment):
480 if cons_collection_len(pattern) != 1:
481 raise Exception("ArgumentError: `defined?` expects 1 argument, received {}".format(len(pattern)))
483 if not isinstance(car(pattern).py_object, Identifier):
484 raise Exception("TypeError: Expected Identifier but got {}".format(type(car(pattern).py_object)))
486 return is_defined(car(pattern), environment)
488 def is_defined(identifier, environment):
489 assert isinstance(identifier, MiniObject)
490 assert isinstance(environment, MiniObject)
492 identifier_symbol = identifier_to_symbol(identifier)
493 parent_symbol = create_symbol('__parent__')
496 if cons_dict_has_key(environment, identifier_symbol) == TRUE:
499 elif cons_dict_has_key(environment, parent_symbol) == TRUE:
500 environment = cons_dict_get(environment, parent_symbol)
505 def _if(pattern, environment):
506 if not cons_collection_len(pattern) in [2,3]:
507 raise Exception("ArgumentError")
509 condition = car(pattern)
510 if_result_true = car(cdr(pattern))
511 if_result_false = car(cdr(cdr(pattern)))
513 result = evaluate(condition, environment)
516 return evaluate(if_result_true, environment)
518 return evaluate(if_result_false, environment)
520 raise Exception("TypeError: `if` expects boolean, received {}".format(type(result)))
522 def nest(environment):
523 isinstance(environment,MiniEnvironment)
525 result = MiniEnvironment()
526 result['__parent__'] = environment
529 # This is vau from John N. Shutt's seminal paper
530 # https://www.wpi.edu/Pubs/ETD/Available/etd-090110-124904/unrestricted/jshutt.pdf
531 # While Greek letters are appropriate for an academic, theoretical context, they make for
532 # poor variable names, so this is tentatively named `operative`
533 def operative(pattern, defining_environment):
534 argument_list_identifier = None
535 argument_identifiers = None
537 calling_environment_identifier = car(cdr(pattern)).py_object.symbol
539 if isinstance(car(pattern).py_object, Identifier):
540 argument_list_identifier = car(pattern).py_object.symbol
542 if calling_environment_identifier == argument_list_identifier:
543 raise Exception("ArgumentError: Argument list identifier `{}` may not be the same as calling environment identifier".format(ai))
545 elif car(pattern).py_object == None or isinstance(car(pattern).py_object, MiniPair):
546 if not all([isinstance(arg.py_object, Identifier) for arg in cons_collection_to_py_collection(car(pattern))]):
547 raise Exception("ArgumentError: Unexpected {} {}".format(type(arg),arg))
549 argument_identifiers = [ai.py_object.symbol for ai in cons_collection_to_py_collection(car(pattern))]
552 for ai in argument_identifiers:
554 raise Exception("ArgumentError: Argument `{}` already defined".format(ai))
556 if calling_environment_identifier == ai:
557 raise Exception("ArgumentError: Argument `{}` may not be the same as calling environment identifier".format(ai))
562 raise Exception("ArgumentError: `operative` expected identifier or cons-list as first argument, received {}".format(type(car(pattern).py_object)))
564 if not isinstance(car(cdr(pattern)).py_object,Identifier):
565 raise Exception("ArgumentError: The second argument to `operative` should be an identifer")
567 def result(calling_pattern, calling_environment):
568 local_environment = nest(defining_environment)
570 assert (argument_list_identifier == None) != (argument_identifiers == None)
571 if argument_list_identifier != None:
572 local_environment[argument_list_identifier] = calling_pattern
574 if argument_identifiers != None:
575 if not cons_collection_len(calling_pattern) == len(argument_identifiers):
576 raise Exception("ArgumentError: operative expected {} arguments, received {}".format(len(argument_identifiers),len(calling_pattern)))
578 calling_pattern = list(cons_collection_to_py_collection(calling_pattern))
580 for i in range(len(argument_identifiers)):
581 local_environment[argument_identifiers[i]] = calling_pattern[i]
583 local_environment[calling_environment_identifier] = calling_environment
585 return evaluate_expressions(cdr(cdr(pattern)), local_environment)
587 return MiniObject(MiniApplicative(result))
589 def read_file(filename):
590 assert isinstance(filename, MiniObject)
592 with open(filename.py_object, 'r') as f:
595 def write_file(filename, string):
596 assert isinstance(filename, MiniObject)
597 assert isinstance(string, MiniObject)
599 with open(filename.py_object, 'w') as f:
600 f.write(string.py_object)
603 if isinstance(l, MiniObject) and isinstance(r, MiniObject):
607 if is_number(l) and is_number(r):
610 raise Excepion('TypeError')
613 if isinstance(l, MiniObject) and isinstance(r, MiniObject):
617 if is_number(l) and is_number(r):
620 raise Excepion('TypeError')
623 if isinstance(l, MiniObject) and isinstance(r, MiniObject):
627 if is_number(l) and is_number(r):
630 raise Excepion('TypeError')
633 if isinstance(l, MiniObject) and isinstance(r, MiniObject):
637 if is_number(l) and is_number(r):
638 if isinstance(l,int) and isinstance(r,int) and l % r != 0:
643 raise Excepion('TypeError')
646 if isinstance(l, MiniObject) and isinstance(r, MiniObject):
650 if is_number(l) and is_number(r):
653 raise Excepion('TypeError')
656 if isinstance(l, MiniObject) and isinstance(r, MiniObject):
660 if is_number(l) and is_number(r):
663 raise Excepion('TypeError')
666 assert isinstance(l,MiniObject)
667 assert isinstance(r,MiniObject)
669 return l.py_object == r.py_object
672 assert isinstance(l,MiniObject)
673 assert isinstance(r,MiniObject)
675 if is_number(l.py_object) and is_number(r.py_object):
676 return l.py_object < r.py_object
678 if isinstance(l.py_object,str) and isinstance(r.py_object,str):
679 return l.py_object < r.py_object
681 if isinstance(l.py_object,MiniSymbol) and isinstance(r.py_object,MiniSymbol):
682 return l.py_object.string < r.py_object.string
684 raise TypeError('`<` expected number or string, received {} and {}'.format(l.py_object, r.py_object))
687 assert isinstance(l,MiniObject)
688 assert isinstance(r,MiniObject)
690 if is_number(l.py_object) and is_number(r.py_object):
691 return l.py_object > r.py_object
693 if isinstance(l.py_object,str) and isinstance(r.py_object,str):
694 return l.py_object > r.py_object
696 if isinstance(l.py_object,MiniSymbol) and isinstance(r.py_object,MiniSymbol):
697 return l.py_object.string > r.py_object.string
699 raise TypeError('`>` expected number or string, received {} and {}'.format(l.py_object, r.py_object))
702 return lt(l,r) or eq(l,r)
705 return gt(l,r) or eq(l,r)
708 return MiniObject(MiniPair(l,r))
711 return p.py_object.car
714 return p.py_object.cdr
716 def is_cons_list(mini_object):
717 assert isinstance(mini_object,MiniObject)
719 if eq(mini_object,NIL) or isinstance(mini_object.py_object,MiniPair):
724 def cons_dict_set(dictionary,key,value):
725 assert isinstance(dictionary,MiniObject)
726 assert isinstance(key,MiniObject)
727 assert isinstance(value,MiniObject)
729 if eq(dictionary,NIL):
730 return cons(cons(key,value),cons(NIL,NIL))
732 current_node_key = car(car(dictionary))
734 if lt(key,current_node_key):
738 cons_dict_set(car(cdr(dictionary)), key, value),
739 cdr(cdr(dictionary))))
741 if gt(key,current_node_key):
745 car(cdr(dictionary)),
746 cons_dict_set(cdr(cdr(dictionary)), key, value)))
748 if eq(key,current_node_key):
749 return cons(cons(key,value), cdr(dictionary))
753 def cons_dict_get(dictionary,key):
754 assert isinstance(dictionary, MiniObject)
755 assert isinstance(key, MiniObject)
757 if eq(dictionary,NIL):
758 raise Exception('KeyError: Dictionary does not contain key "{}"'.format(key))
760 current_node_key = car(car(dictionary))
762 if lt(key, current_node_key):
763 return cons_dict_get(car(cdr(dictionary)), key)
765 if gt(key, current_node_key):
766 return cons_dict_get(cdr(cdr(dictionary)), key)
768 if eq(key, current_node_key):
769 return cdr(car(dictionary))
771 def cons_dict_has_key(dictionary,key):
772 assert isinstance(dictionary, MiniObject)
773 assert isinstance(key, MiniObject)
775 if eq(dictionary,NIL):
778 current_node_key = car(car(dictionary))
780 if lt(key, current_node_key):
781 return cons_dict_has_key(car(cdr(dictionary)), key)
783 if gt(key, current_node_key):
784 return cons_dict_has_key(cdr(cdr(dictionary)), key)
786 if eq(key, current_node_key):
789 def identifier_to_symbol(identifier):
790 assert isinstance(identifier, MiniObject)
792 if not isinstance(identifier.py_object, Identifier):
793 raise Exception('`identifier->symbol` expected identifier, received {}'.format(type(identifier.py_object)))
795 return create_symbol(identifier.py_object.symbol)
798 assert isinstance(string,MiniObject)
800 if not isinstance(string.py_object,str):
801 raise Exception("TypeError: `read` expected string, got {}".format(type(strin.py_object)))
803 result = parse_all(string.py_object)
805 assert cdr(result) == NIL
815 # Builtin comparison functions
816 '=' : py_to_mini(eq),
817 '<' : py_to_mini(lt),
818 '>' : py_to_mini(gt),
819 '<=' : py_to_mini(le),
820 '>=' : py_to_mini(ge),
822 # Builtin conversion functions
823 'identifier->symbol' : py_to_mini(identifier_to_symbol),
825 # Builtin type test functions
826 'cons-list?' : py_to_mini(is_cons_list),
827 'identifier?' : py_to_mini(is_identifier),
829 # Builtin general functions
830 'evaluate' : py_to_mini(evaluate),
831 'evaluate-expressions' : py_to_mini(evaluate_expressions),
832 'print' : py_to_mini(print),
833 'prompt' : py_to_mini(raw_input),
834 'read-file' : py_to_mini(read_file),
835 'write-file' : py_to_mini(write_file),
836 'read' : py_to_mini(read),
837 'wrap' : py_to_mini(wrap),
838 'unwrap' : py_to_mini(unwrap),
840 # Builtin number functions
841 '+' : py_to_mini(add),
842 '-' : py_to_mini(subtract),
843 '*' : py_to_mini(multiply),
844 '/' : py_to_mini(divide),
845 '//' : py_to_mini(idivide),
846 'mod' : py_to_mini(mod),
848 # Builtin pair functions
849 'cons' : py_to_mini(cons),
850 'car' : py_to_mini(car),
851 'cdr' : py_to_mini(cdr),
853 # Builtin cons dictionary functions
854 'cons-dict-set' : py_to_mini(cons_dict_set),
855 'cons-dict-get' : py_to_mini(cons_dict_get),
857 # Builtin string functions
858 'concatenate' : py_to_mini(concatenate),
859 'length' : py_to_mini(length),
860 'slice' : py_to_mini(slice),
862 # Builtin boolean functions
863 'not' : py_to_mini(_not),
865 # Builtin special forms
866 'assert' : MiniObject(MiniApplicative(_assert)),
867 'define' : MiniObject(MiniApplicative(define)),
868 'defined?' : MiniObject(MiniApplicative(defined_p)),
869 'if' : MiniObject(MiniApplicative(_if)),
870 'operative' : MiniObject(MiniApplicative(operative)),
871 'throws?' : MiniObject(MiniApplicative(throws)),
874 builtins = dict_to_environment(builtins)
876 if __name__ == '__main__':
880 arguments = sys.argv[1:]
882 predefineds = nest(builtins)
883 predefineds_filename = os.path.join(os.path.dirname(os.path.realpath(__file__)), 'predefineds.mini')
885 with open(predefineds_filename, 'r') as predefineds_file:
886 predefineds_source = predefineds_file.read()
889 evaluate_expressions(parse_all(predefineds_source), predefineds)
892 traceback.print_exc()
894 if len(arguments) == 0:
895 environment = nest(predefineds)
898 source = raw_input('>>> ')
901 print(evaluate_expressions(parse_all(source), environment))
904 traceback.print_exc()
907 filename = arguments[0]
908 arguments = arguments[1:]
910 environment = nest(predefineds)
911 environment['__file__'] = MiniObject(os.path.join(os.path.realpath(filename)))
912 environment['__arguments__'] = create_cons_collection(map(MiniObject,arguments))
914 with open(filename,'r') as f:
918 print(evaluate_expressions(parse_all(source), environment))
921 traceback.print_exc()