動手寫一門簡單語言吧喵

目錄:

介紹篇:

也就是本文啦

正文:

1. 從計算姬開始

2. (企劃中...)

3. (企劃中...)

4. 宏展開與衛生宏展開

番外:

1. CPS變換與CPS變換編譯

先簡單介紹一下這門簡單的函數式語言吧喵

她的名字叫白雪(しらゆき, Shirayuki), 是我今年三月份時花兩天空閑時間所創造的. 挺喜歡她的, 所以也向大家介紹她.

看先一下她的一個簡單例子吧:

快速排序qsort

// Shirayuki script// By Rika// ==description==// Quick sort algorithm// for example given the input (3,1,2,5,4) and get the output (1,2,3,4,5) // ==description==(lambda:empty_list()={})(lambda:list_element(x)={x})(lambda: if(cond, True, False)= | cond: True | : False)(lambda: qsort(list)= if( list, delay( qsort(filter(lambda:x->x<=list_{1},1-list))+ list_{1}+ qsort(filter(lambda:x->x>list_{1},1-list))), empty_list() ))lambda:f()=qsort(input())

運行一下喵

>>> (3,1,2,5,4)(1,2,3,4,5)

好的喵, 現在正式和大家介紹我家的白雪姬

基礎運算:

(), {} 括弧(引入{}主要用於生成空列表或單個元素列表, 區分()和(1)表達式)_ 列表取元素(標識符中間的下劃線不作為運算符,下標從1開始)! 階乘^ 冪*, / 乘, 除+, - 加, 減=, !=, <, >, <=, >= 等於, 不等於, 小於, 大於, 小於等於, 大於等於

其中的加減符號比較特殊, 在用於列表時表示連接列表或剪除列表

{1}+2={1,2}1+{2}={1,2}{1}+{2,3}={1,2,3}{1,2}-2={1}1-{1,2,3}={2,3}{1,2,3}-{1,2}={1}

特別說明: 減法有個小坑, 減去的數只是一個佔位符, 無具體含義, 如{1,2}-2中減去的2隻是表示減去一個元素, 在{1,2,3}-{1,2}中減去的{1,2}只是表示剪除末尾長度為2的列表, 這麼設計是為了表示的統一性(加減互為逆運算)

數據類型:

None 空類型1 整數3.14 實數(1,2,3) or {1,2,3} 列表[1+2] 表達式

因為白雪的原先設計是作為計算姬, 所以只支持整數, 實數和列表啦喵.

要支持更多的數據結構也是很容易的喵, 甚至還可以加入代數數據結構. 不過我已經差不多懶成一隻廢喵了.

特殊表達式:

lambda為關鍵字, 用於定義函數lambda:x->x 匿名函數, 參數為x, 返回xlambda:x,y->x+y 匿名函數, 參數為x,y, 返回x+ylambda:f(x)=x 命名函數, 參數為x, 返回xlambda:f(x,y)=x+y 命名函數, 參數為x,y, 返回x+y(lambda: if(cond, true, false)= | cond: true | :false)條件表達式, | cond_expr: ret_condcond_expr為條件, ret_cond為條件為真時返回值當值為None, 0, 空列表時條件為假多個條件相接時從前往後取第一個條件為真的表達式, 否則返回None

特別說明: 在函數內部所有的lambda表達式均為匿名函數, 命名函數名稱將被忽略. 另外當然啦函數閉包是少不了的啦喵.

delay關鍵字, 用於懶惰求值(可參考上面例子qsort函數中結合if使用)delay expr or delay(expr)包裝的匿名函數lambda:h(x)=xlambda:g(x)=-xlambda:f()=(h+g)(1) //always return 0

特別說明: 當運算符遇到函數時將會生成一個新的匿名函數喵

lambda:f()=(h+g)(1)//等價於lambda:f()=(lambda:x->h(x)+g(x))(1)

這麼設計是為了貼近數學語言(不過好像並沒有什麼用, 攤手)

其他一些小細節:

一行一個函數表達式, 被括弧包圍的換行將被忽略.

執行的入口點函數默認是f(), 這個嘛可以根據自己的喜好更改啦喵.

還有一些內置函數(主要是數學函數, 因為她是計算姬嘛):

