SML、はじめました

動機

プログラマーの3大欲求と言えば「プログラミング言語(処理系)を作りたい」「テキストエディターを作りたい」「OSを作りたい」である。これらの欲求は定期的に湧いてきて、多くの場合は実を結ぶことなく霧消する。

そんなわけで先日、筆者にもプログラミング言語の処理系を作りたい欲求が湧いてきた。

具体的には、ML系の型推論を持った言語を作りたい。また、エフェクト推論・リージョン推論のような技法を試したい(一旦普通に処理系を作り、その後に改造してエフェクト推論やリージョン推論を試す)。

別の方向性の動機として、型のないスクリプト言語(具体的にはLua)で大きなソフトウェアを書くのがだるい。静的型のついた言語からスクリプト言語にコンパイル(トランスパイル)するやつを作りたい、というものがある。

最近はJavaScriptへトランスパイルする処理系は色々登場したが、それ以外のスクリプト言語を吐き出す処理系というのはまだ少ないように思う。

これらの動機付けが混ざった結果、「型推論のある言語からスクリプト言語へのコンパイラーを作れば良い」という結論に至った。

目次

既存の言語か、自作言語か

新しく言語処理系を作るわけだが、入力となる言語は既存の言語なのか、それとも新しく作った言語なのかという問題がある。

既存の言語の場合は、エディターの構文ハイライトやレキサー・パーサージェネレーター(lex/yacc)等のツールに関しては既存のものを利用できる。また、その言語自身でコンパイラーを書く「セルフホスト」も容易になる。

自作言語の場合はそういう意味ではハードな道のりだが、言語の設計の自由度は高い。

今回は既存の言語を実装することにした。

比較検討

広義のML系言語(MLライクな型推論を持つ言語)として、SML, OCaml, Haskell, PureScriptの4つを比較検討する。

SML

由緒正しい(?)MLである。

型システムに関しては、割と控えめだと思う。控えめということは、実装しやすいということである。

既存の処理系としては、MLtonやMLKitなど、個性的な処理系が存在する。SMLToJsという、JavaScriptを吐き出すコンパイラーも存在する。

算術演算に関しては、組み込み型に関する演算子(とリテラル)のアドホックなオーバーロードができる。その分型推論は犠牲になる。

OCaml

文法が筆者の好みではない(revised syntaxならかなりマシになりそう)。

算術演算に関しては、整数と浮動小数点数の演算では異なる演算子を使い分ける必要がある。

型システムに関しては、SMLと比べるとかなりリッチなはずである。第一級モジュールやGADTsがあるらしい。

Haskell

筆者がメインで使っている言語である。普段使いですでによく知っているのは利点である。

型クラスがあり、それによってアドホックな演算子オーバーロードを実現している。

Haskell 2010の範囲であれば、機能は控えめで、割と実装しやすいのではないかと思う。

ただし、実用的なHaskellプログラムは大抵Haskell 2010の範囲から逸脱している、つまり、何らかののGHC拡張を使っていると思われる。特にRankNTypesやMultiParamTypeClassesやTypeFamilies等は型システムに関する自明でない拡張である。この辺の話題はTaPLやATTaPLにはあまり書かれていないので、実装したかったら自分で文献を探す必要がある。

また、デフォルトで遅延評価であり、正格評価なスクリプト言語を出力する際にオーバーヘッドがかかりそうである。(正格性解析などの最適化を実装すればマシになるかもしれないが、その分手間がかかる)

PureScript

Haskell風の文法を持つ純粋関数型言語である。Haskellの重要な特徴である型クラスを受け継いでいる。

Haskellと違って正格評価なので、割と素直なスクリプト言語コードを吐き出せるのではないかと思う。

若い言語なので、仕様がまだ確定ではない、というか実装が仕様である。

型システムに関してはHaskellで言うところのRankNTypesとMultiParamTypeClasses/FunctionalDependenciesを持つ。

公式の処理系はJavaScriptを吐き出すが、他にもいくつかターゲット言語が異なる処理系が存在するようである (Alternate backends)。Luaバックエンドも存在したようだが、残念ながら開発が止まっている。

どれにするか

色々考えた結果、SMLを実装してみることにした。仕様がしっかりと定まっている、型システムが控えめである、デフォルトで正格評価である、という点がポイントである。

実装に使う言語もSMLとする。これは筆者がSMLに親しんでいないので慣れるためと、SMLコンパイラーを実装した時に動かせるSMLコードがあった方が良いという理由である。

Haskellerから見たSML

というわけでSMLをちょっとかじってみた感想を書く。

演算子と識別子

Haskellではアルファベットからなる識別子を中置演算子として使う場合は ` ` で囲むが、SMLはinfix宣言された識別子は特別な飾り付けなしに中置演算子として使える。例: 10 div 5

一見すると飾りがないSMLの方がスッキリして見えるが、慣れていない読者や処理系にとっては「どれが中置演算子か」を覚えておかなくてはならないので、SMLの方が厄介である。

また、Haskellは型構築子やデータ構築子を大文字から始めるが、SMLにはそのようなルールはない。間違って既存のデータ構築子と同じ名前の変数を定義しようとしたらおかしなエラーが出ることになる。

つまり、演算子・識別子の名付けの規則と中置演算子化の規則に関しては、Haskellの方が優れていると思う。

直積?タプル?

Haskellではタプルの値もタプル型も (,)で表す。一方SMLはタプルの値は (,) だが、タプル型は A * B という風に中置の * を使う。言うまでもなく、数学の直積を意識したのだろう。

SMLの型レベルにも (,) と言う記法はあって、型構築子が複数の引数を取る場合に (,) を使う。

型構築子

Haskellの型構築子は、関数適用と同じように構築子を最初に書いて、引数を後に書く。一方、SMLでは型構築子は後ろに書く。

Haskellでは型構築子もカリー化されているが、SMLはそうではない。

例外

SMLやOCamlには、例外を定義するための文法がある。C++やJavaでは、例外も通常の型として定義する。HaskellのIO例外の場合も例外は通常の型として定義し、ExceptionクラスやTypeableクラスのインスタンスとする。(Haskellの場合はエラー処理にMaybeやEither等のモナドを使うという手もある)

SMLやOCamlがわざわざ例外を定義するための文法を用意しているのは、これらの言語には「実行時型情報がない」ことが関係していると思われる。

レイアウト

Haskellではレイアウト(オフサイド)ルールを採用している。letでの宣言の羅列も、パターンマッチの羅列も、do記法の文の羅列も、明示的に { ; } で区切るか、レイアウトルールに任せるかを選択できる。

SMLにはそういう統一的なルールはなく、let .. in や local .. in は end で閉じるが、パターンマッチには終端記号はない。複数の式の逐次実行 a; b; c が使えるのはカッコの中か let .. in .. end の中である。

その他

SMLにはパターンマッチのガードやレコードの一部フィールドの更新はないが、Successor ML変更点の概要)には提案されている。

Spread the love