LunarML進捗：signatureの実装に向けて

2件の返信

自作SML処理系進捗：Hello Lua! の続き。

自作SML処理系「LunarML」の言語機能の実装も佳境に入ってきて（equalityやexception等の厄介な奴らはだいたい片付けた）、残すところは

  • withtype (derived form)
  • abstype（Successor MLに従いderived formとして実装する予定）
  • signature
  • functor

くらいとなってきている。

derived formはいつでもできるとして、未実装の機能のうち大きなものがsignatureとfunctorだ。このうちfunctorはsignatureに依存するので、signatureを先に実装することになる。

第一級モジュールの動機

それとは別に、モジュール関連の実装したい機能として、第一級モジュールに相当する機能を入れたい。これのモチベーションは標準ライブラリーを実装するための実用上のものだ。

具体的には、LuaバックエンドでInt64モジュールを提供したいとしよう。

Lua 5.3以降であれば標準の整数型が64ビット幅であることが期待できる（Lua処理系のコンパイル時のオプションで変更可能なので、厳密には実装に依存する）。

一方、LuaJITはLua 5.1相当なので標準の整数型なんてものはない。代わりに、C FFI用のint64_t/uint64_tが利用できる（というかC FFIを考慮に入れるならこれを使うべき）。

どちらでもない場合（例：素のLua 5.2）は32ビット整数を二つ組み合わせて64ビット整数を表現するしかない。

というわけで、擬似コードで書けばInt64モジュールの定義は次のようになる：

structure Int64
  = if <Lua 5.3 or later> then
        Int (* 標準の int 型が64ビット *)
    else if <LuaJIT> then
        struct
            <implementation based on ffi.typeof("int64_t")>
        end
    else
        struct
            <emulated implementation>
        end;

SMLでは通常の値レベル（コア）の式とモジュールレベルの式が区別されており、if-then-elseでモジュールの定義を分岐させることはできない。しかし、第一級モジュールがあれば「実行時の判断でモジュールの中身を入れ替える」ことが可能になる。

SMLを拡張した処理系であるAlice MLやHaMLet Sは、pack/unpackという構文でモジュールを値として扱うことを可能としている。これを使うとInt64の例は

structure Int64
  = unpack (if <Lua 5.3 or later> then
                pack Int : INTEGER
            else if <LuaJIT> then
                pack (struct
                          ...
                      end
                     ) : INTEGER
            else
                pack (struct
                          ...
                      end
                     ) : INTEGER
           ) : INTEGER;

と書ける。packとunpackの両方でsignatureの注釈が必要になるのが面倒なところだ。

目標として、ターゲットとするLuaのバージョンは決め打ちするのではなく、「Lua 5.3とLuaJITの両方で動くようなLuaコード」も出力できるようにしたい。その場合、モジュールに関する条件分岐は真に実行時に行われることになる。

モジュール実装方針の転換

というわけで、モジュールの実装にあたっては第一級モジュールを提供できるような設計としたい。つまり、structureを実行時に実体を持つような値としてコンパイルしたい。その場合functorはターゲット言語の関数にコンパイルするのが自然だろう。

ところが、前回の記事の時点でのstructureの実装はコンパイル時にstructureの実体が消えてしまうものだった。つまり、

struct Foo = struct
    val x = 123
end

は

local Foo_x = 123

という風に中身を展開したものになる。これは「structureをとりあえず実装する」には良かったが、functorや第一級モジュールを実装する上では不都合となった（第一級モジュールを考慮しないのであれば、functorは全て展開するという手があるが）。

というわけでコンパイラーを改造して、structureの実体を残すことにした。先程のコードはターゲット言語では

local Foo_x = 123
local Foo = { x = Foo_x }

というコードになる。

この改造がしんどかった。しんどいのは単にstructureの実装を変えるだけではなく他のリファクタリングも一緒にやったからかもしれないが、「変更後のコードが動作する段階までリファクタリングする」のも大変だったし、「リファクタリング後のコードが用意済みのテストをパスするまで機能を充実させる」のも大変だった。リファクタリング前の段階でSMLの機能の大部分を実装してしまっており、リファクタリングではそれを再現する必要があったのだ。

方針転換で気をつけないといけないのが定数伝播や不要コード削除（DCE）等の最適化だ。第一級モジュールを実装可能にした代償に出力コードが巨大化するのは頂けない。ここは最適化を強力にすることでどうにかしている。

F-ing modules

モジュールシステムを作り直す上で参考にしているのが、F-ing modulesである。これはsignatureやfunctorをSystem Fωの存在型を使ってエンコードする代物だ。

現在、LunarMLでは型推論が終わった後にSystem Fライクな中間コードに変換している。この部分をSystem Fω+存在型に拡張する必要がある。

structureの名前空間

F-ing modulesでは、脱糖後のモジュールはレコードの一種として表現している。この際、ソース言語（SML）では同じスコープに同じ名前の値識別子とstructure識別子が共存できる：

structure Foo = struct
    val x = 123
    structure x = struct
        val y = "Hello"
    end
end;
Foo.x; (* => 123 *)
Foo.x.y; (* => "Hello" *)

ので、レコードのラベルは工夫して値識別子とstructure識別子が被らないようにしなければならない。

典型的な回避方法はprefixをつけることだ。例えば、SMLの識別子はアンダースコアから始まることができないので、「脱糖時にstructureの方にはアンダースコアを先頭にくっつける」という方法で衝突を回避できる：

