PythonでLISPっぽい何かを作ってみた

Pythonでのインタプリタのコードは、本体は200行程度で、builtinで100行程度の300行程度です。一番やりたかったのはmacro機構を実装してみたかったこと。

一般のデータに対しては、整数以外の関数は組み込んでないのですが、以下のようなコード例を解釈できます。

; arith
(say (* (+ 1 2) 10)) ; => 30

; cell
(say (cons 1 nil)) ; => (1)
(say (head (cons 1 nil))) ; => 1

; set
(set (quote hoge) 10)
(say (+ 10 hoge)) ; => 20

; lambda
(say ((lambda (a b) (* (+ a b) a)) 10 5)) ; => 150

; macros
(set (quote =) (macro (var value)
  ; `(set (quote ,var) ,value)
  (list (quote set) (list (quote quote) var) value)))

(= foo 5)
(say foo) ; => 5

(= if (macro (nil? is_not_nil is_nil)
  ; `(cond ,nil? ,is_not_nil ,is_nil)
  (list (quote cond) nil? is_not_nil is_nil)))

(if 1 (say 1) (say 0)) ; => 1
(if nil (say 1) (say 0)) ; => 0


(= fun lambda)
(= \ fun)
(= let (macro ((name value) body)
  ; `((fun (,name) ,body) ,value)
  (list (list (quote fun) (list name) body) value)))
(say (let (foo 30) (+ foo 10))) ; => 40

(= let* (macro args
               (if (tail args) ; (one-more? args)
                   ; `(let ,(head args) (let* ,@(tail args)))
                   (list (quote let) (head args)
                                     (cons (quote let*) (tail args)))
                   (head args))))
(say (let* (foo 10)
           (bar (+ foo 20))
           bar)) ; => 30


(= fact (\ (n) (if (== n 0) 1 (* n (fact (- n 1))))))
(say (fact 5)) ; => 120

; prototype based object system
(= newCount
   (ctor (\ (num)
            (do
             (self:= add (\ (other) (+ num other)))
             (self:= append (\ (other) (= num (+ num other))))
             (self:= get (\ () num))
             self))))

(= count (newCount 5))
; (say count) ; => <Scope>
(say (count:add 10)) ; => 15
(count:append 20)
(say (count:get)) ; => 25

condやdo、ファーストクラスmacroあたりはArcの表現を借りてます。あとsetはシンボルに対して環境に変数スロットがある風に値を更新するのではなく、直接環境に値をセットしていて、単一名前空間のレキシカルスコープにしてるので、この辺もArcっぽいかもしれない。

あと、おまけに、環境をオブジェクトにできるprototypeベースのオブジェクトシステムも組み込んでみました。メソッド呼び出しの基本構文((bind obj method) ...)を(obj:method ...)と記述できるようにしてもあります。

インタプリタはpythonで記述してあるけれど、今回Python独自の言語機能はほとんど使用しませんでした。

# LISP like language: lexical, single namespace, symbol based, S-exp only

# cell and symbol
class Memory(object):
    def __repr__(self):
        return self.show()
    def is_nil(self):
        return False
    pass

class Cons(Memory):
    def __init__(self, head=None, tail=None):
        self.head = head
        self.tail = tail
        pass
    def show_inner(self):
        heads = "()" if self.head is None else self.head.show()
        if self.tail is None: return heads
        tails = self.tail.show_inner()
        return "%s %s" % (heads, tails)
    def show(self):
        return "(%s)" % self.show_inner()

def list2cons(objlist, last=None):
    ctxt = last
    rev = list(xrange(len(objlist)))
    rev.reverse()
    for i in rev:
        ctxt = Cons(objlist[i], ctxt)
        pass
    return ctxt

class Atom(Memory):
    def show_inner(self):
        return ". %s" % self.show()
    pass

class Symbol(Atom):
    def __init__(self, name):
        self.name = name
        pass
    def show(self):
        return self.name
    pass

# parser
def parse(code):
    return Parser().parse(code)

