mvoe implementations into subdirs

2 files changed, 198 insertions, 0 deletions

diff --git a/python/minimal.py b/python/minimal.py
new file mode 100644
index 0000000..8a282da
--- /dev/null
+++ b/python/minimal.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) )
+    assert(v is 6)
+    return True
+
+if __name__=='__main__':
+    print(test())
diff --git a/python/sexpr.py b/python/sexpr.py
new file mode 100644
index 0000000..61bb09c
--- /dev/null
+++ b/python/sexpr.py
@@ -0,0 +1,40 @@
+
+def tokenize(s, sep="()", ws=" \t\n"):
+    L = []
+    food = 0
+    for i, c in enumerate(s):
+        if c in sep or c in ws:
+            if food > 0:
+                L.append(s[i-food:i])
+            if c in sep:
+                L.append(c)
+            food = 0
+        elif i+1 == len(s):
+            L.append(s[i-food:])
+        else:
+            food += 1
+    return L
+
+def _parse_tokens(tokens, depth=0):
+    L = []
+    i = 0
+    while i < len(tokens):
+        el = tokens[i]
+        if el == '(':
+            expr, skip = _parse_tokens(tokens[i+1:], depth+1)
+            L.append(expr)
+            i += skip + 1
+        elif el == ')':
+            assert depth > 0, "Missing open bracket..."
+            return L, i+1
+        else:
+            L.append(el)
+            i += 1
+    assert depth == 0, "Missing close bracket..."
+    return L, i
+
+def parse(s):
+    tokens = tokenize(s)
+    expr, size = _parse_tokens(tokens)
+    return expr[0]
+