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

Richard Cornford wrote:
Jens Axel Søgaard wrote:
Richard Cornford wrote:
<snip>
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".

So that would be the stack of "execution contexts" in javascript/ECMAScript terms.

Yes.

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.

I think you are going to be stuck with either this or the switch-case, and there seems to be much more mileage in your trampoline.

Okay.

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

So your problem is that you are compiling a language that will (or should) never cause a stack overflow into one that's only response to the issue is to stop if recursion goes on for too long (and not all ECMAScript environments do that (Opera, as I recall, will go on recursing until it OS runes out of memory).

Exactly.

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.

I think the trampoline is going to be your best option. So the next question should probably be how to implement it in a way that is suited to the task. for which a much more concrete example may be necessary. For example, I am unclear as to how your are going to be handling the variables in original language (their scoping and so on), and arguments to your function calls in javascript.

I am using flat closures (so assigned to variables are converted to
boxes) represented as JavaScript objects. A reference to local variable
number 2 will be eventually become locals[2] in JavaScript, where locals
is a global JavaScript variable. This is a simple strategy, which
can be improved upon later if neccessary.

I can thus use the switch or the trampoline solution as-is.

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,

OK, that is arguably array-specific.

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]()) {}

Actually that is unnecessary, stupid, and will not work. Distracted by the talk of labels I failed to notice that your functions do not return strings but instead return function references, so your original is fine and sticking 'window' in front will break it.

I was also thrown off a bit by the - pc = label0 (); - line. It could have been - pc = label0; -

Oops. You are right.

(assigning a reference to the function instead of a result to the first call to the function). Here the outcome would have been the same, but doing it that way would have allowed the fist function called to return false and so stop the process after only one call.

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 don't see how that happened. But the - window - reference to the ECMAScript global object is general to all web browsers (and some other environments such as W3C standard SVG), it just is not available in all environments, such as windows scripting host, JScript ASP and probably stand-alone javascript interpreters.

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.

No, global variables _are_ properties of the global object,

That I knew.

and - window - is a reference to the global object so the global variable is not shadowed, it is assigned a new value.

But I hadn't understood this. In the global scope this == this.window.

Can I expect one type of variable reference to be faster than
another in the current browser implementation of JavaScript?

For an unqualified Identifier the length of scope chain is a factor in the speed of resolving it to a value or writing a value to it, for a property accessor the location of the property on the prototype chain of the object in question is a factor when reading the value (but not when writing as writing will always assign to the object at the top of the prototype chain).

Thanks. The standard explains the semantics in the same way, but
I wasn't sure browsers actually implemented variable resolution the
same way. For many programs it ought be possible to do variable resolution prior to the execution.

--
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: Three Dog Problems
    ... If you can control the meaning of words, ... This is too narrow a view for the role of language. ... Orwell was just.... ... His idea of history and its control, culture and its control, ...
    (sci.cognitive)
  • Re: Transfering control without growing control context -- i.e. how to implement GOTO
    ... 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. ... language doesn't support Proper Tail Recursion. ...
    (comp.lang.javascript)
  • Re: Suggestion for review: a taxonomy of thread safety
    ... > I have successfully implemented event-based robotic control ... > systems using multiple threads of control. ... > program had no such problems was because I used a language ... It will write to a shared memory area. ...
    (comp.programming)
  • Re: definition of a highlevel language?
    ... to the language of the problem domain. ... while control: ... And if you would propose this solution to a control system engineer, ... So an adequate high level language, ...
    (comp.lang.python)
Loading