PythonプログラマのためのMochi入門

# 元ネタはPythonプログラマのためのErlang入門Erlang for Python Programmersの翻訳

MochiPythonとよく似た構文の「Python上で動作する」、動的型付けの関数型言語だ。

この文章では、PythonとMochiで書いた階乗を計算する関数をとりあげ、関数型言語の手法を見てゆく。MLやHaskellといった他の関数型言語と同様、Mochiはプログラムの構成要素がとても限られてる言語だ。いくつかの制限を設けることで、Pythonでも同様のプログラムを書ける。そうすることによって、Pythonの知識を使ってMochiや関数型言語を理解できるだろう。

なお、この文章に登場するPythonコードは、Python3で書かれている。

繰り返しを再帰で置き換える

階乗を計算する簡単な関数をwhileループを使って書いてみよう。

def factorialOld(n):
    ans = 1
    while n > 1:
        ans = ans * n
        n   = n - 1
    return ans

factorialOld(5)
# => 120

Mochiではこのような手法を用いない。Mochiではwhileやforといった命令を使った繰り返しは実行できない。加えて、変数は一度値を代入したら変更出来ない(単一代入)。

そこで、階乗を計算する関数を再帰を使って書き換えてみよう。

def factorial(n):
    if n == 0: return 1
    else     : return n * factorial(n - 1)

factorial(5)
# => 120

nには複数の値が代入されていると思う方がいるかも知れない。実際、再帰のそれぞれのレベルでは異なった値を取っている。しかし、nは再帰のそれぞれのレベルで異なった変数として扱われる。新しいレベルに入るたび、新しい変数が割り当てられるというわけだ。それぞれのレベルで見ると、単一代入は守られているということになる。

なぜこのようなことをするのだろうか?

変数の束縛(「変数」よりも正確な言い方)を変更できない、ということは、再帰の各レベルにおいて、変数の関係は変化せず、消えたりしない、ということを意味する。こうすると処理が簡単になるし、エラーも少なくなる。多くの潜在的なエラーは、他の変数といろいろなタイミングで相互に作用する変数によって引き起こされる。変数が他の変数と関連を持つタイミングを考慮すると、プログラムはとても複雑になる。構造化プログラミング以前の忌まわしきGOTOを多用したスパゲッティコードでは、プログラムを変更すると新しいバグが埋め込まれる、ということがよく起こった。

変数を不変にしてしまえば、再帰でループを使わないようにしても問題にはならない。なぜなら、変数の値を変更したり、変数の関連性を変えるためにループが必要となるからだ。

では次に、階乗を計算する関数をMochiで書いてみよう。

def factorial:
   0: 1
   n: n * factorial(n - 1)

factorial(5)
# => 120

パターンマッチングになれていない人にとっては、このコードは奇妙に見えるかも知れない。関数を呼び出すときに渡される引数がゼロの場合、1が戻り値として返される。それ以外の場合は、変数nが引数に束縛され、n * factorial(n - 1)を評価した結果が戻り値として返される。この仕組みはPython版のコードと同じだ。

再帰を観測する

Pythonで書いた階乗を計算する関数を、挙動が確認できるように変更してみよう。

def factorialD(n):
    print("Entering", n)
    if n == 0: ans = 1
    else     : ans = n * factorialD(n - 1)
    print("Returning", n, ans)
    return ans

factorialD(5)
# -> Entering 5
# -> Entering 4
# -> Entering 3
# -> Entering 2
# -> Entering 1
# -> Entering 0
# -> Returning 0 1
# -> Returning 1 1
# -> Returning 2 2
# -> Returning 3 6
# -> Returning 4 24
# -> Returning 5 120
# => 120

再帰の「うさぎの穴」を次々に潜っていって、ついには底にたどり着き、戻る過程で計算を行っていることが分かる。

アキュムレータと末尾再帰

さて、次に別の方法を使って階乗を計算する関数を作ってみよう。関数の挙動を追えるように、関数の中にprintを仕込んでみる。

def factorial2(n, acc=1):
    print("Entering with", n, acc)
    if n == 0: return acc
    else     : return factorial2(n - 1, acc * n)

factorial(5)
# -> Entering with 5 1
# -> Entering with 4 5
# -> Entering with 3 20
# -> Entering with 2 60
# -> Entering with 1 120
# -> Entering with 0 120
# => 120

今度は、階乗の計算は、accという変数を使って部分的な計算結果を運びながら、再帰の穴を降りてゆく過程で実行される。最終的な結果は単に再帰のネストされた戻り値に送られてゆくだけだ。引数はaccデフォルト値を持っているので、最初の呼び出し時には値を省略しても、自動的に適切な初期値が設定されるようになっている。

関数内の全ての節において再帰から戻る過程で演算が行われないことを、Mochiコンパイラ(Pythonではない)が見つけたとする。コンパイラは呼び出しにスタックを積まず、代わりに以前のスタックを再利用する。このことには2つの大きな利点がある。一つには何回も戻り値を扱うのではなく一つの戻り値を扱えばいいので効率がよいし、再帰が無限に起こってもスタックを食いつぶすことがない。そして、無限再帰こそMochiで無限ループを実現する唯一の方法なのだ。

次に、Mochiで末尾再帰を使ったfactorial関数の例を示す。

def factorial2:
    n: factorial2(n, 1)
    0, acc: acc
    n, acc: factorial2(n - 1, acc * n)

factorial2(6)
# => 720

最初のパターンは1つだけ引数を取り、外部から呼び出される。2つの引数があるパターンでは、計算の途中結果を次の再帰呼び出しに渡して、最終的に戻り値とする。このパターンがあることで、末尾再帰が実現する。accと名前の付いた変数は、Python版の関数でも同じように扱っていたことを思い出して欲しい。

最後に

もちろん、Mochiを使えばここで示した以上のことができる。もし関数型プログラミングをよく知らないのなら、たとえば"+"演算子を使うことなく2つのリストをzipしたり、連結するプログラムを書いてみるといいと思う。プログラムを作る過程で沢山の間違いを犯すかも知れないが、学びの過程では「間違えること」は常に必要だ。幸運を、そして楽しみましょう。

# 元ネタ作者への連絡方法が不明であるため、許可はとっていません。内容がほぼ元ネタのままなので、問題があるかもしれません。問題があれば、公開を停止します。