S-expression, macro and develop

要引出我們的主題，得從怎樣才算是 Lisp 開始，各家有各家的說法，因此有了 *Lisp 九宮格*的梗圖。首先我們從 Clojure 開始談起。

Clojure 的語法相較於傳統的 Lisp 更加的依賴 parser，下面我們舉三個例子，Racket 作為對照組。

其實事情很簡單，Clojure 的作者並不明白 S-expression 的好處，沒有善用 S-expression 卻又抄了一部分 Lisp。S-expression 要嘛你就全都用，每個語義分隔都用 S-expression 完成；要嘛就有足夠好的 parsing 並報錯的能力。Clojure 缺乏後半部分，所以即使以下程式碼寫得出來（善用 S-expression 的 let form），還是會栽在報錯能力不夠好的問題上。

(defmacro let
  [bindings & body]
  (doseq [bind bindings]
    (assert (= (-> bind count) 2) "invalid binding"))
  `((fn ~@(map first bindings)
      body)
    ~@(map second bindings)))

要進一步探討，就要問下面的問題。

什麼是 macro？不同的語言給出了不同的解答。

對 C 語言來說，macro 就只是文字替換的機制。前面我們費心討論的問題到這裡根本沒有意義，反正 C macro 只能保障寫得出來，不保障產出的程式正確。

對 C++ 的 Template 來說，macro 就是 meta substitution。跟 C 的文字替換其實沒有太大分別，不過有一些小技巧可以提供還可以的錯誤報告。

到了 Clojure 這個程度，我們認為 macro 其實就是 compile-time function。錯誤報告的能力也有了，因此也是 syntax validator，但缺乏定位錯誤的能力（C++ 反而有相應功能）。

Racket 模型中語言是由多個 phase 組成的，phase 0 就是 runtime，phase 1, 2, 3… 都是 compile-time，數字越大越先執行。因此所謂的 macro 不過就是前一個 phase 裡的 function。

Lisp 的 f-expr 後來有個 formal 改進版本，叫做 vau operator，這個 operator 定義出來的東西跟 \(\lambda\) 很像，只是多一個參數拿環境。換句話說這樣的語言有 first-class environment。

到此我們知道 macro 有多種樣態，但萬變不離核心：製造「新」語法甚至「新」語義。

前面說了這麼多，那 Racket/Scheme 又擁有怎樣的能力呢？1975 年最早的 syntax-rules 其實只有完成新語法的能力，並不能做更多事情。

(define-syntax let
  (syntax-rules ()
    [(_ ([var rhs] ...) body)
     ((λ (var ...) body)
      rhs ...)]))

到了 1988 年，=syntax-case= 引入了驗證語法的概念。

(define-syntax (let stx)
  (syntax-case stx ()
    [(_ ([var rhs] ...) body)
     (not (check-duplicate-identifier (syntax->list #'(var ...))))
     #'((λ (var ...) body)
        rhs ...)]))

我們可以用 raise-syntax-error 稍加改進

(define-syntax (let stx)
  (syntax-case stx ()
    [(_ ([var rhs] ...) body)
     (begin
       (for ([var (syntax->list #'(var ...))])
         (unless (identifier? var)
           (raise-syntax-error 'not-identifier "expected identifier" stx var)))
       (let ([dup (check-duplicate-identifier (syntax->list #'(var ...)))])
         (when dup
           (raise-syntax-error 'dup "duplicate variable name" stx))))
     #'((λ (var ...) body)
        rhs ...)]))

但這樣實在太麻煩也太醜了，所以 1993 年加入了 =syntax-parse=。

(define-syntax (let stx)
  (syntax-parse stx
    [(_ ([var:id rhs:expr] ...) body:expr)
     (check-duplicate-identifier (syntax->list #'(var ...)))
     #'((λ (var ...) body)
        rhs ...)]))

其中 var:id 會自動檢查 var 是不是 identifer?=，也就不需要像 =syntax-case 那樣大費周章只是為了驗證語法的類型。=id= 是 =syntax-class=，我們其實可以自己定義。

(define-syntax (let stx)
  (define-syntax-class binding
    #:description "binding pair"
    (pattern [var:id rhs:expr]))
  (define-syntax-class distinct-bindings
    #:description "sequence of binding pairs"
    (pattern (b*:binding ...)
             #:fail-when (check-duplicate-identifier (syntax->list #'(b*.var ...))) "duplicate variable name"
             #:with (var ...) #'(b*.var ...)
             #:with (rhs ...) #'(b*.rhs ...)))
  (syntax-parse stx
    [(_ d:distinct-bindings body:expr)
     #'((λ (d.var ...) body)
        d.rhs ...)]))

syntax-parse 這個名字其實已經說明了很多：這是一個完整的 parsing 工具。它甚至有 error selection 機制。

正如前一節所述，Racket macro 並不是突然就這麼厲害的，其中經過多年中許多人的改進才成為今天的樣貌。其中最重要的要屬 1986 年的 Hygienic Expansion，這是第一個解決 macro 展開後與目標環境變數衝突的機制。

但 1986 年的 Hygienic Expansion 有一些問題，這時的 Hygienic 是靠簡單的 renaming 實現的。

1. 不善應付遞迴定義的環境，假設 macro 引用到自己，正確實作的難度就很高，展開的 macro 也很笨重又難以反追蹤原本的程式
2. 面對 hygiene bending(e.g. datum->syntax) 沒有效率又很難實作

直到 2016 年的 Binding as Sets of Scopes 才提出了新的模型：Scope sets。

其模型概念非常簡單：

• 為綁定處如 let=、=lambda 等 scope 生成新標籤，這些標籤必須獨一無二
• 內層擁有外層的標籤（lambda 捨棄上層標籤除外）。把當前層所有標籤連結到參考
• 參考往外尋找綁定處參考，擁有最大子集的綁定就是當前應該參照到的定義
• syntax 擁有的是一個標籤函數，端看展開位置(eval)決定函數要帶入什麼

(let ([x 1])  ; x{let1}
  (lambda (x) ; x{lambda1}
    x))       ; x{let1, lamdba1}

上面列出了各個 identifier 的 scope sets 做為參考。希望有助於理解 scope sets 的概念。

到此，我們可以總結：macro 就是 compiler。而目前 macro 目前在開發上還有很多的問題。因為僅是創造出新語法是不夠的，新語法還必須是容易開發的。這本來是顯而易見的，在 compiler 上人人如此追求，等到了 macro 這邊，大家卻又忘了這麼一回事。寫不出好的 compiler 就寫不出好的 macro，而僅僅是白費力氣。

macro 總得來說最差勁的地方就是重構與 code navigation。沒有人知道怎麼重構一個新的語法，也不知道怎麼提示使用者補全它。也沒辦法跳到用 macro 定義的定義處。其中一個可行的方向是讓 macro 的作者提供相關的資訊，也是我接下來的計畫之一。racket 在這方面只能算是解決了一半，macro 作者可以利用 compile to define 或是提供 missing reference 提供跳到定義的功能，但補全還是空白一片。

然而還有更難解的問題，racket 的 first-class class 就是典型的例子。在保持 class 跟 racket 本身可以同時使用的前提下，寫不出可以不污染環境又可以跳到 method 定義的 class。因為 new 擦掉了 phase 1 的資訊，然而以 phase 0 帶資訊給 send 沒辦法提供 class information（被擦掉了）。這種困境顯然不只會出現在 class，而是任何具備擦除的 form，然而我們又不總是可以去修改 base language。

希望讀者有更了解 macro，並且明白什麼時候該用，什麼時候不該。做出明智的判斷是每個開發者每天都會面對的挑戰 XD。