lisp.py

import re
from operator import *


def lisp(s_exp):
    """ Evaluate pseudo-lisp.
    `s_exp` should be a string of an s-expression.
    If the first item in the s-exp isn't callable then the s-exp will be
    treated like a literal list.

    >>> from operator import *
    >>> lisp('(add 7 (mul 2 2))')
    11

    >>> lisp('(concat "Hello" "World")')
    'HelloWorld'

    >>> lisp('(sum (1 2 3 4 5))')
    15
    """
    return execute(evaluate(parse(s_exp)))


def parse(expr):
    """
    Split a string of s-exps into tokens.
    """
    # strip whitespace and the surronding parens
    expr = expr.strip()[1:-1]
    regex = re.compile(
        '[\w.]+'    # words and dots
        '|\(.*\)'   # parenthesised lists (s-expression)
        '|".*?"'    # strings
    )
    tokens = regex.findall(expr)

    # Recurse into nested s-exps.
    parsed = []
    for t in tokens:
        if t.startswith('(') and t.endswith(')'):
            parsed.append(parse(t))
        else:
            parsed.append(t)
    return parsed


def evaluate(ls):
    """
    Evaluate the strings in the list into python objects recursing into lists.
    """
    evald = []
    for item in ls:
        if isinstance(item, list):
            evald.append(evaluate(item))
        else:
            evald.append(eval(item))
    return evald


def simple_exec(ls):
    """
    Execute a simple s-expression -- an expression that contains no other
    s-expressions.
    """
    fn = ls[0]
    args = ls[1:]
    return fn(*args)


def execute(ls):
    """
    Reduce nested s-exps into a single s-exp and then return the final result.
    """
    execd = []
    for item in ls:
        if isinstance(item, list):
            if any(isinstance(i, list) for i in item):
                execd.append(execute(item))
            elif callable(item[0]):
                execd.append(simple_exec(item))
            else:
                execd.append(item)
        else:
            execd.append(item)
    return simple_exec(execd)


if __name__ == '__main__':
    import doctest
    doctest.testmod()