importing python metacircular evaluator into git
[boa.git] / boa.py
blob340eab70375b9b98e14f6af6bc9cc996090500e6
1 # Scheme in Python
3 # This is my first attempt to write LISP in Python. The code is
4 # based on the metacircular evaluator explored in ch4, SICP. I have
5 # kept it as pedagogic as possible. For this reason it is not
6 # pragmatic. There is a partial macro implementation (define-syntax
7 # without the ellipsis). Additionally it is also possible to access Python
8 # modules/objects from Scheme and vice versa (look at the module import
9 # hooks).
11 # Honestly, I am planning to write a `real' LISP in Python,
12 # keeping in mind the best of both worlds: syntax/macros in Scheme;
13 # libraries in Python.
15 # See tests.py for test cases
17 # - Basic Scheme
18 # - Access Python in Scheme
19 # - Access Scheme in Python
20 # - pedagogic source code
21 # - An inconceivably inefficient evaluator
23 __author__ = 'Sridhar Ratna'
25 import sys, os, ihooks
27 ## lisp emulation functions
28 ###########################
30 def error(s):
31 raise s
33 class tagged(object):
34 def __init__(self, tag, value):
35 self.tag = tag
36 self.value = value
37 def __eq__(self, other):
38 return type(other) is tagged and \
39 self.tag == other.tag and self.value == other.value
40 def __repr__(self):
41 return "<TAG:%s %s >" % (self.tag, self.value)
43 def symbol(string): return tagged("symbol", string)
44 def symbol_p(o): return type(o) is tagged and o.tag == "symbol"
45 def symbol_to_string(o): return o.value
47 def cons(x, y): return [x, y]
48 def car(pair): return pair[0]
49 def cdr(pair): return pair[1]
50 def cadr(x): return car(cdr(x))
51 def caar(x): return car(car(x))
52 def cddr(x): return cdr(cdr(x))
53 def caddr(x): return car(cdr(cdr(x)))
54 def caadr(x): return car(car(cdr(x)))
55 def cadar(x): return car(cdr(car(x)))
56 def cdadr(x): return cdr(car(cdr(x)))
57 def caddr(x): return car(cdr(cdr(x)))
58 def cadddr(x): return car(cdr(cdr(cdr(x))))
60 def pair_p(o): return type(o) is list and len(o)==2
62 def set_caR(pair, value):
63 assert pair_p(pair)
64 pair[0] = value
65 return symbol("ok")
67 def set_cdR(pair, value):
68 assert pair_p(pair)
69 pair[1] = value
70 return symbol("ok")
72 def slist(*args):
73 if len(args) == 0:
74 return None
75 else:
76 return cons(args[0], slist(*args[1:]))
78 def smap(func, sl):
79 if null_p(sl):
80 return null
81 else:
82 return cons(func(car(sl)),
83 smap(func, cdr(sl)))
85 def slength(sl):
86 if null_p(sl):
87 return 0
88 else:
89 return 1+slength(cdr(sl))
91 def smember(sl, e):
92 if null_p(sl):
93 return False
94 elif eq_p(car(sl), e):
95 return True
96 else:
97 return smember(cdr(sl), e)
99 null = slist()
100 def null_p(o): return o is None # ?? coerce
102 def eq_p(o1, o2):
103 # ??
104 return o1 == o2 # ??
106 def number_p(o):
107 return type(o) in (int, long, float)
109 def string_p(o):
110 return type(o) is str
112 # coercion (TODO)
114 def slist2pylist(slst):
115 if null_p(slst):
116 return []
117 else:
118 return [car(slst)] + slist2pylist(cdr(slst))
120 def dot(o, *args):
121 "a.b.c in Python is translated to (dot a b c) in Lisp"
122 for arg in args:
123 o = getattr(o, arg)
124 return o
126 def l2py(o):
127 if null_p(o):
128 # there is no equivalent of None in Lisp as of now
129 # '() is considered nothing more than an empty list
130 return list()
131 elif pair_p(o):
132 # there is no way we can coerce a `pair' only to
133 # get it back as it was
134 # we also make a deep copy using `l2py' itself
135 return map(l2py, slist2pylist(o))
136 else:
137 return o
139 def py2l(o):
140 if type(o) in (list, tuple):
141 return slist(*o)
142 else:
143 return o
145 py_apply = apply
147 ## eval/appy
148 ############
150 def eval(exp, env):
151 if is_self_evaluating(exp):
152 return exp
153 if is_variable(exp):
154 return lookup_variable_value(exp, env)
155 if is_quoted(exp):
156 return text_of_quotation(exp)
157 if is_assignment(exp):
158 return eval_assignment(exp, env)
159 if is_definition(exp):
160 return eval_definition(exp, env)
161 if is_syntax_definition(exp):
162 return eval_syntax_definition(exp, env)
163 if is_if(exp):
164 return eval_if(exp, env)
165 if is_lambda(exp):
166 return make_procedure(lambda_parameters(exp),
167 lambda_body(exp),
168 env)
169 if is_begin(exp):
170 return eval_sequence(begin_actions(exp), env)
171 if is_cond(exp):
172 return eval(cond_to_if(exp), env)
173 if is_application(exp):
174 op = eval(operator(exp), env)
175 if syntax_rules_p(op):
176 return eval(transform_syntax(op, operands(exp)), env)
177 else:
178 return apply(op, list_of_values(operands(exp), env))
179 # else
180 error("Unknown expression type -- EVAL: %s" % exp)
182 def apply(procedure, arguments):
183 if is_primitive_procedure(procedure):
184 return apply_primitive_procedure(procedure, arguments)
185 if is_compound_procedure(procedure):
186 return eval_sequence(
187 procedure_body(procedure),
188 extend_environment(procedure_parameters(procedure),
189 arguments,
190 procedure_environment(procedure)))
191 if is_python_callable(procedure):
192 return apply_python_procedure(procedure, arguments)
193 # else
194 error("Unknown procedure type -- APPLY: %s" % procedure)
196 def list_of_values(exps, env):
197 if no_operands(exps):
198 return null
199 else:
200 return cons(eval(first_operand(exps), env),
201 list_of_values(rest_operands(exps), env))
203 def eval_if(exp, env):
204 if is_true(eval(if_predicate(exp), env)):
205 return eval(if_consequent(exp), env)
206 else:
207 return eval(if_alternative(exp), env)
209 def eval_sequence(exps, env):
210 if is_last_exp(exps):
211 return eval(first_exp(exps), env)
212 else:
213 eval(first_exp(exps), env)
214 return eval_sequence(rest_exps(exps), env)
216 def eval_assignment(exp, env):
217 set_variable_valuE(assignment_variable(exp),
218 eval(assignment_value(exp), env),
219 env)
220 return symbol("ok")
222 def eval_definition(exp, env):
223 define_variablE(definition_variable(exp),
224 eval(definition_value(exp), env),
225 env)
226 return symbol("ok")
228 def is_self_evaluating(exp):
229 return number_p(exp) or string_p(exp)
231 def is_variable(exp):
232 return symbol_p(exp)
234 def is_quoted(exp):
235 return is_tagged_list(exp, symbol("quote"))
237 def text_of_quotation(exp):
238 return cadr(exp)
240 def is_tagged_list(exp, tag):
241 return pair_p(exp) and eq_p(car(exp), tag)
243 def is_assignment(exp):
244 return is_tagged_list(exp, symbol("set!"))
246 def assignment_variable(exp):
247 return cadr(exp)
249 def assignment_value(exp):
250 return caddr(exp)
252 def is_definition(exp):
253 return is_tagged_list(exp, symbol("define"))
255 def definition_variable(exp):
256 if symbol_p(cadr(exp)):
257 return cadr(exp)
258 else:
259 return caadr(exp)
261 def definition_value(exp):
262 if symbol_p(cadr(exp)):
263 return caddr(exp)
264 else:
265 return make_lambda(cdadr(exp),
266 cddr(exp))
268 def is_lambda(exp):
269 return is_tagged_list(exp, symbol("lambda"))
271 def lambda_parameters(exp):
272 return cadr(exp)
274 def lambda_body(exp):
275 return cddr(exp)
277 def make_lambda(parameters, body):
278 return cons(symbol("lambda"),
279 cons(parameters, body))
281 def is_if(exp):
282 return is_tagged_list(exp, symbol("if"))
284 def if_predicate(exp):
285 return cadr(exp)
287 def if_consequent(exp):
288 return caddr(exp)
290 def if_alternative(exp):
291 if not null_p(cdddr(exp)):
292 return cadddr(exp)
293 else:
294 return symbol("FALSE")
296 def make_if(predicate, consequent, alternative):
297 return slist(symbol("IF"),
298 predicate, consequent, alternative)
300 def is_begin(exp):
301 return is_tagged_list(exp, symbol("begin"))
303 def begin_actions(exp):
304 return cdr(exp)
306 def is_last_exp(seq):
307 return null_p(cdr(seq))
309 def first_exp(seq):
310 return car(seq)
312 def rest_exps(seq):
313 return cdr(seq)
315 def sequence_to_exp(seq):
316 if null_p(seq):
317 return seq
318 elif is_last_exp(seq):
319 return first_exp(seq)
320 else:
321 return make_begin(seq)
323 def make_begin(seq):
324 return cons(symbol("begin"),
325 seq)
327 def is_application(exp):
328 return pair_p(exp)
330 def operator(exp):
331 return car(exp)
333 def operands(exp):
334 return cdr(exp)
336 def no_operands(ops):
337 return null_p(ops)
339 def first_operand(ops):
340 return car(ops)
342 def rest_operands(ops):
343 return cdr(ops)
345 # The following are `derived' expressions (apt to be macros)
347 def is_cond(exp):
348 return is_tagged_list(exp, symbol("cond"))
350 def cond_clauses(exp):
351 return cdr(exp)
353 def is_cond_else_clause(clause):
354 return eq_p(cond_predicate(clause),
355 symbol("ELSE"))
357 def cond_predicate(clause):
358 return car(clause)
360 def cond_actions(clause):
361 return cdr(clause)
363 def cond_to_if(exp):
364 return expand_clauses(cond_clauses(exp))
366 def expand_clauses(clauses):
367 if null_p(clauses):
368 return symbol("FALSE")
369 else:
370 first = car(clauses)
371 rest = cdr(clauses)
372 if is_cond_else_clause(first):
373 if null_p(rest):
374 sequence_to_exp(cond_actions(first))
375 else:
376 error("ELSE clause isn't last -- COND->IF: %s'" % clauses)
377 else:
378 return make_if(cond_predicate(first),
379 sequence_to_exp(cond_actions(first)),
380 expand_clauses(rest))
382 ## evaluator data structures
383 ############################
385 def is_true(x):
386 return l2py(x) is not False # ??
388 def is_false(x):
389 return l2py(x) is False
391 def make_procedure(parameters, body, env):
392 return slist(symbol("procedure"),
393 parameters, body, env)
395 def is_compound_procedure(p):
396 return is_tagged_list(p, symbol("procedure"))
398 def procedure_parameters(p):
399 return cadr(p)
401 def procedure_body(p):
402 return caddr(p)
404 def procedure_environment(p):
405 return cadddr(p)
407 def enclosing_environment(env):
408 return cdr(env)
410 def first_frame(env):
411 return car(env)
413 the_empty_environment = slist()
415 def make_frame(variables, values):
416 return cons(variables, values)
418 def frame_variables(frame):
419 return car(frame)
421 def frame_values(frame):
422 return cdr(frame)
424 def add_binding_to_framE(var, val, frame):
425 set_caR(frame, cons(var, car(frame)))
426 set_cdR(frame, cons(val, cdr(frame)))
428 def extend_environment(vars, vals, base_env):
429 if slength(vars) == slength(vals):
430 return cons(make_frame(vars, vals), base_env)
431 else:
432 error("Too few/many arguments supplied: %s, %s" % (vars, vals))
434 # debug
435 def print_environment(env, depth=1):
436 print '%sEE %s' % (' '*depth, first_frame(env))
437 if not null_p(enclosing_environment(env)):
438 print_environment(enclosing_environment(env), depth+2)
440 def do_variable(var, env, match_thunk, next_thunk=None):
441 def env_loop(env):
442 def scan(vars, vals):
443 if null_p(vars):
444 if next_thunk:
445 return next_thunk()
446 else:
447 return env_loop(enclosing_environment(env))
448 elif eq_p(var, car(vars)):
449 return match_thunk(vars, vals)
450 else:
451 return scan(cdr(vars), cdr(vals))
452 if eq_p(env, the_empty_environment):
453 raise NameError, "Unbound LISP variable: %s" % var
454 else:
455 frame = first_frame(env)
456 return scan(frame_variables(frame), frame_values(frame))
457 return env_loop(env)
459 def lookup_variable_value(var, env):
460 assert symbol_p(var)
461 return do_variable(var, env,
462 lambda vars, vals: car(vals))
464 def set_variable_valuE(var, val, env):
465 assert symbol_p(var)
466 return do_variable(var, env,
467 lambda vars, vals: set_caR(vals, val))
469 def define_variablE(var, val, env):
470 assert symbol_p(var)
471 return do_variable(var, env,
472 lambda vars, vals: set_caR(vals, val),
473 lambda : add_binding_to_framE(var, val,
474 first_frame(env)))
476 ## parser
477 #########
479 import re
480 c = re.compile
482 PATTERNS = [
483 ('whitespace', c(r'(\s+)')),
484 ('comment', c(r'(;[^\n]*)')),
485 ('(', c(r'(\()')),
486 (')', c(r'(\))')),
487 ('number', c(r'''( [+\-]? ## optional sign,
488 (?: ## followed by some
489 ## decimals
490 \d+\.\d+
491 | \d+\.
492 | \.\d+
493 | \d+
496 ''',
497 re.VERBOSE)),
498 ('symbol', c(r'''([a-zA-Z\+\=\?\!\@\#\$\%\^\&\*\-\/\.\>\<]
499 [\w\+\=\?\!\@\#\$\%\^\&\*\-\/\.\>\<]*)''',
500 re.VERBOSE)),
501 ('string', c(r'''
503 (([^\"] | \\")*)
505 ''',
506 re.VERBOSE)),
507 ("'", c(r'(\')')),
508 ('`', c(r'(`)')),
509 (',', c(r'(,)')),
512 def tokenize(s):
513 tokens = []
514 while s:
515 m = None
516 for type, regex in PATTERNS:
517 m = regex.match(s)
518 if m:
519 token = m.group(1)
520 tokens.append((type, token))
521 s = s[m.span()[1]:]
522 break
523 if not m:
524 error("TOKENIZE error from: %s..." % s[:20])
525 return tokens
527 def filter_executable_tokens(tokens):
528 return filter(
529 lambda x: x[0] not in ('whitespace', 'comment'),
530 tokens)
532 def parse(text):
533 tokens = filter_executable_tokens(tokenize(text))
534 def parse_till_end(n):
535 if n == len(tokens):
536 return null
537 else:
538 sexp, n = parse_sexp(tokens, n)
539 return cons(sexp, parse_till_end(n))
540 return sequence_to_exp(parse_till_end(0))
542 def parse_sexp(tokens, fr):
543 if tokens[fr][0] is 'string':
544 return tokens[fr][1], fr+1
545 if tokens[fr][0] is 'number':
546 return int(tokens[fr][1]), fr+1 # ??
547 if tokens[fr][0] is 'symbol':
548 return symbol(tokens[fr][1]), fr+1
549 if tokens[fr][0] is "'":
550 e, fr = parse_sexp(tokens, fr+1)
551 return slist(symbol("quote"), e), fr
552 if tokens[fr][0] == '(':
553 return parse_rest_of_sexps(tokens, fr+1)
554 error("PARSE error -- Invalid/unsupported token: %s" % tokens[fr][0])
556 def parse_rest_of_sexps(tokens, fr):
557 if tokens[fr][0] == ')':
558 return null, fr+1
559 else:
560 e, fr = parse_sexp(tokens, fr)
561 r, fr = parse_rest_of_sexps(tokens, fr)
562 return cons(e, r), fr
564 ## macros (partial)
565 #########
567 # Note that these are `first-class' macros. And so the
568 # `environment' need not distinguish between variables
569 # and keywords (macro names). `eval' looks up the operator
570 # object and determines if it is a procedure application or
571 # a macro expansion (see syntax_rules_p)
572 # Ideally, environment table must distinguish between variables
573 # and keywords. This helps in several ways.
574 # - syntax-case can be implemented (and syntax-rules in in terms of it)
575 # - No need to `eval' operator to transform the syntax
578 def syntax_rules(l, p): return tagged("syntax-rules", cons(l, p))
579 def syntax_rules_p(o): return type(o) is tagged and o.tag == "syntax-rules"
580 def literals(sr):
581 return car(sr)
582 def first_pattern(sr):
583 return cdr(caar(cdr(sr)))
584 def first_clause(sr):
585 return cadar(cdr(sr))
587 def is_syntax_definition(exp):
588 return is_tagged_list(exp, symbol("define-syntax"))
590 def eval_syntax_definition(exp, env):
591 define_variablE(cadr(exp),
592 eval_syntax_transfomer(caddr(exp)),
593 env)
595 def eval_syntax_transfomer(exp):
596 if not eq_p(car(exp), symbol("syntax-rules")):
597 error("only SYNTAX-RULES is supported: %s" % exp)
598 return syntax_rules(cadr(exp), cddr(exp))
600 def binding_get(binding, symbol):
601 return binding[symbol_to_string(symbol)]
602 def binding_put(binding, symbol, value):
603 binding[symbol_to_string(symbol)] = value
604 def binding_in(binding, symbol):
605 return symbol_to_string(symbol) in binding
607 def transform_syntax(syntax_rules, operands):
608 def transform_loop(rules):
609 if null_p(rules):
610 error("No PATTERN matched -- syntax-rules: %s" % operands)
611 else:
612 binding = {}
613 if match(first_pattern(rules), literals(rules), operands, binding):
614 return expand(first_clause(rules), binding)
615 else:
616 return transform_loop(cdr(rules))
617 return transform_loop(syntax_rules.value)
619 def match(pattern, literals, operands, binding):
620 if null_p(pattern):
621 return null_p(operands)
622 if null_p(operands):
623 return False
624 if symbol_p(car(pattern)):
625 if not smember(literals, car(pattern)):
626 binding_put(binding, car(pattern), car(operands))
627 elif pair_p(car(pattern)):
628 if not match(car(pattern), literals, car(operands), binding):
629 return False
630 else:
631 error("Invalid PATTERN: %s" % car(pattern))
632 return match(cdr(pattern), literals, cdr(operands), binding)
634 def expand(clause, binding):
635 if pair_p(clause):
636 return cons(expand(car(clause), binding),
637 expand(cdr(clause), binding))
638 elif symbol_p(clause) and binding_in(binding, clause):
639 return binding_get(binding, clause)
640 else:
641 return clause
644 ## runtime
645 ##########
647 def setup_environment():
648 initial_env = extend_environment(primitive_procedure_names(),
649 primitive_procedure_objects(),
650 the_empty_environment)
651 define_variablE(symbol("true"), py2l(True), initial_env)
652 define_variablE(symbol("false"), py2l(False), initial_env)
653 return initial_env
655 # primitive procedures
657 def is_primitive_procedure(proc):
658 return is_tagged_list(proc, symbol("primitive"))
660 def primitive_implementation(proc):
661 return cadr(proc)
663 # ??
664 primitive_procedures = slist(
665 slist(symbol("car"), car),
666 slist(symbol("cdr"), cdr),
667 slist(symbol("cons"), cons),
668 slist(symbol("null?"), null_p),
669 slist(symbol("list"), slist),
670 slist(symbol("+"), lambda *args: sum(args)),
671 slist(symbol("."), dot),
672 slist(symbol("import"), lambda m: __import__(m)))
674 def primitive_procedure_names():
675 return smap(car, primitive_procedures)
677 def primitive_procedure_objects():
678 return smap(lambda p: slist(symbol("primitive"), cadr(p)),
679 primitive_procedures)
681 def apply_primitive_procedure(proc, args):
682 return py_apply(
683 primitive_implementation(proc),
684 slist2pylist(args))
686 def apply_python_procedure(p, args):
687 return py_apply(p, l2py(args))
689 def is_python_callable(procedure):
690 return callable(procedure)
693 class LispModule:
695 def __init__(self, module_path, parent_env):
696 self.env = extend_environment(null, null,
697 parent_env)
698 self.value = eval(
699 parse(open(module_path).read()),
700 self.env)
702 def __nonzero__(self):
703 # `if m: ..' looks up m.__nonzero__
704 return True
706 def __getattr__(self, attr):
707 return lookup_variable_value(symbol(attr), self.env)
709 class LispModuleLoader(ihooks.ModuleLoader):
711 def __init__(self, env):
712 self.env = env
713 ihooks.ModuleLoader.__init__(self)
714 print "INIT"
716 def find_module_in_dir(self, name, dir, allow_packages=1):
717 if dir:
718 return None, name, ('', '', "lisp-module")
719 else:
720 ihooks.ModuleLoader.find_module_in_dir(
721 self, name, dir, allow_packages)
723 def load_module(self, name, stuff):
724 print "LOAD"
725 file, filename, info = stuff
726 (suff, mode, type) = info
727 if type == "lisp-module":
728 m = self._import_module(filename)
729 m.__file__ = filename
730 return m
731 else:
732 return ihooks.ModuleLoader.load_module(self, name, stuff)
734 def _import_module(self, module):
735 if module in sys.modules:
736 return sys.modules[module]
737 else:
738 m = LispModule(module, self.env)
739 sys.modules[module] = m
740 return m
743 input_prompt = ";;; M-Eval input: "
744 output_prompt = ";;; M-Eval value: "
746 class Interpreter:
748 def __init__(self):
749 self.the_global_environment = setup_environment()
751 def push(self, text):
752 return eval(parse(text), self.the_global_environment)
754 def driver_loop(self):
755 while True:
756 print "\n%s" % input_prompt
757 input = raw_input() # ??
758 output = eval(parse(input), self.the_global_environment)
759 print output_prompt
760 self.user_print(output)
762 def user_print(self, object):
763 if is_compound_procedure(object):
764 print slist(symbol("COMPOUND-PROCEDURE"),
765 procedure_parameters(object),
766 procedure_body(object),
767 symbol("<procedure-env>"))
768 print object
769 else:
770 # ??
771 print object
774 def install():
775 "Install the default interpreter"
776 interpreter = Interpreter()
777 ihooks.install(ihooks.ModuleImporter(
778 LispModuleLoader(interpreter.the_global_environment)))
781 if __name__ == "__main__":
782 Interpreter().driver_loop()