《Understanding Computation: From Simple Machines to Impossible Programs》(計(jì)算的本質(zhì)) 是一本由淺入深逐步講解計(jì)算機(jī)程序的一本書。書中的代碼例子使用 Ruby 描述，因此也有人稱之為 Ruby版本的SCIP。

書中的第二章探討了程序的含義。通過自定義語言規(guī)則，構(gòu)建抽象語法樹展示了編程語言和程序的基本意義。本文即對該內(nèi)容的學(xué)習(xí)而做的學(xué)習(xí)筆記。

因原文代碼是Ruby，Ruby我不是很熟。就使用了熟悉的 Python3， Golang 和 Rust分別實(shí)現(xiàn)了三種版本。

三個(gè)版本的Git源碼倉庫

原書由了小步語義(small step semantic)開始，介紹什么是小步語義，并且設(shè)計(jì)一個(gè)虛擬機(jī)進(jìn)行規(guī)約求值。然后再介紹大步語義(big step sanmactic)，最后再介紹指稱語義(denatation)。三者逐步遞進(jìn)，易于理解。然而本文是對三個(gè)整體概念的筆記，會(huì)從最后宏觀的角度解釋理論和代碼。

語義

語言學(xué)中，語義研究的是單詞和他們之間的關(guān)系。單詞和單詞組成短語和句子。計(jì)算機(jī)的編程語言也有很多種，計(jì)算機(jī)可選重視的是形式語義學(xué)，后者從定義新的語言和進(jìn)化編譯優(yōu)化具體應(yīng)用，到構(gòu)造程序正確性的數(shù)學(xué)證明領(lǐng)域都應(yīng)用廣泛。

計(jì)算機(jī)里的語義值的是程序的含義。通過程序語義的語法描述程序是怎么樣的?，F(xiàn)實(shí)中描述變成語言有兩種。第一種就是官方規(guī)范（C++，Java），即委員會(huì)制定的各種語言規(guī)范，另外一種就是具體實(shí)現(xiàn)（Python，Ruby），如 CPython或Ruby的解釋器實(shí)現(xiàn)。

不管是哪種，程序員使用的編程語言都有一套語法約束，然后通過編譯器或解釋器將語法規(guī)則轉(zhuǎn)換成預(yù)發(fā)解析器，或是構(gòu)建抽象語法樹。最后是進(jìn)行表達(dá)式求值。

我們關(guān)注的是如何定義一種語法規(guī)則，然后構(gòu)建抽象語法樹，進(jìn)而對這個(gè)樹求值以得到結(jié)果。

小步語義

我們可以設(shè)計(jì)一種機(jī)器，用這個(gè)機(jī)器按照某個(gè)語法規(guī)則進(jìn)行一小步一小步的反復(fù)規(guī)約，從而進(jìn)行求值。例如下面表達(dá)式

1 + 3 — 2 

可以從左到右依次求值

1 + 3 - 2
4 - 2
2

通常這種語法規(guī)則可以用數(shù)學(xué)化公式描述。但是作為開發(fā)者，我們理解其中含義更好的方式是通過代碼。

假設(shè)我們需要設(shè)計(jì)一個(gè)叫Simple的編程語言。先通過小步語義規(guī)約進(jìn)行實(shí)現(xiàn)。首先我們的編程語言關(guān)注有三個(gè)要素：

• 環(huán)境(env)：程序運(yùn)行的環(huán)境，類型是Python的字典Dict，其環(huán)境存儲(chǔ)了值
• 表達(dá)式(expr)：運(yùn)算表達(dá)式或操作表達(dá)式
• 語句(stmt)：表達(dá)式構(gòu)成的語句，程序體的構(gòu)成。

設(shè)計(jì)一個(gè)表達(dá)類

class BaseMixin:

    @property
    def value(self) -> Any:
        if hasattr(self, "val"):
            return self.val
        raise AttributeError

    @property
    def reducible(self) -> bool:
        return False


class VarExprMixin(BaseMixin):

    @property
    def reducible(self) -> bool:
        return False



class ExprMixin(BaseMixin):

    @property
    def reducible(self) -> bool:
        return True

    def reduce(self, env: Dict) -> ExprMixin:
        raise NotImplementedError

    def evaluate(self, env: Dict) -> ExprMixin:
        raise NotImplementedError

    @property
    def to_python(self) -> str:
        raise NotImplementedError

ExprMixin是表達(dá)式類，即定義表達(dá)式行為的接口，其中有個(gè)四個(gè)方法或?qū)傩裕?/p>

• reducibel： 表示該表達(dá)式是否可以規(guī)約，像Number，Boolean 這樣的值類型不能規(guī)約了。
• reduce：表達(dá)式的規(guī)范方法，即表達(dá)式求值的邏輯，規(guī)約的方法返回還是表達(dá)式 ExprMixin
• evaluate：大步語義中表達(dá)式求值的方法，求值返回的也是表達(dá)式 ExprMixin
• to_python: 指稱語義中表達(dá)式轉(zhuǎn)換成python語義的方法，返回的是 python 代碼字串

