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

by Peter Norvig

これは Lisp プログラマのための簡単な Python 概説である。 (はからずも、Python プログラマにとってもこのページは Lisp を学ぶのによいそうだ。) 基本的には、Python は「伝統的な」構文 (Lisp 使いが "infix (中置記法)" とか "m-lisp" とか呼ぶもの) をもつ Lisp の方言と思われている。Comp.lang.python のあるメッセージによれば 「自分は Python で遊ぶようになるまで、なぜ LISP がそんなにいいアイデアなのか わからなかった」とのことで、Python は マクロ をのぞく Lisp の主要な機能をすべてサポートしている。それでも eval や演算子オーバーロードの 機能も持っているからマクロが完全になくなったというわけではない。この方法を使えば 自分の独自言語を作ることができる。

わたしが Python に目を向けたのは、 Russell & Norvig の AI 教科書 にある Lisp コード を Lisp から Java に移植しようと考えていたからだった。何人かの教師と学生が Java を望んでいた。 その理由は:

1. 他のクラスでもっともなじんでいた言語だったから。
2. グラフィカルなアプリケーションが欲しかったらしい。
3. 少数派ではあったが、ブラウザ上のアプレットを望んだ人もいた。
4. 何人かはただ単に Lisp の文法に慣れることができなかった。 彼らが授業にささげられる、限りある時間のうちには。

わたしの結論

わたしの見地では Python の欠点は 2つある。それは (1) コンパイル時のエラー解析やタイプ宣言がほとんど、Lisp よりさえも 少ないことと、(2) 実行時間が Lisp よりずっと、多くの場合数十倍のスケールで 遅い、ということだ (100倍遅いときもあるかもしれないし、1倍のときもあるが)。 定性的にみれば、Python はインタプリタ型の Lisp と同じくらいの速度に見える。 だが Lisp をコンパイルしたものと比べると明らかに遅い。この理由から、 わたしは Python をたくさん計算が必要な (あるいは、回数を重ねると結局たくさんの計算が必要になる) アプリケーションに使うことはおすすめしない。 しかしわたしの興味は実用ではなく教育のほうにあるから、 その意味ではこれはとりたてて問題ではない。

Python 入門

