初期の言語設計と開発

原文：http://python-history.blogspot.com/2009/02/early-language-design-and-development.html
原文投稿者：Guido van Rossum

ABCからPythonへ

Pythonの開発のスタート時から、もっとも大きい影響を与えた言語は、1980年代の初め頃にLambert Meetens氏とLeo Geurts氏などがCWIで言語設計を行ったABCである。ABCはBASICの代替の教育用言語を目指していた言語である。そしてパーソナルコンピュータのための言語および環境になることを目指した。ABCの開発は、最初にプログラミングのタスクを分析する作業から始まり、何度か大きなユーザテストを含むイテレーションを実行しながら、言語の設計が行われた。私がABCグループで持った役割というのは、主にこの言語本体と、統合編集環境の実装である。

Pythonがインデントをブロックの区切りに使うようになったのは、ABCからの直接もらってきたアイディアであるが、元々はこの考え方はABCから生まれたものではない。これはすでにDonald Knuth氏によって推奨されるようになっていたし、プログラミングのスタイルとしてよく知られていた。また、occamというプログラミング言語が既にインデントを採用していた。しかし、ABCの設計者は、節とインデントされたブロックとを区別するのにコロンを使用することを思いついた。コロンがないバージョンでの初期のユーザテストにおいて、プログラミングの最初の一歩を教わっている初心者にとって、インデントの意味があまり明快には区別できていないということが分かったからである。コロンの追加により、コロンの前後で何がどうつながっているのかということに注意が向けられるようになり、かなり明確に理解されるようになったのである。

いくつか修正があるものの、Pythonの主なデータ型もABCから取り入れられた。ABCの配列はバッグか、もしくはマルチセットのどちらかであり、改良されたB-tree実装を使って常にソートされるようになっていた。ABCのテーブルも、キーによって常にソートされているような連想配列である。私はどちらのデータ型も、私が予想するような一般的な使用方法にはそぐわないと考えた。例えば、ファイルから読み込んだ行の配列を表現する場合などである。ABCでは行番号をキーとするようなテーブルを使用する必要があり、行の挿入と削除が極めて困難であった。そこで、私はリスト型を、挿入と削除の操作が簡単にできるような柔軟なデータ型に変更し、リスト内の項目の順序に関しては、ユーザがすべてコントロールできるようにした。ソートされた結果が必要な時があれば、そのときだけsortメソッドがそれをサポートするという仕組みにしたのである。

私は、ソート済みテーブルの実装も、ハッシュテーブルの実装に置き換えた。私がハッシュテーブルを選択した理由は、ABCのB-treeを使った実装よりも早く、簡単であると信じていたからである。後に、理論上でB-treeの方がスペースの消費量も、消費時間も、多くの操作領域で優れているということが分かったが、実際はB-treeアルゴリズムがあまりにも複雑なため、正しく実装するのが困難であると判断した。同じ理由から、小さいテーブルサイズのときのパフォーマンスも、部分最適化を行った。

ABCのタプル型(変更できない配列)はそのまま残した。Pythonの変数やりとりの際のパック/アンパックできるようにする、という操作はABCから直接もらったアイディアである。タプルが配列の内部表現として使われるようになると、私は配列のようなインデックスとスライスの操作をタプルに加えた。

配列のようなインタフェースをタプルに追加した結果、長さが0か1という境界条件のタプルをどのように扱えばよいかを決める必要が発生した。ABCから持ってきたルールのひとつに「すべてのデータ型は、画面に表示されるか文字列に変換するときには、言語のパーサーが正しく受け取れる表現で出力されるべきである」というものがある。そのため、これに従うためには、長さが0と1のタプルの場合には何か目印を付ける必要があるのである。しかし、だからといって、１要素のタプルと、カッコなしの数式表現の違いをなくしたくはなかった。最終的には、不恰好ではあるが、現実的なアプローチとして, 1要素でカンマが後ろについている場合には要素数1タプルになり、"()"の場合には要素数がゼロのタプルになる、という表現を採用した。Pythonの通常のカッコの表現は、この問題を除けばタプルの文法で必要とされるものに対して、すべてそのまま同じである。空のタプルが「何もない」と表現されるため、単純なタイプ間違いがあれば容易に発見できるはずである。