當(dāng)前小步語義中，我們主要關(guān)注 reducible 和 reduce方法。下面實(shí)現(xiàn)兩個(gè)基本的值類型

值表達(dá)式 Number & Boolean

值表達(dá)式只有一個(gè)值。無操作符和運(yùn)算符

class Number(VarExprMixin, ExprMixin):
    def __init__(self, val: int):
        self.val = val

    def __repr__(self):
        return f"{self.val}"

class Boolean(VarExprMixin, ExprMixin):
    def __init__(self, val: bool):
        self.val = val

    def __repr__(self):
        return f"{self.val}"

    def __eq__(self, other):
        return self.val == other.val

Number 和 Boolean分表表示數(shù)字和布爾值。它們都不能規(guī)約了。在命令行中可以看到

>>> expr = Number(val=1)
>>> expr
1
>>> Boolean(True)
True
>>>

二元表達(dá)式 Add & Mul & LessThan

二元表達(dá)式有兩個(gè)操作數(shù)，左值和右值。如運(yùn)算表達(dá)式（1 + 2）和比較表達(dá)式 （3 < 2），布爾表達(dá)式（true ** 1 + 2）

class Add(ExprMixin):

    def __init__(self, left: ExprMixin, right: ExprMixin):
        self.left = left
        self.right = right

    def __repr__(self):
        return f"{self.left} + {self.right}"

    def reduce(self, env: Dict) -> ExprMixin:
        if self.left.reducible:
            return Add(self.left.reduce(env), self.right)
        elif self.right.reducible:
            return Add(self.left, self.right.reduce(env))
        else:
            return Number(self.left.value + self.right.value)

class Mul(ExprMixin):

    def __init__(self, left: ExprMixin, right: ExprMixin):
        self.left = left
        self.right = right

    def __repr__(self):
        return f"{self.left} * {self.right}"

    def reduce(self, env: Dict) -> ExprMixin:
        if self.left.reducible:
            return Mul(self.left.reduce(env), self.right)
        elif self.right.reducible:
            return Mul(self.left, self.right.reduce(env))
        else:
            return Number(self.left.value * self.right.value)


class LessThan(ExprMixin):

    def __init__(self, left: ExprMixin, right: ExprMixin):
        self.left = left
        self.right = right

    def __repr__(self):
        return f"{self.left} < {self.right}"

    def reduce(self, env: Dict) -> ExprMixin:
        if self.left.reducible:
            return LessThan(self.left.reduce(env), self.right)
        elif self.right.reducible:
            return LessThan(self.left, self.right.reduce(env))
        else:
            return Boolean(self.left.value < self.right.value)

從上面的代碼可以看到，對于運(yùn)算表達(dá)式，都有左值(left)和右值(right)。其規(guī)約方法如下：

1. left 可以規(guī)約，則對left進(jìn)行規(guī)約，并返回一個(gè)新的表達(dá)式
2. right 可以規(guī)約，則再對right進(jìn)行規(guī)約，同樣返回一個(gè)新的表達(dá)式
3. left和right都無法規(guī)約，則證明表達(dá)式為 Number或Boolean類型，依次返回對應(yīng)類型即可

注意，上面的規(guī)約方法忽略了運(yùn)算的優(yōu)先級，優(yōu)先級會(huì)影響學(xué)習(xí)小步語義，可以暫時(shí)忽略。

下面驗(yàn)證一下上面的代碼：

Add 表達(dá)式

>>> expr = Add(Number(1), Number(2))
>>> expr
1 + 2
>>> expr.reducible           # Add 表達(dá)式可以規(guī)約
True
>>> expr = expr.reduce({})   # 規(guī)約返回新的表達(dá)式
>>> expr
3
>>> expr.reducible           # left 和 right 無法規(guī)約，上一步返回的是 Number 表達(dá)式
False

Mul 表達(dá)式

>>> expr = Add(
...     left=Mul(Number(1), Number(2)),
...     right=Mul(Number(3), Number(4))
... )
>>> expr
1 * 2 + 3 * 4
>>> expr.reducible
True
>>> expr = expr.reduce({})   # Add 的left 規(guī)約 left 1 + 2 規(guī)約為  3
>>> expr
2 + 3 * 4
>>> expr.reducible
True
>>> expr = expr.reduce({})   # Add 的 right 規(guī)約 right 3 * 4 規(guī)約為 12
>>> expr
2 + 12
>>> expr.reducible
True
>>> expr = expr.reduce({})   # 最后規(guī)約 Add 本身
>>> expr
14
>>> expr.reducible
False

LessThan 表達(dá)式

>>> expr = LessThan(Number(1), Number(2))
>>> expr
1 < 2
>>> expr.reducible
True
>>> expr = expr.reduce({})
>>> expr
True
>>> expr.reducible
False

Add， Mul， LessThan的特點(diǎn)都是二元表達(dá)式。類似的 減法 Sub，除法 Div，邏輯與或 And，Or可以參考github的repo。