import re
class Parser(object):
    def parse(self, code):
        objs, code = self.parseCodes(code)
        s, code = self.parseSpaces(code)
        if code == "": return objs
        return None
    def parseSpaces(self, code):
        match = re.match(r"^\s*(;[^\n]*\n\s*)*", code)
        return code[match.start():match.end()], code[match.end():]

    def parseSymbol(self, code):
        match = re.match(r"^[^(),\s]+", code)
        if not match: return None
        return Symbol(code[match.start():match.end()]), code[match.end():]

    def parseList(self, code):
        if code == "": return None
        if code[0] != "(": return None
        objs, code = self.parseCodes(code[1:])
        s, code = self.parseSpaces(code)
        if code[0] == ")": return list2cons(objs), code[1:]
        if code[0] != ".": return None
        last, code = self.parseCode(code[1:])
        s, code = self.parseSpaces(code)
        if code[0] != ")": return None
        return list2cons(objs, last), code[1:]

    def parseCode(self, code):
        s, code = self.parseSpaces(code)
        ret = self.parseSymbol(code)
        if ret: return ret
        return self.parseList(code)

    def parseCodes(self, code):
        objs = []
        while True:
            if code == "": break
            ret = self.parseCode(code)
            if not ret: break
            obj, code = ret
            objs.append(obj)
            pass
        return objs, code
    pass

# runtime evaluator
class Scope(Atom):
    def __init__(self, parent=None):
        self.dict = {}
        self.dict["parent"] = parent
        pass
    def caller(self):
        return self.dict["parent"] if "parent" in self.dict else None
    def get(self, name):
        if name in self.dict: return self.dict[name]
        if self.caller(): return self.caller().get(name)
        return None
    def put(self, name, value):
        self.dict[name] = value
        return value
    def update(self, name, value):
        if name in self.dict:
            self.dict[name] = value
            return value
        if self.caller(): return self.caller().update(name, value)
        return None
    def show(self):
        return "<Scope>"
    def eval(self, obj):
        if isinstance(obj, Symbol): return self.get(obj.name)
        if isinstance(obj, Cons):
            func = self.eval(obj.head)
            return func.call(obj.tail, self)
        return obj
    pass


# for misc func
class Callable(Atom):
    def __init__(self, callable):
        self.callable = callable
        pass
    def show(self):
        return repr(self.callable)
    def call(self, cons, env):
        return self.callable(cons, env)
    def apply(self, scope, cons, env):
        return self.call(cons, env)
    pass

# Base Language Objects with unboxed call
class Value(Atom):
    def __init__(self, value):
        self.value = value
        pass
    def show(self):
        return repr(self.value)
    def call(self, cons, env):
        args = []
        while cons is not None:
            arg = env.eval(cons.head)
            args.append(arg.value) # unbox only Value
            cons = cons.tail
            pass
        return Value(self.value(*args))
    def apply(self, scope, cons, env):
        return self.call(cons, env)
    def is_nil(self):
        return self.value is False or self.value is None
    pass

def eval_list(cons, env):
    if cons is None: return None
    head = env.eval(cons.head)
    return Cons(head, eval_list(cons.tail, env))

def match_pattern(scope, pattern, cons):
    if isinstance(pattern, Symbol):
        scope.put(pattern.name, cons)
        return
    elif isinstance(pattern, Cons):
        match_pattern(scope, pattern.head, cons.head)
        match_pattern(scope, pattern.tail, cons.tail)
        return
    return

# (lambda (a1 a2 ...) body)
class Lambda(Atom):
    def __init__(self, cons, env):
        self.cons = cons
        self.env = env
        pass
    def show(self):
        return Cons(Symbol("lambda"), self.cons).show()
    def call(self, cons, env):
        scope = Scope(self.env)
        return self.apply(scope, cons, env)
    def apply(self, scope, cons, env):
        cons = eval_list(cons, env)
        args = self.cons.head
        match_pattern(scope, args, cons)
        body = self.cons.tail.head
        return scope.eval(body)
    pass

# (macro (a1 a2 ...) gencode)
class Macro(Atom):
    def __init__(self, cons, env):
        self.cons = cons
        self.env = env
        pass
    def show(self):
        return Cons(Symbol("lambda"), self.cons).show()
    def call(self, cons, env):
        expanded = self.expand(cons, env)
        # print expanded
        return env.eval(expanded)
    def apply(self, scope, cons, env):
        expanded = self.expand(cons, env)
        return scope.eval(expanded)
    def expand(self, cons, env):
        scope = Scope(self.env)
        args = self.cons.head
        body = self.cons.tail.head
        match_pattern(scope, args, cons)
        expanded = scope.eval(body)
        return expanded
    pass

