一晚上糊出一個語言「後端」

03-06

前段時間lyzh一直說要做一個程序設計語言，結果做了大半年，重構了四五次，C和C++換來換去，我還是沒有等到一個可以玩的repl。一氣之下，熬了兩個小時寫了一個動態語言的「後端」，包括表達式求值，內建函數，自定義函數和符號表管理。

這門語言的設計跟Scheme差不多，最重要的不同的地方是:

Scheme：只寫(+ 1 2)會對列表求值，(+ 1 2)才是列表

我：(+ 1 2)就是列表，eval (+ 1 2)才對其求值

某種程度上反映了語言設計者的一些奇異癖好

開發使用Python 3.6.2

首先我們需要用到枚舉

from enum import Enum

以及一個用來fuck一切的函數

def zfuck(description) : print("Error: ", description) quit(-1)

我們把一切數值類型、標識符、列表、函數歸納為一個統一的ZObject，它由一個kind標識其類型，由value存儲實際的值。先來定義Object ID：

class ZObjectKind(Enum) : Number = 1 Id = 2 List = 3 Func = 4 Eval = 5

然後是ZObject：

class ZObject : def __init__(self, kind, value) : self.kind = kind self.value = value def isNumber(self) : return self.kind == ZObjectKind.Number def isIdent(self) : return self.kind == ZObjectKind.Id def isList(self) : return self.kind == ZObjectKind.List def isFunc(self) : return self.kind == ZObjectKind.Func def isEval(self) : return self.kind == ZObjectKind.Eval

對於數值、標識符和列表而言，ZObject的value就是一個數值/字元串/由ZObject組成的列表；對eval而言，value就是要求值的object；但是對於函數，它由參數表和函數體兩部分組成，因此我們需要一個額外的class：

class ZFuncImpl : def __init__(self, paramList, funcBody) : self.paramList = paramList self.funcBody = funcBody def isBuiltin(self) : return False

我決定給語言內建的函數開一個洞

class ZBuiltinFuncImpl : def __init__(self, func) : self.func = func def isBuiltin(self) : return True

有了基本的Object，我們還需要一張符號表。因為節guo約yu時lan間duo的原因，我做了一個All-global scoping的符號表，「所有綁定都是全局綁定」，這在之後的更新中會改，不過現在先這樣吧

class ZSymbolTable : def __init__(self) : self.symbols = dict() def set(self, name, theObject) : self.symbols[name] = theObject def query(self, name) : return self.symbols.get(name)globalSymbolTable = ZSymbolTable()

然後我們就可以開始愉快地開始求值了

class ZEvaluator : def __init__(self) : pass def evaluate(self, theObject) : # 如果是數值和列表，原樣返回 if theObject.isNumber() : return theObject elif theObject.isList() : return theObject # 如果是標識符解析其含義 elif theObject.isIdent() : found = globalSymbolTable.query(theObject.value) if found is None : zfuck("undefined reference to " + theObject.value) return found # 如果是eval標記，表明要對表達式求值 elif theObject.isEval() : maybeList = self.evaluate(theObject.value) if not maybeList.isList() : zfuck("evaluaing unknown thing") theList = maybeList.value if len(theList) == 0 : zfuck("evaluating empty list") maybeFunc = self.evaluate(theList[0]) if not maybeFunc.isFunc() : zfuck("not a function apply") funcImpl = maybeFunc.value # 內建函數開洞 if funcImpl.isBuiltin() : return funcImpl.func(theList[1:]) else : return self.simpleCall(funcImpl, theList[1:]) # 簡單調用 def simpleCall(self, funcImpl, argList) : if len(funcImpl.paramList) != len(argList) : zfuck("arguments not appropriate") for i in range(0, len(argList)) : globalSymbolTable.set(funcImpl.paramList[i], self.evaluate(argList[i])) return self.evaluate(funcImpl.funcBody);

最後來兩組測試~

def stdlibAddFunc(argList) : theSum = 0 for arg in argList : evaluatedArg = evaluator.evaluate(arg) if not evaluatedArg.isNumber() : zfuck("not a number") theSum += evaluatedArg.value return ZObject(ZObjectKind.Number, theSum)globalSymbolTable.set("add", ZObject(ZObjectKind.Func, ZBuiltinFuncImpl(stdlibAddFunc)))evaluator = ZEvaluator()test = ZObject(ZObjectKind.Eval, ZObject(ZObjectKind.List, [ZObject(ZObjectKind.Id, "add"), ZObject(ZObjectKind.Number, 3), ZObject(ZObjectKind.Number, 5), ZObject(ZObjectKind.Number, 7)]))print(evaluator.evaluate(test).value)udLazyAdd = ZObject(ZObjectKind.Func, ZFuncImpl(["a", "b"], ZObject(ZObjectKind.List, [ZObject(ZObjectKind.Id, "add"), ZObject(ZObjectKind.Id, "a"), ZObject(ZObjectKind.Id, "b")])))globalSymbolTable.set("lazyadd", udLazyAdd)test2 = ZObject(ZObjectKind.Eval, ZObject(ZObjectKind.Eval, ZObject(ZObjectKind.List, [ZObject(ZObjectKind.Id, "lazyadd"), ZObject(ZObjectKind.Number, 3), ZObject(ZObjectKind.Number, 5)])))print(evaluator.evaluate(test2).value)