變量 Variable

變量是編程語言的重要元素。定義變量的值是表達(dá)式，變量存儲(chǔ)在環(huán)境中。上面的值表達(dá)式和運(yùn)行表達(dá)式都沒有使用環(huán)境，變量需要讀寫環(huán)境。

Variable

class Variable(ExprMixin):

    def __init__(self, name: str):
        self.name = name

    def __repr__(self):
        return f"{self.name}"

    def reduce(self, env: Dict) -> ExprMixin:
        return env[self.name]

變量的規(guī)約方法即返回環(huán)境中的表達(dá)式。

>>> env = {"x": Number(1)}  # 初始化環(huán)境 
>>> env
{'x': 1}
>>> expr = Variable("x")
>>> expr
x
>>> expr.reducible
True
>>> expr = expr.reduce(env)
>>> expr
1
>>> isinstance(expr, Number)
True

語句

ExprMixin 是表達(dá)式接口定義。此外，三個(gè)要素中還有語句。語句與表達(dá)式有點(diǎn)區(qū)別，語句的規(guī)約返回的是語句和環(huán)境。

語句接口

class StmtMixin:

    @property
    def reducible(self) -> bool:
        return True

    def reduce(self, env: Dict) -> (StmtMixin, Dict):
        raise NotImplementedError

    def evaluate(self, env: Dict) -> Dict:
        raise NotImplementedError

    @property
    def to_python(self) -> str:
        raise NotImplementedError

與表達(dá)式接口 ExprMixin 類似，語句接口 StmtMixin 也有四個(gè)方法。其中 reduce 和 表達(dá)式不一樣，它返回的語句本身，同時(shí)還返回了一個(gè)環(huán)境。因?yàn)檎Z句在規(guī)約的時(shí)候，會(huì)對表達(dá)式求值，并且將求值結(jié)果更新到環(huán)境中。

空語句

class DoNothing(VarExprMixin, StmtMixin):

    def __repr__(self):
        return "do-nothing"

    def __eq__(self, other):
        return isinstance(other, DoNothing)

DoNohing 語句表示空語句，它與 Number，Boolean一樣，不能再規(guī)約，表示語句規(guī)約的終點(diǎn)。但是它本身是一個(gè)語句，而不是表達(dá)式。

Assign 賦值語句

對于開發(fā)者而言，賦值語句最平常了。通常是 變量 = 值(表達(dá)式) 的形式。下面是其實(shí)現(xiàn)

class Assign(StmtMixin):

    def __init__(self, name: str, expr: ExprMixin):
        self.name = name
        self.expr = expr

    def __repr__(self):
        return f"{self.name} = {self.expr}"

    def reduce(self, env: Dict) -> (StmtMixin, Dict):
        if self.expr.reducible:
            return Assign(self.name, self.expr.reduce(env)), env
        env[self.name] = self.expr
        return DoNothing(), env

Assign 實(shí)現(xiàn)了 StmtMixin 接口， 它的規(guī)約方法很簡單：

1. 右值表達(dá)式如果可以規(guī)約，則進(jìn)行規(guī)約，返回新的賦值表達(dá)式
2. 右值不能規(guī)約，把當(dāng)前的 name 更新到環(huán)境中，返回 DoNothing 語句，表示規(guī)約完畢

測試：

>>> env = {"x": Number(2)}   # 初始化環(huán)境
>>> env
{'x': 2}
>>> stmt = Assign("x", Add(Variable("x"), Number(1)))  # 賦值語句
>>> stmt
x = x + 1
>>> stmt.reducible
True
>>> stmt, env = stmt.reduce(env)     # 規(guī)約，即右值表達(dá)式進(jìn)行規(guī)約 第一步是變量進(jìn)行規(guī)約
>>> stmt
x = 2 + 1
>>> env
{'x': 2}
>>> stmt.reducible
True
>>> stmt, env = stmt.reduce(env)     # 第二步是 Add 表達(dá)式規(guī)約
>>> stmt
x = 3
>>> env
{'x': 2}
>>> stmt.reducible
True
>>> stmt, env = stmt.reduce(env)    # 最后是賦值語句本身規(guī)約 
>>> stmt
do-nothing
>>> env                             # 賦值表達(dá)式會(huì)更新環(huán)境
{'x': 3}
>>> stmt.reducible
False

虛擬機(jī)

從上面的賦值語句的規(guī)約可以看到，語句的規(guī)約是反復(fù)的調(diào)用自身的reduce方法。同時(shí)將結(jié)果輸出到環(huán)境中。因此可以設(shè)計(jì)一個(gè)虛擬機(jī)，用于一步一步執(zhí)行規(guī)約。這也是本節(jié)titile的含義，小步語義。

