從 frontend(compiler) 到 nanopass
8.3

從 frontend(compiler) 到 nanopass

Lîm Tsú-thuàn <dannypsnl@gmail.com>

採用 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?,然後才檢查其內容,因此一定有做到儲存原始最上層物件的結果。至於 letabstractionapplication 都自行持有 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)。主要的展開可以分成

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

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

在 lambda 還有 application 裡面我們都需要 (syntax->list #'(x* ...)) 的部分,這是為了把一個 syntax 最外層的 list 解開變成一個含有多個 syntaxlist。而接下來 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 並美化輸出避免干擾的技巧,剩下的只有多加練習掌握而已,下次再見。