特集記事

L2Lisp in Ruby

RubyによるモダンなLispの小さな実装

(鈴)[著]

更新日: 2011/03/18
公開日: 2007/07/23

ポスト

Interpクラス 2

大域脱出

　L2LispはEmacsLisp（およびCommon Lisp）のサブセットとして大域脱出に関連して組込み関数throwと特殊形式catch、unwind-protectを用意します。

　組込み関数throwは例外送出として実現します。

Interp#initializeにて

@symbol[:throw] = proc {|x, y| raise Thrown.new(x, y)}

　送出される例外の定義を示します。組込み関数throwの引数を属性tag、valueとして持ちます。

throw用の例外クラス

class Thrown < EvalError
  attr :tag
  attr :value

  def initialize(tag, value)
    super('no catcher for (%s %s)' % [LL.str(tag), LL.str(value)])
    @tag = tag
    @value = value
  end
end

　前述のようにevalメソッドは各特殊形式について専用のメソッドを呼び出します。

Interp#evalにて

when :catch then return eval_catch_body(x.cdr)
when UNWIND_PROTECT then return eval_unwind_protect_body(x.cdr)

　特殊形式（catch tag body...）はbody...を評価してその結果を返します。ただし、body...から直接・間接に（throw t v）が実行されて大域脱出が行われたとき、もしそのtがtagと等しいならば、大域脱出を捕捉してvを返します。さらにL2Lispだけの拡張機能として、一般の評価例外を*error*で捕捉できるようにします。Rubyのbegin - rescue - end構文でそのまま実現できます。

def eval_catch_body(j)      # j = (tag body...)
  (Cell === j) or raise EvalError.new('tag and body expected', j)
  tag = eval(j.car, false)
  begin
    result = nil
    LL.mapc(j.cdr) {|x| result = eval(x, false)}
    return result
  rescue Thrown => th
    if tag == th.tag then return th.value else raise end
  rescue EvalError => ex   # 一般の評価例外は *error* で捕捉される
    if tag == :"*error*" then return ex else raise end
  end
end

　例えば、Lispプログラムの中で式を入力して評価して表示するとき、もしも評価例外が発生したら「エラー発生」というメッセージと例外を表示するには、次のようにします。

(cond ((setq ex (catch *error*
                       (print (eval (read)))
                       nil))
       (princ "エラー発生") (terpri)
       (princ ex)))

　特殊形式（unwind-protect body cleanup...）はbodyを評価してその結果を返します。ただし、bodyの終了後cleanup...を実行します。bodyの中から大域脱出が行われたときもcleanup...を実行します。Rubyのbegin - ensure - end構文でそのまま実現できます。

def eval_unwind_protect_body(j) # j = (body cleanup...)
  (Cell === j) or raise EvalError.new('body (and cleanup) expected', j)
  begin
    return eval(j.car, false)
  ensure LL.mapc(j.cdr) {|x| eval(x, false)}
  end
end

ラムダ式のコンパイル

　ラムダ（lambda）で始まるLisp式を評価するとき、Interp#evalメソッドはInterp#compile_lambdaメソッドを呼び出して簡単なコンパイルをします。そしてその結果を評価の値とします。

