読者です 読者をやめる 読者になる 読者になる

チラシの裏

プログラミングとか色々

SMLでコンパイラを書いた

SML

このエントリはML Advent Calendar 2015言語実装 Advent Calendar 2015の20日目の記事です。 言語実装 Advent Calendar 2015の19日目の記事はh_sakuraiさんのJavaのサブセットコンパイラの作成でした。

続きを読む

GADTを用いた二項ヒープの実装

OCaml

このエントリはML Advent Calendar 2015の14日目の記事です。 13日目の記事はよんたさんの関数型プログラミングにおける再帰関数の考え方でした。

続きを読む

型推論の健全性の証明

Coq OCaml

このエントリはTheorem Prover Advent Calendar 2015言語実装 Advent Calendar 2015の11日目の記事です。 言語実装 Advent Calendar 2015の10日目の記事はkeenさんのリージョンについてでした。

続きを読む

手続き型言語OCaml

OCaml

この記事はML Advent Calendar8日目の記事として書かれました。 7日目の記事はでこれきさんのfoldみぎひだりです。

Standard MLOCamlをはじめとしたML系の言語は関数型言語として有名ですが、参照、配列、例外といった副作用を伴う機能も扱う事ができます。 また、ML系の言語で手続き的に書いたからと言ってその言語の魅力が損なわれるわけではなく、 強い静的型付け、型推論やparametric polymorphismなどの恩恵を受けられるので、むしろ良く設計された手続き型言語のように映る事でしょう。 積極的にMLで手続き的な処理を書いていこうな。

続きを読む

単一化の証明

Coq

この記事はTheorem Prover Advent Calendar 2015の7日目のために書かれました。 6日目の記事はmathinkさんのCoq で環のイデアルを作ってみるです。

続きを読む

Coqでちょっと複雑なデータ構造を書こうと思ったらハマった

Coq

何となくMinCamlにCoqで証明を付けたいと思い立ったのでOccurrence checkの検証を証明しようと思ったのですが、ちょっとした問題に遭遇したのでメモ。

続きを読む

"Syntactically, SML is a nightmare"

SML

現在僕は趣味で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に食わせるなり中間表現の時点で末尾再帰の最適化をするなりしたいですね。