何度か言ってるけどPythonは末尾再帰最適化、と言う素敵な機能を欠いている。
末尾再帰最適化(tail call optimization、略してTCO)、とは、平たく言うと、コンパイラ、ないしはインタプリタが、シンプルな末尾再帰を見つけた時に、アセンブリないしは仮想マシンのバイトコードレベルでジャンプ構文へと自動変換する機能である。
言い換えると、シンプルな末尾再帰はループ構文へと自動変換が可能だ、と言う事だ。
人間コンパイラになってみようか。
前回、我々は次のようなシンプルな末尾再帰によるフィボナッチ数列のコードを手に入れた。
def fibs(n, acc = [0, 1]):
if n < 2:
return acc if len(acc) > 2 else acc[:n+1]
else:
return fibs(n - 1, acc[:2] + [sum(i) for i in zip(acc[:-1], acc[1:])])
見た目スッキリさせる為にちょっと三項演算子っぽい書き方を導入したが、ロジックは全く変わらない。
ところで、末尾再帰だと関数本体で計算する代わりに引数内で計算するのが特徴だ、と言う話を書いた。
多分これを聞いた人は「引数内で計算出来るの?」って初めはビックリすると思う。
上のコードだとこの部分だな。
acc[:2] + [sum(i) for i in zip(acc[:-1], acc[1:])]
でも何故にビックリするか、と言うと関数本体内で変数として計算しないでも引数内で計算出来る、と言う事実にピンと来ないからだ。
しかし、と言う事は、この部分は関数本体内に戻して変数として計算させても結果構わん、と言う事になる。
このロジックが末尾再帰をwhileループに変換する際のポイントとなるのだ。
結果、上のフィボナッチ数列の末尾再帰コードは以下のようなwhileループにすぐさま変換が可能である。
def fibs(n, acc = [0, 1]):
while True:
if n < 2:
return acc if len(acc) > 2 else acc[:n+1]
else:
acc = acc[:2] + [sum(i) for i in zip(acc[:-1], acc[1:])]
n -= 1
殆ど末尾再帰のコードと内容が違わない事が分かるだろうか。基本構造はそのまんまである。
違いは
- 末尾再帰での本体全体がwhile True: で包まれている。
- return fibs(n - 1, acc[:2] + [sum(i) for i in zip(acc[:-1], acc[1:])])内の引数が取り出され、独立した変数としての作業となっている。
これだけである。これだけでシンプルな末尾再帰は機械的にwhileループへと変換出来るのだ。
機械的に、である。ここ重要。
人間が機械的に変換出来る以上、コンパイラもこれを機械的に変換が出来る、と言うのを言外に言われてるのだ。
もっと言っちゃおうか?
whileはシンプルな末尾再帰のシンタックスシュガー(※1)なのだ。少なくともwhileに慣れてる人にとっては、である。
逆に言うとwhileを使いこなしてる人にとっては末尾再帰はフツーの再帰に比べると難しくない。ハナクソなのである。何故なら形式が違うだけで計算ロジック自体は両者とも全く同じだからだ。
例えば、whileを使ったフィボナッチ数列の単純な実装に次のようなモノがある。
def fib(n, a = 0, b = 1):
while True:
if n == 0:
return a
else:
a, b = b, a + b
n -= 1
つまり、これを書ける人はすぐさま同じロジックの末尾再帰版を書き下す事が出来るのだ。
def fib(n, a = 0, b = 1):
if n == 0:
return a
else:
return fib(n - 1, b, a + b)
気を付けるのはカウンターの役目を果たしてるnの位置関係くらいなモンだ。末尾再帰版だと第一引数になってるのにwhile版ではループの最後に来ている。
ところで、末尾再帰とwhileの等価性、なんて話は聞いた事がない人が多いかもしれない。それどころか、C言語しか学んだ事が無い人だと末尾再帰、なんて言い回しさえ知らないケースもある。
つまりこれらから次の二つの事が言えるのだ。
- 再帰は難しい、と言われてただそれだけを信じてる人が多い、と言う事実。
- プログラミングには理論的に考えるのが大事、って言ってる反面、理論的に考える以前に実際は「考える」事自体を放棄してる人間の方が多い、と言う事実。
1. は前にも言った事がある。再帰と言うのは高校数学で習う漸化式の事である。従って最低でも高校を修了した者にとっては再帰は難しくないのだ。
「再帰が難しい」と言ってる人間は再帰が高校で習った漸化式だ、と言う事に気づいてないので、結果「何も考えていない」と言う事になる。
要するにプログラミングを行ってる者の殆どは「理論的に物事を考えていない」と言う事だ。
2. に関しても「再帰と言う難しい事柄を教える」と言う大勘違いのテーゼを持ってきてるせいで、実は末尾再帰自体は簡単なのだ、と言う事に気づいてない人が多い、と言う事だ。言い換えると教育現場で本来なら、whileを教えた時点で関連項目として末尾再帰を教える事が可能だ、と言う事である。
そして、仮に末尾再帰を知った人間でも10回も末尾再帰を練習した辺りで
「あれ、おかしいな、whileで書いてる気分になってきた」
ってならなきゃおかしいのである。
あるいは「おかしな気分になってきた」のなら言語化せんと意味がない。
つまり、whileと末尾再帰の等価性に気づかない以上、「理論的に考えてる」ワケでもない、と言う事である。
一方、本物の理系なら、簡単にwhileと末尾再帰の等価性に気づくだろう。
要するに、プログラミングに対して「論理性が必要だ」って言ってる人たちは「他の人が言ってるから」諳んじてるだけであって、実は言ってる本人は大して論理的でもないのだ(※2)。
これは人によっては朗報だろう。「文系なのにプログラマになれるんだろうか」とか悩んでる人。ハッキリ言って「プログラミング出来る/出来ないと論理性は全く関係がない」のである。
現実がそれを証明している。
さて、今まで見てきた通り、while構文と末尾再帰は、内部処理の違いをおいておくと、実はコードとしては全く等価だ、と言う事が分かった。末尾再帰を見た時、機械的にwhileコードへと変換可能である、と言う事実を。
繰り返すが、「ウンウン唸って考えなくても」末尾再帰はwhileコードに即座に変換可能だ、と言う事である。whileを使いこなしてる人間なら、な。
つまり、人間が機械的に変換可能だからこそコンパイラやインタプリタも当然機械的に末尾再帰をループに変換出来る、と言う事を暗示している。
もちろん、殆どの末尾再帰最適化をするプログラミング言語やコンパイラやインタプリタは低レベルのアセンブリの類でループ構文に変換してるわけで、別に表層的にwhileループに変換してるわけではない。しかしどんなボンクラでも末尾再帰をwhileループに変換可能だ、と言う事は人間以上にボンクラであるコンパイラやインタプリタでさえ末尾再帰最適化を可能とする、と言う事を間接的に証明してるわけだ。
そして、実は機械語/アセンブリレベルだと条件分岐と繰り返しには差がない。両者ともジャンプ構文なのだ。
つまり、末尾再帰最適化、とは極論、「ジャンプの使い方を統一的に扱う」と言う高級言語上の方法論を語ってるに過ぎない。
言い換えると、プログラミング言語は真の意味では、サブルーチンさえ備えていれば
- 逐次処理
- 条件分岐(ジャンプ)
の二つの機能さえあれば良い、って事を言ってのけてるのである。
とまぁ論理的な帰結はそうならざるを得ないのだが。
何度も書いてるし、先にも書いたが、Pythonは実は割に非力な言語なので末尾最適化を実装していない。
と言うわけで上の「論理的な帰結」は残念ながら「机上の空論」となってしまう。
末尾再帰が内部的にループに変換されないとすれば、再帰の最適化は不可能なのだろうか?
と訊けば一つだけ手がある。メモワイズとかメモ化と呼ばれる手法である。
これは別に末尾再帰に限った手ではなく、普通の再帰相手でも使える手法である。
仕組みは、計算結果をハッシュテーブル(Pythonではdictinary型)に登録しておいて、計算が必要な際に、既に結果が登録済みの時に計算をせず、ハッシュテーブルから計算済みの値を持ってくるやり方である。
これは通常、普通のハッシュテーブル、ないしは連想配列を提供しているプログラミング言語の場合、自分で仕組みをプログラミングしておかなければならないのだが、一方、さすがはPython、battery includedなので、気楽に使う事が可能だ。
例えば、元の末尾再帰のコードの場合、計算時間を知る為に次のようにしてみる。
from timeit import timeitdef fibs(n, acc = [0, 1]):
if n < 2:
return acc if len(acc) > 2 else acc[:n+1]
else:
return fibs(n - 1, acc[:2] + [sum(i) for i in zip(acc[:-1], acc[1:])])
print(timeit('fibs(128)', globals = globals(), number = 1))
ここでは128項目を持つ長いフィボナッチ数列のリストを得るが、計算主要時間は手持ちのPCだと例えば次のような結果が出る。
0.0064629150001564994
大体、0.006秒前後の計算時間がかかるようになっている。
これをメモワイズで最適化してみよう。
Pythonの場合、functoolsと言うライブラリからlru_cache(※3)と言うデコレータを持ってくれば単純にメモ化で最適化してくれる筈だが・・・・・・。
from functools import lru_cache
from timeit import timeit@lru_cache
def fibs(n, acc = [0, 1]):
if n < 2:
return acc if len(acc) > 2 else acc[:n+1]
else:
return fibs(n - 1, acc[:2] + [sum(i) for i in zip(acc[:-1], acc[1:])])
print(timeit('fibs(128)', globals = globals(), number = 1))
実はこのままでは上手く行かない。予期せぬエラーコードを目にする事となるだろう。
TypeError: unhashable type: 'list'
これ、どういう事か、と言うとPythonの辞書型ではリストがキーにはなれないから、である。言い換えると、辞書型ではミュータブル(破壊的変更が可能なデータ型)をキーとしては扱えない。キーとして使えるのはイミュータブル(破壊的変更が不可能)なデータ型なのだ。
Pythonでリストの代わりに使えるイミュータブルなデータ型としてタプルがある。
従って、まずは件の末尾再帰なフィボナッチ数列のコードをタプルを返すように書き換える。
from timeit import timeitdef fibs(n, acc = (0, 1)):
if n < 2:
return acc if len(acc) > 2 else acc[:n+1]
else:
return fibs(n - 1, acc[:2] + tuple([sum(i) for i in zip(acc[:-1], acc[1:])]))
print(timeit('fibs(128)', globals = globals(), number = 1))
これの実行時間計測をすると、次のようになる。
0.005033332003222313
大体、やっぱり0.005秒前後、の計算時間がかかる。
これに対してlru_cacheを適用すると次のようになる。
from functools import lru_cache
from timeit import timeit
@lru_cache
def fibs(n, acc = (0, 1)):
if n < 2:
return acc if len(acc) > 2 else acc[:n+1]
else:
return fibs(n - 1, acc[:2] + tuple([sum(i) for i in zip(acc[:-1], acc[1:])]))
print(timeit('fibs(128)', globals = globals(), number = 1))
実行すると次のようになる。
0.006995795003604144
実は実行時間が大して変わらない。
しかしながら、二回目を実行すると次のように計算時間が大幅に短縮されるのだ。
>>> print(timeit('fibs(128)', globals = globals(), number = 1))
3.6849960451945662e-06
>>>
つまり、第一回目だとハッシュテーブルに何も登録されてないので、計算時間がかかるのだが、二回目だと計算しないで、一回目の計算のお陰で既にハッシュテーブルに登録された値を参照するだけで済むので、ハッシュテーブルの検索だけ、で計算が終わるのである。
また、メモワイズした以上、これより大きい値を計算しようとすると、ハッシュテーブルを利用しながら値を計算するので、やはり計算コストが大幅に短縮されるのである。
実は、ここで使われるハッシュテーブルは大して大きくないので、上限的には厳しい事になるが、それでもある程度、末尾再帰をループ構文とは違った意味で最適化してくれる。
かつ、それはスタックを消費しない、と言う事を意味してる。ただし、今度はヒープを代わりに消費する事になるので、結果それなりにコストはかかる事となる。
ちなみに、前に紹介した「たらい回し関数」も、メモ化技法を使えば二回目以降は大幅に計算時間を短縮出来る。
興味がある人は試してみたら良いだろう。
※1: シンタックスシュガー。構文糖衣、とも言う。厳密にはある構文で書かなければならない煩雑な書法を、もっと単純で簡単なショートカット的な書法で許容される書き方、の事を言う。
仮に末尾再帰が難しい、と感じるのなら、while文と言うのはまさしく末尾再帰に対するシンタックスシュガーとして働いている。
※2: 理系の人間と違い、プログラマは徒党を組むのを好む。例えばQiitaなんか見てると、誰かが問題発言したらその情報が伝搬し、全員でその個人を叩くような「苛め」を行うのが大好きで、行動から見ても「理論的に考えるのを好む」人間とか理系の人間と大幅に違う行動をするのだ。
これは性質的には理系/理学の人間みたいに「個人で立脚して仕事をする」、要するに研究に適した性質を持ってなく、あくまで集団作業で仕事をする人間の特徴だとは言えよう。「個人」より「集団」が大事なのである。
そして、集団作業で仕事をするのは、基本的には文系人間側の特徴なのである。
いずれにせよ、「数学を知ってなければならない」が、それと「理論的に考える」あるいは「理系である」ってのは全く関係がない。
むしろプログラマは理論的に考えてるのではなく、プログラミングにおける「パターン」を数多く、良く知ってるだけ、なのである。
そして「知っておくべき数学の質と量」なんつーのは、誤解を畏れずに言うと経済学部で要求する程度かそれ以下である。
なお、最近アメリカの、MITの方の研究では、プログラミングに於いては脳の理論領域はそこまで反応しない模様である。つまり、良く言われる程の理論性はやっぱり必要ないのである。むしろ、パズルを解く時と似た反応をしているらしい。
※3: Python3.9以降では、単にcacheと言う名前のデコレータを用いれば良い。
