scheme 衛生巨集實現介紹
2018-10-22
本文面向的閱讀物件是使用過 scheme 的衛生巨集,希望瞭解它是如何實現的,或者在實現自己的 lisp 語言的一類人。 另一個基礎要求是,至少知道動態作用域和靜態作用域。
巨集的分類
scheme 語言裡面,巨集是一個很讓人誤解的話題,它使用是 syntax-rules。其實 syntax-rules 是混雜了兩個概念,所以使它的理解變得複雜。應該拆成兩個維度來理解。一個維度是衛生/非衛生。另一個維度是過程巨集/高階巨集。
先說過程巨集和高階巨集維度。一些其它的 lisp 或者 common lisp 裡面,有 defmacro,這是很直觀的,巨集就類似於一個普通函式,它的是輸入引數的 sexp,然後輸出也是 sexp。這個巨集函式裡面具體實現瞭如何變換的過程,所以是過程巨集。 在 scheme 的 syntax-rules 裡面,它是使用了模式匹配的方式,來描述如何將一個 sexp 變換成另一個 sexp。這就是高階巨集,或者說模式匹配巨集。
再來說衛生巨集。衛生或者不衛生,跟高階巨集過程巨集其實是不相關的概念。如果用兩個維度來分類,那麼 syntax-rules 是高階巨集,是衛生巨集。而一些 lisp 的 defmacro 是非衛生巨集,是過程巨集。 還有另外一些系統,是衛生的,卻是過程巨集。
defmacro過程巨集不衛生 syntax-rules高階巨集衛生 syntatic-closure過程巨集可實現衛生 explicit-renaming過程巨集可實現衛生 syntax-case 可過程或高階可實現衛生
什麼是衛生
衛生或者不衛生的本質問題,還是作用域問題,理解這個了,對於衛生巨集就理解了。
讓我們先看,defmacro 存在什麼問題呢?
(defmacro (swap! A B) (let ((tmp ,A)) (set! ,A ,B) (set! ,B tmp))) (swap! tmp x)
展開之後,變成了
(let ((tmp tmp)) (set! tmp x) (set! x tmp))
這裡是一個變數重名問題,巨集裡面引入的 tmp,跟巨集呼叫的引數 tmp 相互衝突了。有經驗的 lisp 程式員會說,應該使用(gemsym tmp)
,然而,這並不是衛生的。也並不能解決更多問題。
假設使用者這麼玩,定義巨集 test:
(define x 'hello) (defmacro (test) '(print x))
呼叫巨集展開
(let ((x 'world)) (test****
得到的結果是 hello 還是 world 呢?這個點就能體現衛生巨集和非衛生巨集的本質區別了。一個符號 x,它在巨集定義的位置是代表的什麼含義,以及它在巨集展開的位置代表的是什麼含義。非衛生巨集是做 sexp 的無腦替換。衛生巨集是需要理解語義的 。
這個問題非常類似於靜態作用域和動態作用域的問題。函式定義:
(define x 3) (define (f) x)
函式呼叫:
(let ((x 5)) (f))
在函式定義的作用域裡面,x 的值是 3。在函式呼叫的時候,作用域裡面有一個變數 x 對應的值是 5。如果一門語言採用動態作用域,呼叫 f 返回值將會是 5,因為動態作用域用函式使用時的上下文決定一個變數的值。在靜態作用域裡面,f 返回值是 3。
這裡要強調的一個概念是“引用透明性”。靜態作用域好處就在於,不管 f 在哪裡被呼叫(引用),它的結果都是確定的,因此不會有意想不到的 bug。 前面說了,衛生或者不衛生的本質問題,還是作用域問題。巨集要處理一系列符號,巨集又有巨集定義階段和巨集展開階段,衛生問題說白了就是哪些符號是對應在巨集定義階段,哪些符號是對應在巨集展開階段。如果巨集是衛生的,它就具有“引用透明性”,定義階段就確切知道每個符號的意義,不會出現意外的繫結。
歷史演算法
歷史上比較有影響力的幾個演算法,下面是一個簡單的時間線。
- 1986: Kohlbecker - introduced the idea of hygiene, low-level, used an O(n^2) coloring algorithm
- 1987: Kohlbecker - introduced declare-syntax, high-level, the precursor to syntax-rules
- 1988: Bawden & Rees - "Syntactic closures," low-level, faster than Kohlbecker's algorithm
- 1991: Clinger & Rees - Explicit renaming, low-level, based on syntactic-closures but also supports syntax-rules
- 1992: Dybvig - Syntax-case, primary motivation to remove the distinction between low-level and high-level
一個一個解釋。第一個,KFFD,Kohlbecker 在 86 年的一篇 paper 裡面首次提出了巨集的衛生的概念。四位作者的首字元縮寫出來,就是 KFFD。具體實現方式跳過了,這個演算法低效,並且現今已經沒有人在用了。
第二個,syntax-rules。作者還是 Kohlbecker,在 87 年的一篇 paper 裡面,提出了用模式匹配的方式來宣告巨集的 idea。這就是 syntax-rules 的前身了。
第三個,syntax closure。開始重點介紹。既然我們知道了衛生巨集的本質問題,符號到底對應巨集定義時期的環境,還是巨集展開時期的環境,我們可以新增兩個引數:
(define-syntax foo (lambda (form usage-environment macro-environment) ...))
在 macro 裡面顯示的指定,每個符號是對應定義時期,還是展開時期,這樣就不會出現誤解了。再可以簡化一下,把巨集定義期環境作為預設值,就可以去掉macro-environment
引數,於是得到sc-macro-transformer
:
(define-syntax swap! (sc-macro-transformer (lambda (form env) (let ((a (make-syntactic-closure env '() (cadr form))) (b (make-syntactic-closure env '() (caddr form)))) `(let ((value ,a)) (set! ,a ,b) (set! ,b value))))))
這裡面的 let value set! 等等都是在巨集的定義期環境裡面的符號,因此不會跟執行期環境裡面的符號衝突。而 a 和 b 這兩個符號,則是 swap! 巨集裡面指定了使用巨集展開時期的環境。
第四個,通過 explicit renaming,來決定衛生問題。er-macro-transformer
跟sc-macro-transformer
在使用方面看起來只是一個提供的是環境,另一個提供的是函式,由 rename 函式決定了使用巨集定義時的環境。
(define-syntax swap! (er-macro-transformer (lambda (form rename compare) (let ((a (cadr form)) (b (caddr form))) `(,(rename 'let) ((,(rename 'value) ,a)) (,(rename 'set!) ,a ,b) (,(rename 'set!) ,b ,(rename 'value)))))))
syntatic closure 和 explicit renaming,符合那些 defmacro 的人的使用習慣,如果把rename
當成gensym
來用,但它是可以實現成衛生的。背後的演算法還是區分了巨集定義環境和巨集展開環境,不是簡單的重新命名。
第五個要說的,是 syntax-case。syntax-case 是在 r6rs 以及 chez-scheme 裡面實現的,作者也正是 chez 編譯器的作者 Dybvig。syntax-case 非常強大,既可以支援高階巨集,也可以支援過程巨集,並且可以處理衛生和不衛生。 但是強大的代價是這個巨集系統非常複雜,理解,使用和實現上面都是。
最後最後提一下,當前最先進的(截止2018年)應該是 racket 和 gerbil 的巨集系統。使用的實現的是用的ofollow,noindex" target="_blank">Scope Set 。這個 matthew flatt 在 2012 年就出 paper 了。 在 racket 裡面,引入了語法物件 syntax。為 syntax 綁定了 scope,多了一層抽象來處理巨集。 這不只是記法問題。本來有 symbol。決定 symbol 要區分是 variable 或是 identifier 又需要 quote。我覺得有越搞越複雜的傾向。有點脫離了 sexp 這些簡單的初衷。
由這些個演算法的發展歷史小結一下,這個問題在研究上基本已經到頭了。目前並沒有什麼既簡單,又強大的方案出來。syntax-case 很強大但複雜。我覺得如果是自己實現,可能 syntatic closure 或者 explicit renaming 會好一點 。
更多思考
巨集的展開次序問題
巨集展開是一個遞迴展開的過程,那麼展開的順序是一個需要考慮的問題。這在語言標準裡面是沒定義的。另外,如果巨集帶副作用的,整個結果就不確定了。導致巨集不是一個可組合的東西。
編譯期展開和執行期展開
完全展開和非完成展開,直譯器可以實現成執行期展開,每遇到巨集就進行展開了再解釋。編譯器必須要求巨集是編譯期完成展開的。需要一個 expander 遞迴的處理巨集展開的過程,直到這個過程結束。注意,過程巨集是可以在展開時期做計算的,整個巨集展開過程就不保證收斂了。
巨集展開過程中引入的作用域
巨集呼叫巨集,展開的過程中,會引入新的巨集展開作用域,也是衛生需要考慮到的。
過程巨集的問題,為什麼r7rs r5rs 標準裡面都是用的 syntax-rule
過程巨集很難標準化。主要是它把編譯器和執行期的耦合弄得不確定了。前面說過,衛生的巨集展開,是要考慮語義的。而考慮語義的東西,有些在執行期才能決定。
(let ((x 3)) (macro-test (if x > 5))
比如過程巨集根據某條件做展開,條件要在執行期計算才確定。巨集展開期間它前不知道一些執行期的條件,這就無法完全編譯期展開了。 syntax-rule 的一個好處,它可以避免過程巨集的這種問題,寫出來的巨集是可以完全展開的。
跟模組,separate compilation 的關係
巨集跟模組有莫大的關聯性,racket 強大在 module,這也是為什麼它需要採用複雜的 macro 系統來支援 module 的實現。
巨集可以在展開時計算一些東西,計算依賴的函式本來是執行期的,被依賴到了編譯器。
有了 module 和 separate compilation 之後,其個巨集要引入其它模組函式,而在使用這個模組的巨集,另外模組還沒有編譯,這裡面的依賴就會有些難搞。
參考資料
macro systems and chicken 評論區 groovy2shoes 的回覆 Implementing Lexically Scoped Macros Binding as Sets of Scopes