Mercury 勉強メモ

関数論理型言語 Mercury を勉強するブログです．

Mercury 入門 (1) Hello, World!

Mercury 入門

Mercuryは， 関数論理型言語(functional logic programming language)の一種で， 論理型言語のPrologに関数型言語の機能を追加して拡張したプログラム言語です．

関数型言語と論理型言語の機能を両方同時に扱えるなんて，なんてお得なんだ！！と 思って興味を持って勉強を始めてみたら，本当に面白かったのでブログの記事として まとめてみたいと思います．

処理系のインストール

Mercuryはオーストラリアのメルボルン大学の研究チームが開発した言語です． 処理系は彼らが作った mmc (Merborn Mercury Compiler) があります． まずは処理系のインストールから始めてみたいと思います． 以下は Ubuntu 13.04 の場合ですが，他の環境でも同様にインストールできると思います．

まず，flex と bison を apt-get を使ってインストールします．

$ sudo apt-get install flex bison

Mercury のダウンロードページから， mercury-srcdist-13.05.1.tar.gzをダウンロードします．

展開，configureスクリプトの実行，make，make installします．

$ tar zxvf mercury-srcdist-13.05.1.tar.gz
$ cd mercury-srcdist-13.05.1
$ ./configure
$ make PARALLEL=-j2
$ sudo make install PARALLEL=-j2

j2の2はPCが搭載しているコア数です． 私の環境 (CPU: Celeron 887, メモリ: 8G) では，make に8分，make install に2時間54分かかりました．非常に時間がかかるので， 週末などの時間のあるときにインストールしましょう．

述語

Mercury ではプログラムは述語の集合として記述します． 述語とは引数(あれば)に応じて真(true)であるか偽(fail)であるかが定まる論理式のことです． Mercury では述語を使って，アルゴリズムの入力と出力の関係を記述することでプログラムを表現します．

例えば，引数の整数Nに10を足すとMであるという述語は，

add10(N, M) :- M = N + 10.

と書きます．:- の左側が述語の名前と引数，右側が述語が真になるための条件で，ここでは，M = N + 10 が指定されています．

このような述語があると，例えば，

add10(5, 15).    % 15 = 5 + 10 は成り立つか?

は真(true)になり，

add10(5, 16).    % 16 = 5 + 10 は成り立つか?

は偽(fail)になります．

変数(大文字の英数字で表す)を含む式に対しては，Mercury はその式が成り立つ変数の値を求めようと試みます．

例えば，

add10(5, X).

に対して，Mercury は X = 15 と返し，

add10(X, 100).

に対しては，X = 90 と計算してくれます．

Mercury ではこのように，ひとつの述語を複数の用途に利用できます．上の add10 の例では，

  1. 2引数目が1引数目に10を足した数になっているかを判定する処理．
  2. 1引数目を与えて，2引数名を計算する処理．
  3. 2引数目を与えて，1引数目を逆計算する処理．

という3種類の処理を，単一の述語で表現できています．

このような仕組みを活用することで， Mercuryでは手続き型言語や関数型言語では思いもよらないような方法でプログラムを記述することが可能になります．

プログラムの構成

Mercury のプログラムは以下のような構成になっています． 括弧内はプログラムに応じて書き換わる部分です．

:- module (モジュール名).
:- interface.
(外部に公開する述語の宣言)
:- implementation.
(外部に公開しない述語の宣言と述語の実装)
:- end_module (モジュール名).

Mercury のソースファイルには拡張子.mを付け，モジュール名は拡張子を取り除いたファイル名と同じにします． また，最終行の:- end_module (モジュール名).は省略できます．

コメントは%から始まる単一行コメント

% コメント

と，/*から*/までの複数行コメント

/* 複数行コメント */

があります．

Hello, World!

では，プログラム言語入門の伝統と格式に則って，Hello, World!プログラムを 最初の例題として取り挙げます． 以下のプログラムは，画面にHello, World.と表示するプログラムです．

このプログラムでインターフェイス部は，

:- import_module io.
:- pred main(io::di, io::uo) is det.

の2行です．インターフェイス部では，import_module宣言で標準ライブラリの ioモジュールを読み込んでいます．また，pred宣言で述語mainを宣言しています．

述語mainの宣言では，mainは2引数の述語で， 最初の引数はio型でdiモード，2番目の引数はio型でuoモードであることを示しています．

io型は入出力の状態を保持する値の型で，ファイル入出力などの副作用のある計算の順序を 保持する目的で使います．

