simple python implementation

1 files changed, 158 insertions, 0 deletions

diff --git a/simple.py b/simple.py
new file mode 100644
index 0000000..a34941c
--- /dev/null
+++ b/simple.py
@@ -0,0 +1,158 @@
+"""
+    null -> None
+    pair -> <use tuples>
+    boolean (true/false) -> True/False
+    number -> number
+    identifier/symbol -> string
+
+
+    const (atomic values)
+    lambda
+    quote (s-expr "one level down")
+    identifier (a symbol to be looked up in the context)
+    cond (conditional expression)
+"""
+
+def is_atom(x):
+    return x is () or type(x) not in (None, tuple, list, dict)
+
+def is_boolean(x):
+    return x in (True, False)
+
+def is_number(x):
+    return type(x) in (int, float, long)
+
+def is_zero(x):
+    return x == 0
+
+def is_null(x):
+    return x is ()
+
+def is_eq(a, b):
+    return a == b
+
+def is_builtin(x):
+    return x in ('lambda', 'quote', 'cond', 'else', 'cons', 'car', 'cdr',
+                 'null?', 'eq?', 'atom?', 'zero?', 'number?',
+                 '+', '-', '*', '/')
+
+# because python does not allow circular function definitions, and action
+# functions call out to meaning(), which depends on some actions, we'll use an
+# "action lookup table" to handle function references ourself.
+# A more "pythonic" way to do this might be to use an object.
+actions = dict()
+
+def meaning(x, ctx):
+    action = None
+    if is_atom(x):
+        if is_number(x) or is_boolean(x) or is_builtin(x):
+            action = actions['identity']
+        else:   # an identifier
+            action = actions['lookup']
+    elif type(x) is tuple:
+        if x[0] is 'quote':
+            action = actions['quote']
+        elif x[0] is 'cond':
+            action = actions['cond']
+        elif x[0] is 'lambda':
+            action = actions['lambda']
+        elif type(x[0]) is tuple:
+            action = actions['apply']
+        else:   # some other identifier, either builtin or not
+            action = actions['apply']
+    else:
+        raise ValueError("Unexpected expression: %s" % x)
+    return action(x, ctx)
+
+def meaning_list(l, ctx):
+    return tuple([meaning(x, ctx) for x in l])
+
+def identity_action(x, ctx):
+    return x
+actions['identity'] = identity_action
+
+def lookup_action(x, ctx):
+    if not x in ctx:
+        ValueError("Unknown identifier: %s" % x)
+    else:
+        return ctx[x]
+actions['lookup'] = lookup_action
+
+def quote_action(x, ctx):
+    if len(x) != 2:
+        ValueError("Improper quote usage: %s" % x)
+    return x[1]
+actions['quote'] = quote_action
+
+def cond_action(x, ctx):
+    for line in x[1:]:
+        if line[0] == 'else':
+            return meaning(line[1], ctx)
+        elif meaning(line[0], ctx):
+            return meanint(line[1], ctx)
+        else:
+            # "unspecified"
+            return None
+actions['cond'] = cond_action
+
+def lambda_action(x, ctx):
+    return ('procedure', x[1], x[2:], ctx.copy())
+actions['lambda'] = lambda_action
+
+def apply_action(x, ctx):
+    if is_builtin(x[0]):
+        args = meaning_list(x[1:], ctx)
+        if x[0] is 'cons':
+            return (args[0], ) + args[1]
+        elif x[0] is 'car':
+            return args[0][0]
+        elif x[0] is 'cdr':
+            return args[0][1]
+        elif x[0] is 'null?':
+            return is_null(args[0])
+        elif x[0] is 'eq?':
+            return is_eq(args[0], args[1])
+        elif x[0] is 'atom?':
+            return is_atom(args[0])
+        elif x[0] is 'zero?':
+            return is_zero(args[0])
+        elif x[0] is 'number?':
+            return is_number(args[0])
+        elif x[0] is '+':
+            return args[0] + args[1]
+        elif x[0] is '-':
+            return args[0] - args[1]
+        elif x[0] is '*':
+            return args[0] * args[1]
+        elif x[0] is '/':
+            return args[0] / args[1]
+        else:
+            raise Exception("Unexpected builtin: %s" % x[0])
+    elif type(x[0]) is tuple:
+        proc = meaning(x[0], ctx)
+        if proc[0] is not 'procedure':
+            raise Exception("Not applicable: %s" % str(proc))
+        variables = proc[1]
+        body = proc[2]
+        closure = proc[3].copy()
+        args = meaning_list(x[1:], ctx)
+        for i in range(len(variables)):
+            closure[variables[i]] = args[i]
+        for expr in body:
+            ret = meaning(expr, closure)
+        return ret
+    else:
+        raise Exception("Unexpected... thing...: %s" % str(x[0]))
+actions['apply'] = apply_action
+
+def value(x):
+    return meaning(x, dict())
+
+def test():
+    # ((lambda (x) (+ 1 x)) 5) ; 6
+    v = value( (('lambda', ('x',), ('+', 1, 'x')), 5) )
+    print(v)
+    assert(v is 6)
+
+if __name__=='__main__':
+    test()