Let Little Lambda Lisp be a Little Lazy

2007.7.14 (2007.7.20 追記, 2010.8.11 リンク修正) (鈴)

1. はじめに

前回の最後で Scheme と同様の delay と force をそれぞれマクロと関数として実装し, L2Lisp で遅延評価 (lazy evaluation または delayed evaluation) を実験した。 しかし,その性能は実用的というには微妙だった。

Miranda,Haskell によって具体的に知られるように, 関数型のスタイルによるプログラミングにとって遅延評価は重要である。とりわけ, それは巨大な中間結果を生成せずにパイプライン的にプログラムを構成することを可能にする。 その考え方は,改訂版 C#, Python のような現代的な手続き型言語にも (Ruby の用語法によれば) 外部イテレータを構成する yield を通して応用されはじめている (例えば 続々・C# で作る Prolog 処理系 を見よ)。 逆にいえば,多くの人になじみがある手続き型言語の見地からは, 遅延評価は,イテレータを構成する一般的な手段として見ることができる*1

*1: Abelson と Sussman が SICP 第二版 (1996) §3.5.4 で 「変更と遅延評価…を同時に扱う方法を工夫するのは,研究の盛んな領域である」 (mutability and delayed evaluation ... devising ways to deal with both of these at once is an active area of research) と記述してから 10 年たって得られた成果が,改訂版 Python と C# にある新世代の yield だと言えるかもしれません。 Ruby の輩 (ともがら) にとっては,今の Ruby の (CLU から数えて 30 年来の) yield が必ずしもイテレータを作るたった一つの冴えたやりかたではないことを心に留めておくことが大切です。

このような状況を鑑み,L2Lisp 4.2 版では,いくつかの付随的な改訂のほか, 遅延評価の機能を言語本体に取り込み,組込み関数全般の処理を変更して, 効果的な遅延評価を実現した。 本稿は以下この 4.2 版について記述する。 ただし,コンパイル結果の内部に踏み込まない限り, 大域名が追加のスペシャルフォーム名などと衝突する例外的な場合を除き, 依然として従来との互換性は保たれている。 これが,この改訂がその規模にかかわらず 5.0 版ではなく 4.2 版である理由である。

従来の Lisp プログラムに対する性能は 4.1 版と同程度である。 前回§2に示すような tak 関数に対し, 同じ環境で 4.1 版が約 12.8 秒,4.2 版が約 12.4 秒という実行時間である。

2. コンパイル結果の表現方法の変更

