Shoeisha Technology Media

CodeZine(コードジン)

特集ページ一覧

L2Lisp in Ruby

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

  • ブックマーク
  • LINEで送る
  • このエントリーをはてなブックマークに追加
2007/07/23 00:00

静的スコープ、末尾呼出し(末尾再帰を含む)の最適化、およびマクロを備えた近代的なLispの小さなインタープリタをRuby(およびJRuby)で作ります。Rubyのデータ型と親和性が高く、簡単に組込み関数を増設できる手頃なLisp処理系として利用できます。

目次

はじめに

 P.Graham著『On Lisp』に示されているように、現代的なLispプログラミングでは静的スコープ(字句的スコープ)と末尾呼出し(末尾再帰を含む)の最適化のもとでのマクロが重要な意味をもちます。しかし、今まで処理系作成の初心者が内部に手を入れやすい手頃な大きさの実装が事実上ありませんでした。

 ここでは、そういったモダンな特徴を備えた小さなLispインタープリタL2LispをRubyで作ってみます。L2Lisp(Little Lambda Lisp)は、Lispの理論的背景であるラムダ算法(lambda calculus)に対し、有力なLisp方言であるSchemeと同程度に忠実である一方、その他の点では広く普及しているEmacs Lispのサブセットとしたオリジナルの小型Lispです。

 実行例としてtak関数を定義し、実行する様子を示します。Ruby以外に必要なのはL2Lisp.rbだけです。(tak 18 12 6)から7を得るまでCore Duo 2GHz、Mac OS X Tigerで約9秒かかります。

実行例
$ 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

 単にtakと入力することで、定義したtakの値を見ることができます。ここでL2Lispの特徴をいくつか見ることができます。

> tak
(#<closure> (3) (cond ((>= (#<arg> 0 1 . y) (#<arg> 0 0 . x)) (#<arg> 0 2 . z)) 
(t (tak (tak (- (#<arg> 0 0 . x) 1) (#<arg> 0 1 . y) (#<arg> 0 2 . z)) (tak (- (
#<arg> 0 1 . y) 1) (#<arg> 0 2 . z) (#<arg> 0 0 . x)) (tak (- (#<arg> 0 2 . z) 1
) (#<arg> 0 0 . x) (#<arg> 0 1 . y))))))
> 
  • (Schemeと同じく)関数としての値と変数としての値は区別されません。変数の値として、関数takの(コンパイル後の)関数定義を見ることができます。
  • 関数定義時、(if…)は条件式(cond…)マクロ展開されます。
  • 関数定義時、ローカル変数は(#<arg> 0 1 . y)のような形式にコンパイルされます。0は環境リストの第0フレーム(=最内フレーム)、1はそのフレームの(0から数えて)第1要素、yはコンパイル前の変数名を表します。

 コンパイルといっても、ローカル変数の名前解決とマクロ展開だけのコンパイルですが、モダンなLispに見られる様々な特徴(例えば、なぜCommon Lispのeval関数は、大域的な環境で評価するのか、など)を再現するには十分です。Ruby上の比較的完成度が高いLisp実装として使用するほか、Lispの内部実装を理解し、様々な着想を試すための実験台としても利用できると思います。

対象読者

 本稿は、Lisp処理系の作り方に興味のある読者を対象とします。Rubyのオブジェクトとしてデータ構造を作りますから、メモリ管理の方法等はここでは扱いませんが(興味のある方は標準PascalによるオリジナルのL2Lispを参照してください)、静的スコープ、末尾呼出しの最適化、大域脱出などのRubyによる実装例をみることができます。

必要な環境

 MacおよびWindows(Cygwin)上のRuby 1.8.2、1.8.6およびJava上のJRuby 1.0で動作を確認しています。現行のどのRubyでも動くはずです。

処理系の構成

 単体のLispインタープリタとして利用するほか、他の(大規模な)Rubyプログラムの中に組み込めるようにするため、大域的な名前空間には「L2Lisp」というモジュール名だけを定義します。

プログラムの概観
module L2Lisp
  …
  class EvalError < RuntimeError … end # 評価時例外
  class Thrown < EvalError … end       # Lispがthrowした状態
  class ProperListExpected < EvalError … end
  class Cell … end                     # consセルのクラス
  def str(x) … end                     # Lisp式の文字列表現
  def mapc(x, &block) … end            # リストのイテレータ
  class Reader … end                   # Lisp式の読込みクラス
  class Interp … end                   # Lispインタープリタ
  PRELUDE = %q{ … }                    # 初期化Lispスクリプト
end

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

 単体のRubyスクリプトとして実行したときは__FILE__ == $0が成立します。このときLispインタープリタのインスタンスをL2Lisp::Interp.newで作り、標準入力STDINから与えられたLisp式、またはコマンド行の引数として与えられたLispスクリプトをrunメソッドで実行します。


  • ブックマーク
  • LINEで送る
  • このエントリーをはてなブックマークに追加

修正履歴

  • 2011/03/18 15:56 沖ソフトウェアと On Lisp の URL を更新しました。

著者プロフィール

All contents copyright © 2005-2019 Shoeisha Co., Ltd. All rights reserved. ver.1.5