gistfile1.py

# Lisp like toy in Python
# (c) William Groppe, 2010

import re
import collections

SHOW_REDUCTIONS = False

OP_BEGIN = "("
OP_END = ")"
OP_DEF = "def" # Should throw if already defined
OP_FN = "fn"
OP_IF = "if"
OP_LET = "let"
OP_AND = "and"
OP_OR = "or"
OP_COND = "cond"
OP_MACRO = "defmacro"

SPECIAL_FORMS = [OP_DEF, OP_FN, OP_IF, OP_LET, OP_AND, OP_OR, OP_COND, OP_MACRO]

def is_digit(c):
    return c in "1234567890"

def sus(v):
    if is_digit(v[0]):
        return sus_number("".join(v))
    else:
        return "".join(v)

def sus_number(v):
    if re.match("^\d+$", v):
        return int(v)
    elif re.match("^\d+.\d+$", v):
        return float(v)
    raise TypeError("Invalid format for number: %s" % v)

def is_primitive(form):
    return type(form) in [int, long, float, bool]

def tokenize(src):
    nested = 0
    tokens = []
    chars = []
    for c in src:
        if c in [OP_BEGIN, OP_END]:
            if len(chars) > 0:
                tokens.append(sus(chars))
                chars = []
            tokens.append(c)
            if c == OP_BEGIN:
                nested += 1
            else:
                nested -= 1
        elif c is " ":
            if len(chars) > 0:
                tokens.append(sus(chars))
                chars = []
        elif c in ['\n', '\r']:
            pass # ignore newline/return
        else:
            chars.append(c)
    if nested is not 0:
        raise TypeError("Mismatched parens, time to pull out some hair.", nested)
    return collections.deque(tokens)

def parse(tokens):
    current_form = []
    try:
        while(True):
            token = tokens.popleft()
            if token == OP_BEGIN:
                current_form.append(parse(tokens))
            elif token == OP_END:
                return current_form
            else:
                current_form.append(token)
    except IndexError:
        return current_form

def reduce(scope, form):
    if SHOW_REDUCTIONS:
        print "reduce form: %s" % form.__repr__()
    if type(form) not in [list, collections.deque]:
        return resolve(scope, form)
    else:
        forms = collections.deque(form)
        term = reduce(scope, forms.popleft())
        if term == OP_DEF:
            name = forms.popleft()
            if name in GLOBAL_NAMESPACE:
                print("Warning, redefining %s", name)
            GLOBAL_NAMESPACE[name] = reduce(scope, forms.popleft())
            return None
        elif term == OP_LET:
            subscope = dict()
            name = forms.popleft()
            subscope[name] = reduce(scope, forms.popleft())
            return reduce(subscope, forms)
        elif term == OP_FN:
            return func(scope, forms.popleft(), forms.popleft())
        elif term == OP_IF:
            if len(forms) > 2:
                return lis_if(scope, forms.popleft(), forms.popleft(), forms.popleft())
            else:
                return lis_if(scope, forms.popleft(), forms.popleft(), None)
        elif term == OP_AND:
            test = forms.popleft()
            if len(forms) > 0:
                forms.appendleft(OP_AND)
            else:
                forms.append(True)
            return lis_if(scope, test, forms, False)
        elif term == OP_COND:
            test = forms.popleft()
            branch = forms.popleft()
            if len(forms) > 0:
                forms.appendleft(OP_COND)
            else:
                forms.appendleft(None)
            return lis_if(scope, test, branch, forms)
        elif term == OP_MACRO:
            name = forms.popleft()
            scope[name] = macro(scope, forms.popleft(), forms.popleft())
            return None
        elif callable(term):
            return term(scope, *forms)
        else:
            return term

def resolve(scope, v):
    if is_primitive(v):
        return v
    elif v in SPECIAL_FORMS:
        return v
    else:
        value =  locate_definition(scope, v)
        if SHOW_REDUCTIONS:
            print "%s resolved to: %s" % (str(v), str(value))
        return value


def locate_definition(scope, definition):
    if definition in scope:
        return scope[definition]
    elif "_parent" in scope:
        return locate_definition(scope["_parent"], definition)
    else:
        raise TypeError("%s is undefined" % definition)

