Chas Emerick wrote:
> In those rare circumstances where you need to write mutually-recursive
> functions without consuming stack, clojure provides a trampoline
> implementation (introduced last November here:
> http://groups.google.com/group/clojure/browse_frm/thread/6257cbc4454bcb85)
> . There's obviously a performance penalty associated with their use,
> but it's nice to have that escape hatch.
>
I was thinking about this. For any given tail recursive function, it can be
turned into a
non-stack-building loop. The transformation I'm thinking of looks like this:
public int foo(int bar, String baz) {
/* Some logic for foo, including an escape */
int newBar = ...;
String newBaz = ...;
return foo(newBar, newBaz);
}
becomes
public int foo(int bar, String baz) {
label :top;
/* Some logic for foo, including an escape */
bar = newBar;
baz = newBaz;
jump :top;
}
Now consider two mutually recursive functions, 'foo' and 'bar'.
public int foo(int fooInt, String fooString) {
/* Some logic for foo, possibly including an escape */
int newBarInt = ...;
String newBarString = ...;
return bar(newBarInt, newBarString);
}
public int bar(int barInt, String barString) {
/* Some logic for bar, possibly including an escape */
int newFooInt = ...;
String newFooString = ...;
return foo(newFooInt, newFooString);
}
Given those two functions, what's to keep us from creating a structure like
this?
private static class FooArgs {
public int fooInt;
public String fooString;
public FooArgs(int fooInt, String fooString) {
this.fooInt = fooInt;
this.fooString = fooString;
}
}
private static class BarArgs {
public int barInt;
public String barString;
public BarArgs(int barInt, String barString) {
this.barInt = barInt;
this.barString = barString;
}
}
public int foo(int fooInt, String fooString) {
return foobar(new FooArgs(fooInt, fooString), null, true);
}
public int bar(int barInt, String barString) {
return foobar(null, new BarArgs(barInt, barString), false);
}
private int foobar(FooArgs fooArgs, BarArgs, barArgs, boolean doFoo) {
String fooString, barString;
int fooInt, barInt;
if(doFoo) {
fooInt = fooArgs.fooInt;
fooString = fooArgs.fooString;
fooArgs = null;
jump :foo
} else {
barInt = barArgs.barInt;
barString = barArgs.barString;
barArgs = null;
jump :bar
}
label :foo
/* Some logic for foo, including an escape */
barInt = ...
barString = ...
fooString = null;
jump :bar;
label :bar;
/* Some logic for bar, including an escape */
fooInt = ...
fooString = ...
barString = null;
jump :foo;
}
I know there are method size limits, but assuming we stay under them, this
should work for solving
at least the common case of two, small, mutually recursive functions. And it
could be generalized up.
~~ Robert Fischer.
Grails Training http://GroovyMag.com/training
Smokejumper Consulting http://SmokejumperIT.com
Enfranchised Mind Blog http://EnfranchisedMind.com/blog
Check out my book, "Grails Persistence with GORM and GSQL"!
http://www.smokejumperit.com/redirect.html
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "JVM
Languages" group.
To post to this group, send email to jvm-languages@googlegroups.com
To unsubscribe from this group, send email to
jvm-languages+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/jvm-languages?hl=en
-~----------~----~----~----~------~----~------~--~---