local Foo = {
  x = 123, -- 値の方
  _x = { -- structureの方
    y = "Hello"
  }
}

さて、F-ing modulesのレベルでは値識別子とstructure識別子を区別するだけで良かったが、実際のSMLには他にも色々あり、実装次第では他のモノもエクスポートする必要がある。

LunarMLの今の実装方式でエクスポートする必要がある他のモノというのは具体的には

  • 例外のタグ
  • 型のequality

だ。

例外のタグというのは、例外（exn型の値）をパターンマッチするのに必要な情報だ。他の言語でいう実行時型情報に近い。例えば、今のLunarMLでは

structure Foo = struct
    exception E of string
end

は

local Foo = {
  E = function(payload) ... end, -- Eのコンストラクター
  ["E.tag"] = ..., -- Eのタグ
}

という風なコードにコンパイルされる。

型のequalityは、処理系によっては実行時のタグに基づいて処理するものもある（SML/NJがそんな感じだったはず）が、LunarMLでは型情報に基づいて「比較関数 'a * 'a -> bool」を値として受け渡しするようにコンパイルしている。例えば、 <> : ''a * ''a -> bool は

fun x <> y = not (x = y);

と書いたものが

val <> = fn (eq : 'a * 'a -> bool) => fn (x, y) => not (eq (x, y));

と脱糖される。

モジュールはopaqueなeqtypeをエクスポートすることができるので、比較関数も一緒に提供しなくてはならない。

structure Foo = struct
    ...
end : sig eqtype t end

という定義は

local Foo = {
  ["t.="] = function(a) ... end, -- t に対する比較関数
}

というコードにコンパイルされる。

というわけで、「モジュールをレコードにコンパイルする」と一口に言っても、LunarMLの現行の実装では「値識別子」「structure識別子」「例外タグ」「型の等価性」の4種類のラベル（名前空間）を使い分けている。名前空間の数は今後増えるかもしれない（データ型の表現に関するものなど）

【追記】よく考えるとequalityはモジュールではなく型に付随するものであり、モジュール自体ではなく型のpacking/unpacking（存在型の導入と除去）に付随させるべきであった。なのでtransparent constraintでは必要なく、opaque constraintやfunctorを扱う際に存在型の一環として扱うことになる。【追記終わり】

ユーザー定義のオーバーロード

先程Int64の例を書いたが、SMLの整数型は「リテラルと演算子のアドホックなオーバーロード」に関して特別扱いを受けるという点で本来は組み込み型の一種である。

そういう型をユーザー定義できるようにするには、リテラルと演算子についてのオーバーロードを拡張可能にする必要がある。

現在考えている案は、整数型などの組み込み型をライブラリーで定義する際のstructure束縛に _magic のようなdirectiveをつけてそれが組み込み型であることをコンパイラーに教える方式だ：

_magic(class="Int", prec=SOME 64)
structure Int64 = ...

_magic の引数のclassは定義する型がどのクラス（Int, Word, Real, String, Char）に属するかを表し、他の引数はその型が表現できる範囲等の情報を表す。_magic の直後にはstructureの定義が続き、クラスに応じて指定されたsignatureを持たなければならない。

例えば、クラスがIntなら後続のstructureは

sig
    eqtype int
    val fromInt : Int.int -> int
    val + : int * int -> int
    val - : int * int -> int
    val * : int * int -> int
    val div : int * int -> int
    val mod : int * int -> int
    val < : int * int -> bool
    val <= : int * int -> bool
    val > : int * int -> bool
    val >= : int * int -> bool
    val ~ : int -> int
    val abs : int -> int
end

を実装しなければならない。

関数はいいとして、リテラルの脱糖方法は自明ではない。文字列表現で埋め込んで fromString を使うという手もあるが、 fromString は option を返し、現在のLunarMLでは option は組み込み型ではない。

文字列以外の案としては、「32ビットで表現できる値は Int.int および fromInt を使って表し、32ビットを超える値は fromInt と +, * を組み合わせて表現するように脱糖する」がある。筆者の現在の案はこれである。

いずれにせよ、拡張可能なオーバーロードを大々的に導入してしまうとそれはもはやSMLではなくなってしまうので、 _magic のようなdirectiveは「標準ライブラリーの実装向け」となる。

今後

今後の計画は

  • signatureとfunctorを実装し、一人前のStandard MLコンパイラーとしての機能を確立させる。
  • Lua 5.3+以外のLuaの変種（Lua 5.2, LuaJIT）にも対応させる。
  • JavaScriptバックエンドを実装する。
    • TCOが面倒そう。
      • JavaScript処理系がみんなSafari/JavaScriptCoreになってほしい、とか言ったらｳｪｯﾌﾞｴﾝｼﾞﾆｬｰは怒るんだろうなあ

あたりである。これとは別に、応用（アプリケーション）面もやっていきたい。

LunarMLは、元々「Lua（というか動的言語）で書くのが辛いけど実行環境としてはLua（あるいは他の動的言語）しか選べない」というアプリケーション開発で静的型付けの恩恵に与るために作られた。具体的なアプリケーション名はClutTeXだ。なので、そろそろ「Luaで書かれたClutTeXをSMLで書き直す」作業に取り掛かりたい。

このエントリーをはてなブックマークに追加

「LunarML進捗：signatureの実装に向けて」への2件のフィードバック

  1. ピンバック: LunarMLの進捗と妄想 | 雑記帳

  2. ピンバック: LunarMLの進捗2021 | 雑記帳

コメントを残す

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です