より実用的な L2Lisp.rb

2008.4.4 (鈴)

1. はじめに

Ruby による L2Lisp 4.3 版 を改訂し, 整数リテラルの構文を L2Lisp 5.0 版/Javaと同じく Emacs Lisp のサブセットとするなど,Emacs Lisp との, いくつかの主要な仕様の不一致をなくした。 さらにバッククォートによる準引用 (quasi-quotation) と, 数多くの関数 (Lisp から Ruby を呼び出す関数を含む) を導入することによって実用性を向上させた。 Mac OS X 10.4.11 上の ruby 1.8.2, 1.8.6, 1.9.0-1 および jruby 1.0.3, 1.1RC3 で動作を確認した。 現行のすべての Ruby 処理系で動作すると期待される。

$ ruby -v
ruby 1.9.0 (2008-03-01 revision 15664) [i686-darwin8.11.1]
$ ruby L2Lisp.rb
> (+ 1 #xFF)
256
> `(+ 2 ,(+ 3 4))
(+ 2 7)
> (ruby-send "ruby" 'upcase)
"RUBY"
> 

Scheme を含む Lisp の各方言 (以下,Lisp 族) で, 継続 (continuation) を使って記述され,実現されてきた処理のうち,例えば 非決定性のシミュレーション*1等は,もしも遅延評価 (lazy evaluation) が「使える」機能として用意されていれば,より適切に表現できたかもしれない。 もしそうなら,実装の負荷と意味論の明瞭さ*2の点で重要である。 従来,Lisp 族での遅延評価のサポートは,あってもせいぜい実用にはむずかしい原始的な 道具立てが用意されているだけ*3で,決して十分ではなかった。 本処理系は,当座必要な機能を備えた遅延評価の手軽な作業台とすべく, implicit forcing の実証モデルにとどまっていた L2Lisp 4.3 版を整備したものである。

本稿は以下,改訂の要点である準引用の実現,Lisp からの Ruby の呼出し, および細部の変更について順に記述する。 そのほとんどは一般的な周辺技術であり,そのため今まで後回しにされてきた。

*1:
・P. Graham 著, 野田訳「On Lisp」, オーム社, 2006, ISBN978-4-274-06637-5 の第22章 「非決定性」
・Abelson et al. 著, 和田訳「計算機プログラムの構造と解釈」第二版, ピアソン, 2000, ISBN4-89471-163-X の 4.3「Scheme の変形 − 非決定性」
*2: 例えば KURODA Hisao: Three Dogmas of Scheme (2008.3.10) は (最初の二節の是非はともかく) 最後の "Continuation" に関する議論で Scheme に見られる継続の不明瞭さを分かりやすく指摘しています。 R5RS の表示的意味論も,R6RS の操作的意味論も, 表記方法が若干異なるだけで,どちらもメモリ (store) 上の操作としてプログラムの意味を定義していますから, 現実の処理系での継続の実装には,メモリ以外の資源の取り扱いに不明瞭さがあります。 形式的意味論の範囲外のこととして,その決着は直感ないし常識に照らし合わせるべきですが, 継続が残っているときに (Ruby の beginensure, Python/C#/Java の tryfinally に相当する) unwind-protect で資源を回収することの妥当性は必ずしも直感的に明らかではありません。
*3: 前々回で議論したように Scheme の (delay expression)(force expression) の二つがあれば, 遅延評価プログラミングが一応は可能になりますが, それだけでは, 通常の関数に対し,本体内の式を適切に (force …) に置き換えたり,そういった関数を部品として組み立てた遅延評価バージョンの関数 を 一式 新しく用意する必要があり, 学生実験レベル以上の応用には現実的ではありません。
処理系が (force expression) を自動的に実行するようにすること,つまり,implicit forcing はこの問題を解決すると考えられますが, 実行速度を全般的に落とすおそれがありました。 前々回の成果の一つは, implicit forcing の実装が実行速度に与える影響が実は 5 % 程度にすぎないかもしれないことを示した予備的な実験結果でした。

2. 準引用の実現

準引用は Lisp 式のテンプレートを作るための特別なクォーテーションであり, Scheme (R6RS 11.17) と Common Lisp に見られる。 準引用はバッククォートで表現される。 バッククォート付きの式は,基本的には,普通のクォート付きの式と同じである。

> `(1 2 (list 3 (+ 1 3)) 5)
(1 2 (list 3 (+ 1 3)) 5)

しかし, その内部でカンマが接頭された式は,クォートの効果が打ち消され,評価される。

> `(1 2 ,(list 3 (+ 1 3)) 5)
(1 2 (3 4) 5)

カンマとアットマークがこの順で接頭された式は,クォートの効果が打ち消されて評価され, さらに結果の値のリスト両端の丸括弧がはぎとられる。

> `(1 2 ,@(list 3 (+ 1 3)) 5)
(1 2 3 4 5)

準引用は,それがあるからといって今まで不可能だったことが可能になるわけではないが, マクロ定義 にかかる人間の労力を軽減する便宜として重要である。 例えば,続々 L2Lisp で示したような while マクロ

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

は準引用を使って次のように書ける。

(defmacro while (test &rest body)
  `(let ($a)
        (setq $a
              (lambda () (cond (,test ,@body ($a)))))
        ($a)))

準引用は入れ子にできる。R6RS 11.17 の例から引く。

> (let ((name1 'x)
        (name2 'y))
    `(a `(b ,,name1 ,',name2 d) e))
(a (list 'b x 'y 'd) e)
>

ここで結果が Scheme と異なっていることに注意しよう。 R6RS によれば Scheme での結果は (a `(b ,x ,'y d) e) である。 しかし,ここで相違している部分式

(list 'b x 'y 'd)



`(b ,x ,'y d)

は,同じ環境で評価したとき,どちらも同じ結果になる。 準引用式を準引用式のまま結果とせず,必ず評価するならば,両者はどちらも妥当である。 したがって,主要な用途であるマクロ定義では,このことは実際的な問題にならない。 このような違いが生ずるのは言語の中での準引用の位置づけによる。

Scheme と異なり,本処理系の準引用はファーストクラスの構文ではない。 Common Lisp と同じく (read) 時に働く一種のマクロとして構文解析時に処理される。 言語の処理系本体には,いわば「コンパイル」済みの式が渡される。 準引用式をクォートすることにより,どのように「コンパイル」されるのかを見ることができる。

> '`(+ 2 ,(+ 3 4))
(list '+ 2 (+ 3 4))
> '`(a b ,c)
(list 'a 'b c)
> '`(a ,b ,@c)
(cons 'a (cons b c))
> '`((,a b) ,c ,@d)
(cons (list a 'b) (cons c d))
>

基本的な「コンパイル」方法は

G. L. Steele Jr.: "Common Lisp: The Language Second Edition", Digital Press, 1990, ISBN1-55558-041-6

の 22.1.3. Macro Characters に再帰的な変換ルールが記述されているから, これを再帰的なプログラムとして実装すればよい。 ただし,このルールに従っただけでは効率の悪い式にしか「コンパイル」できない。 例えば,上の例の最後の

`((,a b) ,c ,@d)



(append (list (append (list a) (list 'b) 'nil)) (list c) d 'nil)

にしかならない。 準引用を実際に使えるようにするには,式の単純化が必要である。 同書 Appendix C には 8 ページにわたって Common Lisp による最適化実装が掲載されている。 一方,本処理系では,再帰関数から戻るとき部分式を比較して単純化する方法により, 約 70 行の Ruby プログラムで実現している。 入れ子モジュール QQ が該当する個所である。 この方法でも,上記の式を

(cons (list a 'b) (cons c d))

にできるなど,概ね十分な単純化を行う。

Lisp 式を読む Reader#read メソッドに準引用を組み込む方法は次のとおりである。 カンマ や カンマ・アットマーク が出現したとき,それに続く式を QQ::Unquote インスタンスや QQ::UnquoteSplicing インスタンスに変換する。 バッククォートが出現したとき,それに続く式を QQ.expand_qq(x) に渡す。QQ.expand_qq(x) は式の中に含まれる QQ::Unquote インスタンスなどを適切に判別し, 展開済みの「コンパイル」結果を組み立てる。 妥当な Lisp 式ならば, Reader#read の外側に QQ::Unquote などの内部実装クラスのインスタンスが出現することはない。

  # 式を読む
  class Reader
    ...

    def read
      begin
        _read_token
        return _parse_expression
      rescue SyntaxError => ex
        ...
      end
    end


    RPAREN = :')'; DOT = :'.'

    def _parse_expression
      case @token
      when DOT, RPAREN
        raise SyntaxError, 'unexpected: %s' % @token
      when :'('
        _read_token
        return _parse_list_body
      when :'\''
        _read_token
        return Cell.new(:quote, Cell.new(_parse_expression, nil))
      when :'~'
        _read_token
        return Cell.new(:delay, Cell.new(_parse_expression, nil))
      when :'`'
        _read_token
        return QQ.expand_qq(_parse_expression)
      when :','
        _read_token
        return QQ::Unquote.new(_parse_expression)
      when :',@'
        _read_token
        return QQ::UnquoteSplicing.new(_parse_expression)
      else
        return @token
      end
    end

    ...
定数名 RPARENDOT を定義しているのは, (上記では省略されているが) 構文解析でこの二つが複数回出現するから… というわけでは実はありません。 原因は不明ですが,なぜかこれらを Symbol リテラルの即値で書くと,Emacs の Ruby モードで字下げが効かなくなる現象が発生したからです。>_<

3. Lisp からの Ruby の呼出し

Lisp と Ruby の相互作用を実現するために下記の4関数を用意した。

(ruby-eval str )
文字列 str を Ruby 式としてトップレベルの環境で評価する。
(ruby-send rcv sel param… )
任意の rcv を Ruby オブジェクトとして扱い,文字列またはシンボル sel の名前のメソッドを,任意個数の引数 param… で呼び出す。
(ruby-send-apply rcv sel fun param… )
ruby-send と同様だが,関数またはマクロ fun をブロックとして渡す。
(ruby-self)
Ruby オブジェクトとしてのインタープリタ自身を返す。

典型的には ruby-eval で Ruby オブジェクトへの参照を得て, ruby-send でそのメソッドを呼び出す。 Lisp 関数を ruby-send-apply で渡すことにより, Ruby からのコールバックを受け取ることができる。 L2Lisp.rb: Ruby への移植 で述べたように Lisp 式は Ruby オブジェクトと素直に対応しているから, 数や文字列をそのまま引数として渡したり,戻り値として受け取ることができる。
Integer (Fixnum, Bignum) または Float のインスタンス
文字列 String インスタンス
シンボル Symbol インスタンス (大域変数値は Hash 値 L2Lisp::Interp#symbol に格納)
nil nil
cons セル L2Lisp::Cell インスタンス

例として,初期化 Lisp スクリプトでの STDOUTprintf の定義を示す。

(setq STDOUT (ruby-eval "STDOUT"))
(defun printf (str &rest args)
  (apply ruby-send `(,STDOUT printf ,str ,@args)))

第1行では,文字列 "STDOUT"ruby-eval することによって, Ruby 定数 STDOUT の値を Lisp 変数 STDOUT に得る。 第2行と第3行では,Lisp 関数 printf を, STDOUT が表す Ruby オブジェクトに対し, その printf メソッドを ruby-send を使って呼び出すように定義する。 したがって,

(printf "Hello, %s-san!\n" "Suzuki")



STDOUT.printf("Hello, %s-san!\n", "Suzuki")

という Ruby 式に相当するメソッド呼出しを行う。

> (printf "Hello, %s-san!\n" "Suzuki")
Hello, Suzuki-san!
nil
> 

L2Lisp にハッシュ表のデータ型は用意されていないが,

(setq Hash (ruby-eval "Hash"))
(defun make-hash () (ruby-send Hash 'new))
(defun hash-put (h key val) (ruby-send h "[]=" key val))
(defun hash-get (h key) (ruby-send h "[]" key))
(defun hash-each (h fun) (ruby-send-apply h 'each fun))

のような内容の ruby-hash.l を用意すれば, 下記のようにハッシュ表を使うことができる。

$ ruby L2Lisp.rb ruby-hash.l -
> (setq h (make-hash))
{}
> (hash-put h "foo" 10)
10
> (hash-put h "bar" 20)
20
> (hash-put h "baz" 30)
30
> h
{"foo"=>10, "bar"=>20, "baz"=>30}
> (hash-get h "bar")
20
> (hash-each h (lambda (key val) (printf "%s -- %s\n" key val)))
foo -- 10
bar -- 20
baz -- 30
{"foo"=>10, "bar"=>20, "baz"=>30}
> 

Interp クラスにある ruby-* 関数の実装はごく簡単である。

    alias ruby_eval eval
      @symbol[:'ruby-eval'] = proc {|expression|
        ruby_eval(expression, TOPLEVEL_BINDING)
      }
      @symbol[:'ruby-send'] = proc {|receiver, selector, *parameters|
        receiver.send(selector, *parameters)
      }
      @symbol[:'ruby-send-apply'] = proc {|rcv, sel, fun, *params|
        rcv.send(sel, *params) {|arg| apply(fun, arg)}
      }
      @symbol[:'ruby-self'] = proc {self}

4. 細部の変更

未定義シンボル

ユーザが本処理系を対話セッションで使ったとき,最初に気付く従来との違いは, おそらく,未定義シンボルを評価したときの振舞である。 これまでの旧 L2Lisp は,値を割り当てていないシンボルの評価値としてシンボル自身を返していた。

> foo
foo
> 

この振舞は,もしも計算の最後まで変数に値が束縛されなかったならば, 変数がそのまま変数として結果の式に出現するという Prolog の振舞にヒントを得たものだった。 これは,いくつかのクォートを不要にし,一部の記号計算やマクロ定義の記述を簡単にすることに役立った。 しかし,多くの場合,プログラムの誤りを分かりづらくした。 Prolog では定数データとしてのシンボルと変数が文法上明確に区別されているが,Lisp にはその区別がないことが失敗の原因である。

本処理系は,普通の Lisp と同じく,未定義シンボルの評価でエラーを起こす。

> foo
*** void variable: foo
  0: foo
> 

実装上は,Interp の中で大域変数値を格納している @symbol から シンボル name の値を得るとき, @symbol.fetch(name, name) とするかわりに下記を行う (Interp#eval_symbol)。

      begin
        return @symbol.fetch(name)
      rescue IndexError
        raise EvalError.new('void variable', name)
      end

整数リテラル

2進数,8進数,16進数の整数リテラルの表記方法を,Emacs Lisp のサブセットとして,それぞれ #b, #o, #x を接頭する方式に改めた (これは Common Lisp と Scheme のサブセットでもある)。 一方,0377 はもはや8進数ではないから,10進数 377 と解釈される。

> #o377
255
>  0377
377

対応する実装は Reader#_read_token にある。

ラムダ式,マクロ式の内部表現

旧 L2Lisp では, シンボル lambdamacro を先頭要素とするリスト (lambda …)(macro …) を評価して得られる関数値としてのラムダ式やマクロ式は, 特別な値を先頭要素とするリストとして実装されていた。 もしもそうしたければ, それに carcdr を適用することもできた。

> (lambda (n) (+ n 1))
(#<closure> (1) (+ #0:0:n 1))
> (car (lambda (n) (+ n 1)))
#<closure>
> (cdr (lambda (n) (+ n 1)))
((1) (+ #0:0:n 1))
> 

このようにした理由は,元々の 標準 Pascal での実装 で自動メモリ管理されるのが cons セルに限られていたことによる。 しかし,この実装方法では,ラムダ式やマクロ式を判別するために,まず cons セルであることを 判定し,次にその car 値を調べる必要があった。

本処理系は,これらの関数値を DefinedFunction を共通の基底とするクラスのインスタンスとして実装する。 このことは処理系のあちこちの処理を簡素化する。 インスタンスの inspect メソッドは従来のリスト表現を模した文字列を返すから, 表面上は何も変わらないようにみえるが,実際には cons セルではないから, carcdr を適用することはできない。 このことは関数値への誤ったリスト操作の適用を検出できるから,概ね有益である。

> (lambda (n) (+ n 1))
(#<closure> (1) (+ #0:0:n 1))
> (car (lambda (n) (+ n 1)))
*** NoMethodError: undefined method `car' for (#<closure> (1) (+ #0:0:n 1)):L2Li
sp::CLOSURE -- #<Proc:0x001dd300@6/0/L2Lisp.rb:583> [(#<closure> (1) (+ #0:0:n 1
))]
  0: (car (lambda (n) (+ n 1)))
> 

定義済み関数の追加

スペシャルフォーム,組込み関数,および内蔵の 初期化 Lisp スクリプト で定義する関数とマクロを増やした。

スペシャルフォームとして progn を追加した。 旧 L2Lispprogn(progn e f g h)(cond (t e f g h)) へと展開されるようなマクロとして初期化 Lisp スクリプトで定義していた。

Interp#initialize に追加した組込み関数には §3 で述べた ruby-* 関数のほか, numberp, eql, list, %, load, mapcar, mapc prelude help copyright _add _concat がある。

eq は Ruby の equal? に, eqleql? にそれぞれ対応する。 つまり,今の eq は Emacs Lisp (および Common Lisp) と同じ意味である。

旧 L2Lisp は list を rest 引数の値をそのまま返すラムダ式として 初期化 Lisp スクリプトで定義していたが,基礎的な演算なので組込み関数とした。 組込み関数のうち,listcons は引数の implicit forcing をしない。

load は引数の文字列をファイル名とする Lisp スクリプトを実行する。 拡張子やディレクトリについては何も細工しない。渡された文字列をそのまま使う。

      @symbol[:load] = proc {|file_name| run(File.new(file_name))}

_add_concatconcat を実装するための下請け関数である。 concat は初期化 Lisp スクリプトで定義される。 対話セッションでの便宜として, (prelude) は初期化 Lisp スクリプトの内容を表示する。 同様に (help)(copyright) はそれぞれ処理系のまとめと著作権を表示する。

assq は,標準 Pascal による実装では,処理系内部で使うために用意され, そのついでとして組込み関数となっていたが,ハッシュ表をもった Ruby ではその必要がなくなっていた。 本処理系では初期化 Lisp スクリプトが member, memq, assoc とともに assq を定義する。

5. おわりに

Ruby 版 L2Lisp の機能を強化し,特に必然性がないところでは仕様を標準的なものに合致させるとともに, 内部実装を整理・簡素化した。 今回の改訂で高速化は主眼ではないが,一応の目安として, 前々回 使ったベンチマーク・テスト 8queens.l を実行したところ,意外な結果が得られた。 結果は CoreDuo 2.0GHz/1GB/OS X 10.4.11/(Java 1.5.0_13) で各3回計測した最速値である。
Ruby L2Lisp 4.3 L2Lisp 6.0
ruby 1.8.2 27.4 [s] 24.1 [s]
ruby 1.8.6 24.3 [s] 21.8 [s]
ruby 1.9.0-1 51.4 [s] 36.9 [s]
jruby 1.0.3 104.9 [s] 102.8 [s]
jruby 1.1RC3 41.0 [s] 43.6 [s]

測った限りでは,最速の Ruby 処理系は ruby 1.8.6 である。

ruby 1.9.0-1 はそれほど高速ではない。むしろ低速である。 このテストは ruby 1.9 系が苦手とすると言われる文字列処理を主体としたものではない。 高速性が期待されている処理系でもあり,おそらく他者による追試と検証が必要である。 jruby 1.1RC3 は ruby 1.8.6 と比べて悪くても2倍しか時間がかからないところまで高速化されている。 もしも Java 1.6.0 で動作させれば,さらに高速化されると思われる。

L2Lisp 4.3 と 6.0 を比べると,四つの処理系で高速化されたが, jruby 1.1RC3 では若干の速度低下が起こった。 これについては必ずしも今結論づけることはできない。 もしかしたら jruby のバックにある Java をチューニングすることで結果が変わるかもしれない。


付録: 簡単な遅延評価のプログラム例


次回へつづく


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