lisp.py

# -*- coding: utf-8 -*-

class Env:

    def __init__(self, bindings, parent=None):
        self.bindings = bindings
        self.parent = parent

    @staticmethod
    def init_env():
        return Env({
            x: x
            for x in 't nil quote if lambda define atom eq car cdr cons'.split()
        })

    @staticmethod
    def read(text):
        text_len = len(text)

        def skip_ws(ptr):
            while ptr < text_len and text[ptr] in ' 　\t\r\n':
                ptr += 1
            return ptr

        def f(ptr):
            ptr = skip_ws(ptr)
            if text_len <= ptr:
                raise Exception('Parse failed')
            elif text[ptr] == '(':
                xs = []
                last = 'nil'
                ptr = skip_ws(ptr + 1)
                while ptr < text_len and text[ptr] != ')':
                    if text[ptr] == '.':
                        last, ptr = f(ptr + 1)
                        break
                    sexp, ptr = f(ptr)
                    xs.append(sexp)
                    ptr = skip_ws(ptr)
                ptr = skip_ws(ptr)
                if text_len <= ptr or text[ptr] != ')':
                    raise Exception('Parse failed')
                ptr += 1
                for x in reversed(xs):
                    last = (x, last)
                return last, ptr
            else:
                start = ptr
                while ptr < text_len and text[ptr] not in ' 　\t\r\n)':
                    ptr += 1
                return text[start:ptr], ptr

        sexp, ptr = f(0)
        if ptr == text_len:
            return sexp
        else:
            raise Exception('Parse failed')

    @staticmethod
    def show(sexp):
        if isinstance(sexp, tuple):
            xs = []
            while isinstance(sexp, tuple):
                xs.append(Env.show(sexp[0]))
                sexp = sexp[1]
            if sexp != 'nil':
                xs.append('.')
                xs.append(Env.show(sexp))
            return '(' + ' '.join(xs) + ')'
        elif sexp is None:
            return 'nil'
        elif isinstance(sexp, str):
            return sexp
        else:
            return str(sexp)

    def eval(self, sexp):
        if isinstance(sexp, tuple):
            return self.apply(sexp)
        elif isinstance(sexp, str):
            if sexp in self.bindings:
                return self.bindings[sexp]
            else:
                return self.parent.eval(sexp)
        else:
            return sexp

    def apply(self, sexp):
        op = self.eval(sexp[0])
        bool_dict = {True: 't', False: 'nil'}
        if op == 'quote':
            return sexp[1][0]
        elif op == 'if':
            if self.eval(sexp[1][0]) != 'nil':
                return self.eval(sexp[1][1][0])
            else:
                return self.eval(sexp[1][1][1][0])
        elif op == 'lambda':
            return sexp
        elif op == 'define':
            self.bindings[sexp[1][0]] = self.eval(sexp[1][1][0])
            return 'nil'
        elif op == 'atom':
            return bool_dict[not isinstance(self.eval(sexp[1][0]), tuple)]
        elif op == 'eq':
            return bool_dict[self.eval(sexp[1][0]) == self.eval(sexp[1][1][0])]
        elif op == 'car':
            return self.eval(sexp[1][0])[0]
        elif op == 'cdr':
            return self.eval(sexp[1][0])[1]
        elif op == 'cons':
            return (self.eval(sexp[1][0]), self.eval(sexp[1][1][0]))
        else:
            f = lambda x: [x[0]] + f(x[1]) if isinstance(x, tuple) else []
            xs = list(map(self.eval, f(sexp)))
            return Env(dict(zip(f(xs[0][1][0]), xs[1:])), self).eval(xs[0][1][1][0])


def repl():
    env = Env.init_env()
    while True:
        print(env.show(env.eval(env.read(input()))))


if __name__ == '__main__':
    env = Env.init_env()
    print(env.show(env.read('abc')))
    print(env.show(env.read('()')))
    print(env.show(env.read('(a b c)')))
    print(env.show(env.read('(a b . c)')))
    print(env.show(env.eval(env.read('(cons (quote a) (quote b))'))))
    print(env.show(env.eval(env.read('(car (cons (quote a) (quote b)))'))))
    print(env.show(env.eval(env.read('(cdr (cons (quote a) (quote b)))'))))
    print(env.show(env.eval(env.read('(eq (quote a) (quote b))'))))
    print(env.show(env.eval(env.read('(eq (quote a) (quote a))'))))
    print(env.show(env.eval(env.read('(atom (quote a))'))))
    print(env.show(env.eval(env.read('(atom (quote (a . b)))'))))
    print(env.show(env.eval(env.read('(if t (quote a) (quote b))'))))
    print(env.show(env.eval(env.read('(if nil (quote a) (quote b))'))))
    print(env.show(env.eval(env.read('(define my-cons (lambda (a b) (cons a b)))'))))
    print(env.show(env.eval(env.read('(my-cons (quote 1) (quote 2))'))))

    repl()