From b069f6aa0319eb7c771ac29409d1251f155819ea Mon Sep 17 00:00:00 2001
From: Jorge Gorbe <jgorbe@stcsl.es>
Date: Tue, 14 Jan 2014 16:58:44 +0100
Subject: [PATCH] Made lisp lists iterable. Changed all uses of foldl to
 python's own reduce. Further simplifications.

---
 lisp0.py | 284 +++++++++++++++++--------------------------------------
 repl.py  |  15 ++-
 2 files changed, 99 insertions(+), 200 deletions(-)

diff --git a/lisp0.py b/lisp0.py
index 80c4760..8eabb7f 100644
--- a/lisp0.py
+++ b/lisp0.py
@@ -2,7 +2,7 @@ import types
 import sys
 import operator
 import inspect
-from functools import reduce
+from functools import reduce, wraps
 
 class Pair:
     def __init__(self, car, cdr):
@@ -18,14 +18,28 @@ class Value:
     def __str__(self):
         return Value2String(self)
 
+    def __repr__(self):
+        return "Value[%s]"%Value2String(self)
+
+    # make lisp lists iterable from python, to simplify lots of things
+    def __iter__(self):
+        cur = self
+        while is_pair(cur):
+            yield car(cur)
+            cur = cdr(cur)
+
 Value.TRUE = Value("symbol", "#t")
 Value.FALSE = Value("symbol", "#f")
 Value.NIL = Value("nil", None)
 
 # value constructors
+# lambdas are traditional functions
+# forms are like lambdas, but their arguments are not evaluated on call
+# macros are forms that, when evaluated, produce an expression which is then evaluated
 def make_int(i):                      return Value("int", i)
 def make_string(s):                   return Value("string", s)
 def make_function(params, body, env): return Value("function", [params, body, env])
+def make_form(params, body, env):     return Value("form", [params, body, env])
 def make_macro(f):                    return Value("macro", f)
 def make_symbol(s):                   return Value("symbol", s)
 def make_boolean(b):                  return Value.TRUE if b else Value.FALSE
@@ -33,13 +47,9 @@ def cons(x,y):                        return Value("pair", Pair(x,y))
 def flipcons(x,y):                    return cons(y,x)
 def make_list(*args):                 return reduce(flipcons, reversed(args), Value.NIL)
 
-# pair value accessors
-def car(p):        return p.v.car
-def cdr(p):        return p.v.cdr 
-def set_car(p, v): p.v.car = v 
-def set_cdr(p, v): p.v.cdr = v
-
 # list helper accessors
+def car(p):  return p.v.car
+def cdr(p):  return p.v.cdr 
 def cadr(p): return car(cdr(p))
 def cddr(p): return cdr(cdr(p))
 
@@ -47,6 +57,7 @@ def cddr(p): return cdr(cdr(p))
 def is_pair(v):     return v.t == "pair"
 def is_function(v): return v.t == "function"
 def is_macro(v):    return v.t == "macro"
+def is_form(v):     return v.t == "form"
 def is_symbol(v):   return v.t == "symbol"
 def is_string(v):   return v.t == "string"
 def is_nil(v):      return v.t == "nil"
@@ -55,69 +66,45 @@ def is_false(v):    return is_symbol(v) and v.v == "#f"
 def is_true(v):     return not is_false(v)
 
 # Environment is a dictionary wrapper with "inheritance": if a key is not found
-# the parent environment is searched, and so on.
-class Environment:
-    def __init__(self, parent=None, dictionary=None):
-        self.p = parent
-        self.d = dictionary or {}
-
-    def __getitem__(self, i):
-        if i in self.d:
-            return self.d[i]
+# the outer environment is searched, and so on.
+class Environment(dict):
+    "An environment: a dict of {'var':val} pairs, with an outer Env."
+    def __init__(self, parms=(), args=(), outer=None):
+        self.update(zip(parms,args))
+        self.outer = outer
+    def find(self, var):
+        "Find the innermost Env where var appears."
+        if var in self:
+            return self
         else:
