From: Shugo Maeda Date: 2000-09-17T09:55:18+09:00 Subject: [ruby-dev:10934] Re: proper tail recursion 前田です。 At Fri, 15 Sep 2000 05:26:55 +0900, Shugo Maeda wrote: > tail recursiveにする方法を思いついたので、試しに実装してみました。 末尾のメソッドコールすべてに同様の手法を適用してみました。 # 原理的にはSchemeと同じ? まだ得失についてはよくわかりませんけど、ちょっと試したかぎりでは 著しくパフォーマンスが低下するようなことはないようです。 1.6へのパッチです。 # 前のパッチは不用です。 Index: eval.c =================================================================== RCS file: /home/cvs/ruby/eval.c,v retrieving revision 1.104 diff -u -r1.104 eval.c --- eval.c 2000/09/15 06:00:23 1.104 +++ eval.c 2000/09/17 00:09:55 @@ -504,6 +504,11 @@ static struct FRAME *top_frame; static struct SCOPE *top_scope; +static VALUE tail_call_recv = Qnil; +static ID tail_call_mid = 0; +static VALUE tail_call_args = Qnil; +static int tail_call_scope = 0; + #define PUSH_FRAME() { \ struct FRAME _frame; \ _frame.prev = ruby_frame; \ @@ -770,6 +775,7 @@ #define TAG_RAISE 0x6 #define TAG_THROW 0x7 #define TAG_FATAL 0x8 +#define TAG_TAIL_CALL 0x9 #define TAG_MASK 0xf VALUE ruby_class; @@ -2413,6 +2419,53 @@ result = rb_call(CLASS_OF(self),self,node->nd_mid,0,0,2); break; + case NODE_TAIL_CALL: + { + VALUE recv; + int argc; VALUE *argv; /* used in SETUP_ARGS */ + TMP_PROTECT; + + return_check(); + BEGIN_CALLARGS; + recv = rb_eval(self, node->nd_recv); + SETUP_ARGS(node->nd_args); + END_CALLARGS; + tail_call_recv = recv; + tail_call_mid = node->nd_mid; + tail_call_args = rb_ary_new4(argc, argv); + tail_call_scope = 0; + TMP_PROTECT_END; + JUMP_TAG(TAG_TAIL_CALL); + } + break; + + case NODE_TAIL_FCALL: + { + int argc; VALUE *argv; /* used in SETUP_ARGS */ + TMP_PROTECT; + + return_check(); + BEGIN_CALLARGS; + SETUP_ARGS(node->nd_args); + END_CALLARGS; + tail_call_recv = self; + tail_call_mid = node->nd_mid; + tail_call_args = rb_ary_new4(argc, argv); + tail_call_scope = 1; + TMP_PROTECT_END; + JUMP_TAG(TAG_TAIL_CALL); + } + break; + + case NODE_TAIL_VCALL: + return_check(); + tail_call_recv = self; + tail_call_mid = node->nd_mid; + tail_call_args = Qnil; + tail_call_scope = 2; + JUMP_TAG(TAG_TAIL_CALL); + break; + case NODE_SUPER: case NODE_ZSUPER: { @@ -4306,45 +4359,86 @@ VALUE *argv; /* OK */ int scope; { + VALUE result; NODE *body; /* OK */ int noex; - ID id = mid; + ID id; struct cache_entry *ent; + int state; - /* 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); + again: + id = mid; + 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; + } + } } + + result = rb_call0(klass, recv, id, argc, argv, body, noex & NOEX_UNDEF); } + end: + POP_TAG(); + switch (state) { + case 0: + return result; + case TAG_TAIL_CALL: + recv = tail_call_recv; + klass = CLASS_OF(recv); + 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; + } + scope = tail_call_scope; - return rb_call0(klass, recv, id, argc, argv, body, noex & NOEX_UNDEF); + tail_call_recv = Qnil; + tail_call_mid = 0; + tail_call_args = Qnil; + tail_call_scope = 0; + goto again; + default: + JUMP_TAG(state); + } } VALUE @@ -5596,6 +5690,9 @@ rb_global_variable((VALUE*)&ruby_eval_tree); rb_global_variable((VALUE*)&ruby_dyna_vars); + + rb_global_variable(&tail_call_recv); + 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/17 00:09:55 @@ -58,6 +58,9 @@ NODE_CALL, NODE_FCALL, NODE_VCALL, + NODE_TAIL_CALL, + NODE_TAIL_FCALL, + NODE_TAIL_VCALL, NODE_SUPER, NODE_ZSUPER, NODE_ARRAY, Index: parse.y =================================================================== RCS file: /home/cvs/ruby/parse.y,v retrieving revision 1.57 diff -u -r1.57 parse.y --- parse.y 2000/09/15 06:00:26 1.57 +++ parse.y 2000/09/17 00:09:59 @@ -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 '(' ')' { @@ -4478,6 +4479,28 @@ return a; } return NEW_SUPER(a); +} + +static NODE* +new_return(node) + NODE *node; +{ + switch (nd_type(node)) { + case NODE_CALL: + nd_set_type(node, NODE_TAIL_CALL); + nd_set_line(node, ruby_sourceline); + return node; + case NODE_FCALL: + nd_set_type(node, NODE_TAIL_FCALL); + nd_set_line(node, ruby_sourceline); + return node; + case NODE_VCALL: + nd_set_type(node, NODE_TAIL_VCALL); + nd_set_line(node, ruby_sourceline); + return node; + default: + return NEW_RETURN(node); + } } static struct local_vars {