From: Shugo Maeda Date: 2000-09-15T05:26:55+09:00 Subject: [ruby-dev:10921] proper tail recursion 前田です。 tail recursiveにする方法を思いついたので、試しに実装してみました。 $ ./ruby16 -e 'def foo; return foo; end' でちゃんと無限ループになります:) また下記のような再帰版のfact2.rbで、10000の階乗まで計算できること を確認しました。 # 普通のrubyでは3000くらいでアウトでした。 -- fact2.rb --- def fact_iter(product, counter, max_count) if counter > max_count return product else return fact_iter(product * counter, counter + 1, max_count) end end def fact(n) return fact_iter(1, 1, n) end print fact(ARGV[0].to_i), "\n" ------------- rb_call()のたびに一回余分にPUSH_TAG()/EXEC_TAG()するので速度に影 響が出るかと思ったのですが、思ったほど影響はありませんでした。 現時点ではreturnを使ってない場合はtail recursionが検出されないと いう制限があります。 1.6へのパッチです。 -- 前田 修吾 Index: eval.c =================================================================== RCS file: /home/cvs/ruby/eval.c,v retrieving revision 1.103 diff -u -r1.103 eval.c --- eval.c 2000/09/12 06:41:23 1.103 +++ eval.c 2000/09/14 19:52:57 @@ -504,6 +504,9 @@ static struct FRAME *top_frame; static struct SCOPE *top_scope; +static ID tail_call_mid = 0; +static VALUE tail_call_args = Qnil; + #define PUSH_FRAME() { \ struct FRAME _frame; \ _frame.prev = ruby_frame; \ @@ -770,6 +773,7 @@ #define TAG_RAISE 0x6 #define TAG_THROW 0x7 #define TAG_FATAL 0x8 +#define TAG_TAILCALL 0x9 #define TAG_MASK 0xf VALUE ruby_class; @@ -2369,6 +2373,27 @@ JUMP_TAG(TAG_RETURN); break; + case NODE_RETURN_FCALL: + { + int argc; VALUE *argv; /* used in SETUP_ARGS */ + TMP_PROTECT; + + BEGIN_CALLARGS; + SETUP_ARGS(node->nd_args); + END_CALLARGS; + tail_call_mid = node->nd_mid; + tail_call_args = rb_ary_new4(argc, argv); + TMP_PROTECT_END; + JUMP_TAG(TAG_TAILCALL); + } + break; + + case NODE_RETURN_VCALL: + tail_call_mid = node->nd_mid; + tail_call_args = Qnil; + JUMP_TAG(TAG_TAILCALL); + break; + case NODE_ARGSCAT: result = rb_ary_concat(rb_eval(self, node->nd_head), rb_eval(self, node->nd_body)); @@ -4306,45 +4331,79 @@ VALUE *argv; /* OK */ int scope; { + VALUE result; NODE *body; /* OK */ int noex; ID id = mid; struct cache_entry *ent; + int state; + + again: + PUSH_TAG(PROT_NONE); + if ((state = EXEC_TAG()) == 0) { + /* is it in the method cache? */ + ent = cache + EXPR1(klass, mid); + if (ent->mid == mid && ent->klass == klass) { + if (!ent->method) { + result = rb_undefined(recv, mid, argc, argv, scope==2?CSTAT_VCALL:0); + goto end; + } + klass = ent->origin; + id = ent->mid0; + noex = ent->noex; + body = ent->method; + } + else if ((body = rb_get_method_body(&klass, &id, &noex)) == 0) { + if (scope == 3) { + rb_raise(rb_eNameError, "super: no superclass method `%s'", + rb_id2name(mid)); + } + result = rb_undefined(recv, mid, argc, argv, scope==2?CSTAT_VCALL:0); + goto end; + } + + if (mid != missing) { + /* receiver specified form for private method */ + if ((noex & NOEX_PRIVATE) && scope == 0) { + result = rb_undefined(recv, mid, argc, argv, CSTAT_PRIV); + goto end; + } + + /* self must be kind of a specified form for private method */ + if ((noex & NOEX_PROTECTED)) { + VALUE defined_class = klass; + while (TYPE(defined_class) == T_ICLASS) + defined_class = RBASIC(defined_class)->klass; + if (!rb_obj_is_kind_of(ruby_frame->self, defined_class)) { + result = rb_undefined(recv, mid, argc, argv, CSTAT_PROT); + goto end; + } + } + } - /* is it in the method cache? */ - ent = cache + EXPR1(klass, mid); - if (ent->mid == mid && ent->klass == klass) { - if (!ent->method) - return rb_undefined(recv, mid, argc, argv, scope==2?CSTAT_VCALL:0); - klass = ent->origin; - id = ent->mid0; - noex = ent->noex; - body = ent->method; - } - else if ((body = rb_get_method_body(&klass, &id, &noex)) == 0) { - if (scope == 3) { - rb_raise(rb_eNameError, "super: no superclass method `%s'", - rb_id2name(mid)); - } - return rb_undefined(recv, mid, argc, argv, scope==2?CSTAT_VCALL:0); - } - - if (mid != missing) { - /* receiver specified form for private method */ - if ((noex & NOEX_PRIVATE) && scope == 0) - return rb_undefined(recv, mid, argc, argv, CSTAT_PRIV); - - /* self must be kind of a specified form for private method */ - if ((noex & NOEX_PROTECTED)) { - VALUE defined_class = klass; - while (TYPE(defined_class) == T_ICLASS) - defined_class = RBASIC(defined_class)->klass; - if (!rb_obj_is_kind_of(ruby_frame->self, defined_class)) - return rb_undefined(recv, mid, argc, argv, CSTAT_PROT); + result = rb_call0(klass, recv, id, argc, argv, body, noex & NOEX_UNDEF); + } + end: + POP_TAG(); + switch (state) { + case 0: + return result; + case TAG_TAILCALL: + mid = tail_call_mid; + if (NIL_P(tail_call_args)) { + argc = 0; + argv = 0; + } + else { + argc = RARRAY(tail_call_args)->len; + argv = RARRAY(tail_call_args)->ptr; } + tail_call_mid = 0; + tail_call_args = Qnil; + goto again; + default: + JUMP_TAG(state); } - - return rb_call0(klass, recv, id, argc, argv, body, noex & NOEX_UNDEF); } VALUE @@ -5599,6 +5658,8 @@ rb_global_variable((VALUE*)&ruby_eval_tree); rb_global_variable((VALUE*)&ruby_dyna_vars); + + rb_global_variable(&tail_call_args); rb_define_virtual_variable("$@", errat_getter, errat_setter); rb_define_hooked_variable("$!", &ruby_errinfo, 0, errinfo_setter); Index: node.h =================================================================== RCS file: /home/cvs/ruby/node.h,v retrieving revision 1.16 diff -u -r1.16 node.h --- node.h 2000/09/07 06:59:36 1.16 +++ node.h 2000/09/14 19:52:57 @@ -64,6 +64,8 @@ NODE_ZARRAY, NODE_HASH, NODE_RETURN, + NODE_RETURN_FCALL, + NODE_RETURN_VCALL, NODE_YIELD, NODE_LVAR, NODE_DVAR, Index: parse.y =================================================================== RCS file: /home/cvs/ruby/parse.y,v retrieving revision 1.56 diff -u -r1.56 parse.y --- parse.y 2000/09/12 05:37:24 1.56 +++ parse.y 2000/09/14 19:53:00 @@ -95,6 +95,7 @@ static NODE *new_call(); static NODE *new_fcall(); static NODE *new_super(); +static NODE *new_return(); static NODE *gettable(); static NODE *assignable(); @@ -419,7 +420,7 @@ { if (!compile_for_eval && !cur_mid && !in_single) yyerror("return appeared outside of method"); - $$ = NEW_RETURN($2); + $$ = new_return($2); } | command_call | expr kAND expr @@ -1099,7 +1100,7 @@ if (!compile_for_eval && !cur_mid && !in_single) yyerror("return appeared outside of method"); value_expr($3); - $$ = NEW_RETURN($3); + $$ = new_return($3); } | kRETURN '(' ')' { @@ -4470,6 +4471,27 @@ return a; } return NEW_SUPER(a); +} + +static NODE* +new_return(node) + NODE *node; +{ + switch (nd_type(node)) { + case NODE_FCALL: + if (node->nd_mid == cur_mid) { + nd_set_type(node, NODE_RETURN_FCALL); + return node; + } + break; + case NODE_VCALL: + if (node->nd_mid == cur_mid) { + nd_set_type(node, NODE_RETURN_VCALL); + return node; + } + break; + } + return NEW_RETURN(node); } static struct local_vars {