Python は Scheme の (よいライブラリをもった) 実用的なバージョンか、 ($@ や % がない) きれいなバージョンの Perl ととらえることができる。 Perl の哲学が TIMTOWTDI (there's more than one way to do it - あることをするのにいくつものやり方がある) なのに対して、Python は 人々が同じやり方で使うような最小のサブセットを提供することを 目標としている (たぶんこれは TOOWTDI - あることをするのに ひとつしかやり方がない - ということかもしれないが、もちろん がんばれば常にいくつものやり方はあるだろう)。論争の起こりやすい Python の 機能のひとつは begin/end や中カッコのかわりにインデントを使うというものだが、 これはこの哲学に由来している。つまり、中カッコがないということは、 どこに中カッコを起くべきかという書き方論争がなくなるということだ。 おもしろいことに Lisp もこの点においてはまったく同様の哲学をもっている。 誰もが自分のコードをインデントするのに Emacs を用いるので、 かれらはインデントについて議論するということがない。Lisp プログラムを とってきて正しくインデントし、制御構造用のカッコをとり除けば、 最終的に Python プログラムにかなり似たものができあがる。

Python は簡単なことをとても簡単にし、むずかしいことが 多すぎることのないようにするという、賢明な妥協の哲学をもっている。 わたしの意見では、これは非常にうまくいっている。簡単なことは簡単にでき、 むずかしいことは段階的にむずかしくなっている。その非一貫性は気にならないことが多い。 Lisp はより妥協の少ない哲学をもっていて、非常に強力でよく統制のとれた 言語の核を提供している。このことは Lisp を学ぶのをむずかしくしている。 なぜなら最初から高水準の抽象化を扱わければならず、見た目や感覚に 頼らずに自分がいま何をしているかを理解しなければならないからだ。 しかしこのことは Lisp で抽象化や複雑さの階層をふやすのを簡単している。 Lisp では非常にむずかしいことを、そんなにむずかしくないレベルにまで 落とすことができる。

これはわたしが Python.org にある宣伝文句を 持ってきて、2つのバージョンをつくったものだ。ひとつは ブルーで書かれた Python 用 で、 もうひとつは グリーンの強調文字で書かれた Lisp 用 である。 その他ののこりの部分は両方の言語に共通するもので、黒で書かれている。

Python/Lisp はインタプリタ型で、 コンパイルでき、オブジェクト指向や動的意味論をそなえた 高水準プログラミング言語です。これらの高水準の組み込みデータ構造は、 動的タイプづけや動的束縛と組み合わせることで、「迅速なアプリケーション開発 (Rapid Application Development)」にとって魅力的なものになっています。また スクリプティングや既存のコンポーネントをまとめるための“糊づけ言語”としても使えます。 Python/Lisp の構文はシンプルかつ 簡単に覚えることができ、これはプログラムの可読性を増し、それによってプログラムの維持にかかる費用を 抑えます。Python/Lisp は モジュールや パッケージをサポートしており、これによって プログラムのモジュール性とコードの再利用性を高めることができます。 Python/Lisp インタプリタと豊富な標準ライブラリは、ソースおよびバイナリの形式で、 すべてのプラットフォームにおいて修正することなく使え、かつフリーで配布することができます。 しばしばプログラマ達は Python/Lisp の もたらす高い生産性に酔いしれることでしょう。別過程の コンパイルという 作業がないために、修正-テスト-デバッグ作業は信じられないほど速くなりますし、 Python/Lisp をデバッグするのは 簡単なのです。まずい入力やバグが Segmentation Fault を起こすことは決してありません。 かわりに、インタプリタはエラーを発見し、例外を発生させます。プログラムが例外を キャッチしないときには、インタプリタはスタックトレースを表示します。 ソースレベルデバッガによって、ローカル変数やグローバル変数を検査したり、 任意の式を評価させたり、ブレイクポイントを設定したり一行ずつコードを ステップ実行できたり、といったことができます。デバッガは Python/Lisp 自身で 書かれていて、これは Python/Lisp の 自己記述力の高さを証明しています。いっぽうで、プログラムをデバッグする もっとも手軽な方法は何行かの print 文をソースに埋めこむことです。 すばやい修正-テスト-デバッグ作業のくり返しは、この単純なアプローチを より効果的なものにします。

はじめはその ブロック構造のインデント/カッコ に抵抗を示す人もいますが、ほとんどの人はやがてそれらを 好む/深く愛する ようになります。

経験ゆたかなプログラマが Python についてさらに学ぶならば、わたしは Python.org の ダウンロードページ から ドキュメンテーション パッケージをとってくることをおすすめする。 そして Python リファレンス マニュアルと、Python ライブラリ リファレンス に目を通せばよい。 あらゆる類のチュートリアルや書籍がそろっているが、 これらのリファレンスは絶対に必要だ。

以下の表は、Lisp/Python の翻訳ガイドになっている。 赤字 で書かれている箇所は、わたしからみて 一方の言語がとくに劣っていると感じる部分である。 強調 で書かれている箇所は、2つの言語が非常に異なってはいるものの、 とくにどちらが断然よいというわけではない部分である。 標準的なフォントの部分は 2つの言語が互いに似ている部分を示している。 構文はすこし違うものの、概念はまったく、あるいはほとんど同じ部分である。 この表のあとには 要点 と いくつかの Python用 サンプルプログラム が続く。

多くの人々に重要な部分は Python と Lisp の速度に関するところだろう。 あなたの 利用法に適したベンチマークをおこなうのはむずかしいが、 次の例は役に立つかもしれない。

速度は C++ 用の g++ コンパイラが 1.00 になるよう正規化してある。 だから 2.00 はそれより 2倍遅いことを表す。0.01 は 100倍速いということだ。 Lisp は CMUCL コンパイラを使っている。 背景の色は右の凡例にしたがって変えてある。最後の行は各言語からトップ2 と ワースト2 を除いて 25% から 75% のみの結果を出したものだ。 (トップ2 とワースト2 を除いて Lisp と Python を比較した結果、 Python のほうが Lisp よりも 3～85倍 遅いことがわかった -- これは Perl とほぼ同じで、 Java や Lisp よりずっと遅い。Lisp は Java の約 2倍の速さである。)

Lisp プログラマが Python を学ぶときの要点

1. リストは Cons ではない。 Python のリストは実際には Lisp における adjustable array や、Java における Vector に似ている。つまりリストへの アクセスは O(1) ですむが、cons と cdr をつかった操作に相当するものは O(n) の 新しい記憶領域を消費してしまう。car/cdr を使った再帰よりは map や for e in x: を使ったほうがいい。あと、空のリストがただひとつではなく 複数であることには注意しておく必要がある。これは Lisp でよくあるバグ -- ユーザが (nconc old new) とやって old が変更されると思いこみ、 実際には old が nil のときには何も起こらない -- を防ぐ。 Python では old.extend(new) はつねにうまく動作する。しかしこれは同時に、 空リスト [] に対して検査を行うときにはつねに == を使わなければ ならないということを意味する。is ではだめなのだ。また、デフォルト引数を [] にした場合は、値を修正しないほうがいいということも覚えておこう。
2. Python は Lisp ほど関数的でない。 リストが cons でないせいもあるが、Python のほうが Lisp よりも破壊的な関数を 使うことが多い。そしてこれらの関数はその操作が破壊的であることを強調するため、 多くの場合、None を返すようになっている。for x in list.reverse() は できそうに思えるかもしれないが、実際には Python の reverse は None を返す nreverse のようなものだ。これは いくつかのステートメントに分けておこなうか、自分の reverse を 書く必要がある。reverse 以外にも、remove や sort に ついても同じことがいえる。
3. Python のクラスは Lisp より関数的である。 Lisp (CLOS) では、あるクラス C を再定義すると C を表すオブジェクトも 変更された。したがって、それまでに存在した C のインスタンスやサブクラスは 新しいクラスにつなぎ換えられた。ときにこれは問題をひき起こすが、 対話的にデバッグしているときは、これは望まれる動作だろう。Python では、 新しいクラスを定義して新しいクラスオブジェクトを手にしても、それまでの 古いインスタンスやサブクラスは依然として古いクラスを見ている。つまり クラスを再定義するたびに、ほとんどの場合はサブクラスを再読み込みしたり データ構造を再構築しなければならない。このことを忘れると混乱のもとになる。
4. Python は Lisp より動的で、エラーチェックが少ない。 Python では未定義の関数や未定義のフィールド、関数に渡す引数の 個数間違いなど、読み込みのさいにはどれもほとんど警告されない。 これらの警告には実行時まで待たねばならない。商用の Lisp 実装はこれらの警告を たくさん出すことができる。clisp のような簡単な実装では出ない。 Python のほうが明らかに危険であることを示す例として、 self.field = 0 とするつもりで self.feild = 0 と やったときなどがあげられる。後者の場合、新しいフィールドが動的に 作られてしまう。Lisp では同じことをしても (setf (feild self) 0) は エラーを返すだろう。いっぽう未定義のフィールドに対するアクセスは どちらの言語もエラーになる。
5. self を忘れるな。 これは Lisp プログラマ向けというよりはむしろ Java プログラマ向けの注意である。 メソッドの中では、かならず self.field のように書き、field のようには 書かないこと。暗黙のスコープというものはない。ほとんどの場合これは ランタイムエラーになる。いらいらするが、しばらくすれば慣れると思う。
6. return を忘れるな。 def twice(x): x+x のような書き方は格好いいし警告や例外も出さないのだが、 たぶんあなたのやりたかったことは直前に return をつけることだろう。 これは特にやっかいだ。なぜなら、lambda の中では return をつける ことは禁止されているからだ。にもかかわらず、意味的には lambda は return を含んでいる。
7. ひとつだけのタプルに気をつけろ。 タプルとはただの変更不能なリストであり、角カッコ [ ] ではなく丸カッコ ( ) によって表現される。 () は空のタプルであり、(1, 2) は 2つの要素をもった タプルなのだが、(1) はただの 1 なのだ。かわりに (1,) を使わなければならない。うげー。Damian Morton はわたしに、 タプルというものは丸カッコとともに表示されはするものの、実は カンマによって構成されていると考えれば意味が通ると教えてくれた。 カッコはただグループの曖昧さをなくすためにあるのだと。 この解釈によれば、1, 2 は 2つの要素をもったタプルで、 1, は 1つの要素をもったタプルで、カッコはタプルが 現れる場所によってそのときどきで必要だ、ということになる。 たとえば 2, + 2, は正しい表記だが (2,) + (2,) または (2, 2) を使ったほうがよりクリアーになるだろう。
8. ある種の式に気をつけろ。 dict[key] は key が存在しないときは KeyError 例外を 発生させることに注意。Lisp のハッシュテーブルを使っていたユーザなら nil を期待するところだ。この例外を捕捉するか、dict.has_key(key) や key in dict、あるいは dict.get(key) を使うべし。
9. Python は Lisp-1 である。 これが意味するところは、 Python は Scheme のように ひとつの名前空間を関数と変数に使っているということだ。 Common Lisp のように別々にはしていない。たとえば:

   def f(list, len): return list((len, len(list)))      ## まずい Python
   (define (f list length) (list length (length list))) ;; まずい Scheme
   (defun f (list length) (list length (length list)))  ;; 正しい Common Lisp
   

   このことはフィールドとメソッドにもあてはまる。 メソッドと同じ名前のフィールドを使ってデータ抽象をおこなうことはできない:

   class C:
       def f(self): return self.f  ## まずい Python
       ...
   

10. Python 2.1 以前は字句的スコープ (lexical scope) をサポートしていない。 バージョン 2.1 以前の Python では、各モジュールには 2つの 変数スコープしかなかった。グローバルなスコープと、関数におけるスコープである。 2001年 4月にリリースされた Python 2.1 では、 "from __future__ import nested_scopes" を実行することにより 第 3 のスコープである、ブロック中での入れ子になった変数スコープを使うことができる。 Python 2.2 では、この動作はデフォルトになっている。これは望むところだろう。 これで、外側の変数を参照する閉包をつくることができる。外側の変数の内容を 変更したい場合、選択肢はすこししかなく、どれも少々手がかかる。 変数を 1要素のリストでくるんでおくのはひとつの方法だ。

    def sum(items):
        total = [0.0]
        def f(x): total[0] = total[0] + x
        map(f, items)
        return total[0]
    >>> sum([1.1, 2.2, 3.3])
    6.6
    

    ここでは lambda を使うことはできないということに注意してほしい。 なぜなら lambda 関数の本体部分は単一の式でなければならず、ステートメントは 使えないからだ。これ以外の選択肢は関数のかわりにオブジェクトを使うことだが、 これはいささか冗長すぎる。しかし冗長さというのはそれを見る者の内にあるものだ。 Lisp プログラマなら (lambda (x) (* k x)) がまっとうなやり方だと思うだろうが、 Smalltalk のプログラマはこれでも多すぎると考える。彼らは [:x | x * k] を 使うのだ。これにひきかえ Java プログラマは、次のようにバカバカしいくらい 冗長な inner class 表記を持ちだしてくるだろう。

    new Callable() {
        public Object call(Object x) {
            return x.times(k)
        }
    }
    

11. Python の文字列は Lisp のシンボルとは全然ちがう。 Python は、モジュールやクラス中に存在するハッシュテーブルに 文字列を intern させることでシンボルの検索をおこなっている。 つまり obj.slot と書くと、Python は実行時に クラス obj のハッシュテーブルで文字列 "slot" を 検索する。また、Python はユーザのコード中にある x = "str" などの ようないくつかの文字列も intern する。だが変数らしく見えない文字列は intern されない。たとえば x = "a str" は intern されない (このことを指摘してくれた Brian Spilsbury に感謝)。
12. Python にはマクロがない。 Python はプログラムの抽象的な構文木にアクセスする機能を もっているが、これはなにもびっくりするようなことではない。 このモジュールの長所は理解するのが簡単だということで、 5行ほどのコードを使って、5分かそこらで次のようなものを手にすることができた:

    >>> parse("2 + 2")
    ['eval_input', ['testlist', ['test', ['and_test', ['not_test', ['comparison',
     ['expr', ['xor_expr', ['and_expr', ['shift_expr', ['arith_expr', ['term', 
      ['factor', ['power', ['atom', [2, '2']]]]], [14, '+'], ['term', ['factor',
       ['power', ['atom', [2, '2']]]]]]]]]]]]]]], [4, ''], [0, '']]
    

    この結果にはかなりがっかりした。Lisp なら、これと同等の構文木は (+ 2 2) である。この構文木なら誰にでも使えるが、 Python のこんな構文木をいじれるのは本当のエキスパートだけだろう。 文字列を連結してマクロに似たようなものは作れるかもしれない。 それでもその機能は言語のその他の部分と統合されていないので、 実際には使えない。Lisp では、マクロにはおもに 2つの目的があった: 新しい制御構造をつくることと、ある問題に特化したカスタム言語を つくることである。前者は、単純に Python では実現できない。 後者については、問題に特化した形式の データ を Python で つくることによって実現できる。下の例で、わたしは辞書用の組み込み文法と、 文字列を解析してデータ構造に変換する前処理をつかって、文脈自由文法を定義している。 この組み合わせはほとんど Lisp のマクロと同じくらいに便利だが、 たとえば論理プログラミング言語のコンパイラを書くなどの より複雑なタスクは、Lisp ではやさしいが Python ではむずかしい。

(defparameter *grammar*
  '((sentence -> (noun-phrase verb-phrase))
    (noun-phrase -> (Article Noun))
    (verb-phrase -> (Verb noun-phrase))
    (Article -> the a)
    (Noun -> man ball woman table)
    (Verb -> hit took saw liked))
  "よくある英語の文法のサブセット。")

