Zenn
Open8

Nanopass compiler frameworkのメモ

scheme
lisp
コンパイラ
NiyarinNiyarin

Nanopass compiler frameworkというScheme用のコンパイラを作るためのフレームワークのメモ。
いずれまともな記事として書く予定。

Nanopass compiler frameworkとは

  • コンパイラの中間言語の記述とその変換方法を楽に書ける枠組みを提供してくれる。
  • ただし、このフレームワークが扱えるのはS式言語のみ(LexerやParserを別で用意すれば非S式言語でもいけるが)
  • Andy Keepという人のソフトウェア (もともとChez Scheme開発元のIndiana大学の人)
  • Chez Schemeの実装に使われている(はず)

Multi-pass compiler、Nanopass compilerとは

コンパイラの中でも、入力言語を複数回のパスで処理するものをMulti-pass compilerと呼ぶ。各パスは、前のパスの入力を受け取り、次のパスへの入力を出力する。

Multi-pass compilerの内でも、各パスで行うことを最小限にしたものをNanopass compilerと呼ぶ。
Nanopass compilerは、コンパイラへの手の入れやすさやデバッグのが簡単という利点がある。
一方で、手のいれやすさと引き換えに中間的な言語の出力やASTのトラバース回数が増えるので空間、時間的な計算量が大きくなる。

NiyarinNiyarin

Nanopass compilerのちょっとした例

今回は、Piyo言語と名付けた、Schemeのほとんどの機能を削った言語から、複数のbodyを持つlambda式のbodyをbeginで包むというというパスの例を示す。

Piyo言語 → [lambdaのbodyをbeginで包む] → 複数bodyのlambda式が消えたPiyo言語

Piyo言語の拡張BNF記法

Piyo言語を拡張BNF記法でこのように定義する。この拡張BNF記法は、BNF記法の0回以上の繰り返しを...と表記したものである。Piyo言語は、プリミティブ手続きとブーリアンとシンボル、それからlambda式、begin式、手続き適用からなる。

<Expression> :: = <primitive-procedure>
            　　　    | <boolean>
		　　　| <symbol>
		　　　| (lambda (<symbol> ...) <expression> <expression> ...)
		　　　| (begin <expression> <expression> ...)
		　　　| (<expression> ...)

Nanopass compilerで記述すること

このパスの例で登場する言語は、入力言語Piyoと、変換語の言語(複数bodyのlambda式が消えたPiyo言語)である。これらのパスの入出力の言語は、define-languageという構文でS式表現されたBNFで記述することができる。各パスごとに中間言語を記述するのは面倒そうだが、ある言語との差分だけ記述できるような機能があるため楽できる。

あとは、define-passという構文で各言語間の変換方法を記述すればコンパイラが作れる。define-passでは、syntax-caseのように、構文のパターンとその変換方法を記述する。

NiyarinNiyarin

define-languageでPiyo言語を定義する

define-languageは、S式の拡張BNF記法で中間言語をこのように定義できる。
piyo-langが言語名で、terminalsから始まるリストが非終端記号(BNFの左辺に現れない記号、terminal symbol)の定義で、最後のリストが終端記号(左辺に現れる記号)の定義(ここでは、Expression)となっている。

(define-language piyo-lang
  (terminals
    (primitive-procedure (proc))
    (boolean (b))
    (symbol (x)))
  (Expression (e)
    proc
    b
    x
    (lambda (x ...) e e* ...)
    (begin e e* ... )
    (e e* ...)))

終端記号の定義にある(primitive-procedure　(proc))のprimitive-procedureは非終端記号名で、(proc)はメタ変数と呼ばれる終端記号の表現に使うときの名前のリストである。メタ変数については後で述べる。非終端記号名は、primitive-procedureの定義は術語で決められ、非終端記号名の末尾に?を付けた術語を別で定義する必要がある。例えば、primitive-procedure?はこう定義する。

