^
For anyone how noticed; that Identifier should have been - sum -, not -
sum3 -. I wrote a number of variations and this was the third, and I
omitted changing this Identifier when posting this to parallel the
original - sum - function.
I like the structure of the solution, but it needs a small
modification to avoid a problem with non-tail-calls. The problem
is that the local variables are reused.
Yes, I noticed that there would be an issue with this strategy whenever
a function that used it made a call to another function (which might
indirect re-call it) or itself, directly.
Consider this example:
function foo(n) {
if (n<=1) {
document.write("* " +n + "</br>");
return 1;
}else{
document.write( n+" "+foo(n-1)+"<br/>");
return( foo(n-1) );
}
};
foo(3);
There are two recursive calls to foo.
The call in the expression 1+foo(n-1) is not tail recursive.
The call in return( foo(n-1) ) is tail-recursive.
The output of the above is:
* 1
2 1
* 1
3 1
* 1
2 1
* 1
Introducing local variables as properties of the functions
give:
function bar() {
if (bar.n<=1) {
document.write("* " + bar.n + "</br>");
return 1;
}else{
bar.n = bar.n-1;
document.write( "n" +" "+bar()+"<br/>");
bar.n = bar.n-1;
return( bar() );
}
};
bar.n = 3;
bar();
The output is:
* 1
n 1
* 0
n 1
* -1
Allocating new local variables at entry, restores the
behavior of foo:
function baz() {
var n = baz.n;
if (n<=1) {
document.write("* " + n + "</br>");
return 1;
}else{
baz.n = n-1;
document.write( n +" "+baz()+"<br/>");
baz.n = n-1;
return( baz() );
}
};
baz.n = 3;
baz();
This is true, but have you noticed that backing up the properties of the
function to local variables is only relevant in the - else - branch
where - baz - is actually called. Certainly you could have a formal
strategy of passing arguments as properties of the function and then
systematically transferring them to local variables, but you could also
have a strategy where the properties of the function where only
backed-up to local variables if control was to pass out of the function
(prior to calling other functions) and then restoring them once that
function had returned.
function baz() {
var n;
if (baz.n <= 1) {
document.write("* " + baz.n + "</br>");
return 1;
}else{
n = (--baz.n);
document.write( n +" "+baz()+"<br/>");
baz.n = n;
return( baz() );
}
};
(the output is different, but only because the value of - n - is
different in my example due to - baz.n - being decremented once instead
of being assigned the value of (n-1) twice.)
Then there would be the possibility of doing it the other way around; a
function (and so, by implication, all functions) never backs-up its own
properties (except by coincidence) but instead whenever it is going to
call another function it backs up the properties of that function. This
could be formalised into two methods of functions that took, say, an
'empty' object (or array) as an argument, with one method transferring
its 'argument properties onto the object and the other restoring them
form it. So the form would go:-
1. Declare a local variable to refer to the object : var obj;
2. If a function is to be called create and assign the
object : obj = {};
3. Call a method passing in the object : func.backupState(obj);
4. Assign the 'arguments for the call to the properties of the
function to be called.
4. Call the function:
5. Restore the properties from the object : func.resoreState(obj);
- with a general case for each method defined on the -
Function.prototype - and overridden on specific functions where
necessary.
Having written that it occurs to me that the whole lot could be wrapped
up in one prototype method of functions. If the public properties of a
function were always a0, a1, a2 ... an, and the function had a property
called, say, argumentsLength, you could have a prototype method that
took the arguments for the call as real arguments (though not declared
formal parameters):-
Function.prototype.specialCall = function(){
var ret, prop, c, len, ar = [];
/* I suppose this could also be - (len = arguments.length) -
and have the number of arguemnts to the method call
determine the number of function parameters backed-up:-
*/
if((len = this.argumentsLength)){
for(c = 0;c < len;++c){
ar[c] = this[(prop = ('a'+c))];
this[prop] = arguments[c];
}
}
ret = this(); //call the function itself.
if(len){
for(c = 0;c < len;++c){
this[('a'+c)] = ar[c];
}
}
return ret;
};
- and so given a function - func - you would call it as -
func.specialCall(arg1, arg2, etc) - for non-tail recursion and as -
func() - for tail recursion. So - baz - above becomes:-
function baz() {
if (baz.a0 <= 1) {
document.write("* " + baz.a0 + "</br>");
return 1;
}else{
--baz.a0;
document.write( baz.a0 +" "+baz.specialCall((baz.a0))+"<br/>");
return( baz() );
}
};
baz.argumentsLength = 1; //state the number of arguments/parameters.
baz.a0 = 3;
baz();
Now - baz - has no local variable to do the backing-up but instead all
of that goes on inside the function's method and is fully automated.
Adding the trampoline is now easy:
function trampoline(pc) {
while (typeof (pc) == 'function')
pc = pc();
return pc;
};
function qux() {
var n = qux.n;
if (n<=1) {
document.write("* " + n + "</br>");
return 1;
}else{
qux.n = n-1;
document.write( n +" " + trampoline(qux) + "<br/>");
qux.n = n-1;
return( qux );
}
};
qux.n = 3;
trampoline(qux);
The method seems viable. The idea of the giant switch was to
avoid expensive functions calls,
I though it was to avoid stack overflows, which I can entirely
understand given how poorly javascript is specified in the area of stack
overflows, and how unhelpfully they are handled in reality. But given
that javascript is a functional programming language I can see no reason
for avoiding function calls as such.
and thus the local variables had to be
held by a global variable.
I have (there is) a systematic (axiomatic) revulsion at the idea of
using global variable in javascript (or at all). But that is largely a
reaction to the way their over use results in incomprehensible,
un-maintainable code, which is an issue for human authors and probably
not quite the same issue in machine generated code.
However, if I am forced to use the
trampoline it is worth while to explore alternative solutions.
If there is time exploration is often a good idea.
The next thing to consider is continuation capturing. In the
all-local-variables-are-stored-in-a-global-variable scenario this
is easy to do (since it is easy to determine live local variables).
In the local-variables-are-properties-of-the-function
a general continuation capturing mechanism such as call/cc is harder
to implement. In a straight call to call/cc one can solve the
problem via lexical analysis, but if call/cc is passed around as
a function value, and applied later, then things becomes tricky.
Perhaps another situation where coming up with something a bit more
concrete as a starting point may elicit suggestions about how it may be
handled.
Then again, if the local variables are named l1, ..., ln and
we have a separate property, say, locals_count holding the
number of current local variables, then ... Hmm. This might be
easier than I thought after all.
Actually a hybrid solution might turn out to be the best:
Representing function arguments as above, and keeping the free
variables in a global JavaScript variable.
You have given me food for thought,
It is quite refreshing to be having something a little less
run-of-the-mill to talk about on the group.
Richard.
