Will Thimbleby

Using Tailspin, a flexible and reversible Javascript interpreter, for algorithm visualisation merely scratches the surface of what it can do.

One of the more interesting opportunities is interactive learning environments. There are many online interactive Javascript websites, but all use the browser’s interpreter or server-side execution of code. Websites like Code Academy and Khan Academy do a pretty good job, but they are limited by the black-box execution of code in the browser.

By using Tailspin which provides access to the inner workings of the interpreter it is possible to expand what can be done in these online interactive coding websites.

Modelled on the pointer programming puzzles of Jhavé, I have used Tailspin to create a small website for interactive Javascript programming problems. Access to Tailspin’s workings during execution allows the visualise of any user supplied program as it runs, and enables them to see how their solution succeeds or fails.

Among other things it provides:

• Live code errors and warnings
• A range of programming puzzles
• Automatic saving of your progress
• Scrubbable execution of your Javascript program
• A visualisation of your program running that shows the values and lists in your program
• A visualisation that animates as you scrub through the program execution

Check it out here: JS problems — How will you fare?

Stepping through code in the browser is very cool, but it can already be done with a bit of work by enabling developer mode on your browser and writing your own .html and .js files.

What you can’t do is go back in time.

Which leads me to Tailspin. It is a fully reversible, standards-compliant¹, meta-circular Javascript interpreter. As well as running in the browser and allowing algorithms to be visualised, it can run code both forwards and backwards.

A reversible interpreter provides some really interesting opportunities for exploration and education. So far I have focused on algorithm visualisation where reversibility makes it possible to scrub through the execution of algorithms. This is not just fun, it transforms the experience of understanding the algorithm. You can see this used to great effect in the Algorithm Wiki and in the depth-first traversal example below. The code that is highlighted on the left-hand side is the actual code that is running.

All the visualisations on the Algorithm Wiki have been updated and support reversible execution. You can now scrub through algorithms such as Factorial, Insertion Sort or Fisher-Yates Shuffle.

I have also updated the in-browser IDE to support reversibility, so you can step backward through your own code. Even after your code has hit an exception or ended, you can step backwards into the code to see what happened.

A while ago I implemented an algorithm from Wikipedia. It turned out it had a subtle bug. A single less-than instead of a greater-than. Unfortunately I spent a long time finding the problem, but it did start me thinking about how to improve pseudo-code on the web.

In an interactive medium there is little reason why algorithms should still be presented as static text. Text which can not be visualised, verified or checked in any way. Algorithms are complex beasts and ensuring they are correct is tricky and understanding them takes time. Running an algorithm is essential for correctness and stepping through an algorithm is extremely helpful for comprehension.

This meshed with something a few things I had been tinkering with for a while. A full Javascript-in-Javascript interpreter, Narcissus, rewritten in continuation-passing style to allow more control over the interpretation. Using an interpreter on-top of the browser’s native interpreter allows code to be paused and controlled in ways that are impossible when running native Javascript code in the browser.

The result is Javascript code that runs in the browser but can be controlled and visualised. Code that a user can pause and step through to see the control flow. Code which is verifiable and has a much better chance of being correct. Real code not pseudo-code. Right in your web-browser. As an example here is an interpreter and visualisation which runs the Javascript code for the bubble sort algorithm:

This is pretty neat, but it is a bit more interesting taking it a bit further. On top of the Javascript interpreter I built an experimental wiki http://will.thimbleby.net/algorithms to explore making algorithms interactive on the web. It’s experimental because there are still lots of things to do and to figure out (eg. security), but I think it is very promising.

After spending a while looking for a decent scanline flood fill algorithm and not finding one, I built my own. The above interactive example shows how both scanline and simple flood filling work. You can draw and test any of the four different flood fills to see how they compare. Once you have filled an area, clicking and holding the “Show pixels tested” button shows a “heat” map of the number of times each pixel has been tested (from green:1 to red:8).

