L2Lisp.rb: Ruby への移植

2007.7.7 (2010.8.11 リンク修正) (鈴)

1. はじめに

標準 Pascal で書かれた L2Lisp 3.0 版Ruby および JRuby に移植した。 文字列の表現方法など Lisp としての仕様にいくつかの非互換性があるから,版数は 4 とする。 Ruby の低速さにより速度は大きく低下したが, Ruby の強力さにより評価時例外の捕捉や無限多倍長整数のサポート, 組込み関数の拡張の容易さなど,それ以外の実用性は向上した。 プログラムの大きさは概ね半減した。 本稿は処理系の要約と移植の要点を述べる。 処理系自体の解説については CodeZine に公開する記事を参照されたい。

2. 処理系の要約

L2Lisp 4.1 版は Ruby 1.8.2 以降 (JRuby 1.0 を含む) で動作する。 基本的には同 4.0 版と同じだが, cons セルに対しイテレータを定義するなど,より Ruby らしいプログラムとした。 構成ファイルは L2Lisp.rb 1本だけである*1

*1: 標準 Pascal と異なり,Ruby は必ずしもプログラムを1本にまとめる必要はありません。 それどころか1個のクラスやモジュールを複数のファイルから構成することもできます。 1本にまとめたのは取り扱いの手軽さのためです。 Pascal 版では別ファイルだった初期化 Lisp スクリプト l2init も, 文字列定数として L2Lisp.rb にまるまる取り込んでいます。 とはいえ,現状ですでにやや長大すぎるきらいがあるのも事実です。 今後プログラムがもう一まわりか二まわり大きく成長したら, そのときは,ファイルの分割を考えなくてはならないでしょう。

下記のように無引数で起動すると対話セッションに入る。 この (tak 18 12 6) の計算は Pentium 4 3.2GHz, 1GB, Windows XP SP2, Cygwin 1.5.24-2 上の ruby 1.8.6 で約 13 秒かかる。 同環境の GNU Pascal による L2Lisp 3.0 版は起動および終了時間込みで約 0.2 秒で終わる (起動して終了するだけで約 0.1 秒かかるから,実質的に Ruby 版より約 100 倍高速である。 つまり,Ruby 版は約 100 倍遅い。他のいくつかのテストでも概ね同様の結果が得られている)。

$ ruby L2Lisp.rb
> (defun tak (x y z)
    (if (>= y x) z
      (tak (tak (- x 1) y z)
           (tak (- y 1) z x)
           (tak (- z 1) x y))))
tak
> (tak 18 12 6)
7
> 

コマンド行引数として Lisp スクリプトのファイル名を1個以上与えると,それらを順に実行する。 ただし,ハイフン1文字の引数は標準入力と解釈し,対話セッションに入る*2

*2: つまり,$ ruby L2Lisp.rb file1.l -$ python -i file1.py と同じく,与えられたスクリプトを実行してから,そのままその環境で対話セッションに入ります。 ruby 自体も $ irb -r file1.rb で一応は似たようなことができますが, ここの二つめの会話文で指摘されているように若干の不便さがあります。

L2Lisp.rb は他の Ruby プログラムからライブラリとして利用することもできる。 一部品として問題なく組み込めるように 大域的な名前空間に L2Lisp というモジュール名だけを定義する。 組込みクラス等の振舞は変更しない。

  require "L2Lisp"
  LL = L2Lisp
  i = LL::Interp.new                  # インタープリタ・オブジェクト構築
  i.symbol[:to_s] = proc {|x| x.to_s}              # 組込み関数追加
  r = i.run("(to_s 123)")                          # Lisp スクリプト実行
  p r                                              # "123" を表示
  e = LL::Cell.new(:to_s, LL::Cell.new(123, nil))  # (to_s 123) を手作り
  r = i.eval(e)                                    # (to_s 123) を評価
  p r                                              # "123" を表示

Lisp 値は次のように表現される。

