L2 Lisp の Python 2.5 & 3.0 への移植

2008.5.23 - 2008.6.3 (鈴)

1. はじめに

Ruby による Little Lazy Lisp インタープリタの実装を Python に移植した。 Ruby と Python でのプログラムの長さの差を確かめるために改行の入れ方を整理するなど,Ruby による実装も改めた。 Ruby による実装を 7.0 版,Python による実装を 7.1 版とする。 両者は,ruby-send 関数 (前々回 §3) と python-apply 関数 (本稿 §3.5) などホスト言語との相互作用にかかわる個所を除いて,同一の仕様であることを意図している。

5月22日作成の 7.1 版 は,本稿 §3.5 と 旧 §3.6 に関係する2箇所の修正により 5月27日作成の 7.1a 版 に, さらに旧 §3.6 に関係する2箇所の修正により 5月30日作成の 7.1c 版に差し替えられました (7.1b 版はありません)。以下,7.1 版は 7.1c 版と読み替えてください。

6.1 版とは下記の非互換性がある。

ただし,t への代入禁止を実現する方法は Emacs Lisp と異なる。 Emacs Lisp と異なり,t はもはやシンボルではない。 ホスト言語の真値 (Ruby ならば true) がそのまま使われる。 しかし,本 Lisp には symbolp のようなシンボルを判定する述語はないから,この Emacs Lisp との非互換性を Lisp プログラムが直接知ることはない。

もしも symbolp が必要なときは,ruby-send や python-apply を使えば定義できます。 どちらを使うかの場合分けには,大域変数 *version* (前回 §1) の値を見ます。

2. Ruby による実装の変更点

L2Lisp.rb 6.1 版から 7.0 版への変更点は次の四つにまとめられる。

  1. 数リテラルでの下線の禁止:
    Ruby 関数 IntegerFloat をラップするメソッド Reader#_to_intReader#_to_float を設け, 与えられた引数に下線文字が含まれるかどうかを陽に検査するようにした。

  2. Lisp 値 t の内部表現としての true:
    Lisp 値 t の内部表現として Ruby の true をそのまま用いるようにした。 このことは t の代入禁止を実現し,わずかながら実装を簡素化した。 例えば,今まで
          @symbol[:atom] = proc {|x| (Cell === x) ? nil : :t}
    
    だった Lisp 組込み関数 atom の実装が
          @symbol[:atom] = proc {|x| !(Cell === x) || nil}
    
    になった。

  3. バグの修正:
    スペシャルフォーム catchunwind-protect を実装する Interp#eval_catch_bodyInterp#eval_unwind_protect_body にあったバグを修正した。 スペシャルフォームを構成するリストの末尾が nil でない場合に対して例外を送出するとき,未定義の変数 x を誤って参照していた。

  4. コーディング書法などの整理:
    コーディングに then を使わず,セミコロンが必要な箇所は原則として改行するようにした。 これは Python でコロンの直後に必ず改行することと概ね同等である。 これにより一般的な可読性の向上が期待されるほか,Python とのコード量の比較がより妥当なものになる。 ただし,Ruby には if/unless 修飾子など記法上のバリエーションがあるが, どれかに機械的に統一するのではなく,その都度,最も読みやすいと判断したものを選択した。 したがって,完全な客観性はなく,その妥当性は最終的には読者が各自判断すべきものである。

Interp#eval_catch_body の変更前 (6.1 版) と変更後 (7.0 版) のコードを示す。 上記 3. と 4. について確認されたい。

変更前:

    def eval_catch_body(j)      # j = (tag body...)
      (Cell === j) or raise EvalError.new('tag and body expected', j)
      tag = eval(j.car)
      begin
        result = nil
        case j.cdr
        when Cell then j.cdr.each {|x| result = eval(x)}
        when nil
        else raise ProperListExpected, x
        end
        return result
      rescue Thrown => th
        if tag == th.tag then return th.value else raise end
      rescue EvalError => ex    # 一般の評価時例外の捕捉
        if tag == S_ERROR then return ex else raise end
      end
    end

