The biggest issue in running anything within a browser is that it has to by 'asynchronous'. I'm still not completely sure about all the ins and outs of this, but what it essentially means is that anything the script does goes on hidden from the display of the browser, and it only gets updated when control is ceded back to the browser.
This causes problems for interactivity, because in PEBL, you write code to maybe draw something, wait a while, then move it and redraw, then wait for a response, etc. But to run in a browser, you have to essentially turn this inside out--whenever you want to draw something, you need to sort of 'pause' execution of where you are at, return control to the browser, by exiting the function, and reprogram a future event when you want to process more stuff.
For most games that have been ported to emscripten, this is not too problematic, because they are written with a loop that updates everything at a (hopefully) fixed interval. But it presents a challenge for PEBL because typically the execution chain is handled by an 'evaluator' that recursively processes a parse tree.
First, some basics on how PEBL works. When you execute a PEBL script, the text you write in a file first gets parsed by a compiler written in yacc/bison production rules. As the text is parsed, it creates a binary tree nodes that defines the set of operations it will later execute. So, if you write a statement:
(5 + 2) + 8
It will eventually get parsed into a set of nodes sort of like the following:
N1: Plus
/ \
N2: Plus N5: 8
/ \
N3: 5 N4: 2
This parsing all happens at the outset, before any part of the experiment is run. Later, once PEBL is completely loaded, an evaluator operates recursively on this tree, using a stack to keep track of its intermediate data values. For example, the following iterations would produce the result:
==================================================================== Step Recursive Depth Node Actions Stack ==================================================================== 1 1 N1 Evaluate N2 - --------------------------------------------------------------------- 2 .2 N2 Evaluate N3 - --------------------------------------------------------------------- 3 ..3 N3 Push 5 5 --------------------------------------------------------------------- 4 .2 N2 Evaluate N4 5 --------------------------------------------------------------------- 5 ..3 N5 Push 2 2|5 --------------------------------------------------------------------- 6 .2 N2 Pop 2, Pop 5, Push 2+5 7 --------------------------------------------------------------------- 7 1 N1 Evaluate N5 7 --------------------------------------------------------------------- 8 .2 N5 Push 8 8|7 --------------------------------------------------------------------- 9 1 N1 Pop 8, Pop 7, Push 8+7 15 ====================================================================
At the end of this, we get our answer at the top of the stack. But notice that our evaluation of Node 1 occurred 3 different times; we recursively executed a branch of the tree and eventually came back up to the branch we care about, where we then recursively executed the other branch, came back up, and finally added the two together at the current level.
This recursive strategy is very elegant, but causes us some problems for putting it in Javascript. Because once you run the evaluation on the first node, the entire tree gets evaluated 'ballistically' without any further intervention from a higher-up. This includes all interactivity, display mechanics, etc. What we would love is for the evaluator to 'pause' and put itself on hold after each important processing step, returning control to the browser between each step (or possibly less often to improve performance).
EMSCRIPTEN offers a way to execute chunks of a main loop asynchronously. Essentially, you create a single-cycle of your main execution loop that does whatever processing it needs. You can then either have the javascript shell execute that step at a fixed rate, or daisy chain the main loop so that right before the loop completes, you instruct the browser to run the function again at a point slightly in the future (Like Alon--kripken--did for the port of 'me and my shadow' to emscripten) Then, before it gets run, the browser has a chance to update, poll for input events, etc. As far as I can tell, neither approach can be done with a recursive evaluator.
This is because a higher-up node NEEDS the result of the lower-level evaluation to continue, and so if I were to simply call each subsequent Evaluation() step asynchronously, the stack would not get updated in the right order and everything would fall apart. I know--I tried this in several ways before almost giving up.
What I need to do here, I think, is to change the PEBL's evaluator to be non-recursive. I'm just spec'ing this out now, but I think it can be done with two changes. First, by creating a second 'evaluation stack' which will keep track of where we are at in the evaluation sequence, we can run one step of the evaluator, exit, and resume later. The second thing we probably need to do is split up the execution of some of the function evaluations into two parts; a 'pre' step and a 'post' step. So in the example above, the 'plus' operator would have a pre step where it pushes three operations onto the execution stack, instructions to handle N2, N5, and finally a plus_tail operation. Later, the plus_tail operation would simply pop two values off the stack and add them together.
Stay tuned for more as I try this major refactoring. This is really the main obstacle for PEBL in the browser, and if it succeeds, I think all the rest is just cleanup and improvements.
1 comment:
very interesting! I am looking forward for your updates.
Post a Comment