class Machine:
    def __init__(self, stmt: StmtMixin, env: Dict):
        self.stmt = stmt
        self.env = env

    def step(self):
        self.stmt, self.env = self.stmt.reduce(self.env)   # 規(guī)約

    def run(self, debug=True):
        while self.stmt.reducible:                         # 在循環(huán)中小步規(guī)約
            print(self.stmt, self.env)
            self.step()
        print(self.stmt, self.env)

有了虛擬機(jī)，賦值語句的小步規(guī)約就簡單了

>>> stmt = Assign("x", Add(Variable("x"), Number(1)))
>>> stmt
x = x + 1
>>> env = {"x": Number(2)}
>>> env
{'x': 2}
>>> machine = Machine(stmt, env)
>>> machine.run()
x = x + 1 {'x': 2}
x = 2 + 1 {'x': 2}
x = 3 {'x': 2}
do-nothing {'x': 3}
>>> machine.stmt
do-nothing
>>> machine.env
{'x': 3}

If 條件語句

下一步是實(shí)現(xiàn) If 條件語句。if 語句有三個(gè)部分，條件 cond 表達(dá)式，if主體 consequence 語句，和 else 主體 alternative 語句。

class If(StmtMixin):

    def __init__(self, cond: ExprMixin, consequence: StmtMixin, alternative: StmtMixin):
        self.cond = cond
        self.consequence = consequence
        self.alternative = alternative

    def __repr__(self):
        return f"if ({self.cond}) {{{self.consequence}}} else {{{self.alternative}}}"

    def reduce(self, env: Dict) -> (StmtMixin, Dict):
        if self.cond.reducible:
            return If(self.cond.reduce(env), self.consequence, self.alternative), env
        else:
            if self.cond == Boolean(True):
                return self.consequence, env
            else:  # self.cond == Boolean(False)
                return self.alternative, env

規(guī)約的方法比較中規(guī)中矩：

1. cond 表達(dá)式可以規(guī)約，則對其規(guī)約，并返回新的 if 表達(dá)式和環(huán)境。
2. cond表達(dá)式不能規(guī)約，即為 Boolean值的時(shí)候，如果為真，則返回 consequence 語句和環(huán)境，否則返回 alternative 語句。注意 if 的主體是語句。

>>> stmt = If(
...     cond=Variable("x"),
...     consequence=Assign("y", Number(1)),
...     alternative=Assign("y", Number(2)),
... )
>>> stmt
if (x) {y = 1} else {y = 2}
>>> env = {"x": Boolean(True)}
>>> env
{'x': True}
>>> machine = Machine(stmt, env)
>>> machine.run()
if (x) {y = 1} else {y = 2} {'x': True}
if (True) {y = 1} else {y = 2} {'x': True}
y = 1 {'x': True}
do-nothing {'x': True, 'y': 1}
>>> env
{'x': True, 'y': 1}

if 語句最終規(guī)約返回的 stmt也是 donothing，因此如果只是 if 語句而忽略 else，那么 else 可以直接初始化為 DoNothing 語句。

Sequence 序列組合語句

從 If 語句可以看出，它必然返回 consequence 或者 alternative。這兩者都是語句，通常程序不會(huì)只有一句話。因此下面實(shí)現(xiàn)的是序列組合語句

class Sequence(StmtMixin):
    def __init__(self, first: StmtMixin, second: StmtMixin):
        self.first = first
        self.second = second

    def __repr__(self):
        return f"{self.first};{self.second}"

    def reduce(self, env: Dict) -> (StmtMixin, Dict):
        if self.first.reducible:
            reduced_first, reduced_env = self.first.reduce(env)
            return Sequence(reduced_first, self.second), reduced_env
        else:
            return self.second.reduce(env)

Sequence有兩部分，其規(guī)約如下：

1. first 可以規(guī)約，則對其進(jìn)行規(guī)約，并返回新的 Sequence 語句
2. first 不能規(guī)約（donothing），則 scond 進(jìn)行規(guī)約

>>> stmt = Sequence(
...     first=Assign("x", Add(Number(1), Number(1))),
...     second=Assign("y", Add(Variable("x"), Number(1))),
... )
>>> stmt
x = 1 + 1;y = x + 1
>>> env = {}
>>> machine = Machine(stmt, env)
>>> machine.run()
x = 1 + 1;y = x + 1 {}
x = 2;y = x + 1 {}
do-nothing;y = x + 1 {'x': 2}
y = 2 + 1 {'x': 2}
y = 3 {'x': 2}
do-nothing {'x': 2, 'y': 3}
>>> env
{'x': 2, 'y': 3}

second初始化的時(shí)候是可以規(guī)約，當(dāng)他不能規(guī)約的時(shí)候，會(huì)不滿足 machine而直接終止。并且若有 3或3+的語句，也用擔(dān)心，可以一次規(guī)約，這將在 while 循環(huán)語句中體現(xiàn)。

While 循環(huán)語句

class While(StmtMixin):

    def __init__(self, cond: ExprMixin, body: StmtMixin):
        self.cond = cond
        self.body = body

    def __repr__(self):
        return f"while ({self.cond}) {{{self.body}}}"

    def reduce(self, env: Dict) -> (StmtMixin, Dict):
        return If(self.cond, Sequence(self.body, self), DoNothing()), env

