Lisp.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys, traceback

nil = type('Nil', (), {'__str__': lambda self: '()'})()
undef = type('Undef', (), {'__str__': lambda self: '#<undef>'})()
f = type('F', (), {'__str__': lambda self: '#f'})()
t = type('T', (), {'__str__': lambda self: '#t'})()

class Cell:

    def __init__(self, car=nil, cdr=nil):
        self.car = car
        self.cdr = cdr

    def __str__(self):
        return '(' + str(self.car) + ' . '+ str(self.cdr) + ')'

    def __eq__(self, x):
        if x is nil:
            return self.car is nil and self.cdr is nil
        elif isinstance(x, Cell):
            return self.car == x.car and self.cdr == x.cdr
        else:
            return False
    
class Symbol:

    def __init__(self, exp):
        self.exp = exp

    def __str__(self):
        return self.exp

    def __eq__(self, x):
        return self.exp == x

    def __hash__(self):
        return hash(self.exp)

class Procedure:

    def __init__(self, exp, pars, env):
        self.exp = exp
        self.pars = pars
        self.env = env

    def __str__(self):
        return '#<procedure>'

class Macro:

    def __init__(self, proc):
        self.proc = proc

class Lexer:

    def __init__(self, data):
        self.data = list(data+'\0')
        self.move()

    def move(self):
        if not self.data:
            raise SyntaxError()
        self.token = self.data.pop(0)
    
    def get_sexp(self):

        if self.token.isspace():
            self.move()
            return self.get_sexp()
        elif self.token == '(':
            self.move()
            return self.get_list()
        elif self.token == '\'':
            self.move()
            return self.get_quote()
        elif self.token == '"':
            self.move()
            return self.get_string()
        elif self.token == '#':
            self.move()
            if self.token == '\\':
                self.move()
                return self.get_char()
            elif self.token == 't':
                self.move()
                return t
            elif self.token == 'f':
                self.move()
                return f
        else:
            return self.get_atom()

    def get_list(self):
        
        while self.token.isspace():
            self.move()

        if self.token == ')':
            self.move()
            return nil

        cell = Cell()
        cell.car = self.get_sexp()

        while self.token.isspace():
            self.move()

        if self.token == '.':
            self.move()
            cell.cdr = self.get_sexp()
            while self.token.isspace(): self.move()
            self.move()
            return cell
        else:
            cell.cdr = self.get_list()
            return cell


    def get_quote(self):

        cell = Cell()
        cell.car = Symbol('quote')
        cell.cdr = Cell(self.get_sexp(), nil)

        return cell

    def get_char(self):

        ch = self.token
        self.move()
        while self.token not in (' ', '\t', '\n', '(', ')', '\0'):
            ch += self.token
            self.move()

        if len(ch) == 1:
            return ch
        elif ch in ('space'):
            return ' '
        elif ch in ('newline', 'linefeed'):
            return '\n'
        elif ch in ('return'):
            return '\r'
        elif ch in ('tab'):
            return '\t'

    def get_string(self):
        
        if self.token == '"':
            self.move()
            return ''
        else:
            if self.token == '\\':
                self.move()
                if self.token == '\\':
                    self.move()
                    head = '\\'
                elif self.token == '"':
                    self.move()
                    head = '"'
            else:
                head = self.token
                self.move()

            tail = self.get_string()
            return head+tail

    def get_atom(self):

        atom = ''
        while self.token not in ('(', ')', ' ', '\n', '\t', '\0'):
            atom += self.token
            self.move()

        try:
            return int(atom)
        except ValueError:
            try:
                return float(atom)
            except:
                return Symbol(atom)

