rb.blog.pasberth.com

User
@pasberthのRuby系ブログ

パーサの勉強のために、前回は infixing library を作りましたが、今回は型システムを作ってみます。 Lisp という言語はコード自体がデータとして扱えるので、このようなシステムを作るにはうってつけです。

型システム入門を読みつつ型システムを Lisp のコードに落とし込んでいきます。

今回作ったものは このコミット にあります。

とはいえなんというか、ブログにできることがそんなに多いわけではなく(実装の詳細を日本語にできない)。

まず、型の制約を表すデータを定義します。

(defrecord Constraint [expected actual])
(defrecord Forall [variables expression])
(defrecord Bound [variable])
(defrecord Pair [first second])
(defrecord Arrow [source target])

Forall は変数を導入するデータで、 Bound が束縛変数、 Arrow が関数に相当します。 (Forall. [:a] (Arrow. (Bound. :a) (Bound. :a))) のように使います。

Constraintexpected は期待する型で、 actual が実際の型です。これが同じじゃなかったら型エラーにするわけです。

それから、このデータはまだ人間が扱えるものではありませんから、もうすこし人間が読み書きできるようにマクロを定義してあげます (ここ重要) 。 このあたり に定義があります。

このマクロのおかげで (Forall. [:a] (Arrow. (Bound. :a) (Bound. :a)))(constraint :a -> :a) と書けるようになりました。やったね! (hold :a -> :a) と書くと、 (Constraint. (Forall. [:a] (Arrow. (Bound. :a) (Bound. :a))) (Forall. [:a] (Arrow. (Bound. :a) (Bound. :a)))) に展開してくれます。

そして { 'identity (hold :a -> :a) } のような単純な Map を型システムを表すデータとして扱い、このデータをインタプリトする感じにして型システムを構築します。

とりあえずザッと書いて動きを確かめてみます。

それからいろいろと必要な定義して、 infer-type' 関数で、型システムとコードからコードの型を得るようにします。 ただし、 infer-type' 関数はマクロ展開済みのコードを受け取る必要があります。

というわけで実際に動かしてみるとこんな感じです

うむ、なんかいい感じに推論できてるっぽいので、とりあえずこれでよしとしましょう。

とりあえず型システムを実装してみての雑感は、型システムを実装すると分岐の嵐になるってことです (特に型変数への代入とか)。 多態は分岐の汎用的な形なので、このあたりだと Clojure の Multimethods がわりと活かされてくる気もしました。