09 December 2006

orange4.py -- an interpreter for a Lisp like lang in Python

Orange4.py [as text] implements a Lisp like language in Python. I make use of Python tuples to represent the source code. Here is the Y Combinator:
(using('ycomb x proc arg fact fnarg n'),
 (let, ((ycomb, (olambda, (x,),
                 ((olambda, (proc,),
                    (x, (olambda, (arg,), ((proc, proc), arg)))),
                  (olambda, (proc,),
                    (x, (olambda, (arg,), ((proc, proc), arg))))))),),
  (let, ((fact, (olambda, (fnarg,),
                  (olambda, (n,),
                    (oif, (eq, n, 0),
                          (multiply, n,
                                     (fnarg, (minus, n, 1))))))),),
   (pr, "hi"),
   (pr, ((ycomb, fact), 10)),
   ((ycomb, fact), 10))))
Yeah, the syntax is UGLY, and to make this tuples-as-source work (since Python would complain about variables in "(olambda, (b, c, d), ...)", you have to say something like, "(using('b c d'), (olambda, (b, c, d), ...)". Also, you need to be careful about singleton tuples in Python: so you can't write "(let, ((a, 20)), ...)"; you need to say: "(let, ((a, 20),), ...)".

using is defined as:
class using:
    def __init__(self, string):
        for name in string.split():
            if name in globals():
                print "Warning: `%s' already defined, ignoring it" % name
                globals()[name] = var(name)

And here are EVAL and APPLY, named OEVAL and OAPPLY so that they don't conflict with the Python builtins of the same name:
def oeval(x, env=None):
    if trace: print 'oeval', x, env

    if isinstance(x, var):
        return env_lookup(x, env)
    elif not isinstance(x, tuple):
        return x

    if isinstance(x[0], using):
        x = x[1]

    fn   = x[0]
    args = x[1:]

    if fn == OIF:
        if oeval(args[0], env) == NIL:
            return oeval(args[2], env)
            return oeval(args[1], env)

    elif fn == OLAMBDA:
        return (CLOSURE, args[0], args[1:], env)

    elif fn == LET:
        bindings = args[0]
        newenv = dict((var.name, oeval(val, env))
                      for (var, val) in bindings)

        return oevalis(args[1:], [newenv, env])

    else: # function application
        # global env is the python global env,
        # so we don't need to evaluate fn (i think).
        return oapply(oeval(fn, env),
                      tuple(oeval(arg, env) for arg in args))
# since we are applying fns, args are evalled
def oapply(fn, args):
    def err(type):
        error("%s %s, %s" % (
            (fn.name if isinstance(fn, var) else fn),

    if not isinstance(fn, tuple):
        if fn == GT:
            if args[0] > args[1]:
                return TRUE
            return NIL

        elif fn == PR:
            print args[0]
            return NIL

        elif fn == PLUS:
            return args[0] + args[1]

        elif fn == MINUS:
            return args[0] - args[1]

        elif fn == EQ:
            # args should just be numbers
            if args[0] == args[1]:
                return TRUE
            return NIL

        elif fn == MULTIPLY:
            return args[0] * args[1]

            err("unknown function")

    # user-defined functions:
    elif fn[0] == CLOSURE:
        if trace: print 'calling closure', fn, args

        formal_params, body, env_when_defined = fn[1:]
        actual_params = args

        if len(formal_params) != len(actual_params):
            err("wrong number of args")
        newenv = dict(zip((x.name for x in formal_params),
        # lexical scoping
        return oevalis(body, [newenv, env_when_defined])

        # return oevalis(body, [newenv, env])
        # the above specifies dynamic scoping (i think!)
        # env, should be an env passed
        # to this oapply fn.

        err("unknown function")