訳注：ここで言っている「要素数が0か1のタプル」というのは、数式の中では 4 - (1 + 2) ⇒ 4 - (3) ⇒ 4 - 3と、項目数がひとつだけのカッコは処理の過程で外されることになるが、データ構造としての要素数1のタプルにおいて、a = (3) ⇒ a = 3とされてしまうと、a[0]とアクセスができなくなってしまい、困ってしまうのでカッコは外れて欲しくない、という事象のこと。最終的には長さが0, 1のタプルは()および(1,)と表現するようになった。

Pythonの文字列は、表現以外はABCの文字列と非常に似た動作をするようにした。どちらも、文字列というのは変更不可能な文字列である。表現上異なっているのは、Pythonは最初の要素を0番目として順番を指定するところである。このときはインデックスで要素を指定できるデータ型にはリスト、タプル、文字列の３種類の型があった。私はこれらのシーケンスの操作を共通のコンセプトで一般化しようと決めた。この一般化により、どのシーケンス型であっても同じように基本の操作することができるようになった。例えば、長さの取得(len(s)), インデックス(s[i]), スライス(s[i:j]), ループ(for i in s)などである。

数値は、ABCから大きく外れた設計を行ったもののひとつである。ABCでは実行時には２つのデータ型があった。任意の精度の有利数として正確な数値が格納できる型と、CPU上の浮動小数点数で表された近似された値と拡張された指数の組み合わせで表現された数値型の２つである。有理数は私の視界の外にあった。私の体験談になるが、ABCで自分の税金を計算しようとしたことがあった。このプログラムはとてもシンプルに見えたが、ちょっとしたシンプルな数値を計算するのにものすごい時間がかかったのである。調査の結果、ABCは数千桁の精度の数値を使って計算を行い、画面に出力するときにギルダーとセントに丸めて表示しているということが分かった。Pythonでは伝統的な、CPUの持っている数値型と浮動小数点数をそのまま使用するという、良く使用されるモデルを採用した。Pythonの中では、これらの型はそれぞれ、C言語のデータ型のlongとdoubleに単純にマッピングされている。

訳注：ギルダーはGuidoの出身のオランダの通貨。セントは米ドルと同じく、100セント=1ギルダー。

正確で限界のない数値を使って計算を行うという使い方も重要であると感じたので、bignumデータ型を追加した。私はこれをlongと呼んでいた。私は既に数年にわたってABCのbignumを改良したいと思い続けていた。ABCのオリジナルの実装は私が最初にABCに貢献したもののひとつである。これは内部は10進数で表現されていた。このコードをPythonの中で使用するのは簡単であった。

Pythonにbignumを追加したが、重要なことは、すべての数値の計算にこれを使用したいと思っているわけではなかった点である。私が自分で書いたPythonプログラムと、CWIの同僚が書いたプログラムをプロファイルした結果、ほとんどのプログラムの実行時間のうち、数値の計算が全体に占める割合が大きいことが分かった。また、もっとも多く数値が使われる場面というのは、メモリの範囲内に収まるような小さい配列のインデックスである。そのため、私が想定したのは「厳密な数学」の計算を行うか、アメリカの国家予算をセント単位で計算するかというケース以外の、一般的に使われる場面のほとんどすべてはCPUの数値に納まる、というモデルである。

数値にまつわる問題

数値の実装、特に整数に関しては、設計当時に、私がいくつもの大きな設計間違いをしてしまった領域のひとつである。しかし、Pythonの設計に関連する重要な教訓をいくつも学ぶことができた。

訳注：ここでこれから述べる問題は現在では解決済みです。

Pythonが異なる二つの整数型を持っているので、プログラムの中でまずはこの二つを見分ける方法を考える必要があった。私が選択した解決策は、制限のない長い数値(long型)を扱いたい場合には、ユーザにきちんと宣言をしてもらう、というものであった。具体的には数値の後ろにLをつけて書く(例えば、1234L)という方法をとった。「ユーザには、興味のない実装の詳細を気にさせてはならない」というABCに影響された哲学があるが、この分野ではPythonはこれを破ることになってしまった。

