kmizuの日記

プログラミングや形式言語に関係のあることを書いたり書かなかったり。

ちょっと行列作りますね言語Matlikeを作りました

注:この記事は、2020年1月にQiitaに投稿した自作言語Matlikeについての記事のリメイクです。アカウントを消して元の記事が全部消えたので、移植ではなくリメイクです。

はじめに

 私は、2019年12月から、1か月1言語計画というのを始めています。要はどんなダメダメぽい石ころみたいなアイデアみたいでも、中には原石もあるかもしれないということで、思い浮かんだアイデアをどんどん言語として実装していこうというものです。悲しいことに、2020年2月分、3月分が出来ていないままですが、その辺は今週にえいやっとなんかテキトーなものを作るつもりです。この記事は、2019年12月分の言語として作成したMatlike言語の紹介です。

Matlikeを作った動機

 Matlikeのキーワードは「行列」です。皆さんが普段から使ってるJavaやらPythonやらJavaScriptやら、大半の言語には何らかの形で行列を扱うライブラリがついています。行列計算を必要とする分野とは案外多いものなので、シェアの多い言語は自然とそういうライブラリを備えるようになるのでしょう。そこからさらに一歩進んで、行列を扱う言語機能を持った言語もあります。たとえばMatlabやそのOSS実装(ぽいもの)であるGNU Octaveとか、あるいはJuliaもそういう言語に含めてもいいかもしれません。

 さて、既存の大抵のプログラミング言語では行列を扱えるわけですが、既存の言語の行列の扱いには少し不満がありました。

  • 誤った行列同士の演算を静的に検出できない

 たとえば、行列積としては、

[1 2 3]  *  [4
                 5
                 6]

 というのはOKでも、

[1 2 3] * [4 5 6]

 というのは未定義なのではじいて欲しいのですが、こういうのを静的に検出できる言語が案外ないのです。実のところ、研究レベルではそういう話はままあるでしょうし、C++のテンプレートを使って依存型モドキを使えばそういう機能を実現できるでしょう。しかし、フルスペックの依存型を使うのはいかにも大げさです。なんかいい感じに行列のを型パラメタとして持つちょうどいい感じの言語が作れないかな、というのが一つです。

 皆さん、数学で習う行列って

[1 2 3
 4 5 6]

 て書きますよね(?)いや、もっと専門の分野では違うのかもしれませんが、まあ少なくとも行列を書き下したいときは、こんな風に二次元上に行列の要素を書きたいことは多いはずです。しかし、残念ながら、既存の言語で、こういう感じのレイアウトを良い感じで解釈して(上の例なら 3 * 3 行列として扱って欲しい)くれる言語はあまりありません。Juliaはそのような数少ない言語の一つですが、静的型付き言語ではないので、たとえば、

[1 2 3
 4 5]

 みたいな、型検査の段階ではじいて欲しいリテラルをはじけないのでダメということにします。

 これはやや無理くりなんですが、たとえば、以下のような行列リテラルMatrix<Int, 2, 2> て感じで型がついて欲しいなと私は思うのです。

[1 2
 3 4]

 しかし、そういう都合のいい言語は知る限りでは、ほとんどありません。

 という感じで、多少無理やりですが、理由をこじつけて、以上の要件を満たすプログラミング言語Matlikeを作ってみました。

Matlikeの機能

 というわけで、機能紹介です。

 実は、行列リテラルのパーザをいい感じに書いてみたいというのが一番大きな理由でしたので、これについてはかなり凝っています。

 たとえば、以下のように行列リテラルを書くと、 Matrix<Int, 2, 3> という型が付きます。

 [
 1 2 3
 4 5 6
] // Matrix<Int, 2, 3>

 ちなみに、これを見ればわかる通り、空白が要素間のセパレータになれる上に、改行が行セパレータになれるという仕様です。おかげで結構パーザを作るのに苦労したのですが、後述する型推論との兼ね合いで、たとえば、

val m = [
 1 2 3
 4 5 
]

 のような、行列としてなんかおかしいリテラル型推論の段階で、 2 != 3 みたいなメッセージが出て、はじかれます。

 さて、Matlikeでは行列をファーストクラスとして扱っています。ここでいうファーストクラスとは、行列を引数として渡したり、返したり、無名の行列が作れる程度の意味です。それに加えて、Matlikeの行列を表すMatrixMatrix<E, Row, Col>という形を取ります。RowColが整数であるというのがポイントで、そのおかげで依存型モドキぽいものが実現できています。

 たとえば、Matlikeで行列同士の積を表す演算子_*_ ですが、これを使って、以下のような関数を定義することができます。

def mult(x, y) = x _*_ y

 文法がなんだかScala風味ですが気にしないでください。このmult関数の型は以下のように推論されます。

def mult<A, B, C, D>(x: Matrix<A, B, C>, y: Matrix<A, C, D>): Matrix<A, B, D> = x _*_ y

 ここで、xyの内、要素型がAで一致していて、xの列数とyの行数も一致しているのがポイントです。Matlikeの型推論器はHindley-Milner型推論をテキトーに拡張したものなのえで、型注釈が一切なくても、こんな感じでいい感じで型を推論してくれます。型推論万歳(いや、現実問題、これでいいのかは微妙ですが)。

  • 誤った行列同士の演算を静的に検査できる

 これは機能というより、そういう型システムを作ったことによる恩恵なわけですが、上の方で例に出た

[1 2 3] * [4 5 6]

 なんて例は、1 != 3 て感じのメッセージが出て、型検査を通りません(現在の実装だと、unificationに失敗しただの何だのといったメッセージが出ますが、それはおいておきます)。

まとめ

 Qiitaに書いた記事の方はもうちょっと色々書いた気がするのですが、こんな感じで行列をなんかうまいこと取り扱えるプログラミング言語を作ってみたのでした。Qiitaの記事にも書いたのですが、これからは、こんな感じで(いや、私のはいい加減ですが)、ドメイン特化型の型システムをがんがん作っていくと色々恩恵が大きいのではないかと思う今日この頃です。

 ではでは。