変更後:

    def eval_catch_body(j)      # j = (tag body...)
      (Cell === j) or raise EvalError.new('tag and body expected', j)
      tag = eval(j.car)
      begin
        result = nil
        case k = j.cdr
        when Cell
          k.each {|x| result = eval(x)}
        when nil
        else
          raise ProperListExpected, k
        end
        return result
      rescue Thrown => th
        return th.value if tag == th.tag
        raise
      rescue EvalError => ex    # 一般の評価時例外の捕捉
        return ex if tag == S_ERROR
        raise
      end
    end

3. Python への移植

L2Lisp.py は L2Lisp.rb の Python への移植である。 Mac OS X 10.4.11 の Python 2.5.2 と Python 3.0a5 のもとで作成し, Windows ネイティブの Python 2.5, 2.5.1 や Cygwin, Mac OS X 10.5.3 上の Python 2.5.1 で動作を確認した。 使い方は L2Lisp.rb 7.0 版と同様である。 下記は,前回の「農夫と狼と山羊とキャベツ」の問題を L2Lisp.py で解いた例である。

$ time ./L2Lisp.py farmer-and-wolf-etc1.l
((n n n n) (s n s n) (n n s n) (s s s n) (n s n n) (s s n s) (n s n s) (s s s s)
)
$ 

3.1 Python 2.5 と Python 3.0 のはざまで

現在,Python は,Python 2.5 から Python 3.0 への大きなバージョンの移行期にさしかかり始めている。 Python の現行版は Python 2.5 の第2バグ修正リリースである Python 2.5.2 である。 一方,開発者向けに Python 3.0 の第5アルファ・リリースである Python 3.0a5 が公開されている。 いくつか抜本的な改正が行われているため,Python 2.5 と Python 3.0 は非互換である。

バージョン間の移行を助けるための中間的な Python 2.6 は,開発者向けに第3アルファ・リリース Python 2.6a3 が公開されている。 Python 2.5 と Python 2.6,または Python 2.6 と Python 3.0 でプログラムを共通化できるため,これによる数年がかりでの移行が予定されている。

しかし,ここでは無謀にも,Python 2.6 に頼ることなく,今このときの現行版である Python 2.5.* と, 初秋には正式版がリリース (PEP 361) される Python 3.0 の両方で動くように移植することを試みた。 意外なことに,両者の非互換性が不利に働くことはほとんどなかった。

それでも一つだけ局所的に閉じ込められない問題があった。 それは tryexcept 文での例外オブジェクトの参照である。

一般に SomeException クラスの例外オブジェクトを変数 ex に捕捉するために,Python 2.5 までは except SomeException, ex: … と書くが,Python 3.0 では except SomeException as ex: … と書く。 構文レベルで非互換なため,本移植では,両者の共通サブセットとして,変数 ex を指定しない except SomeException: … を採らざるを得ない。

さいわい,その場合でも, except 節で捕捉された例外オブジェクトは,組込みモジュール sys の関数 exc_info() の戻り値の (0 から数えて) 第1要素として参照できる。 つまり,上記に示した Interp#eval_catch_body は下記のように翻訳できる。

    def __eval_catch_body(self, j): # j = (tag body...)
        if not isinstance(j, Cell):
            raise EvalError('tag and boy expected', j)
        tag = self.eval(j.car)
        try:
            result = NIL
            k = j.cdr
            if isinstance(k, Cell):
                for x in k:
                    result = self.eval(x)
            elif k is not NIL:
                raise ProperListExpected(k)
            return result
        except Thrown:
            th = sys.exc_info()[1]
            if tag == th.tag:
                return th.value
            else:
                raise
        except EvalError:       # 一般の評価時例外の捕捉
            if tag is S_ERROR:
                return sys.exc_info()[1]
            else:
                raise

3.2 Cons セル・クラスの移植とイテレータ