循環(huán)語句的規(guī)約使用了點(diǎn)小技巧

1. 可以把循環(huán)看成是 If 語句中 else 為 DoNothing 進(jìn)行規(guī)約
2. 當(dāng)執(zhí)行 If 語句的 consequence的時(shí)候，使用 Sequence語句將 body 和 while 進(jìn)行組合，這樣執(zhí)行完 body（first）之后，Sequence語句將將執(zhí)行 second，即 下一次 while

>>> env = {"x": Number(1)}
>>> env
>>> stmt = While(
            cond=LessThan(Variable("x"), Number(5)),
            body=Assign("x", Mul(Variable("x"), Number(3)))
... )
>>> stmt
while (x < 5) {x = x * 3}
>>> machine = Machine(stmt, env)
>>> machine.run()
while (x < 5) {x = x * 3} {'x': 1}
if (x < 5) {x = x * 3;while (x < 5) {x = x * 3}} else {do-nothing} {'x': 1}
if (1 < 5) {x = x * 3;while (x < 5) {x = x * 3}} else {do-nothing} {'x': 1}
if (True) {x = x * 3;while (x < 5) {x = x * 3}} else {do-nothing} {'x': 1}
x = x * 3;while (x < 5) {x = x * 3} {'x': 1}
x = 1 * 3;while (x < 5) {x = x * 3} {'x': 1}
x = 3;while (x < 5) {x = x * 3} {'x': 1}
do-nothing;while (x < 5) {x = x * 3} {'x': 3}
if (x < 5) {x = x * 3;while (x < 5) {x = x * 3}} else {do-nothing} {'x': 3}
if (3 < 5) {x = x * 3;while (x < 5) {x = x * 3}} else {do-nothing} {'x': 3}
if (True) {x = x * 3;while (x < 5) {x = x * 3}} else {do-nothing} {'x': 3}
x = x * 3;while (x < 5) {x = x * 3} {'x': 3}
x = 3 * 3;while (x < 5) {x = x * 3} {'x': 3}
x = 9;while (x < 5) {x = x * 3} {'x': 3}
do-nothing;while (x < 5) {x = x * 3} {'x': 9}
if (x < 5) {x = x * 3;while (x < 5) {x = x * 3}} else {do-nothing} {'x': 9}
if (9 < 5) {x = x * 3;while (x < 5) {x = x * 3}} else {do-nothing} {'x': 9}
if (False) {x = x * 3;while (x < 5) {x = x * 3}} else {do-nothing} {'x': 9}
do-nothing {'x': 9}
>>> env
{'x': 9}

應(yīng)用

通過上面介紹的值表達(dá)式和語句表達(dá)式。Simple語義實(shí)現(xiàn)了編程語言的基本骨架。下面就使用 Simple 計(jì)算一個(gè)問題。

高斯問題： 從 1 到 100個(gè)數(shù)進(jìn)行加和。我們可以使用 while 循環(huán)從 1-100 進(jìn)行求值。

>>> env = {
...     "sum": Number(100),
...     "i": Number(1),
...     "n": Number(101),
... }
>>> env
{'sum': 100, 'i': 1, 'n': 101}
>>> stmt.evaluate(env)
>>> stmt = While(
...     cond= LessThan(
...         left=Variable("i"),
...         right=Variable("n"),
...     ),
...     body=Sequence(
...         first=Assign("sum", Add(Variable("sum"), Variable("i"))),
...         second=Assign("i", Add(Variable("i"), Number(1))),
...     )
... )
>>> stmt
while (i < n) {sum = sum + i;i = i + 1}
>>> machine = Machine(stmt, env)
>>> machine.run()
...   # ?省略輸出
 
>>> machine.env
{'sum': 5050, 'i': 101, 'n': 101}

大步語義

值表達(dá)式

小步語義展示了如何對抽象的語法樹進(jìn)行一步一步的規(guī)約，從而最終對整個(gè)表達(dá)式或語句求值。自底向上，這是一個(gè)迭代的過程。

大步語義則是自動(dòng)向下，使用遞歸的方式進(jìn)行表達(dá)式或語句求值。表達(dá)式（ExprMixin）的大步語義求值返回一個(gè)新的表達(dá)式。語句(StmtMixin)求值返回一個(gè)新的環(huán)境，畢竟語句會(huì)更新環(huán)境。

前文介紹了表達(dá)式和語句的代碼，大步語義不需要 reducible屬性和 reduce方法，只需要實(shí)現(xiàn) evaluate 方法即可。下面是其代碼，省略了 小步語義相關(guān)的代碼

class Number(VarExprMixin, ExprMixin):
    def __init__(self, val: int):
        self.val = val

    def evaluate(self, env: Dict) -> ExprMixin:
        return self

class Boolean(VarExprMixin, ExprMixin):
    def __init__(self, val: bool):
        self.val = val

    def evaluate(self, env: Dict) -> ExprMixin:
        return self