モードは引数の使われ方を示しています．例えば，

  • in(input)モード: 入力．このモードの変数は入力に使われ，述語を実行する前に値が定まっていなければならない．
  • out(output)モード: 出力．このモードの変数は出力に使われ，述語を実行する前に値が定まっていてはならない．
  • di(destructive input): 破壊的入力．このモードの変数は，述語内ででちょうど1度だけ使われなくてはならない．
  • uo(unique output): 唯一出力．述語実行後にこのモードの変数が保持している値は，プログラムの他の場所では出てこない．

などのモードをよく使います．

述語宣言の最後の det は述語の決定性の指定で，述語が返す値の数を示しています．例えば，

  • det(deterministic): 決定的．入力に対して，出力が1つ必ずもとまる．(1個の答を返す)
  • semidet(semideterministic): 準決定的．入力によっては失敗することもあるが，成功した場合は出力が一意に定まる．(0個以上1個以下の答を返す)
  • multi(mulisolution): 複解．入力によって複数の値が求まるが，失敗することはない．(1個以上の答を返す)
  • nondet(nondeterministic): 非決定的．入力によって複数の値が求まったり，失敗したりする．(0個以上の答を返す)

などの決定性をよく使います．

Mercury ではアリティ(引数の個数)が異なる述語は別の述語として扱われます． 述語を示すときは，名前にアリティを添えて，main/2のようによびます．

述語main/2の実装は以下のようになっています．

 main(IO1, IO2) :-
     write_string("Hello, World!\n", IO1, IO2).

変数IO1には，述語を実行する前のIO状態を表す値が入っており，IO2に述語実行後のIO状態を代入して返します． Mercury の入出力関数は必ずIO状態を受け取って，IO状態を返すように宣言・定義されています． ここでは標準ライブラリの述語write_string/3を使っています．

write_string/3はioモジュールで以下のように宣言されています．

:- pred io.write_string(string::in, io::di, io::uo) is det.

write_string/3は1引数目に文字列を入力として受け取り， 2引数目と3引数目でIO状態の受け渡しをすることがわかります．

上のプログラムではmain/2が受け取ったIO状態をそのまま渡し， write_string/3が返す新しいIO状態を返しています．

コンパイルと実行

上のプログラムがhello.mという名前で保存されているとします． Mercury ではモジュール名とファイル名を一致させないといけないので， ここでは必ずhello.mという名前である必要があります．

プログラムをコンパイル・実行するには，mmcコマンドを使います． 以下に実行例を示します．

$ mmc hello.m
$ ./hello
Hello, World!

コンパイルによってたくさんのファイルが生成されますが， その中にC言語のコードが含まれていると思います． Mercury では，C言語のコードを出力し， それをC言語のコンパイラでコンパイルすることで実行ファイルを作ります．

複数の入出力

以下の例では複数の入出力述語を呼んでいます．

実行結果

$ mmc hello2.m
$ ./hello2
Hello, Mercury World!

複数の入出力を行う場合は，このようにIO状態に別名を付けて受け渡すことで処理を続けます．

main/2の最初の引数のモードdiは，その値をちょうど一度しか使うことができないという意味で， そのことはMercuryのモードシステムによって保証されます． また，2番目の引数のモード uo は，その値が一箇所でしか使われていないという意味で， この条件を満たしているかどうかもモードシステムによってコンパイル時に検査されます．

Mercury の述語は，

Goal0 :- Goal1, Goal2, ..., Goaln.

のような形で表現します．Goal0のことを頭部(head)， Goal1, Goal2, ..., Goalnのことを体部(body)とよびます． Goal0やGoal1のことをゴール(goal)とよび，項が入ります．

項は，"hello"のような定数，IO1のような変数， write_string("Hello, ", IO1, IO2)のような複合項を書きます．

上の述語は，

Goal1 かつ Goal2 かつ ... かつ Goaln ならば Goal0 である

という論理式を表しています． Mercury は純粋(pure)な言語なので，体部に現れるゴールの順番に意味はありません．

つまり，

Goal0 :- Goal1, Goal2.

も

Goal0 :- Goal2, Goal1.

も同じ意味になります． この節のプログラムの3つの述語を

main(IO1, IO4) :-
  write_string("World!\n", IO3, IO4),
  write_string("Mercury ", IO2, IO3),
  write_string("Hello, ", IO1, IO2).

のように書き換えても，入れ替える前のものと同じ順番で出力されます．

状態変数構文

前節の例では，中間のIO状態に手で名前をつけていましたが，!.Xと!:Xという特殊な変数名を使うと， 以下のようにこの状態の受け渡しを自動化できます．

実行結果

$ mmc hello3.m
$ ./hello3
Hello, Mercury World!

さらに，!Xという変数名を使うと，!.Xと!:Xのペアを以下のようにまとめることができます．

実行結果

$ mmc hello4.m
$ ./hello4
Hello, Mercury World!

!IOで2引数分の状態受け渡しを表しいることに注意してください．