FC2ブログ
--.--
--
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

01.11
Fri
なんか春休みに入ったぽいです

ということで簡単なLisp処理系みたいのをPythonで書いてみました

python sexparser.py

ってやるとインタプリタが起動すると思われます

python sexparser.py testcode.lisp

とかやるとtestcode.lispを実行すると思われます

以下はこの処理系的なもので動いたコードの例です


#定数的なのはdefconstで定義する
(defconst lst '(1 2 3 (2 4 (2 4 1 9 8) 2 3 0) 4 5))
(defconst factor 2)
(defconst x 10)
(defconst mult (lambda (x) (lambda (y) (* x y))))


#名前付きの関数は (define fname (arg1 arg2 ...) body) みたいな感じ

#(fact 5) -> 5!
(define fact (n)
	(if (= n 0)
		1
		(* n (fact (- n 1)))))

#(reverse '(1 2 3)) -> (3 2 1)
(define reverse (lst)
	(if (null? lst)
		nil
		(cons (last lst) (reverse (init lst)))))

#(delete '(2 3 4 (5 2 3) 2 9) 2) -> (3 4 (5 3) 9)
(define delete (lst factor)
	(if (null? lst)
		nil
		(if (list? (car lst))
			(cons (delete (car lst) factor) (delete (cdr lst) factor))
  			(if (equal? (car lst) factor)
				(delete (cdr lst) factor)
				(cons (car lst) (delete (cdr lst) factor))))))

#(append '(1 2 3) '(4 5 6)) -> (1 2 3 4 5 6)
(define append (lst1 lst2)
	(if (null? lst2)
		lst1
		(if (null? lst1)
			lst2
			(append (reverse (cons (car lst2) (reverse lst1))) (cdr lst2)))))


#(flatten '(1 2 (3 4 (5 6) 7) 8) ) -> (1 2 3 4 5 6 7 8)
(define flatten (lst)
	(if (null? lst)
		nil
		(if (list? (car lst))
			(append (flatten (car lst)) (flatten (cdr lst)))
			(cons (car lst) (flatten (cdr lst))))))

#(qsort '(2 3 0 -1 9 18)) -> (-1 0 2 3 9 18)
(define qsort (lst)
	(if (null? lst)
		nil
		((lambda (pv)
			(append
				(append
					(qsort (filter (lambda (x) (> pv x)) lst))
					(filter (lambda (x) (= x pv)) lst)
				)
				(qsort(filter (lambda (x)(< pv x)) lst))
			)
		)(car lst))))



(print lst)
(print (delete lst factor))
(print (reverse lst))
(print (fact x))
(print (append '(1 2 3) '(4 5)))
(print (flatten '(1 2 3 (3.1 3.2 3.3 (3.301 3.31) 3.4) 4 (4.01 4.02 (4.021 4.023) 4.03) 5)))
(print (qsort '(3 2 4 1)))
(print ((mult 3) 2))
#ラムダでfact
(print ((lambda (n self)
	(if (= n 0)
			1
			(* n (self (- n 1) self)))) 5 

		(lambda (n self)
			(if (= n 0)
					1
					(* n (self (- n 1) self))))))





winの実行可能なやつですダウンロードkeyはlisp

以下はPythonのそのコードになります.

なんかファイルアップロードできないみたいなので...そのまま貼りますね...




sexparser_new.py
#!/usr/bin/env python
#coding:utf-8

import constant_new as const
import functions_new as func
import types
import os
import sys

function = types.FunctionType
functionb = types.BuiltinFunctionType

def W_isatom(exp):
    _ , typ = evalconst(exp)
    return True if typ != const.LIST else False

def W_islist(exp):
    return not W_isatom(exp)

def W_isnil(exp):
    value ,typ = evalconst(exp)
    return True if typ == const.BOOLEAN and value == const.FALSE else False 

def W_isstring(exp):
    _ , typ = evalconst(exp)
    return True if typ == str else False 

def W_issymbol(exp):
    _ , typ = evalconst(exp)
    return True if typ == const.SYMBOL else False

def W_isbool(exp):
    _ , typ = evalconst(exp)
    return True if typ == const.BOOLEAN else False

def W_isfunction(exp):
    return isinstance(exp , function) or isinstance(exp , functionb)

#string1がstring2だけでなるか
def consis(str1 , str2):
    if str1 == "":
        return False
    elif len(str1) == 1:
        return True if str1[0] == str2 else False
    else:
        return False if str1[0] != str2 else consis(scdr(str1) , str2)

#文字列の先頭を返す
def scar(exp):return "" if exp == "" else exp[0]

#文字列の先頭以外を返す
def scdr(exp):return "" if exp == "" else exp[1:]

#文字列の最後を返す
def slast(exp):return exp[len(exp)-1]

#expの最初と最後がcarとlastである
def andeq(exp , car , last):return (scar(exp) == car) and (slast(exp) == last)

#辞書をくっつける.同一のキーがある場合は1番目が優先
def joindict(dic1 , dic2):
    for key in dic2:
        if not key in dic1:dic1[key] = dic2[key]
    return dic1

#nilであるか
def isnil(exp):
    #真偽値の定義からnilならnil
    if   exp == const.FALSE:
        return True
    #空のリストもnilとする
    elif exp == const.FALSE_:
        return True
    #空白が無駄に含まれていた場合. (          )
    elif andeq(exp , const.R_BACKET , const.L_BACKET) and exp[1] == " ":
        return isnil(const.R_BACKET + scdr(scdr(exp)))
    else:
        return False

#Lisp処理系の中で文字列となるか
def isstring(exp):
    #文字列ならば必ず最初と最後がダブルクォート
    #2文字以下なら無条件でアウト
    return False if (len(exp) < 2) or (not andeq(exp , const.D_QUOTE , const.D_QUOTE)) else True

#アトムであるか
def isatom(exp):
    #文字列なら無条件でアトム
    if isstring(exp):
        return True
    #'Aは(quote A)の略称なので
    elif scar(exp) == const.QUOTE :
        return False
    #括弧が含まれてなければアトム.シンボルとか
    elif (exp.find(const.R_BACKET) == -1) and (exp.find(const.L_BACKET) == -1):
        return True
    else:
        return False

#リストか否か
def islist(exp):return not isatom(exp)

#symbolかどうか
def issymbol(exp):
    return True if evalconst(exp)[1] == const.SYMBOL else False

def isquoted(exp):return True if exp[0] == const.QUOTE else False


#真偽値か否か
def isbool(exp):return (exp == const.TRUE) or (isnil(exp))


#リストをevalconstしたリストを返す
def mapevalconst(lst):return [evalconst(each)[0] for each in lst]

#リストを全てevalする
def mapeval(lst , scope):return [eval(each , scope) for each in lst]

#アトムとか真偽値とかの定数を評価する
def evalconst(exp):
    if W_isfunction(exp):return exp , const.FUNCTION
    exp = str(exp)
    if isbool(exp):
        if isnil(exp):
            return const.FALSE , const.BOOLEAN
        else:
            return const.TRUE , const.BOOLEAN
    if islist(exp):return exp , const.LIST
    if isstring(exp):return str(exp) , str
    #数かシンボルか
    try:
        float(exp)
        #実数か整数
        try:
            val = int(exp)
            if isinstance(val , int):
                return int(exp) , int
            else:
                #明示的にLがついてない場合の長整数をみつける
                return long(exp) , long
        except:
            return float(exp) , float
    except:
        #ここにきたなら長整数かシンボル
        try:
            long(exp)
            return long(exp) , long
            #長整数ただし、明示的にLのついてるものとする
        except:
            #ここにきたならシンボル
            return exp , const.SYMBOL

#文字列のリストをパーサにかける
def part(exp):
    ins = SexpressionParser(exp)
    argv = ins.argv[0:len(ins.argv)-1]
    return ins.car , argv

#関数名部と引数部にわけない
def tokenize(exp):
    car , cdr = part(exp)
    cdr.insert(0,car)
    return cdr



#引数を評価して普通に実行
def exec_nf(fname , argv , scope):
    if func.FUNCTIONS[fname][const.SCOPE]:
        return apply(func.FUNCTIONS[fname][const.FUNC_INS] , [eval(each , scope) for each in argv] , scope)
    else:
        return apply(func.FUNCTIONS[fname][const.FUNC_INS] , [eval(each , scope) for each in argv])


#引数を評価しないで関数の実行. 文字列のリスト"(+ 1 2 3)"みたいのが渡る
def exec_sf(fname , argv , scope):
    argv.append(scope)
    return apply(func.FUNCTIONS[fname][const.FUNC_INS] , argv)

#関数を実行
def exec_f(fname , argv , scope):
    fname = eval(fname , scope)
    if (not fname in func.FUNCTIONS) and (not isinstance(fname , function)) : 
        raise Error(const.ERROR["FUNC_UNDEF"] %(fname))
    if isinstance(fname , function):
        #ラムダでfnameには関数の自体が入ってるはず
        return apply(fname , [eval(eacharg , scope) for eacharg in argv])
    if func.FUNCTIONS[fname][0]:
        return exec_nf(fname , argv , scope)
    else:
        return exec_sf(fname , argv , scope)



#eval("(+ x y z)" , {"x": 1 , "y": 2 , "z": 3})
#eval("(fact x)" , {"x": 5})
def eval(exp , scope = const.GLOBAL_VALUE):
    value , typ = evalconst(exp)
    #アトムは評価してもそのまま
    if typ != const.SYMBOL and typ != const.LIST:return value
    
    # これ以降スコープを考慮した評価を行う必要がある
    # 特にシンボルについて

    #nilで無いリストがくるよー. クォートされてんのが厄介だ
    if typ == const.LIST:
        #クォートの除去
        if isquoted(exp):return scdr(exp)
        (fname , arg) = part(exp)
        #(equal (car '(1 2 3)) 1) で(car '(1 2 3))を評価すると文字列の"1"が返ってしまい,かたや1はintがかえるので
        #evalconstするしたも同じ
        return evalconst(exec_f(fname , arg , scope))[0] 
    elif typ == const.SYMBOL:
        if not exp in scope:
            #スコープ内で定義されてないシンボル名だけど実は関数名だった場合
            if exp in func.FUNCTIONS:
                return exp
            else:
                raise Error(const.ERROR["NO_VAL"] %exp)
        else:
            return evalconst(scope[exp])[0]
    else:
        #ここにはこないはず
        pass




#真偽値の変換
def booltolisp(boolean): return const.TRUE if boolean else const.FALSE

#真偽値の変換
def booltopy(boolean) : return False if boolean == const.FALSE else True

#ファイルからn個のS式を読む
def filereader(filepath):
    #n個のS式を返す
    code = \
    [each for each in  [eachline.strip(const.EOL_PATTERN) for eachline in open(os.path.expanduser(filepath)).readlines() ] if each != "" and each[0] != const.COMMENT] 
    result= []
    fix = ""
    fixflag = 0
    for each in code:
        if isatom(each) and fixflag == 0:
            result.append(each)
        #整形の必要のないS式
        elif (each.count(const.R_BACKET) == each.count(const.L_BACKET)) and fixflag == 0:
            result.append(each)
        #整形が必要なS式
        else:
            fix += each + " "
            if fix.count(const.R_BACKET) == fix.count(const.L_BACKET):
                fixflag = 0
                result.append(fix.strip(const.EOL_PATTERN))
                fix = ""
            else:
                fixflag = 1    
    return result


#debug用
def Debug(exp):SexpressionParser(exp).debug()

#例外の送出クラス
class Error(Exception):
    def __init__(self , message):
        self.message = message
    def __str__(self):
        return repr(self.message)


#S式パースするクラス
class SexpressionParser:

    def __init__(self , expr_string):
        self.expr   = expr_string
        self.isnil  = isnil(self.expr)
        self.isatom = isatom(self.expr)
        self.length = len(self.expr)
        self.qtflg  = False
        self.car    = self.getcar()
        self.argv   = self.getargv()

    def debug(self):
        print "EXPR: %s"     %(self.expr)
        print "EXPR LEN: %s" %(self.length)
        print "ISATOM: %s"   %(self.isatom)
        print "ISNIL: %s"    %(self.isnil)
        print "CAR: \"%s\""  %(self.car)
        print "CDR: %s"      %(self.argv)
        print 

    def getcar(self):
        if self.isatom:return ""
        if self.isnil: return const.FALSE

        result = "" 
        backf  = 0
        dblqt  = False
        cnt    = 1
        escp   = 0
        first  = True 
      
        #糖衣構文クォートの特殊用
        if self.expr[0] == const.QUOTE:
            self.qtflg = True
            self.argv  = [scdr(self.expr) , const.FALSE] 
            return const.QUOTE
        
        #(if(= 1 1)true(car '(1 2 3)))
        #(car '(1 2 3))
        while self.length - 1> cnt :
            char = self.expr[cnt:cnt+1]

            #先頭の空白を除去するため
            if first and char == " ":
                cnt += 1
                continue
            else:
                first = False

            #if ((char==const.R_BACKET)and(backf == 0))and(not dblqt)and(result != "")and(char==const.QUOTE):break
            if ((char==const.R_BACKET)and(backf == 0))and(not dblqt)and(result != "")and(not consis(result , const.QUOTE)):break


            #左右の括弧でフラグを調節
            if char == const.R_BACKET:backf += 1
            if char == const.L_BACKET:backf -= 1

            if char == const.D_QUOTE and (escp == 0) : dblqt = not dblqt
            escp = 1 if char == "\\" else 0
            if ((char == " ") and (backf == 0)) and (not dblqt):break
            result += char 
            if ((char == const.L_BACKET) and (backf == 0)) and (not dblqt) and (result != ""):break
            cnt += 1
        return result
 
    def getargv(self):
        result = []        
        if self.qtflg:return self.argv 
        if self.isatom or isnil(self.expr):return result
        nxt = const.R_BACKET + self.expr[self.expr.find(self.car)+len(self.car):]
        ins = SexpressionParser(nxt)
        result.append(ins.car)
        result.extend(ins.argv)
        return result

def test(codelst):
    for each in map(eval , codelst):print each

def main():
    if len(sys.argv) > 1:
        map(eval , filereader(sys.argv[1]))
    else:
         while True:
            try:
                print eval(raw_input(">>> "))
            except Exception,i:
                print i.message

if __name__ == "__main__" : main()






functions_new.py
#!/usr/bin/env python
#coding:utf-8

import sexparser_new as pr
import constant_new as const
import math
import sys


def functionisntace(func):
    if pr.W_isfunction(func):
        return func
    elif (func in const.GLOBAL_VALUE) and (pr.W_isfunction(const.GLOBAL_VALUE[func])):
        return functionisntace(const.GLOBAL_VALUE[func])
    elif func in FUNCTIONS:
        return functionisntace(FUNCTIONS[func][1])
    else:
        raise pr.Error(const.ERROR["FUNC_UNDEF"]%(func))


#(define fact (n) (if (= n 0) 1 (* n (fact (- n 1)))))
#funcname = "fact"
#["fact" , "(n)" , "(if ..)" , scope]
#(define fact (n))

#こいつが関数の実態
#(True,(lambda *arg:pr.eval(body,scope=pr.joindict({e:arg[i]for i,e in enumerate(pr.tokenize(argv))},scope))))
def makefunc(dmyarg ,body,scope):

    def FUNCTION(*arg):
        #ここで束縛されるargは実引数となる
        #dmyargは"(x , y , z)"みたいな仮引数
        if dmyarg == "nil": 
            lst = [pr.eval(each , scope) for each in body]
        else:
            s = pr.joindict({e:arg[i]for i,e in enumerate(pr.tokenize(dmyarg))},scope) 
            lst = [pr.eval(each , s) for each in body]
        return lst.pop()

    return FUNCTION

#(define fname (arg))
def define(*arg):
    if len(arg) < 3:raise pr.Error(const.ERROR["FUNC_ARGST"] %("define" , "more than 2"))

    scope = arg[len(arg)-1]

    fname = arg[0]
    argv  = arg[1]
    body  = arg[2:len(arg)-1]
    
    if not pr.issymbol(fname) :
        raise pr.Error(const.ERROR["NOT_SYMBL"]%(fname))
    
    #引数を全て評価するような関数しかユーザ定義ではできない
    #スコープも得れない
    FUNCTIONS[fname] = (True , makefunc(argv , body , scope) , False) 
    return fname

#(defconst SYMBOL VALUE)
def defconst(symbol , value , scope):
    if not pr.issymbol(symbol):raise pr.Error(const.ERROR["NOT_SYMBL"]%(symbol))


    if symbol in const.GLOBAL_VALUE:return const.GLOBAL_VALUE[symbol]

    val = pr.eval(value,scope) 
    const.GLOBAL_VALUE[symbol] = val
    return val

#printが関数じゃないからしょうがなく定義
def show(exp):
    print exp
    return exp


#リストを作る関数
def makelist(*seq):
    return pr.evalconst(const.R_BACKET + reduce((lambda x,y: str(x) + " " + str(y)) , seq , "").strip(" ") + const.L_BACKET)[0]


#(lambda(x)x)
#('(x)', 'x', {})
#(lambda(x)(print x)(print x))
#('(x)','(print x)' , '(print x)',{})
#(lambda(x))
def lmd(*arg):

    if len(arg) < 2 : raise pr.Error(const.ERROR["FUNC_ARGST"] %("lambda" , "more than 1" ))

    scope = arg[len(arg)-1]
    argv  = arg[0]
    body  = arg[1:len(arg)-1]

    return makefunc(argv , body , scope)
    

def last(lst):
    l = pr.tokenize(lst)
    #nilだったらnil
    return const.FALSE if l[0] == "" else l[len(l)-1]

def init(lst):
    l = pr.tokenize(lst)
    return apply(makelist , l) if l[0] == "" else apply(makelist , l[0:len(l)-1])

def map_(func , lst ):
    l = pr.tokenize(lst)
    #nilだったらnil
    if l == [""] : return const.FALSE
    #tokenizeでばらした要素そのままでは文字列のままである
    return apply(makelist , map(functionisntace(func) , pr.mapevalconst(l)))


def filter_(func , lst):
    l = pr.tokenize(lst)
    if l == [""] : return const.FALSE
    return apply(makelist , [elm for elm in pr.mapevalconst(l) if pr.booltopy(functionisntace(func)(elm))])


def fin():
    print "bye!"
    sys.exit()


#{関数名: (引数を評価していいか , 関数の実態 , scopeが欲しいか)}
#評価しないFalseな関数にはscopeが与えられる
FUNCTIONS = {\
    "sin"     :(True , math.sin , False), 
    "cos"     :(True , math.cos , False),
    "tan"     :(True , math.tan , False),
    
    "+"       :(True , (lambda *arg: reduce((lambda x,y: x+y) , arg)) , False),
    "-"       :(True , (lambda *arg: reduce((lambda x,y: x-y) , arg)) , False),
    "*"       :(True , (lambda *arg: reduce((lambda x,y: x*y) , arg)) , False),
    "/"       :(True , (lambda *arg: reduce((lambda x,y: x/y) , arg)) , False),
    ">"       :(True , (lambda x,y: pr.booltolisp(x>y)) , False),
    ">="      :(True , (lambda x,y: pr.booltolisp(x>=y)), False),
    "<"       :(True , (lambda x,y: pr.booltolisp(x<y)) , False),
    "<="      :(True , (lambda x,y: pr.booltolisp(x<=y)) , False),
    "="       :(True , (lambda x,y: pr.booltolisp(x == y)) , False),
    "and"     :(True , (lambda x,y: pr.booltolisp(pr.booltopy(x) and pr.booltopy(y))) , False),
    "or"      :(True , (lambda x,y: pr.booltolisp(pr.booltopy(x) or pr.booltopy(y))) , False),
    "not"     :(True , (lambda x: pr.booltolisp(not pr.booltopy(x)) ) , False),
  
    "cons"    :(True , (lambda x,y: apply(makelist,[x] + pr.tokenize(y))) , False),
    "car"     :(True , (lambda x:pr.tokenize(x)[0]) , False),
    "cdr"     :(True , (lambda x:apply(makelist ,pr.tokenize(x)[1:])) , False),
    "list"    :(True , makelist , False),
    "last"    :(True , last , False),
    "length"  :(True , (lambda x: len(pr.tokenize(x))) , False),
    "init"    :(True , init , False),
    "map"     :(True , map_ , False),
    "filter"  :(True , filter_  , False),

    "list?"   :(True , (lambda x:pr.booltolisp(pr.W_islist(x))) , False),
    "atom?"   :(True , (lambda x:pr.booltolisp(pr.W_isatom(x))) , False),
    "null?"   :(True , (lambda x:pr.booltolisp(pr.W_isnil(x))) , False),
    "equal?"  :(True , (lambda x,y: pr.booltolisp(x == y)) , False),
    
    "print"   :(True , (lambda x: show(x)) , False),
    "define"  :(False , define , False),
    "defconst":(False , defconst , False),
    "lambda"  :(False , lmd , False),
    "if"      :(False , (lambda c,x,y,s: pr.eval(x,s) if pr.booltopy(pr.eval(c,s)) else pr.eval(y,s)) , False),

    "exit"    :(True , fin , False)
}




constant_new.py
#!/usr/bin/env python
#coding:utf-8

#グローバル変数
GLOBAL_VALUE = {}


#コメントは何ではじまるか
COMMENT = "#"

#文字列用
D_QUOTE = "\""

#評価を避ける記号
QUOTE     = "\'"

#括弧の定義
R_BACKET  = "("
L_BACKET  = ")"

#無限大の定義
inf = float("inf")

#ファイルからS式を呼んだ時の形の整形用
EOL_PATTERN = " \t\n"

#真偽値の定義
TRUE = "true"
FALSE = "nil"
FALSE_ = "()"


#型の名前
LIST = "list"
BOOLEAN = "boolean"
FUNCTION = "function"
INT = "int"
LONG = "long"
FLOAT = "float"
STRING = "string"
SYMBOL = "symbol"




#エラー文
ERROR = {\
    "FUNC_UNDEF": "Error: undefined function name %s" , 
    "FUNC_ARGST": "Error: %s function takes %s arguments" ,
    "NO_VAL"    : "Error: variable %s has no value" ,
    "VAL_UNDEF" : "Error: variable %s can not be used",
    "NOT_SYMBL" : "Error: %s is not a symbol",
}

SP_FUNC = 0
FUNC_INS = 1
SCOPE = 2



スポンサーサイト
comment 0 trackback 0
トラックバックURL
http://telracsmoratori.blog.fc2.com/tb.php/155-5e4ad4b1
トラックバック
コメント
管理者にだけ表示を許可する
 
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。