現在地: ホーム ‣ Dive Into Python 3 ‣
難易度: ♦♦♦♦♢
❝ 大ノミの背中には小ノミが棲み、彼らに背中を噛みつかれる。
小ノミの背中にはもっと小さいノミが棲み……と無限に続く。❞
— Augustus De Morgan
正規表現が文字列にステロイドを与えるのと同様に、itertoolsモジュールはイテレータにステロイドを与える。まあその前に、あなたに古典的なパズルをお見せしたい。
HAWAII + IDAHO + IOWA + OHIO == STATES
510199 + 98153 + 9301 + 3593 == 621246
H = 5
A = 1
W = 0
I = 9
D = 8
O = 3
S = 6
T = 2
E = 4このようなパズルは、「クリプト算術」や「覆面算」と呼ばれている。これらの文字は実在の単語を綴っているが、各々の文字を0-9の数字で置き換えると、方程式を「綴る」ようにもなる。このパズルのカギは、どの文字にどの数字が対応するのかを見つけ出すことだ。この時、同じ文字には同じ数字を対応させなければならず、同じ数字を2つの文字に割り当てることもできず、さらにどの「単語」も0で始めてはならない。
この章では、元はRaymond Hettingerによって作成された、驚くべきPythonプログラムに飛び込んでいく。このプログラムは覆面算のパズルをたった14行のコードで解く。
import re
import itertools
def solve(puzzle):
words = re.findall('[A-Z]+', puzzle.upper())
unique_characters = set(''.join(words))
assert len(unique_characters) <= 10, 'Too many letters'
first_letters = {word[0] for word in words}
n = len(first_letters)
sorted_characters = ''.join(first_letters) + \
''.join(unique_characters - first_letters)
characters = tuple(ord(c) for c in sorted_characters)
digits = tuple(ord(c) for c in '0123456789')
zero = digits[0]
for guess in itertools.permutations(digits, len(characters)):
if zero not in guess[:n]:
equation = puzzle.translate(dict(zip(characters, guess)))
if eval(equation):
return equation
if __name__ == '__main__':
import sys
for puzzle in sys.argv[1:]:
print(puzzle)
solution = solve(puzzle)
if solution:
print(solution)このプログラムはコマンドラインから実行できる。Linuxでは次のようにする（コンピュータの速度によっては少し時間がかかるかもしれない。プログレスバーは表示されない。我慢だ！）。
you@localhost:~/diveintopython3/examples$ python3 alphametics.py "HAWAII + IDAHO + IOWA + OHIO == STATES" HAWAII + IDAHO + IOWA + OHIO = STATES 510199 + 98153 + 9301 + 3593 == 621246 you@localhost:~/diveintopython3/examples$ python3 alphametics.py "I + LOVE + YOU == DORA" I + LOVE + YOU == DORA 1 + 2784 + 975 == 3760 you@localhost:~/diveintopython3/examples$ python3 alphametics.py "SEND + MORE == MONEY" SEND + MORE == MONEY 9567 + 1085 == 10652
⁂
覆面算ソルバが最初に行うのは、そのパズルに含まれるすべての文字 (A–Z) を見つけ出すことだ。
>>> import re
>>> re.findall('[0-9]+', '16 2-by-4s in rows of 8') ①
['16', '2', '4', '8']
>>> re.findall('[A-Z]+', 'SEND + MORE == MONEY') ②
['SEND', 'MORE', 'MONEY']
reモジュールはPythonの正規表現の実装だ。このモジュールはfindall()という素敵な関数を持っている。この関数は、正規表現パターンと文字列を受け取り、その文字列の中にあるパターンの出現をすべて見つけ出す。この場合は、パターンは数字の並びにマッチする。findall()関数は、パターンにマッチしたすべての部分文字列のリストを返す。
次の例も、頭をすこしストレッチしてくれる。
>>> re.findall(' s.*? s', "The sixth sick sheikh's sixth sheep's sick.")
[' sixth s', " sheikh's s", " sheep's s"]
意外だっただろうか？ この正規表現が探すのは、空白、s、すべての文字のできるだけ短い繰り返し (.*?)、空白、そしてもうひとつのsだ。さて、入力文字列を見ると、5つのマッチが目に入る：
The sixth sick sheikh's sixth sheep's sick.
The sixth sick sheikh's sixth sheep's sick.
The sixth sick sheikh's sixth sheep's sick.
The sixth sick sheikh's sixth sheep's sick.
The sixth sick sheikh's sixth sheep's sick.
だが、re.findall()関数は3つのマッチしか返していない。具体的は1つ目と3つ目と5つ目だ。これはなぜだろうか？ 理由は、この関数は重なったマッチを返さないからだ。1つ目のマッチは2つ目に重なり合っているので、1つ目は返されるが2つ目はスキップされる。3つ目のマッチは4つ目に重なり合っているので、3つ目は返されるが4つ目はスキップされる。そして最後に5つ目が返される。マッチするのは5つではなく3つだ。
これが覆面算ソルバに影響を与えることはない。ただ興味深いと思って紹介しただけだよ。
⁂
集合を使うと、シーケンスから重複を取り除く作業が取るに足らないものになる。
>>> a_list = ['The', 'sixth', 'sick', "sheik's", 'sixth', "sheep's", 'sick'] >>> set(a_list) ① {'sixth', 'The', "sheep's", 'sick', "sheik's"} >>> a_string = 'EAST IS EAST' >>> set(a_string) ② {'A', ' ', 'E', 'I', 'S', 'T'} >>> words = ['SEND', 'MORE', 'MONEY'] >>> ''.join(words) ③ 'SENDMOREMONEY' >>> set(''.join(words)) ④ {'E', 'D', 'M', 'O', 'N', 'S', 'R', 'Y'}
set()関数はリストから重複する要素を取り除いた集合を返す。これは、forループのように考えれば理解できる。リストから1つ目の要素を取って集合に入れる。2つ目を入れる。3つ目を入れる。4つ目を入れる。5つ目を……待った、5つ目はすでに集合に含まれている。Pythonの集合は重複を許さないので、これは一度しか追加されない。6つ目入れる。7つ目を……これも重複だ。よって、これも一度しか追加されない。最終的な結果はどうなっただろうか？ 結果は元のリストから重複を取り除いたものとなる。あらかじめ元のリストをソートしておく必要すらないのだ。
''.join(a_list)はすべての文字列を1つに連結する。
覆面算ソルバはこのテクニックを使って、パズルに含まれるすべての文字を含んだ集合を構築する。
unique_characters = set(''.join(words))このリストは、あとでソルバが解候補をイテレートする際に、数字を文字に割り当てるために使われる。
⁂
多くのプログラミング言語と同様に、Pythonはassert文を持っている。これは次のように動作する。
>>> assert 1 + 1 == 2 ① >>> assert 1 + 1 == 3 ② Traceback (most recent call last): File "<stdin>", line 1, in <module> AssertionError >>> assert 2 + 2 == 5, "Only for very large values of 2" ③ Traceback (most recent call last): File "<stdin>", line 1, in <module> AssertionError: Only for very large values of 2
assert文には、正しいPythonの式であれば何でも置ける。この場合、式1 + 1 == 2はTrueと評価されるので、assert文は何もしない。
Falseと評価された場合、assert文はAssertionErrorを送出する。
AssertionErrorが起きた場合に表示するための、人間が読めるメッセージ含めておくこともできる。
つまり、コードのこの行は：
assert len(unique_characters) <= 10, 'Too many letters'……これと同等だ：
if len(unique_characters) > 10:
raise AssertionError('Too many letters')覆面算ソルバは、パズルが10種類以上の文字を含んでいるときの緊急脱出手段としてassert文を使っている。各々の文字は一意な数字に割り当てられるわけだが、数字は10個しかないので、10種類以上の文字を持つパズルは解を持ち得ないのだ。
⁂
ジェネレータ式は、関数を使わずに作るジェネレータ関数、という感じのものだ。
>>> unique_characters = {'E', 'D', 'M', 'O', 'N', 'S', 'R', 'Y'}
>>> gen = (ord(c) for c in unique_characters) ①
>>> gen ②
<generator object <genexpr> at 0x00BADC10>
>>> next(gen) ③
69
>>> next(gen)
68
>>> tuple(ord(c) for c in unique_characters) ④
(69, 68, 77, 79, 78, 83, 82, 89)
next(gen)の呼び出しによって、イテレータから次の値が返される。
tuple()、list()、set()に渡せば、すべての値がイテレートされてタプル・リスト・集合として返ってくる。これらの場合、余分な括弧は必要ない。つまり、tuple()関数に「はだか」の式ord(c) for c in unique_charactersを渡すだけで、Pythonがジェネレータ式だと識別してくれるのだ。
☞リスト内包表記の代わりにジェネレータ式を使うことで、CPU使用量とRAM使用量の両方を削減できる。もし作ったリストをすぐ投げ捨てるのであれば（つまり、それを
tuple()やset()に渡しているのなら）、代わりにジェネレータ式を使おう！
以下では、同じことをジェネレータ関数を使ってやっている：
def ord_map(a_string):
for c in a_string:
yield ord(c)
gen = ord_map(unique_characters)ジェネレータ式のほうがコンパクトだが、機能的には同等だ。
⁂
そもそも、順列というのは一体何だろう？ 順列は数学の概念だ（実際には、数学の分野によっていくつかの定義がある。ここで私が話しているのは組み合わせ論についてのものだが、その意味がまったく分からなくても心配する必要はない。いつものことながら、Wikipediaはあなたの味方だ）。
順列というのはこういうものだ。あなたは何か（数字とか、文字とか、踊っている熊さんとか）のリストを受け取る。そして、そのリストから取り出せる小さなリストをすべて見つけ出す。この時、取り出すリストはすべて同じサイズにする。そのサイズは最小で1、最大で全要素の数にできる。加えて、リストを取り出す際には1つの要素を2回以上使ってはならない。数学者は、「3つの異なる要素から2つずつ取り出すときの順列を見つけましょう」というようなことを言うが、これが意味することは、あなたは3つの要素からなるシーケンスを持っており、その要素から作り出せるすべての順序対を見つけ出したいということだ。
>>> import itertools ① >>> perms = itertools.permutations([1, 2, 3], 2) ② >>> next(perms) ③ (1, 2) >>> next(perms) (1, 3) >>> next(perms) (2, 1) ④ >>> next(perms) (2, 3) >>> next(perms) (3, 1) >>> next(perms) (3, 2) >>> next(perms) ⑤ Traceback (most recent call last): File "<stdin>", line 1, in <module> StopIteration
itertoolsモジュールには愉快なものがたくさん詰まっており、その中には、順列を見つけるという面倒な仕事をすべてやってくれるpermutations()関数も入っている。
permutations()関数は、シーケンス（ここでは3つの整数からなるリスト）と数値を受け取る。この数値が個々の小さなグループの要素の数になる。この関数はイテレータを返すが、このイテレータはfor文のようなイテレートを行う場所でならどこでも使用できる。ここでは手動でイテレータを動かして、すべての値を示している。
[1, 2, 3]から一度に2つずつ取り出したときの最初の順列は(1, 2)だ。
(2, 1)と(1, 2)は区別される。
[1, 2, 3]から一度に2つずつ取り出したときのすべての順列だ。(1, 1)や(2, 2)のようなペアは絶対に現れない。これらは同じ要素が繰り返し使われているので、正しい順列ではないのだ。返す順列が無くなると、イテレータはStopIteration例外を送出する。
permutations()関数はリストしか受け取れないわけではない。これは任意のシーケンスを受けとれる — つまり文字列さえも受け取れるのだ。
>>> import itertools
>>> perms = itertools.permutations('ABC', 3) ①
>>> next(perms)
('A', 'B', 'C') ②
>>> next(perms)
('A', 'C', 'B')
>>> next(perms)
('B', 'A', 'C')
>>> next(perms)
('B', 'C', 'A')
>>> next(perms)
('C', 'A', 'B')
>>> next(perms)
('C', 'B', 'A')
>>> next(perms)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
StopIteration
>>> list(itertools.permutations('ABC', 3)) ③
[('A', 'B', 'C'), ('A', 'C', 'B'),
('B', 'A', 'C'), ('B', 'C', 'A'),
('C', 'A', 'B'), ('C', 'B', 'A')]
'ABC'はリスト['A', 'B', 'C']と等価だ。
['A'、'B'、'C']から一度に3つずつ取るときの最初の順列は('A', 'B', 'C') だ。この他に5つの順列 — すなわち、この3文字の考えうる並べ方すべて — が存在する。
permutations()関数は常にイテレータを返すので、順列をデバッグする簡易な方法として、イテレータを組み込みのlist()関数に渡すことで、順列の全体を即座に見るというやり方がある。
⁂
itertoolsモジュールにある他の愉快なもの
>>> import itertools
>>> list(itertools.product('ABC', '123')) ①
[('A', '1'), ('A', '2'), ('A', '3'),
('B', '1'), ('B', '2'), ('B', '3'),
('C', '1'), ('C', '2'), ('C', '3')]
>>> list(itertools.combinations('ABC', 2)) ②
[('A', 'B'), ('A', 'C'), ('B', 'C')]
itertools.product()関数は、2つのシーケンスの直積からなるイテレータを返す。
itertools.combinations()関数は与えられたシーケンスについて、指定された要素の数からなる組み合わせ全部を取り出して、イテレーターとして返す。これはitertools.permutations()関数に似ているが、順序違いのものは含まないということが異なる。すなわち、itertools.permutations('ABC', 2)は、('A', 'B')と('B', 'A')の両方を返すが、itertools.combinations('ABC', 2)は、('B', 'A')を返さない。なぜなら、これは('A', 'B')の順序を変えたものでしかないからだ。
[favorite-people.txtをダウンロードする]
>>> names = list(open('examples/favorite-people.txt', encoding='utf-8')) ①
>>> names
['Dora\n', 'Ethan\n', 'Wesley\n', 'John\n', 'Anne\n',
'Mike\n', 'Chris\n', 'Sarah\n', 'Alex\n', 'Lizzie\n']
>>> names = [name.rstrip() for name in names] ②
>>> names
['Dora', 'Ethan', 'Wesley', 'John', 'Anne',
'Mike', 'Chris', 'Sarah', 'Alex', 'Lizzie']
>>> names = sorted(names) ③
>>> names
['Alex', 'Anne', 'Chris', 'Dora', 'Ethan',
'John', 'Lizzie', 'Mike', 'Sarah', 'Wesley']
>>> names = sorted(names, key=len) ④
>>> names
['Alex', 'Anne', 'Dora', 'John', 'Mike',
'Chris', 'Ethan', 'Sarah', 'Lizzie', 'Wesley']
list(open(filename))というイディオムで処理すると、各行の末尾にある改行文字が残ってしまう。このリスト内包表記は、文字列メソッドのrstrip()を使って、文字列の後ろに付いている空白文字を各行から取り除いている（文字列は、先頭にある空白文字を取り除くためのlstrip()メソッドや、先頭と末尾の両方の空白文字を取り除くstrip()メソッドも持っている）。
sorted()関数はリストを受け取って、そのリストをソートしたものを返す。デフォルトではアルファベット順にソートする。
sorted()関数はkey引数として関数を受け取り、そのキーに基づいてソートを行うこともできる。この例では、ソート関数はlen()なので、これはlen(各要素)に基づいてソートを行う。短い名前が先に来て、次に長い名前、その後ろにもっと長い名前が続くというわけだ。
これがitertoolsモジュールと何の関係があるのかって？ その質問を待っていた。
……前の対話シェルの続き…… >>> import itertools >>> groups = itertools.groupby(names, len) ① >>> groups <itertools.groupby object at 0x00BB20C0> >>> list(groups) [(4, <itertools._grouper object at 0x00BA8BF0>), (5, <itertools._grouper object at 0x00BB4050>), (6, <itertools._grouper object at 0x00BB4030>)] >>> groups = itertools.groupby(names, len) ② >>> for name_length, name_iter in groups: ③ ... print('Names with {0:d} letters:'.format(name_length)) ... for name in name_iter: ... print(name) ... Names with 4 letters: Alex Anne Dora John Mike Names with 5 letters: Chris Ethan Sarah Names with 6 letters: Lizzie Wesley
itertools.groupby()関数はシーケンスとキー関数を受け取り、ペアを生成するイテレータを返す。各々のペアには、key_function(each item)の値と、キー関数に渡したときにその値を返すような要素を集めたイテレータが入っている。
list()関数を呼び出したことでイテレータは「使い果たされた」。つまり、リストを作るために、イテレータの要素をすべて生成しつくしたのだ。イテレータに「リセット」ボタンは無いので、一度使い果たしたら最初からやり直させることはできない。もう一度（例えば、次のforループで）イテレートしたいのであれば、再びitertools.groupby()を呼び出して新しいイテレータを作る必要がある。
itertools.groupby(names, len)は、4文字の名前をすべて1つのイテレータに入れ、5文字の名前をすべてもう1つのイテレータに入れ……というように同じ長さの名前を同じ1つのイテレータに入れてくれた。groupby()関数は完全に汎用的なので、文字列を最初の1文字でグループ分けすることもできるし、数字を因数の数で分類することもできる。思いつくキー関数ならどんなものでも使えるのだ。
☞
itertools.groupby()関数は、入力されたシーケンスがグループ関数ですでにソートされているときにだけ機能する。上の例では、名前のリストをlen()関数でグループ分けしたが、これが上手くいったのは、あらかじめ入力リストを名前でソートしておいたからだ。
よく見ているかな？
>>> list(range(0, 3)) [0, 1, 2] >>> list(range(10, 13)) [10, 11, 12] >>> list(itertools.chain(range(0, 3), range(10, 13))) ① [0, 1, 2, 10, 11, 12] >>> list(zip(range(0, 3), range(10, 13))) ② [(0, 10), (1, 11), (2, 12)] >>> list(zip(range(0, 3), range(10, 14))) ③ [(0, 10), (1, 11), (2, 12)] >>> list(itertools.zip_longest(range(0, 3), range(10, 14))) ④ [(0, 10), (1, 11), (2, 12), (None, 13)]
itertools.chain()関数は、2つのイテレータを受け取って、1つ目のイテレータのすべての要素と、それに続いて2つ目のイテレータのすべての要素を含んだ1つのイテレータを返す（実は、任意数のイテレータを受け取ることができ、それらを関数に渡された順序で連結する）。
zip()関数はつまらないことを行うのだが、実はこれはものすごく便利なことが分かる。この関数は任意の数のシーケンスを受け取り、各シーケンスの1つ目の要素からなるタプル、各シーケンスの2つ目の要素からなるタプル、3つ目の要素からなるタプル……を生成するイテレータを返す。
zip()関数は、最も短いシーケンスの終わりで停止する。range(10, 14)は4つの要素 (10, 11, 12, 13) を持つが、range(0, 3)は3つしか持たないので、このzip()関数は3つの要素を持つイテレータを返す。
itertools.zip_longest()関数は最も長いシーケンスの終わりで停止する。短いシーケンスが尽きた後についてはNoneを挿入する。
OK、全部とても興味深いものだったけど、覆面算ソルバにはどんな関係があるのだろうか？ それはこういうことだ：
>>> characters = ('S', 'M', 'E', 'D', 'O', 'N', 'R', 'Y')
>>> guess = ('1', '2', '0', '3', '4', '5', '6', '7')
>>> tuple(zip(characters, guess)) ①
(('S', '1'), ('M', '2'), ('E', '0'), ('D', '3'),
('O', '4'), ('N', '5'), ('R', '6'), ('Y', '7'))
>>> dict(zip(characters, guess)) ②
{'E': '0', 'D': '3', 'M': '2', 'O': '4',
'N': '5', 'S': '1', 'R': '6', 'Y': '7'}
zip関数は文字と数字のペアを順番通りに作成する。
dict()関数に渡すことで、「文字をキー、対応する数字を値とした辞書」を構築できる構造になっているのだ（もちろんこれは唯一の方法ではない。辞書内包表記を使って、この辞書を直接構築することだってできる）。表示された辞書の表現ではペアの順序が変わっているが（辞書は本質的に「順序」を持たない）、元のcharactersとguessのシーケンス内の順序に基づいて、各文字に数字が対応付けられていることが見て取れるだろう。
覆面算ソルバは、パズルの文字を解の数字に対応させる辞書を作るために、各々の解候補に対してこのテクニックを使っている。
characters = tuple(ord(c) for c in sorted_characters)
digits = tuple(ord(c) for c in '0123456789')
...
for guess in itertools.permutations(digits, len(characters)):
...
equation = puzzle.translate(dict(zip(characters, guess)))だけど、このtranslate()メソッドというのは何かって？ それでは、これから本当に面白い部分に入っていくとしよう。
⁂
Pythonの文字列は多くのメソッドを持っている。lower(), count(), format()といった一部のメソッドについては文字列の章で学んだ。今度は、パワフルだがほとんど知られていない文字列操作のテクニックであるtranslate()メソッドを紹介したいと思う。
>>> translation_table = {ord('A'): ord('O')} ①
>>> translation_table ②
{65: 79}
>>> 'MARK'.translate(translation_table) ③
'MORK'
ord()関数は文字のASCII値を返し、これはA–Zの場合、常に65から90までの1バイトになる。
translate()メソッドは変換表を受け取り、文字列をその変換表に通す。つまり、変換表のキーに一致する部分をすべて対応する文字に変換するのだ。この例では、MARKをMORKに「変換 (translate)」している。
これが覆面算パズルを解くのとどう関係するのかって？ 結論を言えば、これはすべてに関係しているのだ。
>>> characters = tuple(ord(c) for c in 'SMEDONRY') ① >>> characters (83, 77, 69, 68, 79, 78, 82, 89) >>> guess = tuple(ord(c) for c in '91570682') ② >>> guess (57, 49, 53, 55, 48, 54, 56, 50) >>> translation_table = dict(zip(characters, guess)) ③ >>> translation_table {68: 55, 69: 53, 77: 49, 78: 54, 79: 48, 82: 56, 83: 57, 89: 50} >>> 'SEND + MORE == MONEY'.translate(translation_table) ④ '9567 + 1085 == 10652'
"SMEDONRY"は、alphametics.solve()関数におけるsorted_charactersの値の例だ。
alphametics.solve()関数においてitertools.permutations()関数によって返されるものと同じ形をしている。
alphametics.solve()関数がforループの中でやっていることそのものだ。
translate()メソッドに変換表を渡す。これは、文字列の各文字を（charactersの文字とguessの数字にもとづいて）対応する数字に変換する。その結果は、有効なPythonの式を文字列として表したものになる。
これはずいぶん感動的だ。しかし、たまたま正しいPythonの式になった文字列を使って何ができるのだろうか？
⁂
これはパズルの最後のピースだ（というより、パズルソルバの最後のピースと言うべきか）。手の込んだ文字列操作の末に、'9567 + 1085 == 10652'というような文字列が手に入った。しかし、これは文字列であって、文字列で何ができるというのだ？ eval()の話に入ろう。これは、Pythonの式を評価するための万能ツールだ。
>>> eval('1 + 1 == 2')
True
>>> eval('1 + 1 == 3')
False
>>> eval('9567 + 1085 == 10652')
True
ちょっと待って。これだけじゃない！ eval()関数が扱えるものはブール式だけではなく、どんなPythonの式でも扱えるし、どんなデータ型でも返せるのだ。
>>> eval('"A" + "B"')
'AB'
>>> eval('"MARK".translate({65: 79})')
'MORK'
>>> eval('"AAAAA".count("A")')
5
>>> eval('["*"] * 5')
['*', '*', '*', '*', '*']
待って、まだ終わりじゃない！
>>> x = 5
>>> eval("x * 5") ①
25
>>> eval("pow(x, 2)") ②
25
>>> import math
>>> eval("math.sqrt(x)") ③
2.2360679774997898
eval()が受け取る式は、eval()の外側で定義されたグローバル変数を参照できる。関数の中で呼び出されたときはローカル変数も参照できる。
話はもう少し……
>>> import subprocess
>>> eval("subprocess.getoutput('ls ~')") ①
'Desktop Library Pictures \
Documents Movies Public \
Music Sites'
>>> eval("subprocess.getoutput('rm /some/random/file')") ②
subprocessモジュールは、任意のシェルコマンドを実行し、その結果をPythonの文字列として受け取る機能を提供する。
状況はもっと悪くなる。というのは、グローバルの__import__()関数が存在するからだ。この関数はモジュール名を文字列として受け取り、そのモジュールをインポートしてそれへの参照を返す。この関数とeval()の力を組み合わせれば、すべてのファイルを消し飛ばす式を作れるのだ：
>>> eval("__import__('subprocess').getoutput('rm /some/random/file')") ①
'rm -rf ~'の実行結果を想像してみよう。実際には一切何も出力されないのだが、あなたのファイルは全て消え去ってしまう。
eval() is EVIL
eval()は邪悪
邪悪というのは、信頼できないところから入力された任意の式を評価してしまうことだ。eval()を使うのは、信頼している入力に対してだけにすべきだ。もちろん重要なのは「信頼している」とは何かを理解することであるが、確実に言えることがある： この覆面算ソルバを小さなおもしろWebサービスとしてインターネットに公開すべきではない。「え？ この関数は文字列を評価する前に沢山の文字列操作をしてるんだから、これのセキュリティホールを突く方法を誰かが見つけ出すなんて想像できないや」という誤った考えをしてはいけない。きっと何者かが、すべての文字列操作を通過する気色悪い実行可能コードを忍び込ませる方法を見いだすだろう（奇妙なことは実際に起きている）。そうしたら、自分のサーバにキスして、お別れをしなければならない。
でも、式を安全に評価する何らかの方法は本当に無いの？ 外の世界にアクセスしたり傷つけたりできないサンドボックスにeval()を入れる方法は無いの？ うーん、それはイエスでもノーでもある。
>>> x = 5
>>> eval("x * 5", {}, {}) ①
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<string>", line 1, in <module>
NameError: name 'x' is not defined
>>> eval("x * 5", {"x": x}, {}) ②
>>> import math
>>> eval("math.sqrt(x)", {"x": x}, {}) ③
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<string>", line 1, in <module>
NameError: name 'math' is not defined
eval()関数に渡された2つ目と3つ目のパラメータは、式を評価するときのグローバル名前空間とローカル名前空間として機能する。この場合は、両方が空になっている。このことは、"x * 5"という文字列が評価されるときに、グローバルとローカル名前空間のどちらにもxへの参照が存在しないということを意味するので、このeval()は例外を送出する。
mathモジュールをインポートしているが、eval()関数に渡す名前区間にこれを含めていないので、この評価は失敗する。
おお、これなら簡単だ。覆面算ウェブサービスを作らせてよ！
>>> eval("pow(5, 2)", {}, {}) ①
25
>>> eval("__import__('math').sqrt(5)", {}, {}) ②
2.2360679774997898
pow(5, 2)は問題なく評価される。5と2がリテラルで、pow()が組み込み関数だからだ。
__import__()関数も組み込み関数なので、これも使えてしまう。
そう、これが意味するのは、たとえeval()を呼び出すときにグローバル・ローカル名前空間に空の辞書を明示的に設定したとしても、悪事を働けるということだ：
>>> eval("__import__('subprocess').getoutput('rm /some/random/file')", {}, {})
わぁ、覆面算ウェブサービスを作っていなくて良かったよ。eval()を安全に使う方法は何か無いの？ うーん、イエスでもあり、ノーでもある。
>>> eval("__import__('math').sqrt(5)",
... {"__builtins__":None}, {}) ①
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<string>", line 1, in <module>
NameError: name '__import__' is not defined
>>> eval("__import__('subprocess').getoutput('rm -rf /')",
... {"__builtins__":None}, {}) ②
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<string>", line 1, in <module>
NameError: name '__import__' is not defined
"__builtins__"をPythonのNull値のNoneにマッピングしたグローバル名前空間を定義する必要がある。内部的には「組み込み」関数は"__builtins__"という疑似モジュールに含まれているのだ。この疑似モジュール（つまり、組み込み関数の集合）は、明示的に無効にしないかぎり、評価される式で使用できるようになっている。
__builtins__が上書きされていることを確認しよう。これが__builtin__や__built-ins__のようなものになっていると、問題なく動作するにもかかわらず、恐ろしいリスクにさらされることになる。
じゃあ、eval()はもう安全？ うーん、イエスでもノーでもある。
>>> eval("2 ** 2147483647",
... {"__builtins__":None}, {}) ①
__builtins__にアクセスできなかったとしても、なおDOS攻撃を仕掛けることはできる。例えば、2の2147483647乗は、長時間にわたってサーバのCPU使用率を100%に跳ね上げるだろう（これを対話シェルで試すときは、Ctrl-Cを何回か押して脱出しよう）。厳密にいえば、最終的にはこの式は実際に値を返すのだが、その間、サーバは無意味な処理に全力を注ぎ込むことになる。
最終的に、信頼されていないPythonの式を安全に評価できるようになった。ただし、現実世界ではほとんど役に立たない「安全」の定義においてだが。これは、遊びでつかう場合や、信頼された入力だけを渡すのであれば良いが、他のことに使うと災いを招くことになる。
⁂
復習： このプログラムは、ブルートフォースによって（つまり、すべての解候補を総当り的に検索することによって）覆面算パズルを解く。これを行うために、このプログラムは……
re.findall()関数を使って、パズルに含まれる文字をすべて見つける
set()関数を使って、パズルに含まれるすべてのユニークな文字を見つける
assert文を使って、10個以上のユニークな文字があるかチェックする（その場合、パズルは絶対に解けない）
itertools.permutations()関数を使って、すべての解候補を求める
translate()を使って、すべての解候補をPythonの式に変換する
eval()関数を使い、Pythonの式を評価することによってそれぞれの解候補をテストする
Trueと評価された最初の解を返す
……これを14行のコードで行う。
⁂
itertoolsモジュール
itertools — Iterator functions for efficient looping
コードの再ライセンスに同意してくれたことについて、Raymond Hettingerに大変感謝している。そのおかげで、私はこのコードをPython 3へ移植することができ、この章の土台として使うことができた。
© 2001– Mark Pilgrim
© Fukada, Fujimoto（日本語版）