2010-11-22 36 views
0

Pour un projet d'école, moi et un camarade de classe écrivent un langage spécifique au domaine en javascript (node). La langue contient des instructions qui nécessitent une entrée de l'utilisateur via une connexion Websocket.Interprétation inter-utilisateur dans un environnement monothread non-bloquant (difficile)

Lorsqu'une instruction nécessite une entrée utilisateur, l'interpréteur doit arrêter l'exécution et attendre un événement.

Normalement on mettrait le thread en pause et attendrait que l'entrée d'utilisateur soit reçue avant de continuer le thread, mais nous ne pouvons pas faire cela puisque node.js est single-threaded, et n'offre aucune option de sommeil sans bloquer le processeur.

Nous avons essayé de nombreuses façons de contourner ce problème, mais nous avons échoué. :-(

La réponse à cette question pourrait être une suggestion à la façon de faire un interprète pausable.

Ci-dessous, nous courons à travers une simplification de l'interprète (avec des erreurs)

Nous construisons un résumé arbre de syntaxe avec ces nœuds

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; 
} 
  • Imprimer -. une simple déclaration, qui ne doit jamais être mis en pause
  • Bloc - une séquence d'instructions
  • Retardé - une séquence d'instructions à exécuter après un certain temps.
  • Loop - de multiples itérations d'une séquence d'instructions

L'arbre ressemble à ceci:

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

L'interprète utilisé pour évaluer les déclarations. Notez que ce code ne fonctionne pas correctement. Il ne fait jamais une pause pour attendre l'entrée.

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" 
    } 
} 

L'interprète doit faire une pause lorsqu'une instruction « retardée » est rencontré, puis a continué lorsque le retard est fait.

Le code ci-dessus ne fait jamais de pause. Lorsqu'une instruction "Delayed" est rencontrée, les sous-états sont retardés, mais les autres instructions après "Delayed" sont exécutées.

Pour une version non fragmentée du code, Sé http://pastie.org/1317023

Répondre

0

vous êtes boucle est tout simplement faux. Au lieu d'utiliser une boucle ici:

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

} 

Vous devez retravailler votre fonction poignée complète:

// 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); 
} 

Vous avez donc besoin de « faux » votre boucle via un rappel, semble difficile, mais il isn vraiment Ceci n'a pas tous les avantages de la boucle (bien, vous avez besoin de la pile/récursion que j'ai mentionné) ci-dessus, mais il vous donne également tous les autres trucs que vous voulez. En ce qui concerne l'entrée WebSocket, également asynchrone, dans l'événement de données, vous vérifiez simplement si vous êtes actuellement en mode blocage et si c'est le cas, vous introduisez les données en tant qu'entrées utilisateur.

Rappelez-vous, il n'y a qu'une seule chose en cours d'exécution à la fois, donc si vous boucle à travers votre progamme, rien d'autre obtient jamais la chance de courir, même vos événements WebSocket obtiendrez juste mis en attente, puis déclencher tous après votre boucle est terminée .

+0

Nous vous remercions de votre réponse. Ce truc de continuation-passing pourrait fonctionner. Nous allons vérifier. –

1

Je pense que la réponse de Ivo est fondamentalement juste, mais je vais essayer de reformuler et ajouter quelques suggestions:

  1. retardée() devrait être une action de congé, pas un noeud interne de l'AST - en supposant que j'ai la bonne sémantique voulue: elle devrait se bloquer jusqu'à ce que les données soient reçues, puis terminer/terminer.

  2. Vous avez en quelque sorte besoin d'émuler la notion de compteur de programme et d'une trame de pile. Pour les actions réellement construites (telles que la boucle), le cadre de pile doit contenir la valeur actuelle de la variable de boucle et la position actuelle dans la séquence d'instructions. Vous ne devriez pas recycler vos objets AST pour cet état, car la même boucle peut être exécutée simultanément plusieurs fois (en supposant plusieurs clients).

  3. L'état a une opération "suivante", exécutant une étape d'exécution. Retardé, lors de son premier appel, renvoie immédiatement avec un code indiquant que l'exécution ultérieure n'est pas souhaitée. Lorsqu'il est appelé la deuxième fois, il ne fait rien (indiquant que l'action est terminée).

+0

Je ne sais pas ce que vous voulez dire par Retardé étant une action de congé. Retardé est sur une représentation d'une instruction qui nécessite certaines données asynchrones, et doit donc s'arrêter et attendre. Le reste, ça sonne à peu près juste, et nous en avons déjà essayé une variante, mais ça a vraiment dérapé. Pour de nombreuses variables différentes. Peut-être que nous devrions essayer à nouveau, merci –