Re: Transfering control without growing control context -- i.e. how to implement GOTO

Richard Cornford wrote:

Here you have a terminology problem. You are trying to express your problem with the terminology that is familiar to you, but your desired audience are people who know about javascript and so are likely familiar with its terminology, but not necessarily both.

You are right, thanks for bringing it to my attention. I'll
try my best to explain a little further.

You may have to be more explicit about whatever it is you are trying to achieve. I, for one, attach no absolute an certain meaning to the term "control context" and so have no idea what constructs in javascript it may relate to, and so why 'growing' them may be a problem.

In languages (such as JavaScript) where continuations aren't first
class, the control context is normally referred to as the "control
stack". (In some languages the control context is a not a stack,
but a tree - hence the use of the more general term). Calling a function
in JavaScript will always push an activation record onto the control
stack. This "grows the control context".

If you look at how the behaviour of the control stack in the example:

function label0 () { document.write(0); return label2;}
function label1 () { document.write(1); return label2;}
function label2 () { document.write(2); return false;}

pc = label0 ();
while (pc=pc()) {}

It will "jump up and down" - hence the nickname "trampoline".

Trampolines are a well-known way of compiler technique of
implementing Proper Tail Recursion [1], used when the target
language doesn't support Proper Tail Recursion.


As for why the growth of the control context is a problem,
when translating a source language supporting proper tail
recursion into a language without, consider the following
example. In the example the recursive call to sum is a tail
call (if a the result of a function call, is to be returned
by the calling function, then the function call is a tail call):

function sum (n, s) {
if (n==0)
return s;
else
return sum(n-1, s+n);
}
document.write(sum(1000,0));

In Scheme and ML which support tail recursion, the
a compiler essentially compiles sum(n-1,s+n) to
a jump instruction - which doesn't grow the control
context. Therefore the above works.

In JavaScript the control stack will grow, and eventually
you get the error "too much recursion" (wording taking from FireFox).


Supporting Proper Tail Recursion means that an arbitrary number
of tail calls can be active (a call is active, as long as the
callee hasn't returned) using nothing but a bounded amount of space.


A normal strategy to transfer control from one point to another
without growing control context is to use goto. However since
goto is not part of JavaScript, I need to find a construct that
works in a similar way. The switch-example is one solution and
the trampoline is another.

If the control points are named, it is possible to omit the array
references:

They are not "array references" they are "property accessors". Javascript has no array-specific syntax.

The [1,2,3] notation are called array literals in the standard,
but I realize that it is nothing but syntactic sugar for
objects. Coming from Scheme it is hard for me to get used to say
"property accessor", when conceptually I am referencing
elements in an array.

function label0 () { document.write(0); return label2;}
function label1 () { document.write(1); return label2;}
function label2 () { document.write(2); return false;}

pc = label0 ();
while (pc=pc()) {}

Globally declared named functions become properties of the javascript global object so they can be referenced, but still with property accessors, as members of that object. In a web browser where the global object is available as a - window - property of the global object the code would be:-

pc = label0 ();
while (pc=window[pc]()) {}

Thanks for mentioning this. I tried the trampoline example in FireFox
and it works there, but am I correctly reading between the lines, that
I can't expect it to work in other browsers?


I tried this example in FireFox:

function foo() {document.write(1); }
this.window.foo = function () {document.write(2);}
foo();

The example prints 2. If the line this.window.foo=... is
deleted, then the example prints 1. Variables in window
thus shadows global variables.

Can I expect one type of variable reference to be faster than
another in the current browser implementation of JavaScript?
Or is that non-measurable?

--
Jens Axel Søgaard
.

Relevant Pages

  • Re: Transfering control without growing control context -- i.e. how to implement GOTO
    ... the control context is normally referred to as the "control ... language doesn't support Proper Tail Recursion. ... In JavaScript the control stack will grow, ... Globally declared named functions become properties of the javascript global object so they can be referenced, but still with property accessors, as members of that object. ...
    (comp.lang.javascript)
  • Re: VB.Net Horisontal Menu
    ... There is no "menu" control of a Webpage. ... javascript, VBNet and servercontrols. ... This is nothing strange because a button is in fact often used in webpages ... > even my web development is for operational purposes. ...
    (microsoft.public.dotnet.general)
  • Re: altering .UniqueID
    ... javascript call itself where the validation fires off nor is it really ... validators have been fixed to work with Firefox in .NET 2.0". ... Admittedly the control sits inside an ascx (which has a ...
    (microsoft.public.dotnet.framework.aspnet)
  • Re: asp:DropDownList and Javascript
    ... disable JavaScript in my browser, ... than firing immediately after a new selection is made. ... Is there any way to determine which control initiated the PostBack? ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Cross domain iframe access
    ... I have no intention to satisfy your curiosity, nor do I put any value on any ... What can be observed, however, is that all UAs but IE reset the value of the ... control when the type is changed to "file", ... Prototype.js was written by people who don't know javascript for people ...
    (comp.lang.javascript)
Loading