int float len map filter reduce ceil floor abs sin cos tan ln exp pi e input output

特別說明: pi和e這兩個是常值函數返回pi和e, 這麼設計是因為白雪她不喜歡常數只獨愛函數.

input函數用於讀取外部輸入, output當然就是輸出啦.

當然啦, 上面這些內置函數並不是關鍵字, 你可以自己實現並覆蓋. 白雪只有7個關鍵字:

lambda def def! delay callcc eval curry

沒有介紹到的特性請看第4篇關於宏的文章, 裡面介紹了關於宏, 表達式對象, 匹配表達式的語法以及使用.

有了以上這些元素之後就可以拜託白雪做一些簡單的工作啦, 比如做計算姬啦, 排序姬, 統計姬啦什麼的. 當然我們也可以根據自己喜好加入更多元素讓我們的白雪小姐能力更強大更漂亮(笑)

好啦, 最後就是白雪的源碼啦(Python 3.5, 這份實現已經棄用啦. 最新的是JavaScript實現, 在新文章里有, 快去看看吧喵):

白雪她本身也是使用函數式方式編寫, 所以非常嬌小, 不過嘛可讀性就比較差啦. 各位小夥伴如果有興趣可以使用傳統的方式實現一下喵.

import sysimport reimport mathfrom functools import reducesys.setrecursionlimit(8192)def do_raise(msg): raise Exception("Syntax Error, "+msg+".")wapper=lambda _f: (lambda *_x: _f(wapper(_f), *_x))preprocessor_x=wapper( lambda self, __Str, _n=0, _m=0: if not __Str and (_n==0 and _m==0) else do_raise("unmatched parentheses "+(( if _n>0 else ))+"") if not __Str and (_n!=0 or _m!=0) else
+self(__Str[1:], _n) if __Str[0]==
and _n==0 else self(__Str[1:], _n) if __Str[0]==
and _n!=0 else __Str[0]+self(__Str[1:], _n+(__Str[0]==()-(__Str[0]==)), _m+(__Str[0]=={)-(__Str[0]==})) if re.match(r[wd+-*/.()^!<>=:, |{} ], __Str[0]) else do_raise("unexpect symbol "+__Str[0]+""))preprocessor=lambda __Str: preprocessor_x(
.join(filter(None, re.sub(r[ f
v]+, , re.sub(r//.*, , __Str)).split(
))))lexer=(lambda __Str: list(map( (lambda s: None if s==None else int(s) if s.isdigit() else float(s) if re.match(r^(d+?.d*?|d*?.d+?)$, s) else != if s==<> else s if s.find(.)==-1 or s===< or s===> or s==>< else do_raise("unexpect symbol "+s+"")), filter(lambda c: c and c not in { , }, re.split(r(->|[<>=]{2}|!=|_(?=s*{)|[><=+-*/()^!:,
| {} ]), preprocessor(__Str))))))parser_unit=wapper( lambda self, __List, __Level=10: ((lambda _t: [[(),_t[:-1] if len(_t)>=2 and _t[0]!=None else []],_t[-1][1:]] if len(_t)>2 or _t[1][0]==} else [_t[0],_t[1][1:]]) (wapper(lambda self, rf, _t0: (lambda _tx: [_t0[0]]+self(rf, _tx))(rf(_t0[1][1:])) if _t0[1] and _t0[1][0]==, else _t0 )(self, self(__List[1:]))) if __List and (__List[0]==( or __List[0]=={) else [__List[0], __List[1:]] if __List and (not isinstance(__List[0], str) or not re.match(r(->|[<>=]{2}|[><=,+-*/()^!|{}\_:]), __List[0])) else [None, __List]) if __Level==0 else (((lambda _t: (lambda _tf: [_tf[:-1],_tf[-1]]) ([lambda]+(lambda _t0: ((([_t0[0]] if not _t0[0] in {lambda,def,delay} else do_raise("invaild function name "+_t0[0]+"")) if len(_t0)>1 and _t0[1] in {=,(} else [])+ (lambda _tc: [_tc[0]]+ (self(_tc[1][2:]) if _t0[1]==( and _tc and _tc[1][0]==) and (len(_tc[1])>1 and (_tc[1][1] in {=,->})) else do_raise("expect symbol )") if _t0[0]==) and (not _tc[1] or _tc[1][0]!=)) else self(_tc[1][1:]) if _t0[1]!=( and _tc[1] and (_tc[1][0] in {=,->}) else do_raise("expect symbol =")) )((wapper(lambda self, _t1: (lambda _tx: [[_t1[0]]+_tx[0], _tx[1]])(self(_t1[1+(len(_t1)>1 and _t1[1]==,):])) if _t1 and re.match(r^w+$,_t1[0]) else [[],_t1] if not _t1 or _t1[0] in {->,=,)} else do_raise("unexpect symbol "+_t1[0]+"") )(_t0[2*(len(_t0)>1 and _t0[1]==():])) if not(len(_t0)>1 and _t0[1]===) else [[], _t0[1:]])) )(_t[1:])) if _t and _t[0]==: else do_raise("expect symbol :") )(__List[1:])) if __List and __List[0] in {lambda,def} else self(__List, __Level-1)) if __Level==1 else (wapper(lambda self, rf, _t: (lambda _t0: self(rf, [[<-,_t[0],_t0[0]],_t0[1]]))( (lambda _t: [[(),_t[:-1]],_t[-1][1:]]) (wapper(lambda self, rf, _t0: (lambda _tx: [_t0[0]]+self(rf, _tx))(rf(_t0[1][1:])) if _t0[1] and _t0[1][0]==, else _t0 )(rf, rf(_t[1][1:]))) ) if _t[1] and _t[1][0]==( else do_raise("unexpect symbol {") if _t[1] and _t[1][0]=={ else (lambda _t0: self(rf, [[*,_t[0],_t0[0]],_t0[1]]))(rf(_t[1], 4)) if _t[1] and not re.match(r(->|[<>=]{2}|[><=,+-*/()^!|:{}\_
]), str(_t[1][0])) else _t) )(self, self(__List, __Level-1)) if __Level==2 else ((lambda _t: [[delay,_t[0]],_t[1]])(self(__List[1:],__Level-1)) if __List and __List[0]==delay else self(__List, __Level-1)) if __Level==3 else (wapper(lambda self, rf, _t: (lambda _t0: self(rf, [[_t[1][0],_t[0],_t0[0]],_t0[1]])) (rf(_t[1][1:], __Level-1)) if _t[1] and _t[1][0] in [{_},{!},{^},{*,/},{+,-},{=,!=,<,>,<=,>=}][__Level-4] else _t)) (self, self(__List, __Level-1)) if __Level>3 and __Level<10 else ((lambda _t0: [[|,_t0[:-2]],_t0[-1]]) ((wapper(lambda self, rf, _t: (lambda _tx: (lambda _ty: [[_tx[0], _ty[0]]]+self(rf, _ty[1]))(rf(_tx[1][1:])) if _tx[1] and _tx[1][0]==: else do_raise("expect symbol :")) (rf(_t[1:])) if _t and _t[0]==| else [[], _t] ))(self, __List)) if __List and __List[0]==| else self(__List, __Level-1)) if __Level==10 else self(__List, __Level-1))parser=wapper( lambda self, __List: (lambda rf, _t: [_t[0]]+(rf(_t[1][1:]) if _t[1] else []) )(self, parser_unit(__List)))merge_dict=lambda x,y: (lambda a,b: a.update(b) or a)(x.copy(),y)global_symtable=(lambda _t: (lambda _d0, _d: _d0.update({k: val_func(func(v[1:], {}, _d0, evaluate)) for k, v in _d.items()}) or _d0 )((lambda builtin: lambda numeric_func: { int: builtin(numeric_func(lambda x: int(x),int),int,[x]), float: builtin(numeric_func(lambda x: float(x),float),float,[x]), len: builtin(lambda x: len(x) if isinstance(x, list) else do_raise("call lambda <len> with not vector argument"),len,[x]), map: builtin(lambda f,x: list(map(lambda y:f()([y]), x)) if isinstance(x, list) else do_raise("call lambda <map> with not vector argument"),map,[f,x]), filter: builtin(lambda f,x: list(filter(lambda y:f()([y])()(), x)) if isinstance(x, list) else do_raise("call lambda <filter> with not vector argument"),filter,[f,x]), reduce: builtin(lambda f,x: (reduce(lambda a,b:f()([a,b]), x) if x else []) if isinstance(x, list) else do_raise("call lambda <reduce> with not vector argument"),reduce,[f,x]), ceil: builtin(numeric_func(lambda x: math.ceil(x),ceil),ceil,[x]), floor: builtin(numeric_func(lambda x: math.floor(x),floor),floor,[x]), abs: builtin(numeric_func(lambda x: math.fabs(x),abs),abs,[x]), sin: builtin(numeric_func(lambda x: math.sin(x),sin),sin,[x]), cos: builtin(numeric_func(lambda x: math.cos(x),cos),cos,[x]), tan: builtin(numeric_func(lambda x: math.tan(x),tan),tan,[x]), ln: builtin(numeric_func(lambda x: math.log(x),ln),ln,[x]), exp: builtin(numeric_func(lambda x: math.exp(x),exp),exp,[x]), pi: builtin(lambda: math.pi,pi,[]), e: builtin(lambda: math.e,e,[]), input: builtin(lambda: evaluate(parser(lexer(input(>>> )))[0],dict(),dict())()(),input,[]), output: builtin(lambda x: print(result_of(x)) or x,output,[x], False), })(lambda f,name,args,decay=True: val_func(builtin_func(f,name,args,decay))) (lambda f,name: lambda x: f(x) if isinstance(x, int) or isinstance(x, float) else do_raise("call lambda <"+name+"> with not isnumeric argument")), (lambda v: reduce(lambda x,y: merge_dict(x,y),v) if v else {})( map(lambda x: {x[1]:x}, filter(lambda x: (isinstance(x, list) and x[0]==lambda and x[1]), _t)))))environment=(lambda _env, _symtable: (lambda _syb: _env[_syb] if _syb in _env else _symtable[_syb] if _syb in _symtable else do_raise("undefine symbol: "+_syb)))builtin_func=(lambda f, name, args, decay=True: lambda i=0: (lambda _args=[]: (val_func(f(*map(lambda x: x()() if decay else x,_args))) if decay else f(*map(lambda x: x()() if decay else x,_args))) if len(_args)==len(args) else do_raise("call lambda <"+name+"> with unmatched arguments") ) if i==0 else (lambda<+name+(+, .join(args)+)>) if i==1 else (lambda_builtin) if i==2 else None)func=(lambda _body, _env, _gsym, _eval: lambda i=0: (lambda _args=[]: _eval(_body[2], merge_dict(_env, dict(zip(_body[1], _args))), _gsym) if len(_args)==len(_body[1]) else do_raise("call lambda <"+(_body[0] if _body[0] else unnamed)+"> with unmatched arguments") ) if i==0 else (lambda<+(_body[0] if _body[0] else unnamed)+(+, .join(_body[1])+)>) if i==1 else (lambda) if i==2 else None)delay_func=(lambda _body, _env, _gsym, _eval, _value: (lambda i=0: (_value[0](i) if _value else (lambda v: _value.append(v) or v(i))(_eval(_body, _env, _gsym))) if not i==3 else delay_expr))val_func=(lambda _val: lambda i=0: (lambda _args=[]: _val) if i==0 else (_val(1) if callable(_val) else ((+,.join(map(lambda v:v(1),_val))+) if isinstance(_val, list) else str(_val))) if i==1 else (value) if i==2 else None)func_combinator=(lambda x, y, op, op_ch: lambda i=0: (lambda _args=[]: op(x()(_args), y()(_args))) if i==0 else (lambda<+x(1)+ +op_ch+ +y(1)+>) if i==1 else (lambda_combinator) if i==2 else None)op_gen=(lambda op, op_ch, cond=lambda x: callable(x): wapper(lambda self,x,y: val_func((lambda a,b: op(a if a!=None else 0, b if b!=None else 0) if not cond(a) and not cond(b) else func_combinator(a if cond(a) else val_func(x), b if cond(b) else val_func(y), self, op_ch))(x()(), y()()))))op_check=(lambda flambda x,y: f(x,y) if not isinstance(x, list) and not isinstance(y, list) else do_raise("invaild operatation on vector")))op_check_x=(lambda flambda x,y: f(x,(y if not isinstance(y, list) else y[0]()())) if not isinstance(x, list) and (not isinstance(y, list) or (len(y)==1 and not isinstance(y[0]()(), list))) else do_raise("invaild operatation on vector")))combinator=(lambda _sym: { <-:lambda x,y: x()()()((lambda v: v if not (len(v)<=1 and not v[0](3) and v[0]()()==None) else [])(y()())) if callable(x()()) and x()()(2)!=value else do_raise("calling a not callable object "+result_of(x)), <=:op_gen(op_check(lambda a,b: a<=b),<=), >=:op_gen(op_check(lambda a,b: a>=b),>=), <:op_gen(op_check(lambda a,b: a<b),<), >:op_gen(op_check(lambda a,b: a>b),>), !=:op_gen(op_check(lambda a,b: a!=b),!=), =:op_gen(op_check(lambda a,b: a==b),=), +:op_gen(lambda a,b: a+b if not isinstance(a, list) and not isinstance(b, list) else (lambda f: f(a)+f(b))(lambda z: z if isinstance(z, list) else [val_func(z)]),+), -:op_gen((lambda a,b: a-b if not isinstance(a, list) and not isinstance(b, list) else a[:(lambda l: l if l>=0 else 0)(len(a)-(len(b) if isinstance(b, list) else 1))] if isinstance(a, list) else b[(len(a) if isinstance(a, list) else 1):]),-), *:op_gen(op_check(lambda a,b: a*b),*), /:op_gen(op_check(lambda a,b: float(a)/float(b)),/), ^:op_gen(op_check_x(lambda a,b: a**b),^), _:op_gen(lambda a,b: (lambda x,yx[y-1]()() if 0<y and y<=len(x) else None))(a,b[0]()()) if isinstance(a, list) and isinstance(b,list) and len(b)==1 and isinstance(b[0]()(),int) else do_raise("invaild operatation on vector"),_), !:op_gen(op_check(lambda x,y: (wapper(lambda self,x,y: (x*self(x-1, y) if x>y else 1))(x if x>=0 else 0, y if y>=0 else 0) if isinstance(x, int) else do_raise("invaild factorial"))),!), }[_sym])evaluate=wapper( lambda self, _t, _env, _gsym: ((combinator(_t[0])(self(_t[1], _env, _gsym), self(_t[2], _env, _gsym))) if _t and _t[0] in {!=,<=,>=,<,>,=,+,-,*,/,^,!,<-,_} else val_func(list(map(lambda x: self(x, _env, _gsym), _t[1]))) if _t and _t[0]==() else val_func((lambda x: self(x[1], _env, _gsym)()() if x else self(_t[1][-1][1], _env, _gsym)()() if _t[1][-1][0]==None else None) (next(filter(lambda x: self(x[0], _env, _gsym)()(), _t[1]), None))) if _t and _t[0]==| else val_func(func(_t[1:], _env, _gsym, self)) if _t and _t[0]==lambda else delay_func(_t[1], _env, _gsym, self, []) if _t and _t[0]==delay else val_func(None)) if isinstance(_t, list) else (val_func(_t) if isinstance(_t, int) or isinstance(_t, float) else (environment(_env, _gsym)(_t)) if isinstance(_t, str) else val_func(None)))result_of=lambda x: x(1)execute=lambda __Str: lambda f: (lambda t: result_of(t[f]()()()()) if f in t else None)(global_symtable(parser(lexer(__Str))))try: f=open(source.syk) print(execute(f.read())(f)) f.close()except Exception as e: print(str(e))

讀取源碼文件source.syk, 入口點函數為f, 在代碼最後這個可以根據自己喜歡更改啦喵.

全部加起來只有185行, 總共11.6k大小, 使用遞歸下降語法分析, 直接執行語法樹.

大家有興趣可以試試看.

如果大家對具體源碼細節感興趣或者有什麼疑問我下次另外寫一篇文章專門介紹一下吧喵.

另外我還給她寫了sublime text的高亮, 這樣是不是就漂亮很多了呢

希望大家喜歡我家的白雪小姐~

推薦閱讀：