宏展開與衛生宏展開

01-26

本文是動手寫一門簡單語言吧喵系列的正篇的第四篇文章, 你問我第二第三去哪裡了呀喵? 被我吃掉啦~好啦, 其實我打算第二篇寫如何在有第一篇文章的四則運算的基礎上加入函數與閉包, 第三篇寫如何繼續添加一些語言的基礎語句, 比如實現條件語句, 實現包裝匿名函數, 實現懶惰求值等等. 但是呢喵, 好像並沒有很多人感興趣, 可能是太簡單了吧, 所以我就坑啦. 以後應該都寫寫比較深入點點的內容, 不知道大家感不感興趣(之後可能會寫類型系統與抽象解釋的相關內容, 企劃中...).

這篇文章同樣需要大家有λ-calculus的相關的簡單基礎知識, 可以參考Wiki Lambda_calculus.

白雪(しらゆき, Shirayuki) 在線解釋器來啦, 歡迎大家來嘗試. (這次更新了柯里化, 宏系統, 表達式對象以及模式匹配功能, 添加了一些內置函數, 並且完全重寫了語法高亮部分, 新的解釋器為了節省空間對JavaScript代碼進行了壓縮, 如果想要源碼的話請告訴我喲)

白雪與宏系統

宏相信大家應該並不陌生, 學過C/C++的朋友應該都很熟悉宏. 宏本質上是編譯期函數, 作用於源碼之上, 以參數和返回值都是源碼. 這次我為白雪添加上了宏系統, 使得白雪也擁有了操縱自身代碼的能力.

白雪的宏系統與C/C++不同, 她更接近Lisp的宏系統. C/C++的宏作用於詞法層面之上進行簡單的詞法替換, 把某個token替換為另一個token或一系列token. 而白雪的宏系統作用於語法層面之上, 將某個表達式替換為另一個表達式.

簡單的介紹一下白雪的宏相關語法.

定義宏:

def:pi=3.14//expansion: pi*2 => 3.14*2def:macro(a)=a//expansion: macro(1+2) => 1+2 (identity)

使用關鍵字def或def!進行宏定義, 語法與定義函數lambda一致, 不過區別是不允許匿名的宏以及在函數和宏內部定義宏. 另外一個小區別是常值宏, 就是上面第一個啦, 沒有參數不加括弧(與定義常量相似), 在調用宏的時候也不需要寫括弧.

宏的參數是源碼中的表達式, 返回值同樣是表達式, 返回的表達式將會被插入在調用宏處.

如果需要對表達式進行操作的話需要使用表達式對象:

[expr]

使用中括弧包圍表達式, 例如

[1+2][lambda:x->x]

表達式轉義操作:

[1+{x}]//x=[2+3]//result: [1+(2+3)]

轉義操作符

{expr} or (expr)

在轉義操作符包圍中的表達式將會被求值, 求得的值將會被放置在轉義符對應的位置上. 應用於表達式對象中的子表達式需要在運行時確定的情況. 轉義操作符{}與()的區別在於是否拆解轉義列表:

[(1,{x})]//x=[(2,3)]//result: [(1,(2,3))][(1,(x))]//x=[(2,3)]//result: [(1,2,3)]

表達式為了宏添加的一種新的類型, 如果需要執行表達式的話使用eval:

//eval expr or eval(expr)eval([1+2])//result: 3eval([lambda:x->x])//result: lambda<unnamed(x)>

表達式對象可以簡單理解為其他語言里的字元串, 不過這裡的表達式對象實際上是Ast, 在生成時會進行語法檢查, 並且可以通過匹配表達式提取子表達式. 下面將會介紹匹配表達式.

如果我們需要對表達式對象進行修改或者添加內容需要使用匹配表達式:

expr_0->(| expr_1: expr_2 | expr_3: expr_4 | ...)

expr_0為被匹配的表達式, expr_1與expr_3等為模式, expr_2與expr_4為匹配成功後的操作, 舉個例子吧:

x->| [{~x}+{~y}]: y | [{~x}]: x//x=[1+2]//match: [{~x}+{~y}]//result: [2]//x=[1]//match: [{~x}]//result: [1]

其中的~操作符聲明了一個自由名稱, 將會在匹配成功後與對應的部分的值綁定, 看看上面的~x與~y的使用相信不會很難理解.