class Add(ExprMixin):

    def __init__(self, left: ExprMixin, right: ExprMixin):
        self.left = left
        self.right = right

   
    def evaluate(self, env: Dict) -> ExprMixin:
        return Number(self.left.evaluate(env).value + self.right.evaluate(env).value)


class Mul(ExprMixin):

    def __init__(self, left: ExprMixin, right: ExprMixin):
        self.left = left
        self.right = right

    def evaluate(self, env: Dict) -> ExprMixin:
        return Number(self.left.evaluate(env).value * self.right.evaluate(env).value)

class LessThan(ExprMixin):

    def __init__(self, left: ExprMixin, right: ExprMixin):
        self.left = left
        self.right = right

    def evaluate(self, env: Dict) -> ExprMixin:
        return Boolean(self.left.evaluate(env).value < self.right.evaluate(env).value)


class Variable(ExprMixin):

    def __init__(self, name: str):
        self.name = name

    def evaluate(self, env: Dict) -> ExprMixin:
        return env[self.name]

上述的表達(dá)式都實(shí)現(xiàn)了 evaluate 方法。其中值表達(dá)式的 evaluate 返回值本身。二元表達(dá)式依次是對其左右值 進(jìn)行求值。小步語義需要通過虛擬機(jī)迭代依次規(guī)約求值。大步語義則不需要了。

值表達(dá)式

>>> expr = Number(1)
>>> expr
1
>>> expr.evaluate({})
1
>>> expr = Boolean(False)
>>> expr
False
>>> expr.evaluate({})
False

二元表達(dá)式

>>> expr = Add(
...     Mul(Number(1), Number(2)),
...     Mul(Number(3), Number(4)),
... )
>>> expr
1 * 2 + 3 * 4
>>> expr.evaluate({})
14
>>> expr = LessThan(Variable("x"), Number(1))
>>> expr
x < 1
>>> expr.evaluate({"x": Number(2)})
False

語句

語句的實(shí)現(xiàn)的是 StmtMixin接口的evaluate 方法。該方法不會(huì)返回表達(dá)式，而是返回一個(gè)環(huán)境。下面的代碼同樣省略了小步語義的規(guī)約方法。

class DoNothing(VarExprMixin, StmtMixin):

    def evaluate(self, env: Dict) -> Dict:
        return env


class Assign(StmtMixin):

    def __init__(self, name: str, expr: ExprMixin):
        self.name = name
        self.expr = expr

    def evaluate(self, env: Dict) -> Dict:
        return env | {self.name: self.expr.evaluate(env)}


class If(StmtMixin):

    def __init__(self, cond: ExprMixin, consequence: StmtMixin, alternative: StmtMixin):
        self.cond = cond
        self.consequence = consequence
        self.alternative = alternative

    def evaluate(self, env: Dict) -> Dict:
        cond = self.cond.evaluate(env)
        if cond == Boolean(True):
            return self.consequence.evaluate(env)
        else:  # cond == Boolean(False)
            return self.alternative.evaluate(env)

class Sequence(StmtMixin):
    def __init__(self, first: StmtMixin, second: StmtMixin):
        self.first = first
        self.second = second

    def evaluate(self, env: Dict) -> Dict:
        return self.second.evaluate(self.first.evaluate(env))

class While(StmtMixin):

    def __init__(self, cond: ExprMixin, body: StmtMixin):
        self.cond = cond
        self.body = body

    def evaluate(self, env: Dict) -> Dict:
        cond = self.cond.evaluate(env)
        if cond == Boolean(True):
            return self.evaluate(self.body.evaluate(env)) # 遞歸調(diào)用
        else:  # cond == Boolean(False)
            return env

assign 賦值語句

>>> stmt = Assign("x", Add(Variable("x"), Number(1)))
>>> stmt
x = x + 1
>>> stmt.evaluate({"x": Number(2)})
{'x': 3}

if 條件語句

>>> stmt = If(
    cond=Variable("x"),
    consequence=Assign("y", Number(1)),
    alternative=Assign("y", Number(2)),
... )
>>> stmt
if (x) {y = 1} else {y = 2}
>>> stmt.evaluate({"x": Boolean(True)})
{'x': True, 'y': 1}

序列組合語句

>>> stmt = Sequence(
...     first=Assign("x", Add(Number(1), Number(1))),
...     second=Assign("y", Add(Variable("x"), Number(1))),
... )
>>> stmt
x = 1 + 1;y = x + 1
>>> stmt.evaluate({})
{'x': 2, 'y': 3}

while 循環(huán)語句

>>> stmt = While(
        cond=LessThan(Variable("x"), Number(5)),
        body=Assign("x", Mul(Variable("x"), Number(3)))
... )
>>> stmt
while (x < 5) {x = x * 3}
>>> stmt.evaluate({"x": Number(1)})
{'x': 9}

最后依然是使用大步語義進(jìn)行高斯問題求解