(define (primitive-procedure? x)
  (or (eq? x 'cons)
       (eq? x 'car)
       (eq? x 'cdr)
       (eq? x 'display)))

他の終端記号であるsymbolやbooleanは、Schemeの標準にsymbol?、boolean?があり、import等でそれらを消去、リネームしたりしない限りは名前空間にロードされているため、新しく定義する必要はない。

メタ変数について

メタ変数は、非終端記号の定義や後述する、言語変換構文のdefine-passで使われる変数である。
terminals等で定義したメタ変数名の末尾に*、数字、?、^を付けたものもメタ変数として使える。
例えば、primitive-procedureは、procというメタ変数名で使うことができるが、proc*、proc1もメタ変数として使うことができる。慣習的には、末尾に*を付けるのは0回以上の繰り返しの対象に使う。

まだ途中

NiyarinNiyarin

出力言語(複数bodyのlambda式が消えたPiyo言語)をdefine-languageで定義する

この出力言語は、Piyo言語から複数bodyのlambda式の定義を1つのbodyのlambda式の定義に書き換えるだけで良い。このようにある言語を拡張して、差分だけ記述するような方法がnanopass-compiler frameworkにはある。

Piyo言語を拡張した言語を作るには、define-languageの中にextends piyo-langと書き、削除したい項目の頭に-、追加したい項目の頭に+を置く。

(define-language single-body-lambda-piyo-lang
   (extends piyo-lang)
   (Expression (e)
       (- (lambda (x ...) e e* ...))
       (+ (lambda (x ...) e))))
NiyarinNiyarin

複数bodyのbeginを削除するパスをdefine-passで定義する

(define-pass remove-multi-body-lambda :
   piyo-lang (e) ->  single-body-lambda-piyo-lang ()
   (Expression : Expression (ir) -> Expression ()
      ((lambda (,x ...) ,(e) ,(e*) ...) `(lambda (,x ...) (begin ,e ,e* ...)))))
NiyarinNiyarin

nanopass compiler frameworkのChez Schemeでの実行方法

R7RS以外のライブラリ読み込み方法を知らないので、最低限実行するためのコードの書き方とChez Schemeの実行方法について書く。
適当な場所にnanopass-framework-schemeをcloneする。

git clone https://github.com/nanopass/nanopass-framework-scheme

で、ソースコードの頭にnanopassを読み込むためのimport式を付けておく。rnrsも読みこむ。

(import (nanopass) (rnrs))

あとは、

scheme --libdirs .:[nanopass-framework-schemeへのリンク] --script [コンパイラのソースコードへのリンク]

とすれば実行できる。

NiyarinNiyarin

簡単な例のソースコード

(import (nanopass) (rnrs))

(define (primitive-procedure? x)
  (or (eq? x 'cons)
      (eq? x 'car)
      (eq? x 'cdr)
      (eq? x 'display)))

(define-language piyo-lang
  (terminals
    (primitive-procedure (proc))
    (boolean (b))
    (symbol (x)))
  (Expression (e)
    proc
    b
    x
    (lambda (x ...) e e* ...)
    (begin e e* ... )
    (e e* ...)))

(define-parser parse-piyo-lang piyo-lang)

(define-language single-body-lambda-piyo-lang
   (extends piyo-lang)
   (Expression (e)
       (- (lambda (x ...) e e* ...))
       (+ (lambda (x ...) e))))

(define-parser parse-single-body-lambda-piyo-lang single-body-lambda-piyo-lang)

(define-pass remove-multi-body-lambda :
   piyo-lang (e) ->  single-body-lambda-piyo-lang ()
   (Expression : Expression (ir) -> Expression ()
      ((lambda (,x ...) ,(e) ,(e*) ...) `(lambda (,x ...) (begin ,e ,e* ...)))))

;(display (unparse-single-body-lambda-piyo-lang
;            (remove-multi-body-lambda
;                (parse-piyo-lang
;                    '(cons (lambda (x y) (display x) (lambda (z) (cons x y))) foo )))))
;(newline)