関数型論理プログラミング言語Mercuryのチュートリアルを読む

http://www.icfpcontest.org/rules.htmlにある言語のうち、ひときわマイナーで目立ってました。

関数型論理言語にはCurryもありますがCurryがHaskellに論理プログラミング機能が追加された感じであるのに対し、MercuryはPrologから進化させた感じに見えます(main的な意味で)。

コンパイラによってC環境だけでなく、.NET、Java、Erlangを実行環境につかえるなど、面白い構造になっています。

Hello World

:- module hello.
:- interface.
:- import module io.
:- pred main(io::di, io::uo) is det.
:- implementation.

main(IOState_in, IOState_out) :-
  io.write_string("Hello, World!\n", IOState_in, IOState_out).

pred main(...) is detのis detは決定的(入出力の組が決定的)という意味です。
ioが型で、後ろが属性とのこと。io::diはdestrutive input,io::uoはunique outputだそうです。

出力が連続する場合、

main(IOState_in, IOState_out) :-
  io.write_string("Hello, ", IOState_in, IOState_tmp1),
  io.write_string("World!", IOState_tmp1, IOState_tmp2),
  io.nl(IOState_tmp2, IOState_out).

と、前のoutを次のinにいれることでつなげています。このIO数珠繋ぎ引数は!でまとめて書くこともできます

main(!IO) :-
  io.write_string("Hello, ", !IO),
  io.write_string("World!", !IO),
  io.nl(!IO).

di、uoの役目はCleanのuniqueness typingとそっくりで、!はそれをさらにまとめたような感じです。

フィボナッチ

predicateで記述する方法と、関数で記述する方法が載ってます。

述語版:

:- module fib.
:- interface.
:- import module io.
:- pred main(io::di, io::uo) is det.

:- implementation.
:- import module int.
:- pred fib(int::in, int::out) is det.

fib(N, X) :-
( if N =< 2
  then X = 1
  else fib(N - 1, A), fib(N - 2, B), X = A + B
).

main(!IO) :-
fib(17, X),
  io.write_string("fib(17, ", !IO),
  io.write_int(X, !IO),
  io.write_string(")\n", !IO).

関数版:

:- module fib.
:- interface.
:- import module io.
:- pred main(io::di, io::uo) is det.

:- implementation.
:- import module int.
:- func fib(int) = int.
fib(N) = X :-
( if N =< 2
  then X = 1
  else X = fib(N - 1) + fib(N - 2)
).

main(!IO) :-
  io.write_string("fib(17) = ", !IO),
  io.write_int(fib(17), !IO),
  io.nl(!IO).

関数は以下のようにも書けるようです

fib(N) = ( if N =< 2 then 1 else fib(N - 1) + fib(N - 2) ).

if-then-elseでも使えてるので、predicateはPropを返す関数という扱いなのだろう。

インプット

11ページ

:- import module list, string.

main(!IO) :-
  io.read_line_as_string(Result, !IO),
  ( if
      Result = ok(String),
      string.to_int(string.strip(String), N)
    then
      io.format("fib(%d) = %d\n", [i(N), i(fib(N))], !IO)
    else
      io.format("That’s not a number...\n", [], !IO)
  ).
Result = ok(String),

はResultがok("...")だとStringが"..."になるパターンマッチングになってます。任意に構造パターンが使えるのはPrologっぽい。

io.format("fib(%d) = %d\n", [i(N), i(fib(N))], !IO)

同様に第二引数のリスト中のi(N)はformat中で整数扱いできるようにするデータ構造ですね。

ifの条件部分はpredicateなのでif-then-elseでは、成功すればthen、失敗すればelseが行われます。

main(!IO) :-
  io.read_line_as_string(Result, !IO),
  ( if
      Result = eof
    then
      io.format("bye bye...\n", [], !IO)
    else if
      Result = ok(String),
      string.to_int(string.strip(String), N)
    then
      io.format("fib(%d) = %d\n", [i(N), i(fib(N))], !IO),
      main(!IO)
    else
      io.format("I didn't expect that...\n", [], !IO)
  ).

のように、thenやelse中もpredicateである場合は、;で並行記述のように書けます

main(!IO) :-
  io.read_line_as_string(Result, !IO),
  (
    Result = eof,
    io.format("bye bye...\n", [], !IO)
  ;
    Result = ok(String),
    ( if string.to int(string.strip(String), N)
      then io.format("fib(%d) = %d\n", [i(N), i(fib(N))], !IO)
      else io.format("that isn't a number\n", [], !IO)
    ),
    main(!IO)
  ;
    Result = error(ErrorCode),
    io.format("%s\n", [s(io.error message(ErrorCode))], !IO)
  ).

つまり、,がand、;がorのようなかんじです。

型

type宣言するようです。パラメトリックなTree型の例

:- type tree(T) ---> leaf ; branch(tree(T), T, tree(T)).

レコード例

:- type playing_card ---> card(card_rank :: rank, card_suit :: suit) ; joker.
:- type employee ---> employee(id :: int, contact :: contact_details).
:- type contact_details ---> contact_details(address :: string, phone :: int).

フィールドアクセス

Card^card_rank = B.
card(A, _, _)^card_rank = A.
(card(_, B, C)^card_rank := A) = card(A, B, C).

関数型

:- func map(func(T1) = T2, list(T1)) = list(T2).
map(_, []) = [].
map(F, [X | Xs]) = [F(X) | map(F, Xs)].

predicate型

:- pred filter(pred(T), list(T), list(T), list(T) ).
:- mode filter(in(pred(in) is semidet), in, out, out ) is det.
filter(_, [], [], []).
filter(P, [X | Xs], Ys, Zs) :-
  filter(P, Xs, Ys0, Zs0),
  ( if P(X) then Ys = [X | Ys0], Zs = Zs0
    else Ys = Ys0, Zs = [X | Zs0]
  ).

もしくは、

:- pred filter( pred(T)::in(pred(in) is semidet),
                list(T)::in, list(T)::out, list(T)::out) is det.

det,semidet,nondetは入力に対する解の数が違う

  • det: 1
  • semidet: 1, 0
  • multi: >=1
  • nondet: >= 0
  • failure: 0

感想

関数型で推論が使えるなんてプログラミングコンテストには最強の言語じゃないかな。