Dave Beazley had us implement a mini-scheme like interpreter in Python today: this is what we came up with.

scheme.py

# scheme.py
#
# Challenge:  Can you implement a mini-scheme interpreter (program that's running another program) capable of
# executing the following code (now at bottom of file):

def seval(sexp, env):
    if isinstance(sexp, (int, float)):
        return sexp
    elif isinstance(sexp, str):  #Symbols
        return env[sexp]  #Evaluate symbol names in the 'env'
    elif isinstance(sexp, tuple):
        # Special forms
        if sexp[0] == 'define':
            name = sexp[1]
            value = seval(sexp[2], env)
            env[name] = value
            return
        if sexp[0] == 'if':
            # (if test consequence alternative)
            if seval(sexp[1], env):
                return seval(sexp[2], env)
            else:
                return seval(sexp[3], env)
        if sexp[0] == 'lambda':
            # (lambda (parameters) body)
            parameters = sexp[1] # names
            body = sexp[2] # expression
            def proc(*args):
                localenv = dict(env)
                # Bind names (this is wrong wrt SICP & principle of substitution)
                for name, arg in zip(parameters, args):
                    localenv[name] = arg
                return seval(body, localenv)
            return proc

        # (x, y, z)
        proc = seval(sexp[0], env)
        args =  [ seval(a,  env)
                    for a in sexp[1:]]
        return proc(*args)

env = {
    # Make some builtin  functions

    '+' : lambda x,y: x + y,
    '*' : lambda x,y: x * y,
    '-' : lambda x,y: x - y,
    '<' : lambda x,y: x < y,
    '=' : lambda x,y: x == y,
    '>' : lambda x,y: x > y
}

# # A function definition expressed as a S-expression (in tuples)
# fact = ('define', 'fact',
#         ('lambda', ('n',), ('if', ('=', 'n', 1), 1, ('*', 'n', ('fact', ('-', 'n', 1))))))
# 
# # Some test code
# seval(fact, env)
# seval(('define', 'n', 5), env)
# result = seval(('fact', 'n'), env)
# assert result == 120

to test out your new interpreter, execute python -i scheme.py in your terminal & try out the following

• return an int:seval(42, env)
• your addition operator: seval('+', env)
• add something to your environment & return it:env['x'] = 23; seval('x', env)
• addition: seval(('+',2,3), env) (try multiplication also!)
• if else: seval(('if', ('>', 2, 3), 42, 37), env)
• create a lambda function: seval(('lambda',('x',), ('*', 'x', 'x')), env)
• create a function & evaluate it: p = seval(('lambda',('x',), ('*', 'x', 'x')), env); p(4)
• build an expression: expr = ('*', 'x', 'x')

Another cool things you can do is define a function then evaluate it like this:

seval(('define', 'square', ('lambda',('x',), ('*', 'x', 'x'))), env)
seval(('square', 4), env)

note that the above is wrong wrt the principle of substitution, as introduced in SICP, because it doesn't explicitly substitute values into functions before evaluation. see here for an interpreter that performs the substitution also.

Then try this:

expr = ('*', 'x', 'x')
substitute(expr, 'x', 42)

from @jasonamyers:

The binding of name and values in the initial solution really wasn't in the spirit SICP which really focuses on evaluation via the substitution method.

Essentially, in the new version linked in previous comment, we're replacing symbols instead of binding values to names in the env dict (args to params).