javascript nested loops waiting for user input

Question

I built a C interpreter in C# a while ago and have now begun converting it to Javascript. Everything was going fine until I realized js has no sleep function. My interpreter uses a recursive parser and it pauses for user input while it is nested several functions deep (in C# I used waithandle in a second thread). I have looked at setInterval and setTimeout but they are asynchronous /non-blocking; of course a busywait is out of the question and I looked at a timed_queue implementation I found on SO but no luck. I have tried the parser both in the main window and in a webworker. I am using jQuery. I have limited experience with js and am looking for ideas to pursue. I know little about continuation passing style, or yield and am wondering if they might hold the key. Here is a bit cut from the code to show some of the controlscript. Any ideas please...

var STATE = {
    START: "START",
    RUN: "RUN", //take continuous steps at waitTime delay
    STEP: "STEP", //take 1 step
    PAUSE: "PAUSE",//wait for next step command
    STOP: "STOP",
    ERROR: "ERROR"
}
var state = state.STOP;

function parsing_process() //long process we may want to pause or wait in 
{
    while(token !== end_of_file)//
    {
        //do lots of stuff - much of it recursive
        //the call to getNextToken will be encountered a lot in the recursion
        getNextToken();
        if (state === STATE.STOP)
            break;
    }
}

function getNextToken()
{
    //retrieve next token from lexer array
    if (token === end_of_line)
    {
        //tell the gui to highlight the current line
        if (state === STATE.STOP) 
            return;
        if (state === STATE.STEP)//wait for next step
        {
            //mimick wait for user input by using annoying alert
            alert("click me to continue")
        }

        if (state === STATE.RUN) {
            //a delay here - set by a slider in the window
            //a busy wait haults processing of the window
        }
    }
}

I have gotten this to work in Firefox using task.js

<html>
<head>
    <title>task.js examples: sleep</title>
    <script type="application/javascript" src="task.js"></script>
</head>
<body>
    Only works in FIREFOX
    <button onclick="step()">Step</button>
    <button onclick="run()">Run</button>
    <button onclick="stop()">Stop</button>
    <pre style="border: solid 1px black; width: 300px; height: 200px;" id="out">
</pre>

    <script type="application/javascript;version=1.8">

        function start() {
            process();
        }

        function step() {
            if (state === STATE.STOP)
                start();
            state = STATE.STEP;
        }
        function run() {
            if (state === STATE.STOP)
                start();
            state = STATE.RUN;
        }
        function stop() {
            state = STATE.STOP;
        }

        var STATE = {
            START: "START",
            RUN: "RUN", //take continuous steps at sleepTime delay
            STEP: "STEP", //take 1 step
            PAUSE: "PAUSE",//wait for next step command
            STOP: "STOP",
            ERROR: "ERROR"
        }

        var state = STATE.STOP;
        var sleepTime = 500;

        function process() {
            var { spawn, choose, sleep } = task;
            var out = document.getElementById("out");
            var i=0;
            out.innerHTML = "i="+i;
            var sp = spawn(function() {
                while(state !== STATE.STOP)
                {
                    i++;
                    out.innerHTML = "i="+i;
                    if (state === STATE.RUN)
                    {
                        yield sleep(sleepTime);
                    }
                    if (state === STATE.STEP)
                        state = STATE.PAUSE;
                    while (state===STATE.PAUSE)
                    {
                        yield;
                    }
                }
            });
        }
    </script>
</body>
</html>

I would appreciate it if someone who knew something about promises could give me some more clues. My application is not a consumer one but it would be nice if it ran in more than Firefox

What *environment* are you running in? The absense of a `sleep` function is primarily an *environmental* thing, not a language thing. — T.J. Crowder, Jun 07 '15 at 21:12
Can you explain how this might be used, i.e., what is the purpose? — Yogi, Jun 07 '15 at 21:39
I am wanting to run this in a browser, any chance you could help me a littl emore with how promises might be used, thanks — user2153050, Jun 08 '15 at 21:59

score 2 · Answer 1 · answered Jun 08 '15 at 03:19

If you're running your script in a browser and need to wait for user's input (click event, field-change event, etc) - then you can't use "while" and "pause" it to wait for browser's event. Event handler will be invoked asynchronously, and by that time "while" loop may even finish reading a list of tokens. Probably you should try read token by token and basing on its value - call the next action.

Try this example: http://jsbin.com/puniquduqa/1/edit?js,console,output