-            if self.p is not None:
-                return self.p[i]
-            else:
-                print "value not found for symbol %s"%(i)
-                raise KeyError
-
-    def __setitem__(self, i, v):
-        self.d[i] = v
-
-    def __contains__(self, i):
-        item = self.__getitem__(i)
-        return (item is not None)
-
-    def __str__(self):
-        return "[d="+str(self.d)+", p="+str(self.p)+"]"
-
-
-# helper lisp-list functions
-def find(pred, l):
-    while not is_nil(l):
-        x = car(l)
-        if pred(x): return x
-        l = cdr(l)
-    return Value.NIL
-
-def foldl(func, initial, l):
-    result = initial
-    while not is_nil(l):
-        result = func(result, car(l))
-        l = cdr(l)
-    return result
-
-def foldr(func, initial, l):
-    if is_nil(l): return initial
-    else:         return func(car(l), foldr(func, initial, cdr(l)))
-
-def reverse_list(l):      return foldl(flipcons, Value.NIL, l)
-def map_list(func, l):    return foldr(lambda x,y: cons(func(x), y), Value.NIL, l)
-def do_list(func, l):     return foldl(lambda x,y: func(y), None, l)
+            if self.outer is not None:
+                return self.outer.find(var)
+            else: 
+                raise KeyError(var)
+    def __repr__(self):
+        return "env"
+
+# helper one-liners
+# -----------------
+def do_list(func, l):     reduce(lambda x,y: func(y), l, None)
+def list_length(l):       return reduce(lambda x,y: x+1, l, 0)
+def reverse_list(l):      return reduce(flipcons, l, Value.NIL)
+def find(pred, l):        return reduce(lambda x,y: x or (pred(y) and y), l, None)
+def map_list(func, l):    return reverse_list(reduce(lambda x,y: cons(func(y), x), l, Value.NIL))
 def eval_list(args, env): return map_list(lambda x: lisp_eval(x, env), args)
-def list_length(l):       return foldl(lambda x,y: x+1, 0, l)
+
+def is_python_function(x): return type(x) == types.FunctionType
 
 # Built-in functions and special forms
 # ------------------------------------
-#
-# Built-in functions sometimes need to access the raw (non-evaluated) args.
-# Therefore, if a python function wants evaluated args, it must call eval_list(args) to get them
-
 def lisp_lambda(args, env):
-    return make_function(car(args), cadr(args), Environment(env))
+    return make_function(car(args), cadr(args), env)
+
+def lisp_form(args, env):
+    return make_form(car(args), cadr(args), env)
 
 def lisp_macro(args, env):
-    return make_macro(lisp_lambda(args, env))
+    return make_macro(lisp_form(args, env))
 
 def lisp_define(args, env):
     name = car(args)
@@ -132,10 +119,6 @@ def lisp_quote(args, env):
     assert(is_nil(cdr(args)))
     return car(args)
 