The scanline flood fill algorithm works by scanning a line, and adding ranges on the next/previous lines to a stack. For a shape with no loops or thin walls which are filled on both sides the scanline algorithm will only test each pixel once. It achieves this by skipping testing the range of pixels that the current line was filled from.

A rough outline of the algorithm is:

1. Add the starting range [x, y] to a stack.
2. While there is a range to fill:
   1. Extend the current range left and right.
   2. Add new ranges on the previous and next lines that overlap the current range to the stack. Skip testing the range of pixels that the current range was created from.

This implementation is nice, clean, fast and supports 8-way (diagonal) filling. All the values needed are passed in as parameters to floodFillScanline. The test(x, y) function returns true for pixels that need filling, the paint(x, y) function paints the pixel. This function will fill all connected pixels starting from (x, y) as long as test and paint are defined over x:[0, width) and y:[0, height) and a painted pixel does not test true.

function floodFillScanline(x, y, width, height, diagonal, test, paint) {
    // xMin, xMax, y, down[true] / up[false], extendLeft, extendRight
    var ranges = [[x, x, y, null, true, true]];
    paint(x, y);

    while(ranges.length) {
        var r = ranges.pop();
        var down = r[3] === true;
        var up =   r[3] === false;

        // extendLeft
        var minX = r[0];
        var y = r[2];
        if(r[4]) {
            while(minX>0 && test(minX-1, y)) {
                minX--;
                paint(minX, y);
            }
        }
        var maxX = r[1];
        // extendRight
        if(r[5]) {
            while(maxX<width-1 && test(maxX+1, y)) {
                maxX++;
                paint(maxX, y);
            }
        }

        if(diagonal) {
            // extend range looked at for next lines
            if(minX>0) minX--;
            if(maxX<width-1) maxX++;
        }
        else {
            // extend range ignored from previous line
            r[0]--;
            r[1]++;
        }

        function addNextLine(newY, isNext, downwards) {
            var rMinX = minX;
            var inRange = false;
            for(var x=minX; x<=maxX; x++) {
                // skip testing, if testing previous line within previous range
                var empty = (isNext || (x<r[0] || x>r[1])) && test(x, newY);
                if(!inRange && empty) {
                    rMinX = x;
                    inRange = true;
                }
                else if(inRange && !empty) {
                    ranges.push([rMinX, x-1, newY, downwards, rMinX==minX, false]);
                    inRange = false;
                }
                if(inRange) {
                    paint(x, newY);
                }
                // skip
                if(!isNext && x==r[0]) {
                    x = r[1];
                }
            }
            if(inRange) {
                ranges.push([rMinX, x-1, newY, downwards, rMinX==minX, true]);
            }
        }

        if(y<height)
            addNextLine(y+1, !up, true);
        if(y>0)
            addNextLine(y-1, !down, false);
    }
}

A* is a well known and popular shortest path algorithm. With the correct heuristic it is efficient and finds the optimal solution. Here’s a fun and simple Javascript implementation that makes use of the canvas element. The code is free (public domain) for anyone to use or improve.

The above demo lets you play with the algorithm. By clicking you can add/remove walls or drag the start (blue) or end (red) nodes. The shortest route is highlighted by a red line and the searched nodes are drawn from yellow to green by distance from the start node.

The options to the right of the map control how the path is calculated. Diagonal movement is considered as the same cost as straight movement, but the tweak diagonal cost toggle adjust the diagonal cost to be slightly more expensive so that nicer looking paths are preferred. This doesn’t alter the length of the found path only the number of nodes searched and the path’s appearance.

A tie breaker can be used to decided which nodes with the same estimated cost are preferred. Preferring new nodes is a very simple and efficient tie breaker. The prefer new nodes option toggles preferring new/old nodes, if old nodes are preferred then A* performs much worse especially for empty spaces. The dot product tie breaker is a different tie breaker that chooses paths that are closer to the straight line between the start and end for equal paths.

For more information on the A* algorithm and path finding I would recommend Amit’s A* Pages.

There has been plenty of interest in MISC, that warrant some quick comments.