>>> env = {
...     "sum": Number(100),
...     "i": Number(1),
...     "n": Number(101),
... }
>>> env
{'sum': 100, 'i': 1, 'n': 101}
>>> stmt.evaluate(env)
>>> stmt = While(
...     cond= LessThan(
...         left=Variable("i"),
...         right=Variable("n"),
...     ),
...     body=Sequence(
...         first=Assign("sum", Add(Variable("sum"), Variable("i"))),
...         second=Assign("i", Add(Variable("i"), Number(1))),
...     )
... )
>>> stmt.evaluate(env)
{'sum': 5150, 'i': 101, 'n': 101}

指稱語義

指稱語義確實(shí)是一種比操作語義更抽象的方法，因?yàn)樗皇怯靡环N語言替換另一種語言，而不是把一種語言轉(zhuǎn)換成真實(shí)的行為。指稱語義通常用來把程序轉(zhuǎn)成數(shù)學(xué)化的對象，所以不出意料，可以用數(shù)學(xué)工具研究和控制它們

原書使用 ruby 構(gòu)建的Simple語言，然后通過指稱語義轉(zhuǎn)換成 ruby代碼執(zhí)行。這里我們就轉(zhuǎn)換成 Python代碼執(zhí)行。即 ExprMixin 和 StmtMixin 里聲明的 to_python屬性方法。

類似的Golang和Rust版本也實(shí)現(xiàn)了 to_python 方法。具體可以參考github版本。下面的代碼演示，省略了 小步語義 和 大步語義 的代碼。

class Number(VarExprMixin, ExprMixin):
    def __init__(self, val: int):
        self.val = val

    @property
    def to_python(self) -> str:
        return f"lambda e: {self.val}"


class Boolean(VarExprMixin, ExprMixin):
    def __init__(self, val: bool):
        self.val = val

    @property
    def to_python(self) -> str:
        return f"lambda e: {self.val}"


class Add(ExprMixin):

    def __init__(self, left: ExprMixin, right: ExprMixin):
        self.left = left
        self.right = right

    @property
    def to_python(self) -> str:
        return f"lambda e: ({self.left.to_python})(e) + ({self.right.to_python})(e)"


class Sub(ExprMixin):

    def __init__(self, left: ExprMixin, right: ExprMixin):
        self.left = left
        self.right = right

    @property
    def to_python(self) -> str:
        return f"lambda e: ({self.left.to_python})(e) - ({self.right.to_python})(e)"


class Mul(ExprMixin):

    def __init__(self, left: ExprMixin, right: ExprMixin):
        self.left = left
        self.right = right

    @property
    def to_python(self) -> str:
        return f"lambda e: ({self.left.to_python})(e) * ({self.right.to_python})(e)"


class LessThan(ExprMixin):

    def __init__(self, left: ExprMixin, right: ExprMixin):
        self.left = left
        self.right = right

    @property
    def to_python(self) -> str:
        return f"lambda e: ({self.left.to_python})(e) < ({self.right.to_python})(e)"


class Variable(ExprMixin):

    def __init__(self, name: str):
        self.name = name

    @property
    def to_python(self) -> str:
        return f"lambda e: e['{self.name}']"



class DoNothing(VarExprMixin, StmtMixin):

    @property
    def to_python(self) -> str:
        return f"lambda e: e"


class Assign(StmtMixin):

    def __init__(self, name: str, expr: ExprMixin):
        self.name = name
        self.expr = expr

    @property
    def to_python(self) -> str:
        return f'lambda e: e | {{"{self.name}": ({self.expr.to_python})(e)}}'


class If(StmtMixin):

    def __init__(self, cond: ExprMixin, consequence: StmtMixin, alternative: StmtMixin):
        self.cond = cond
        self.consequence = consequence
        self.alternative = alternative

    @property
    def to_python(self) -> str:
        return f"lambda e: ({self.consequence.to_python})(e) if ({self.cond.to_python})(e) else ({self.alternative.to_python})(e)"


class Sequence(StmtMixin):
    def __init__(self, first: StmtMixin, second: StmtMixin):
        self.first = first
        self.second = second

    @property
    def to_python(self):
        return f"lambda e: ({self.second.to_python})(({self.first.to_python})(e))"


class While(StmtMixin):

    def __init__(self, cond: ExprMixin, body: StmtMixin):
        self.cond = cond
        self.body = body

    @property
    def to_python(self) -> str:
        return f"(lambda f: (lambda x: x(x))(lambda x: f(lambda *args: x(x)(*args))))(lambda wh: lambda e: e if ({self.cond.to_python})(e) is False else wh(({self.body.to_python})(e)))"

to_python 將 Simple 構(gòu)建的抽象表達(dá)式，轉(zhuǎn)換成 Python的 lambda 字串，通過 eval 可以轉(zhuǎn)換成 python 代碼。進(jìn)而執(zhí)行。相當(dāng)于將 Simple 解釋編譯成 Python代碼。對于 Golang和 Rust 版本也類似。