-# empty function used as a marker, the code is inlined into lisp_eval
-def lisp_cond(args, env):
-    pass
-
 def quasiquote_expression(expr, env):
     """returns a tuple with:
     - the expression with unquotes recursively expanded as needed
@@ -153,10 +136,10 @@ def quasiquote_expression(expr, env):
             def quasiquote_and_push_front(result, element):
                 r, mode = quasiquote_expression(element, env)
                 if mode == "splicing":
-                    return foldl(flipcons, result, r) # push elements of r, in reverse order, at the head of result
+                    return reduce(flipcons, r, result) # push elements of r, in reverse order, at the head of result
                 else:
                     return cons(r, result)
-            result = foldl(quasiquote_and_push_front, make_list(), expr)
+            result = reduce(quasiquote_and_push_front, expr, make_list())
             return reverse_list(result), "normal"
     else:
         return expr, "normal"
@@ -173,6 +156,7 @@ def lisp_quasiquote(args, env):
 # a decorator which checks the number of arguments, evals them,
 # and forwards them to a python function as positional arguments
 def lisp_function(f):
+    @wraps(f)
     def result(args, env):
         argspec = inspect.getargspec(f)
         if (argspec.varargs is None):
@@ -180,10 +164,8 @@ def lisp_function(f):
             given_args = list_length(args)
             if (given_args != expected_args):
                 raise Exception("function %s takes %d arguments (%d given)"%(f.func_name, expected_args, given_args))
-        def eval_and_append(l, x):
-            l.append(lisp_eval(x, env))
-            return l
-        python_args = foldl(eval_and_append, [], args)
+
+        python_args = [lisp_eval(x, env) for x in args]
         return f(*python_args)
     return result
 
@@ -221,110 +203,50 @@ def lisp_display(*args):
         sys.stdout.write(str(i))
     sys.stdout.write("\n")
     return Value.NIL
-    
-# Helper functions for the evaluator
-# ----------------------------------
 
-def is_python_function(x):
-    return type(x) == types.FunctionType
+@lisp_function
+def lisp_eval_exported(expr, env):
+    keys = [car(x).v for x in env]
+    values = [cadr(x) for x in env]
+    print "eval: %s"%expr
+    return lisp_eval(expr, Environment(keys, values))
     
-def should_eval_arguments(x):
-    if is_python_function(x) or is_macro(x):
-        return False
-    elif is_function(x):
-        return True
-    else:
-        print "Expected a function or macro, found %s"%str(x)
-        raise Exception
-
 # Evaluator
 # ---------
-
-global_env = Environment()
-
-# inline apply into eval, to convert last call to eval in apply into a loop
-# in order to optimize tail calls
 def lisp_eval(e, env):
-    """evals an expression"""
     while True:
-        if e is None:        return Value.NIL
-        elif is_symbol(e):   return env[e.v]
+        if   e is None:      return Value.NIL
+        elif is_symbol(e):   return env.find(e.v)[e.v]
         elif not is_pair(e): return e
         else:
-            f = lisp_eval(car(e), env)
+            first = car(e)
             args = cdr(e)
-            # inlined body of the apply function
-            if should_eval_arguments(f):
-                args = eval_list(args, env)
-            if type(f) == types.FunctionType:
-                # TEST: special case for cond, the old lisp_cond function is only used as a marker, but evaluated inline
-                if f == lisp_cond:
-                    satisfied = find(lambda x: is_true(lisp_eval(car(x), env)), args)
-                    if not is_nil(satisfied):
-                        e = cadr(satisfied)
-                else:
-                    return f(args, env)
-                    
-            elif f.t == "macro":
-                e = lisp_apply(f.v, args, env)
+            if is_symbol(first) and first.v == "cond":
+                satisfied = find(lambda x: is_true(lisp_eval(car(x), env)), args)
+                if not is_nil(satisfied):
+                    e = cadr(satisfied)
             else:
-                formals, body, environment = f.v
-                new_env = Environment(environment)
-                #insert parameters into the environment
-                while not is_nil(formals):
-                    name = car(formals)
-                    formals = cdr(formals)
-                    if not is_nil(args):
-                        arg = car(args)
-                        args = cdr(args)
-                    else:
-                        arg = Value.NIL
-
-                    new_env[name.v] = arg
-                
-                e = body
-                env = new_env
-
-def lisp_apply(f, args, env):
-    """applies an argument list to a function or special form"""
-    # special forms and built-in functions are stored in the global environment as python functions
-    if type(f) == types.FunctionType:
-        return f(args, env)
-    elif f.t == "macro":
-        expansion = lisp_apply(f.v, args, env)
-        #print "macro expansion:", expansion
-        result = lisp_eval(expansion, env)
-        return result
-    else:
-        formals, body, environment = f.v
-        new_env = Environment(environment)
-        #insert parameters into the environment
-        while not is_nil(formals):
-            name = car(formals)
-            formals = cdr(formals)
-            if not is_nil(args):
-                arg = car(args)
-                args = cdr(args)
-            else:
-                arg = Value.NIL
-
-            new_env[name.v] = arg
-
-        return lisp_eval(body, new_env)
-
-# lisp_eval accepts a single expression instead of a list of args,
-# this one can be called from lisp
-def lisp_eval_exported(args, env):
-    args = eval_list(args, env)
-    return lisp_eval(car(args), env)
-
+                f = lisp_eval(first, env)
+                if is_python_function(f):
+                    return f(args, env)
+                elif f.t == "macro":
+                    e = lisp_eval(cons(f.v, args), env)
+                else:
+                    if is_function(f): args = eval_list(args, env)
+                    formals, body, environment = f.v
+                    new_env = Environment((x.v for x in formals), args, environment)
+                    e = body
+                    env = new_env
+
+# Initial environment
+# -------------------
+global_env = Environment()
 global_env["lambda"]     = lisp_lambda
 global_env["macro"]      = lisp_macro
 global_env["define"]     = lisp_define
 global_env["cons"]       = lisp_cons
 global_env["car"]        = lisp_car
 global_env["cdr"]        = lisp_cdr
-global_env["cond"]       = lisp_cond
 global_env["eval"]       = lisp_eval_exported
 global_env["quote"]      = lisp_quote
 global_env["quasiquote"] = lisp_quasiquote
@@ -336,14 +258,10 @@ global_env["-"]          = lisp_minus
 global_env["*"]          = lisp_times
 global_env["/"]          = lisp_div
 global_env["%"]          = lisp_mod
-
 global_env["nil"]        = Value.NIL
 
-
-
 # Simple S-expression parser
 # --------------------------
-
 def parse_list(s):
     if s[0] != '(':
         return None
@@ -359,38 +277,24 @@ def parse_list(s):
     return reverse_list(result), s[1:]
 
 def parse_symbol(s):
-    index = 0
-    l = len(s)
-    while index < l:
+    for index in range(len(s)):
         c = s[index]
         if c.isspace() or c == '(' or c == ')':
             return make_symbol(s[:index]), s[index:]
-        index = index + 1
-
     return make_symbol(s), ""
 
 def parse_int(s):
-    index = 0
-    l = len(s)
-    while index < l:
+    for index in range(len(s)):
         if not s[index].isdigit():
             return make_int(int(s[:index])), s[index:]
-        index = index + 1
-
     return make_int(int(s)), ""
 
 def parse_string(s):
-    index = 1
-    l = len(s)
-    while index < l:
-        c = s[index]
-        if c == '"':
+    for index in range(1,len(s)):
+        if s[index] == '"':
             return make_string(s[1:index]), s[index+1:]
-        index = index + 1
     return None # no ending quote -> parse error
 
-
-
 def parse_quote(s):
     quoted, s = parse(s[1:])
     return make_list(make_symbol("quote"), quoted), s
@@ -407,7 +311,6 @@ def parse_unquote(s):
         quoted, s = parse(s[1:])
         return make_list(make_symbol("unquote"), quoted), s
 
-
 def parse(s):
     s = s.lstrip()
     if s == '':
@@ -427,14 +330,6 @@ def parse(s):
     else:
         return parse_symbol(s)
     
-def eval_file(name):
-    f = file(name)
-    s = f.read()
-    while s != "":
-        e, s = parse(s)
-        if e is not None:
-            lisp_eval(e, global_env)
-
 # value pretty-printing
 def Value2String(x):
     result = ""
@@ -448,10 +343,10 @@ def Value2String(x):
         if not is_nil(cdr(l)):
             result += " . %s" % cdr(l)
         result += ")"
-    elif is_function(x):
-        result += "(lambda %s %s), environment: %s"%(x.v[0], x.v[1], x.v[2])
+    elif is_function(x) or is_form(x):
+        result += "(%s %s %s)"%(x.t, x.v[0], x.v[1])
     elif is_macro(x):
-        result += "macro: %s"%str(x.v)
+        result += "(macro %s %s)"%(x.v.v[0], x.v.v[1])
     elif is_nil(x):
         result += "nil"
     elif is_string(x):
@@ -460,4 +355,3 @@ def Value2String(x):
         result += str(x.v)
     return result
 
-
diff --git a/repl.py b/repl.py
index 96122d7..e943aef 100644
--- a/repl.py
+++ b/repl.py
@@ -1,6 +1,14 @@
 from lisp0 import *
 import sys
 
+def eval_file(name):
+    f = file(name)
+    s = f.read()
+    while s != "":
+        e, s = parse(s)
+        if e is not None:
+            lisp_eval(e, global_env)
+
 eval_file("prelude.l")
 
 if len(sys.argv) > 1:
@@ -10,10 +18,7 @@ else:
     while True:
         in_str = raw_input()
         e,s = parse(in_str)
-        try:
-            result = lisp_eval(e, global_env)
-            print(result)
-        except Exception as e:
-            print '%s: %s' % (type(e).__name__, e)
+        result = lisp_eval(e, global_env)
+        print(result)
 
 
-- 
2.34.1