LunarMLの進捗・2022年1月

前回の報告記事：

LunarMLの進捗2021

第二回関数型プログラミングの会（仮）での発表と、今年の目標

先日の第二回関数型プログラミングの会（仮）のLTでLunarMLについて発表させていただいた。「関数型プログラミング」というよりは「言語」の話になってしまった気がするが気にしない。

スライドは

LunarML@func_party.pdf

に置いた。最後のページには

2021年のStandard MLニュース

SML/NJがMLRISCからLLVMに移行
SML#がGitHubへ移行
日本語書籍「プログラミング言語Standard ML入門改訂版」
Poly/MLがARM64コードジェネレーターを実装

2022年はLunarMLが実用的になる年です！

と書いた。そう、2022年のLunarMLの目標は「実用的な処理系にする」ことだ（宣言ドリブン開発）。具体的には、

標準ライブラリーを整備する。
自分自身をコンパイルできるようにする。
Standard MLで書かれた他の処理系（HaMLetが候補）もコンパイルできるようにする。
REPLとインタープリターを実装する。
JavaScriptバックエンドを作る。Webで試せるようにする。

あたりを考えている。

ちょっと大見得を切った気がするが、1年もあればできるだろう（楽観）。

直近の進捗報告

前回の記事以降の進捗を報告する。

リテラルのオーバーロード

前回はユーザー（ライブラリー）定義のオーバーロードを書けるようにしたが、リテラルのオーバーロードがまだだった。今回、IntとWordのリテラルのオーバーロードを実装した。

オーバーロードを実装したい型に対しては、 fromInt : int -> t, fromWord : word -> t という関数を提供させる。int や word に収まる範囲の値にはこれを直接使い、int や word で表せない範囲の場合は + や * と組み合わせて目的の値を作る。

実数、文字、文字列リテラルのオーバーロードはまだ実装していない。

record extension / update (Successor ML)

多くのフィールドを持つレコードの、一部のフィールドだけを更新したいという状況が時々ある。Successor MLではそのための構文として

(* { <式> where <フィールド...> } *)
{ someRecord where x = 1, y = "foo" }

という構文 (record update) を提供している。

SML#にも独自拡張で someRecord # {x = 1, y = "foo"} という構文があるが、Successor MLのものはフィールドの型を変更できるのに対してSML#のrecord updateはフィールドの型を変更できないという違いがある。Successor MLのやつはrow polymorphism的だがSML#はそうではないのだ。

閑話休題。

LunarMLはSuccessor ML志向なので、Successor MLのrecord updateを実装したい。Successor MLのrecord updateはrecord extensionという機能のシンタックスシュガーとして規定されているので、record extensionを実装しなければならない。

record extensionというのは、「元々のレコードからいくつかのフィールドを取り除いたレコード」を作る手段 (record extension pattern) および「元々のレコードにいくつかの（元々存在しない）フィールドを追加したレコード」を構築する手段 (record extension expression) である。このほか、「既存のレコード型にいくつかのフィールドを追加したレコード型を作る」という機能もある。

case someRecord of
   { x, ... = rest } => (* rest には someRecord から x を取り除いたものが束縛される *)
val otherRecord = { z = 999, ... = someRecord } (* otherRecord には someRecord に z を追加したものが束縛される。ここで someRecord はフィールドとして z を持たない *)

SML/NJやMLtonはSuccessor MLの一部を実装しているが、record extensionは実装していない。record extensionを実装するのはHaMLet Sに続いてLunarMLが2例目となる。

Standard MLのrecord patternを型推論するためには

ある型変数（が表すレコード型）にはこういうフィールドが生えている

という制約を表現できれば十分だった。これに対し、record extensionを型推論するためには、

ある型変数（が表すレコード型）からこれこれのフィールドを取り除いたものがこの型変数（が表すレコード型）になる
この型変数（が表すレコード型）にこれこれのフィールドを追加したものがある型変数（が表すレコード型）となる

という制約を表現できる必要がある。

列多相 (row polymorphism) があればそれで良いが、LunarMLでは列変数を導入することはせずに、型変数に対する制約を2種類追加することでお茶を濁した。

「実装する」という行為は仕様の誤植・バグや他の実装のバグを洗い出すのに絶好の機会である。実際、

Successor MLのrecord updateの脱糖後のコードが間違っていたので報告した。
HaMLet Sが空のrecord update { someRecord where } を受け付けなかったので報告した。

Standard MLでは、式の評価順は「左から右へ」が原則である。record extensionの、 ... の右側にフィールドが来るやつは ... が右端にくる構文に対するderived formだが、そこでも「左から右へ」の原則が守られるようになっている。つまり、

val _ = { x = print "A", ... = (print "B"; { y = () }), z = print "C" };

というコードは ABC を出力する。

ところで、Successor MLのnested matchという機能を使うとパターンマッチの途中で副作用を起こすことができる。パターンに対するrecord extensionは順序を入れ替えるようになっているので、以下のコードはソース上の見かけとは裏腹に ACB を出力する：

case { x = 1, y = 2, z = 3 } of
    { x = (_ with () = print "A"), ... = ({ y } with () = print "B"), z = (_ with () = print "C") } => ();