> (lambda (a b) (+ a b))
(#<closure> (2) (+ (#<arg> 0 0 . a) (#<arg> 0 1 . b)))

　ここで(2)つまり(2 . nil)の2は仮引数の個数（arity）を意味し、nilはこの式を適用するときの環境リストを意味します。仮引数(#<arg> 0 0 . a)の最初の0は環境リストの第0フレームを意味し、次の0はそのフレームの先頭からのオフセットを意味します。(#<arg> 0 1 . b)はオフセットが1です。

　式を適用するとき、ローカル変数に対し、名前をキーにして環境を探しまわるようなことはしません。PascalやAlgolのような一般の言語でのローカル変数参照と同じく、フレームとオフセットで決定される環境リストの特定の場所を参照します。

　ラムダ式を入れ子にすると次のようになります。

> (lambda (a b) (lambda (c) (+ a b c)))
(#<closure> (2) (#<lambda> 1 (+ (#<arg> 1 0 . a) (#<arg> 1 1 . b)
 (#<arg> 0 0 . c))))

　入れ子のラムダ式の中では、外側のラムダ式の変数は、フレームの値が0でなく1になることに注意してください。1段階外側のフレームに属する変数というわけです。入れ子のラムダ式は、環境が未定ですから、仮引数の個数1が単独で置かれます。環境を持たず、クロージャ（closure）とは言えませんから、最初の要素は#<closure>ではなく#<lambda>とします。

　コンパイルではマクロ展開もします。

> (defmacro unless (e1 &rest e2)
     (list 'cond (cons (list 'not e1) e2)))
unless
> (lambda (a b) (unless a (print b)))
(#<closure> (2) (cond ((not (#<arg> 0 0 . a)) (print (#<arg> 0 0 . b)))))

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

　利用者がLisp言語で定義した関数は、最終的にはラムダ式の適用というかたちで実行されます。

> (defun add (a b) (+ a b))
add
> add
(#<closure> (2) (+ (#<arg> 0 0 . a) (#<arg> 0 1 . b)))
> (add 1 2)
3
>

　ここまでInterp#evalの第2引数には説明なしにfalseを与えてきました（これはデフォルト引数値ですから省略も可能です）。以下で説明するように、第2引数は、ラムダ式の適用で末尾呼出しの最適化を行うために使われます。

　evalメソッドでラムダ式の適用に関係する部分を下記に示します。条件式（cond）に対するeval_cond_bodyメソッドの場合とおなじく、apply_lambdaメソッドは末尾の式を評価せずにtrueとともに返します。このとき、末尾の式はローカル変数xの新しい値としてloopして評価されます。

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メソッドの第2引数は、評価しようとする式が（全体として）末尾の式かどうかのフラグです。このフラグはapply_lambdaメソッドに引き継がれます。

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

　フラグが立っているとき、ラムダ式本体の最後の式が（本当の）末尾の式ということになりますから、評価せずにevalメソッドに戻ります。このとき@environは新しい環境にしたままにします。

# 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を元に戻します。

　この一連の処理をよく見ると、結局、字面の上で末尾にある呼出しかどうかが問題ではなく、元の環境に戻す必要があるかどうかが問題であることが分かります。もしも戻す必要がなければ、再帰的にevalメソッドを呼び出すかわりに、未評価の式を戻り値として、呼出し元のevalメソッドに渡すことができる、というわけです。これがフラグの変数名can_lose_current_envとcan_lose_original_envの由来です。

　Lisp組込み関数evalは、字面の上では末尾とは限らないのにフラグを立てる実例です。

@symbol[:eval] = proc {|x|
  old_env = @environ
  @environ = nil          # 大域的な環境にする
  begin eval(x, true)     # 末尾呼出しと同じく環境復元は不要
  ensure @environ = old_env
  end
}

　ちなみに、Common Lispと同じくL2Lispの組込み関数evalが大域的な環境を使う理由は、ラムダ式のコンパイルと関係があります。ラムダ式の適用時、ローカル変数はコンパイル済みの(#<arg> 0 0 . a)のような形式です。しかし、組込み関数evalに渡されるのは生のリストやシンボルですから、ローカル変数として評価できません。この矛盾が表面化しないように、はじめから大域的な環境、つまり空の字句的環境にするわけです。

初期化Lispスクリプト

　前述のようにInterpクラスのインスタンスは、その初期化作業の最後に、文字列定数PRELUDEをLispスクリプトとして実行します。スクリプトはlistやprintを関数として、defunやifをマクロとして定義します。定義の詳細についてはPascal版実装に関する「L2Lisp 第6節」（および「続 L2Lisp 第2節」と「続々 L2Lisp 第2節」）を参照してください。

  PRELUDE = %q{
;; 初期化 Lisp スクリプト

(setq list (lambda (&rest x) x))
(setq progn (macro (&rest x) (list cond (cons t x))))

(setq defmacro
      (macro (name args &rest body)
             (list progn
                   (list setq name (cons macro (cons args body)))
                   (list quote name))))

(defmacro defun (name args &rest body)
  (list progn
        (list setq name (cons lambda (cons args body)))
        (list quote name)))

(defun caar (x) (car (car x)))
…
(defun print (x) (prin1 x) (terpri) x)
…
(defun /= (x y) (not (= x y)))

(defmacro if (test then &rest else)
  (cons cond (cons (list test then)
                   (cond (else (list (cons t else)))))))
…
}

おわりに

　本稿で述べたL2LispのRuby実装は、標準Pascalによる元の実装に比べおよそ1/100の速さです。Ruby上のLispインタープリタとしては比較的高速な部類に入りますが、実用性の観点からは、より高速な言語処理系への移植、あるいは本格的なコンパイラの作成が望ましいでしょう。

　一方、速度がそれほど重要でない分野では、本処理系はRubyのデータ型とよく統合されており、ごく簡単に組込み関数を増設できるなど、手頃で改造の容易なLisp処理系として利用できます。実行効率をいったん度外視し、イテレータ等を活用して、どこまでエレガントに内部処理を表現できるかに挑戦することは、Rubyプログラミングのよい練習になるでしょう。より高度な課題として、Ruby処理系を改造し、CellクラスをC言語で実装してLispの能力をRubyに取り込むことは、コンパイラの作成とあわせて興味深いテーマになるかもしれません。