參數模式匹配, 直接把值表達式寫在參數里在函數調用時進行模式匹配. 可以類比Haskell里的模式匹配和C++的模板特化/偏特化.

//fibonacci series(lambda:fib(0)=1)(lambda:fib(1)=1)(lambda:fib(n)=fib(n-1)+fib(n-2))(lambda:f()=fib(10))

匹配表達式不僅僅只用於表達式的操作, 還可以用於對象的等價性判斷, 比如lambda:x->x與lambda:y->y就會匹配成功, 它們不是同一個函數但是它們是等價的(α-conversion), 同樣的可以用來測試列表是否等價(每一個元素等價).

匹配表達式是條件表達式的拓展(對true的匹配, 是否等價於true). 在更新後所有的條件表達式均轉換為匹配表達式執行.

匹配表達式是使用合一演算法(unification algorithm)實現的, 大家如果有興趣的話也可以更多地介紹一下.

有了以上的工具之後宏可以實現很多很操作了, 比如將表達式中的加減操作對調:

(def:reverse(expr)= expr->( | [{~x}+{~y}]: [{reverse(x)}-{reverse(y)}] | [{~x}-{~y}]: [{reverse(x)}+{reverse(y)}] | : expr ))(lambda:f()=reverse(1+2-4))//expansion: [((1-2)+4)]//result: 3

白雪的宏與C/C++的宏不能進行遞歸只能進行詞法替換不同的是, 白雪的宏可以使用語言所有能力對表達式進行操作, 包括內置函數, 嵌套與遞歸等等, 宏函數擁有白雪的所有表達能力. 注意不要把宏寫成不終止的喔.

宏展開與衛生宏展開

重點來啦喵~擁有了宏之後一個最大的問題是名稱干擾, 傳統的宏是不衛生的, 意思是宏會污染命名空間, 舉例來說:

第一: 如果一個不衛生的宏進行展開:

(def:M(x)= [lambda:x->{x}+x])(lambda:h(x)=M(x)(1))(lambda:f()=h(2))//expansion: [(lambda:x->(x+x))]//result: 2

很明顯地可以發現, 宏引入的新的名稱x覆蓋了h函數中的參數x, 導致返回結果為2. 而我們對宏的預期應該是

//expansion: [(lambda:x_0->(x+x_0))]//result: 3

第二: 同樣地, 展開環境當中的名稱同樣會覆蓋宏之中的自由變數, 污染命名空間, 例如:

(def:M(x)= [len({x})])(lambda:h(l,len)=M(l))(lambda:f()=h((1,2),lambda:x->len(x)+1))//result: 3

h函數展開後是:

(lambda:h(l,len)=len(l))

此時內置函數len被參數len覆蓋, 因此返回的是len(l)+1=3. 而我們對宏的預期應該是len為內置函數.

這個時候我們需要衛生宏(Hygienic macro), 將名稱分隔開不互相干擾. (相信熟悉Lisp的朋友對衛生宏一定不陌生)

衛生宏的實現為KFFD演算法與詞法閉包. 同樣的, 為了簡潔說明宏展開的原理, 這裡採用的是最簡單的λ-calculus.

表達式的構成如下

