Will Thimbleby

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.

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.  

I found WWDC a disappointment. It felt like half last years conference and half a web conference. I went last year and there are better places to learn AJAX. So it is nice to see Apple doing interesting things.

LLVM (Low Level Virtual Machine), which Apple is involved in, could be described as compiler infrastructure. That is it can be used to replace various aspects of compilers. It is very clean, neat and well designed system that provides optimisations at various levels, including compile and run-time.

Why is this neat? Well it provides very good optimisations. One comparison has the LLVM JIT performing 20% faster than gcc4.2 and 100% faster than gcc4.0.1 (which Apple currently ships) for one benchmark. For those that are interested I think the best way to learn about LLVM is to read the experiences of Reid Spencer’s implementation of creating Stacker which is a Forth-like language which compiles to an LLVM backend.

There is already a C/C++ LLVM frontend and Apple is working on a very nice new C frontend. Have a look at some interesting presentations. The presentation I thought was most interesting is Steve Naroff’s New LLVM C Front-end. Especially look at the error messages it can produce.

Apple also use it for GLSL just in time compilation to provide OpenGL shader support for features unsupported by video cards. Chris Lattner also presents an overview of the more technical side of this functionality.

I just got back from Apple’s WWDC and I’ve decided to start a blog. I think there’s room for at least one more. There are too many things I want put online that do not fit into an article format, thus this experiment. If I run out of intelligent things to say, I’ll try to stop.

The focus here will be on programming and user interaction, I intend to write intelligent things and as I am a user interaction researcher those are my areas of expertise.