■

コメントで教えてもらって、PrologのコードをCurryのコードにどう変換すればいいのか大体分かった気がする。密かに出来なかった述語版append

append :: [a]->[a]->[a]->Success
append [] x y = (x=:=y)
append (x:xs) y (z:zs) = (x=:=z) & (append xs y zs)

app x y = head $ findall (\r->append x y r)
main = putStrLn $ app "Hello, " "world!"

(Eq a)=>という指定が要らないという。型とか無名関数のおかげで、Prologより多少分かりやすくなるんでないかな〜。

非決定性オートマトン via http://bach.istc.kobe-u.ac.jp/prolog/intro/lang.html

data State = State String deriving Show
data Input = Input Char deriving Show

delta :: State -> Input -> State -> Success
delta (State "q0") (Input 'a') (State "q1") = success
delta (State "q1") (Input 'a') (State "q1") = success
delta (State "q1") (Input 'a') (State "q2") = success
delta (State "q1") (Input 'b') (State "q1") = success
delta (State "q2") (Input 'b') (State "q3") = success

ndfa :: String -> Success
ndfa ls = ndfa_aux (State "q0") (map Input ls) (State "q3")
where
 ndfa_aux q0 [] q1 = (q0=:=q1)
 ndfa_aux q0 (a:as) q = (delta q0 a q1) & (ndfa_aux q1 as q) where q1 free

論理変数の必要性が理解できた。

Curry割と楽しいので、パズルとか練習用コードではなく、何か書いてみたいけど、関数的に書くならHaskellでいいので、論理型な側面を活かせるお題が欲しい。関数的に書くより、論理型のスタイルで書いた方が自然なアルゴリズムって何だろう。英語版WikipediaのPrologの項には、PrologはAIと自然言語処理に向いているとあるけど、私はどっちもよく分からんし。computer algebraで何かいい例がありそうな気もするが、Wikipediaの末尾に載ってるような例は、むしろ関数的に書いた方が自然な感じだし、他にいい例も思いつかない。あと思いつくのは定理証明器。こないだのRoy Dyckhoffのdecision procedureをCurryで書いてみるかな〜。あと型推論とかか(なんとなく、論理型の方がいいのではないかと推測)

で、Curryの意味論。Curryのサブセットに過ぎないHaskell(暴言)の意味論がないのに、Curryの(というか、FLPLの)意味論は割と確立されているという不思議。
・Monadic Semantics for Core Curry
・Operational Semantics for Functional Logic Languages
まあ、読めば分かるので、特にどうということもなく。

Monadic Semanticsに基づく"Core Curry"のためのインタープリタが
http://web.cecs.pdx.edu/~apt/curry-monads/
にある。動かしてないけど。論理変数も非決定性も、narrowingもない、Interpreter for call-by-need functional languageというのがあるけど、それってHaskellじゃん

ところで、Natural Semanticsみたいなやり方で、意味論を与えると、半自動的に、ナイーブなインタープリタが生成できる(と思う)んだけど、これは構文木をたどる、ナイーブ過ぎるアレなので、実用には供さない。で、実際の処理系は、VMのバイトコードなり、ネイティブコードなりに変換されるわけだけど、その変換が正しいことを証明しようとしたら、VMなり実機なりの形式的な記述が必要になるけど、意味論みたく、そういうのの記述形式って、なんか確立されたもんがあんのかね、というのが、ふと気になった。まあ、なさそうだが(HDLとかは、いくらなんでも低レベルすぎると思う)。あと、わざわざ言語ごとにVM作るっていうのは、言語ごとに、適したVMの構造が違うからなはずで、そうすると、言語に適したVMを半機械的に導出する方法があるべきなんでないかと。しかし、VMとかの設計ってどうやるんだろうな〜っていうのが、さっぱり検討がつかないのだった。やっぱ、そのへんは、設計者の勘と経験という、ad hocなやり方しかないんだろうか。まあ、そのうち調べるかもしれない