Lisp の nil の内部表現として,Ruby による処理系では同名のオブジェクト nil を使った。 Python で Ruby の nil に相当する値は,一般に None である。 しかし,本移植では空のタプルを nil として使うことにした。

NIL = ()                        # Lisp の nil 値

本移植での Cons セルのクラス Cell の実装 (部分) を下記に示す。 これは object を基底クラスとする,いわゆる "新しいスタイル" のクラス定義である。 Python 3.0 では基底クラスを省略しても "新しいスタイル" のクラスになるが,ここでは Python 2.5 にも対応するため,陽に object を指定した。 __slots__ を定義して,インスタンス変数を carcdr に限定する。 __slots__ は "新しいスタイル" のクラスにだけ有効な属性であり, 意図しないインスタンス変数の誤代入の検出に役立つほか,インスタンス変数の動的追加のための辞書 __dict__ が個々のオブジェクトに作られるのを防ぎ,効率の向上に貢献する。

class Cell (object):
    "cons セル"
    __slots__ = 'car', 'cdr'

    def __init__(self, car, cdr):
        "Lisp の (cons car cdr) に相当"
        self.car = car
        self.cdr = cdr

    def __repr__(self):
        return 'Cell(%r, %r)' % (self.car, self.cdr)

    def __str__(self):
        return lstr(self)

    def __iter__(self):
        "Lisp のリストとして各要素を与える"
        j = self
        while isinstance(j, Cell):
            yield j.car
            j = j.cdr
            if isinstance(j, Promise):
                j = j.deliver()
        if j is not NIL:
            raise ProperListExpected(j)

    def __len__(self):
        "Lisp のリストとしての長さ"
        c = 0
        for e in self:
            c += 1
        return c

    def _lrepr(self, print_quote, reclevel, printed):
        "関数 lstr のための補助メソッド"
        if self in printed:

Ruby の each メソッド (第4回 §3.2) に相当するものは __iter__ メソッドである。 このメソッドにより,任意の Cell オブジェクト x が Python の 列 (sequence) オブジェクトのように扱われる。 例えば tuple(x) は, Lisp のリストとしての各要素をそのまま要素とするタプルを構築する。

x の Lisp のリストとしての長さを求めるために len(x) を実行したとき, Python 内部では,x を仮引数 self の値として __len__ メソッドが呼び出される。 同メソッドは for c in self: c += 1 によるループで要素数を c にカウントしているが,この for 文でも暗黙のうちに __iter__ メソッドが使われる。

関数 fn を Python の任意の列オブジェクト x の要素にそれぞれ適用し, その結果の値からなる Lisp のリストを作成する mapcar 関数は,次のように定義される。 ここで Lisp の空リスト nil の内部表現が空のタプルであることを思い出されたい。 空タプルは列オブジェクトの一つであり,for 文をゼロ回繰り返すから, 特別な場合分けなしに mapcar の第2引数として Lisp のリストを与えることができる。

def mapcar(fn, x):
    "Lisp の mapcar 関数に相当"
    z = y = Cell(NIL, NIL)
    for e in x:
        y.cdr = Cell(fn(e), NIL)
        y = y.cdr
    return z.cdr

3.3 Symbol クラスの実現

Ruby と異なり,Python には組込みの Symbol クラスがない。 本移植では,Java による Symbol クラスの実装 (第6回 §4.1) にならって Symbol を実現した。 __new__ メソッドを使ってオブジェクトの割付け方法をカスタマイズできるから, Java と異なり,同一の印字名に対する一意性の実現をクラス内部に隠蔽できる。

SYMBOL_MAP = {}           # 印字名からシンボルへ一意に変換するための表
SYMBOL_LOCK = threading.Lock()  # シンボル構築時の排他ロック