4.2 版の作成にあたり,まず (遅延評価とは直接関係ないが) 処理系実装の簡素化のため, ラムダ式やマクロ式のコンパイル結果に含まれる 仮引数 (#<arg> level offset . symbol ) とダミー・シンボル (#<dummy> . symbol ) を それぞれ Arg インスタンス Arg.new(level, offset, symbol ) と Dummy インスタンス Dummy.new(symbol ) で表現するように改めた。各クラスの定義を示す。

  class Arg                 # コンパイル後のラムダ式やマクロ式の仮引数
    attr :level
    attr :offset
    attr :symbol

    def initialize(level, offset, symbol)
      @level = level
      @offset = offset
      @symbol = symbol
    end

    def inspect
      return "#%p:%p%p" % [@level, @offset, @symbol]
    end

    def set_value(x, link)
      @level.times {link = link.cdr}
      link.car[@offset] = x
    end

    def get_value(link)
      @level.times {link = link.cdr}
      return link.car[@offset]
    end
  end # Arg
  class Dummy                  # コンパイル後のマクロ式の dummy symbol
    attr :symbol

    def initialize(symbol)
      @symbol = symbol
    end

    def inspect
      return "%p:%x" % [@symbol, object_id]
    end
  end # Dummy

典型的な使用例として,内蔵初期化 Lisp スクリプト PRELUDE で定義される while マクロの値を示す。

4.1 版

> while
(#<macro> (-2) (list let (quote ((#<dummy> . $a))) (list setq (#<dummy> . $a) (l
ist lambda nil (list cond (cons (#<arg> 0 0 . test) (_append (#<arg> 0 1 . body)
 (quote (((#<dummy> . $a))))))))) (quote ((#<dummy> . $a)))))
> 

4.2 版

> while
(#<macro> (-2) (list let (quote (:$a:34666)) (list setq :$a:34666 (list lambda n
il (list cond (cons #0:0:test (_append #0:1:body (quote ((:$a:34666)))))))) (quo
te (:$a:34666))))
> 

どちらも下記のコンパイル結果である。

(defmacro while (test &rest body)
  (list let (quote ($a))
        (list setq $a
              (list lambda () (list cond (cons test (append body '(($a)))))))
        '($a)))

L2Lisp 1.0 版から 4.1 版まで,#<arg> 等の特別なシンボルを第1要素とするリストを使って 仮引数等を表現していたのは,Pascal 版の実装で cons セルだけを自動メモリ管理の対象としていたからである。 仮引数用のレコード,つまり構造体を別に管理するのではなく,cons セルですべてを表現することによって, 処理系の実装を簡単に済ませていた。

Ruby 版の実装ではメモリ管理を ruby に任せているから,cons セルですべてを表現する必要はない。 したがって 4.2 版では,特別なシンボルを第1要素とするリストではなく, 専用のクラスのインスタンスを使うことにした。 属性へのアクセスが Ruby により直接サポートされるようになったこと, cons セルに対し car のシンボル値を判定する処理が軽減されたことにより, 数パーセントの処理速度の向上が見られた*2

*2: ただし,このわずかな向上分は,最終的には,遅延評価を実現するコストによってほぼ相殺されています。 より正確にいえば,この向上分を使い切らない範囲で遅延評価の機能を充実させました。

3. 遅延評価の実現

前回の実験と同じく 4.2 版は任意の式 exp を遅延評価するために Scheme と同じスペシャルフォーム (delay exp) を陽に使う。 (delay exp) は約束 (promise) と呼ばれるオブジェクトを返す。 このオブジェクトは,未来のある時点で exp を評価して結果の値をかなえる (deliver) ことができる。 R5RS §4.2.5 を見よ。

SICP 第二版 §3.5 で記述されている遅延評価実装のように 「約束」をかなえる機能を force 関数だけに限れば, 他に性能上のペナルティを与えることなく遅延評価を実現できる。 しかし,その場合,同書 §3.5.4 が指摘するように,通常版の関数のほかに 遅延評価対応の関数を一式用意する必要がある。

これに対し,L2Lisp 4.2 版では,広く遅延評価のコストを負担して, 今までの関数でそのまま遅延評価に対応できるようにした。 具体的には R5RS §6.4 で言及されている implicit forcing を実装した。

3.1 約束クラス Promise

前節で述べた Arg クラスおよび Dummy クラスと並んで 「約束」を表現する Promise クラスを定義する。

  NONE = :"#<none>"
  class Promise                 # 約束: (delay exp) の評価結果
    attr :exp, true
    attr :link, true            # 字句的環境 (評価済みならば NONE)

    def initialize(exp, link)
      @exp = exp
      @link = link
    end

    def inspect
      if @link == NONE
        return "#delivered:%p" % @exp
      else
        return "#promised:%p:%p" % [@link, @exp]
      end
    end
  end # Promise

「約束」つまり Promise インスタンスはスペシャルフォーム (delay exp) の評価結果としてだけ作られる。メソッド Interp#eval の該当部分を示す。

    def eval(x, can_lose_current_env=false)
      begin
        loop {
          case x
          when Symbol then return @symbol.fetch(x, x)
          when Arg then return x.get_value(@environ)
          when Cell
            case x.car
            
            when :delay
              kdr = x.cdr
              (Cell === kdr and kdr.cdr.nil?) or raise EvalError, "bad delay"
              return Promise.new(kdr.car, @environ)
            else

3.2 約束をかなえるメソッド Interp#deliver

「約束」をかなえるメソッド Interp#deliver の定義を示す。 R5RS §6.4 での実装例と同じく Interp#eval メソッドの実行中に再帰呼出しによって約束がかなえられる場合に備えて unless … によるチェックを二度行う。 追記: 5. も参照せよ。

    def deliver(promise)        # 約束をかなえる
      unless promise.link == NONE
        old_env = @environ
        @environ = promise.link
        begin
          x = eval(promise.exp, true)
        ensure
          @environ = old_env
        end
        unless promise.link == NONE # eval の中でかなえられていなければ…
          promise.exp = x
          promise.link = NONE
        end
      end
      return promise.exp
    end

条件式での真偽判定と,cons を除く組込み関数の各実引数に対し, その値を x としたとき, (Promise === x) が成立するならば x = deliver(x) を行う。 組込み関数 length 等は,Cell の派生クラス EagerList を利用して,実引数に再帰的に Interp#deliver を適用する。

このような implicit forcing により,従来の言語仕様との互換性を保ったまま 遅延評価を扱うことが可能になる。ただし,たとえ遅延評価の機能を利用しないときでも, わずかとはいえ,式 (Promise === x) を評価するコストが条件式と組込み関数によって広く負担される ことに注意されたい。

3.3 使用例

使用例を示す。4.2 版では range と reduce も内蔵初期化 Lisp スクリプト PRELUDE で定義されている。

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

PRELUDE に含まれる range の定義は下記のとおりである。 (range m n) は Python の同名の関数の2引数版と同じく m 以上 n 未満の整数の列を作る。 ただし,この列はきたるべき Python 3000 で予定されているように遅延評価的であり, (リストの cdr をとることにより) 次の要素を求めたとき,はじめてその値が計算される。 (リストの car をどんどん捨てることにより) 計算中に保持されるのは, 今の要素の整数値と,次以降の要素の約束の二つのオブジェクトだけである。

(defun range (m n)                      ; from Python 3000
  (cond ((< m n)
         (cons m ~(range (+ m 1) n)))))

ここで ~exp は (delay exp) の L2Lisp 特有の略記法である。 実装についてはメソッド Reader#_parse_expression の when TILDE の分岐枝を見よ。

PRELUDE に含まれる reduce の定義は下記のとおりである。 遅延評価のための処理は特にない。 (cdr x) を評価したとき,implicit forcing により約束の値が自動的にかなえられる (前回の定義と比較せよ)。

(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)))

4. おわりに

Pentium 3.2GHz/Cygwin/Ruby 1.8.6 のもとで (reduce * (range 1 10001)) で 10000 の階乗を求めると約 5.0 秒かかる。 前回iota.l を使った (reduce * (iota 10000)) は約 5.1 秒かかる (公平を期して両者とも iota.l を読み込んで計測した)。 ちなみに PRELUDE の range の定義から ~ を除去して遅延評価をしないようにすると, (reduce * (range 1 10001)) に対し, ruby 自体が stack level too deep (SystemStackError) というエラーで終わる。 range の定義が末尾再帰的でないため,普通の評価方法ではスタックを消費するからである。 遅延評価にすると,一度に深く入れ子呼出しをしなくなり,末尾再帰の最適化と同じ効果が得られる (似たような現象が Python などの yield でも見られる)。

今回の遅延評価機能の導入が成功かどうか結論づけるにはまだ例が不足しているが, この予備的な結果は十分に有望である。 C# と Python にある新世代の yield の価値が広く認識されはじめ, さらに,数年前まで一般にほとんど知られていなかった Haskell が一定の知名度を得た現在, Lisp もまた,この (アイディア自体は決して新しくないが今まで有効な利用方法が 広く知られていなかった) 遅延評価の力を得て,再び新しく発展する様子を想像することは 決して困難ではない。

5. 追記: Interp#deliver の修正 (L2Lisp 4.3 版/Ruby)

3.2 で示した L2Lisp 4.2 版のメソッド Interp#deliver には, 多重に遅延されている式に対して implicit forcing が適切に行われない欠陥がある。

> (defun f (x) ~(g (* x 3)))
f
> (defun g (y) ~(+ y y))
g
> (setq a (f 2))
#promised:([2]):(g (* #0:0:x 3))
> (+ a 1)
*** TypeError: L2Lisp::Promise can't be coerced into Fixnum -- #<Proc:0x0001a054
@L2Lisp.rb:444> [#promised:([6]):(+ #0:0:y #0:0:y), 1]
  0: (+ a 1)
> 

explicit に force を多重適用すればよいが, 式が関数内部でどれだけ多重に遅延されるかに依存する難がある。

> (+ (force a) 1)
13 
> 

解決策としては下記のように Interp#deliver に1行 追加して, もしも約束をかなえた結果が別の約束だったら,その約束をかなえるようにすればよい。

    def deliver(promise)        # 約束をかなえる
      unless promise.link == NONE
        old_env = @environ
        @environ = promise.link
        begin
          x = eval(promise.exp, true)
          x = deliver(x) if Promise === x
        ensure
          @environ = old_env
        end
        unless promise.link == NONE # eval の中でかなえられていなければ…
          promise.exp = x
          promise.link = NONE
        end
      end
      return promise.exp
    end

細かな修正を除き,L2Lisp 4.3 版の主要な変更点はこの1行である。 4.3 版の実行例を示す。

> (defun f (x) ~(g (* x 3)))
f
> (defun g (y) ~(+ y y))
g
> (setq a (f 2))
#promised:([2]):(g (* #0:0:x 3))
> (+ a 1)
13
> a
#delivered:12
> 

6. 追記: tarai 関数の果たされない約束

遅延評価の強力さを示す好例としてネット上で人気があるベンチマーク・テストに tarai 関数がある。

(defun tarai (x y z)
  (if (>= y x)
      y
    (tarai (tarai (- x 1) y z)
           (tarai (- y 1) z x)
           (tarai (- z 1) x y))))

CoreDuo 2.0GHz/OS X/Ruby 1.8.2 上の L2Lisp 4.3 版で (tarai 10 5 0)10 を計算させると約 49.2 秒かかる。 しかし,下記のように各引数を遅延評価させると,同じ計算が約 0.10 秒で終わる (ともに起動時間込み)。

(defun tarai (x y z)
  (if (>= y x)
      y
    (tarai ~(tarai (- x 1) y z)
           ~(tarai (- y 1) z x)
           ~(tarai (- z 1) x y))))

この例では,遅延評価によって約 500 倍の圧倒的な高速化が達成されている。 理由は単純である。 (>= y x) が成立するとき,第3引数 z は評価されない。 z の実引数として渡された約束は果たされることなく捨てられる。 これにより計算量が大幅に節約される。

もしも下記のように第3引数だけ遅延評価をさせない場合, なんら計算量は節約されず,約束をしたり果たしたりする手間だけが余分にかかる。 約束として渡された tarai 関数の第1引数と第2引数は, (>= y x) の計算のため,ただちに具体的な数値へと評価される。 実際,この場合は (tarai 10 5 0) の計算に約 54.4 秒かかる*3

(defun tarai (x y z)
  (if (>= y x)
      y
    (tarai ~(tarai (- x 1) y z)
           ~(tarai (- y 1) z x)
           (tarai (- z 1) x y))))
*3: このように tarai 関数に見られる遅延評価の圧倒的な高速性は, とにかく遅延させれば OK というような法則を意味しているわけでは決してありません。 むしろ,遅延評価が有利になるように注意深く選んだ特別な例とみるほうが妥当です。 実際,tarai 関数とほとんど同じ tak 関数を遅延評価で実行しても, 果たされない約束がありませんから高速化されません。
ですから,遅延評価を説明するとき, tarai 関数のような例は最初に強い印象を与える一種の「ねこだまし」としては有効ですが, それだけで終わると,(かつて再帰呼出しがそうであったように) 高等な知的遊戯にすぎないと 誤解されるおそれがあります。
本稿冒頭の繰り返しになりますが, (とりわけ Ruby の朋輩にとっては) 遅延評価を外部イテレータを表現する高水準の方法と理解すると, より応用が利きます。遅延評価の利点についての,さらに説得力のある解説は Hughes 著 山下訳 なぜ関数プログラミングは重要か に見ることができます。

7. 追記: 約束の代償は…? (L2LispEE/Ruby)

Ruby による L2Lisp 4.2 版,4.3 版は,従来の Lisp の意味論を保持しつつ, プログラマによる遅延評価の利用をできる限り妨げないようにするため, implicit forcing を採用している。 3.2 で述べたように,これには性能上のペナルティがある。 しかし,2. で述べたようにコンパイル結果の表現方法を簡素化したため, 4.1 版と比べ, 約束オブジェクトに関する性能上の代償はほとんど目立たなくなっている*4

*4: 遅延評価を絵に描いた餅にしないためには,少なくともほどほどの効率の良さが必要です。 そのための目安として, 表現方法の簡素化で得られた性能向上の範囲内にペナルティを収めることを目標としました。 その一方で,試行錯誤の開発の手間を減らすため, 不完全ながらも簡素化をした初期内部バージョンで数パーセントの性能向上を確かめた後, それ以降の改訂を遅延評価用とそれ以外に切り分けて後者をそのバージョンに適用することはしませんでした。 結果,4.1 版と比較して当初の目標は達成できたわけですが, 約束の代償の大きさを直接は確認できないままになっていました。

より正確な比較のため,処理系のバリアントとして 4.3 版のプログラムから約束クラスその他,遅延評価に 関係する部分だけを取り除いた L2LispEE (EE: Eager Evaluation) を作成した。

CoreDuo 2.0GHz/OS X/Ruby 1.8.2 で (tak 18 12 6)(reduce + (iota 10000))(length (nqueens 8)) の各所要時間を測った。 これらは遅延評価機能を使用しない。結果は下表のとおりである。

プログラム L2Lisp L2LispEE
(tak 18 12 6) 9.0 [s] 8.6 [s] 1.05
(reduce + (iota 10000)) 2.4 [s] 2.3 [s] 1.04
(length (nqueens 8)) 27.4 [s] 26.0 [s] 1.05

この結果から判断する限り,全く遅延評価をしない場合でも, 遅延評価機能のために約 5 % のいわゆる一般課税がある。 その多くは条件式と組込み関数での式 (Promise === x) の評価コストと考えられる。


次回へつづく


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