Integer (Fixnum, Bignum) または Float のインスタンス
文字列 String インスタンス
シンボル Symbol インスタンス (大域変数値は Hash 値 L2Lisp::Interp#symbol に格納)
nil nil
cons セル L2Lisp::Cell インスタンス

L2Lisp::Interp インスタンスの irb (JRuby では jirb) での表示を簡潔にするため, L2Lisp::Interp#symbol の Hash オブジェクトは inspect を キーからなるリストの文字列表現を返す特異メソッドとして定義している。

$ jirb -r L2Lisp.rb
irb(main):001:0> i = L2Lisp::Interp.new
=> #<L2Lisp::Interp:0x1b77 @reader=#<L2Lisp::Reader:0xaed52c @rf=#<IO:0x2d7165>,
 @buf=[], @line=nil>, @environ=nil, @symbol=(cdr eq rplaca cadr if and atom < ca
ar print /= append car cons - = _append read / list defun <= * >= equal + copyri
ght assq summary defmacro > dump length *eof* not let terpri stringp progn null 
mapcar princ eval throw cddr while prin1 rplacd cdar or)>
irb(main):002:0> i.symbol
=> (cdr eq rplaca cadr if and atom < caar print /= append car cons - = _append r
ead / list defun <= * >= equal + copyright assq summary defmacro > dump length *
eof* not let terpri stringp progn null mapcar princ eval throw cddr while prin1 
rplacd cdar or)
irb(main):003:0> i.symbol[:cdr]
=> #<Proc:0x190ae9>
irb(main):004:0> 

上記の i.symbol の評価結果に見るように, 定義済みの大域的変数の一覧は L2Lisp::Interp#symbol のキーのリストとして得られる。 上記の i.symbol[:cdr] の評価結果に見るように, 組込み関数は Proc インスタンスとして表現され, 大域変数値として L2Lisp::Interp#symbol に格納される。 組込み関数はいつでも追加できる。

L2Lisp::Interp#initialize では下記のように car, cdr, cons, +, - 等を定義している。

      @symbol[:car] = proc {|x| (x.nil?) ? nil : x.car}
      @symbol[:cdr] = proc {|x| (x.nil?) ? nil : x.cdr}
      @symbol[:cons] = proc {|x, y| Cell.new(x, y)}
      @symbol[:'+'] = proc {|*x| x.inject(0) {|a, b| a + b}}
      @symbol[:'*'] = proc {|*x| x.inject(1) {|a, b| a * b}}

Ruby の機能により無限多倍長整数演算などが可能である。 例えば,自然数列生成関数 iota (FP, APL に由来する) と 高階関数 reduce (Common Lisp に由来する) から下記のように 100 の階乗を計算できる*3

$ cat iota.l
(defun iota (n)
  (let ((r nil))
    (while (< 0 n)
      (setq r (cons n r)
            n (- n 1)))
    r))
$ cat reduce.l
(defun reduce (f x)
  (if (null x)
      (f)
    (let ((r (car x)))
      (setq x (cdr x))
      (while x
        (setq r (f r (car x))
              x (cdr x)))
      r)))
$ ruby L2Lisp.rb iota.l reduce.l -
> (recude * (iota 100))
93326215443944152681699238856266700490715968264381621468592963895217599993229915
608941463976156518286253697920827223758251185210916864000000000000000000000000
> 
*3: この計算は一瞬で終わります。 Pentium 4 3.2GHz, 1GB, Windows XP SP2, Cygwin 1.5.24-2 上の ruby 1.8.6 で同様にして 10000 の階乗を求めると約 5 秒かかります。 while マクロが末尾再帰に展開されてスタックを消費しないとはいえ, cons セルで長さ 10000 のリストを実際に構築する という富豪的アプローチでもそれなりに動いているわけです。 付録も参照してください。

その他,特徴をまとめる。 EvalError などの名前はモジュール L2Lisp 内で定義される。

  1. 静的スコープをとる。
  2. 末尾呼出しの最適化を行う。
  3. 関数と変数の名前空間は同一である。
  4. シンボルの初期値は自分自身である。
  5. 関数 / と - は1個以上の引数をとる。
  6. (eval e) は e を大域的な環境で評価する。
  7. (eq x y) の結果は Ruby の x == y に従う。
  8. (read) は EOF に対して *eof* の大域変数値を返す。
  9. 評価時例外 EvalError は (catch *error* …) で捕捉できる。
  10. (lambda …) を評価すると再帰的に内部形式のラムダ式になる。
  11. (macro …) は大域的な環境でだけ評価できる。結果はマクロ式である。
    マクロ式はラムダ式と同様だが,適用時,引数を評価せず,適用結果を評価する。
  12. マクロ式で,自由なシンボルは捕捉されないが,マクロ引数は捕捉される。
  13. (macro …) 内の $ で始まるシンボルは (quote 内も含め) dummy symbol となる。
    そのマクロ式の中でだけ eq が成り立つ。(マクロ引数の捕捉防止用)
  14. (lambda …) を評価する時,最大 MAX_MACRO_EXPS 重だけ再帰的にマクロ展開する
    (非大域的に束縛されたマクロを除く)。残りは適用時に処理される。
  15. 印字する時,高々 MAX_EXPANSIONS 重だけ再帰的に印字済みリストを印字する。
  16. (dump) は内部状態である symbol キーのリストと字句的環境のペアを返す。
  17. その他の点では基本的に Emacs Lisp のサブセットである。

3. 移植の要点

Lisp 処理系の Ruby への移植では,まず,基本データ構造である cons セルの表現方法を決定する必要がある。

1個の cons セルを表現するために L2Lisp::Cell (以下,単に Cell。他も同様とする) のインスタンスを1個用いる方法の妥当性は必ずしも明らかではない。 1個の cons セルは典型的には 8 バイト固定長であるが, 一般のインスタンスはより多くのメモリを消費する。 一方,Ruby の Fixnum は即値で格納されるから, Array の1要素を car または cdr に割り当て,Pascal 版実装のように添え字で cons セル値を表現すれば, 1 cons セルあたり 8 バイトで実現できる。 しかし,この方法は,Pascal 版と同じくセル領域の管理を自力で行う必要がある。 Ruby に組込みの機能に頼らずに Ruby プログラムで処理を行う場合,Ruby の低速性の犠牲になるおそれがある。

どちらの方法が優れているかは自明ではない。 そこで,インスタンスを用いる方法と,配列の添え字を用いる方法で, それぞれ cons セルの初期化と生成を行うテスト・プログラム test1.rb (ファイル) と test2.rb (ファイル) を作成し,その実行時間を比較した。

テスト環境 test1.rb test2.rb
Pentium4 3.2GHz/Cygwin/Ruby 1.8.6 6.6 [s] 3.9 [s]
Core Duo 2.0GHz/OS X/Ruby 1.8.2 3.0 [s] 2.9 [s]
〃/OS X/Java 1.5.0_07/JRuby 1.0 6.8 [s] 7.4 [s]

この結果を見る限り,(驚くべきことに) 両者の実行速度に決定的な差はない。 したがってインスタンスを用いる方法を採ることにした。 これには下記の利点があり,多少の不利に十分引き合うと考えられる。

  1. メモリ管理を Ruby に任すことができる。 演算中にガーベジコレクトされないようにスタックに計算途中の値を明示的に置く必要はない。 そういった値を (Ruby が暗黙裏にスタックを用意する) ローカル変数にそのまま格納できる。
  2. Ruby が用意するデータ型をそのまま利用できる。データ変換の必要はない。 とりわけ,シンボル,nil,整数値を Ruby プログラムでそのまま利用できる。 副次的な効果として無限多倍長整数演算など Ruby の高水準な機能をそのまま享受できる。

移植作業の大部分を占める個々の手続きや関数の書き換え要領は,これにより具体化される。

3.1 全体の構成

ファイル L2Lisp.rb の構成を示す。

module L2Lisp
  
  class EvalError < RuntimeError  end # 評価時エラー
  class Thrown < EvalError  end       # Lisp が throw した状態
  class Cell  end                     # cons セルのクラス
  def str(x)  end                     # Lisp 式の文字列表現
  class Reader  end                   # Lisp 式の読込みクラス
  class Interp  end                   # Lisp インタープリタ
  PRELUDE = %q{  }                    # 初期化 Lisp スクリプト
end

if __FILE__ == $0                       # 主ルーチン
   lisp = L2Lisp::Interp.new
   lisp.run(STDIN) 
end

構成の要点を述べる。

  1. 名前の衝突を発生させずにプログラム部品として利用できるように定義をすべて module L2Lisp に入れ子にする。
  2. 標準 Pascal の手続き間 goto で実現していた評価時エラー処理と Lisp の大域脱出を Ruby の例外機構で実現する。前者のために EvalError を定義し,後者のために Thrown を定義する。 例外としてまとめることにより, ソース上,2行の追加で,(catch *error* …) による評価時エラーの捕捉を可能にできる。 EvalError と Thrown は派生関係にあり,評価時エラーと未捕捉の大域脱出を Ruby プログラムからまとめて処理できる。
  3. cons セル1個を Cell のインスタンス1個で表現する。 Pascal 実装の WriteExpression 手続きに相当する式の出力処理は Cell のメソッドとモジュール関数 str(x) で行う。
  4. 式の読込みに関する状態 (現在のトークンなど) を保持するため Reader クラスを設ける。 Pascal 実装では ReadExpression 手続きのローカル変数が,読込みに関する状態として入れ子の手続き間で共有されていた。 Ruby では,入れ子の手続きではなくクラスのメソッドとして,状態を共有する副プログラム群を構成する。
  5. Pascal 実装にあった大域的な状態を Interp インスタンスにまとめる。 これにより,必要ならば,複数の Lisp インタープリタをオブジェクトとして同時に設けることができる。
  6. L2Lisp.rb が単体の Ruby スクリプトとして実行されたときは __FILE__ == $0 が成立する。 このときは,Interp インスタンスを作り,run メソッドを使って, 対話的に標準入力(STDIN)から与えられた式を読み込み,評価し,そして表示する。

3.2 Cell クラスと str 関数

Cell クラスとモジュール関数 str(x) を下記に示す。 Cell クラスは Pascal 版実装の CellType に相当するが, Ruby のデータ型として自然に使えるようにイテレータ each を定義し, Enumerable を include する。 さらに irb 等で自然な印字表現がなされるように inspect メソッドを str(x) を利用して上書き定義する。

  class Cell
    include Enumerable
    attr :car, true
    attr :cdr, true

    def initialize(car, cdr)
      @car = car
      @cdr = cdr
    end

    def inspect
      return LL.str(self)
    end

    def each                    # Lisp の mapc に相当
      j = self
      begin
        yield j.car
        j = j.cdr
      end while Cell === j
      j.nil? or raise ProperListExpected, j
    end

ProperListExpected は EvalError の派生クラスである。 多数の箇所で真正のリストかどうかのチェックを行うから, エラーメッセージの記述の繰り返しを避けるための便宜として用意した。

    def length
      return inject(0) {|x, y| x + 1}
    end

inject は Enumerable で用意される。内部実装として Cell#each イテレータが使われる。

    def _repr(print_quote, reclevel, printed)
      if printed.has_key?(self)
        reclevel -= 1
        return ['...'] if reclevel == 0
      else
        printed[self] = true
      end
      case @cdr
      when nil
        s = LL.str(@car, print_quote, reclevel, printed)
        return [s]
      when Cell
        s = LL.str(@car, print_quote, reclevel, printed)
        t = @cdr._repr(print_quote, reclevel, printed)
        return t.unshift(s)
      else
        s = LL.str(@car, print_quote, reclevel, printed)
        t = LL.str(@cdr, print_quote, reclevel, printed)
        return [s, '.', t]
      end
    end
  end # Cell
  LL = L2Lisp                   # 便宜上の短縮名
  MAX_EXPANSIONS = 5            # 再帰的に印字する深さ
  # 引数の文字列表現を得る
  def str(x, print_quote=true, reclevel=MAX_EXPANSIONS, printed={})
    case x
    when Cell
      return '(' + x._repr(print_quote, reclevel, printed).join(' ') + ')'
    when Symbol then return x.to_s
    when String, Exception then return (print_quote) ? x.inspect : x
    else return x.inspect
    end
  end
  module_function :str

Ruby の (一見すると非直感的な) クセとして, モジュール内のクラスのメソッドからモジュール関数を呼び出すとき,モジュール名を接頭する必要がある。 煩雑さを避けるため,モジュール内でだけ通用する L2Lisp の短縮名 LL を定義し, LL.str(x) として呼び出す。 これには,将来,L2Lisp というモジュール名を変更するときの影響を局限する効果もある*4

*4: モジュールや名前空間を設けて名前の衝突を避けることは,息の長い,または規模の大きな開発で重要です。 いわゆるスクリプト言語でも Python などはそういった機能をごく初期からナチュラルにサポートしていました。
一方,Ruby 界隈では,伝統的に,その場で楽しく手みじかに書けることを重視し, 将来的な規模の増大に備えることについては (少なくとも表向きは) あまり重視していませんでした。 むしろ,いつか禍いしかねない組込みクラスの振舞の勝手な変更を,とっておきの技法としているほどです。
Ruby 言語の設計者自らが著作または監修をしている下記の3冊の文献は, この L2Lisp.rb のようなモジュール構成をあまり表立っては説明していません。 他の言語では空気のように意識せずにできることが,Ruby では, 資料の隅々まで見渡し,先人のスクリプトを調査し,試行を繰り返してようやく習得できる高等技術であるかのようです…。
  1. まつもと・石塚: オブジェクト指向スクリプト言語Ruby, アスキー, 1999.
  2. 原 (まつもと監修): Rubyプログラミング入門, オーム社, 2000.
  3. D. Thomas & A.HUnt (田和訳,まつもと監修): 達人プログラマーズガイド・プログラミングRuby, ピアソン・エデュケーション, 2001.
これらは古い資料ですが,現在でも状況はそれほど変わりません。 一般的な理解は,おそらく Perl, Python, Ruby の比較 が代表例です。これに対する 批判的意見 も,少なくとも大規模プログラムについては,module_function 等を使った 具体的な解決策を示していないため,建設的な改善に向かっていません。 実際には,Ruby でも十分 Python 等に匹敵する大規模プログラム作成能力があります。 本処理系がその具体例として役立てば幸いです。

循環リストで破綻しないように str(x) は reclevel 引数と printed 引数で 再帰呼出しを制御する。 LL.str(x) と呼び出したとき,これらの引数はデフォルト値で初期化される。 下記は jirb で Cell オブジェクトを構築し,代入によって循環リストを構成した例である。 Cell#inspect 経由で LL.str(self) が呼び出され,破綻なくリストが表示されている。

$ jirb
irb(main):001:0> require "L2Lisp"
=> true
irb(main):002:0> def cons(x, y) L2Lisp::Cell.new(x, y) end
=> nil
irb(main):003:0> a = cons(1, cons(2, 3))
=> (1 2 . 3)
irb(main):004:0> a.cdr.cdr = a
=> (1 2 1 2 1 2 ...)
irb(main):005:0> 

3.3 ラムダ式適用時の末尾呼出しの最適化

Pascal 版の実装では, スタックトップの式を評価する EvalTop 手続きへ,その入れ子手続き ApplyLambda から,手続き間 goto でジャンプすることによって,ラムダ式適用時の末尾呼出しの最適化をしていた。 しかし,このような手続き間 goto を行うためのフラグが立つのは,実際には, ApplyLambda 手続きが EvalTop 手続きから直接呼び出されている場合に限られる。

そこで,Ruby 版実装では,手続き間 goto を行う代わりに,未評価の式 と true のペア (実際は Array インスタンス) を返すようにした。 このとき,未評価の式に対してもう一度評価処理をループする。 通常の場合は,評価済みの式 と false のペアが返されるから, このときは評価済みの式をそのまま結果の値とする。

Ruby 版実装で Pascal の EvalTop 手続きに相当する Interp#eval メソッドの主要部を示す。

    def eval(x, can_lose_current_env=false)
      begin
        loop {
          case x
          
          when Cell
              case kar = x.car
              
              when Cell
                case kar.car
                when CLOSURE
                  args = get_args(x.cdr, true)
                  x, cont = apply_lambda(kar.cdr, args, can_lose_current_env)
                  return x unless cont
                
    end

eval メソッドの第1引数は,評価しようとする式である。 第2引数は,現在の環境を失ってよいかどうかのフラグである。 典型的には,評価しようとする式が (全体として) 末尾に位置するかどうかを意味する。 このフラグは apply_lambda メソッドに引き継がれる。

apply_lambda メソッドは,実引数リスト args と,ラムダ式が保持している環境リスト link から 新しい環境 @environ = Cell.new(args, link) を作成する。 それから,ラムダ式本体のそれぞれの式に対し再帰的に eval メソッドを (第2引数を false にして) 呼び出す。ただし,本体の最後の式だけは特別に扱う。

フラグが立っているときは元の環境を失ってよいから,@environ を新しい環境にしたまま, 本体最後の式を評価せずに true とペアにして eval メソッドに返す。

    # j = ((arity . link) . body)
    def apply_lambda(j, args, can_lose_original_env)
      body = j.cdr
      (Cell === body) or raise EvalError, 'body expected'
      j = j.car
      arity = j.car
      link = j.cdr
      if arity < 0
        
      end
      (args.length == arity) or raise EvalError, 'arity not matched'
      old_env = @environ              # 元の環境を退避する
      @environ = Cell.new(args, link) # 新環境に変更する
      begin
        while Cell === (d = body.cdr)
          eval(body.car, false)
          body = d
        end
        if can_lose_original_env then # ⇒ (典型的には) 末尾呼出し
          old_env = @environ          # 新環境のまま
          return body.car, true       # 戻った先で評価する
        else
          return eval(body.car, true), false
        end
      ensure
        @environ = old_env
      end
    end

フラグが立っていないとき,本体最後の式は,そのラムダ式の中だけでみれば末尾の式だから, 第2引数を true にして eval メソッドを再帰的に呼び出す。 こうすることによって,ラムダ式の中での末尾呼出しの最適化が行われる。 最後に @environ を元に戻す。

条件式 (cond …) の各節の末尾についても, 同様に未評価の式と true のペアを返すことによって最適化を行う。

4. おわりに

Ruby のオブジェクト指向的な型をそのまま Lisp の式の値の型として,Lisp インタープリタを移植した。 この方法は,自動的なメモリ管理機能をもつ他の (超) 高水準言語への移植に応用できると考えられる。 配列要素を高速に参照できる言語の場合,もとの Pascal 実装の直訳が好ましい可能性もある。 その場合でも,標準 Pascal の手続き間 goto の代替方法として,この移植が参考になると思われる。

5. 付録: L2Lisp での遅延評価

§2 では iota と reduce を定義して (FP や APL のように) 陽なループや再帰なしに階乗計算をした。

(reduce * (iota 100)) 
⇒ (reduce * (1 2 3 4 … 99 100))
⇒ (* (* … (* (* (* 1 2) 3) 4) … 99) 100)
⇒ 933262…0000

しかし,この方法では n の階乗を計算するために 長さ n のリストを構築する必要がある。 遅延評価を行えば,このような構築を無くすことができる。

Scheme にならって,式の評価を遅延する (delay exp) と 評価を強制する (force exp) を定義する。

;; (delay (+ 5 6)) -> (*delay* nil . (#<closure> (0 . env) (+ 5 6)))
(defmacro delay (exp)
  (list cons *delay* (list cons nil (list lambda nil exp))))

(delay exp) の結果,つまり約束 (promise) は *delay* で始まるリストとする。 リストの cadr 値は評価済みかどうかのフラグとする。フラグの初期値は未評価を意味する nil とする。 cddr 値は遅延評価された式を含むクロージャとする。

;; (setq a (delay (+ 5 6)))
;; (force a) -> 11
;; a         -> (*delay* t . 11)
(defun force (exp)
  (cond ((atom exp) exp)
        ((eq (car exp) *delay*)
         (if (cadr exp)
             (cddr exp)
           (rplacd exp (cons t ((cddr exp))))
           (cddr exp)))
        (t exp)))

(force exp) は exp が約束でなければそのまま exp を返す。 約束の cadr 値のフラグが真ならば,評価済みのはずの cddr 値を返す。 フラグが偽ならば,cddr 値を評価する。真フラグと評価値のペアで, exp の cdr を (破壊的に) 置き換える。

> (setq a (delay (+ 5 6)))
(*delay* nil #<closure> (0) (+ 5 6))
> (force a)
11
> a
(*delay* t . 11)
> (force a)
11
> 

1引数の iota は再帰的定義になじまないので, (Python 風の)2引数の range 関数を遅延評価的かつ再帰的に定義する。

(defun range (m n)
  (cond ((< m n)
         (cons m (delay (range (+ m 1) n))))))

下記に示すように,これは cdr が約束であるリストを返す。 引数の値がクロージャの中に保持されている様子に注意されたい。

> (setq a (range 1 3))
(1 *delay* nil #<closure> (0 [1, 3]) (range (+ (#<arg> 1 0 . m) 1) (#<arg> 1 1 .
 n)))
> (car a)
1
> (setq a (force (cdr a)))
(2 *delay* nil #<closure> (0 [2, 3]) (range (+ (#<arg> 1 0 . m) 1) (#<arg> 1 1 .
 n)))
> (car a)
2
> (setq a (force (cdr a)))
nil
> 

リストの cdr 値を force にかけてから取り出すように reduce を定義し直す。 force は約束以外には透過的だから, この reduce は通常のリストに対して今までどおりに振舞う。

(defun reduce (f x)
  (if (null x)
      (f)
    (let ((r (car x)))
      (setq x (force (cdr x)))
      (while x
        (setq r (f r (car x))
              x (force (cdr x))))
      r)))

ここまでの定義を lazy.l にまとめる。 実行例を下記に示す。

$ ruby L2Lisp.rb lazy.l -
> (reduce list '(1 2 3))
((1 2) 3)
> (reduce list (range 1 4))
((1 2) 3)
> (reduce * (range 1 101))
93326215443944152681699238856266700490715968264381621468592963895217599993229915
608941463976156518286253697920827223758251185210916864000000000000000000000000
> 

Pentium 3.2GHz/Cygwin/Ruby 1.8.6 で (reduce * (range 1 10001)) で 10000 の階乗を求めると約 10 秒かかる。 これは §2 の結果に比べておよそ半分の速さである。 長大なリストを構築する代わりに,ループごとに force する手間が意外にかかっている。 遅延評価は一般化されたイテレータとして利用できるが,この実装が実用的かどうかは現時点では微妙である。


次回へつづく


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