class Symbol (object):
    "シンボル: これ自体には変数としての値はない"
    __slots__ = '__name'

    def __new__(cls, name):
        "シンボルの印字名を引数として構築する。印字名が同じなら同じ値を返す"
        SYMBOL_LOCK.acquire()
        try:
            self = SYMBOL_MAP.get(name)
            if self is None:
                self = object.__new__(cls)
                self.__name = name
                SYMBOL_MAP[name] = self
            return self
        finally:
            SYMBOL_LOCK.release()

    def __repr__(self):
        return 'Symbol(%r)' % self.__name

    def __str__(self):
        return self.__name


S_APPEND = Symbol('append')
S_CATCH = Symbol('catch')
S_COND = Symbol('cond')
S_CONS = Symbol('cons')
S_DELAY = Symbol('delay')
S_EOF = Symbol('#<eof>')
S_ERROR = Symbol('*error*')
S_LAMBDA = Symbol('lambda')
S_LIST = Symbol('list')
S_MACRO = Symbol('macro')
S_PROGN = Symbol('progn')
S_QUOTE = Symbol('quote')
S_REST = Symbol('&rest')
S_SETQ = Symbol('setq')
S_UNWIND_PROTECT = Symbol('unwind-protect')

3.4 関数の部分適用,それとも…?

Ruby 版の実装で,Lisp のラムダ式の仮引数並びから構築した名前表 table にしたがってラムダ式の本体 j を走査 (scan) し,そこに出現する仮引数をその内部表現に置き換える手続きは,下記のとおりである。

    def scan2(j, table)
      case j
      when Symbol, Dummy
        k = table[j]
        return (k.nil?) ? j : k
      when Arg
        k = table[j.symbol]
        return (k.nil?) ? Arg.new(j.level + 1, j.offset, j.symbol) : k
      when Cell
        return (j.car == :quote) ? j : LL.mapcar(j) {|x| scan2(x, table)}
      else
        return j
      end
    end

この scan2 は次のように Python に直訳できる (ただし,関数名は _scan に改めた)。

def _scan(j, table):
    if isinstance(j, (Symbol, Dummy)):
        k = table.get(j)
        return j if k is None else k
    elif isinstance(j, Arg):
        k = table.get(j.symbol)
        return Arg(j.level + 1, j.offset, j.symbol) if k is None else k
    elif isinstance(j, Cell):
        return j if j.car is S_QUOTE else mapcar(lambda x: _scan(x, table), j)
    else:
        return j

ここで mapcar 関数の第1引数 lambda x: _scan(x, table) は,_scan 関数に table を与えた部分適用 (partial application) の,Python のラムダ式による表現である。 Python 2.5 以降,functools モジュールの partial により関数の部分適用が直接サポートされている (PEP 309)。 引数の順序をかえるか,または下記のようにキーワード引数を使うことにより,この partial を利用できる。このとき,ラムダ式の仮引数 x がコードから消える。


lambda x: _scan(x, table)
  ↓
partial(_scan, table=table)

しかし,本移植では,結局,下記のようにした。 table は,実質的な処理をになう入れ子関数 scan にとって自由な自動変数である。 これは Pascal と Scheme に受け継がれている Algol (第1回 §4) 的な解法である。

def _scan(j, table):
    def scan(j):
        if isinstance(j, (Symbol, Dummy)):
            k = table.get(j)
            return j if k is None else k
        elif isinstance(j, Arg):
            k = table.get(j.symbol)
            return Arg(j.level + 1, j.offset, j.symbol) if k is None else k
        elif isinstance(j, Cell):
            return j if j.car is S_QUOTE else mapcar(scan, j)
        else:
            return j
    return scan(j)

必ずしも,この方法が現在の Python にとって最も効率が良いわけではない。 実際,この部分を上記三つのどの方法で書いても処理系全体の性能に大差はなかった。 これを選んだのは,伝統的な構文要素だけで自然に書けるからである。

ここで Ruby には,波括弧と doend のような単純な同義語の言い換えを除き,事実上,書き方のバリエーションがないのに比べ,Python が異なった三つの流儀で同じ問題を表現できることに注意してください。 いわゆる TIMTOWTDI (There is more than one way to do it) のスローガンを意味のあるかたちで実現しているのがどちらであるかは明らかです。 TIMTOWTDI のような性質は,作為的に色々な構文を用意しなくても, 言語そのものの表現力の帰結として備わるものだ,と言えそうです。

