[ruby-dev:10934] Re: proper tail recursion

前田です。

At Fri, 15 Sep 2000 05:26:55 +0900,
Shugo Maeda <[e-mail]> 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 {