前田修吾
先日、Pythonのメーリングリストで、再帰呼び出しを使った階乗の計算をどれ くらいまでできるかということが話題になりました。ちょっと気になったので Rubyではどれくらい計算できるのか試してみました。Rubyで階乗の計算を行う プログラムは、再帰呼び出しを使ってList1のように書くことができます。実 行結果はFig1のようになりました。どうも私の環境では1700と1800の間に限界 があるようです。ちなみにPythonでは9000くらいまで計算できました。これだ けの材料で判断するのは早計かもしれませんが、RubyインタプリタはPythonに くらべてスタックの消費が多いようですね:-(
このように再帰呼び出しは深くなる(呼び出し回数が多くなる)ほどスタックを 消費し、ついにはスタックを使い尽くしてしまいます。たとえば、List1では、 fact(n - 1)の呼び出しの時に、nの値を覚えておいて、後でかけ算をしてやる 必要があります。そのため、呼び出し回数に比例してスタックを消費してしま うわけです。
ところで、実は、List2のように再帰呼び出しをメソッドの最後に行うような 形に変形することで、原理的には再帰呼び出し時に何も値を覚えておく必要が なくなります。このような再帰は末尾再帰と呼ばれます。(詳しくは参考文献 [1]の1.2.1節を参照してください。) 末尾再帰ではスタックの消費を呼 び出し回数に関わらず一定にすることができます。ただ、そのためにはある種 の最適化が必要で、残念ながらRubyには実装されていません。
どうして、Rubyでできないようなことを紹介するかというと、実は末尾再帰の 最適化を行うためのちょっとしたパッチを用意したからです。(実は以前にも 同じようなことを試したことがあるのですが、かなり汚い手を使っています;-p) CD-ROMに収録されているruby17-tail-recursive.diffがそのパッチです。この パッチをRuby1.7(CVSの開発版)に適用し、Makefileを編集してCFLAGSに -DTAIL_RECURSIVEを追加してコンパイルすると、fact2.rbで10000の階乗も計 算することができます。ただ、実装の都合上、bindingを予約語にするという 文法変更を行っています(!)ので、このパッチが正式に取り入れられることは ないでしょう。こっそり遊ぶのに使ってください。
-- List1 fact.rb 素朴な再帰
def fact(n)
if n == 1
return 1
else
return n * fact(n - 1)
end
end
p fact(ARGV.shift.to_i)
-- Fig1 再帰呼び出しの限界
$ ruby -v
ruby 1.6.3 (2001-03-28) [i386-linux]
$ ruby fact.rb 1700
299835320555841809470113111....
$ ruby fact.rb 1800
fact.rb:5:in `fact': stack level too deep (SystemStackError)
from fact.rb:5:in `fact'
from fact.rb:5:in `fact'
....
-- List2 fact2.rb 末尾再帰化されたfact
def fact_iter(product, counter, max_count)
if counter > max_count
return product
else
return fact_iter(counter * product,
counter + 1,
max_count)
end
end
def fact(n)
return fact_iter(1, 1, n)
end
p fact(ARGV.shift.to_i)
さて、今回のお話は末尾再帰とは何の関係もありません。(これからも本題と 関係ないヨタ話が入ることがあるかもしれませんが、どうかご容赦ください。) 今回はRubyインタプリタのアプリケーションへの組み込みについてお話ししま す。
少し前に他の雑誌でも紹介した[2]のですが、筆者が作ったもので、 mod_ruby[3]というソフトウェアがあります。これはApacheというHTTP サーバにRubyインタプリタを組み込むモジュールで、プロセス起動のコストを 削減することにより、CGIよりも高速にRubyで記述されたWebアプリケーション を実行することができます。
この場合は高速化のためにRubyインタプリタの組み込みを行っていますが、こ のような例はむしろ少数派でしょう。ここでちょっとRubyの組み込みの意義に ついて考えてみたいと思います。
エディタなどのアプリケーションを使っていると、その機能に物足りなさを感 じることがあります。しかし、ユーザの要求は人によってそれぞれ異なるため、 すべての機能をアプリケーションに取り入れていたらきりがありません。時に はそれぞれの要求が矛盾することもあるでしょう。自分ではこれは素晴らしい 機能だと思っても、他の人にとってみればかえって邪魔であったりすることは よくあることです。(どうしてソニーの携帯のセンタージョグは決定ボタンを 兼ねているんでしょう。)
こういった問題を解決するために、気のきいたアプリケーションは拡張言語を 用意しています。たとえば、GNU Emacsというエディタは、EmacsLispと呼ばれ るLispの方言によって、ユーザが自由にエディタの機能を拡張できるようになっ ています。これは素晴らしいアイデアです。もしエディタの機能が気に入らな ければ、ユーザ自身がそれを変えることができるのです。
ただ、問題は言語処理系を実装するのがなかなか大変なことです。そこで、 Rubyの出番です。Rubyをアプリケーションの拡張言語として利用することで、 簡単にアプリケーションの拡張性を高めることができます。
まずは、Rubyインタプリタの仕組みを説明します。といっても、詳細にはあま り触れず、おおまかな処理の流れを簡単に説明するだけです。List3はRubyの ソースアーカイブ中の、main.cのmain()の定義です。
-- List3 main.c main()の定義
int
main(argc, argv, envp)
int argc;
char **argv, **envp;
{
#if defined(NT)
NtInitialize(&argc, &argv);
#endif
#if defined(__MACOS__) && defined(__MWERKS__)
argc = ccommand(&argv);
#endif
ruby_init();
ruby_options(argc, argv);
ruby_run();
return 0;
}
まず、ruby_init()という関数を呼び出しています*1 が、これはRubyインタプリタの初期化を行 う関数です。この関数ではトップレベルの環境の準備や、標準ライブラリの初 期化などが行われます。Rubyインタプリタを組み込むアプリケーションは、 Rubyインタプリタを呼び出す前にかならずこの関数を呼び出す必要があります。
ところで、みなさんはObjectとClassのどちらが先かご存知でしょうか。Ruby ではクラスもオブジェクトなので、Objectもオブジェクトであり、特定のクラ スに属しています。ObjectのクラスはClassという特別なクラスです。また、 Objectはすべてのクラスの祖先(スーパークラス)なので、当然ClassもObject を祖先としています。(Fig2)つまり、ObjectはClassの存在を前提にしており、 ClassはObjectの存在を前提にしているわけです。まさに鶏と卵のような関係 ですね。
Rubyはこの問題を解決するために、インタプリタの初期化時にちょっとしたト リックを使っています。(List4) 通常、オブジェクトを生成する際にはクラス を指定しますが、Objectを生成する際には、クラスを指定せず、空にしたまま で生成します。そして、同じようにModuleやClassも生成します。それから、 ObjectのクラスにClass(正確にはその特異クラス)を設定します。というわけ で、正解はObjectでした。
-- Fig2 ObjectとClassの関係
$ ruby -e 'p Object.type'
Class
$ ruby -e 'p Class.ancestors'
[Class, Module, Object, Kernel]
-- List4 object.c ObjectとClassの作成
void
Init_Object()
{
VALUE metaclass;
rb_cObject = boot_defclass("Object", 0);
rb_cModule = boot_defclass("Module", rb_cObject);
rb_cClass = boot_defclass("Class", rb_cModule);
metaclass = RBASIC(rb_cObject)->klass = rb_singleton_class_new(rb_cClass);
rb_singleton_class_attached(metaclass, rb_cObject);
metaclass = RBASIC(rb_cModule)->klass = rb_singleton_class_new(metaclass);
rb_singleton_class_attached(metaclass, rb_cModule);
metaclass = RBASIC(rb_cClass)->klass = rb_singleton_class_new(metaclass);
rb_singleton_class_attached(metaclass, rb_cClass);
...
ruby_options()はRubyに与えられたコマンドライン引数を解析し、-Kや-rなど のオプションを処理した後で、実行すべきスクリプト(引数で与えられたファ イルや-eで与えられた文字列)を構文木と呼ばれる木構造に変換(コンパイル) します。この構文木はNodeDumpという拡張ライブラリ[4]を利用して表 示することができます。たとえば、List5のようなスクリプトの構文木を表示 させるとFig3のようになります。普通のRubyユーザにはあまり縁のないような ソフトウェアですが、この連載を読まれているような方には興味深いのではな いでしょうか。*2
-- List5 hello.rb
def hello
puts "hello world"
end
hello
-- Fig3 List5の構文木
$ ruby -r NodeDump hello.rb
NodeDump V0.1.2
NODE_BLOCK:
NODE_NEWLINE: [/tmp/hello.rb:1]
NODE_DEFN: method 8977 (hello)
NODE_SCOPE:
NODE_BLOCK:
NODE_ARGS: count = 0
additional default values:
NODE_NEWLINE: [/tmp/hello.rb:2]
NODE_FCALL: to function: 6753 (puts)
Parameters:
NODE_ARRAY: size = 1
NODE_STR: "hello world"
NODE_NEWLINE: [/tmp/hello.rb:4]
NODE_VCALL: self.hello
ruby_run()は構文木にコンパイルされたプログラムを実際に実行します。Perl などと違って、Rubyの場合はメソッド定義やクラス定義などもすべてこの実行 時に行われます。*3 実行 部の核となる部分はeval.cのrb_eval()という非常に長い関数です。rb_eval() は構文木の各ノードを再帰的に辿りながら、ノードの種類によってメソッド呼 び出しや条件分岐などの適切な処理を行います。Rubyはこのように実行部に再 帰を利用している上に、alloca()を多用しているので、スタックの消費が多く なっています。alloca()を利用できない環境ではmalloc()によって実装された 代用品が利用されますが、その分実行速度は遅くなります。
ruby_run()にはプログラムの実行の他にもう一つ仕事があります。それは終了 処理です。主な処理は、
の三つです。ここでちょっと注意が必要なのが三つ目のファイナライザの実行 です。
ファイナライザとは、GC(ガーベージコレクション)時にどこからも参照されな くなったオブジェクトが回収される時に呼び出されるコードで、 ObjectSpace::define_finalizerで設定することができます。プログラムの終 了時には、すべてのオブジェクトがどこからも参照されなくなると考えられる ため、すべての(まだ実行されていない)ファイナライザが実行されます。*4
しかし、筆者としては、それに依存するようなプログラムを書くべきではない と思います。その理由は二つあります。一つは、ファイナライザは本来あくま でもリソースの解放のためのものであり、積極的な動作(たとえば何らかの出 力など)を行わせるためのものではないということです。したがって、ファイ ナライザが実行されなかったとしてもプログラムは正常に動作するべきです。 もう一つは、mod_rubyのように、アプリケーションにRubyインタプリタを組み 込んで、一つのインタプリタで複数のRubyプログラムを実行する場合には、個々 のプログラムの終了時に必ずしもファイナライザが呼ばれないということです。 また、将来Rubyの仕様自体が変わってしまうことも考えられます。実際、Java の場合には仕様変更があり、以前の仕様では必ずファイナライザが呼び出され ましたが、現在の仕様では必ず呼ばれるとはかぎりません。
さて、それでは実際にRubyインタプリタを利用してみることにしましょう。 まずはRubyをリンクしたプログラムをビルドするためのMakefileを用意します。
手でMakefileを書いてもよいのですが、Rubyのへッダファイルなどがインストー ルされるディレクトリは環境によって異なるため、それぞれの環境に適した Makefileを自動的に生成するスクリプトを作成することにします。
configure.rb(List6)はmkmf.rbの機能を利用し、Makefile.in(List7)という雛 型から適切なMakefileを生成するスクリプトです。Makefile.in中の@CC@のよ うな文字列を置換して、List8のようなMakefileを出力します。 環境に よって適切な値を得るために、Config::CONFIGというHashを利用しています。 このHashにはRubyをconfigureした時の情報が格納されています。また、 $hdrdirという変数を利用していますが、これはruby.hなどのへッダファイル があるディレクトリのパスです。
-- List6 configure.rb
#!/usr/bin/env ruby
require "mkmf"
config = {}
config["CC"] = Config::CONFIG["CC"]
config["CFLAGS"] = Config::CONFIG["CFLAGS"] + " -I" + $hdrdir
config["LIBS"] = Config::CONFIG["LIBS"]
config["LIBRUBYARG"] = Config::CONFIG["LIBRUBYARG"]
open("Makefile.in") do |min|
open("Makefile", "w") do |mout|
while line = min.gets
line.gsub!(/@.*?@/) do |s|
key = s[1..-2]
config[key]
end
mout.print(line)
end
end
end
-- List7 Makefile.in
CC = @CC@
CFLAGS = @CFLAGS@
LIBS = @LIBS@
LIBRUBYARG = @LIBRUBYARG@
PROGRAM = test1
OBJS = test1.o
.c.o:
$(CC) $(CFLAGS) -c $<
all: $(PROGRAM)
clean:
rm -f $(PROGRAM) $(OBJS)
$(PROGRAM): $(OBJS)
$(CC) $(OBJS) $(LIBRUBYARG) $(LIBS) -o $@
-- List8 Makefileの例
CC = gcc
CFLAGS = -g -O2 -fPIC -I/usr/lib/ruby/1.6/i386-linux
LIBS = -ldl -lcrypt -lm
LIBRUBYARG = -L. -lruby
PROGRAM = test1
OBJS = test1.o
.c.o:
$(CC) $(CFLAGS) -c $<
all: $(PROGRAM)
clean:
rm -f $(PROGRAM) $(OBJS)
$(PROGRAM): $(OBJS)
$(CC) $(OBJS) $(LIBRUBYARG) $(LIBS) -o $@
List9は文字列をRubyプログラムを評価するプログラムです。まず、はじめに ruby_init()によってRubyインタプリタの初期化を行っています。 rb_eval_string()は引数で与えられた文字列をRubyプログラムとして評価しま す。この際、Rubyインタプリタの仕組みで説明したような、コンパイル 処理と実行処理が行われます。このプログラムを実行した結果がFig4です。た しかに"this is a testprogram."と出力されていますが、プログラムがあまり にも簡単なので、本当にRubyインタプリタが呼び出されているのかどうか疑い たくなりますね。
そこでもう少しRubyらしいプログラムを実行することにしましょう。(List10) rb_eval_string()の返り値の型はVALUEで、Rubyプログラムを評価した結果を 返します。たとえば、"1 + 1"というRubyプログラムを評価した場合は、 Fixnumオブジェクトの2を返します。List10では"Object.new"というプログラ ムを評価して、結果をobjという変数に代入しています。これだけでは何も出 力されないため、objをrb_p()という関数によって出力しています。rb_p()は Rubyのpに相当する関数で、オブジェクトを人間に理解しやすい形式で出力し ます。実行結果はFig5のようになります。これでRubyインタプリタが実際に利 用されていると信じていただけたのではないでしょうか。
-- List9 test1.c
#include "ruby.h"
int main()
{
ruby_init();
rb_eval_string("puts 'this is a test program.'");
return 0;
}
-- Fig4 List9の実行結果
$ ruby configure.rb
$ make
gcc -g -O2 -fPIC -I/usr/lib/ruby/1.6/i386-linux -c test1.c
gcc test1.o -L. -lruby -ldl -lcrypt -lm -o test1
$ ./test1
this is a test program.
-- List10 test2.c
#include "ruby.h"
int main()
{
VALUE obj;
ruby_init();
obj = rb_eval_string("Object.new");
rb_p(obj);
return 0;
}
-- Fig5 List10の実行結果
$ ./test2
#<Object:0x4024ecd4>
今度はRubyプログラムが記述されたファイルをロードしてみることにしましょ う。(List11) rb_load()は指定されたファイルをRubyスクリプトとして実行 します。第1引数にはファイル名を指定しますが、ちょっと注意が必要なのは、 Cの文字列(char*)ではなく、Rubyの文字列(VALUE)で指定する必要がある点で す。ここではrb_str_new2()によって"foo.rb"というStringオブジェクトを生 成しています。
第2引数はスクリプトを個別の名前空間で実行するかどうかを指定します。第2 引数が真の場合、スクリプトは無名モジュールの名前空間の下で実行されます。 トップレベルで定義されたクラスやメソッドなどはObjectの下に定義される代 りに、その無名モジュールの下に定義されます。したがって、グローバルな名 前空間の汚染の危険性を低くすることが可能になります。この機能は、 mod_rubyのように関連性のない複数のスクリプトを実行する必要があるような 場合に有用です。
-- List11 test3.c
#include "ruby.h"
int main()
{
ruby_init();
rb_load(rb_str_new2("foo.rb"), 0);
return 0;
}
ここで、ちょっとList12のようなプログラムをコンパイルして実行してみてく ださい。実行してみると何も出力されません。Rubyのバグでしょうか。
いえいえ、これはRubyのバグではありません。rb_eval_string()はENDブロッ クの実行などの終了処理は一切行いませんから、終了処理を行わせたい場合は 自分で行う必要があります。
List13は終了処理の例です。ruby_stop()はRubyインタプリタの仕組み で説明したような終了処理を行う関数です。ruby_stop()は終了処理をした後 でexit()を呼び出します。その際、exit()にはruby_stop()の引数が渡されま す。exit()したくないという場合にはruby_finalize()という関数を利用する ことができます。ruby_finalize()は引数を取りません。ただ、 ruby_finalize()の場合はスレッドの強制終了は行われませんので、注意が必 要です。
-- List12 test4.c
#include "ruby.h"
int main()
{
ruby_init();
rb_eval_string("END { puts 'goodbye to romance' }");
return 0;
}
-- List13 test5.c
#include "ruby.h"
int main()
{
ruby_init();
rb_eval_string("END { puts 'goodbye to romance' }");
ruby_stop(0);
return 0;
}
次回も引き続きRubyインタプリタの組み込みに関する話題を取り上げます。今 度はもう少し実際的なプログラムについて解説したいと思います。
H・エーベルソン/G・J・サスマン著, 「プログラムの構造と実行」, 元吉文男訳, マグロウヒル出版
前田修吾, Software Design 2001年3月号「mod_rubyによるWebシステム構築」, 技術評論社, <URL:http://www.shugo.net/article/>
mod_ruby <URL:http://www.modruby.net/>
NodeDump <URL:http://www.pragmaticprogrammer.com/ruby/downloads/nodeDump.html>
*1 WindowsやMacでは他の
処理をその前にしています。
*2 実は非常に読者層を限定しているような気がしてちょっと
心配です。
*3 Perlなどの場合はコンパイル時に行われます。
*4
終了時にはもはやオブジェクトを回収する必要はないため、実際にGCが行われ
るわけではありません。