Curryで関数論理型言語を体験してみた

これは「[ドワンゴ Advent Calendar 2019](https://qiita.com/advent-calendar/2019/dwango)」の18日目の記事です。

# Curry とは

[Curry](https://www-ps.informatik.uni-kiel.de/currywiki/) はプログラミング言語の一種で、関数型言語の機能と論理型言語の機能を合体させた言語です。言語仕様が [The Curry Report](https://www-ps.informatik.uni-kiel.de/currywiki/documentation/report) で定義されていて、それをもとにいくつかの実装が存在します。

- [Curryの実装一覧](https://www-ps.informatik.uni-kiel.de/currywiki/implementations/overview)

今回は Curry の実装の一つである [PAKCS](https://www.informatik.uni-kiel.de/~pakcs/) を触ってみました。PAKCSはHaskellで実装されていて、入力されたコードをPrologのコードに変換して実行しているらしいです。バックエンドのPrologの処理系として、SICStus Prolog (有償)もしくはSWI Prolog (フリー)を利用できます。私自身は Curry の名前は以前から知っていたのですが、これまできちんと触ったことはありませんでした。たまには日頃使う言語とは全く違う言語も触ってみたいというモチベーションで今回は挑戦してみます。

# PAKCS のセットアップ

PAKCS は Ubuntu であれば以下のコマンドで簡単にインストールできます。

```
$ sudo apt install pakcs
```

できるのですが、この方法でインストールすると、Curry のパッケージマネージャである `cypm` が動かないことがあり([参考](https://www.informatik.uni-kiel.de/~curry/listarchive/1330.html))、公式サイトのバイナリをインストールするほうがトラブルが少ないです。Linuxであれば `pakcs-2.2.0-src.tar.gz` を展開して `make` を実行するとインストールが終わります。PAKCSはMacでも動くらしいのですが、入れ方がよくわかりませんでした。うまくいったら追記します。今回は以下の環境で試しています。

- OpenSUSE Leap 15.1 x86_64
- SICStus 4.5.1 (体験版)
- PAKCS 2.2.0

# インタラクティブ環境

インストールして `bin` ディレクトリにパスを通して以下のようにインタラクティブ環境を起動します。

```
$ pakcs
  ______      __       _    _    ______   _______     
 |  __  |    /  \     | |  / /  |  ____| |  _____|   Portland Aachen Kiel
 | |  | |   / /\ \    | |_/ /   | |      | |_____    Curry System
 | |__| |  / /__\ \   |  _  |   | |      |_____  |   
 |  ____| / ______ \  | | \ \   | |____   _____| |   Version 2.2.0
 |_|     /_/      \_\ |_|  \_\  |______| |_______|   
 ***WITH TYPECLASSES***

Curry2Prolog(sicstus 4.5) Compiler Environment (Version of 2019-10-30)
(RWTH Aachen, CAU Kiel, Portland State University)

Type ":h" for help (contact: pakcs@curry-lang.org)
Prelude> 
```

式を入力すると計算ができます。

```
Prelude> 1 + 2 * 3 + 4
11
```

終了するには `:q` を入力します。

```
Prelude> :q
```

# ファイルの読み込み

Curry の構文は Haskell とそっくりです。例えば階乗を計算する関数の定義は以下のようになります。

```
fact :: Int -> Int
fact n
  | n == 0 = 1
  | otherwise = n * fact (n - 1)
```

上の内容が `fact.curry` という名前で保存されているとき、インタラクティブ環境上で `:l` コマンドを利用すると読み込むことができます。

```
Prelude> :l fact
[1 of 2] Skipping  Prelude          ( /home/naoki/repos/pakcs-2.2.0/lib/Prelude.curry, /home/naoki/repos/pakcs-2.2.0/lib/.curry/Prelude.fcy )
[2 of 2] Skipping  fact             ( fact.curry, .curry/fact.fcy )
fact> fact 5
120
```

# パッケージマネージャ

PAKCS には Curry の[パッケージマネージャー](https://www-ps.informatik.uni-kiel.de/currywiki/tools/cpm)が付属します。パッケージのリストを取得するために以下のコマンドを実行します。

```
$ cypm update
```

以下はコマンドの `runcurry` をインストールする例です。

```
$ cypm install runcurry
```

`runcurry` は curry のソースファイルを直接実行するコマンドです。例えば以下のプログラムが `hello.curry` という名前で保存されているとき、

```
main :: IO ()
main = putStrLn "hello, world."
``` 

以下のように実行します。

```
$ runcurry hello.curry 
hello, world.
```

ライブラリをインストールする場合は、 install ではなくて add を利用します。以下のコマンドはパッケージの `gui` をインストールします。

```
$ cypm add gui
```

# PAKCS を利用する上で参考になる資料

PAKCS の使い方ですが、最初に読む資料としては以下のチュートリアルが分かりやすいです。

- [Curry A Tutorial Introduction](https://www-ps.informatik.uni-kiel.de/currywiki/documentation/tutorial)

上を読んだあとは以下の資料を拾い読みしました。

- [PAKCS 2.2.0 The Portland Aachen Kiel Curry System User Manual](https://www.informatik.uni-kiel.de/~pakcs/Manual.pdf)
- [Curry An Integrated Functional Logic Language Version 0.9.0](https://www-ps.informatik.uni-kiel.de/currywiki/documentation/report)
- [PAKCS: System Libraries](https://www.informatik.uni-kiel.de/~pakcs/lib/)

具体的なプログラム例が以下にまとまっているので参考になります。

- [Curry: Example Programs](https://www.informatik.uni-kiel.de/~curry/examples/)

# PAKCSでいろいろ試してみた

整数リストの各要素の値を2倍する関数はPAKCSでは再帰を使って以下のように書きます。

```
doubleList :: [Int] -> [Int]
doubleList [] = []
doubleList (x : xs) = x * 2 : doubleList xs
```

1行目は型の宣言です。`doubleList` が整数のリストを受け取って整数のリストを返す関数であることを宣言しています。型宣言はなくても自動で推論されますが、トップレベルの宣言には型を書くことが推奨されているようです。リストは、空リスト `[]` の場合とコンスの場合 `x : xs` があります。パターンマッチで分岐して `=` の右側にそれぞれの場合の式を書くと定義が完成します。

```
double> doubleList [1..5]
[2,4,6,8,10]
```

`[1..5]`は`[1,2,3,4,5]`を生成する式です。実行すると期待通り動くことが確認できます。

2つのリストを連結する関数 `append` は次のようになります。任意の型のリストに適用できる多相関数になっています。

```
append :: [a] -> [a] -> [a]
append [] ys = ys
append (x:xs) ys = x : append xs ys
```

期待通り実行できます。

```
append> append [1,2,3] [4,5,6]
[1,2,3,4,5,6]
```

Haskell同様文字列は文字のリスト `[Char]` になっているので文字列も連結できます。

```
append> append "hello" "world"
"helloworld"
```

`append` は自分で定義しなくても `++` という演算子で予め定義されています。

```
append> [1,2,3] ++ [4,5,6]
[1,2,3,4,5,6]
append> "hello" ++ "world"
"helloworld"
```

ここまでの例は Haskell でも同じことができるので、特に目新しさはありません。しかし、以下の例は Haskell では書けない定義になります。

```
last :: [a] -> a
last (_ ++ [x]) = x
```

`last` はリストの最後の要素を取得する関数です。`++` は再帰的に定義された関数ですが、パターンマッチの場所に書くことができます。この機能は Curry の機能ではなく PAKCS の拡張ですが、極めて簡潔に定義できています。

```
last> last [1,2,3,4,5]
5
last> last "hello"
'o'
```

拡張を利用せずに書くには、以下のように関数のガードで制約を記述します。右辺に自由変数がある場合は、明示する必要があります。

```
last :: [a] -> a
last xs | _ ++ [v] =:= xs = v where v free
```

期待通り動きます。`++`は先程自分で定義した `append` に置き換えても動きます。

```
last :: [a] -> a
last (append _ [x]) = x
```

以下のような定義もできます。

```
middle :: [a] -> [a]
middle (x ++ y ++ x) | length x > 0 = y
```

例えば以下のように使います

```
middle> middle "abc123abc"
"123"
```

関数 `middle` は入力によっては複数値を返すことがあります。

```
middle> middle "aba123aba"
"ba123ab"
"123"
```

この例では `x` が `a` の場合と `aba` の場合が出力されています。PAKCSでは複数の値を返す関数（非決定的な関数）をそのまま扱えます。以下の関数は値をリストの中に挿入する関数です。

```
insert :: a -> [a] -> [a]
insert v xs = v : xs
insert v (x : xs) = x : insert v xs
```

実行すると以下のようにすべてのパターンを返します。

```
insert> insert 'x' "12345"
"12345x"
"1234x5"
"123x45"
"12x345"
"1x2345"
"x12345"
```

この `insert` を利用してリストの順列を返す関数 `perm` を定義できます。

```
perm :: [a] -> [a]
perm [] = []
perm (x : xs) = insert x (perm xs)
```

実行すると次のようになります。

```
perm> perm [1,2,3]
[3,2,1]
[3,1,2]
[2,3,1]
[2,1,3]
[1,3,2]
[1,2,3]
```

非決定的な結果をリストに変換するには、いろいろ方法があるようですが、例えば`searchtree` の `allValues` を利用できます。

- [Control.Findall](https://www.informatik.uni-kiel.de/~curry/cpm/DOC/searchtree-1.0.0/Control.Findall.html#allSolutions)

```
permList :: [a] -> [[a]]
permList = allValues . perm
```

`.` は関数合成の演算子です。上の関数は以下のように結果を返します。

```
perm> permList [1,2,3]
[[3,2,1],[3,1,2],[2,3,1],[2,1,3],[1,3,2],[1,2,3]]
```

# おわりに

とりあえずまだまだ機能はたくさんあるようですが、PAKCSの様子はつかめてきました。PAKCSを触ってみて、論理型の機能を活用したプログラムを書くのはなかなか難しいと感じました。以下は文字列の先頭から数字の列を取り出す関数です。

```
readInt :: String -> String
readInt (str ++ rest)
    | all isDigit str & all (not . isDigit) rest = str
```

この関数はPAKCSの機能を使って制約で書いているのですが、以下のように高階関数を使って書いたほうがバックトラックも起きず、効率的なコードになり、さらに可読性も高いように感じます。

```
readInt :: String -> String
readInt = takeWhile isDigit
```

PAKCSは遅延評価で、リスト周りの操作もとても充実しているので、どういうときに論理型のスタイルで書くのが良いのか、まだ掴みきれていません。まだ機能を把握したばかりの段階なので、今後いくつかまとまったプログラムを書いてみれば見えてくるのだろうなと思っています。実際に業務でPAKCSを使うことはなさそうですが、たまには考え方の違う言語を触るのは大切だなと思いを新たにしました。