Here's a really small lisp interpreter.

iterpreter = (lambda s: (
  (lambda g: lambda env, exp: g(g)(env, exp))
  (lambda g: (lambda interpret:(
    lambda env, exp:{
      list:lambda exp:(
        (exp[:1]==["lambda"]) and
          (lambda env: lambda params:
            (lambda nenv: [interpret(nenv, e)
                for e in exp[2:]][-1])
              (lambda x: dict(zip(exp[1], params)).get(x, False)
                or env(x)))(env)
        or (lambda pexp: pexp[0](pexp[1:]))([interpret(env, e)
          for e in exp])),
      str:lambda exp: env(exp), int:lambda exp: exp
    }[type(exp)](exp)))(lambda env, exp:g(g)(env, exp))))
    (lambda x:{"sum":(lambda params: sum(params))}.get(x, False),
    reduce(lambda env, v:
      (v==")" and
        (lambda:((lambda i:env[:i]+[env[i+1:]])
          (len(env)-env[::-1].index("(")-1)))
      or (lambda:env+[v]))(),
        [(i==2 and int(e[i]) or e[i]) for e, i in
          [(e,sum([c*(i is not "") for i, c in zip(e, count())]))
            for e in re.findall(r"(()|())|(d+)|(w+)",s)]],
            [])[0]))


The whole program is a single python expression. You can add new functions using the lambda operator and there is a sum function for adding numbers. There is no conditional operator but that could be added quite easily.

The program uses a regular expression based parser to convert simple s-expressions into trees of python lists.

    reduce(lambda env, v:
      (v==")" and
        (lambda:((lambda i:env[:i]+[env[i+1:]])
          (len(env)-env[::-1].index("(")-1)))
      or (lambda:env+[v]))(),


Implementing recursive functions inside python expressions is hard. We use the reduce function instead and pass a list which acts like a stack to store the intermediate stages of the tree.

        [(i==2 and int(e[i]) or e[i]) for e, i in
          [(e,sum([c*(i is not "") for i, c in zip(e, count())]))
            for e in re.findall(r"(()|())|(d+)|(w+)",s)]],
            [])[0]))


The regular expression used isn't very good but it does the job and is readable. We also convert numeric strings into ints here.

The interpreter uses python's stack rather than implementing it's own, this is easier but we lose the ability to implement such goodies as tail recursion and continuation. Using the stack does bring one issue that we need to implement recursive function calls, as I mentioned earlier this is hard inside expressions.

The issue is that to create a recursive function you need to bind it to a name that can be accessible from within the function. There is also an additional restriction that since this is an expression assignment operations are not possible. The only way to create new name in a python expression is using the lambda operator. Unfortunately when binding a function in this way it is not possible for the bound function to see the name it is bound to because that name didn't exist when the function was created.

Here's a neat trick I learnt a while ago to implement recursive functions.

  (lambda g: lambda env, exp: g(g)(env, exp))
  (lambda g: (lambda interpret:(
.
.
.
    }[type(exp)](exp)))(lambda env, exp:g(g)(env, exp))))


What we need to do is pass a function a pointer to itself as a parameter, now this can be bound to a name and used inside the function. Of course a function cannot get a pointer to itself because it only has access to things that existed before it was created. What we do is create another function to bootstrap the process. This function will accept the function we want to make recursive as a parameter and pass the function a copy of itself. Now the recursive function needs to keep passing itself copies, this could get quite tedious, imagine looking at g(g) all over the place. To make things easier to read we bind g(g) to the name interpret.

The interpreter itself is quite trivial to implement.

    lambda env, exp:{
      list:lambda exp:(
        (exp[:1]==["lambda"]) and
          (lambda env: lambda params:
            (lambda nenv: [interpret(nenv, e)
                for e in exp[2:]][-1])
              (lambda x: dict(zip(exp[1], params)).get(x, False)
                or env(x)))(env)
        or (lambda pexp: pexp[0](pexp[1:]))([interpret(env, e)
          for e in exp])),
      str:lambda exp: env(exp), int:lambda exp: exp
    }[type(exp)](exp)))(lambda env, exp:g(g)(env, exp))))


We walk through the tree matching the type of the element. Strings are treated as symbols and are evaluated by looking up the env function. Lists are evaluate as function applications except for lists starting with the symbol lambda. Those construct a new function.

When a function is called, a new environment function is created binding the parameters passed to the function to the names declared in it's lambda form. Then the interpreter is run on the list of operations declared in the lambda form, using the new env function as it's environment.

As I mentioned before this interpreter is very simple. But it can be extended quite easily, to add conditional operators for example. Adding more types might me turn out to be painful.