残念ながら、これは数多くある数値の問題の中では、小さい問題のひとつでしかない。もっとひどい問題は、私が実装したint型とlong型では、いくつかのケースで微妙に異なる動作をしたことである。int型はコンピュータの数値型で表現されているため、計算結果がオーバーフローすると32bitの境界でクリップされてしまうのである。C言語のlong型でも、同じことは時々起こった。さらに、int型は通常は正も負も扱える(符号つき)ものとして処理されるが、ビット演算やビットのシフト操作、、8進数や16進数との間の相互変換時には、正だけの(符号なし)の整数として扱われた。long型は常に符号つきとして扱われた。そのため、いくつかの演算では、数値がint型かlong型かによって計算結果が変化してしまっていた。例えば、32ビット環境の場合、1<<31(1を左に31ビット分シフトする)の結果は、32ビットの数値の中で最大の負の値が返ってくる。そして、1<<32では0となる。しかし、1L<31(long型で表現された1を左に31ビット分シフトする)の結果は、2**31と同じ大きな数値になるのである。1L<<32は同様に2**32と同じ結果となった。

これらの問題のいくつかを解決するために、簡単な修正をほどこした。ユーザに内緒で数値をクリップしてしまう代わりに、ほとんどの数値演算子を書き換えて、結果が合わないときはOverflowError例外が上がるようにした。一部、ビット演算に関しては、ユーザはC言語とおなじ結果を期待すると思われたので、上記のチェックは入れなかった。もしこのチェックを入れていなければ、Pythonユーザは、C言語ユーザと同様に、符号つきの2**32という領域内でしかきちんと計算できないという認識に頼ったコードを書き始めていたことは疑いないだろう。そして、これらの問題の修正は、コミュニティにとってはより苦痛の大きい移行となっただろう。

オーバーフローのチェックは実装の詳細としては小さな問題に見えるかもしれないが、かなり困難を極めたデバッグの体験から、この機能はとても便利な機能であると実感していた。私が最初に実装したPythonプログラムのひとつに、Meertens数の計算という、シンプルな数値計算アルゴリズムを実装しようとしたものがあった。ABCのメインの作者のRichard Bird氏がCWIに勤めて25周年になった記念の、ちょっとした息抜きの数学の問題であった。最初のいくつかのMeertens数は小さいが、中間の結果は32ビットで扱えるよりも遥かに大きい数になるということを私は認識していなかった。私はこの事実を発見するまでは、長く苦しいデバッグの苦労を味わうことになった。この事実に気づいたときに、その場ですぐにすべての数値演算にオーバーフローチェックを入れて、C言語のlongで扱えない結果になるときはいつでも例外が上がるようにして、問題を特定することができた。オーバーフローのチェックにかかるオーバーヘッドのコストは、結果のための新しいオブジェクトの割り当てを実現するために既にかかっているコストを考慮すると、小さなものである。

訳注：どう書く？orgの説明によると、Meertens数の定義は以下の通りである。

正の整数 n を引数としてとり， 2^d1 * 3^d2 * 5^d3 ... * pk^dk を返す関数 がgoedel関数である。ただし，n を10進表現で k 桁の数としたときの各桁の数が数列 [d1,d2,d3,...,dk] をなすとし，dk が 1 の位，d1 が 10^(k-1) の位。また，pk は k番目の素数。

• goedel 9 ⇒ 2^9 ⇒ 512
• goedel 81 ⇒ 2^8 * 3^1 ⇒ 768
• goedel 230 ⇒ 2^2 * 3^3 * 5^0 ⇒ 108

このgoedel関数を適用すると自分自身になるような数，すなわち goedel (n) == n となるような正整数 n がMeertens数である。

読者の方には、オーバーフローの例外を上げるというのも、最終的な解ではなかった、ということを謝らなければならない。当時の私は「T型の数値演算の結果は、同じT型になる」というC言語のルールにとらわれていたのである。このルールもまた、数値の意味を考える上で、私が大きな間違いをしてしまった原因である。数値の割り算の結果の切り捨てについてはまた別のブログの記事で説明をしたいと思う。後になって思うと、オーバーフローの時には例外を投げるのではなく、結果をlong型にして返すようにするべきであった。これは現在のPythonの実装のやり方である。しかし、このように移行するまでには長い期間がかかってしまった。

このような数に関する問題には苦労してきたが、ひとつだけ、とてもポジティブな考えをこの経験から生み出すことができた。それはPythonでは未定義な結果というのを根絶しよう、と意志を固めたことである。正しい計算結果が返せないときには、いつでも例外を上げるべきである。そのため、Pythonのプログラムは、見えないところで渡される未定義の値によって問題が引き起こされるということはないだろう。この考え方は、言語、つまり言語そのものと標準ライブラリの双方にとって、今日でも重要な原則となっている。