(defun generate (phrase)
  "ランダムな文あるいは句を生成する。"
  (cond ((listp phrase)
         (mappend #'generate phrase))
        ((rewrites phrase)
         (generate (random-elt (rewrites phrase))))
        (t (list phrase))))

(defun generate-tree (phrase)
  "ランダムな文あるいは句を、完全な構文木つきで生成する。"
  (cond ((listp phrase)
         (mapcar #'generate-tree phrase))
        ((rewrites phrase)
         (cons phrase
               (generate-tree (random-elt (rewrites phrase)))))
        (t (list phrase))))

(defun mappend (fn list)
  "リストの各要素に関数 fn を適用させた結果を append する。
  mapcon のようなものだが、nconc のかわりに append を使っている。"
  (apply #'append (mapcar fn list)))

(defun rule-rhs (rule)
  "生成規則の右辺。"
  (rest (rest rule)))

(defun rewrites (category)
  "このカテゴリに対する可能な書き換えのリストを返す。"
  (rule-rhs (assoc category *grammar*)))

from whrandom import choice

def Dict(**args): return args

grammar = Dict(
        S = [['NP','VP']],
        NP = [['Art', 'N']],
        VP = [['V', 'NP']],
        Art = ['the', 'a'],
        N = ['man', 'ball', 'woman', 'table'],
        V = ['hit', 'took', 'saw', 'liked']
        )

def generate(phrase):
    "ランダムな文あるいは句を生成する。"
    if is_list(phrase):
        return mappend(generate, phrase)
    elif phrase in grammar:
        return generate(choice(grammar[phrase]))
    else: return [phrase]
    
def generate_tree(phrase):
    "ランダムな文あるいは句を、完全な構文木つきで生成する。"
    if is_list(phrase):
        return map(generate_tree, phrase)
    elif phrase in grammar:
        return [phrase] + generate_tree(choice(grammar[phrase]))
    else: return [phrase]

def mappend(fn, list):
    "リストの各要素に関数 fn を適用させた結果を append する。"
    return reduce(lambda x,y: x+y, map(fn, list))
    
def is_list(x): return type(x) is type([])

> (generate 'S)
(the man saw the table)

>>> generate('S')
['the', 'man', 'saw', 'the', 'table']

>>> string.join(generate('S'))
'the man saw the table'

Python のコードに含まれている文法が Lisp のそれより汚なくなっているのが いやだったので、Python で構文解析器を書く (あとでこれにはフリーで 使用可能なものがすでにいくつかあることを知った) か、組み込み演算子を オーバーロードすることを考えた。後者のアプローチは、わたしが 論理式を表現・操作するためにつくった Expr クラス などで実現可能である。しかし今回のアプリケーションではよくある その場かぎりのアドホックな生成規則パーサでいいだろう。つまり 生成規則は '|' で区切られた候補のリストからなり、各候補は ' ' で区切られた単語のリストになっている、というように。そして Lisp でできたプログラムを翻訳するよりも Python の慣習にしたがった 文法プログラムにしたら、次のようなものができあがった:

"""与えられた文法からランダムな文を生成するモジュール。文法は
S = 'NP VP | S and S' のような形式のエントリで構成される。各エントリは
{'S': [['NP', 'VP'], ['S', 'and', 'S']]} のような形式に変換され、
これはそれぞれの外側の大きなリスト (top-level lists) からどれか
ひとつの書き換え候補がランダムに選ばれることを示す。そして、選ばれた
リストの内側にある各要素 (each element of the second-level list) が
書き換えられる。その要素が文法中になければ、各要素はそれ自身に書き
換えられる。関数 rewrite および rewrite_tree はそれぞれ単語のリストと、
結果が追加されるアキュムレータ (空リスト) を引数としてとるようになっている。
関数 generate および generate_tree は、rewrite と rewrite_tree への
簡便なインタフェイスを提供しており、これは文字列 (デフォルトは 'S') を
入力として受けとる。"""

import random

def make_grammar(**grammar):
  "シンボルから各書き換え候補へのマッピングをおこなう辞書を作成する。"
  for k in grammar.keys():
    grammar[k] = [alt.strip().split() for alt in grammar[k].split('|')]
  return grammar
  
grammar = make_grammar(
  S = 'NP VP',
  NP = 'Art N',
  VP = 'V NP',
  Art = 'the | a',
  N = 'man | ball | woman | table',
  V = 'hit | took | saw | liked'
  )

def rewrite(words, into):
  "リスト中の各単語を文法中のランダムなエントリで (再帰的に) 置き換える。"
  for word in words:
    if word in grammar: rewrite(random.choice(grammar[word]), into)
    else: into.append(word)
  return into

def rewrite_tree(words, into):
  "単語のリストを、文法から選ばれたランダムな木で置き換える。"
  for word in words:
    if word in grammar:
      into.append({word: rewrite_tree(random.choice(grammar[word]), [])})
    else:
      into.append(word)
  return into

def generate(str='S'):
  "str に含まれている各単語を文法中のランダムなエントリで (再帰的に) 置き換える。"
  return ' '.join(rewrite(str.split(), []))

def generate_tree(cat='S'):
  "文法を使ってカテゴリ cat を書き換える。"
  return rewrite_tree([cat], [])

Japanese Translation Changes:
公開。(2002/10/13)
深町 和哉さん, Shiro Kawai さん, 木村 栄伸さん から指摘をいただき修正しました。(2002/10/27)
Yusuke Shinyama <yusuke at cs . nyu . edu>