[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 {