アルゴリズムの擬似コードと関数型言語

アルゴリズムの擬似コードを書く際は、いわゆる手続き型のスタイルで書くことが多いかと思います。つまり、更新可能な変数とループを使います。

一方、私がよく書くのは関数型言語で、これは更新可能な変数やループの代わりに末尾呼び出しを使用します。

では、アルゴリズムを提示してそれを関数型言語で実装する、というスタイルの文章を書く場合、アルゴリズムの擬似コードはどう書けばいいのでしょうか？

（ここでは、アルゴリズムの停止性、計算量、不変条件の明示等の観点から擬似コードの方が有益であり、関数型のコードだけを書けば良いというものではない、という立場を取ります。）

例えば、階乗を計算するプログラムを考えます。手続き的な擬似コードで書けば次のようになるでしょう：

fun fact(n):
    acc := 1
    for i = n to 1 step -1:
        assert acc = n * (n - 1) * ... * (i + 1)
        acc := i * acc
    return acc

ここではforループ（繰り返しの回数が最初から明示されたループ）を使っています。assertは不変条件の明示で、もっぱら人間用のコメントです。変数accはループの中で更新されています。

一方で、関数型言語で同等のコードを書くと次のようになるでしょう：

(* Standard ML *)
fun fact n
  = let fun loop {i, acc} = if i = 0 then
                                acc
                            else
                                loop {i = i - 1, acc = i * acc}
    in loop {i = n, acc = 1}
    end
-- Haskell
fact :: Integer -> Integer
fact n = loop n 1
  where
    loop i acc = if i == 0 then
                     acc
                 else
                     loop (i - 1) (i * acc)

関数型言語では、変数の更新も繰り返しも末尾呼び出しで実現することが特徴です。

ここで提示した擬似コードと関数型コードの溝をどうやったら埋められるか？というのがこの記事で考えたいことです。

擬似コードを関数型に寄せる

関数型言語のゴールは動かすのが難しいので、まずは擬似コードを関数型に近づけることにします。

まず、for文の同等物は関数型にはなさそうなので、for文を解体してwhile文にします：

fun fact(n):
    acc := 1
    i := n
    while i != 0:
        assert acc = n * (n - 1) * ... * (i + 1)
        acc := i * acc
        i := i - 1
    return acc

次に、while文をさらに解体して引数付きgotoにしてみます：

fun fact(n):
    goto loop(i := n, acc := 1)
    loop(i, acc):
        assert acc = n * (n - 1) * ... * (i + 1)
        if i == 0:
            return acc
        else:
            goto loop(i := i - 1, acc := i * acc)

あるいは、「goto」の代わりに別のキーワードを使ってみても良いかもしれません：

fun fact(n):
    enter loop(i := n, acc := 1)
    loop(i, acc):
        assert acc = n * (n - 1) * ... * (i + 1)
        if i == 0:
            return acc
        else:
            continue loop(i := i - 1, acc := i * acc)

ループの初期値の書き方を変えてもいいかもしれません：

fun fact(n):
    loop(i := n, acc := 1):
        assert acc = n * (n - 1) * ... * (i + 1)
        if i == 0:
            return acc
        else:
            continue loop(i := i - 1, acc := i * acc)

いずれにせよ、引数付きgotoは実質末尾呼び出しなので、関数型のコードと素直に対応します。

私が気になっているのは、「引数付きgoto」を使ったコードはアルゴリズムの擬似コードとして提示しても不自然ではないか？という点です。

手続き型に寄せた関数型言語は作れるか

逆に、関数型言語でありながら手続き型のアルゴリズムに寄せた書き方ができる言語は作れるか、というのも気になります。いくつかポイントとして、

  • ループの役割をする関数定義を呼び出しの後に書けると良いのか。
    • Haskellのwhereみたいなやつがあると良いのではないか
  • 複数の変数の更新を複数行で書けると良いのか。
  • 手続き型のfor文のような、「ループの実行回数・範囲が最初から明示された書き方」があると良いのか。配列の走査であればfoldだが、数の範囲のループにもそういう高階関数があると良いのか。
    • Haskellだと [0..n-1] みたいな等差数列が使えるのでそれで十分かも

などが考えられます。

特に結論はありません。「階乗」という例も単純すぎるかもしれません。伝わったかどうかはともかくとして、私が考えている問題意識の言語化でした。

Spread the love