So-net無料ブログ作成
検索選択

CSV parsing for Standard ML [SML]

ありそうでなかった(と思う)、Standard ML用のCSV読み込みライブラリを作りました。

CSV parsing for Standard ML

単純な使い方テストケースを見るとすぐわかると思います。


Standard ML用の新しいXMLパーサー [SML]

Standard ML用のXMLパーサーを作った。

UXML

SMLの世界にはSMLで書かれたXMLパーサーが(知っている範囲では)すでに2つある。 1つはfxpという、かなり昔からあるもので、これはDTDの検証も行うフルセットのXML1.0準拠もの、 もう1つはSMLNJ-LIBの中にあるXMLストラクチャで、これはかなり非力なものだ。

UXMLは非検証のXMLプロセッサーとしてXML1.0になるべく準拠しようとしている。 現段階ではUTF-8しか受け入れない点と𐀀以上の文字を受け入れない点 (これはUXMLが依存しているSMLNJ-LIBのUTF8ストラクチャの制約)、 そしてXML1.0の整形条件違反のかなりの部分を報告しない(受け入れてしまう)点が 非準拠であるが、現実的な処理では十分に使える状態になっていると思う。

他の2つのXMLプロセッサーにない点として、 名前空間をサポートしている点と、XPathライクなナビゲーションAPIを持つ点がある。

使用するにはタグv.0.1.0を取得するか、Smackageから利用してほしい。 Smackageを使う場合、.smackage/sources.localにuxml git git://github.com/tkob/uxml.gitという行を追加し、SML/NJのCMファイルからは`$SMACKAGE/uxml/v0.1.0/uxml.cmのように参照する。


SMLZIP: Standard ML用のZIPファイル読み込みライブラリ [SML]

Standard MLからZIPファイルの読み込み・解凍をするためのライブラリを作った。

SMLZIP https://github.com/tkob/smlzip

特徴はPure-SMLである(Cバインディングではない)という点である。 機能は読み込みのみで、現状は最低限のことができる程度だ。 PKZIP形式から読み込みたい場合と、Deflate形式を直接扱いたい場合で 異なるMLB/CMを選択できるようになっている。 Smackage から利用できるようにするためのファイルも配置してみた。

バグ等をみつけたらGithubのissueに報告してほしい。


Proglrの最近の進展 [SML]

SML用のパーサジェネレータProglrの最近の進展について。

字句解析の自動生成

Proglrはml-ulexで生成された字句解析器と結合するようになっていて、 これまでは字句解析は自分で書く必要があった。

しかし、凝った字句解析をしない場合はやはり自動で生成してくれるのが便利だ。 というわけで文法定義からml-ulexのソースを自動生成する機能をつけた。

具体的にはtoken Add "+";のようなトークン定義があった場合は 指定された文字列のトークンを字句解析にも追加する。

token Integer of int;, token Double of real;, token Char of char;, token String of string;, token Ident of string; のような定義があった場合はそれぞれのリテラルのトークンを追加する。

これにより簡単な言語を作る場合はml-ulexのソースをまったく書かなくてもよくなる。

example/calc/calc.cfというサンプルがあるのでそれを参照してほしい。

コメント定義の自動生成

同様にコメントについても字句解析に自動追加できるようになった。 下記のような定義でそれぞれブロックコメントと行コメントを追加できる。 これはBNFCと同様である。

comment "/*" */";
comment "//";

各処理系のための雛形の自動生成

各ML処理系でビルドするためのドライバ、Makefileなども自動生成するようにした。 ml-lptランタイムが同梱されていない処理系のために、 ml-lptランタイムのソースも展開されるようにした。

これにより基本的には文法定義ファイルだけから実行可能ファイルを作るまでのすべてが生成可能となった。

MLton, Poly/ML, Alice ML, MLKit, Moscow ML では数行のコマンドラインでサンプルプロジェクトがビルドできるようになっている。 起動方法はREADMEを参照してほしい。

一方でProglr自身をビルドするための処理系としては、 当面MLtonとPoly/MLに注力することにした。 SML#向けのファイルも残っているが、動かないものと思ってほしい。

ちなみにAlice MLのビルドの作法を調べていたのだが、 リンクに関してはまだあまりわかっていない。 コンパイルをすると.alcというオブジェクトファイルができ、 これは依存する.alcがしかるべき位置に配置されていればそのまま実行できる。 依存するものも含めて1ファイルにするためにalicelinkを使う…と思っているのだが、 alicelinkを使ってリンクしたつもりのファイルだけで実行しようとすると やはり依存性のエラーが出てしまう。 このためREADMEではリンクせずに実行するような手順を書いている。