– The source code is now available here: MISC source (about 3000 lines of Java code and 350 of MISC). Hopefully you’ll find it useful. It might also be interesting/confusing to look at the bootstrap file.
– The mathematical operators now accept multiple operands like [+ 2 3 4 5]
– Yes I like square brackets (Smalltalk, ObjC) it saves the shift key
– Quoting is required in lamda/let because there are no special forms in MISC. This means that it is possible to write lambda, let and if etc. without macros and also to have the results of an expression provide the arguments for these functions, eg. [let [union '[a:3] '[b:4]] '[+ a b]] which is not possible to write in this fashion in Lisp, because in Lisp let is a special form and does not evaluate it’s first argument.
– Creating new things and exploring ideas are always important, which is what MISC achieves for me.

MISC has been a long time in the creation. It started when I got sick of XML’s lack of consistent structure and heavy markup. I wanted something consistent and clean like LISP but with a more general basic data structure. This was the initial spark “LISP with maps instead of lists”.

• [if [> 5 10] then:[+ 5 10] else:[– 5 10]]
• [let '[square:[lambda '[x:1] '[* x x]]]
    '[square 12]
  ]
• [take 20 [numbers from:0]]

After writing some example pseudo code to see what it would look like, I wrote a simple version in a couple of days. Since that speedy start the actual design with the complexities of a language have taken a very long time to finish. I changed the basic structure several times to fix major issues I hadn’t thought of and I switched the design from an eager language to a lazy language which I felt matched the base data structure of maps better.

I became interested in how rich metadata as basic part of the language and the source code could enable powerful reflective programming, like documentation built into source code. All these different ideas and designs added up and every time I thought “Would it not be easier if it just worked like language X,” I had to tell myself if it did there’d be no point in writing MISC. Thus the result is not a language for real-world use but one that I hope embodies many different unique and novel design decisions in a way that triggers thoughts and ideas in those that take the time to play with it.

What’s different and why you should be interested:

• Novel LISP-like language
• Homoiconicity (ie. source code that is data) using maps
• A great lazy data-language
• Cool stuff with metadata
• A metacircular– interpreter and syntax-colourer

Not only that; but it runs as an applet with some neat inline documentation: MISC

Just for fun here are a couple of applet based roguelikes I wrote a while back. The first is a reasonable example of a simple and concise roguelike. The second is an attempt at a roguelike with directional player facing, it also adds directional monsters, hearing and sprinting. The above-right picture shows an unknown monster sneaking up on the player from behind and an ant, above-right of the player, looking towards the player.

I hope these are somehow informative/fun for someone. The source code for both applets is public domain.

eWeek described the top 5 programming languages to learn (if you want a job) as:

• PHP
• C#
• AJAX
• Javascript
• Perl

Not the most exciting list. My top 5 languages to learn (if you want to learn something) are:

• Scheme — The essentials of programming without syntax. It also allows for some crazy metaprogramming.
• C — It’s everywhere, has become the defacto syntax, and it forces you to learn about manual memory management, pointers, arrays, bits etc…
• Simple assembly — Lets you deal directly with registers and interrupts. I learnt Z80 assembly but I would recommend learning PIC, AVR or MSP430 programming. It’s much more fun than it sounds and it makes you appreciate every other language out there.
• Haskell — Pure, functional, lazy and strongly typed. A head-job but it will stretch your thinking.
• Prolog — A declarative language, you describe facts and rules and hopefully Prolog does the rest.

The top 5 languages that I would like an excuse to learn are:

• Erlang — A process based language with lots of interesting ideas.
• Lua — An extremely light-weight and fast scripting language.
• Objective Caml — A statically typed functional language.
• C# — Java like but with some additional good ideas.
• Squeak — A language with its own OS and GUI!

Scripting with JavaScript in Cocoa is a brilliant way to add scripts and a language to your app. Even better it is extremely easy. My article is a great place to start. I’ve just updated it thanks to Jack Nutting who fixed a bug on Leopard.  

Next Page »