$e:=x;|;m;|;lambda x.e|;ee^{$

$m:=m^{$

$m$ 為宏函數表達式, $macro$ 為宏集合

$macro:={syntax ightarrow syntax}$

$(m=syntax ightarrow syntax)in macro$

簡單的宏展開(不衛生)語義為:

$[[;e;]];:;(syntax ightarrow macro) ightarrow syntax$

$[[;x;]];=;lambda kappa .x$

$[[;m;]];=;lambda kappa .[[;kappa m;]]kappa$

$[[;lambda x.M;]];=;lambda kappa.lambda x.[[M]]kappa$

$[[;MN;]];=;lambda kappa.([[M]]kappa)([[N]]kappa)$

可以發現在進行每一步宏展開 $kappa m$ 時引入的新的名稱可能會造成命名空間污染, 解決辦法並不複雜, 記錄下每一個名稱被引入的階段, 顯然不同階段引入的相同名應稱互不相同, 那麼只需要找到不同階段引入的相同名稱並進行重命名即可.

舉例來說:

$m_{1}=lambda e. (lambda x.(m_{2}e)(x))$

$m_{2}=lambda e. lambda x_0. (lambda x.(ex_0)(x))$

$m_1 f$ 的宏展開為:

$lambda x. (lambda x. (fx)x)$

記錄與標識出(上標)每個名稱引入的階段:

$lambda x^1. (lambda x^2. (f^0x^1)x^2)$

0為原始參數中的名稱, 1為宏 $m_1$ 引入的名稱, 2為宏 $m_2$ 引入的名稱. 根據引入階段標識進行重命名:

$lambda x_1. (lambda x_2. (fx_1)x_2)$

原始參數中的名稱保持不變, 不同階段引入的相同名稱進行重命名, 這樣就不會發生命名污染了.

因此可以寫出衛生宏展開語義:

$[[;e;]]_{hyg};:;(syntax ightarrow macro) ightarrow syntax$

$[[;e;]]_{hyg};=;lambda kappa .mathcal{U}(mathcal{A}(E(mathcal{T}(e,l_0),kappa,l_1)))$

$label:={l_n;|;nin mathbb{N}}$

$mathcal{T}:(syntax ightarrow label) ightarrow syntax$

$mathcal{T}: x,l_n ightarrow x^{n}$

$mathcal{T}: x^{n},l_m ightarrow x^{n}$

$mathcal{T}: m,l_m ightarrow m$

$mathcal{T}: (lambda x.M),l_n ightarrow lambda x^n.mathcal{T}(M,l_n)$

$mathcal{T}: (MN),l_n ightarrow (mathcal{T}(M,l_n)mathcal{T}(N,l_n))$

$mathcal{E}:(syntax ightarrow macro ightarrow label) ightarrow syntax$

$mathcal{E}: x^n,kappa,l_m ightarrow x^n$

$mathcal{E}: m,kappa,l_n ightarrow mathcal{E}(mathcal{T}(kappa m,l_n),kappa,l_{n+1})$

$mathcal{E}: (lambda x^n.M),kappa,l_n ightarrow lambda x^n.mathcal{E}(M,kappa,l_n)$

$mathcal{E}: (MN),kappa,l_n ightarrow (mathcal{E}(M,kappa,l_n)mathcal{E}(N,kappa,l_n))$

$mathcal{A}:syntax ightarrow syntax$

$mathcal{A}: x^n ightarrow x^n$

$mathcal{A}: (lambda x^0.M) ightarrow lambda x^0.mathcal{A}(M)$

$mathcal{A}: (lambda x^n.M) ightarrow lambda v.mathcal{A}([v/x^n]M)$ $(where v is a new name, [v/x]M:replace all name x by v in expression M)$

$mathcal{A}: (MN) ightarrow (mathcal{A}(M)mathcal{A}(N))$

$mathcal{U}:syntax ightarrow syntax$

$mathcal{U}: x ightarrow x$

$mathcal{U}: x^n ightarrow x$

$mathcal{U}: (lambda x^n.M) ightarrow lambda x.mathcal{U}(M)$

$mathcal{U}: (lambda x.M) ightarrow lambda x.mathcal{U}(M)$

$mathcal{U}: (MN) ightarrow (mathcal{U}(M)mathcal{U}(N))$

衛生宏展開中分為4個階段, $mathcal{T}, mathcal{E}, mathcal{A}, mathcal{U}$ . 以上面 $m_1 f$ 的宏展開為例

第一步 $mathcal{T}$ , $mathcal{T}$ 負責對名稱進行標註, 將原始表達式參數標上標識0: $f^0$

第二步 $mathcal{E}$ , $mathcal{E}$ 進行遞歸宏展開, 每進行一次遞歸標識號加1.

0). $m_1 f^0quad(label:l_0)$

1). $lambda x^1. ((M_2 f^0)x^1)quad(label:l_1)$

2). $lambda x^1. (lambda x^2. (f^0x^1)x^2)quad(label:l_2)$

第三步 $mathcal{A}$ , $mathcal{A}$ 對宏引入的名稱進行重命名: $lambda x_1. (lambda x_2. (f^0x_1)x_2)$

第四步 $mathcal{U}$ , $mathcal{U}$ 對剩餘的自由名稱去除標識符: $lambda x_1. (lambda x_2. (fx_1)x_2)$

在進行衛生宏展開之後所有由宏引入的綁定名稱不會造成命名污染了, 解決了第一個問題.

對於第二個問題, 展開環境中的名稱污染了宏中的自由名稱.