Graphvizファイルの生成

文法定義から作られるオートマトンを視覚化するためのdotファイルを生成できるようにした。 -a 出力ファイル名 というオプションを与えると生成できる。

依存するツール

Proglrが依存している外部ツールを挙げる。 基本的には昔ながらのUnixのツールであるため、 利用できないということはないと思う。

  • m4: ファイル生成時にテンプレート機能として使う
  • Perl: ml-ulexの出力結果にパッチを当てるのに使っている(Alice ML互換にするためのパッチ)
  • Expect: Poly/MLでビルドするときにインタラクティブシェルを制御するのに使う
  • DejaGnu: Proglrのテスト(make check)で使う

Mling: ML処理系のC言語インターフェイスを自動生成する [SML]

SMLの処理系のC言語インターフェイスをCのヘッダから自動生成するツールを作った。

Mling: ML FFI Interface Generator

現在のところMLtonとPoly/MLに対応していて、cursesを使うサンプルが動くようになっている。

先行するものとしてSML/NJとMLtonにはmlnlffigenというツールがあるようなのだけど、使い方がよくわからなかったのだ。 やりたいのはCの関数の型をMLの型に書き換える機械的な作業なので、いいや自分で作ろうということになった。

C言語の構文解析には紆余曲折の後libclangをPythonから使うことにした。 Ubuntupython-clang-3.3を導入した環境で動作を確認している。

一般的な構文解析ツールでC言語の構文解析をしようとするとtypedef問題などに突き当たってしまって、かなり面倒なことになる。 libclangは何と言ってもCコンパイラが使う真正のC言語パーサーだからそれを使えるのは理想的なはずだ。 でもlibclang自体の使い方もドキュメントが乏しくてよくわからないところが多い。 だから面倒くささということに関しては結局どっちもどっちかもしれない。


SML の long identifier のドットについて [SML]

Standard MLの文法について調べていて気付いたこと。

SMLでは Int.toString みたいなドットで区切られた識別子のことを long identifier というんだけど、これは The Definition of Standard ML では longx ::= x | strid1.・・・.stridn.x というBNFで定義している(2.4 Identifiers)。 また、2.5 Lexical analysis では "Each item of lexical analysis is ... or a long identifier." と書いていて、long identifier が(syntacticなカテゴリではなく)lexicalなitemであるとしている。

そうするとこのドットの前後にホワイトスペースは許容されるのかという疑問が生じてくる。 通常の lexical analysis ではホワイトスペースをトークン中に含まない。とはいえそういうことができないわけではない。 一方でプログラミング言語一般的にはドットの前後で改行できるのが普通だと思う。

各種のSML実装で比較してみると、なんと!許容しないほうが多数派だった。

  • 許容しない: MLton, MLKit, Poly/ML, Moscow ML, Hamlet
  • 許容する: SML/NJ, SML#, Alice ML

検証ソース

$ cat longvid-split.sml
val _ = print (Int
.toString (Array.
maxLen))

実行結果

$ mlton longvid-split.sml
Error: longvid-split.sml 2.1.
  Illegal token.
Error: longvid-split.sml 2.17.
  Illegal token.
Error: longvid-split.sml 1.16.
  Undefined variable Int.
Error: longvid-split.sml 2.2.
  Undefined variable toString.
Error: longvid-split.sml 2.12.
  Undefined variable Array.
Error: longvid-split.sml 3.1.
  Undefined variable maxLen.