# builtins
import sys
class Builtins(Scope):
    def __init__(self):
        Scope.__init__(self)
        # basic
        self.put("lambda", Callable(Lambda))
        self.put("macro", Callable(Macro))
        self.put("nil", None)
        self.put("quote", Callable(lambda cons, env: cons.head))
        def listFunc(cons, env):
            if cons is None: return None
            head = env.eval(cons.head)
            tail = listFunc(cons.tail, env)
            return Cons(head, tail)
        self.put("list", Callable(listFunc))
        def doFunc(cons, env):
            head = env.eval(cons.head)
            if cons.tail is None: return head
            return doFunc(cons.tail, env)
        self.put("do", Callable(doFunc))
        def headFunc(cons, env):
            data = env.eval(cons.head)
            return data.head
        self.put("head", Callable(headFunc))
        def tailFunc(cons, env):
            data = env.eval(cons.head)
            return data.tail
        self.put("tail", Callable(tailFunc))
        def consFunc(cons, env):
            head = env.eval(cons.head)
            tail = env.eval(cons.tail.head)
            return Cons(head, tail)
        self.put("cons", Callable(consFunc))
        def condFunc(cons, env):
            last = env.eval(cons.head)
            if cons.tail is None: return last
            if last is not None and not last.is_nil():
                return env.eval(cons.tail.head)
            return condFunc(cons.tail.tail, env)
        self.put("cond", Callable(condFunc))
        def setFunc(cons, env):
            head = env.eval(cons.head)
            tail = env.eval(cons.tail.head)
            return env.put(head.name, tail)
        self.put("set", Callable(setFunc))

        # object
        def ctorFunc(cons, env):
            ctor = env.eval(cons.head)
            def create(cons, cenv):
                obj = Scope(env)
                obj.put("self", obj)
                ctor.apply(obj, cons, cenv)
                return obj
            return Callable(create)
        self.put("ctor", Callable(ctorFunc))
        def newFunc(cons, env):
            obj = Scope(env)
            obj.put("self", obj)
            return obj
        self.put("new", Callable(newFunc))
        def bindFunc(cons, env):
            target = env.eval(cons.head)
            #print cons.tail.head
            method = target.eval(cons.tail.head)
            def bound(cons, env):
                return method.apply(target, cons, env)
            return Callable(bound)
        self.put("bind", Callable(bindFunc))

        # system
        def evalFunc(cons, env):
            data = env.eval(cons.head)
            return env.eval(data)
        self.put("eval", Callable(evalFunc))
        def parseFunc(cons, env):
            code = env.eval(cons.head)
            return list2cons(parse(code.value))
        self.put("parse", Callable(parseFunc))
        def sayFunc(cons, env):
            result = env.eval(cons.head)
            show = "nil" if result is None else result.show()
            sys.stdout.write(show + "\n")
            return result
        self.put("say", Callable(sayFunc))
        def writeFunc(cons, env):
            result = env.eval(cons.head)
            sys.stdout.write(result.value)
            return result
        self.put("write", Callable(writeFunc))
        def readFunc(cons, env):
            return Value(sys.stdin.readline().strip())
        self.put("read", Callable(readFunc))

        # operators
        self.put("+", Value(lambda a, b: a + b))
        self.put("-", Value(lambda a, b: a - b))
        self.put("*", Value(lambda a, b: a * b))
        self.put("/", Value(lambda a, b: a / b))
        self.put("%", Value(lambda a, b: a % b))
        self.put("==", Value(lambda a, b: a == b))
        pass
    def get(self, name):
        if re.match(r"^-?[\d]+$", name): return Value(int(name)) # literal
        match = re.match(r"^([^:]+):([^:]+)$", name)
        if match:
            recv, name = match.groups()
            pair = Cons(Symbol(recv), Cons(Symbol(name), None))
            bind = self.get("bind")
            def bound(cons, env):
                method = bind.call(pair, env)
                return method.call(cons, env)
            return Callable(bound)
        return Scope.get(self, name)
    pass

if __name__ == "__main__":
    filename = sys.argv[1]
    code = open(filename).read()
    datalist = parse(code)
    # print datalist
    env = Builtins()
    for data in datalist:
        env.eval(data)
        pass
    pass