aboutsummaryrefslogtreecommitdiffstats
path: root/python
diff options
context:
space:
mode:
Diffstat (limited to 'python')
-rw-r--r--python/minimal.py158
-rw-r--r--python/sexpr.py40
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]
+