compilation aborted: parseAndElaborate reported errors
$ mlkit longvid-split.sml
[reading source file:   longvid-split.sml]
longvid-split.sml, line 2, column 2:
  .toString (Array.
    ^
cannot lex "."
[[ERR in sub process:
  PARSE_ELAB_ERROR]]
Stopping compilation of MLB-file due to error (code 1).
$ polyc longvid-split.sml
Error- in 'longvid-split.sml', line 2.
unknown symbol .t
Error- in 'longvid-split.sml', line 2.
invalid identifer - Array.
Exception- Fail "Static Errors" raised
$ sml
Standard ML of New Jersey v110.76 [built: Tue Oct 22 14:04:11 2013]
- use "longvid-split.sml";
[opening longvid-split.sml]
[autoloading]
[library $SMLNJ-BASIS/basis.cm is stable]
[autoloading done]
16777215val it = () : unit
$ mosml -P full
Moscow ML version 2.10
Enter `quit();' to quit.
- use "longvid-split.sml";
[opening file "longvid-split.sml"]
File "longvid-split.sml", line 2, characters 0-1:
! .toString (Array.
! ^
! Lexical error: ill-formed token.
[closing file "longvid-split.sml"]
$ alice
Alice 1.4 ("Kraftwerk 'Equaliser' Album") mastered 2013/11/08
### loaded signature from x-alice:/lib/system/Print
### loaded signature from x-alice:/lib/tools/Inspector
### loaded signature from x-alice:/lib/distribution/Remote
- use "longvid-split.sml";
val it : unit = ()
### evaluating file /home/ether/longvid-split.sml
16777199-
SML# 2.0.0 (2014-04-04 11:47:08 JST) for i686-unknown-linux-gnu with LLVM 3.4
# use "longvid-split.sml";
8388607#
$ ./hamlet
HaMLet 2.0.0 - To Be Or Not To Be Standard ML
[loading standard basis library]
- use "longvid-split.sml";
val it = () : unit
[processing /home/ether/longvid-split.sml]
../longvid-split.sml:2.0-2.1: invalid character `.'

ちなみにこの実験中に MLKit では Array.maxLen が 123456789 と定義されていることにも気づいてしまった。たぶん嘘だと思う。

$ cat longvid.sml
val _ = print (Int.toString (Array.maxLen))
$ mlkit longvid.sml
[wrote X86 code file:   MLB/RI_GC/base-link_objects.s]
[wrote executable file: run]
$ ./run
123456789

Proglr: SML用のGLRパーサージェネレーター [SML]

ちまちま作っていたSML用のパーサージェネレーターが結構形になってきたので紹介します。

https://github.com/tkob/proglr

先日の記事ではML-BNFCという名前で、パーサーはLR(0)の状態だった。当初のもくろみとしては一度SLR(1)にした後でBermudez and Logothetisの方法なるものを使ってLALR(1)にするということを考えていたんだけど、面倒に思えてきたのと、そのわりに得られる結果がLALR(1)で独自性がない気がしたので結局GLRにした。 そうするとこのパーサージェネレーターの独自性はどちらかというとGLRになるのでML-BNFCという名前もやめてML-GLRという名前にした。[追記参照] いまでは文法定義ファイルからSMLソースを生成するようになっていて、文法定義ファイルの解析自体もML-GLR自身が生成したものになっている。

[追記]: ML-GLRっていう名前のパーサージェネレーターが既にあった!http://www.cis.uni-muenchen.de/~leiss/relationaleGrammatik-09-10/ml-glr.pdf

ということでさらに名称変更してProglrという名前にした。 [追記終わり]

ビルド

git clone --recursive https://github.com/tkob/proglr
cd proglr
make -f Makefile.mlton

パターンマッチに関する警告がたくさん出ますが無視してください。 proglrという実行ファイルができます。 なお、MLtonのほかに一応MLKitとPoly/MLでもビルドできるようになっています。[追記]SML#2.0.0でもコンパイルできるようになりました。

使用例

文法定義は次のように書く。BNFCにおおむね似ている。

token Add "+" ;
token Sub "-" ;
token Mul "*" ;
token Div "/" ;
token LParen "(" ;
token RParen ")" ;
token Integer of int;

EAdd. Exp ::= Exp "+" Exp1 ;
_.    Exp ::= Exp1 ;
ESub. Exp ::= Exp "-" Exp1 ;
EMul. Exp1 ::= Exp1 "*" Exp2 ;
EDiv. Exp1 ::= Exp1 "/" Exp2 ;
_.    Exp1 ::= Exp2 ;
EInt. Exp2 ::= Integer ;
_.    Exp2 ::= "(" Exp ")" ;

この文法定義からは次のようなAST型が生成される。

  structure Ast = struct
    datatype exp =
      EAdd of Lex.span * exp * exp
    | ESub of Lex.span * exp * exp
    | EMul of Lex.span * exp * exp
    | EDiv of Lex.span * exp * exp
    | EInt of Lex.span * int
  end

スキャナーの定義はml-ulexを使う。

%defs (
  open Token
  type lex_result = Token.token
  val eof = fn () => Token.EOF
);

%name Lexer;

%let digit = [0-9];
%let space = [ \t\r\n];

<INITIAL> "+" => (Add);
<INITIAL> "-" => (Sub);
<INITIAL> "*" => (Mul);
<INITIAL> "/" => (Div);
<INITIAL> "(" => (LParen);
<INITIAL> ")" => (RParen);
<INITIAL> {digit}+ => (Integer (Option.valOf (Int.fromString (yytext))));
<INITIAL> {space}+ => (continue ());

ドライバとなるプログラムは次のような感じで書く。

structure Parse = ParseFun(Lexer)

open Parse.Ast

fun calc (EAdd (_, e1, e2)) = (calc e1) + (calc e2)
  | calc (ESub (_, e1, e2)) = (calc e1) - (calc e2)
  | calc (EMul  (_, e1, e2)) = (calc e1) * (calc e2)
  | calc (EDiv  (_, e1, e2)) = Int.div (calc e1, calc e2)
  | calc (EInt (_, e)) = e

fun main () =
  let
    val strm = Lexer.streamifyInstream TextIO.stdIn
    val sourcemap = AntlrStreamPos.mkSourcemap ()
    val ast = Parse.parse sourcemap strm
    val result = calc (hd ast)
  in
    print (Int.toString result);
    print "\n"
  end

val _ = main ()

ビルドするときはランタイムとしてsmlnj-libとmllpt-libをリンクする。

(* calc.mlb *)
$(SML_LIB)/basis/basis.mlb
$(SML_LIB)/smlnj-lib/smlnj-lib.mlb
$(SML_LIB)/mllpt-lib/mllpt-lib.mlb

calc-parse.sml
scan.ulex.sml
calc.sml

スキャナーとパーサーを生成するためのMakefile

mlglr: calc-parse.sml scan.ulex.sml
        mlton -output calc calc.mlb

calc-parse.sml: calc.cf
        proglr < calc.cf > calc-parse.sml

scan.ulex.sml: scan.ulex
        ml-ulex scan.ulex

clean:
        rm -f calc calc-parse.sml scan.ulex.sml

実行例

$ ./calc
(1 - 2) + 3 * 4 + 5
16

SML用のLRパーサージェネレーターを作る [SML]

SMLのためのLRパーサージェネレーターを新しく自分で作っている。 まだ限定的なことしかできないしコードが汚い部分も残っているのだけど、公開された場所に置くことがモチベーションになるかもしれないと思ってGithubにアップロードした。

ML-BNFC: BNF Converter for Standard ML

SML処理系のためのパーサージェネレーターは各SML処理系に付属している場合が多いから、 新しくパーサージェネレーターを作るということ―車輪の再発明―を正当化するのはなかなか難しい。 私の場合は、自分で好きなように手を入れられるものが欲しいと思った、という程度ものだ。 でも新しく作るからには既存のものと少しは違う。 とりあえず作るにあたっての方針と、今後の目標を次に記そうと思う。

方針

  • ml-ulexと組み合わせて使える

SML/NJには歴史のあるml-yacc/ml-lexに加えて、ml-lptという言語処理系作成向けのツール群がある。 ml-ulexはml-lptに付属するスキャナージェネレーターである。 これはml-lexに比べると非常に進化していて、どうしてもこれを使いたかった。 もちろんml-lptを使えば使えるのだが、基本的にはml-antlrというLL(k)のパーサージェネレーターと組み合わせるしかなかった。

  • 構文木のデータ型を自動生成する

パーサージェネレーターには普通セマンティックアクションを付与した文法定義を与え、そのセマンティックアクションの中で構文木の生成を行うという形をとることが多い。 多いというか、パーサージェネレーターを使う殆どのケースでまずは構文木を作ると思う。 だとしたらパーサージェネレーターが構文木のデータ型も構文木を構築するコードも自動生成してくれればいい。 以前紹介したBNFCがそのような機能を提供していてとても便利だと思っていたのでそれを取り入れた。 また、ツールの名前もそこからとってML-BNFCとした。

生成されるコードはできるだけ多くのSML処理系で動くようにする。

現状

現時点でコミットしてあるコードはブートストラップしていなくて、文法定義はSMLのデータとして直接与えて一緒にコンパイルするしかない。 ビルドするとmlbnfcというバイナリができ、ファイル名を与えて実行するとパーサーおよび構文木のデータ型のコードを出力する。 このコードはml-ulexで書いたスキャナーを組み合わせて使えるようになっていて、パースすると構文木が作られる。

今後の目標

  • 文法定義を外部ファイルから読み込むようにする
  • 雛形となるようなドライバのコードも自動生成するようにしたい
  • 現在LR(0)の文法しかサポートされていない。いずれLALR(1)まで持っていきたい
  • コードをきれいにする

[追記] この記事の続きはこちら http://rainyday.blog.so-net.ne.jp/2014-06-18


SML処理系で利用可能なSML Basis Libraryを一覧化する [SML]

各SML処理系がSML Basis Libraryをどこまでサポートしているかを比較してみたいことがある。 自分だけかもしれないが、そういう一覧が必要だと思ったので作ることにした。

とはいえ数多いモジュールとそれに属する関数や定数をいちいち手作業で確かめるのは大変なのでスクリプトを書いた。

https://gist.github.com/tkob/11498077

スクリプトに関する覚書

まず、manpages.rbが http://www.standardml.org/Basis/manpages.html から個別のモジュールの解説ページのURLを取得してmanpages.txtに保存する。

次にgethtml.shがwgetを使って個別解説ページをダウンロードし、 module.rbがそれらのページからstructureとそれに属する値を抽出する。 ここでInt{N}とかWord{N}のようなstructureは16,31,32,63,64の値で展開することにした。 (ただし一部の処理系ではもっと細かく用意されている場合がある) この結果がval.txtに保存される。これは「Array.length」のような名前が1行1つの形式である。

こうして得られた名前が処理系でサポートされているかを確認するには、 REPLのある処理系ならばREPLに打ち込んで評価させればよい。 これをそのまま行うためExpectを使ってREPLを制御することにした。 check.tclがそれを行う。 check.tclは処理系ごとに実行し、smlnj.txt, poly.txtなどの名前で結果が保存される。

compare.rbが処理系ごとの結果を列として読み込んで横に並べ変える。(この種の処理をしたくなることは多いのだけどいつもコードをたくさん書いている気がする。何かいい方法はないのだろうか) 最後にperlのワンライナーでMarkdown形式に変換する。

こうして得られたのが次の結果である。

結果

https://gist.github.com/tkob/11498120

MLtonやMLKitのようなREPLのない処理系はいまのところ未対応である。 やるとしたらautoconf系のツールで行われているように短いプログラムをコンパイルさせてコンパイルが通るかどうかを見る方法になるだろう。

またこれは64bit版のUbuntuで得られた結果だが、32bit環境などではInt{N}などのサポート状況は変化するだろう。


SMLのためのMessagePack実装 - ML-MessagePack [SML]

SML用のMessagePack実装を作りました。

https://github.com/tkob/mlmsgpack

対応するSML処理系としてはMLton, MLKit, Poly/ML, SML/NJ, Moscow ML, HaMLet, Alice ML, SML#です。これらすべてでコンパイルが通るようにしてありますが、テストケースが無傷で通るのは最初の3つだけで、他は処理系側で機能に制限があったりバグがあったりします。特にSML#は大半のテストが通りません。

[2014/4/5追記] SML#1.2.0ではテストが通りませんでしたがSML#2.0.0では通るようになりましたので、SML#を使う場合は2.0.0以上をお使いください。

* 使い方

扱いたいデータ型に対するpacker/unpackerを基本的なコンビネーターを組み合わせて作ります。こんな感じです。

> val outs = BytesIO.mkOutstream ();
val outs = ref Nil : BytesIO.bytes_list ref
> doPack (packList (packPair (packInt, packBool))) [(1, true),  (2, false)] outs;
val it = () : unit
> BytesIO.toBytes outs;
val it = fromList[0wx92, 0wx92, 0wx1, 0wxC3, 0wx92, 0wx2, 0wxC2]
: Word8Vector.vector
> doUnpack (unpackList (unpackPair (unpackInt, unpackBool))) (BytesIO.fromBytes it);
val it = ([(1, true), (2, false)], fromList[])
: (int * bool) list * BytesIO.instream


詳しくは同梱のTUTORIAL.mdを参照してください。

* 開発の経緯

別のSMLプロジェクトで、データをマーシャルして流すようにしたいとおもい、フォーマットとしてはMessagePackに目を付けました。

SML向けのMessagePack実装としてはMsgPack-SML https://msgpacksml.codeplex.com/ というものがすでに存在することが分かったのですが、少し使ってみたところこれは事実上MLton専用で、移植も簡単にはいかないということがわかったので、結局自分で作ることにしました。

移植性というのをコンセプトの1つにしたので各種処理系でテストしながら作っていたのですが途中からSML処理系自体に対するテストみたいになってしまった。

あといざ実装してみるとMessagePackの仕様自体にも多少不満があって、もうちょっと明示的に書いてほしいところが足りてなくて迷うときがあった。これについては時間があれば別の機会に書きたい。

この広告は前回の更新から一定期間経過したブログに表示されています。更新すると自動で解除されます。