Transfering control without growing control context -- i.e. how toimplement GOTO

[ron.h.hall]

(e-mail address removed) wrote:




<snip>
Perhaps not fully understanding what you're trying to achieve, my
approach would be to use a closure.
<snip>

I did consider a variation using closures, but I could not see any great
advantage in encapsulating the variables, and did see some potential
advantages in having them externally accessible in the context of the
original question.

One of the nicer thing about the closure is the retention of
meaningful variable names. However, as you mentioned earlier, where
the code is machine generated, that isn't going to necessarily be a
determining issue.

 

[ron.h.hall]

(e-mail address removed) wrote:

On Jul 4, 5:22 am, Jens Axel Søgaard wrote:


And you reached this conclusion based on what?

I have never looked at the internals of a Javascript implementation,
but it appears to me that Javascript is designed to be implemented in
a prototypal inheritance environment. That would suggest to me, that
in all likelihood, closures are implemented as (internal) objects, and
therefore would be no more expensive to create than an ordinary
Javascript object.
<snip>

I would be inclined to agree, but maybe not for the same reasons. The
objects involved in a closure are the function object, the structure
referred to by its [[Scope]] property and the Variable object for the
execution context in which it was created. The creation of the scope
structure and the Variable object are implied in all function calls so
the effect of forming a closure may be no more than that these objects
that would be created anyway are just not garbage collected following
their use. So all the costs of closures would be in the ongoing memory
consumption needed to accommodate the required objects/structures.

Interesting take.

I did some quick trivial tests with the closure I gave previously to
see what the (timing) costs were like. As usual, the results vary
greatly depending on the browser used.

It appears that closures are relatively inexpensive to create in FF
and IE (maybe 2 to 3 times the cost of creating an object), but Opera
was more than an order of magnitude greater. [1]

More testing would be required to get an accurate/reliable
determination.

[1] Not that I want to dis Opera. Quite often I find Opera to be much
faster than other browsers.

 

[Richard Cornford]

Richard Cornford wrote:

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();

<snip>

This first call to the function is wrong in this context as it is not a
tail-recursion type call.

baz.a0 = 3;
baz();

should be:-

baz.specialCall(3);

- for consistency.

Richard.

 

[Jens Axel Søgaard]

Well, actually s is intended to be of type number, so no.

Sorry. I meant to write:

This is nice way to restrict the scope of n and s to
the body of sum (and the helper res which belongs to sum).

Which actually makes sense.

As it wasn't intended to be solution for control context constraint
alternative for all recursive functions, and in that it relates
directly to your opening remarks in this thread, that doesn't seem
like a problem under consideration.
Okay.

And you reached this conclusion based on what?

Mostly pessimism ;-) Or optimism?

Various implementations represent closures in differently,
so in the first place the claim only makes sense as a rule
of thumb.

Conceptually the contents of a closure consists of the body
expression and the values of the free variables at the
time the closure was created.

The body expression is usually represented as a pointer
to the result of compiling the body. How the values of the
free variables are represented differ among implementations.
Some compiler actually have several different ways of
representing closures, and choose beween them based on
a static analysis of the program.

A common strategy of implementing closures is to use
flat closures. When the closure is created the values
of all free variables are stored in the closure.
The advantage of this is that references to free variables
in the body are fast - no need to search the chain of
activation frames. The disadvantage is of course that closure
creation is slowish.

Not knowing when and how a given JavaScript implementation
determines the set of free variables, I figured it were
better to use objects, since I can calculate the free
variables my self on compile time.

So in short, it is possible that closures might be as
effective as objects, but given the range of implementation
choices it is hard to rely on.

I have never looked at the internals of a Javascript implementation,
but it appears to me that Javascript is designed to be implemented in
a prototypal inheritance environment. That would suggest to me, that
in all likelihood, closures are implemented as (internal) objects, and
therefore would be no more expensive to create than an ordinary
Javascript object.

I am not sure I had grasped exactly how the generalization would work.