score 1 · Answer 2 · answered Jun 11 '15 at 05:48

1

The work done here https://github.com/felixhao28/JSCPP is very useful, he uses generators and it runs in both Chrome and Firefox.

answered Jun 11 '15 at 05:48

user2153050

103
1
7

score 1 · Accepted Answer · answered Jul 31 '15 at 07:19

As the author of JSCPP, I faced the exactly same issue when I was implementing a debugger which pauses and continues the program interpreting on the fly. In the end I decide to use generator functions from es6 but I would like to share my thought process here.

The common way is to first compile target code into a low-level recursive-free byte-code. You label each statement and then handle all the control flow with unconditional jump and conditional jump. Then you run a byte-code interpreter on top of that. This is a good option if you don't mind all these compiling work to be done.

The other way is a "call stack save/call stack load" work flow. When you need to pause interpreting, you recursively push all arguments and all local variables to a customized stack all the way back to bottom. When you need to continue execution, you recursively load all these arguments and local variables. Your code will be transformed from

AddExpression.prototype.visit = function(param) {
  var leftVal = visit(this.left, param);
  var rightVal = visit(this.right, param);
  return leftVal + rightVal;
}

to

AddExpression.prototype.visit = function(param) {
    if (needToStop) {
        stack.push({
            method: AddExpression.prototype.visit,
            _this: this,
            params: [param],
            locals: {},
            step: 0
        });
        return;
    }
    if (recoverFromStop && stack.top().step === 0) {
        var thisCall = stack.pop();
        if (stack.length > 0) {
            var nextCall = stack.top();
            nextCall.method.apply(nextCall._this, params);
        }
    }
    var leftvalue = visit(this.left, param);
    if (needToStop) {
        stack.push({
            method: AddExpression.prototype.visit,
            _this: this,
            params: [],
            locals: {
                leftvalue: leftvalue
            },
            step: 1
        });
        return;
    }
    if (recoverFromStop && stack.top().step === 1) {
        var thisCall = stack.pop();
        leftvalue = thisCall.locals.leftvalue;
        if (stack.length > 0) {
            var nextCall = stack.top();
            nextCall.method.apply(nextCall._this, params);
        }
    }
    var rightvalue = visit(this.right, param);
    if (needToStop) {
        stack.push({
            method: AddExpression.prototype.visit,
            _this: this,
            params: [],
            locals: {
                leftvalue: leftvalue,
                rightvalue: rightvalue
            },
            step: 2
        });
        return;
    }
    if (recoverFromStop && stack.top().step === 2) {
        var thisCall = stack.pop();
        leftvalue = thisCall.locals.leftvalue;
        rightvalue = thisCall.locals.rightvalue;
        if (stack.length > 0) {
            var nextCall = stack.top();
            nextCall.method.apply(nextCall._this, params);
        }
    }
    return leftvalue + rightvalue;
};

This method does not alter the main logic of your interpreter but you can see for yourself how crazy the code is for a simple A+B syntax.

Finally I decide to use generators. Generators are not meant for interactively altering program execution, but rather for lazy-evaluation purpose. But with some simple hacking, we can use lazy-evaluate our statements upon receiving "continue" command.

function interpret(mainNode, param) {
    var step;
    var gen = visit(mainNode);
    do {
        step = gen.next();
    } while(!step.done);
    return step.value;
}

function visit*(node, param) {
    return (yield* node.visit(param));
}

AddExpression.prototype.visit = function*(param) {
    var leftvalue = yield* visit(this.left, param);
    var rightvalue = yield* visit(this.right, param);
    return leftvalue + rightvalue;
}

Here, function* indicates we want the AddExpression.visit function to be generator function. yield* followed by visit call means visit function itself is a recursive generator function.

This solution seems perfect at first glance but it is suffering from a huge performance decrease by using generators (http://jsperf.com/generator-performance) and that it is from es6 and not many browsers support it.

To conclude, you have three different ways of achieving interruptible execution:

compile to low-level code:
- Pros: common practice, separate of concerns, easy to optimize and maintain
- Cons: too much work
save stack/load stack:
- Pros: relatively fast, retains interpreting logic
- Cons: hard to maintain
generator:
- Pros: easy to maintain, perfectly retains interpreting logic
- Cons: slow, needs es6 to es5 transpiling

javascript nested loops waiting for user input

3 Answers3