日々の流転

λ. 関数論理型言語Curryを試してみる

Haskellでパーサを書く時に面倒な点 で書いたようなこともあり、最近、関数論理型言語に興味がわいている。色々な人が試しているので、私も試してみる事に。処理系は他の人が試しているZincではなく、Münster Curry Compilerを選んでみた。Zincは最新版1.02のリリースが2004-12-07で、あまりメンテナンスされていなそうだったので。

choose

インストールして早速 <URL:http://d.hatena.ne.jp/m-a-o/20070205#p2> に書いてあった chooseを試してみたのだが……

-- Choose.curry
choose x y = x
choose x y = y

% cyi Choose.curry
    _____ __ __
   / ___/ |  / _               Muenster Curry Compiler
  / /     | / | |              Version 0.9.10, Copyright (c) 1998-2006
 / /___  / /  | |
 \____/ /_/   |_|              Type :h for help

> let x = choose 0 1 in x - x
[Compiling ...]
0 | 0
> choose 0 1 - choose 0 1
[Compiling ...]
0 | -1 | 1 | 0

……これはやっぱりキモイよ。 後者で「-1」や「1」が答えに含まれるということはchooseは関数になっていないということだし、参照透明でもないということじゃん。

が、実行メカニズム的には仕方ないんだろうな。 オーバーラップしたパターンを禁止するならともかく、オーバーラップしたパターンを許す場合に関数的に振る舞うように実装するのは現実的でない(もしくは不可能)だと思う。

パターンマッチで単一化は起らない?

> let x free in if x then x else x
[Compiling ...]
Suspended
> let x free in case x of True -> x; False -> x
[Compiling ...]
Suspended

「True | False」が結果になるとばかり思っていたので、意外だった。

しかし、以下のように関数を介した形にしたところ、Suspendedにならなくなった。

ifte :: Bool -> a -> a -> a
ifte True x _  = x
ifte False _ y = y

> let x free in ifte x x x
[Compiling ...]
{x = True} True | {x = False} False

関数引数におけるパターンマッチとcase式でのパターンマッチとでは振る舞いが違うのね……。これは何故こうなっているのだろう?

非決定性

上では「実行メカニズム的に仕方ないんだろうな」と書いたが、標準ライブラリに Success.choose :: [a] -> a やら Combinatorial.permute :: [a] -> [a] みたいなのがあるのを見ると、非決定的・非関数的な振る舞いを積極的に利用するのがCurryのスタイルのようだ。やっぱり関数型言語よりも論理型言語っぽいな。

パーサー

<URL:http://web.sfc.keio.ac.jp/~mukai/2006-langsem/06-dcg-feature.pl>を真似てみる。

import Parser

data Person = First | Second | Third
data Number = Singular | Plural

s =
  let person free
      number free
  in n person number <*> v person number

n :: Person -> Number -> Parser String
n First Singular = terminal "I"
n First Plural   = terminal "we"
n Second _       = terminal "you"
n Third Singular = terminal "he"
n Third Singular = terminal "she"
n Third Singular = terminal "it"
n Third Plural   = terminal "they"

v :: Person -> Number -> Parser String
v First  _ = terminal "run"
v Second _ = terminal "run"
v Third Singular = terminal "runs"
v Third Plural   = terminal "run"

> s ["he", "runs"]
[Compiling ...]
[]
> s ["he", "run"]
[Compiling ...]
No solution