這個問題比較好解決, 只需要引入詞法閉包將宏中的所有自由名稱綁定在宏函數的命名空間就行(綁定名稱不受干擾), 具體實現便是在第一步 $mathcal{T}$ 中為不僅添加標識同時為名稱添加上其所對應的宏的命名空間引用, 並在最後一步 $mathcal{U}$ 中將所有標識大於1的名稱綁定在對應的命名空間里(所有綁定名稱在第三步 $mathcal{A}$ 中被移除了標識, 剩下的便是自由名稱). 實現不會很複雜, 大致如下:

$mathcal{T}: x,l_n, env ightarrow x^{n}:env$

$mathcal{E}: m,kappa,l_n ightarrow mathcal{E}(mathcal{T}(kappa m,l_n,env_{kappa}),kappa,l_{n+1})$

$mathcal{U}: x^n:env ightarrow x:envquad(n>0)$

上面提到白雪中的宏使用關鍵字def與def!, 那麼很明顯啦喵, def是衛生宏def!是普通宏.

在擁有了強大宏系統之後呢, 可以使用宏實現很多很有趣的東西, 比如之前的CPS變換與CPS變換編譯就可以使用白雪的宏來完成, 而且還可以使用宏實現callcc, 是不是很有趣呢.

CPS與callcc實現代碼如下(實現原理可以看上面那篇文章喔, 這裡只實現了函數表達式和函數調用, 其它更多語句如大家有興趣可以試試自己實現一下):

(def:CPS_impl(e,k)= e->( | [lambda:{~n}((~x))->{~M}]: ( k([ (lambda:{n}((x))-> lambda:k->({ CPS_impl(M,lambda:m->[k({m})]) }) ) ]) ) | [{~M}({~N})]: ( CPS_impl(M, (lambda:m-> CPS_impl(N, (lambda:n-> [{m}({n})(lambda:a->{k([a])})] )) )) ) | [callcc {~M}]: ( (lambda:c->[{CPS_impl(M, (lambda:m-> [{m}(lambda:v->lambda:k0->{c})(lambda:v->{c})])) }])(k([v])) ) | [{~x}]: k(x) ))(def:CPS(e)= CPS_impl(e,lambda:x->x))

或者直接使用參數模式匹配寫成更簡略的形式:

(def:CPS_impl([lambda:{~n}((~x))->{~M}],k)= k([ (lambda:{n}((x))-> lambda:k->({ CPS_impl(M,lambda:m->[k({m})]) }) ) ]))(def:CPS_impl([{~M}({~N})],k)= CPS_impl(M, (lambda:m-> CPS_impl(N, (lambda:n-> [{m}({n})(lambda:a->{k([a])})] )) )))(def:CPS_impl([callcc {~M}],k)= (lambda:c->[{CPS_impl(M, (lambda:m-> [{m}(lambda:v->lambda:k0->{c})(lambda:v->{c})])) }])(k([v])))(def:CPS_impl([{~x}],k)= k(x))(def:CPS(e)= CPS_impl(e,lambda:x->x))

對(lambda:x->x)(x)進行CPS變換:

//expansion:>>> [ ((lambda:x-> (lambda:k->k(x)) )(x))(lambda:a->a)]

使用宏實現callcc:

(def:CALL_CPS(e)= [{e}(lambda:x->x)])CPS(lambda:g(x)=x(2))CPS(lambda:k(x)=(lambda:x->output(1))(g(x)))CPS(lambda:h()=callcc(k))(lambda:f()=CALL_CPS(h()))

//expansion:>>> [ (lambda:h()= (lambda:k-> (k(lambda:v-> (lambda:k0->k(v)) ))(lambda:v->k(v)) ) )]>>> [ (lambda:k(x)= (lambda:k-> (g(x))( (lambda:a-> ((lambda:x-> (lambda:k-> (output(1))(lambda:a->k(a)) ) )(a))(lambda:a->k(a)) ) ) ) )]>>> [ (lambda:g(x)= (lambda:k-> (x(2))(lambda:a->k(a)) ) )]//result: 2

注意在g中調用了continuation函數之後直接返回了h而沒有返回到k執行output(1), 輸出1. 因此結果是2.

文章比較長, 謝謝大家的耐心閱讀喵~

如果還有有什麼感興趣的或者有什麼問題歡迎留言~