August 20, 2013

Ticks, Animation, and Queueing in TurtleBits

A note on queuing and animation in TurtleBits.

RichB comments that the following program hangs the browser in TurtleBits:

# Program 1: will hang your tab.
while true
  turnto lastmousemove
  fd 10
  wait 1

This program is perfectly valid Coffeescript, but running it will freeze your browser tab. If you bring up the debugger and force the program to pause, you will find that it is forever in the middle of looping super-fast within the infinite "while" loop without drawing anything interesting on the screen.

A couple solutions below....

The timeline for Program 1 looks like this:

Program 1: browser loads the program while true loops forever. . . .         (never terminates)

In contrast, the following very similar program will not freeze the browser at all. It will work as expected.

# Program 2.
speed Infinity
tick 2, ->
  turnto lastmousemove
  fd 10

Program 2: browser loads the program tick browser renders tick browser renders tick browser...

The "tick" function sets up a function to be called repeatedly at a given rate per second. Since the rate is 2, the requested movement will happen twice per second. Between ticks, the browser is not busy running our program, so it is free to render graphics, deal with the scrollbar and the back button, and other mundane tasks.

Program 2 is probably the clearest way to write what Program 1 is trying to do: really the intent isn't literally to repeat something forever, but to do something at regular intervals. Animation programs are traditionally written as a sequence of frames, like Program 2.

Turtle Animations Are Queued

But the first program has a "wait" which seems like it should pause things - why does it keep the browser frozen up?

The key thing to understand is that turtle motion is queued. Your computer is much too fast for students to see and understand the individual steps of turtle motion, so when you write "fd 10", actually your program is putting the "fd" command on a queue for the browser to paint and animate over time. The same goes for "turnto" and "wait". The "wait" function queues a delay in the animation: it does not pause the actual program.

When you run Program 1, it starts the computer at the task of building an infinite queue of turtle motions. This list will grow to be billions long before the computer will start noticing any problems. So that is why the browser tab hangs: it is stuck inside your program, building an ever longer list of turtle motions to do at some future time.

A Finite Loop Does Not Hang

If we make the loop non-infinite, then the program stops and lets the browser go through the list and paint the animation.

# Program 3
for x in [1..1000]
  turnto lastmousemove
  fd 10
  wait 1

Interestingly, even though this program defines 3000 seconds worth of animations, the program itself completes in about 0.03 seconds.

That is because the functions "turnto", "fd", and "wait" are not executing motion immediately. They are just queuing the motion for animation later. The timeline looks like this:

Program 3: browser loads the program for x in [1..1000] browser renders 3000 seconds of animation browser is idle

However, this finite loop is not really the best solution to this problem. For a solution that will allow our loop to be infinite without hanging the browser, see the example with await/defer below.

Infinite Speed and Interactive Animation

There is a way to make turtle motion happen immediately: set the speed to Infinity. When you set the speed to Infinity, your program will do all the motion immediately. Normally this will be too fast to see, so it will appear that all the drawing finished in an instant.

The normal way to write an interactive animation is to set the speed to Infinity, then use the "tick" function to execute instant motions at short intervals of time. Within each tick, we can write logic that decide on motion that responds to user actions.

Some Thoughts on Threading

The reason the browser cannot paint at the same time as your program is running is that browser tabs are single-threaded: they can only do one thing at once. This is a basic limitation of the web browser programming model, but it is a good design. Over the years single-threading has also evolved as the easiest way to write interactive programs.

If you allow multiple threads to manage your graphics at once, then you face the dilemma of how to prevent multiple threads from interfering with each other. For example, suppose a counter starts at zero, and two threads both run "counter++" at the same time. Should the answer end up being 1 or 2? It turns out that with multithreading, the result could end up either 1 or 2 after both programs run, depending on exactly how simultaneously the threads do their work. Special locks need to be arranged to guarantee that the sensible answer (2) is what you get, and in a complicated program, it is very difficult to verify that the locks are done correctly.

Because of this type of interference, modern programming models for complicated user interfaces tend to avoid multithreading. Concurrency is managed using events that trigger of time such as the "tick" event. You do not actually run two functions simultaneously: instead, you schedule functions to be run at future times, and they are run one at a time.

Why not WebWorkers?

Modern browsers actually do support multithreading. If you run a script in a WebWorker, then it runs on a separate thread (truly) simultaneously to the main thread. An infinite loop in a WebWorker will not lock up the browser.

When designing TurtleBits, the first dilemma was to decide whether or not to run turtlebits programs on a WebWorker thread so that "while true" programs could be written safely. I decided against this approach for a few reasons:

  1. Real browser programs are not written this way. Seems odd to teach something that is not actually done in practice.
  2. Turtle programs would be too isolated from the webpage. A WebWorker has no direct access to the DOM, so we would lose the opportunity for kids learn about HTML.
  3. The main reason to want concurrency is to write infinite "while true" loops that interact with the user. But a WebWorker is too isolated from the DOM to make interaction very flexible.

Other Possible Models

There are still more alternatives that try to split the difference between event-based and thread-based concurrency.

For example Scratch has a hybrid model. They do not use full multithreaded concurrency. Instead, they allow context switching at every loop.

The Scratch interpreter takes control and switches between different "stacks" (different programs) whenever a program repeats a loop. So if you write a loop in Scratch, you are actually (effectively) scheduling future iterations of the loop to happen some time in the future, possibly after other unrelated parts of your program have run to deal with animations or interactions.

The trick done by Scratch, again, is something that isn't actually done by professional programmers in practice, because you typically don't want your "while" loop to be automatically inserting hidden concurrency. If you ask for things to be repeated a few times, you want them repeated right away.

However, there have been some attempts to bring this sort of "deferred execution" technique into a mainstream programming language. The key difference with Scratch is that mainstream approaches allow you to yield control explicitly at particular moments in your program instead of automatically at every loop. A simple example of this idiom is the "yield" operator in python generators. Another approach is the python variant called stackless python that supports full-fledged tasks that can yield control when waiting on a channel. And a variant of Coffeescript called Iced Cofeescript will introduces an an "await" keyword that can yield control and await completion callbacks within a loop.

Iced Coffeescript

If TurtleBits used Iced Coffeescript instead of vanilla Coffeescript, you could write a program that looks something like this:

# Program 4: await/defer from iced Coffeescript.
while true
  turnto lastmousemove
  fd 10
  await done defer()

The magical line "await done defer()" tells the compiler to pause the program in the middle of the "while" loop and wait for the turtle animation to stop before continuing the loop.

Program 4: browser loads the program 1st loop await animation done 2nd loop await animation done 3rd loop await...

During the pause after an "await" is hit, the program is not running, and the browser is free to render the turtle animation on the screen. As soon as the "done" callback triggers (i.e., when animation is done), the program starts running again, starting with the code after the "await" - that is, it loops again. This process continues indefinitely.

I originally considered adding Iced CoffeeScript to TurtleBits, but I hesitated mainly because (1) there doesn't seem to be a sizable community around Iced, and (2) I am not sure the "await/defer" idiom is any clearer than just teaching kids to use "tick".

Opinions? Should TurtleBits use Iced CoffeeScript so students can play with infinite while loops?

Here is a little blog article from Dave Herman on why stackless-python-style coroutines shouldn't be used in web standards (but why yield-style or iced-coffeescript-style continuations might make sense).

Update: after showing this problem to a few people and thinking about it, I decided to add iced coffeescript to turtle bits. The "await done defer()" example above now works, and other things such as "read", can also be done more cleanly. Will blog about it soon.

Posted by David at August 20, 2013 08:17 PM
Post a comment

Remember personal info?