賢いコンパイラーであれば「副作用付きのパターンの順序の入れ替えが起こる」場合に警告を発するという選択ができるかもしれないが、実装するのが大変そうな割に意義が薄い気がする。

andalso/orelseの文法

Standard MLでは a + case x of y => ... という形の式はコンパイルが通らない。つまり、二項演算子の右側に raise, fn, case, if, while 式を置くことはできない（そのせいでモナドっぽい >>= 演算子を定義しても x >>= (fn y => ...) という風に余計なカッコが要る）。

一方で、 andalso, orelse の右側には raise, case, if 式を置くことができる（fn と while は型が合わないという意味で置けない）。つまり、andalso と orelse は「優先順位が低めの二項演算子」ではなく、「構文レベルで他の二項演算子とは別物」なのだ。

Standard MLの式の文法を「パラメーター化された非終端記号」を含むBNF（ECMAScriptの仕様書で使われているもの）で書けば次のようになるだろう：

TypedExp ::= InfExp
           | TypedExp ':' Ty

AndalsoExp[Head, Match] ::= TypedExp
                          | TypedExp 'andalso' AndalsoExp[?Head, ?Match]
                  | [+Head] TypedExp 'andalso' HeadExp[?Match]

OrelseExp[Head, Match] ::= AndalsoExp[?Head, ?Match]
                         | AndalsoExp[~Head, ~Match] 'orelse' OrelseExp[?Head, ?Match]
                 | [+Head] AndalsoExp[~Head, ~Match] 'orelse' HeadExp[?Match]

(* 特定のトークンから始まる式 *)
HeadExp[Match] ::= 'raise' Exp[?Match]
                 | 'if' Exp[+Match] 'then' Exp[+Match] 'else' Exp[?Match]
                 | 'while' Exp[+Match] 'do' Exp[?Match]
        | [+Match] 'case' Exp[+Match] 'of' Match
        | [+Match] 'fn' Match

(* Exp[+Match] は末尾が Match であることを許容し、 Exp[~Match] は許容しない *)
Exp[Match] ::= OrelseExp[+Head, ?Match]
             | HeadExp[?Match]
    | [+Match] OrelseExp[~Head, ~Match] 'handle' Match

Match ::= Pat '=>' Exp[~Match] '|' Match
        | Pat '=>' Exp[+Match]

現状のLunarMLの文法はこれを通常のBNFで書き下した感じになっている。

なお、話はこれで終わりではなく、Successor MLで追加された注釈によると、 V andalso if W then X else Y orelse Z という形の式は、

(V andalso (if W then X else Y)) orelse Z  (* ifよりもorelseの方が優先順位が高いのでおかしい *)
V andalso (if W then X else (Y orelse Z))  (* orelseよりもandalsoの方が優先順位が高いのでおかしい *)
V andalso ((if W then X else Y) orelse Z)  (* orelseよりもandalsoの方が優先順位が高いのでおかしい *)

という感じで拒絶されなければならないらしい（先に載せた文法では真ん中の形にパースされる）。ヤンナルネ。LunarMLで実装するとしたら、パース後の処理で弾く感じにしたい。

sequenced type realisation (where type … and type …)

SML ’97では

structure S = struct
  type t = int
  type u = string
end : sig
        type t
        type u
      end where type t = int
            and type u = string
and T = struct
end;

というコードが書ける。後半の and type と and に注目して頂きたいのだが、where type t = int の後に and が来た段階ではsequenced type realisation (and type) なのかstructure binding (and T = struct) なのかわからないようになっている。先読みすれば簡単に判別できそうなものだが、ML-Yaccでこれをパースするには文法定義で泥臭いことをする必要がある。

この機能は where type で簡単に代替できるし、パーサーを複雑にするだけだということで、Successor MLではsequenced type realisationは廃止された。

LunarMLはSuccessor ML志向なので、sequenced type realisationはこれまで実装してこなかった。

……のだが、HaMLetのコンパイルを試した際にsequenced type realisationが使用されていることが判明した。どの口で「The syntax does not seem to be widely used either, it is hence abolished.」（HaMLet Sのマニュアルより）なんて言っとるんじゃ。

世の中で使用されているからには、LunarMLでも実装しなければならない。というわけで実装した。ヤンナルネ。

将来、「厳格にSuccessor ML準拠を目指すモード」を実装する際には、sequenced type realisationが使われていないことをチェックするようになるだろう。

直近の目標

今はHaMLet / HaMLet Sをコンパイルできるように、バグ修正とライブラリーの実装を行なっている。HaMLetは必要な外部ライブラリーを添付しているのと、ML-Lex/ML-Yaccのファイルも処理済みのものを添付しているので、標準ライブラリーを備えたStandard MLコンパイラーさえあればコンパイルできるはずなのだ。

record extensionを実装したことで本格的に「Successor ML実装」への道を踏み出したわけだが、Successor MLの大きな機能としては他にパターンマッチ周りのもの、特にnested matchがある。パターンマッチ実装の改良の目処をつけるまではSuccessor MLの実装を焦ることはしたくない。

Spread the love

雑記帳

人生やっていき