從 frontend(compiler) 到 nanopass

8.6

從 frontend(compiler) 到 nanopass

採用 nanopass 內建的 parser 最大的問題就是只能處理內建的 s-expression（用 quote 包住的那些表達式），然而這樣一來就失去了在錯誤發生時回報精確位置的能力，是我們不樂見的情況。為了解決這個問題，我們需要手寫把 frontend 的節點翻譯到 nanopass 的 language 部分。首先我們定義一個簡單的 language。

(require nanopass/base)

(define (unparse-id x)
  (syntax->datum x))

(define-language L0
  (terminals
   (syntax (stx))
   ((identifier (name param)) . => . unparse-id)
   ((stx-number (num)) . => . syntax-e))
  (Expr (expr)
        num
        name
        ; let binding
        (let stx name expr) => (let name expr)
        ; abstraction
        (λ stx (param* ...) expr) => (λ (param* ...) expr)
        ; application
        (stx expr expr* ...) => (expr expr* ...)))

stx-number 顯然是個新酷玩意兒，沒錯，它的定義是：

(define (stx-number? stx)
  (if (syntax? stx)
      (number? (syntax-e stx))
      #f))

因為我們需要儲存任意表達式的位置，最簡單的方式就是儲存原始的 syntax 物件，我們在每一層物件裡面都確保了它儲存了最上層的原始物件。stx-number? 跟 identifier? 都首先是一個 syntax?，然後才檢查其內容，因此一定有做到儲存原始最上層物件的結果。至於 let、abstraction、application 都自行持有 stx 欄位來達成這點。然而如果每次我們都列印原始的物件，這一定很煩人，所以用 => 簡化輸出結果(可以看到這對 terminals 一樣適用)。

現在我們可以專注在最後的核心：parse，這個 pass 把原始 syntax 物件轉換成 nanopass 的結構以利於後續採用 nanopass 的方式開發。

(require syntax/parse)

(define-pass parse : * (stx) -> L0 ()
  (Expr : * (stx) -> Expr (expr)
        (syntax-parse stx
          #:literals (let λ)
          ; let form
          [(let name:id expr)
           `(let ,stx ,#'name ,(parse #'expr))]
          ; lambda form
          [(λ (param*:id ...) expr)
           `(λ ,stx (,(syntax->list #'(param* ...)) ...) ,(parse #'expr))]
          [(f arg* ...)
           `(,stx ,(parse #'f) ,(map parse (syntax->list #'(arg* ...))) ...)]
          ; literal expression
          [x #:when (ormap (λ (pred?) (pred? stx)) (list identifier? stx-number?))
             #'x]
          [else (error 'syntax "unknown form: ~a" stx)]))
  (Expr stx))

這個 define-pass 接收了不知道是什麼的輸入 *，並輸出到 L0。內部只定義了 Expr 函數，把 * (stx) 翻譯成 Expr (expr)。主要的展開可以分成

let form
lambda form
application form
literal
error

我們可以簡單解釋 literal 跟 error，當展開的內容是 identifier? 或 stx-number? 其中之一，我們只需要直接回傳，因為這兩者都是和法的 L0 Expr。當其他語法處理部分都沒有捕捉成功，就報告語法錯誤。

let 是剩下來裡面最好讀懂的東西，它幾乎直接對照著翻譯到 L0 Expr，只是多給原始的 syntax 物件，並且需要再展開 expr 才傳給 L0 Expr。

在 lambda 還有 application 裡面我們都需要 (syntax->list #'(x* ...)) 的部分，這是為了把一個 syntax 最外層的 list 解開變成一個含有多個 syntax 的 list。而接下來 arg* 需要全部拿去再 parse 一遍而 param* 只需要直接傳（已經是我們想要的內容：identifier?）就好了。接著我們來測試成果。

(parse #'(let a 1))
(parse #'(let id (λ (x) x)))
(parse #'(let a-id (id a)))
(parse #'(let no-arg (foo)))

這些產出雖然看起來十分複雜，但在使用 nanopass 時卻不需要關心這些細節，只需要用 meta name 就可以了。歡迎提出問題或是改進建議，我們有 Discord channel，這篇的程式也可以在這個專案裡面找到。到這裡我相信讀者也已經了解怎麼把各種輸入傳進 nanopass 並美化輸出避免干擾的技巧，剩下的只有多加練習掌握而已，下次再見。