It seems like tail-calls will become mandatory in the not too distant future.
What support do we have for tail-calls? I remember discussing this early on in the project, but I'm not sure that at this point in time the intermediate representation supports it.
Marc
Begin forwarded message:
From: David Herman dherman@ccs.neu.edu Date: January 30, 2011 12:04:29 PM EST To: YC yinso.chen@gmail.com Cc: Racket Users users@racket-lang.org Subject: Re: [racket] moby/wescheme & TCO
I don't have your answer, but an interesting anecdote: I learned recently why the setTimeout(k, 0) trick is so slow. Apparently too many web sites (including nytimes.com, I believe) rely on a minimum delay of somewhere between 4 and 10ms to do animations, so browsers have to throttle the events. As I understand it, Firefox uses a 10ms minimum delay, and Chrome uses 4ms.
Since Chrome seems to have gotten away with dropping it to 4ms, we may be able to do the same -- though I haven't heard anyone specifically say they planned to. Maybe at some point we can eliminate this silliness altogether, and setTimeout could become a more viable tool for compiler-writers. But happily, the ECMAScript committee recently agreed to try to mandate proper tail calls in the next version of the standard. So with a little (okay, maybe more than a little) luck, compiler-writers may eventually be able to rely on having tail calls built in to the web.
Dave
On Jan 29, 2011, at 9:12 PM, YC wrote:
Hi all -
I am wondering if there are documentations on how moby/wescheme solve the tail call optimization issue to compile down to javascript. My google'fu is failing me.
If not - can someone shed some light on how it's done?
Thanks, yc
For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
Afficher les réponses par date
It seems like tail-calls will become mandatory in the not too distant future.
What support do we have for tail-calls? I remember discussing this early on in the project, but I'm not sure that at this point in time the intermediate representation supports it.
Marc
Begin forwarded message:
From: David Herman dherman@ccs.neu.edu Date: January 30, 2011 12:04:29 PM EST To: YC yinso.chen@gmail.com Cc: Racket Users users@racket-lang.org Subject: Re: [racket] moby/wescheme & TCO
I don't have your answer, but an interesting anecdote: I learned recently why the setTimeout(k, 0) trick is so slow. Apparently too many web sites (including nytimes.com, I believe) rely on a minimum delay of somewhere between 4 and 10ms to do animations, so browsers have to throttle the events. As I understand it, Firefox uses a 10ms minimum delay, and Chrome uses 4ms.
Since Chrome seems to have gotten away with dropping it to 4ms, we may be able to do the same -- though I haven't heard anyone specifically say they planned to. Maybe at some point we can eliminate this silliness altogether, and setTimeout could become a more viable tool for compiler-writers. But happily, the ECMAScript committee recently agreed to try to mandate proper tail calls in the next version of the standard. So with a little (okay, maybe more than a little) luck, compiler-writers may eventually be able to rely on having tail calls built in to the web.
Dave
On Jan 29, 2011, at 9:12 PM, YC wrote:
Hi all -
I am wondering if there are documentations on how moby/wescheme solve the tail call optimization issue to compile down to javascript. My google'fu is failing me.
If not - can someone shed some light on how it's done?
Thanks, yc
For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
Tachyon-list mailing list Tachyon-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/tachyon-list
It should be possible to analyze the tail recursive functions and transform them so the recursion becomes a loop in the CFG. This way we can keep the IR the same-old SSA.
- Maxime
It seems like tail-calls will become mandatory in the not too distant future.
What support do we have for tail-calls? I remember discussing this early on in the project, but I'm not sure that at this point in time the intermediate representation supports it.
Marc
Begin forwarded message:
From: David Herman dherman@ccs.neu.edu Date: January 30, 2011 12:04:29 PM EST To: YC yinso.chen@gmail.com Cc: Racket Users users@racket-lang.org Subject: Re: [racket] moby/wescheme & TCO
I don't have your answer, but an interesting anecdote: I learned recently why the setTimeout(k, 0) trick is so slow. Apparently too many web sites (including nytimes.com, I believe) rely on a minimum delay of somewhere between 4 and 10ms to do animations, so browsers have to throttle the events. As I understand it, Firefox uses a 10ms minimum delay, and Chrome uses 4ms.
Since Chrome seems to have gotten away with dropping it to 4ms, we may be able to do the same -- though I haven't heard anyone specifically say they planned to. Maybe at some point we can eliminate this silliness altogether, and setTimeout could become a more viable tool for compiler-writers. But happily, the ECMAScript committee recently agreed to try to mandate proper tail calls in the next version of the standard. So with a little (okay, maybe more than a little) luck, compiler-writers may eventually be able to rely on having tail calls built in to the web.
Dave
On Jan 29, 2011, at 9:12 PM, YC wrote:
Hi all -
I am wondering if there are documentations on how moby/wescheme solve the tail call optimization issue to compile down to javascript. My google'fu is failing me.
If not - can someone shed some light on how it's done?
Thanks, yc
For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
Tachyon-list mailing list Tachyon-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/tachyon-list
On 2011-01-30, at 1:18 PM, chevalma@iro.umontreal.ca wrote:
It should be possible to analyze the tail recursive functions and transform them so the recursion becomes a loop in the CFG. This way we can keep the IR the same-old SSA.
That is not sufficient. Correct support for tail-calls must be dynamic. For example if you have a tail-call to g in f, and in g you have a tail-call to f (mutual recursion with tail-calls). It has to be dynamic because g might be the defined with an eval, or other dynamic method.
The bottom line is that there must be a tail-call instruction (often called "jump") to transfer control to functions without stack growth.
Marc
I guess we'll see when the spec is released whether they mean static or dynamic tail calls. I'm guessing the latter would require a rather tricky analysis to work in JavaScript, and may not be what they will include in the spec.
Does scheme mandate that the compiler must be able to discover tail calls that occur at any point, say, after functions are redefined? For example, if you define some function f to call a function g that is not yet defined, and then later you dynamically define g, and the functions end up being mutually tail-recursive, does scheme mandate this must be optimized through tail recursion?
- Maxime
On 2011-01-30, at 1:18 PM, chevalma@iro.umontreal.ca wrote:
It should be possible to analyze the tail recursive functions and transform them so the recursion becomes a loop in the CFG. This way we can keep the IR the same-old SSA.
That is not sufficient. Correct support for tail-calls must be dynamic. For example if you have a tail-call to g in f, and in g you have a tail-call to f (mutual recursion with tail-calls). It has to be dynamic because g might be the defined with an eval, or other dynamic method.
The bottom line is that there must be a tail-call instruction (often called "jump") to transfer control to functions without stack growth.
Marc
Tachyon-list mailing list Tachyon-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/tachyon-list
On 2011-01-30, at 1:58 PM, chevalma@iro.umontreal.ca wrote:
I guess we'll see when the spec is released whether they mean static or dynamic tail calls. I'm guessing the latter would require a rather tricky analysis to work in JavaScript, and may not be what they will include in the spec.
Does scheme mandate that the compiler must be able to discover tail calls that occur at any point, say, after functions are redefined? For example, if you define some function f to call a function g that is not yet defined, and then later you dynamically define g, and the functions end up being mutually tail-recursive, does scheme mandate this must be optimized through tail recursion?
Of course! The semantics does not make special cases. If a function f calls g in tail position, then it is a tail-call. The time when a function was called has no effect on the semantics. Remember that Scheme, like JavaScript, are dynamic languages, in the sense that the semantics is described in terms of operations that happen at run time. Static analysis is viewed as an optimization (i.e. discovering some properties at compile time, such as types, that in the general case would require an execution of the program).
Think of this case:
var g;
function f(n) { print(n); if (n>0) g(n-1); }
if (sometimes) g = f;
Then sometimes f will be a tail-recursion. The fact that f is calling f isn't known statically. It is only at run time that we know f is calling itself.
What would be required to extend the IR "call" instruction to support tail-calls?
Marc
On 2011-01-30, at 2:20 PM, Marc Feeley wrote:
On 2011-01-30, at 1:58 PM, chevalma@iro.umontreal.ca wrote:
I guess we'll see when the spec is released whether they mean static or dynamic tail calls. I'm guessing the latter would require a rather tricky analysis to work in JavaScript, and may not be what they will include in the spec.
Does scheme mandate that the compiler must be able to discover tail calls that occur at any point, say, after functions are redefined? For example, if you define some function f to call a function g that is not yet defined, and then later you dynamically define g, and the functions end up being mutually tail-recursive, does scheme mandate this must be optimized through tail recursion?
Of course! The semantics does not make special cases. If a function f calls g in tail position, then it is a tail-call. The time when a function was called has no effect on the semantics.
I meant "when the function was defined...".
Marc
I'm guessing a different call instruction implementation (with support in the backend) that doesn't push a new stack frame.
- Maxime
On 2011-01-30, at 1:58 PM, chevalma@iro.umontreal.ca wrote:
I guess we'll see when the spec is released whether they mean static or dynamic tail calls. I'm guessing the latter would require a rather tricky analysis to work in JavaScript, and may not be what they will include in the spec.
Does scheme mandate that the compiler must be able to discover tail calls that occur at any point, say, after functions are redefined? For example, if you define some function f to call a function g that is not yet defined, and then later you dynamically define g, and the functions end up being mutually tail-recursive, does scheme mandate this must be optimized through tail recursion?
Of course! The semantics does not make special cases. If a function f calls g in tail position, then it is a tail-call. The time when a function was called has no effect on the semantics. Remember that Scheme, like JavaScript, are dynamic languages, in the sense that the semantics is described in terms of operations that happen at run time. Static analysis is viewed as an optimization (i.e. discovering some properties at compile time, such as types, that in the general case would require an execution of the program).
Think of this case:
var g;
function f(n) { print(n); if (n>0) g(n-1); }
if (sometimes) g = f;
Then sometimes f will be a tail-recursion. The fact that f is calling f isn't known statically. It is only at run time that we know f is calling itself.
What would be required to extend the IR "call" instruction to support tail-calls?
Marc
Tachyon-list mailing list Tachyon-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/tachyon-list
On 2011-01-30, at 4:54 PM, chevalma@iro.umontreal.ca wrote:
I'm guessing a different call instruction implementation (with support in the backend) that doesn't push a new stack frame.
That seems doable, given that the parameters are part of the instruction (the parameters are the initial content of the activation frame of the called function). However, the return address parameter will have to be an explicit operand, pretty much like the "cont" annotation on calls.
Marc
-
chevalma＠iro.umontreal.ca -
Marc Feeley