從代碼也可以看出，to_python 代碼邏輯與 evaluate 類似，都是自頂向下對局部表達(dá)式求值。

其中 python的 lambda 表達(dá)式不支持 while 語句，因此需要借助 Y-combinator 方式實(shí)現(xiàn)。由于python沒有實(shí)現(xiàn)尾遞歸優(yōu)化，如果Simple 表達(dá)式過于復(fù)雜，那么可能會(huì)觸發(fā)python的最大遞歸深度。

下面使用指稱語義解決高斯問題，更多的例子可以參考代碼庫的測試文件。

>>> stmt = While(
...     cond= LessThan(
...         left=Variable("i"),
...         right=Variable("n"),
...     ),
...     body=Sequence(
...         first=Assign("sum", Add(Variable("sum"), Variable("i"))),
...         second=Assign("i", Add(Variable("i"), Number(1))),
...     )
... )
>>> stmt
while (i < n) {sum = sum + i;i = i + 1}
>>> code = stmt.to_python
>>> code
'(lambda f: (lambda x: x(x))(lambda x: f(lambda *args: x(x)(*args))))(lambda wh: lambda e: e if (lambda e: (lambda e: e[\'i\'])(e) < (lambda e: e[\'n\'])(e))(e) is False else wh((lambda e: (lambda e: e | {"i": (lambda e: (lambda e: e[\'i\'])(e) + (lambda e: 1)(e))(e)})((lambda e: e | {"sum": (lambda e: (lambda e: e[\'sum\'])(e) + (lambda e: e[\'i\'])(e))(e)})(e)))(e)))'
>>> fn = eval(code)
>>> fn
<function <lambda>.<locals>.<lambda> at 0x10a7739d0>
>>> fn({'sum': 100, 'i': 1, 'n': 101})
{'sum': 5150, 'i': 101, 'n': 101}

語法解析

我們實(shí)現(xiàn)的 Simple 語義是一種抽象語法表達(dá)式。實(shí)際開發(fā)者更習(xí)慣書寫字面語句 x = x + 1 而不是 Assign(Variable("x"), Add(Variable("x"), Number(1))) 。我們可以實(shí)現(xiàn)一個(gè)規(guī)則，然后使用程序，將 x = x + 1 轉(zhuǎn)換成 Assign(Variable("x"), Add(Variable("x"), Number(1))) 。

python 生態(tài)的 lark 可以實(shí)現(xiàn)這一點(diǎn)。具體的代碼文件可以參考parse

下面使用parse 解析字面語句，生成 simple 表達(dá)式，進(jìn)而求解高斯問題

>>> source = """
        sum = 0
        i = 1
        n = 101
        while (i < n){
            sum = sum + i
            i = i + 1
        }
    """
>>> simple = parse(source)
>>> simple 
sum = 0;i = 1;n = 101;while (i < n) {sum = sum + i;i = i + 1}
>>> fn = eval(simple.to_python)({})
{'sum': 5050, 'i': 101, 'n': 101}

通過書寫直觀的字面量表達(dá)式，通過 parse 解析成 Simple 語言的抽象語法樹。再通過小步語義，大步語義或者指稱語義進(jìn)行求值。

總結(jié)

通過設(shè)計(jì)一個(gè) Simple 編程語言，對其抽象表達(dá)式進(jìn)行操作語義或指稱語義求值。從而計(jì)算程序的結(jié)果。其中抽象表達(dá)式解析有小步語義，大步語義和指稱語義。理解這些語義，就能更好的理解程序和計(jì)算機(jī)的含義。

• 編程語言通過一個(gè)規(guī)范或者實(shí)現(xiàn)定義一些規(guī)則。程序就是使用其規(guī)則表達(dá)式或語句求值。
• 小步語義：自底向上，通過迭代的方式，一步步對規(guī)則進(jìn)行規(guī)約
• 大步語義：自頂向下，通過遞歸方式直接對表達(dá)式求值
• 指稱語義：轉(zhuǎn)換成別的語義的一種方式。

求值規(guī)則：

• 值表達(dá)式：返回其自身
• 二元表達(dá)式：左值先求值，然后右值求值
• 變量：從環(huán)境中返回變量名match的表達(dá)式*
• Assign 賦值語句：對右值表達(dá)式求值，再把結(jié)果更新到環(huán)境中
• If 條件語句：對條件cond表達(dá)式求值，其結(jié)果為true則對 consequence 求值，否則對 alternative 求值，返回環(huán)境
• Sequence 序列語句：一次對序列first和second語句求值，返回環(huán)境
• While 循環(huán)語句：先對條件cond求值，如果返回true則對 body 語句進(jìn)行遞歸求值，返回環(huán)境

版本說明：

• Python 版本基于Mixin的繼承方式實(shí)現(xiàn)
• Golang 版本基于interface的組合方式實(shí)現(xiàn)
• Rust 充分利用 Enum 類型和 Trait 系統(tǒng)實(shí)現(xiàn)