def func(scope, params, forms):
    def _f(scope, *args):
        if len(args) != len(params):
            raise TypeError("Expected %d arguments, got %d" % (len(params), len(args)))
        func_scope = dict(zip(params, [reduce(scope, a) for a in args]))
        func_scope["_parent"] = scope
        return reduce(func_scope, forms)
    return _f

def macro(scope, params, forms):
    def _m(scope, *args):
        func_scope = dict(zip(params, args))
        func_scope["_parent"] = scope
        return reduce(func_scope, macro_substitute(func_scope, forms))
    return _m

def macro_substitute(scope, form):
    updated_forms = []
    forms = collections.deque(form)
    try:
        while(True):
            form = forms.popleft()
            if type(form) in [list, collections.deque]:
                updated_forms.append(macro_substitute(scope, form))
            elif form.startswith("~"):
                updated_forms.append(reduce(scope, form[1:]))
            else:
                updated_forms.append(form)
    except IndexError:
        return updated_forms

def lis_if(scope, test_form, true_form, false_form = None):
    if reduce(scope, test_form) in [False, None]:
        if false_form is not None:
            return reduce(scope, false_form)
    else:
        return reduce(scope, true_form)

######################################################################################
#
# Functions exposed in the language
#
######################################################################################

def lis_addition(scope, *forms):
    result = reduce(scope, forms[0])
    for f in forms[1:]:
        result += reduce(scope, f)
    return result

def lis_subtraction(scope, *forms):
    result = reduce(scope, forms[0])
    for f in forms[1:]:
        result -= reduce(scope, f)
    return result

def lis_multiplication(scope, *forms):
    result = reduce(scope, forms[0])
    for f in forms[1:]:
        result *= reduce(scope, f)
    return result

def lis_division(scope, *forms):
    result = reduce(scope, forms[0])
    for f in forms[1:]:
        result /= reduce(scope, f)
    return result

def lis_equal(scope, value_one, value_two):
    return reduce(scope, value_one) == reduce(scope, value_two)

def lis_lesser(scope, value_one, value_two):
    return reduce(scope, value_one) < reduce(scope, value_two)

def lis_greater(scope, value_one, value_two):
    return reduce(scope, value_one) > reduce(scope, value_two)

# Yuck, one global namespace, but it works for now.
GLOBAL_NAMESPACE = {'+' : lis_addition,
                    '-' : lis_subtraction,
                    '*' : lis_multiplication,
                    '/' : lis_division,
                    '=' : lis_equal,
                    '>' : lis_greater,
                    '<' : lis_lesser}                    

###################################################################################
#
# REPL
#
###################################################################################

boot = """(defmacro defn (name args forms) (def ~name (fn ~args ~forms)))"""

BANNER ="Welcome to LIS.PY\n\nA lisp like language written in Python.\nTotally experimental, " + \
    "and as a bonus, probably contains many serious bugs.\n\nIn other words, have fun!\n\n[To " + \
    "see reductions as they happen use /reductions on]"


def try_tokenization(stream):
    try:
        tokenize(stream)
        return 0
    except TypeError as err:
        _message, nest_level = err.args
        return nest_level

def evaluate(stream):
    return reduce(GLOBAL_NAMESPACE, parse(tokenize(stream)))

def repl():
    import readline
    prompt = "lis.py > "
    cli = ""

    # Setup initial environment
    reduce(GLOBAL_NAMESPACE, parse(tokenize(boot)))

    print(BANNER)

    while(True):
        cli += raw_input(prompt)
        if cli == "/reductions on":
            SHOW_REDUCTIONS = True
            print "Reduction printing on"
            cli = ""
            continue
        elif cli == "/reductions off":
            SHOW_REDUCTIONS = False
            print "Reduction printing off"
            cli = ""
            continue
        elif cli == "/show defines":
            print GLOBAL_NAMESPACE.__repr__()
            cli = ""
            continue
        else:
            nesting_level = try_tokenization(cli)
            if nesting_level is 0:
                try:
                    print evaluate(cli)
                except Exception as err:
                    print "Oops, you broke it. [%s]" % err.__str__()
                prompt = "lis.py > "
                cli = ""
            else:
                if nesting_level > 0:
                    cli += " "
                    prompt = "*        "
                    prompt += "    " * nesting_level
                else:
                    print "Mismatched parens, try again."
                    cli = ""
                    prompt = "lis.py > "

repl()