class Env(dict):

    def __init__(self, params=(), args=(), outer=None):
        if outer is None:
            self.add_global_vars()
            self.add_global_macros()

        self.update(zip(params, args))
        self.outer = outer

    def find(self, var):
        try:
            return self[var] if var in self else self.outer.find(var)
        except:
            raise Exception("Not found the symbol: "+str(var))
    
    def add_global_vars(self):
        import operator as op
        funcs = {
            'cons': lambda x,y: Cell(x,y),
            'car': lambda x: x.car,
            'cdr': lambda x: x.cdr,
            '+': lambda *args: reduce(op.add, args),
            '-': lambda *args: reduce(op.sub, args),
            '*': lambda *args: reduce(op.mul, args),
            '/': lambda *args: reduce(op.div, args),
            'mod': lambda x,y: t if x % y == 0 else f,
            'not': lambda x: f if x == t else t,
            '>': lambda x,y: t if x > y else f,
            '<': lambda x,y: t if x < y else f,
            '>=': lambda x,y: t if x >= y else f,
            '<=': lambda x,y: t if x <= y else f,
            '=': lambda x,y: t if x == y else f,
            'equal?': lambda x,y: t if x == y else f,
            'eq?': lambda x,y: t if x is y else f,
            'list?': lambda x: t if isinstance(x, Cell) else f,
            'null?': lambda x: t if x == nil else f,
            'symbol?': lambda x: t if isinstance(x, Symbol) else f,
            'atom?': lambda x: t if not isinstance(x, Cell) else f,
            'println': lambda x: sys.stdout.write(str(x)+'\n') or undef,
            }

        for name, cont in funcs.items():
            self[Symbol(name)] = cont

    def add_global_macros(self):
        pass

def evals(x, env):

    if isinstance(x, Symbol):
        return env.find(x)

    elif not isinstance(x, Cell):
        return x

    elif x.car == 'quote':
        return x.cdr.car

    elif x.car == 'if':
        c = evals(x.cdr.car, env)
        if c == t:
            return evals(x.cdr.cdr.car, env)
        elif c == f:
            return evals(x.cdr.cdr.cdr.car, env)
        else:
            raise Exception('test must be #t or #f')

    elif x.car == 'set!':
        var = x.cdr.car
        exp = x.cdr.cdr.car
        if var in env:
            env[var] = evals(exp, env)
            return env[var]
        else:
            raise Exception('{0} is not binded before'.format(var))

    elif x.car == 'define':
        var = x.cdr.car
        exp = x.cdr.cdr.car
        env[var] = evals(exp, env)
        return var

    elif x.car == 'lambda':
        pars = x.cdr.car
        exp = x.cdr.cdr.car
        return Procedure(exp, pars, env)

    elif x.car == 'begin':
        local_env = Env(outer=env)
        exp = x.cdr
        while not exp == nil:
            val = evals(exp.car, local_env)
            exp = exp.cdr
        return val

    elif x.car == 'define-macro':
        name = x.cdr.car
        proc = x.cdr.cdr.car
        env[name] = Macro(evals(proc, env))
        return undef

    else:
        proc = evals(x.car, env)
        if isinstance(proc, int) or isinstance(proc, float) or isinstance(proc, str) or (proc in (nil, t, f)):
            return proc
        elif isinstance(proc, Macro):
            return evals(proc.proc.eval(x.cdr), env)
        elif isinstance(proc, Procedure):

            def eval_rec(exps):
                if exps == nil:
                    return nil
                else:
                    head = evals(exps.car, env)
                    tail = eval_rec(exps.cdr)
                    return Cell(head, tail)

            def eval_zip(pars, args):
                binds = {}
                if pars == nil:
                    return binds
                elif isinstance(pars, Cell):
                    binds[pars.car] = evals(args.car, env)
                    binds.update(eval_zip(pars.cdr, args.cdr))
                    return binds
                else:
                    binds[pars] = eval_rec(args)
                    return binds

            binds = eval_zip(proc.pars, x.cdr)

            return evals(proc.exp, Env(binds.keys(), binds.values(), proc.env))
        else:
            args = []
            elem = x.cdr
            while not elem == nil:
                args.append(evals(elem.car, env))
                elem = elem.cdr
            return proc(*args)


if __name__ == '__main__':
    print '//////////////////////////////////'
    print '/// Lisp Interpreter by wasabi ///'
    print '//////////////////////////////////'
    print 'Type "quit" to exit interactive mode'
    print 

    global_env = Env()

    while True:
        print 'そんなS式で大丈夫か? >>', 
        s = raw_input()
        if s == 'quit':
            break
        elif s == '':
            continue
        else:
            try:
                print evals(Lexer(s).get_sexp(), global_env)
            except SyntaxError:
                print 'Syntax Error!'
            except:
                print 'Rumtime Error!'
                print '-'*30
                traceback.print_exc(file=sys.stdout)
                print '-'*30


    print 'Bye-Bye!'