3.5 Python との相互作用

Ruby 版の実装がそうであるように,本移植もモジュールとしてホスト言語 (この場合は Python) から利用できる。

下記の例では,Lisp インタープリタ i が持つシンボル表 i.symbol に, Python 関数 hex を,Lisp シンボル Symbol('hex') をキーとして登録している。 そして,Lisp の S 式 (hex 1638) を文字列としてメソッド i.run に与え,評価した結果である文字列 '0x666' を得ている。

>>> import L2Lisp as LL
>>> i = LL.Interp()
>>> sy_hex = LL.Symbol("hex")
>>> hex
<built-in function hex>
>>> sy_hex
Symbol('hex')
>>> i.symbol[sy_hex] = hex
>>> i.run("(hex 1638)")
'0x666'
>>> 

§3.2 で述べたように,Lisp の Cons セルは,モジュールに属する Cell クラスのインスタンスとして表現される。

>>> cons = LL.Cell
>>> e = cons(sy_hex, cons(1638, LL.NIL))
>>> e
Cell(Symbol('hex'), Cell(1638, ()))
>>> print(e)
(hex 1638)
>>> 

Cons セルで構築した S 式は,メソッド i.eval を使って評価できる。

>>> i.eval(e)
'0x666'
>>> 

ただし,実際に S 式を構築するときは便宜関数 llist (lisp list の意) を使うとよい。

>>> cdr = LL.Symbol("cdr")
>>> quote = LL.Symbol("quote")
>>> lst = LL.llist
>>> e = lst(1, 2, 3)
>>> e
Cell(1, Cell(2, Cell(3, ())))
>>> lst(quote, e)
Cell(Symbol('quote'), Cell(Cell(1, Cell(2, Cell(3, ()))), ()))
>>> print(lst(quote, e))
'(1 2 3)
>>> i.eval(lst(cdr, lst(quote, e)))
Cell(2, Cell(3, ()))
>>> 

