チラシの裏

プログラミングとか色々

"Syntactically, SML is a nightmare"

現在僕は趣味でStandard MLのサブセットの処理系を実装しようとしているのですが、皆さんのご存知の通り、Standard ML構文解析は非常に難しい事が知られています。 今回はML Kitの実装に関する文書を参考に構文解析器を実装した時の事について書きたいと思います。 ちなみに、タイトルもその文書からの引用です。

何が難しいのか

言語仕様のpp.4-10を読むと分かる通り、アルファベットその他の列では終わらずにいくつかの記号(+、-など)のみからなる文字列も変数名に使う事もできます。 加えてどの変数も二項演算子にできるわけですから、明らかに字句解析の段階ではどの変数が二項演算子なのか判別ができません。

さらに、どの変数が二項演算子なのかはもちろん、演算子の優先順位や結合性もプログラマーが自由に決められます。それもスコープに依存して。 また、二項演算子として定義した変数の前に"op"と書けば一時的にキャンセルすることもできます。

従って、Standard MLでは以下のようなプログラムを書くことができます。

(* divisibleを左結合の二項演算子として用いる *)
infix divisible
fun n divisible m = n mod m = 0
(* 二項演算子なのでこういう使い方ができる *)
val hoge = 30 divisible 5
(* opで一時的にキャンセルできる *)
val hogehoge = op divisible (17, 2)
local
  (* nonfixでこれ以降キャンセルできる *)
  nonfix divisible
in
  val foo = divisible (42, 42)
end
(* スコープを出たので元に戻っている! *)
val bar = 1 divisible 2

(* *は結合の強さが7で左結合の二項演算子とする *)
infix 7 *
(* +は結合の強さが6で左結合の二項演算子とする *)
infix 6 +
(* ::は結合の強さが5で右結合の二項演算子とする *)
infixr 5 ::

(* ((1 + (2 * 3) * 4) + 5) :: (1 + 2) :: []と解釈される!! *)
val baz = 1 + 2 * 3 * 4 + 5 :: 1 + 2 :: []

lexとyaccだけでは荷が重そうです。

解法

最初に挙げた文書を参考に、yaccで生成する構文解析器は二項演算子の現われ得る部分についてはAtExpの列として残し、後でStandard MLで書いた構文解析器を用いてスコープを見ながら構文解析する事で解決しています。

実際のコードを見てみましょう。ML-Yaccで生成する構文解析器のソースコードudon.grmに書かれています。 この構文解析器はStandard MLのサブセットの二項演算子を除いた部分を構文解析し、concreteSyntax.smlに書かれている形式の構文木を出力します。

structure ConcreteSyntax = struct
  (* abstract syntax tree of expression *)
  datatype exp =
    (* constant *)
      CONST of Const.t
    (* variable *)
    | VAR of string
    (* non-infixed operator *)
    | OP of string
    (* if M then N_1 else N_2 *)
    | IF of exp * exp * exp
    (* fn x => M *)
    | ABS of string * exp
    (* let d in N end *)
    | LET of dec list * exp
    (* sequence of expression *)
    | SEQ of exp list
    (* ( M ) *)
    | PAREN of exp
    (* (M_1, ... , M_n) *)
    | TUPLE of exp list
    (* case M of (x_1, ... , x_n) => N *)
    | CASE of exp * string list * exp
  (* abstract syntax tree of declaration *)
  and dec =
    (* val x = M *)
      VAL of string * exp
    (* val rec f = M *)
    | VALREC of string * exp
    (* infix d vid_1 ... vid_n *)
    (* infixr d vid_1 ... vid_n *)
    | INFIX of Infixer.Assoc.assoc * int * string list
    (* nonfix vid_1 ... vid_n *)
    | NONFIX of string list
end

本来の意味での抽象構文木には括弧、opや列等の要素は必要無いはずですが、まだ完全には構文解析が終わっていないので残してあります。

後はスコープを意識しながら残りを構文解析する訳ですが、この処理はinfixer.smlとinfixing.smlに書かれてあります。 関数適用は必ず二項演算子より優先順位が高いと決め打ちして再帰下降構文解析を行い、二項演算子はその環境での優先順位や結合性に従って演算子順位構文解析を行っています。この構文解析器の出力についてはsyntax.smlを参照して下さい。 やたら引数の多い関数がありますが、Standard MLには第1級モジュールが無くてファンクタを使えなかったので泣く泣くこういうインターフェースになりました。

今後の方針

構文解析だけで無駄にエネルギーを使ってしまいました。 この記事を書いた時点でCPSっぽい中間表現までは変換できたので、今後はSSAに落としてLLVMに食わせるなり中間表現の時点で末尾再帰の最適化をするなりしたいですね。

演算子順位構文解析

普段日常生活を営んでいると何となくコンパイラを作りたくなる事はありませんか?僕はあります。 演算子順位構文解析を用いることでStandard MLで行なわれているような演算子の順序の入れ替えを実現できるのではないかと思い、試しに実装してみました。

続きを読む

LCF MLについて

この記事はML Advent Calendar 2014 24日目のために書かれました。

Standard MLをはじめとするML系言語の始祖として、よくLCF MLの名前が挙げられます。 ここでは、LCF MLの言語機能について解説しつつ後の言語に与えた影響について思いを馳せたいと思います。

続きを読む

SMLでソート

この記事はML Advent Calendar 2014 8日目のために書かれました。

多くの言語においてソートは標準ライブラリで提供されていますが、Standard ML Basis Libraryにはソートを行う関数が存在しません。 処理系依存で良ければSML/NJのListMergeSort.sortの様に用意されている場合もある様ですが、 ここでは別の方法を考えたいと思います。

続きを読む

ニュートン法とDKA法の実装

大学でニュートン法DKA法で方程式の解を求める課題が出たので、今回は趣向を変えてStandard MLで実装しました。

続きを読む

ちょっとだけクイックソート

よい実装かどうかは抜きにして、一般的な関数型言語ではリストに対するクイックソートを簡単に書く事ができます。 一方、そのようなよく見かける実装ではリストの結合を再帰内で用いていますが、 一般に関数型言語ではO(n)の時間計算量を要するため、リストの結合を用いる事はよくないとされています。

今回はアキュムレータを用いる事でリストの結合を用いずにクイックソートを実装したいと思います。

続きを読む

CoqからSMLへ

CoqにはExtractionという機能があり、Coqで書かれたソースコードから対応する他の言語のソースコードを出力する事ができます。今回はそのExtractionをStandard MLに対応させた事について書こうと思います。

続きを読む