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
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
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 ###########################
34 def __init__(self
, tag
, value
):
37 def __eq__(self
, other
):
38 return type(other
) is tagged
and \
39 self
.tag
== other
.tag
and self
.value
== other
.value
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
):
67 def set_cdR(pair
, value
):
76 return cons(args
[0], slist(*args
[1:]))
82 return cons(func(car(sl
)),
89 return 1+slength(cdr(sl
))
94 elif eq_p(car(sl
), e
):
97 return smember(cdr(sl
), e
)
100 def null_p(o
): return o
is None # ?? coerce
107 return type(o
) in (int, long, float)
110 return type(o
) is str
114 def slist2pylist(slst
):
118 return [car(slst
)] + slist2pylist(cdr(slst
))
121 "a.b.c in Python is translated to (dot a b c) in Lisp"
128 # there is no equivalent of None in Lisp as of now
129 # '() is considered nothing more than an empty list
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
))
140 if type(o
) in (list, tuple):
151 if is_self_evaluating(exp
):
154 return lookup_variable_value(exp
, env
)
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
)
164 return eval_if(exp
, env
)
166 return make_procedure(lambda_parameters(exp
),
170 return eval_sequence(begin_actions(exp
), env
)
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
)
178 return apply(op
, list_of_values(operands(exp
), env
))
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
),
190 procedure_environment(procedure
)))
191 if is_python_callable(procedure
):
192 return apply_python_procedure(procedure
, arguments
)
194 error("Unknown procedure type -- APPLY: %s" % procedure
)
196 def list_of_values(exps
, env
):
197 if no_operands(exps
):
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
)
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
)
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
),
222 def eval_definition(exp
, env
):
223 define_variablE(definition_variable(exp
),
224 eval(definition_value(exp
), env
),
228 def is_self_evaluating(exp
):
229 return number_p(exp
) or string_p(exp
)
231 def is_variable(exp
):
235 return is_tagged_list(exp
, symbol("quote"))
237 def text_of_quotation(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
):
249 def assignment_value(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
)):
261 def definition_value(exp
):
262 if symbol_p(cadr(exp
)):
265 return make_lambda(cdadr(exp
),
269 return is_tagged_list(exp
, symbol("lambda"))
271 def lambda_parameters(exp
):
274 def lambda_body(exp
):
277 def make_lambda(parameters
, body
):
278 return cons(symbol("lambda"),
279 cons(parameters
, body
))
282 return is_tagged_list(exp
, symbol("if"))
284 def if_predicate(exp
):
287 def if_consequent(exp
):
290 def if_alternative(exp
):
291 if not null_p(cdddr(exp
)):
294 return symbol("FALSE")
296 def make_if(predicate
, consequent
, alternative
):
297 return slist(symbol("IF"),
298 predicate
, consequent
, alternative
)
301 return is_tagged_list(exp
, symbol("begin"))
303 def begin_actions(exp
):
306 def is_last_exp(seq
):
307 return null_p(cdr(seq
))
315 def sequence_to_exp(seq
):
318 elif is_last_exp(seq
):
319 return first_exp(seq
)
321 return make_begin(seq
)
324 return cons(symbol("begin"),
327 def is_application(exp
):
336 def no_operands(ops
):
339 def first_operand(ops
):
342 def rest_operands(ops
):
345 # The following are `derived' expressions (apt to be macros)
348 return is_tagged_list(exp
, symbol("cond"))
350 def cond_clauses(exp
):
353 def is_cond_else_clause(clause
):
354 return eq_p(cond_predicate(clause
),
357 def cond_predicate(clause
):
360 def cond_actions(clause
):
364 return expand_clauses(cond_clauses(exp
))
366 def expand_clauses(clauses
):
368 return symbol("FALSE")
372 if is_cond_else_clause(first
):
374 sequence_to_exp(cond_actions(first
))
376 error("ELSE clause isn't last -- COND->IF: %s'" % clauses
)
378 return make_if(cond_predicate(first
),
379 sequence_to_exp(cond_actions(first
)),
380 expand_clauses(rest
))
382 ## evaluator data structures
383 ############################
386 return l2py(x
) is not False # ??
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
):
401 def procedure_body(p
):
404 def procedure_environment(p
):
407 def enclosing_environment(env
):
410 def first_frame(env
):
413 the_empty_environment
= slist()
415 def make_frame(variables
, values
):
416 return cons(variables
, values
)
418 def frame_variables(frame
):
421 def frame_values(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
)
432 error("Too few/many arguments supplied: %s, %s" % (vars, vals
))
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):
442 def scan(vars, vals
):
447 return env_loop(enclosing_environment(env
))
448 elif eq_p(var
, car(vars)):
449 return match_thunk(vars, vals
)
451 return scan(cdr(vars), cdr(vals
))
452 if eq_p(env
, the_empty_environment
):
453 raise NameError, "Unbound LISP variable: %s" % var
455 frame
= first_frame(env
)
456 return scan(frame_variables(frame
), frame_values(frame
))
459 def lookup_variable_value(var
, env
):
461 return do_variable(var
, env
,
462 lambda vars, vals
: car(vals
))
464 def set_variable_valuE(var
, val
, env
):
466 return do_variable(var
, env
,
467 lambda vars, vals
: set_caR(vals
, val
))
469 def define_variablE(var
, val
, env
):
471 return do_variable(var
, env
,
472 lambda vars, vals
: set_caR(vals
, val
),
473 lambda : add_binding_to_framE(var
, val
,
483 ('whitespace', c(r
'(\s+)')),
484 ('comment', c(r
'(;[^\n]*)')),
487 ('number', c(r
'''( [+\-]? ## optional sign,
488 (?: ## followed by some
498 ('symbol', c(r
'''([a-zA-Z\+\=\?\!\@\#\$\%\^\&\*\-\/\.\>\<]
499 [\w\+\=\?\!\@\#\$\%\^\&\*\-\/\.\>\<]*)''',
516 for type, regex in PATTERNS:
520 tokens.append((type, token))
524 error("TOKENIZE error from: %s..." % s[:20])
527 def filter_executable_tokens(tokens):
529 lambda x: x[0] not in ('whitespace
', 'comment
'),
533 tokens = filter_executable_tokens(tokenize(text))
534 def parse_till_end(n):
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] == ')':
560 e, fr = parse_sexp(tokens, fr)
561 r, fr = parse_rest_of_sexps(tokens, fr)
562 return cons(e, r), fr
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
"
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)),
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):
610 error("No PATTERN matched
-- syntax
-rules
: %s" % operands)
613 if match(first_pattern(rules), literals(rules), operands, binding):
614 return expand(first_clause(rules), binding)
616 return transform_loop(cdr(rules))
617 return transform_loop(syntax_rules.value)
619 def match(pattern, literals, operands, binding):
621 return null_p(operands)
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):
631 error("Invalid PATTERN
: %s" % car(pattern))
632 return match(cdr(pattern), literals, cdr(operands), binding)
634 def expand(clause, binding):
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)
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)
655 # primitive procedures
657 def is_primitive_procedure(proc):
658 return is_tagged_list(proc, symbol("primitive
"))
660 def primitive_implementation(proc):
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):
683 primitive_implementation(proc),
686 def apply_python_procedure(p, args):
687 return py_apply(p, l2py(args))
689 def is_python_callable(procedure):
690 return callable(procedure)
695 def __init__(self, module_path, parent_env):
696 self.env = extend_environment(null, null,
699 parse(open(module_path).read()),
702 def __nonzero__(self):
703 # `if m: ..' looks up m.__nonzero__
706 def __getattr__(self, attr):
707 return lookup_variable_value(symbol(attr), self.env)
709 class LispModuleLoader(ihooks.ModuleLoader):
711 def __init__(self, env):
713 ihooks.ModuleLoader.__init__(self)
716 def find_module_in_dir(self, name, dir, allow_packages=1):
718 return None, name, ('', '', "lisp
-module
")
720 ihooks.ModuleLoader.find_module_in_dir(
721 self, name, dir, allow_packages)
723 def load_module(self, name, stuff):
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
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]
738 m = LispModule(module, self.env)
739 sys.modules[module] = m
743 input_prompt = ";;; M
-Eval
input: "
744 output_prompt = ";;; M
-Eval value
: "
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):
756 print "\n%s" % input_prompt
757 input = raw_input() # ??
758 output = eval(parse(input), self.the_global_environment)
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
>"))
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()