この例では S 式 (cdr '(1 2 3)) を構築し,i.eval で評価して,Lisp のリスト (2 3) つまり Cell(2, Cell(3, ())) を得ている。

一方,Lisp から Python を利用するために,次の四つの組込み関数を用意した。

  1. (python-exec s)
    文字列 s を Python の文または文の並びとして評価し,nil を返す。
  2. (python-eval s)
    文字列 s を Python の式として評価し,結果の値を返す。
  3. (python-apply fn a k)
    Python の式 fn(*a, **dict(k)) を実行し,結果の値を返す。
  4. (python-self)
    Python のオブジェクトとしてのインタープリタ自身を返す。

普通は python-exec でモジュールの import や関数の定義を行い,python-eval でその関数を得て, python-apply でそれを Lisp から呼び出す。 典型例は,初期化 Lisp スクリプト PRELUDE に含まれる printf の定義である。

(python-exec
 (concat
  "import sys\n"
  "def printf(fs, *args):\n"
  "  sys.stdout.write(fs % args)\n"))
(setq _printf (python-eval "printf"))
(defun printf (fs &rest args)
  (python-apply _printf (cons fs args) nil))

Python の名前空間を汚染しないように,python-execpython-eval は,Python の文や式を評価するとき,共通の専用環境を使う。 この環境はインタープリタ・オブジェクトごとに空の辞書として作られる。 上記の例で import sysdef printf は,この環境で行われている。

Lisp のリストは,Cell クラスの __iter__ メソッドにより Python の「列」として扱われるから, python-apply の位置引数として渡されたときは自動的にタプルに変換される。 下記は Lisp から printf を呼び出した例である。

> (printf "%04d: %s\n" 1 "Now is the time for all good men to come to the aid")
0001: Now is the time for all good men to come to the aid
None
> 

4. 速度の比較

MacBook Pro 15" (Mac OS X 10.4.11, Core Duo 2GHz, 1GB) を使って, Ruby 1.8.6 と Python 2.5.2 で Lisp の速度を測ると, (tak 18 12 6) (第5回 §7) にかかる時間が前者が約 8.3 秒,後者が約 7.6 秒であり,Python 版が約 1.1 倍高速である。 同様に Ruby 1.9.0-1 と Python 3.0a5 で比べると, 前者が約 13.8 秒,後者が約 12.6 秒であり,Python 版が約 1.1 倍高速である。

同マシンの Ruby 1.8.6 と Python 2.5.2 について同様に (length (nqueens 8)) (第5回 §7) の所要時間を比較すると,約 21.9 秒と約 20.1 秒であり,やはり Python 版が約 1.1 倍高速である。

しかし,さらにマシンをかえて試行したところ,当惑させられるような結果が得られた。

PowerBook 12" (Mac OS X 10.4.11, PowerPC G4 1GHz, 768MB) で Ruby 1.8.6 と Python 2.5.2 について (tak 18 12 6) の所要時間を測ると,約 51.1 秒と約 21.5 秒であり,Python 版が約 2.4 倍高速である。 (length (nqueens 8)) については約 127.9 秒と約 56.4 秒であり,Python 版が約 2.3 倍高速である。

一方,別の MacBook Pro 15" (Mac OS X 10.5.3, Core 2 Duo 2.5GHz, 4GB) で Ruby 1.8.6 と Python 2.5.1 (ともに OS 標準添付) について (tak 18 12 6) の所要時間を測ると,約 6.5 秒と約 6.4 秒である。 (length (nqueens 8)) については約 17.0 秒と約 16.9 秒である。 1% 前後だけ Python が高速だが,事実上,両者の速度はほぼ同じといってよい。

PowerPC で Ruby が遅い理由は不明だが,それよりも驚くべきことは, 最近のマシンを使って今の Ruby と Python で Lisp インタープリタを走らせたとき, 気味が悪いほど似た性能を両者が示したことである。

読者自ら確認できるとおり,スクリプト・ファイル L2Lisp.rb と L2Lisp.py になんら作為的な速度調整はありません。 Ruby 1.8.* と Python 2.5.* の内部実装の違いやスクリプトの複雑さを考えると,信じがたい偶然の一致です。 もしも偶然の一致でなければ,あるいは例えば,似た演算ならば CPU のキャッシュに収まるかどうかが速度の違いを決める,というようなことかもしれません。

5. おわりに

Little Lazy Lisp の Ruby による実装を整理し,また Python に移植した。 この移植では Python 2.5 と Python 3.0 の両方の言語仕様を満たすことに成功した。

Ruby 版の実装と Python 版の実装を比較すると, 簡単に測った限りでは,最近のマシンのもとで驚くほど速度に差がないことが分かった。 一方,プログラムの行数は Ruby 版が約 3 % だけ少ない。 本稿で示した例からも読み取れるように,Ruby は,構文を閉じる end のために行数が余分にかかるが, 簡潔な記述を可能にする様々な構文要素にはそれを打ち消す効果がある (ここでは言語の習得にかかるコスト等の議論はひとまず措く)

このように,今日では,この Lisp 実装のために必要なプログラムの規模と達成される性能から見る限り,Python と Ruby はほぼ互角であり,どちらにも特に優位性はない。 Python と Ruby のどちらが良いかは (より定量化困難な) 他の観点から考える必要がある。

この帰結は,§3.4 で示した Python の優れた TIMTOWTDI 性とともに,一般的な通説を覆すものかもしれません。 しかし,結論にはまだ早いおそれがあります。なぜなら,Python には Psyco というコンパイラがあるからです。


付録: Psyco コンパイラによる L2Lisp.py の高速化


次回へつづく


Copyright (c) 2008 OKI Software Co., Ltd.