As well, the generation of the closures would be done in an initiation
phase. The "giant switch" alternative you propose is bound to be
inefficient firstly because of its inherent design in Javascript, and
the fact that it would be invoked throughout the execution phase, not
just during initiation.

If only the number of cases in the switch were small ...

 

[Jens Axel Søgaard]

Allocating new local variables at entry, restores the

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.

In this example it is relatively easy to determine where backing up
is necessary. But suppose baz calls qux, which in turn calls baz.
In this case backing up is necessary too. Since functions are
first class, one can't determine the call sites of a function simply
by scanning the source for calls the function.

In some cases the analysis is possible, but I better postpone
these kind of optimizations until the compiler proper works.

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.

That would work too.

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.

Even for function tail calls without arguments normal JavaScript
implementations allocates stack frames. So the trampoline trick
must to used to handle the tail call. Oh! If we are tail calling
another function then caller can't do the backing up, since
we won't come back after the call.

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.

Both the switch and the trampoline avoid stack overflow. But if
there were an efficient "switch-like" construct (such as labels and
goto), then that would be faster than the trampoline construct.

I have (there is) a systematic (axiomatic) revulsion at the idea of
using global variable in javascript (or at all).
Ditto.

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.
Agree.


If there is time exploration is often a good idea.


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.

I need to think a little more, otherwise the questions most likely
won't make sense.

It is quite refreshing to be having something a little less
run-of-the-mill to talk about on the group.

Thanks.

 

[ron.h.hall]

Mostly pessimism ;-) Or optimism?

Ah, though perhaps always better employed in the presence of
supporting pessimetrics/optimetrics ;-)

Various implementations represent closures in differently,
so in the first place the claim only makes sense as a rule
of thumb.

Agreed. The variations in the implementations are exposed in many
areas when measures of efficiency are taken, and closures are expected
to be no different in that respect. The only requirement is that the
implementation meet the standard.

Conceptually the contents of a closure consists of the body
expression and the values of the free variables at the
time the closure was created.

The body expression is usually represented as a pointer
to the result of compiling the body. How the values of the
free variables are represented differ among implementations.
Some compiler actually have several different ways of
representing closures, and choose beween them based on
a static analysis of the program.

Again agreed, although for an interpreted language, the compiler would
not generally expect to be afforded a generous amount of time for
optimizations.

A common strategy of implementing closures is to use
flat closures. When the closure is created the values
of all free variables are stored in the closure.
The advantage of this is that references to free variables
in the body are fast - no need to search the chain of
activation frames. The disadvantage is of course that closure
creation is slowish.

Not knowing when and how a given JavaScript implementation
determines the set of free variables, I figured it were
better to use objects, since I can calculate the free
variables my self on compile time.

But, if I understand correctly, you would be doing that creation under
Javascript interpretation, versus the closure being created through
execution of fast non-interpreted (or at least faster interpreted code
if the interpreter was implement in Java) code?

So in short, it is possible that closures might be as
effective as objects, but given the range of implementation
choices it is hard to rely on.

The unreliability of execution efficiencies, because of the varying
underlying implementations, aren't restricted however to closures. So
for any application, execution time can vary significantly (as per
parser measures I gave earlier).

In the case of closures, though, my quick tests seem to indicate that
closure creation under Opera is very expensive. So if that's
considered an important environment, it may mitigate against heavy use
of closures in your application. The other issue is that Javascript
versions may change in efficiency as the development progresses.

I am not sure I had grasped exactly how the generalization would work.

My view, in brief, was that the program tree structure (or sub-
structure for closures) could be represented by objects, with local
variable properties, and outer function variable property inheritance.
So variable value fetch would just be the normal chained lookup
(possibly with caching for long lookups?).

Value assignment, however, would have to be different from the
standard Javascript action, since the assignment would need to be done
at the correct level/location, rather than to the immediate local
object.

Not that I've really thought anything through, or tried to. Compiler
writing isn't really my area.