User interacting interpreter in a non-blocking single-threaded environment (tricky)

For a school project me and a classmate are writing a domain-specific language in javascript (node). The language contains statements that require user input via a Websocket connection.

When a statement requires user input, the interpreter must stop executing, and wait for an event.

Normally one would pause the thread and wait for the user input to be received before continuing thread, but we cant do that since node.js is single-threaded, and of开发者_运维问答fers no option of sleep without blocking the processor.

We tried a lot of ways to get around it, but failed. :-(

The answer to this question could be a suggestion to how to make a pausable interpreter.

Below, we run through a simplification of the interpreter (with errors)

We construct an abstract syntax tree with these nodes

var Print = function( str ){
  this.str = str;
}
var Block = function( stats ){
  this.stats = stats;
}
var Delayed = function( stats ){
  this.stats = stats;
}
var Loop = function( times, stats ){
  this.times = times;
  this.stats = stats;
}

• Print - a simple statement, that never needs to be paused.
• Block - a sequence of statements
• Delayed - a sequence of statements to be executed after some time.
• Loop - multiple iterations of a sequence of statements

The tree looks like this:

var ast = new Block([
  new Delayed([
    new Print("blah blah"),
    new Delayed([])
  ]),
  new Loop(3,[
    new Delayed([
      new Print("loop delayed")
    ])
  ])
]);

The interpreter used to evaluate the statements. Note, that this code does not work as it should. It never pauses to wait for input.

var Interpreter = function( ast ){
  this.ast = ast;
}

Interpreter.prototype.run = function(){
  this.handle( this.ast );
}

Interpreter.prototype.handleAll = function( stats ){
  for( var i = 0; i < stats.length; i++ ){
    this.handle(stats[i]);
  }
}

Interpreter.prototype.handle = function( stat ){
  var t = this;
  /*-----------------------------------------------*
   *   Simple statement - no need for pause here   *
   *-----------------------------------------------*/
  if( stat instanceof Print ){
    sys.puts(stat.str);
  }

  /*-----------------------------------------------------*
   *   Delayed - this might contain more delayed stats   *
   *-----------------------------------------------------*/
  else if( stat instanceof Delayed ){
    sys.debug("waiting for user input");
    // this represents a user input with a string
    setTimeout(function(str){

      sys.debug("done waiting");
      sys.puts(str);

      // this might contain delayed stats 
      t.handleAll(stat.stats);

    }, 2000, "some string");
  }

  // ============================================
  // = Block - this might contain delayed stats =
  // ============================================
  else if( stat instanceof Block ){
    sys.debug("doing a block - before");

    this.handleAll(stat.stats);

    sys.debug("doing a block - after");
  }


  // ===========================================
  // = Loop - this might contain delayed stats =
  // ===========================================
  else if( stat instanceof Loop ){
    sys.debug("before loop");
    for( var i = 0; i < stat.times; i++ ){
      sys.debug("inside loop[" + i + "] - begin");

      // this will maybe contain delayed stats
      this.handleAll(stat.stats); 

      sys.debug("inside loop[" + i + "] - end");
    }
    sys.debug("after loop");
  }

  else {
    throw "error.. statement not recognized"
  }
}

The interpreter needs to pause when a "Delayed" statement is encountered, and then continued when the Delay is done.

The code above never pauses. When a "Delayed" statement is encountered, the substatements are delayed, but the other statements after the "Delayed" is executed.

For a non fragmented version of the code, se http://pastie.org/1317023

I think Ivo's answer is basically right, but I'll try to rephrase it and add a few suggestions:

1. Delayed() should be a leave action, not an inner node of the AST - assuming I got the intended semantics right: it should block until data is received, and then complete/terminate.

2. You somehow need to emulate the notion of a program counter, and of a stack frame. For truly constructed actions (such as loop), the stack frame needs to contain the current value of the loop variable, and the current position within the sequence of statements. You should not recycle your AST objects for that state, as the same loop may be simultaneously in execution several times (assuming several clients).

3. The state has a "next" operation, performing one step of execution. Delayed, when first called, returns immediately with a code indicating that further execution is not desired. When called the second time, it does nothing (indicating that the action is complete).

You're loop is simply wrong. Instead of using a loop here:

for( var i = 0; i < stat.times; i++ ){

}

You need to rework your complete handle function:

// you might want to make it so that you can pass null to indicate blocking etc.
Interpreter.prototype.handle = function( stat ){ 
    var that = this;
    var wait = 0;

    // in case of delayed, just set wait to the desired delay

    // in case of a loop, well you either go recursive or use a stack based approach

    // fake the loop
    setTimeout(function(){that.handle();}, wait); 
}

So you need to "fake" your looping via a callback, seems tricky, but it really isn't this has all the advantages of the loop (well you need the stack/recursion i mentioned) above, but it also give you all the other stuff you want.

As for the WebSocket input, that is async too, in the data event you simply check via whether you're currently block and if so, you feed in the data as user input.

Remember there's only one thing running at a time, so if you loop through your progam, nothing else ever gets the chance to run, even your WebSocket events will just get queued and then trigger all after your loop has ended.