例によって翻訳です。Erlang for Python Programmersという英文記事の翻訳です。
Pythonを使っている人が関数型言語の考え方を学ぶのによい記事になってます。
Pythonはコードが分かりやすいので，Pythonistaだけでなく，RubyやPerl，PHPそしてJavaのような命令型言語を使っている人にとっても有益な記事だと思います:-)。
初めに
ここ数年，Erlangへの注目が高まっている。Erlangのプログラミングモデルはプロセス間でメッセージをやりとりするだけで実行する並行プロセスに根ざしている。それぞれのプロセスはとてもシンプルな関数型言語で作られ，PythonやRuby，Javaといった命令型の言語とは異なった考え方を要求する。
このプロジェクトでは，PythonとErlangで書いた簡単な例題をとりあげ，関数型言語の手法を見てゆく。MLやHaskellといった他の関数型言語と同様，Erlangはプログラムの構成要素がとても限られてる言語だ。いくつかの制限を設けるとこで，Pythonでも同様のプログラムを書くことができる。そうすることによって，Pythonの知識を使ってErlangや関数型言語を理解できるはずだ。
このプロジェクトの2番目のパートでは，Erlangの同時実行性とメッセージ・パッシングの受け渡し機能について見てゆく。論理回路を例に取り，簡単なNandゲートを使って複合論理ゲートを作る。Pythonではそれぞれのゲートはインスタンスになりますが，Erlangでは別々の並行プロセスになる。メッセージ・パッシングで回路をつなぐ。
3番目のパートでは，高階関数のようなより洗練された関数型言語のテクニックを見てゆく(2番目，3番目のパートは未訳)。
コードはそれぞれ次のリンクに(Python, Erlang)ある。
繰り返しを再帰で置き換える
階乗を計算する簡単な関数をwhileループを使って書いてみよう。
def factorialOld(n) :
ans = 1
while n > 1 :
ans = ans * n
n = n - 1
return ans
>>> import samples
>>> samples.factorialOld(5)
120
Erlangではこのような手法は使わない。Erlangではwhileやforといった命令を使った繰り返しは実行できない。加えて，変数は一度値を代入したら変更出来ない(単一代入)。
そこで，階乗を計算する関数を再帰を使って書き換えてみよう。
def factorial(n) :
if n == 0 : return 1
else : return n * factorial(n-1)
>>> import samples
>>> samples.factorial(5)
120
nには複数の値が代入されていると思う方がいるかも知れない。実際，再帰のそれぞれのレベルで異なった値を取っている。しかし，nは再帰のそれぞれのレベルで異なった変数として扱われる。新しいレベルに入るたび，新しい変数が割り当てられるというわけだ。それぞれのレベルで見ると，単一代入は守られているということになる。
しかし，なぜこのようなことをしなければならないのだろう？
変数の束縛(「変数」よりも正確な言い方)を変更できない，ということは，再帰の各レベルにおいて，変数の関係は変化せず，消えたりしない，ということを意味する。こうすると処理が簡単になるし，エラーも少なくなる。多くの潜在的なエラーは，他の変数といろいろなタイミングで相互に作用する変数によって引き起こされる。変数が他の変数と関連を持つタイミングを考慮すると，プログラムはとても複雑になる。構造化プログラミング以前の忌まわしきGOTOを多用したスパゲッティコードでは，プログラムを変更すると新しいバグが埋め込まれる，ということがよく起こった。
変数を不変にしてしまえば，再帰でループを使わないようにしても問題にはならない。なぜなら，変数の値を変更したり，変数の関連性を変えるためにループが必要となるからだ。
では次に，階乗を計算する関数をErlangで書いてみよう。
factorial(0) -> 1;
factorial(N) -> N * factorial(N-1).
パターンマッチングになれていない人にとっては，このコードは奇妙に見えるかも知れない。Pythonで書いた階乗を計算する関数のコードでは，if/elseを使って2つのケースを分けていた。パターンマッチングを使うと，この場合分けが関数の外で行われる。関数を呼び出すときに渡される引数がゼロの場合，1が戻り値として返される。それ以外の場合は，変数Nが引数に束縛され，N * factorial(N-1)を評価した結果が戻り値として返される。この仕組みはPython版のコードと同じだ。
次に，Erlang版のコードをテストしてみよう。
chris@ubuntu:~/projects/erlang$ erl
Erlang (BEAM) emulator version 5.6.3
Eshell V5.6.3 (abort with ^G)
1> c(samples).
{ok,samples}
2> samples:factorial(20).
2432902008176640000
1行目の"c(samples)."では"samples.erl"をコンパイルして，問題があった場合にはエラーメッセージを表示する。Pythonのimport文と同じだ。2行目ではsampleモジュールの"factorial"関数を実行している。":"はモジュール名と関数名の区切り文字として使われていることに注意してほしい。Pythonでは代わりに"."が使われる。また，文の最後は"."で終わっていることにも注意してほしい。
Erlangの基本的な文法
覚えることはそう多くない。慣れてさえしまえば，Erlangは驚くほどシンプルな言語だ。以下に挙げる項目は完璧ではないが，このプロジェクトで学ぶことには十分なはずだ。
"->" は条件を組み立てる。Pythonでは，この記号の位置に常に ":" を書く。
"." は文の最後に書く。文は，";"で区切られた1つか複数の節から構成される。入力のパターンにマッチした最初の節が，文では選ばれる。
節の中には，","で区切られた複数の式が記述される。節は順番に評価される。文の中で最後に評価された値が，呼び出し元に戻り値として返される。
Erlangの変数は英大文字で始める。分かりやすいように，Pythonのプログラムと同じ変数名を使っている。
英小文字で始まる単語はErlangでは単語自体をあらわすシンボルとなる。このような場合，Pythonでは普通文字列を利用する。パート2まで使わない。
再帰を観測する
Pythonで書いた階乗を計算する関数を，挙動が確認できるように変更してみよう。Python版とErlang版を容易に比較できるよう，Pythonの変数名を大文字から始まるようにしてみる。
def factorialD(N) :
print "Entering", N
if N == 0 : Ans = 1
else : Ans = N * factorialD(N-1)
print "Returning", N, Ans
return Ans
>>> import samples
>>> samples.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)
>>> import samples
>>> samples.factorial2(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デフォルト値を持っているので，最初の呼び出し時には値を省略しても，自動的に適切な初期値が設定されるようになっている。
関数内の全ての節において再帰から戻る課程で演算が行われないことを，Erlangのコンパイラ(Pythonではない)が見つけたとする。コンパイラは呼び出しにスタックを積まず，代わりに以前のスタックを再利用する。このことには2つの大きな利点がある。一つには何回も戻り値を扱うのではなく一つの戻り値を扱えばいいので効率がよいし，再帰が無限に起こってもスタックを食いつぶすことがない。そして，無限再帰こそErlangで無限ループを実現する唯一の方法なのだ。
次に，Erlangで末尾再帰を使ったfactorial関数の例を示す。
factorial2(N) -> factorial2(N,1).
factorial2(0,ACC) -> ACC;
factorial2(N,ACC) -> factorial2(N-1, ACC*N).
2つの関数定義があって，それぞれピリオドで終わっていることに注意して欲しい。最初の関数は1つだけ引数を取り，外部から呼び出される。2つの引数がある関数の定義部分では，計算の途中結果を次の再帰呼び出しに渡して，最終的に戻り値とする。2つめ関数があることで，末尾再帰が実現する。ACCと名前の付いた変数は，Python版の関数でも同じように扱っていたことを思い出して欲しい。次に実行結果を示す。
6> c(samples).
{ok,samples}
7> samples:factorial2(6).
720
リストの処理
6> c(samples).
{ok,samples}
7> samples:factorial2(6).
720
Erlangのインタラクティブシェルで，次のようなコードを実行してみた。
Eshell V5.6.3 (abort with ^G)
1> A = [1,2,3,4].
[1,2,3,4]
2> [H|T] = A.
[1,2,3,4]
3> H.
1
4> T.
[2,3,4]
ErlangのリストはPythonのリストとそっくりに見える。1行目では変数Aが[1, 2, 3, 4]というリストに束縛される。2行目では，「=」が単なる割り当てを行う演算子ではないことが見て取れる。実際には，「=」は値を束縛されていない変数に割り当てて左辺と右辺を統合しようとしている。この例では，束縛されていないHという変数には"1"というリストの先頭の値が割り当てられ，Tにはその後が割り当てられる。パイプ文字列"|"は特別な意味を持っている。Pythonと同じように，Erlangでもコンマ(,)はリストの要素を分けるために使われるが，"|"はリストの最初の要素と残りを分けるために使われる。
Erlangでは，"|"はリストの右側に要素を連結するためにも使われる。例を示す。
2> [4 | [5,6,7]].
[4,5,6,7]
ここでは，まずリストの先頭となる値とリストを記述して，"|"演算子を間において1つのリストを作っている。
Pythonには"|"のような演算子は存在しないが，同じような処理をすることは可能だ。
"[H|T] = L" というErlangのコードは，Pythonでは"H=L[0]; T=L[1:]"となる。
Erlangの"L = [H|T]"は，Pythonでは"L = [H]+T"になる。
PythonでもErlangでも，リストを連結することができる。Pythonでは"+"演算子を使う。Erlangでは"++"という演算子を使う。
Pythonでリストを連結するときには以下のようにする。
>>> [1, 2, 3] + [5, 6, 7] [1, 2, 3, 5, 6, 7]
>>>
Erlangではこうだ。
Eshell V5.6.3 (abort with ^G)
1> [1,2,3] ++ [6,7,8].
[1,2,3,6,7,8]
2>
次に，リストを使った例を見てみよう。数値リストの総計を取ってみる。Pythonで書いた2つの例を示す。二つ目の例は末尾再帰を使っている。
def sum(L) :
if not L : return 0
else : return L[0] + sum(L[1:])
def suma(L, Acc=0) :
if not L : return Acc
else : return suma(L[1:], Acc+L[0])
試してみよう。
>>> import samples
>>> samples.sum([1,2,3,4,5])
15
>>> samples.suma([1,2,3,4,5])
15
>>>
Erlang版も基本的には同じだ。
sum([]) -> 0;
sum([H|T]) -> H + sum(T).
suma(L) -> suma(L,0).
suma([],Acc) -> Acc;
suma([H|T],Acc) -> suma(T, Acc+H).
Erlangのシェルで実行してみよう。
Eshell V5.6.3 (abort with ^G)
1> c(samples.erl).
{ok,samples}
2> samples:sum([1,2,3,4,5,6]).
21 3> samples:suma([1,2,3,4,5,6]).
21
4>
PythonとErlangでクイックソート
最後に，よく知られたクイックソートのアルゴリズムをPythonとErlangで見てみよう。
クイックソートはシンプルな再帰を使う美しいアルゴリズムだ。クイックソートは，要素のリストからランダムに選ばれた要素を元に，要素は2つのリストに分けられている。リストを選択する要素のことをピボットと呼ぶ。ピボットより大きな要素が最初のリストに分けられ，他の要素はもう一方のリストに分けられる。ピボットと同じ値の要素があれば，どちらか一方のリストに分けられる。
Python版の，再帰だけを使ったsplit関数を示す。
def split(P, L, A=[], B=[]) :
if not L : return [A,B]
H = L[0] # H and T assigned only once
T = L[1:]
if H <= P : return split(P, T, [H]+A, B )
else : return split(P, T, A, [H]+B)
このコードは，ここに示したコードの中でも一番トリッキーなコードだ。深呼吸をしてからコードを読んで欲しい。通常はwhileループを使って実行することを，再帰を使って置き換えている。個々の再帰呼び出しが直前の呼び出しで実行されており，ソートするリストの先頭を2つのリストのどちらかに割り当てている。出力用のリストは再帰を通して持ち歩かれるので，すべてが末尾最適化を使って実行される。
早速実行してみよう。
>>> samples.split(5,[1,2,3,4,5,6,7,8,9])
[[5, 4, 3, 2, 1], [9, 8, 7, 6]]
>>>
リストを分割する関数を作ってしまえば，ソートは難しくない。リストと，再帰呼び出しされるサブリストをソートするには，リストの先頭をピボットとして利用し，リストの後ろを二番目のリストとして分割し，それぞれをソートして最終的に全部をPythonのリスト連結機能を使ってまとめればよい。次にコードを示す。
def sort(L) :
if not L : return []
H = L[0] # H and T assigned only once
T = L[1:]
[A,B] = split(H,T)
print "Pivot %s: %s --> %s %s" % (H,T,A,B)
return sort(A) + [H] + sort(B)
関数をもう少し面白く見せるために，分割の課程を表示するようにしてみた。ピボット，入力されたリストと出力するリストを表示するようになっている。
>>> samples.sort([5,4,3,6,7,8,4,3])
Pivot 5: [4, 3, 6, 7, 8, 4, 3] --> [3, 4, 3, 4] [8, 7, 6]
Pivot 3: [4, 3, 4] --> [3] [4, 4]
Pivot 3: [] --> [] []
Pivot 4: [4] --> [4] []
Pivot 4: [] --> [] []
Pivot 8: [7, 6] --> [6, 7] []
Pivot 6: [7] --> [] [7]
Pivot 7: [] --> [] []
[3, 3, 4, 4, 5, 6, 7, 8]
>>>
最後に，Erlang版のコードを見てみよう。
split(P,L) -> split(P,L,[],[]).
split(_,[],A,B) -> [A,B];
split(P,[H|T],A,B) when H =< P -> split(P,T,[H|A], B);
split(P,[H|T],A,B) -> split(P,T, A,[H|B]).
sort( [] ) -> [];
sort([H|T]) ->
[A,B] = split(H,T),
io:format("Pivot ~p: ~p ~p ~p~n",[H,T,A,B]),
sort(A) ++ [H] ++ sort(B).
実行結果は以下。
Eshell V5.6.3 (abort with ^G)
1> samples:sort([5,4,3,6,7,8,4,3]).
Pivot 5: [4,3,6,7,8,4,3] [3,4,3,4] [8,7,6]
Pivot 3: [4,3,4] [3] [4,4]
Pivot 3: [] [] []
Pivot 4: [4] [4] []
Pivot 4: [] [] []
Pivot 8: [7,6] [6,7] []
Pivot 6: [7] [] [7]
Pivot 7: [] [] []
[3,3,4,4,5,6,7,8]
2>
最後に
もちろん，Erlangを使えばここで示した以上のことができる。しかし，私の経験から言って，この独特のプログラミングスタイルに慣れることが関数型プログラミングに必要なことなのだ。もし関数型プログラミングをよく知らないのなら，たとえば"+"や"++"という演算子を使うことなく2つのリストをzipしたり，連結するプログラムを書いてみるといいと思う。プログラムを作る課程で沢山の間違いを犯すかも知れないが，学びの課程では「間違えること」は常に必要なことなのだ。幸運を，そして楽しみましょう。
